w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-rectangular-scan-converter.c
Go to the documentation of this file.
1 /* cairo - a vector graphics library with display and print output
2  *
3  * Copyright © 2009 Intel Corporation
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it either under the terms of the GNU Lesser General Public
7  * License version 2.1 as published by the Free Software Foundation
8  * (the "LGPL") or, at your option, under the terms of the Mozilla
9  * Public License Version 1.1 (the "MPL"). If you do not alter this
10  * notice, a recipient may use your version of this file under either
11  * the MPL or the LGPL.
12  *
13  * You should have received a copy of the LGPL along with this library
14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16  * You should have received a copy of the MPL along with this library
17  * in the file COPYING-MPL-1.1
18  *
19  * The contents of this file are subject to the Mozilla Public License
20  * Version 1.1 (the "License"); you may not use this file except in
21  * compliance with the License. You may obtain a copy of the License at
22  * http://www.mozilla.org/MPL/
23  *
24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26  * the specific language governing rights and limitations.
27  *
28  * The Original Code is the cairo graphics library.
29  *
30  * Contributor(s):
31  * Chris Wilson <chris@chris-wilson.co.uk>
32  */
33 
34 #include "cairoint.h"
35 
36 #include "cairo-combsort-inline.h"
37 #include "cairo-error-private.h"
38 #include "cairo-freelist-private.h"
39 #include "cairo-list-private.h"
40 #include "cairo-spans-private.h"
41 
42 #include <setjmp.h>
43 
44 typedef struct _rectangle {
45  struct _rectangle *next, *prev;
49  int dir;
51 
52 #define UNROLL3(x) x x x
53 
54 /* the parent is always given by index/2 */
55 #define PQ_PARENT_INDEX(i) ((i) >> 1)
56 #define PQ_FIRST_ENTRY 1
57 
58 /* left and right children are index * 2 and (index * 2) +1 respectively */
59 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
60 
61 typedef struct _pqueue {
62  int size, max_size;
63 
67 
68 typedef struct {
74  int32_t xmin, xmax;
75 
76  struct coverage {
77  struct cell {
78  struct cell *prev, *next;
79  int x, covered, uncovered;
80  } head, tail, *cursor;
81  unsigned int count;
84 
87  unsigned int num_spans;
88  unsigned int size_spans;
89 
90  jmp_buf jmpbuf;
91 } sweep_line_t;
92 
93 static inline int
95  const rectangle_t *b)
96 {
97  int cmp;
98 
99  cmp = a->top_y - b->top_y;
100  if (cmp)
101  return cmp;
102 
103  return a->left - b->left;
104 }
105 
106 static inline int
108  const rectangle_t *b)
109 {
110  return a->bottom_y - b->bottom_y;
111 }
112 
113 static inline void
115 {
117  pq->size = 0;
118 
119  pq->elements = pq->elements_embedded;
121 }
122 
123 static inline void
125 {
126  if (pq->elements != pq->elements_embedded)
127  free (pq->elements);
128 }
129 
130 static cairo_bool_t
132 {
133  rectangle_t **new_elements;
134  pq->max_size *= 2;
135 
136  if (pq->elements == pq->elements_embedded) {
137  new_elements = _cairo_malloc_ab (pq->max_size,
138  sizeof (rectangle_t *));
139  if (unlikely (new_elements == NULL))
140  return FALSE;
141 
142  memcpy (new_elements, pq->elements_embedded,
143  sizeof (pq->elements_embedded));
144  } else {
145  new_elements = _cairo_realloc_ab (pq->elements,
146  pq->max_size,
147  sizeof (rectangle_t *));
148  if (unlikely (new_elements == NULL))
149  return FALSE;
150  }
151 
152  pq->elements = new_elements;
153  return TRUE;
154 }
155 
156 static inline void
158 {
160  int i, parent;
161 
162  if (unlikely (sweep->stop.size + 1 == sweep->stop.max_size)) {
163  if (unlikely (! pqueue_grow (&sweep->stop)))
164  longjmp (sweep->jmpbuf,
166  }
167 
168  elements = sweep->stop.elements;
169  for (i = ++sweep->stop.size;
170  i != PQ_FIRST_ENTRY &&
171  rectangle_compare_stop (rectangle,
172  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
173  i = parent)
174  {
176  }
177 
178  elements[i] = rectangle;
179 }
180 
181 static inline void
183 {
184  rectangle_t **elements = pq->elements;
185  rectangle_t *tail;
186  int child, i;
187 
188  tail = elements[pq->size--];
189  if (pq->size == 0) {
191  return;
192  }
193 
194  for (i = PQ_FIRST_ENTRY;
195  (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
196  i = child)
197  {
198  if (child != pq->size &&
200  elements[child]) < 0)
201  {
202  child++;
203  }
204 
206  break;
207 
208  elements[i] = elements[child];
209  }
210  elements[i] = tail;
211 }
212 
213 static inline rectangle_t *
215 {
216  return sweep->stop.elements[PQ_FIRST_ENTRY];
217 }
218 
220 
221 static void
223 {
224  sweep->head.left = INT_MIN;
225  sweep->head.next = &sweep->tail;
226  sweep->tail.left = INT_MAX;
227  sweep->tail.prev = &sweep->head;
228  sweep->insert_cursor = &sweep->tail;
229 
230  _cairo_freepool_init (&sweep->coverage.pool, sizeof (struct cell));
231 
232  sweep->spans = sweep->spans_stack;
233  sweep->size_spans = ARRAY_LENGTH (sweep->spans_stack);
234 
235  sweep->coverage.head.prev = NULL;
236  sweep->coverage.head.x = INT_MIN;
237  sweep->coverage.tail.next = NULL;
238  sweep->coverage.tail.x = INT_MAX;
239 
240  pqueue_init (&sweep->stop);
241 }
242 
243 static void
245 {
247  pqueue_fini (&sweep->stop);
248 
249  if (sweep->spans != sweep->spans_stack)
250  free (sweep->spans);
251 }
252 
253 static inline void
254 add_cell (sweep_line_t *sweep, int x, int covered, int uncovered)
255 {
256  struct cell *cell;
257 
258  cell = sweep->coverage.cursor;
259  if (cell->x > x) {
260  do {
261  UNROLL3({
262  if (cell->prev->x < x)
263  break;
264  cell = cell->prev;
265  })
266  } while (TRUE);
267  } else {
268  if (cell->x == x)
269  goto found;
270 
271  do {
272  UNROLL3({
273  cell = cell->next;
274  if (cell->x >= x)
275  break;
276  })
277  } while (TRUE);
278  }
279 
280  if (x != cell->x) {
281  struct cell *c;
282 
283  sweep->coverage.count++;
284 
285  c = _cairo_freepool_alloc (&sweep->coverage.pool);
286  if (unlikely (c == NULL)) {
287  longjmp (sweep->jmpbuf,
289  }
290 
291  cell->prev->next = c;
292  c->prev = cell->prev;
293  c->next = cell;
294  cell->prev = c;
295 
296  c->x = x;
297  c->covered = 0;
298  c->uncovered = 0;
299 
300  cell = c;
301  }
302 
303 found:
304  cell->covered += covered;
305  cell->uncovered += uncovered;
306  sweep->coverage.cursor = cell;
307 }
308 
309 static inline void
311 {
312  int32_t y = sweep->current_y;
313  rectangle_t *rectangle;
314  int coverage, prev_coverage;
315  int prev_x;
316  struct cell *cell;
317 
318  sweep->num_spans = 0;
319  if (sweep->head.next == &sweep->tail)
320  return;
321 
322  sweep->coverage.head.next = &sweep->coverage.tail;
323  sweep->coverage.tail.prev = &sweep->coverage.head;
324  sweep->coverage.cursor = &sweep->coverage.tail;
325  sweep->coverage.count = 0;
326 
327  /* XXX cell coverage only changes when a rectangle appears or
328  * disappears. Try only modifying coverage at such times.
329  */
330  for (rectangle = sweep->head.next;
331  rectangle != &sweep->tail;
332  rectangle = rectangle->next)
333  {
334  int height;
335  int frac, i;
336 
337  if (y == rectangle->bottom_y) {
338  height = rectangle->bottom & CAIRO_FIXED_FRAC_MASK;
339  if (height == 0)
340  continue;
341  } else
343  if (y == rectangle->top_y)
344  height -= rectangle->top & CAIRO_FIXED_FRAC_MASK;
345  height *= rectangle->dir;
346 
347  i = _cairo_fixed_integer_part (rectangle->left),
348  frac = _cairo_fixed_fractional_part (rectangle->left);
349  add_cell (sweep, i,
350  (CAIRO_FIXED_ONE-frac) * height,
351  frac * height);
352 
353  i = _cairo_fixed_integer_part (rectangle->right),
354  frac = _cairo_fixed_fractional_part (rectangle->right);
355  add_cell (sweep, i,
356  -(CAIRO_FIXED_ONE-frac) * height,
357  -frac * height);
358  }
359 
360  if (2*sweep->coverage.count >= sweep->size_spans) {
361  unsigned size;
362 
363  size = sweep->size_spans;
364  while (size <= 2*sweep->coverage.count)
365  size <<= 1;
366 
367  if (sweep->spans != sweep->spans_stack)
368  free (sweep->spans);
369 
370  sweep->spans = _cairo_malloc_ab (size, sizeof (cairo_half_open_span_t));
371  if (unlikely (sweep->spans == NULL))
372  longjmp (sweep->jmpbuf, _cairo_error (CAIRO_STATUS_NO_MEMORY));
373 
374  sweep->size_spans = size;
375  }
376 
377  prev_coverage = coverage = 0;
378  prev_x = INT_MIN;
379  for (cell = sweep->coverage.head.next; cell != &sweep->coverage.tail; cell = cell->next) {
380  if (cell->x != prev_x && coverage != prev_coverage) {
381  int n = sweep->num_spans++;
382  int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
383  sweep->spans[n].x = prev_x;
384  sweep->spans[n].inverse = 0;
385  sweep->spans[n].coverage = c - (c >> 8);
386  prev_coverage = coverage;
387  }
388 
389  coverage += cell->covered;
390  if (coverage != prev_coverage) {
391  int n = sweep->num_spans++;
392  int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
393  sweep->spans[n].x = cell->x;
394  sweep->spans[n].inverse = 0;
395  sweep->spans[n].coverage = c - (c >> 8);
396  prev_coverage = coverage;
397  }
398  coverage += cell->uncovered;
399  prev_x = cell->x + 1;
400  }
402 
403  if (sweep->num_spans) {
404  if (prev_x <= sweep->xmax) {
405  int n = sweep->num_spans++;
406  int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
407  sweep->spans[n].x = prev_x;
408  sweep->spans[n].inverse = 0;
409  sweep->spans[n].coverage = c - (c >> 8);
410  }
411 
412  if (coverage && prev_x < sweep->xmax) {
413  int n = sweep->num_spans++;
414  sweep->spans[n].x = sweep->xmax;
415  sweep->spans[n].inverse = 1;
416  sweep->spans[n].coverage = 0;
417  }
418  }
419 }
420 
421 static inline void
423  rectangle_t *rectangle)
424 {
425  if (sweep->insert_cursor == rectangle)
426  sweep->insert_cursor = rectangle->next;
427 
428  rectangle->prev->next = rectangle->next;
429  rectangle->next->prev = rectangle->prev;
430 
431  pqueue_pop (&sweep->stop);
432 }
433 
434 static inline void
436  rectangle_t *rectangle)
437 {
438  rectangle_t *pos;
439 
440  pos = sweep->insert_cursor;
441  if (pos->left != rectangle->left) {
442  if (pos->left > rectangle->left) {
443  do {
444  UNROLL3({
445  if (pos->prev->left < rectangle->left)
446  break;
447  pos = pos->prev;
448  })
449  } while (TRUE);
450  } else {
451  do {
452  UNROLL3({
453  pos = pos->next;
454  if (pos->left >= rectangle->left)
455  break;
456  });
457  } while (TRUE);
458  }
459  }
460 
461  pos->prev->next = rectangle;
462  rectangle->prev = pos->prev;
463  rectangle->next = pos;
464  pos->prev = rectangle;
465  sweep->insert_cursor = rectangle;
466 
467  pqueue_push (sweep, rectangle);
468 }
469 
470 static void
472  cairo_span_renderer_t *renderer,
473  int height)
474 {
476 
477  _active_edges_to_spans (sweep_line);
478 
479  status = renderer->render_rows (renderer,
480  sweep_line->current_y, height,
481  sweep_line->spans,
482  sweep_line->num_spans);
483  if (unlikely (status))
484  longjmp (sweep_line->jmpbuf, status);
485 }
486 
487 static cairo_status_t
489  cairo_span_renderer_t *renderer,
490  rectangle_t **rectangles)
491 {
492  sweep_line_t sweep_line;
495 
496  sweep_line_init (&sweep_line);
497  sweep_line.xmin = _cairo_fixed_integer_part (self->extents.p1.x);
498  sweep_line.xmax = _cairo_fixed_integer_part (self->extents.p2.x);
499  sweep_line.start = rectangles;
500  if ((status = setjmp (sweep_line.jmpbuf)))
501  goto out;
502 
503  sweep_line.current_y = _cairo_fixed_integer_part (self->extents.p1.y);
504  start = *sweep_line.start++;
505  do {
506  if (start->top_y != sweep_line.current_y) {
507  render_rows (&sweep_line, renderer,
508  start->top_y - sweep_line.current_y);
509  sweep_line.current_y = start->top_y;
510  }
511 
512  do {
513  sweep_line_insert (&sweep_line, start);
514  start = *sweep_line.start++;
515  if (start == NULL)
516  goto end;
517  if (start->top_y != sweep_line.current_y)
518  break;
519  } while (TRUE);
520 
521  render_rows (&sweep_line, renderer, 1);
522 
523  stop = peek_stop (&sweep_line);
524  while (stop->bottom_y == sweep_line.current_y) {
525  sweep_line_delete (&sweep_line, stop);
526  stop = peek_stop (&sweep_line);
527  if (stop == NULL)
528  break;
529  }
530 
531  sweep_line.current_y++;
532 
533  while (stop != NULL && stop->bottom_y < start->top_y) {
534  if (stop->bottom_y != sweep_line.current_y) {
535  render_rows (&sweep_line, renderer,
536  stop->bottom_y - sweep_line.current_y);
537  sweep_line.current_y = stop->bottom_y;
538  }
539 
540  render_rows (&sweep_line, renderer, 1);
541 
542  do {
543  sweep_line_delete (&sweep_line, stop);
544  stop = peek_stop (&sweep_line);
545  } while (stop != NULL && stop->bottom_y == sweep_line.current_y);
546 
547  sweep_line.current_y++;
548  }
549  } while (TRUE);
550 
551  end:
552  render_rows (&sweep_line, renderer, 1);
553 
554  stop = peek_stop (&sweep_line);
555  while (stop->bottom_y == sweep_line.current_y) {
556  sweep_line_delete (&sweep_line, stop);
557  stop = peek_stop (&sweep_line);
558  if (stop == NULL)
559  goto out;
560  }
561 
562  while (++sweep_line.current_y < _cairo_fixed_integer_part (self->extents.p2.y)) {
563  if (stop->bottom_y != sweep_line.current_y) {
564  render_rows (&sweep_line, renderer,
565  stop->bottom_y - sweep_line.current_y);
566  sweep_line.current_y = stop->bottom_y;
567  }
568 
569  render_rows (&sweep_line, renderer, 1);
570 
571  do {
572  sweep_line_delete (&sweep_line, stop);
573  stop = peek_stop (&sweep_line);
574  if (stop == NULL)
575  goto out;
576  } while (stop->bottom_y == sweep_line.current_y);
577 
578  }
579 
580  out:
581  sweep_line_fini (&sweep_line);
582 
583  return status;
584 }
585 static void generate_row(cairo_span_renderer_t *renderer,
586  const rectangle_t *r,
587  int y, int h,
589 {
590  cairo_half_open_span_t spans[4];
591  unsigned int num_spans = 0;
592  int x1 = _cairo_fixed_integer_part (r->left);
593  int x2 = _cairo_fixed_integer_part (r->right);
594  if (x2 > x1) {
595  if (! _cairo_fixed_is_integer (r->left)) {
596  spans[num_spans].x = x1;
597  spans[num_spans].coverage =
598  coverage * (256 - _cairo_fixed_fractional_part (r->left)) >> 8;
599  num_spans++;
600  x1++;
601  }
602 
603  if (x2 > x1) {
604  spans[num_spans].x = x1;
605  spans[num_spans].coverage = coverage - (coverage >> 8);
606  num_spans++;
607  }
608 
609  if (! _cairo_fixed_is_integer (r->right)) {
610  spans[num_spans].x = x2++;
611  spans[num_spans].coverage =
612  coverage * _cairo_fixed_fractional_part (r->right) >> 8;
613  num_spans++;
614  }
615  } else {
616  spans[num_spans].x = x2++;
617  spans[num_spans].coverage = coverage * (r->right - r->left) >> 8;
618  num_spans++;
619  }
620 
621  spans[num_spans].x = x2;
622  spans[num_spans].coverage = 0;
623  num_spans++;
624 
625  renderer->render_rows (renderer, y, h, spans, num_spans);
626 }
627 
628 static cairo_status_t
630  cairo_span_renderer_t *renderer)
631 {
632  const rectangle_t *r = self->chunks.base;
633  int y1 = _cairo_fixed_integer_part (r->top);
634  int y2 = _cairo_fixed_integer_part (r->bottom);
635  if (y2 > y1) {
636  if (! _cairo_fixed_is_integer (r->top)) {
637  generate_row(renderer, r, y1, 1,
638  256 - _cairo_fixed_fractional_part (r->top));
639  y1++;
640  }
641 
642  if (y2 > y1)
643  generate_row(renderer, r, y1, y2-y1, 256);
644 
645  if (! _cairo_fixed_is_integer (r->bottom))
646  generate_row(renderer, r, y2, 1,
647  _cairo_fixed_fractional_part (r->bottom));
648  } else
649  generate_row(renderer, r, y1, 1, r->bottom - r->top);
650 
651  return CAIRO_STATUS_SUCCESS;
652 }
653 
654 static cairo_status_t
656  cairo_span_renderer_t *renderer)
657 {
658  cairo_rectangular_scan_converter_t *self = converter;
659  rectangle_t *rectangles_stack[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *)];
660  rectangle_t **rectangles;
661  struct _cairo_rectangular_scan_converter_chunk *chunk;
663  int i, j;
664 
665  if (unlikely (self->num_rectangles == 0)) {
666  return renderer->render_rows (renderer,
667  _cairo_fixed_integer_part (self->extents.p1.y),
668  _cairo_fixed_integer_part (self->extents.p2.y - self->extents.p1.y),
669  NULL, 0);
670  }
671 
672  if (self->num_rectangles == 1)
673  return generate_box (self, renderer);
674 
675  rectangles = rectangles_stack;
676  if (unlikely (self->num_rectangles >= ARRAY_LENGTH (rectangles_stack))) {
677  rectangles = _cairo_malloc_ab (self->num_rectangles + 1,
678  sizeof (rectangle_t *));
679  if (unlikely (rectangles == NULL))
681  }
682 
683  j = 0;
684  for (chunk = &self->chunks; chunk != NULL; chunk = chunk->next) {
685  rectangle_t *rectangle;
686 
687  rectangle = chunk->base;
688  for (i = 0; i < chunk->count; i++)
689  rectangles[j++] = &rectangle[i];
690  }
691  rectangle_sort (rectangles, j);
692  rectangles[j] = NULL;
693 
694  status = generate (self, renderer, rectangles);
695 
696  if (rectangles != rectangles_stack)
697  free (rectangles);
698 
699  return status;
700 }
701 
702 static rectangle_t *
704 {
705  rectangle_t *rectangle;
706  struct _cairo_rectangular_scan_converter_chunk *chunk;
707 
708  chunk = self->tail;
709  if (chunk->count == chunk->size) {
710  int size;
711 
712  size = chunk->size * 2;
714  sizeof (rectangle_t),
715  sizeof (struct _cairo_rectangular_scan_converter_chunk));
716 
717  if (unlikely (chunk->next == NULL))
718  return NULL;
719 
720  chunk = chunk->next;
721  chunk->next = NULL;
722  chunk->count = 0;
723  chunk->size = size;
724  chunk->base = chunk + 1;
725  self->tail = chunk;
726  }
727 
728  rectangle = chunk->base;
729  return rectangle + chunk->count++;
730 }
731 
734  const cairo_box_t *box,
735  int dir)
736 {
737  rectangle_t *rectangle;
738 
739  rectangle = _allocate_rectangle (self);
740  if (unlikely (rectangle == NULL))
742 
743  rectangle->dir = dir;
744  rectangle->left = MAX (box->p1.x, self->extents.p1.x);
745  rectangle->right = MIN (box->p2.x, self->extents.p2.x);
746  if (unlikely (rectangle->right <= rectangle->left)) {
747  self->tail->count--;
748  return CAIRO_STATUS_SUCCESS;
749  }
750 
751  rectangle->top = MAX (box->p1.y, self->extents.p1.y);
752  rectangle->top_y = _cairo_fixed_integer_floor (rectangle->top);
753  rectangle->bottom = MIN (box->p2.y, self->extents.p2.y);
754  rectangle->bottom_y = _cairo_fixed_integer_floor (rectangle->bottom);
755  if (likely (rectangle->bottom > rectangle->top))
756  self->num_rectangles++;
757  else
758  self->tail->count--;
759 
760  return CAIRO_STATUS_SUCCESS;
761 }
762 
763 static void
765 {
766  cairo_rectangular_scan_converter_t *self = converter;
767  struct _cairo_rectangular_scan_converter_chunk *chunk, *next;
768 
769  for (chunk = self->chunks.next; chunk != NULL; chunk = next) {
770  next = chunk->next;
771  free (chunk);
772  }
773 }
774 
775 void
778 {
779  self->base.destroy = _cairo_rectangular_scan_converter_destroy;
780  self->base.generate = _cairo_rectangular_scan_converter_generate;
781 
782  _cairo_box_from_rectangle (&self->extents, extents);
783 
784  self->chunks.base = self->buf;
785  self->chunks.next = NULL;
786  self->chunks.count = 0;
787  self->chunks.size = sizeof (self->buf) / sizeof (rectangle_t);
788  self->tail = &self->chunks;
789 
790  self->num_rectangles = 0;
791 }
#define head
Definition: aptex-macros.h:513
#define height(a)
Definition: aptex-macros.h:200
#define next(a)
Definition: aptex-macros.h:924
#define stop
Definition: aptex-macros.h:362
#define tail
Definition: aptex-macros.h:514
int cmp(const void *p, const void *q)
Definition: bkmk2uni.c:1611
struct _sweep_line sweep_line_t
#define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP)
#define CAIRO_STACK_ARRAY_LENGTH(T)
cairo_status_t _cairo_error(cairo_status_t status)
Definition: cairo-error.c:65
static int _cairo_fixed_integer_floor(cairo_fixed_t f)
static int _cairo_fixed_is_integer(cairo_fixed_t f)
static int _cairo_fixed_fractional_part(cairo_fixed_t f)
#define CAIRO_FIXED_ONE
static int _cairo_fixed_integer_part(cairo_fixed_t f)
#define CAIRO_FIXED_FRAC_MASK
#define CAIRO_FIXED_FRAC_BITS
int32_t cairo_fixed_t
void _cairo_freepool_fini(cairo_freepool_t *freepool)
static void * _cairo_freepool_alloc(cairo_freepool_t *freepool)
void _cairo_freepool_init(cairo_freepool_t *freepool, unsigned nodesize)
static void _cairo_freepool_reset(cairo_freepool_t *freepool)
#define _cairo_realloc_ab(ptr, a, size)
#define _cairo_malloc_ab(a, size)
#define _cairo_malloc_ab_plus_c(a, size, c)
void _cairo_box_from_rectangle(cairo_box_t *box, const cairo_rectangle_int_t *rect)
static void pqueue_fini(pqueue_t *pq)
static void add_cell(sweep_line_t *sweep, int x, int covered, int uncovered)
#define PQ_LEFT_CHILD_INDEX(i)
static cairo_status_t generate(cairo_rectangular_scan_converter_t *self, cairo_span_renderer_t *renderer, rectangle_t **rectangles)
void _cairo_rectangular_scan_converter_init(cairo_rectangular_scan_converter_t *self, const cairo_rectangle_int_t *extents)
struct _pqueue pqueue_t
static void pqueue_push(sweep_line_t *sweep, rectangle_t *rectangle)
static rectangle_t * _allocate_rectangle(cairo_rectangular_scan_converter_t *self)
static void sweep_line_insert(sweep_line_t *sweep, rectangle_t *rectangle)
static void sweep_line_init(sweep_line_t *sweep)
cairo_status_t _cairo_rectangular_scan_converter_add_box(cairo_rectangular_scan_converter_t *self, const cairo_box_t *box, int dir)
static cairo_bool_t pqueue_grow(pqueue_t *pq)
static rectangle_t * peek_stop(sweep_line_t *sweep)
struct _rectangle rectangle_t
static cairo_status_t _cairo_rectangular_scan_converter_generate(void *converter, cairo_span_renderer_t *renderer)
static void sweep_line_fini(sweep_line_t *sweep)
#define UNROLL3(x)
static void rectangle_sort(rectangle_t **base, unsigned int nmemb)
static void sweep_line_delete(sweep_line_t *sweep, rectangle_t *rectangle)
#define PQ_FIRST_ENTRY
#define PQ_PARENT_INDEX(i)
static void render_rows(sweep_line_t *sweep_line, cairo_span_renderer_t *renderer, int height)
static void pqueue_pop(pqueue_t *pq)
static cairo_status_t generate_box(cairo_rectangular_scan_converter_t *self, cairo_span_renderer_t *renderer)
static void pqueue_init(pqueue_t *pq)
static void generate_row(cairo_span_renderer_t *renderer, const rectangle_t *r, int y, int h, uint16_t coverage)
static void _cairo_rectangular_scan_converter_destroy(void *converter)
static int rectangle_compare_stop(const rectangle_t *a, const rectangle_t *b)
static void _active_edges_to_spans(sweep_line_t *sweep)
static int rectangle_compare_start(const rectangle_t *a, const rectangle_t *b)
int cairo_bool_t
Definition: cairo.h:107
@ CAIRO_STATUS_SUCCESS
Definition: cairo.h:315
@ CAIRO_STATUS_NO_MEMORY
Definition: cairo.h:317
enum _cairo_status cairo_status_t
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
#define n
Definition: t4ht.c:1290
#define b
Definition: jpegint.h:372
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
#define free(a)
Definition: decNumber.cpp:310
int h
Definition: dviconv.c:9
static gregorio_element ** elements
static FIELD_PTR prev
Definition: genind.c:36
#define c(n)
Definition: gpos-common.c:150
#define a(n)
Definition: gpos-common.c:148
#define memcpy(d, s, n)
Definition: gsftopk.c:64
FILE * out
Definition: hbf2gf.c:286
#define likely(x)
Definition: jbig2arith.cc:115
#define unlikely(x)
Definition: jbig2arith.cc:116
#define MIN(a, b)
Definition: jpegint.h:269
#define MAX(a, b)
Definition: jpegint.h:267
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
kerning y
Definition: ttdriver.c:212
unsigned short uint16_t
Definition: stdint.h:79
signed int int32_t
Definition: stdint.h:77
#define INT_MIN
Definition: c-minmax.h:50
#define INT_MAX
Definition: c-minmax.h:53
struct cell_struct cell
const int * pos
Definition: combiners.h:905
float x
Definition: cordic.py:15
static int size
Definition: ppmlabel.c:24
int r
Definition: ppmqvga.c:68
#define x1
#define y1
#define y2
#define x2
#define dir
#define status
static void chunk(LexState *ls)
Definition: minilua.c:4678
#define parent(a, t)
Definition: interp.c:105
cairo_status_t(* render_rows)(void *abstract_renderer, int y, int height, const cairo_half_open_span_t *coverages, unsigned num_coverages)
cairo_bo_event_t * elements_embedded[1024]
cairo_bo_event_t ** elements
struct _rectangle * next
struct _rectangle * prev
Definition: jquant2.c:258
struct cell * prev
struct cell * next
Definition: job.h:44
struct chunk * next
Definition: splineutil.c:76
Definition: tfm.c:163
cairo_half_open_span_t * spans
struct sweep_line_t::coverage coverage
cairo_half_open_span_t spans_stack[((512 *sizeof(int))/sizeof(cairo_half_open_span_t))]
int j
Definition: t4ht.c:1589
static double prev_x
Definition: tex4ht.c:1079
found
Definition: tex4ht.c:5000
@ start
Definition: preamble.c:52
#define end(cp)
Definition: zic.c:71