Subversion Repositories Kolibri OS

Rev

Rev 1892 | Go to most recent revision | 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->state  = CAIRO_RTREE_NODE_AVAILABLE;
  61.     node->pinned = FALSE;
  62.     node->x      = x;
  63.     node->y      = y;
  64.     node->width  = width;
  65.     node->height = height;
  66.  
  67.     cairo_list_add (&node->link, &rtree->available);
  68.  
  69.     return node;
  70. }
  71.  
  72. void
  73. _cairo_rtree_node_destroy (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  74. {
  75.     int i;
  76.  
  77.     cairo_list_del (&node->link);
  78.  
  79.     if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
  80.         rtree->destroy (node);
  81.     } else {
  82.         for (i = 0; i < 4 && node->children[i] != NULL; i++)
  83.             _cairo_rtree_node_destroy (rtree, node->children[i]);
  84.     }
  85.  
  86.     _cairo_freepool_free (&rtree->node_freepool, node);
  87. }
  88.  
  89. void
  90. _cairo_rtree_node_collapse (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  91. {
  92.     int i;
  93.  
  94.     do {
  95.         assert (node->state == CAIRO_RTREE_NODE_DIVIDED);
  96.  
  97.         for (i = 0;  i < 4 && node->children[i] != NULL; i++)
  98.             if (node->children[i]->state != CAIRO_RTREE_NODE_AVAILABLE)
  99.                 return;
  100.  
  101.         for (i = 0; i < 4 && node->children[i] != NULL; i++)
  102.             _cairo_rtree_node_destroy (rtree, node->children[i]);
  103.  
  104.         node->children[0] = NULL;
  105.         node->state = CAIRO_RTREE_NODE_AVAILABLE;
  106.         cairo_list_move (&node->link, &rtree->available);
  107.     } while ((node = node->parent) != NULL);
  108. }
  109.  
  110. cairo_status_t
  111. _cairo_rtree_node_insert (cairo_rtree_t *rtree,
  112.                           cairo_rtree_node_t *node,
  113.                           int width,
  114.                           int height,
  115.                           cairo_rtree_node_t **out)
  116. {
  117.     int w, h, i;
  118.  
  119.     assert (node->state == CAIRO_RTREE_NODE_AVAILABLE);
  120.     assert (node->pinned == FALSE);
  121.  
  122.     if (node->width  - width  > rtree->min_size ||
  123.         node->height - height > rtree->min_size)
  124.     {
  125.         w = node->width  - width;
  126.         h = node->height - height;
  127.  
  128.         i = 0;
  129.         node->children[i] = _cairo_rtree_node_create (rtree, node,
  130.                                                       node->x, node->y,
  131.                                                       width, height);
  132.         if (unlikely (node->children[i] == NULL))
  133.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  134.         i++;
  135.  
  136.         if (w > rtree->min_size) {
  137.             node->children[i] = _cairo_rtree_node_create (rtree, node,
  138.                                                           node->x + width,
  139.                                                           node->y,
  140.                                                           w, height);
  141.             if (unlikely (node->children[i] == NULL))
  142.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  143.             i++;
  144.         }
  145.  
  146.         if (h > rtree->min_size) {
  147.             node->children[i] = _cairo_rtree_node_create (rtree, node,
  148.                                                           node->x,
  149.                                                           node->y + height,
  150.                                                           width, h);
  151.             if (unlikely (node->children[i] == NULL))
  152.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  153.             i++;
  154.  
  155.             if (w > rtree->min_size) {
  156.                 node->children[i] = _cairo_rtree_node_create (rtree, node,
  157.                                                               node->x + width,
  158.                                                               node->y + height,
  159.                                                               w, h);
  160.                 if (unlikely (node->children[i] == NULL))
  161.                     return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  162.                 i++;
  163.             }
  164.         }
  165.  
  166.         if (i < 4)
  167.             node->children[i] = NULL;
  168.  
  169.         node->state = CAIRO_RTREE_NODE_DIVIDED;
  170.         cairo_list_move (&node->link, &rtree->evictable);
  171.         node = node->children[0];
  172.     }
  173.  
  174.     node->state = CAIRO_RTREE_NODE_OCCUPIED;
  175.     cairo_list_move (&node->link, &rtree->evictable);
  176.     *out = node;
  177.  
  178.     return CAIRO_STATUS_SUCCESS;
  179. }
  180.  
  181. void
  182. _cairo_rtree_node_remove (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  183. {
  184.     assert (node->state == CAIRO_RTREE_NODE_OCCUPIED);
  185.     assert (node->pinned == FALSE);
  186.  
  187.     rtree->destroy (node);
  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_int_status_t ret = CAIRO_INT_STATUS_UNSUPPORTED;
  229.     cairo_rtree_node_t *node, *next;
  230.     cairo_list_t tmp_pinned;
  231.     int i, cnt;
  232.  
  233.     cairo_list_init (&tmp_pinned);
  234.  
  235.     /* propagate pinned from children to root */
  236.     cairo_list_foreach_entry_safe (node, next,
  237.                                    cairo_rtree_node_t, &rtree->pinned, link) {
  238.         node = node->parent;
  239.         while (node && ! node->pinned) {
  240.             node->pinned = 1;
  241.             cairo_list_move (&node->link, &tmp_pinned);
  242.             node = node->parent;
  243.         }
  244.     }
  245.  
  246.     cnt = 0;
  247.     cairo_list_foreach_entry (node, cairo_rtree_node_t,
  248.                               &rtree->evictable, link)
  249.     {
  250.         if (node->width >= width && node->height >= height)
  251.             cnt++;
  252.     }
  253.  
  254.     if (cnt == 0)
  255.         goto out;
  256.  
  257.     cnt = hars_petruska_f54_1_random () % cnt;
  258.     cairo_list_foreach_entry (node, cairo_rtree_node_t,
  259.                               &rtree->evictable, link)
  260.     {
  261.         if (node->width >= width && node->height >= height && cnt-- == 0) {
  262.             if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
  263.                 rtree->destroy (node);
  264.             } else {
  265.                 for (i = 0; i < 4 && node->children[i] != NULL; i++)
  266.                     _cairo_rtree_node_destroy (rtree, node->children[i]);
  267.                 node->children[0] = NULL;
  268.             }
  269.  
  270.             node->state = CAIRO_RTREE_NODE_AVAILABLE;
  271.             cairo_list_move (&node->link, &rtree->available);
  272.  
  273.             *out = node;
  274.             ret = CAIRO_STATUS_SUCCESS;
  275.             break;
  276.         }
  277.     }
  278.  
  279. out:
  280.     while (! cairo_list_is_empty (&tmp_pinned)) {
  281.         node = cairo_list_first_entry (&tmp_pinned, cairo_rtree_node_t, link);
  282.         node->pinned = 0;
  283.         cairo_list_move (&node->link, &rtree->evictable);
  284.     }
  285.     return ret;
  286. }
  287.  
  288. void
  289. _cairo_rtree_unpin (cairo_rtree_t *rtree)
  290. {
  291.     while (! cairo_list_is_empty (&rtree->pinned)) {
  292.         cairo_rtree_node_t *node = cairo_list_first_entry (&rtree->pinned,
  293.                                                            cairo_rtree_node_t,
  294.                                                            link);
  295.         node->pinned = 0;
  296.         cairo_list_move (&node->link, &rtree->evictable);
  297.     }
  298. }
  299.  
  300. void
  301. _cairo_rtree_init (cairo_rtree_t        *rtree,
  302.                    int                   width,
  303.                    int                   height,
  304.                    int                   min_size,
  305.                    int                   node_size,
  306.                    void (*destroy) (cairo_rtree_node_t *))
  307. {
  308.     assert (node_size >= (int) sizeof (cairo_rtree_node_t));
  309.     _cairo_freepool_init (&rtree->node_freepool, node_size);
  310.  
  311.     cairo_list_init (&rtree->available);
  312.     cairo_list_init (&rtree->pinned);
  313.     cairo_list_init (&rtree->evictable);
  314.  
  315.     rtree->min_size = min_size;
  316.     rtree->destroy = destroy;
  317.  
  318.     memset (&rtree->root, 0, sizeof (rtree->root));
  319.     rtree->root.width = width;
  320.     rtree->root.height = height;
  321.     rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
  322.     cairo_list_add (&rtree->root.link, &rtree->available);
  323. }
  324.  
  325. void
  326. _cairo_rtree_reset (cairo_rtree_t *rtree)
  327. {
  328.     int i;
  329.  
  330.     if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
  331.         rtree->destroy (&rtree->root);
  332.     } else {
  333.         for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
  334.             _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
  335.         rtree->root.children[0] = NULL;
  336.     }
  337.  
  338.     cairo_list_init (&rtree->available);
  339.     cairo_list_init (&rtree->evictable);
  340.     cairo_list_init (&rtree->pinned);
  341.  
  342.     rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
  343.     rtree->root.pinned = FALSE;
  344.     cairo_list_add (&rtree->root.link, &rtree->available);
  345. }
  346.  
  347. static void
  348. _cairo_rtree_node_foreach (cairo_rtree_node_t *node,
  349.                            void (*func)(cairo_rtree_node_t *, void *data),
  350.                            void *data)
  351. {
  352.     int i;
  353.  
  354.     for (i = 0; i < 4 && node->children[i] != NULL; i++)
  355.         _cairo_rtree_node_foreach(node->children[i], func, data);
  356.  
  357.     func(node, data);
  358. }
  359.  
  360. void
  361. _cairo_rtree_foreach (cairo_rtree_t *rtree,
  362.                       void (*func)(cairo_rtree_node_t *, void *data),
  363.                       void *data)
  364. {
  365.     int i;
  366.  
  367.     if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
  368.         func(&rtree->root, data);
  369.     } else {
  370.         for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
  371.             _cairo_rtree_node_foreach (rtree->root.children[i], func, data);
  372.     }
  373. }
  374.  
  375. void
  376. _cairo_rtree_fini (cairo_rtree_t *rtree)
  377. {
  378.     int i;
  379.  
  380.     if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
  381.         rtree->destroy (&rtree->root);
  382.     } else {
  383.         for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
  384.             _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
  385.     }
  386.  
  387.     _cairo_freepool_fini (&rtree->node_freepool);
  388. }
  389.