Bug Summary

File:root/firefox-clang/gfx/cairo/cairo/src/cairo-bentley-ottmann-rectangular.c
Warning:line 639, column 3
Value stored to 'update' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name cairo-bentley-ottmann-rectangular.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -ffp-contract=off -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/root/firefox-clang/obj-x86_64-pc-linux-gnu/gfx/cairo/cairo/src -fcoverage-compilation-dir=/root/firefox-clang/obj-x86_64-pc-linux-gnu/gfx/cairo/cairo/src -resource-dir /usr/lib/llvm-21/lib/clang/21 -include /root/firefox-clang/config/gcc_hidden.h -include /root/firefox-clang/obj-x86_64-pc-linux-gnu/mozilla-config.h -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/system_wrappers -U _FORTIFY_SOURCE -D _FORTIFY_SOURCE=2 -D _GLIBCXX_ASSERTIONS -D DEBUG=1 -D HAVE_FT_LOAD_SFNT_TABLE -D PACKAGE_VERSION="moz" -D PACKAGE_BUGREPORT="http://bugzilla.mozilla.org/" -D CAIRO_HAS_PTHREAD -D _GNU_SOURCE -D MOZ_TREE_PIXMAN -D SIZEOF_VOID_P=__SIZEOF_POINTER__ -D SIZEOF_INT=__SIZEOF_INT__ -D SIZEOF_LONG=__SIZEOF_LONG__ -D SIZEOF_LONG_LONG=__SIZEOF_LONG_LONG__ -D HAVE_UINT64_T -D HAVE_CXX11_ATOMIC_PRIMITIVES -D MOZ_HAS_MOZGLUE -D MOZILLA_INTERNAL_API -D IMPL_LIBXUL -D MOZ_SUPPORT_LEAKCHECKING -D STATIC_EXPORTABLE_JS_API -I /root/firefox-clang/gfx/cairo/cairo/src -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/gfx/cairo/cairo/src -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/nspr -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/nss -D MOZILLA_CLIENT -I /usr/include/freetype2 -I /usr/include/libpng16 -I /usr/include/freetype2 -I /usr/include/libpng16 -internal-isystem /usr/lib/llvm-21/lib/clang/21/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-error=tautological-type-limit-compare -Wno-range-loop-analysis -Wno-error=deprecated-declarations -Wno-error=array-bounds -Wno-error=free-nonheap-object -Wno-error=atomic-alignment -Wno-error=deprecated-builtins -Wno-psabi -Wno-error=builtin-macro-redefined -Wno-unknown-warning-option -Wno-enum-compare -Wno-int-to-pointer-cast -Wno-int-conversion -Wno-incompatible-pointer-types -Wno-sign-compare -Wno-type-limits -Wno-missing-field-initializers -Wno-conversion -Wno-narrowing -Wno-switch -Wno-unused -Wno-unused-variable -Wno-error=uninitialized -Wno-absolute-value -Wno-deprecated-register -Wno-incompatible-pointer-types -Wno-macro-redefined -Wno-shift-negative-value -Wno-tautological-compare -Wno-tautological-constant-out-of-range-compare -Wno-unreachable-code -ferror-limit 19 -fstrict-flex-arrays=1 -stack-protector 2 -fstack-clash-protection -ftrivial-auto-var-init=pattern -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2025-06-26-231904-1820671-1 -x c /root/firefox-clang/gfx/cairo/cairo/src/cairo-bentley-ottmann-rectangular.c
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
49typedef struct _rectangle rectangle_t;
50typedef struct _edge edge_t;
51
52struct _edge {
53 edge_t *next, *prev;
54 edge_t *right;
55 cairo_fixed_t x, top;
56 int dir;
57};
58
59struct _rectangle {
60 edge_t left, right;
61 int32_t top, bottom;
62};
63
64#define UNROLL3(x)x x x x x x
65
66/* the parent is always given by index/2 */
67#define PQ_PARENT_INDEX(i)((i) >> 1) ((i) >> 1)
68#define PQ_FIRST_ENTRY1 1
69
70/* left and right children are index * 2 and (index * 2) +1 respectively */
71#define PQ_LEFT_CHILD_INDEX(i)((i) << 1) ((i) << 1)
72
73typedef struct _sweep_line {
74 rectangle_t **rectangles;
75 rectangle_t **stop;
76 edge_t head, tail, *insert, *cursor;
77 int32_t current_y;
78 int32_t last_y;
79 int stop_size;
80
81 int32_t insert_x;
82 cairo_fill_rule_t fill_rule;
83
84 cairo_bool_t do_traps;
85 void *container;
86
87 jmp_buf unwind;
88} sweep_line_t;
89
90#define DEBUG_TRAPS0 0
91
92#if DEBUG_TRAPS0
93static void
94dump_traps (cairo_traps_t *traps, const char *filename)
95{
96 FILE *file;
97 int n;
98
99 if (getenv ("CAIRO_DEBUG_TRAPS") == NULL((void*)0))
100 return;
101
102 file = fopen (filename, "a");
103 if (file != NULL((void*)0)) {
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
125static inline int
126rectangle_compare_start (const rectangle_t *a,
127 const rectangle_t *b)
128{
129 return a->top - b->top;
130}
131
132static inline int
133rectangle_compare_stop (const rectangle_t *a,
134 const rectangle_t *b)
135{
136 return a->bottom - b->bottom;
137}
138
139static inline void
140pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
141{
142 rectangle_t **elements;
143 int i, parent;
144
145 elements = sweep->stop;
146 for (i = ++sweep->stop_size;
147 i != PQ_FIRST_ENTRY1 &&
148 rectangle_compare_stop (rectangle,
149 elements[parent = PQ_PARENT_INDEX (i)((i) >> 1)]) < 0;
150 i = parent)
151 {
152 elements[i] = elements[parent];
153 }
154
155 elements[i] = rectangle;
156}
157
158static inline void
159rectangle_pop_stop (sweep_line_t *sweep)
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) {
167 elements[PQ_FIRST_ENTRY1] = NULL((void*)0);
168 return;
169 }
170
171 for (i = PQ_FIRST_ENTRY1;
172 (child = PQ_LEFT_CHILD_INDEX (i)((i) << 1)) <= sweep->stop_size;
173 i = child)
174 {
175 if (child != sweep->stop_size &&
176 rectangle_compare_stop (elements[child+1],
177 elements[child]) < 0)
178 {
179 child++;
180 }
181
182 if (rectangle_compare_stop (elements[child], tail) >= 0)
183 break;
184
185 elements[i] = elements[child];
186 }
187 elements[i] = tail;
188}
189
190static inline rectangle_t *
191rectangle_pop_start (sweep_line_t *sweep_line)
192{
193 return *sweep_line->rectangles++;
194}
195
196static inline rectangle_t *
197rectangle_peek_stop (sweep_line_t *sweep_line)
198{
199 return sweep_line->stop[PQ_FIRST_ENTRY1];
200}
201
202CAIRO_COMBSORT_DECLARE (_rectangle_sort,static void _rectangle_sort (rectangle_t * *base, unsigned int
nmemb) { unsigned int gap = nmemb; unsigned int i, j; int swapped
; do { gap = _cairo_combsort_newgap (gap); swapped = gap >
1; for (i = 0; i < nmemb-gap ; i++) { j = i + gap; if (rectangle_compare_start
(base[i], base[j]) > 0 ) { rectangle_t * tmp; tmp = base[
i]; base[i] = base[j]; base[j] = tmp; swapped = 1; } } } while
(swapped); }
203 rectangle_t *,static void _rectangle_sort (rectangle_t * *base, unsigned int
nmemb) { unsigned int gap = nmemb; unsigned int i, j; int swapped
; do { gap = _cairo_combsort_newgap (gap); swapped = gap >
1; for (i = 0; i < nmemb-gap ; i++) { j = i + gap; if (rectangle_compare_start
(base[i], base[j]) > 0 ) { rectangle_t * tmp; tmp = base[
i]; base[i] = base[j]; base[j] = tmp; swapped = 1; } } } while
(swapped); }
204 rectangle_compare_start)static void _rectangle_sort (rectangle_t * *base, unsigned int
nmemb) { unsigned int gap = nmemb; unsigned int i, j; int swapped
; do { gap = _cairo_combsort_newgap (gap); swapped = gap >
1; for (i = 0; i < nmemb-gap ; i++) { j = i + gap; if (rectangle_compare_start
(base[i], base[j]) > 0 ) { rectangle_t * tmp; tmp = base[
i]; base[i] = base[j]; base[j] = tmp; swapped = 1; } } } while
(swapped); }
205
206static void
207sweep_line_init (sweep_line_t *sweep_line,
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((void*)0);
215 rectangles[-1] = NULL((void*)0);
216 rectangles[num_rectangles] = NULL((void*)0);
217 sweep_line->rectangles = rectangles;
218 sweep_line->stop = rectangles - 2;
219 sweep_line->stop_size = 0;
220
221 sweep_line->insert = NULL((void*)0);
222 sweep_line->insert_x = INT_MAX2147483647;
223 sweep_line->cursor = &sweep_line->tail;
224
225 sweep_line->head.dir = 0;
226 sweep_line->head.x = INT32_MIN(-2147483647-1);
227 sweep_line->head.right = NULL((void*)0);
228 sweep_line->head.prev = NULL((void*)0);
229 sweep_line->head.next = &sweep_line->tail;
230 sweep_line->tail.prev = &sweep_line->head;
231 sweep_line->tail.next = NULL((void*)0);
232 sweep_line->tail.right = NULL((void*)0);
233 sweep_line->tail.x = INT32_MAX(2147483647);
234 sweep_line->tail.dir = 0;
235
236 sweep_line->current_y = INT32_MIN(-2147483647-1);
237 sweep_line->last_y = INT32_MIN(-2147483647-1);
238
239 sweep_line->fill_rule = fill_rule;
240 sweep_line->container = container;
241 sweep_line->do_traps = do_traps;
242}
243
244static void
245edge_end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot)
246{
247 cairo_status_t status = CAIRO_STATUS_SUCCESS;
248
249 /* Only emit (trivial) non-degenerate trapezoids with positive height. */
250 if (likely (left->top < bot)(__builtin_expect (!!(left->top < bot), 1))) {
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)((cairo_traps_t *) sweep_line->container)->status;
261 } else {
262 cairo_box_t box;
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,
270 CAIRO_ANTIALIAS_DEFAULT,
271 &box);
272 }
273 }
274 if (unlikely (status)(__builtin_expect (!!(status), 0)))
275 longjmp (sweep_line->unwind, status);
276
277 left->right = NULL((void*)0);
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. */
285static inline void
286edge_start_or_continue_box (sweep_line_t *sweep_line,
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((void*)0)) {
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 */
327static edge_t *
328merge_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((void*)0) && 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((void*)0))
352 return head;
353
354start_with_b:
355 x = head_a->x;
356 while (head_b != NULL((void*)0) && 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((void*)0))
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 */
385static edge_t *
386sort_edges (edge_t *list,
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((void*)0)) {
396 *head_out = list;
397 return NULL((void*)0);
398 }
399
400 remaining = head_other->next;
401 if (list->x <= head_other->x) {
402 *head_out = list;
403 head_other->next = NULL((void*)0);
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((void*)0);
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
420static edge_t *
421merge_unsorted_edges (edge_t *head, edge_t *unsorted)
422{
423 sort_edges (unsorted, UINT_MAX(2147483647 *2U +1U), &unsorted);
424 return merge_sorted_edges (head, unsorted);
425}
426
427static void
428active_edges_insert (sweep_line_t *sweep)
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((void*)0);
447 sweep->insert_x = INT_MAX2147483647;
448}
449
450static inline void
451active_edges_to_traps (sweep_line_t *sweep)
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((void*)0)) {
479 assert (left->right == NULL)((void) sizeof ((left->right == ((void*)0)) ? 1 : 0), __extension__
({ if (left->right == ((void*)0)) ; else __assert_fail ("left->right == NULL"
, "/root/firefox-clang/gfx/cairo/cairo/src/cairo-bentley-ottmann-rectangular.c"
, 479, __extension__ __PRETTY_FUNCTION__); }));
480 /* continuation on left */
481 left->top = right->top;
482 left->right = right->right;
483 right->right = NULL((void*)0);
484 }
485 winding += right->dir;
486 right = right->next;
487 }
488
489 if (winding == 0) {
490 if (left->right != NULL((void*)0))
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)(__builtin_expect (!!(right->right != ((void*)0)), 0)))
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 (TRUE1);
511
512 edge_start_or_continue_box (sweep, left, right, top);
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)(__builtin_expect (!!(right->right != ((void*)0)), 0)))
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 (TRUE1);
532
533 edge_start_or_continue_box (sweep, pos, right, top);
534
535 pos = right->next;
536 } while (pos != &sweep->tail);
537 }
538
539 sweep->last_y = sweep->current_y;
540}
541
542static inline void
543sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
544{
545 if (edge->right != NULL((void*)0)) {
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
561static inline cairo_bool_t
562sweep_line_delete (sweep_line_t *sweep, rectangle_t *rectangle)
563{
564 cairo_bool_t update;
565
566 update = TRUE1;
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
580static inline void
581sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
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((void*)0);
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
596static cairo_status_t
597_cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
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;
605 cairo_status_t status;
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)_setjmp (sweep_line.unwind)))
613 return status;
614
615 update = FALSE0;
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((void*)0) && stop->bottom < rectangle->top) {
624 if (stop->bottom != sweep_line.current_y) {
625 if (update) {
626 active_edges_to_traps (&sweep_line);
627 update = FALSE0;
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 = FALSE0;
Value stored to 'update' is never read
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((void*)0) &&
648 sweep_line.current_y == rectangle->top);
649 update = TRUE1;
650 } while (rectangle);
651
652 while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL((void*)0)) {
653 if (rectangle->bottom != sweep_line.current_y) {
654 if (update) {
655 active_edges_to_traps (&sweep_line);
656 update = FALSE0;
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
667cairo_status_t
668_cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
669 cairo_fill_rule_t fill_rule)
670{
671 rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)((512 * sizeof (int)) / sizeof(rectangle_t))];
672 rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles)((int) (sizeof (stack_rectangles) / sizeof (stack_rectangles[
0]))) + 3];
673 rectangle_t *rectangles, **rectangles_ptrs;
674 cairo_status_t status;
675 int i;
676
677 assert (traps->is_rectangular)((void) sizeof ((traps->is_rectangular) ? 1 : 0), __extension__
({ if (traps->is_rectangular) ; else __assert_fail ("traps->is_rectangular"
, "/root/firefox-clang/gfx/cairo/cairo/src/cairo-bentley-ottmann-rectangular.c"
, 677, __extension__ __PRETTY_FUNCTION__); }));
678
679 if (unlikely (traps->num_traps <= 1)(__builtin_expect (!!(traps->num_traps <= 1), 0))) {
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)((int) (sizeof (stack_rectangles) / sizeof (stack_rectangles[
0])))) {
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)(__builtin_expect (!!(rectangles == ((void*)0)), 0)))
701 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
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((void*)0);
722 rectangles[i].right.right = NULL((void*)0);
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);
733 status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
734 fill_rule,
735 TRUE1, traps);
736 traps->is_rectilinear = TRUE1;
737 traps->is_rectangular = TRUE1;
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
747cairo_status_t
748_cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
749 cairo_fill_rule_t fill_rule,
750 cairo_boxes_t *out)
751{
752 rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)((512 * sizeof (int)) / sizeof(rectangle_t))];
753 rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles)((int) (sizeof (stack_rectangles) / sizeof (stack_rectangles[
0]))) + 3];
754 rectangle_t *rectangles, **rectangles_ptrs;
755 rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *)((512 * sizeof (int)) / sizeof(rectangle_t *)) ];
756 rectangle_t **rectangles_chain = NULL((void*)0);
757 const struct _cairo_boxes_chunk *chunk;
758 cairo_status_t status;
759 int i, j, y_min, y_max;
760
761 if (unlikely (in->num_boxes == 0)(__builtin_expect (!!(in->num_boxes == 0), 0))) {
762 _cairo_boxes_clear (out);
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
784 _cairo_boxes_clear (out);
785 status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
786 assert (status == CAIRO_STATUS_SUCCESS)((void) sizeof ((status == CAIRO_STATUS_SUCCESS) ? 1 : 0), __extension__
({ if (status == CAIRO_STATUS_SUCCESS) ; else __assert_fail (
"status == CAIRO_STATUS_SUCCESS", "/root/firefox-clang/gfx/cairo/cairo/src/cairo-bentley-ottmann-rectangular.c"
, 786, __extension__ __PRETTY_FUNCTION__); }));
787 }
788 return CAIRO_STATUS_SUCCESS;
789 }
790
791 y_min = INT_MAX2147483647; y_max = INT_MIN(-2147483647 -1);
792 for (chunk = &in->chunks; chunk != NULL((void*)0); 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 }
801 y_min = _cairo_fixed_integer_floor (y_min);
802 y_max = _cairo_fixed_integer_floor (y_max) + 1;
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)((int) (sizeof (stack_rectangles_chain) / sizeof (stack_rectangles_chain
[0])))) {
808 rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
809 if (unlikely (rectangles_chain == NULL)(__builtin_expect (!!(rectangles_chain == ((void*)0)), 0)))
810 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
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)((int) (sizeof (stack_rectangles) / sizeof (stack_rectangles[
0])))) {
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)(__builtin_expect (!!(rectangles == ((void*)0)), 0))) {
823 if (rectangles_chain != stack_rectangles_chain)
824 free (rectangles_chain);
825 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
826 }
827
828 rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
829 }
830
831 j = 0;
832 for (chunk = &in->chunks; chunk != NULL((void*)0); 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((void*)0);
852 rectangles[j].right.right = NULL((void*)0);
853
854 rectangles[j].top = box[i].p1.y;
855 rectangles[j].bottom = box[i].p2.y;
856
857 if (rectangles_chain) {
858 h = _cairo_fixed_integer_floor (box[i].p1.y) - y_min;
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
887 _cairo_boxes_clear (out);
888 status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j,
889 fill_rule,
890 FALSE0, out);
891 if (rectangles != stack_rectangles)
892 free (rectangles);
893
894 return status;
895}