Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | 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-private.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.             sweep->spans[n].x = prev_x;
  383.             sweep->spans[n].coverage = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
  384.             sweep->spans[n].coverage -= sweep->spans[n].coverage >> 8;
  385.             prev_coverage = coverage;
  386.         }
  387.  
  388.         coverage += cell->covered;
  389.         if (coverage != prev_coverage) {
  390.             int n = sweep->num_spans++;
  391.             sweep->spans[n].x = cell->x;
  392.             sweep->spans[n].coverage = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
  393.             sweep->spans[n].coverage -= sweep->spans[n].coverage >> 8;
  394.             prev_coverage = coverage;
  395.         }
  396.         coverage += cell->uncovered;
  397.         prev_x = cell->x + 1;
  398.     }
  399.     _cairo_freepool_reset (&sweep->coverage.pool);
  400.  
  401.     if (sweep->num_spans) {
  402.         if (prev_x <= sweep->xmax) {
  403.             int n = sweep->num_spans++;
  404.             sweep->spans[n].x = prev_x;
  405.             sweep->spans[n].coverage = coverage;
  406.         }
  407.  
  408.         if (coverage && prev_x < sweep->xmax) {
  409.             int n = sweep->num_spans++;
  410.             sweep->spans[n].x = sweep->xmax;
  411.             sweep->spans[n].coverage = 0;
  412.         }
  413.     }
  414. }
  415.  
  416. static inline void
  417. sweep_line_delete (sweep_line_t *sweep,
  418.                              rectangle_t        *rectangle)
  419. {
  420.     if (sweep->insert_cursor == rectangle)
  421.         sweep->insert_cursor = rectangle->next;
  422.  
  423.     rectangle->prev->next = rectangle->next;
  424.     rectangle->next->prev = rectangle->prev;
  425.  
  426.     pqueue_pop (&sweep->stop);
  427. }
  428.  
  429. static inline void
  430. sweep_line_insert (sweep_line_t *sweep,
  431.                    rectangle_t  *rectangle)
  432. {
  433.     rectangle_t *pos;
  434.  
  435.     pos = sweep->insert_cursor;
  436.     if (pos->left != rectangle->left) {
  437.         if (pos->left > rectangle->left) {
  438.             do {
  439.                 UNROLL3({
  440.                     if (pos->prev->left < rectangle->left)
  441.                         break;
  442.                     pos = pos->prev;
  443.                 })
  444.             } while (TRUE);
  445.         } else {
  446.             do {
  447.                 UNROLL3({
  448.                     pos = pos->next;
  449.                     if (pos->left >= rectangle->left)
  450.                         break;
  451.                 });
  452.             } while (TRUE);
  453.         }
  454.     }
  455.  
  456.     pos->prev->next = rectangle;
  457.     rectangle->prev = pos->prev;
  458.     rectangle->next = pos;
  459.     pos->prev = rectangle;
  460.     sweep->insert_cursor = rectangle;
  461.  
  462.     pqueue_push (sweep, rectangle);
  463. }
  464.  
  465. static void
  466. render_rows (sweep_line_t *sweep_line,
  467.              cairo_span_renderer_t *renderer,
  468.              int height)
  469. {
  470.     cairo_status_t status;
  471.  
  472.     _active_edges_to_spans (sweep_line);
  473.  
  474.     status = renderer->render_rows (renderer,
  475.                                     sweep_line->current_y, height,
  476.                                     sweep_line->spans,
  477.                                     sweep_line->num_spans);
  478.     if (unlikely (status))
  479.         longjmp (sweep_line->jmpbuf, status);
  480. }
  481.  
  482. static cairo_status_t
  483. generate (cairo_rectangular_scan_converter_t *self,
  484.           cairo_span_renderer_t *renderer,
  485.           rectangle_t **rectangles)
  486. {
  487.     sweep_line_t sweep_line;
  488.     rectangle_t *start, *stop;
  489.     cairo_status_t status;
  490.  
  491.     sweep_line_init (&sweep_line);
  492.     sweep_line.xmin = self->xmin;
  493.     sweep_line.xmax = self->xmax;
  494.     sweep_line.start = rectangles;
  495.     if ((status = setjmp (sweep_line.jmpbuf)))
  496.         goto BAIL;
  497.  
  498.     sweep_line.current_y = self->ymin;
  499.     start = *sweep_line.start++;
  500.     do {
  501.         if (start->top_y != sweep_line.current_y) {
  502.             render_rows (&sweep_line, renderer,
  503.                          start->top_y - sweep_line.current_y);
  504.             sweep_line.current_y = start->top_y;
  505.         }
  506.  
  507.         do {
  508.             sweep_line_insert (&sweep_line, start);
  509.             start = *sweep_line.start++;
  510.             if (start == NULL)
  511.                 goto end;
  512.             if (start->top_y != sweep_line.current_y)
  513.                 break;
  514.         } while (TRUE);
  515.  
  516.         render_rows (&sweep_line, renderer, 1);
  517.  
  518.         stop = peek_stop (&sweep_line);
  519.         while (stop->bottom_y == sweep_line.current_y) {
  520.             sweep_line_delete (&sweep_line, stop);
  521.             stop = peek_stop (&sweep_line);
  522.             if (stop == NULL)
  523.                 break;
  524.         }
  525.  
  526.         sweep_line.current_y++;
  527.  
  528.         while (stop != NULL && stop->bottom_y < start->top_y) {
  529.             if (stop->bottom_y != sweep_line.current_y) {
  530.                 render_rows (&sweep_line, renderer,
  531.                              stop->bottom_y - sweep_line.current_y);
  532.                 sweep_line.current_y = stop->bottom_y;
  533.             }
  534.  
  535.             render_rows (&sweep_line, renderer, 1);
  536.  
  537.             do {
  538.                 sweep_line_delete (&sweep_line, stop);
  539.                 stop = peek_stop (&sweep_line);
  540.             } while (stop != NULL && stop->bottom_y == sweep_line.current_y);
  541.  
  542.             sweep_line.current_y++;
  543.         }
  544.     } while (TRUE);
  545.  
  546.   end:
  547.     render_rows (&sweep_line, renderer, 1);
  548.  
  549.     stop = peek_stop (&sweep_line);
  550.     while (stop->bottom_y == sweep_line.current_y) {
  551.         sweep_line_delete (&sweep_line, stop);
  552.         stop = peek_stop (&sweep_line);
  553.         if (stop == NULL)
  554.             goto out;
  555.     }
  556.  
  557.     sweep_line.current_y++;
  558.  
  559.     do {
  560.         if (stop->bottom_y != sweep_line.current_y) {
  561.             render_rows (&sweep_line, renderer,
  562.                          stop->bottom_y - sweep_line.current_y);
  563.             sweep_line.current_y = stop->bottom_y;
  564.         }
  565.  
  566.         render_rows (&sweep_line, renderer, 1);
  567.  
  568.         do {
  569.             sweep_line_delete (&sweep_line, stop);
  570.             stop = peek_stop (&sweep_line);
  571.             if (stop == NULL)
  572.                 goto out;
  573.         } while (stop->bottom_y == sweep_line.current_y);
  574.  
  575.         sweep_line.current_y++;
  576.     } while (TRUE);
  577.  
  578.   out:
  579.     status =  renderer->render_rows (renderer,
  580.                                      sweep_line.current_y,
  581.                                      self->ymax - sweep_line.current_y,
  582.                                      NULL, 0);
  583.  
  584.   BAIL:
  585.     sweep_line_fini (&sweep_line);
  586.  
  587.     return status;
  588. }
  589.  
  590. static cairo_status_t
  591. _cairo_rectangular_scan_converter_generate (void                        *converter,
  592.                                             cairo_span_renderer_t       *renderer)
  593. {
  594.     cairo_rectangular_scan_converter_t *self = converter;
  595.     rectangle_t *rectangles_stack[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *)];
  596.     rectangle_t **rectangles;
  597.     struct _cairo_rectangular_scan_converter_chunk *chunk;
  598.     cairo_status_t status;
  599.     int i, j;
  600.  
  601.     if (unlikely (self->num_rectangles == 0)) {
  602.         return renderer->render_rows (renderer,
  603.                                       self->ymin, self->ymax - self->ymin,
  604.                                       NULL, 0);
  605.     }
  606.  
  607.     rectangles = rectangles_stack;
  608.     if (unlikely (self->num_rectangles >= ARRAY_LENGTH (rectangles_stack))) {
  609.         rectangles = _cairo_malloc_ab (self->num_rectangles + 1,
  610.                                        sizeof (rectangle_t *));
  611.         if (unlikely (rectangles == NULL))
  612.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  613.     }
  614.  
  615.     j = 0;
  616.     for (chunk = &self->chunks; chunk != NULL; chunk = chunk->next) {
  617.         rectangle_t *rectangle;
  618.  
  619.         rectangle = chunk->base;
  620.         for (i = 0; i < chunk->count; i++)
  621.             rectangles[j++] = &rectangle[i];
  622.     }
  623.     rectangle_sort (rectangles, j);
  624.     rectangles[j] = NULL;
  625.  
  626.     status = generate (self, renderer, rectangles);
  627.  
  628.     if (rectangles != rectangles_stack)
  629.         free (rectangles);
  630.  
  631.     return status;
  632. }
  633.  
  634. static rectangle_t *
  635. _allocate_rectangle (cairo_rectangular_scan_converter_t *self)
  636. {
  637.     rectangle_t *rectangle;
  638.     struct _cairo_rectangular_scan_converter_chunk *chunk;
  639.  
  640.     chunk = self->tail;
  641.     if (chunk->count == chunk->size) {
  642.         int size;
  643.  
  644.         size = chunk->size * 2;
  645.         chunk->next = _cairo_malloc_ab_plus_c (size,
  646.                                                sizeof (rectangle_t),
  647.                                                sizeof (struct _cairo_rectangular_scan_converter_chunk));
  648.  
  649.         if (unlikely (chunk->next == NULL))
  650.             return NULL;
  651.  
  652.         chunk = chunk->next;
  653.         chunk->next = NULL;
  654.         chunk->count = 0;
  655.         chunk->size = size;
  656.         chunk->base = chunk + 1;
  657.         self->tail = chunk;
  658.     }
  659.  
  660.     rectangle = chunk->base;
  661.     return rectangle + chunk->count++;
  662. }
  663.  
  664. cairo_status_t
  665. _cairo_rectangular_scan_converter_add_box (cairo_rectangular_scan_converter_t *self,
  666.                                            const cairo_box_t *box,
  667.                                            int dir)
  668. {
  669.     rectangle_t *rectangle;
  670.  
  671.     rectangle = _allocate_rectangle (self);
  672.     if (unlikely (rectangle == NULL))
  673.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  674.  
  675.     rectangle->left  = box->p1.x;
  676.     rectangle->right = box->p2.x;
  677.     rectangle->dir = dir;
  678.  
  679.     rectangle->top = box->p1.y;
  680.     rectangle->top_y  = _cairo_fixed_integer_floor (box->p1.y);
  681.     rectangle->bottom = box->p2.y;
  682.     rectangle->bottom_y = _cairo_fixed_integer_floor (box->p2.y);
  683.     assert (rectangle->bottom_y >= rectangle->top_y);
  684.  
  685.     self->num_rectangles++;
  686.  
  687.     return CAIRO_STATUS_SUCCESS;
  688. }
  689.  
  690. static void
  691. _cairo_rectangular_scan_converter_destroy (void *converter)
  692. {
  693.     cairo_rectangular_scan_converter_t *self = converter;
  694.     struct _cairo_rectangular_scan_converter_chunk *chunk, *next;
  695.  
  696.     for (chunk = self->chunks.next; chunk != NULL; chunk = next) {
  697.         next = chunk->next;
  698.         free (chunk);
  699.     }
  700. }
  701.  
  702. void
  703. _cairo_rectangular_scan_converter_init (cairo_rectangular_scan_converter_t *self,
  704.                                         const cairo_rectangle_int_t *extents)
  705. {
  706.     self->base.destroy = _cairo_rectangular_scan_converter_destroy;
  707.     self->base.add_edge = NULL;
  708.     self->base.add_polygon = NULL;
  709.     self->base.generate = _cairo_rectangular_scan_converter_generate;
  710.  
  711.     self->xmin = extents->x;
  712.     self->xmax = extents->x + extents->width;
  713.     self->ymin = extents->y;
  714.     self->ymax = extents->y + extents->height;
  715.  
  716.     self->chunks.base = self->buf;
  717.     self->chunks.next = NULL;
  718.     self->chunks.count = 0;
  719.     self->chunks.size = sizeof (self->buf) / sizeof (rectangle_t);
  720.     self->tail = &self->chunks;
  721.  
  722.     self->num_rectangles = 0;
  723. }
  724.