Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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;
  46.     cairo_fixed_t left, right;
  47.     cairo_fixed_t top, bottom;
  48.     int32_t top_y, bottom_y;
  49.     int dir;
  50. } rectangle_t;
  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.  
  64.     rectangle_t **elements;
  65.     rectangle_t *elements_embedded[1024];
  66. } pqueue_t;
  67.  
  68. typedef struct {
  69.     rectangle_t **start;
  70.     pqueue_t stop;
  71.     rectangle_t head, tail;
  72.     rectangle_t *insert_cursor;
  73.     int32_t current_y;
  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;
  82.         cairo_freepool_t pool;
  83.     } coverage;
  84.  
  85.     cairo_half_open_span_t spans_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_half_open_span_t)];
  86.     cairo_half_open_span_t *spans;
  87.     unsigned int num_spans;
  88.     unsigned int size_spans;
  89.  
  90.     jmp_buf jmpbuf;
  91. } sweep_line_t;
  92.  
  93. static inline int
  94. rectangle_compare_start (const rectangle_t *a,
  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
  107. rectangle_compare_stop (const rectangle_t *a,
  108.                         const rectangle_t *b)
  109. {
  110.     return a->bottom_y - b->bottom_y;
  111. }
  112.  
  113. static inline void
  114. pqueue_init (pqueue_t *pq)
  115. {
  116.     pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
  117.     pq->size = 0;
  118.  
  119.     pq->elements = pq->elements_embedded;
  120.     pq->elements[PQ_FIRST_ENTRY] = NULL;
  121. }
  122.  
  123. static inline void
  124. pqueue_fini (pqueue_t *pq)
  125. {
  126.     if (pq->elements != pq->elements_embedded)
  127.         free (pq->elements);
  128. }
  129.  
  130. static cairo_bool_t
  131. pqueue_grow (pqueue_t *pq)
  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
  157. pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
  158. {
  159.     rectangle_t **elements;
  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,
  165.                      _cairo_error (CAIRO_STATUS_NO_MEMORY));
  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.     {
  175.         elements[i] = elements[parent];
  176.     }
  177.  
  178.     elements[i] = rectangle;
  179. }
  180.  
  181. static inline void
  182. pqueue_pop (pqueue_t *pq)
  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) {
  190.         elements[PQ_FIRST_ENTRY] = NULL;
  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 &&
  199.             rectangle_compare_stop (elements[child+1],
  200.                                     elements[child]) < 0)
  201.         {
  202.             child++;
  203.         }
  204.  
  205.         if (rectangle_compare_stop (elements[child], tail) >= 0)
  206.             break;
  207.  
  208.         elements[i] = elements[child];
  209.     }
  210.     elements[i] = tail;
  211. }
  212.  
  213. static inline rectangle_t *
  214. peek_stop (sweep_line_t *sweep)
  215. {
  216.     return sweep->stop.elements[PQ_FIRST_ENTRY];
  217. }
  218.  
  219. CAIRO_COMBSORT_DECLARE (rectangle_sort, rectangle_t *, rectangle_compare_start)
  220.  
  221. static void
  222. sweep_line_init (sweep_line_t *sweep)
  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
  244. sweep_line_fini (sweep_line_t *sweep)
  245. {
  246.     _cairo_freepool_fini (&sweep->coverage.pool);
  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,
  288.                      _cairo_error (CAIRO_STATUS_NO_MEMORY));
  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
  310. _active_edges_to_spans (sweep_line_t    *sweep)
  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
  342.             height = CAIRO_FIXED_ONE;
  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.     }
  401.     _cairo_freepool_reset (&sweep->coverage.pool);
  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
  422. sweep_line_delete (sweep_line_t *sweep,
  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
  435. sweep_line_insert (sweep_line_t *sweep,
  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
  471. render_rows (sweep_line_t *sweep_line,
  472.              cairo_span_renderer_t *renderer,
  473.              int height)
  474. {
  475.     cairo_status_t status;
  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
  488. generate (cairo_rectangular_scan_converter_t *self,
  489.           cairo_span_renderer_t *renderer,
  490.           rectangle_t **rectangles)
  491. {
  492.     sweep_line_t sweep_line;
  493.     rectangle_t *start, *stop;
  494.     cairo_status_t status;
  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,
  588.                          uint16_t coverage)
  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
  629. generate_box (cairo_rectangular_scan_converter_t *self,
  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
  655. _cairo_rectangular_scan_converter_generate (void                        *converter,
  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;
  662.     cairo_status_t status;
  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))
  680.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  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 *
  703. _allocate_rectangle (cairo_rectangular_scan_converter_t *self)
  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;
  713.         chunk->next = _cairo_malloc_ab_plus_c (size,
  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.  
  732. cairo_status_t
  733. _cairo_rectangular_scan_converter_add_box (cairo_rectangular_scan_converter_t *self,
  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))
  741.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  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
  764. _cairo_rectangular_scan_converter_destroy (void *converter)
  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
  776. _cairo_rectangular_scan_converter_init (cairo_rectangular_scan_converter_t *self,
  777.                                         const cairo_rectangle_int_t *extents)
  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. }
  792.