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 Chris Wilson
  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.  * The Initial Developer of the Original Code is Chris Wilson.
  31.  *
  32.  * Contributor(s):
  33.  *      Chris Wilson <chris@chris-wilson.co.uk>
  34.  *
  35.  */
  36.  
  37. #include "cairoint.h"
  38.  
  39. #include "cairo-error-private.h"
  40. #include "cairo-rtree-private.h"
  41.  
  42. cairo_rtree_node_t *
  43. _cairo_rtree_node_create (cairo_rtree_t          *rtree,
  44.                           cairo_rtree_node_t     *parent,
  45.                           int                     x,
  46.                           int                     y,
  47.                           int                     width,
  48.                           int                     height)
  49. {
  50.     cairo_rtree_node_t *node;
  51.  
  52.     node = _cairo_freepool_alloc (&rtree->node_freepool);
  53.     if (node == NULL) {
  54.         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
  55.         return NULL;
  56.     }
  57.  
  58.     node->children[0] = NULL;
  59.     node->parent = parent;
  60.     node->owner  = NULL;
  61.     node->state  = CAIRO_RTREE_NODE_AVAILABLE;
  62.     node->pinned = FALSE;
  63.     node->x      = x;
  64.     node->y      = y;
  65.     node->width  = width;
  66.     node->height = height;
  67.  
  68.     cairo_list_add (&node->link, &rtree->available);
  69.  
  70.     return node;
  71. }
  72.  
  73. void
  74. _cairo_rtree_node_destroy (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  75. {
  76.     int i;
  77.  
  78.     cairo_list_del (&node->link);
  79.  
  80.     if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
  81.         if (node->owner != NULL)
  82.             *node->owner = NULL;
  83.     } else {
  84.         for (i = 0; i < 4 && node->children[i] != NULL; i++)
  85.             _cairo_rtree_node_destroy (rtree, node->children[i]);
  86.     }
  87.  
  88.     _cairo_freepool_free (&rtree->node_freepool, node);
  89. }
  90.  
  91. void
  92. _cairo_rtree_node_collapse (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  93. {
  94.     int i;
  95.  
  96.     do {
  97.         assert (node->state == CAIRO_RTREE_NODE_DIVIDED);
  98.  
  99.         for (i = 0;  i < 4 && node->children[i] != NULL; i++)
  100.             if (node->children[i]->state != CAIRO_RTREE_NODE_AVAILABLE)
  101.                 return;
  102.  
  103.         for (i = 0; i < 4 && node->children[i] != NULL; i++)
  104.             _cairo_rtree_node_destroy (rtree, node->children[i]);
  105.  
  106.         node->children[0] = NULL;
  107.         node->state = CAIRO_RTREE_NODE_AVAILABLE;
  108.         cairo_list_move (&node->link, &rtree->available);
  109.     } while ((node = node->parent) != NULL);
  110. }
  111.  
  112. cairo_status_t
  113. _cairo_rtree_node_insert (cairo_rtree_t *rtree,
  114.                           cairo_rtree_node_t *node,
  115.                           int width,
  116.                           int height,
  117.                           cairo_rtree_node_t **out)
  118. {
  119.     int w, h, i;
  120.  
  121.     assert (node->state == CAIRO_RTREE_NODE_AVAILABLE);
  122.     assert (node->pinned == FALSE);
  123.  
  124.     if (node->width  - width  > rtree->min_size ||
  125.         node->height - height > rtree->min_size)
  126.     {
  127.         w = node->width  - width;
  128.         h = node->height - height;
  129.  
  130.         i = 0;
  131.         node->children[i] = _cairo_rtree_node_create (rtree, node,
  132.                                                       node->x, node->y,
  133.                                                       width, height);
  134.         if (unlikely (node->children[i] == NULL))
  135.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  136.         i++;
  137.  
  138.         if (w > rtree->min_size) {
  139.             node->children[i] = _cairo_rtree_node_create (rtree, node,
  140.                                                           node->x + width,
  141.                                                           node->y,
  142.                                                           w, height);
  143.             if (unlikely (node->children[i] == NULL))
  144.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  145.             i++;
  146.         }
  147.  
  148.         if (h > rtree->min_size) {
  149.             node->children[i] = _cairo_rtree_node_create (rtree, node,
  150.                                                           node->x,
  151.                                                           node->y + height,
  152.                                                           width, h);
  153.             if (unlikely (node->children[i] == NULL))
  154.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  155.             i++;
  156.  
  157.             if (w > rtree->min_size) {
  158.                 node->children[i] = _cairo_rtree_node_create (rtree, node,
  159.                                                               node->x + width,
  160.                                                               node->y + height,
  161.                                                               w, h);
  162.                 if (unlikely (node->children[i] == NULL))
  163.                     return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  164.                 i++;
  165.             }
  166.         }
  167.  
  168.         if (i < 4)
  169.             node->children[i] = NULL;
  170.  
  171.         node->state = CAIRO_RTREE_NODE_DIVIDED;
  172.         cairo_list_move (&node->link, &rtree->evictable);
  173.         node = node->children[0];
  174.     }
  175.  
  176.     node->state = CAIRO_RTREE_NODE_OCCUPIED;
  177.     cairo_list_move (&node->link, &rtree->evictable);
  178.     *out = node;
  179.  
  180.     return CAIRO_STATUS_SUCCESS;
  181. }
  182.  
  183. void
  184. _cairo_rtree_node_remove (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  185. {
  186.     assert (node->state == CAIRO_RTREE_NODE_OCCUPIED);
  187.     assert (node->pinned == FALSE);
  188.  
  189.     node->state = CAIRO_RTREE_NODE_AVAILABLE;
  190.     cairo_list_move (&node->link, &rtree->available);
  191.  
  192.     _cairo_rtree_node_collapse (rtree, node->parent);
  193. }
  194.  
  195. cairo_int_status_t
  196. _cairo_rtree_insert (cairo_rtree_t           *rtree,
  197.                      int                      width,
  198.                      int                      height,
  199.                      cairo_rtree_node_t     **out)
  200. {
  201.     cairo_rtree_node_t *node;
  202.  
  203.     cairo_list_foreach_entry (node, cairo_rtree_node_t,
  204.                               &rtree->available, link)
  205.     {
  206.         if (node->width >= width && node->height >= height)
  207.             return _cairo_rtree_node_insert (rtree, node, width, height, out);
  208.     }
  209.  
  210.     return CAIRO_INT_STATUS_UNSUPPORTED;
  211. }
  212.  
  213. static uint32_t
  214. hars_petruska_f54_1_random (void)
  215. {
  216. #define rol(x,k) ((x << k) | (x >> (32-k)))
  217.     static uint32_t x;
  218.     return x = (x ^ rol (x, 5) ^ rol (x, 24)) + 0x37798849;
  219. #undef rol
  220. }
  221.  
  222. cairo_int_status_t
  223. _cairo_rtree_evict_random (cairo_rtree_t         *rtree,
  224.                            int                    width,
  225.                            int                    height,
  226.                            cairo_rtree_node_t           **out)
  227. {
  228.     cairo_rtree_node_t *node, *next;
  229.     int i, cnt;
  230.  
  231.     /* propagate pinned from children to root */
  232.     cairo_list_foreach_entry_safe (node, next, cairo_rtree_node_t,
  233.                                    &rtree->pinned, link)
  234.     {
  235.         if (node->parent != NULL)
  236.             _cairo_rtree_pin (rtree, node->parent);
  237.     }
  238.  
  239.     cnt = 0;
  240.     cairo_list_foreach_entry (node, cairo_rtree_node_t,
  241.                               &rtree->evictable, link)
  242.     {
  243.         if (node->width >= width && node->height >= height)
  244.             cnt++;
  245.     }
  246.  
  247.     if (cnt == 0)
  248.         return CAIRO_INT_STATUS_UNSUPPORTED;
  249.  
  250.     cnt = hars_petruska_f54_1_random () % cnt;
  251.     cairo_list_foreach_entry (node, cairo_rtree_node_t,
  252.                               &rtree->evictable, link)
  253.     {
  254.         if (node->width >= width && node->height >= height && cnt-- == 0) {
  255.             if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
  256.                 if (node->owner != NULL)
  257.                     *node->owner = NULL;
  258.             } else {
  259.                 for (i = 0; i < 4 && node->children[i] != NULL; i++)
  260.                     _cairo_rtree_node_destroy (rtree, node->children[i]);
  261.                 node->children[0] = NULL;
  262.             }
  263.  
  264.             node->state = CAIRO_RTREE_NODE_AVAILABLE;
  265.             cairo_list_move (&node->link, &rtree->available);
  266.  
  267.             *out = node;
  268.             return CAIRO_STATUS_SUCCESS;
  269.         }
  270.     }
  271.  
  272.     return CAIRO_INT_STATUS_UNSUPPORTED;
  273. }
  274.  
  275. void
  276. _cairo_rtree_unpin (cairo_rtree_t *rtree)
  277. {
  278.     cairo_rtree_node_t *node, *next;
  279.     cairo_list_t can_collapse;
  280.  
  281.     if (cairo_list_is_empty (&rtree->pinned))
  282.         return;
  283.  
  284.     cairo_list_init (&can_collapse);
  285.  
  286.     cairo_list_foreach_entry_safe (node, next,
  287.                                    cairo_rtree_node_t,
  288.                                    &rtree->pinned,
  289.                                    link)
  290.     {
  291.         node->pinned = FALSE;
  292.         if (node->state == CAIRO_RTREE_NODE_OCCUPIED && node->owner == NULL) {
  293.             cairo_bool_t all_available;
  294.             int i;
  295.  
  296.             node->state = CAIRO_RTREE_NODE_AVAILABLE;
  297.             cairo_list_move (&node->link, &rtree->available);
  298.  
  299.             all_available = TRUE;
  300.             node = node->parent;
  301.             for (i = 0; i < 4 && node->children[i] != NULL && all_available; i++)
  302.                 all_available &= node->children[i]->state == CAIRO_RTREE_NODE_AVAILABLE;
  303.  
  304.             if (all_available) {
  305.                 cairo_list_move (&node->link, &can_collapse);
  306.                 for (i = 0;  i < 4 && node->children[i] != NULL; i++)
  307.                     cairo_list_del (&node->children[i]->link);
  308.             }
  309.         }
  310.         else
  311.         {
  312.             cairo_list_move (&node->link, &rtree->evictable);
  313.         }
  314.     }
  315.  
  316.     cairo_list_foreach_entry_safe (node, next,
  317.                                    cairo_rtree_node_t,
  318.                                    &can_collapse,
  319.                                    link)
  320.     {
  321.         _cairo_rtree_node_collapse (rtree, node);
  322.     }
  323. }
  324.  
  325. void
  326. _cairo_rtree_init (cairo_rtree_t        *rtree,
  327.                    int                   width,
  328.                    int                   height,
  329.                    int                   min_size,
  330.                    int                   node_size)
  331. {
  332.     assert (node_size >= (int) sizeof (cairo_rtree_node_t));
  333.     _cairo_freepool_init (&rtree->node_freepool, node_size);
  334.  
  335.     cairo_list_init (&rtree->available);
  336.     cairo_list_init (&rtree->pinned);
  337.     cairo_list_init (&rtree->evictable);
  338.  
  339.     rtree->min_size = min_size;
  340.  
  341.     memset (&rtree->root, 0, sizeof (rtree->root));
  342.     rtree->root.width = width;
  343.     rtree->root.height = height;
  344.     rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
  345.     cairo_list_add (&rtree->root.link, &rtree->available);
  346. }
  347.  
  348. void
  349. _cairo_rtree_reset (cairo_rtree_t *rtree)
  350. {
  351.     int i;
  352.  
  353.     if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
  354.         if (rtree->root.owner != NULL)
  355.             *rtree->root.owner = NULL;
  356.     } else {
  357.         for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
  358.             _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
  359.         rtree->root.children[0] = NULL;
  360.     }
  361.  
  362.     cairo_list_init (&rtree->available);
  363.     cairo_list_init (&rtree->evictable);
  364.     cairo_list_init (&rtree->pinned);
  365.  
  366.     rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
  367.     rtree->root.pinned = FALSE;
  368.     cairo_list_add (&rtree->root.link, &rtree->available);
  369. }
  370.  
  371. void
  372. _cairo_rtree_fini (cairo_rtree_t *rtree)
  373. {
  374.     int i;
  375.  
  376.     if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
  377.         if (rtree->root.owner != NULL)
  378.             *rtree->root.owner = NULL;
  379.     } else {
  380.         for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
  381.             _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
  382.     }
  383.  
  384.     _cairo_freepool_fini (&rtree->node_freepool);
  385. }
  386.