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-bentley-ottmann-rectangular.c
Go to the documentation of this file.
1 /*
2  * Copyright © 2004 Carl Worth
3  * Copyright © 2006 Red Hat, Inc.
4  * Copyright © 2009 Chris Wilson
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it either under the terms of the GNU Lesser General Public
8  * License version 2.1 as published by the Free Software Foundation
9  * (the "LGPL") or, at your option, under the terms of the Mozilla
10  * Public License Version 1.1 (the "MPL"). If you do not alter this
11  * notice, a recipient may use your version of this file under either
12  * the MPL or the LGPL.
13  *
14  * You should have received a copy of the LGPL along with this library
15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17  * You should have received a copy of the MPL along with this library
18  * in the file COPYING-MPL-1.1
19  *
20  * The contents of this file are subject to the Mozilla Public License
21  * Version 1.1 (the "License"); you may not use this file except in
22  * compliance with the License. You may obtain a copy of the License at
23  * http://www.mozilla.org/MPL/
24  *
25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27  * the specific language governing rights and limitations.
28  *
29  * The Original Code is the cairo graphics library.
30  *
31  * The Initial Developer of the Original Code is Carl Worth
32  *
33  * Contributor(s):
34  * Carl D. Worth <cworth@cworth.org>
35  * Chris Wilson <chris@chris-wilson.co.uk>
36  */
37 
38 /* Provide definitions for standalone compilation */
39 #include "cairoint.h"
40 
41 #include "cairo-boxes-private.h"
42 #include "cairo-error-private.h"
43 #include "cairo-combsort-inline.h"
44 #include "cairo-list-private.h"
45 #include "cairo-traps-private.h"
46 
47 #include <setjmp.h>
48 
49 typedef struct _rectangle rectangle_t;
50 typedef struct _edge edge_t;
51 
52 struct _edge {
53  edge_t *next, *prev;
54  edge_t *right;
56  int dir;
57 };
58 
59 struct _rectangle {
60  edge_t left, right;
62 };
63 
64 #define UNROLL3(x) x x x
65 
66 /* the parent is always given by index/2 */
67 #define PQ_PARENT_INDEX(i) ((i) >> 1)
68 #define PQ_FIRST_ENTRY 1
69 
70 /* left and right children are index * 2 and (index * 2) +1 respectively */
71 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
72 
73 typedef struct _sweep_line {
75  rectangle_t **stop;
79  int stop_size;
80 
83 
85  void *container;
86 
87  jmp_buf unwind;
89 
90 #define DEBUG_TRAPS 0
91 
92 #if DEBUG_TRAPS
93 static void
94 dump_traps (cairo_traps_t *traps, const char *filename)
95 {
96  FILE *file;
97  int n;
98 
99  if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
100  return;
101 
102  file = fopen (filename, "a");
103  if (file != NULL) {
104  for (n = 0; n < traps->num_traps; n++) {
105  fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
106  traps->traps[n].top,
107  traps->traps[n].bottom,
108  traps->traps[n].left.p1.x,
109  traps->traps[n].left.p1.y,
110  traps->traps[n].left.p2.x,
111  traps->traps[n].left.p2.y,
112  traps->traps[n].right.p1.x,
113  traps->traps[n].right.p1.y,
114  traps->traps[n].right.p2.x,
115  traps->traps[n].right.p2.y);
116  }
117  fprintf (file, "\n");
118  fclose (file);
119  }
120 }
121 #else
122 #define dump_traps(traps, filename)
123 #endif
124 
125 static inline int
127  const rectangle_t *b)
128 {
129  return a->top - b->top;
130 }
131 
132 static inline int
134  const rectangle_t *b)
135 {
136  return a->bottom - b->bottom;
137 }
138 
139 static inline void
141 {
143  int i, parent;
144 
145  elements = sweep->stop;
146  for (i = ++sweep->stop_size;
147  i != PQ_FIRST_ENTRY &&
148  rectangle_compare_stop (rectangle,
149  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
150  i = parent)
151  {
153  }
154 
155  elements[i] = rectangle;
156 }
157 
158 static inline void
160 {
161  rectangle_t **elements = sweep->stop;
162  rectangle_t *tail;
163  int child, i;
164 
165  tail = elements[sweep->stop_size--];
166  if (sweep->stop_size == 0) {
168  return;
169  }
170 
171  for (i = PQ_FIRST_ENTRY;
172  (child = PQ_LEFT_CHILD_INDEX (i)) <= sweep->stop_size;
173  i = child)
174  {
175  if (child != sweep->stop_size &&
177  elements[child]) < 0)
178  {
179  child++;
180  }
181 
183  break;
184 
185  elements[i] = elements[child];
186  }
187  elements[i] = tail;
188 }
189 
190 static inline rectangle_t *
192 {
193  return *sweep_line->rectangles++;
194 }
195 
196 static inline rectangle_t *
198 {
199  return sweep_line->stop[PQ_FIRST_ENTRY];
200 }
201 
203  rectangle_t *,
205 
206 static void
208  rectangle_t **rectangles,
209  int num_rectangles,
210  cairo_fill_rule_t fill_rule,
211  cairo_bool_t do_traps,
212  void *container)
213 {
214  rectangles[-2] = NULL;
215  rectangles[-1] = NULL;
216  rectangles[num_rectangles] = NULL;
217  sweep_line->rectangles = rectangles;
218  sweep_line->stop = rectangles - 2;
219  sweep_line->stop_size = 0;
220 
221  sweep_line->insert = NULL;
222  sweep_line->insert_x = INT_MAX;
223  sweep_line->cursor = &sweep_line->tail;
224 
225  sweep_line->head.dir = 0;
226  sweep_line->head.x = INT32_MIN;
227  sweep_line->head.right = NULL;
228  sweep_line->head.prev = NULL;
229  sweep_line->head.next = &sweep_line->tail;
230  sweep_line->tail.prev = &sweep_line->head;
231  sweep_line->tail.next = NULL;
232  sweep_line->tail.right = NULL;
233  sweep_line->tail.x = INT32_MAX;
234  sweep_line->tail.dir = 0;
235 
236  sweep_line->current_y = INT32_MIN;
237  sweep_line->last_y = INT32_MIN;
238 
239  sweep_line->fill_rule = fill_rule;
240  sweep_line->container = container;
241  sweep_line->do_traps = do_traps;
242 }
243 
244 static void
246 {
248 
249  /* Only emit (trivial) non-degenerate trapezoids with positive height. */
250  if (likely (left->top < bot)) {
251  if (sweep_line->do_traps) {
252  cairo_line_t _left = {
253  { left->x, left->top },
254  { left->x, bot },
255  }, _right = {
256  { left->right->x, left->top },
257  { left->right->x, bot },
258  };
259  _cairo_traps_add_trap (sweep_line->container, left->top, bot, &_left, &_right);
260  status = _cairo_traps_status ((cairo_traps_t *) sweep_line->container);
261  } else {
263 
264  box.p1.x = left->x;
265  box.p1.y = left->top;
266  box.p2.x = left->right->x;
267  box.p2.y = bot;
268 
269  status = _cairo_boxes_add (sweep_line->container,
271  &box);
272  }
273  }
274  if (unlikely (status))
275  longjmp (sweep_line->unwind, status);
276 
277  left->right = NULL;
278 }
279 
280 /* Start a new trapezoid at the given top y coordinate, whose edges
281  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
282  * then either add it to the traps in `traps', if the trapezoid's
283  * right edge differs from `edge->next', or do nothing if the new
284  * trapezoid would be a continuation of the existing one. */
285 static inline void
287  edge_t *left,
288  edge_t *right,
289  int top)
290 {
291  if (left->right == right)
292  return;
293 
294  if (left->right != NULL) {
295  if (left->right->x == right->x) {
296  /* continuation on right, so just swap edges */
297  left->right = right;
298  return;
299  }
300 
301  edge_end_box (sweep_line, left, top);
302  }
303 
304  if (left->x != right->x) {
305  left->top = top;
306  left->right = right;
307  }
308 }
309 /*
310  * Merge two sorted edge lists.
311  * Input:
312  * - head_a: The head of the first list.
313  * - head_b: The head of the second list; head_b cannot be NULL.
314  * Output:
315  * Returns the head of the merged list.
316  *
317  * Implementation notes:
318  * To make it fast (in particular, to reduce to an insertion sort whenever
319  * one of the two input lists only has a single element) we iterate through
320  * a list until its head becomes greater than the head of the other list,
321  * then we switch their roles. As soon as one of the two lists is empty, we
322  * just attach the other one to the current list and exit.
323  * Writes to memory are only needed to "switch" lists (as it also requires
324  * attaching to the output list the list which we will be iterating next) and
325  * to attach the last non-empty list.
326  */
327 static edge_t *
328 merge_sorted_edges (edge_t *head_a, edge_t *head_b)
329 {
330  edge_t *head, *prev;
331  int32_t x;
332 
333  prev = head_a->prev;
334  if (head_a->x <= head_b->x) {
335  head = head_a;
336  } else {
337  head_b->prev = prev;
338  head = head_b;
339  goto start_with_b;
340  }
341 
342  do {
343  x = head_b->x;
344  while (head_a != NULL && head_a->x <= x) {
345  prev = head_a;
346  head_a = head_a->next;
347  }
348 
349  head_b->prev = prev;
350  prev->next = head_b;
351  if (head_a == NULL)
352  return head;
353 
354 start_with_b:
355  x = head_a->x;
356  while (head_b != NULL && head_b->x <= x) {
357  prev = head_b;
358  head_b = head_b->next;
359  }
360 
361  head_a->prev = prev;
362  prev->next = head_a;
363  if (head_b == NULL)
364  return head;
365  } while (1);
366 }
367 
368 /*
369  * Sort (part of) a list.
370  * Input:
371  * - list: The list to be sorted; list cannot be NULL.
372  * - limit: Recursion limit.
373  * Output:
374  * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
375  * input list; if the input list has fewer elements, head_out be a sorted list
376  * containing all the elements of the input list.
377  * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
378  * all the elements of the input list).
379  *
380  * Implementation notes:
381  * Special case single element list, unroll/inline the sorting of the first two elements.
382  * Some tail recursion is used since we iterate on the bottom-up solution of the problem
383  * (we start with a small sorted list and keep merging other lists of the same size to it).
384  */
385 static edge_t *
387  unsigned int level,
388  edge_t **head_out)
389 {
390  edge_t *head_other, *remaining;
391  unsigned int i;
392 
393  head_other = list->next;
394 
395  if (head_other == NULL) {
396  *head_out = list;
397  return NULL;
398  }
399 
400  remaining = head_other->next;
401  if (list->x <= head_other->x) {
402  *head_out = list;
403  head_other->next = NULL;
404  } else {
405  *head_out = head_other;
406  head_other->prev = list->prev;
407  head_other->next = list;
408  list->prev = head_other;
409  list->next = NULL;
410  }
411 
412  for (i = 0; i < level && remaining; i++) {
413  remaining = sort_edges (remaining, i, &head_other);
414  *head_out = merge_sorted_edges (*head_out, head_other);
415  }
416 
417  return remaining;
418 }
419 
420 static edge_t *
422 {
423  sort_edges (unsorted, UINT_MAX, &unsorted);
424  return merge_sorted_edges (head, unsorted);
425 }
426 
427 static void
429 {
430  edge_t *prev;
431  int x;
432 
433  x = sweep->insert_x;
434  prev = sweep->cursor;
435  if (prev->x > x) {
436  do {
437  prev = prev->prev;
438  } while (prev->x > x);
439  } else {
440  while (prev->next->x < x)
441  prev = prev->next;
442  }
443 
444  prev->next = merge_unsorted_edges (prev->next, sweep->insert);
445  sweep->cursor = sweep->insert;
446  sweep->insert = NULL;
447  sweep->insert_x = INT_MAX;
448 }
449 
450 static inline void
452 {
453  int top = sweep->current_y;
454  edge_t *pos;
455 
456  if (sweep->last_y == sweep->current_y)
457  return;
458 
459  if (sweep->insert)
460  active_edges_insert (sweep);
461 
462  pos = sweep->head.next;
463  if (pos == &sweep->tail)
464  return;
465 
466  if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING) {
467  do {
468  edge_t *left, *right;
469  int winding;
470 
471  left = pos;
472  winding = left->dir;
473 
474  right = left->next;
475 
476  /* Check if there is a co-linear edge with an existing trap */
477  while (right->x == left->x) {
478  if (right->right != NULL) {
479  assert (left->right == NULL);
480  /* continuation on left */
481  left->top = right->top;
482  left->right = right->right;
483  right->right = NULL;
484  }
485  winding += right->dir;
486  right = right->next;
487  }
488 
489  if (winding == 0) {
490  if (left->right != NULL)
491  edge_end_box (sweep, left, top);
492  pos = right;
493  continue;
494  }
495 
496  do {
497  /* End all subsumed traps */
498  if (unlikely (right->right != NULL))
499  edge_end_box (sweep, right, top);
500 
501  /* Greedily search for the closing edge, so that we generate
502  * the * maximal span width with the minimal number of
503  * boxes.
504  */
505  winding += right->dir;
506  if (winding == 0 && right->x != right->next->x)
507  break;
508 
509  right = right->next;
510  } while (TRUE);
511 
513 
514  pos = right->next;
515  } while (pos != &sweep->tail);
516  } else {
517  do {
518  edge_t *right = pos->next;
519  int count = 0;
520 
521  do {
522  /* End all subsumed traps */
523  if (unlikely (right->right != NULL))
524  edge_end_box (sweep, right, top);
525 
526  /* skip co-linear edges */
527  if (++count & 1 && right->x != right->next->x)
528  break;
529 
530  right = right->next;
531  } while (TRUE);
532 
534 
535  pos = right->next;
536  } while (pos != &sweep->tail);
537  }
538 
539  sweep->last_y = sweep->current_y;
540 }
541 
542 static inline void
544 {
545  if (edge->right != NULL) {
546  edge_t *next = edge->next;
547  if (next->x == edge->x) {
548  next->top = edge->top;
549  next->right = edge->right;
550  } else
551  edge_end_box (sweep, edge, sweep->current_y);
552  }
553 
554  if (sweep->cursor == edge)
555  sweep->cursor = edge->prev;
556 
557  edge->prev->next = edge->next;
558  edge->next->prev = edge->prev;
559 }
560 
561 static inline cairo_bool_t
563 {
564  cairo_bool_t update;
565 
566  update = TRUE;
567  if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
568  rectangle->left.prev->dir == rectangle->left.dir)
569  {
570  update = rectangle->left.next != &rectangle->right;
571  }
572 
573  sweep_line_delete_edge (sweep, &rectangle->left);
574  sweep_line_delete_edge (sweep, &rectangle->right);
575 
576  rectangle_pop_stop (sweep);
577  return update;
578 }
579 
580 static inline void
582 {
583  if (sweep->insert)
584  sweep->insert->prev = &rectangle->right;
585  rectangle->right.next = sweep->insert;
586  rectangle->right.prev = &rectangle->left;
587  rectangle->left.next = &rectangle->right;
588  rectangle->left.prev = NULL;
589  sweep->insert = &rectangle->left;
590  if (rectangle->left.x < sweep->insert_x)
591  sweep->insert_x = rectangle->left.x;
592 
593  pqueue_push (sweep, rectangle);
594 }
595 
596 static cairo_status_t
598  int num_rectangles,
599  cairo_fill_rule_t fill_rule,
600  cairo_bool_t do_traps,
601  void *container)
602 {
603  sweep_line_t sweep_line;
604  rectangle_t *rectangle;
606  cairo_bool_t update;
607 
608  sweep_line_init (&sweep_line,
609  rectangles, num_rectangles,
610  fill_rule,
611  do_traps, container);
612  if ((status = setjmp (sweep_line.unwind)))
613  return status;
614 
615  update = FALSE;
616 
617  rectangle = rectangle_pop_start (&sweep_line);
618  do {
619  if (rectangle->top != sweep_line.current_y) {
620  rectangle_t *stop;
621 
622  stop = rectangle_peek_stop (&sweep_line);
623  while (stop != NULL && stop->bottom < rectangle->top) {
624  if (stop->bottom != sweep_line.current_y) {
625  if (update) {
626  active_edges_to_traps (&sweep_line);
627  update = FALSE;
628  }
629 
630  sweep_line.current_y = stop->bottom;
631  }
632 
633  update |= sweep_line_delete (&sweep_line, stop);
634  stop = rectangle_peek_stop (&sweep_line);
635  }
636 
637  if (update) {
638  active_edges_to_traps (&sweep_line);
639  update = FALSE;
640  }
641 
642  sweep_line.current_y = rectangle->top;
643  }
644 
645  do {
646  sweep_line_insert (&sweep_line, rectangle);
647  } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
648  sweep_line.current_y == rectangle->top);
649  update = TRUE;
650  } while (rectangle);
651 
652  while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
653  if (rectangle->bottom != sweep_line.current_y) {
654  if (update) {
655  active_edges_to_traps (&sweep_line);
656  update = FALSE;
657  }
658  sweep_line.current_y = rectangle->bottom;
659  }
660 
661  update |= sweep_line_delete (&sweep_line, rectangle);
662  }
663 
664  return CAIRO_STATUS_SUCCESS;
665 }
666 
669  cairo_fill_rule_t fill_rule)
670 {
672  rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
673  rectangle_t *rectangles, **rectangles_ptrs;
675  int i;
676 
677  assert (traps->is_rectangular);
678 
679  if (unlikely (traps->num_traps <= 1)) {
680  if (traps->num_traps == 1) {
681  cairo_trapezoid_t *trap = traps->traps;
682  if (trap->left.p1.x > trap->right.p1.x) {
683  cairo_line_t tmp = trap->left;
684  trap->left = trap->right;
685  trap->right = tmp;
686  }
687  }
688  return CAIRO_STATUS_SUCCESS;
689  }
690 
691  dump_traps (traps, "bo-rects-traps-in.txt");
692 
693  rectangles = stack_rectangles;
694  rectangles_ptrs = stack_rectangles_ptrs;
695  if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
696  rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
697  sizeof (rectangle_t) +
698  sizeof (rectangle_t *),
699  3*sizeof (rectangle_t *));
700  if (unlikely (rectangles == NULL))
702 
703  rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
704  }
705 
706  for (i = 0; i < traps->num_traps; i++) {
707  if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
708  rectangles[i].left.x = traps->traps[i].left.p1.x;
709  rectangles[i].left.dir = 1;
710 
711  rectangles[i].right.x = traps->traps[i].right.p1.x;
712  rectangles[i].right.dir = -1;
713  } else {
714  rectangles[i].right.x = traps->traps[i].left.p1.x;
715  rectangles[i].right.dir = 1;
716 
717  rectangles[i].left.x = traps->traps[i].right.p1.x;
718  rectangles[i].left.dir = -1;
719  }
720 
721  rectangles[i].left.right = NULL;
722  rectangles[i].right.right = NULL;
723 
724  rectangles[i].top = traps->traps[i].top;
725  rectangles[i].bottom = traps->traps[i].bottom;
726 
727  rectangles_ptrs[i+2] = &rectangles[i];
728  }
729  /* XXX incremental sort */
730  _rectangle_sort (rectangles_ptrs+2, i);
731 
732  _cairo_traps_clear (traps);
734  fill_rule,
735  TRUE, traps);
736  traps->is_rectilinear = TRUE;
737  traps->is_rectangular = TRUE;
738 
739  if (rectangles != stack_rectangles)
740  free (rectangles);
741 
742  dump_traps (traps, "bo-rects-traps-out.txt");
743 
744  return status;
745 }
746 
749  cairo_fill_rule_t fill_rule,
751 {
753  rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
754  rectangle_t *rectangles, **rectangles_ptrs;
755  rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
756  rectangle_t **rectangles_chain = NULL;
757  const struct _cairo_boxes_chunk *chunk;
759  int i, j, y_min, y_max;
760 
761  if (unlikely (in->num_boxes == 0)) {
763  return CAIRO_STATUS_SUCCESS;
764  }
765 
766  if (in->num_boxes == 1) {
767  if (in == out) {
768  cairo_box_t *box = &in->chunks.base[0];
769 
770  if (box->p1.x > box->p2.x) {
771  cairo_fixed_t tmp = box->p1.x;
772  box->p1.x = box->p2.x;
773  box->p2.x = tmp;
774  }
775  } else {
776  cairo_box_t box = in->chunks.base[0];
777 
778  if (box.p1.x > box.p2.x) {
779  cairo_fixed_t tmp = box.p1.x;
780  box.p1.x = box.p2.x;
781  box.p2.x = tmp;
782  }
783 
787  }
788  return CAIRO_STATUS_SUCCESS;
789  }
790 
791  y_min = INT_MAX; y_max = INT_MIN;
792  for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
793  const cairo_box_t *box = chunk->base;
794  for (i = 0; i < chunk->count; i++) {
795  if (box[i].p1.y < y_min)
796  y_min = box[i].p1.y;
797  if (box[i].p1.y > y_max)
798  y_max = box[i].p1.y;
799  }
800  }
803  y_max -= y_min;
804 
805  if (y_max < in->num_boxes) {
806  rectangles_chain = stack_rectangles_chain;
807  if (y_max > ARRAY_LENGTH (stack_rectangles_chain)) {
808  rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
809  if (unlikely (rectangles_chain == NULL))
811  }
812  memset (rectangles_chain, 0, y_max * sizeof (rectangle_t*));
813  }
814 
815  rectangles = stack_rectangles;
816  rectangles_ptrs = stack_rectangles_ptrs;
817  if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
818  rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
819  sizeof (rectangle_t) +
820  sizeof (rectangle_t *),
821  3*sizeof (rectangle_t *));
822  if (unlikely (rectangles == NULL)) {
823  if (rectangles_chain != stack_rectangles_chain)
824  free (rectangles_chain);
826  }
827 
828  rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
829  }
830 
831  j = 0;
832  for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
833  const cairo_box_t *box = chunk->base;
834  for (i = 0; i < chunk->count; i++) {
835  int h;
836 
837  if (box[i].p1.x < box[i].p2.x) {
838  rectangles[j].left.x = box[i].p1.x;
839  rectangles[j].left.dir = 1;
840 
841  rectangles[j].right.x = box[i].p2.x;
842  rectangles[j].right.dir = -1;
843  } else {
844  rectangles[j].right.x = box[i].p1.x;
845  rectangles[j].right.dir = 1;
846 
847  rectangles[j].left.x = box[i].p2.x;
848  rectangles[j].left.dir = -1;
849  }
850 
851  rectangles[j].left.right = NULL;
852  rectangles[j].right.right = NULL;
853 
854  rectangles[j].top = box[i].p1.y;
855  rectangles[j].bottom = box[i].p2.y;
856 
857  if (rectangles_chain) {
859  rectangles[j].left.next = (edge_t *)rectangles_chain[h];
860  rectangles_chain[h] = &rectangles[j];
861  } else {
862  rectangles_ptrs[j+2] = &rectangles[j];
863  }
864  j++;
865  }
866  }
867 
868  if (rectangles_chain) {
869  j = 2;
870  for (y_min = 0; y_min < y_max; y_min++) {
871  rectangle_t *r;
872  int start = j;
873  for (r = rectangles_chain[y_min]; r; r = (rectangle_t *)r->left.next)
874  rectangles_ptrs[j++] = r;
875  if (j > start + 1)
876  _rectangle_sort (rectangles_ptrs + start, j - start);
877  }
878 
879  if (rectangles_chain != stack_rectangles_chain)
880  free (rectangles_chain);
881 
882  j -= 2;
883  } else {
884  _rectangle_sort (rectangles_ptrs + 2, j);
885  }
886 
889  fill_rule,
890  FALSE, out);
891  if (rectangles != stack_rectangles)
892  free (rectangles);
893 
894  return status;
895 }
int level
Definition: afm2pl.c:1694
#define head
Definition: aptex-macros.h:513
#define count(a)
Definition: aptex-macros.h:781
#define box(a)
Definition: aptex-macros.h:675
#define next(a)
Definition: aptex-macros.h:924
#define stop
Definition: aptex-macros.h:362
#define tail
Definition: aptex-macros.h:514
char * p1
Definition: bmpfont.h:62
struct _sweep_line sweep_line_t
cairo_status_t _cairo_bentley_ottmann_tessellate_rectangular_traps(cairo_traps_t *traps, cairo_fill_rule_t fill_rule)
cairo_status_t _cairo_bentley_ottmann_tessellate_boxes(const cairo_boxes_t *in, cairo_fill_rule_t fill_rule, cairo_boxes_t *out)
cairo_status_t _cairo_boxes_add(cairo_boxes_t *boxes, cairo_antialias_t antialias, const cairo_box_t *box)
Definition: cairo-boxes.c:184
void _cairo_boxes_clear(cairo_boxes_t *boxes)
Definition: cairo-boxes.c:320
#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)
int32_t cairo_fixed_t
#define _cairo_malloc_ab(a, size)
#define _cairo_malloc_ab_plus_c(a, size, c)
#define _cairo_traps_status(T)
void _cairo_traps_add_trap(cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom, const cairo_line_t *left, const cairo_line_t *right)
Definition: cairo-traps.c:151
void _cairo_traps_clear(cairo_traps_t *traps)
Definition: cairo-traps.c:98
enum _cairo_fill_rule cairo_fill_rule_t
int cairo_bool_t
Definition: cairo.h:107
@ CAIRO_STATUS_SUCCESS
Definition: cairo.h:315
@ CAIRO_STATUS_NO_MEMORY
Definition: cairo.h:317
@ CAIRO_ANTIALIAS_DEFAULT
Definition: cairo.h:710
enum _cairo_status cairo_status_t
@ CAIRO_FILL_RULE_WINDING
Definition: cairo.h:754
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
#define PQ_LEFT_CHILD_INDEX(i)
static void active_edges_insert(sweep_line_t *sweep)
static void pqueue_push(sweep_line_t *sweep, rectangle_t *rectangle)
static cairo_status_t _cairo_bentley_ottmann_tessellate_rectangular(rectangle_t **rectangles, int num_rectangles, cairo_fill_rule_t fill_rule, cairo_bool_t do_traps, void *container)
static rectangle_t * rectangle_pop_start(sweep_line_t *sweep_line)
static cairo_bool_t sweep_line_delete(sweep_line_t *sweep, rectangle_t *rectangle)
static void sweep_line_insert(sweep_line_t *sweep, rectangle_t *rectangle)
static void active_edges_to_traps(sweep_line_t *sweep)
static void edge_start_or_continue_box(sweep_line_t *sweep_line, edge_t *left, edge_t *right, int top)
static void _rectangle_sort(rectangle_t **base, unsigned int nmemb)
#define dump_traps(traps, filename)
static rectangle_t * rectangle_peek_stop(sweep_line_t *sweep_line)
static edge_t * merge_sorted_edges(edge_t *head_a, edge_t *head_b)
static edge_t * sort_edges(edge_t *list, unsigned int level, edge_t **head_out)
static void sweep_line_init(sweep_line_t *sweep_line, rectangle_t **rectangles, int num_rectangles, cairo_fill_rule_t fill_rule, cairo_bool_t do_traps, void *container)
static void edge_end_box(sweep_line_t *sweep_line, edge_t *left, int32_t bot)
#define PQ_PARENT_INDEX(i)
static edge_t * merge_unsorted_edges(edge_t *head, edge_t *unsorted)
static void rectangle_pop_stop(sweep_line_t *sweep)
static void sweep_line_delete_edge(sweep_line_t *sweep, edge_t *edge)
static int rectangle_compare_stop(const rectangle_t *a, const rectangle_t *b)
static int rectangle_compare_start(const rectangle_t *a, const rectangle_t *b)
#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
#define fopen
Definition: xxstdio.h:21
int y_min
int y_max
static gregorio_element ** elements
static FIELD_PTR prev
Definition: genind.c:36
#define a(n)
Definition: gpos-common.c:148
FILE * out
Definition: hbf2gf.c:286
assert(pcxLoadImage24((char *)((void *) 0), fp, pinfo, hdr))
#define likely(x)
Definition: jbig2arith.cc:115
#define unlikely(x)
Definition: jbig2arith.cc:116
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
@ right
Definition: annotate.c:15
int int double double double char double char * top
Definition: gdfx.h:19
#define INT32_MAX
Definition: stdint.h:137
#define INT32_MIN
Definition: stdint.h:136
signed int int32_t
Definition: stdint.h:77
char * getenv()
#define INT_MIN
Definition: c-minmax.h:50
#define INT_MAX
Definition: c-minmax.h:53
#define UINT_MAX
Definition: c-minmax.h:56
#define fclose
Definition: debug.h:100
#define fprintf
Definition: mendex.h:64
cell * list
Definition: list_routines.h:30
const int * pos
Definition: combiners.h:905
float x
Definition: cordic.py:15
char * filename[256]
Definition: pbmtopk.c:46
int r
Definition: ppmqvga.c:68
bstring c int memset(void *s, int c, int length)
#define status
static void chunk(LexState *ls)
Definition: minilua.c:4678
#define parent(a, t)
Definition: interp.c:105
static void(* trap)(void)
Definition: memory.c:38
lft_cell * left
Definition: routines.h:73
static FILE * in
Definition: squeeze.c:36
cairo_point_t p2
cairo_point_t p1
cairo_trapezoid_t * traps
unsigned int is_rectangular
unsigned int is_rectilinear
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
struct quorem x
struct edge * prev
struct edge * next
Definition: filedef.h:30
Definition: ttf.h:354
#define FILE
Definition: t1stdio.h:34
int j
Definition: t4ht.c:1589
char * file
Definition: t4ht.c:931
@ start
Definition: preamble.c:52