diff options
Diffstat (limited to 'gfx/cairo/cairo/src/cairo-rtree.c')
-rw-r--r-- | gfx/cairo/cairo/src/cairo-rtree.c | 388 |
1 files changed, 388 insertions, 0 deletions
diff --git a/gfx/cairo/cairo/src/cairo-rtree.c b/gfx/cairo/cairo/src/cairo-rtree.c new file mode 100644 index 0000000000..dbc040929a --- /dev/null +++ b/gfx/cairo/cairo/src/cairo-rtree.c @@ -0,0 +1,388 @@ +/* cairo - a vector graphics library with display and print output + * + * Copyright © 2009 Chris Wilson + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + * + * The Original Code is the cairo graphics library. + * + * The Initial Developer of the Original Code is Chris Wilson. + * + * Contributor(s): + * Chris Wilson <chris@chris-wilson.co.uk> + * + */ + +#include "cairoint.h" + +#include "cairo-error-private.h" +#include "cairo-rtree-private.h" + +cairo_rtree_node_t * +_cairo_rtree_node_create (cairo_rtree_t *rtree, + cairo_rtree_node_t *parent, + int x, + int y, + int width, + int height) +{ + cairo_rtree_node_t *node; + + node = _cairo_freepool_alloc (&rtree->node_freepool); + if (node == NULL) { + _cairo_error_throw (CAIRO_STATUS_NO_MEMORY); + return NULL; + } + + node->children[0] = NULL; + node->parent = parent; + node->state = CAIRO_RTREE_NODE_AVAILABLE; + node->pinned = FALSE; + node->x = x; + node->y = y; + node->width = width; + node->height = height; + + cairo_list_add (&node->link, &rtree->available); + + return node; +} + +void +_cairo_rtree_node_destroy (cairo_rtree_t *rtree, cairo_rtree_node_t *node) +{ + int i; + + cairo_list_del (&node->link); + + if (node->state == CAIRO_RTREE_NODE_OCCUPIED) { + rtree->destroy (node); + } else { + for (i = 0; i < 4 && node->children[i] != NULL; i++) + _cairo_rtree_node_destroy (rtree, node->children[i]); + } + + _cairo_freepool_free (&rtree->node_freepool, node); +} + +void +_cairo_rtree_node_collapse (cairo_rtree_t *rtree, cairo_rtree_node_t *node) +{ + int i; + + do { + assert (node->state == CAIRO_RTREE_NODE_DIVIDED); + + for (i = 0; i < 4 && node->children[i] != NULL; i++) + if (node->children[i]->state != CAIRO_RTREE_NODE_AVAILABLE) + return; + + for (i = 0; i < 4 && node->children[i] != NULL; i++) + _cairo_rtree_node_destroy (rtree, node->children[i]); + + node->children[0] = NULL; + node->state = CAIRO_RTREE_NODE_AVAILABLE; + cairo_list_move (&node->link, &rtree->available); + } while ((node = node->parent) != NULL); +} + +cairo_status_t +_cairo_rtree_node_insert (cairo_rtree_t *rtree, + cairo_rtree_node_t *node, + int width, + int height, + cairo_rtree_node_t **out) +{ + int w, h, i; + + assert (node->state == CAIRO_RTREE_NODE_AVAILABLE); + assert (node->pinned == FALSE); + + if (node->width - width > rtree->min_size || + node->height - height > rtree->min_size) + { + w = node->width - width; + h = node->height - height; + + i = 0; + node->children[i] = _cairo_rtree_node_create (rtree, node, + node->x, node->y, + width, height); + if (unlikely (node->children[i] == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + i++; + + if (w > rtree->min_size) { + node->children[i] = _cairo_rtree_node_create (rtree, node, + node->x + width, + node->y, + w, height); + if (unlikely (node->children[i] == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + i++; + } + + if (h > rtree->min_size) { + node->children[i] = _cairo_rtree_node_create (rtree, node, + node->x, + node->y + height, + width, h); + if (unlikely (node->children[i] == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + i++; + + if (w > rtree->min_size) { + node->children[i] = _cairo_rtree_node_create (rtree, node, + node->x + width, + node->y + height, + w, h); + if (unlikely (node->children[i] == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + i++; + } + } + + if (i < 4) + node->children[i] = NULL; + + node->state = CAIRO_RTREE_NODE_DIVIDED; + cairo_list_move (&node->link, &rtree->evictable); + node = node->children[0]; + } + + node->state = CAIRO_RTREE_NODE_OCCUPIED; + cairo_list_move (&node->link, &rtree->evictable); + *out = node; + + return CAIRO_STATUS_SUCCESS; +} + +void +_cairo_rtree_node_remove (cairo_rtree_t *rtree, cairo_rtree_node_t *node) +{ + assert (node->state == CAIRO_RTREE_NODE_OCCUPIED); + assert (node->pinned == FALSE); + + rtree->destroy (node); + + node->state = CAIRO_RTREE_NODE_AVAILABLE; + cairo_list_move (&node->link, &rtree->available); + + _cairo_rtree_node_collapse (rtree, node->parent); +} + +cairo_int_status_t +_cairo_rtree_insert (cairo_rtree_t *rtree, + int width, + int height, + cairo_rtree_node_t **out) +{ + cairo_rtree_node_t *node; + + cairo_list_foreach_entry (node, cairo_rtree_node_t, + &rtree->available, link) + { + if (node->width >= width && node->height >= height) + return _cairo_rtree_node_insert (rtree, node, width, height, out); + } + + return CAIRO_INT_STATUS_UNSUPPORTED; +} + +static uint32_t +hars_petruska_f54_1_random (void) +{ +#define rol(x,k) ((x << k) | (x >> (32-k))) + static uint32_t x; + return x = (x ^ rol (x, 5) ^ rol (x, 24)) + 0x37798849; +#undef rol +} + +cairo_int_status_t +_cairo_rtree_evict_random (cairo_rtree_t *rtree, + int width, + int height, + cairo_rtree_node_t **out) +{ + cairo_int_status_t ret = CAIRO_INT_STATUS_UNSUPPORTED; + cairo_rtree_node_t *node, *next; + cairo_list_t tmp_pinned; + int i, cnt; + + cairo_list_init (&tmp_pinned); + + /* propagate pinned from children to root */ + cairo_list_foreach_entry_safe (node, next, + cairo_rtree_node_t, &rtree->pinned, link) { + node = node->parent; + while (node && ! node->pinned) { + node->pinned = 1; + cairo_list_move (&node->link, &tmp_pinned); + node = node->parent; + } + } + + cnt = 0; + cairo_list_foreach_entry (node, cairo_rtree_node_t, + &rtree->evictable, link) + { + if (node->width >= width && node->height >= height) + cnt++; + } + + if (cnt == 0) + goto out; + + cnt = hars_petruska_f54_1_random () % cnt; + cairo_list_foreach_entry (node, cairo_rtree_node_t, + &rtree->evictable, link) + { + if (node->width >= width && node->height >= height && cnt-- == 0) { + if (node->state == CAIRO_RTREE_NODE_OCCUPIED) { + rtree->destroy (node); + } else { + for (i = 0; i < 4 && node->children[i] != NULL; i++) + _cairo_rtree_node_destroy (rtree, node->children[i]); + node->children[0] = NULL; + } + + node->state = CAIRO_RTREE_NODE_AVAILABLE; + cairo_list_move (&node->link, &rtree->available); + + *out = node; + ret = CAIRO_STATUS_SUCCESS; + break; + } + } + +out: + while (! cairo_list_is_empty (&tmp_pinned)) { + node = cairo_list_first_entry (&tmp_pinned, cairo_rtree_node_t, link); + node->pinned = 0; + cairo_list_move (&node->link, &rtree->evictable); + } + return ret; +} + +void +_cairo_rtree_unpin (cairo_rtree_t *rtree) +{ + while (! cairo_list_is_empty (&rtree->pinned)) { + cairo_rtree_node_t *node = cairo_list_first_entry (&rtree->pinned, + cairo_rtree_node_t, + link); + node->pinned = 0; + cairo_list_move (&node->link, &rtree->evictable); + } +} + +void +_cairo_rtree_init (cairo_rtree_t *rtree, + int width, + int height, + int min_size, + int node_size, + void (*destroy) (cairo_rtree_node_t *)) +{ + assert (node_size >= (int) sizeof (cairo_rtree_node_t)); + _cairo_freepool_init (&rtree->node_freepool, node_size); + + cairo_list_init (&rtree->available); + cairo_list_init (&rtree->pinned); + cairo_list_init (&rtree->evictable); + + rtree->min_size = min_size; + rtree->destroy = destroy; + + memset (&rtree->root, 0, sizeof (rtree->root)); + rtree->root.width = width; + rtree->root.height = height; + rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE; + cairo_list_add (&rtree->root.link, &rtree->available); +} + +void +_cairo_rtree_reset (cairo_rtree_t *rtree) +{ + int i; + + if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) { + rtree->destroy (&rtree->root); + } else { + for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++) + _cairo_rtree_node_destroy (rtree, rtree->root.children[i]); + rtree->root.children[0] = NULL; + } + + cairo_list_init (&rtree->available); + cairo_list_init (&rtree->evictable); + cairo_list_init (&rtree->pinned); + + rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE; + rtree->root.pinned = FALSE; + cairo_list_add (&rtree->root.link, &rtree->available); +} + +static void +_cairo_rtree_node_foreach (cairo_rtree_node_t *node, + void (*func)(cairo_rtree_node_t *, void *data), + void *data) +{ + int i; + + for (i = 0; i < 4 && node->children[i] != NULL; i++) + _cairo_rtree_node_foreach(node->children[i], func, data); + + func(node, data); +} + +void +_cairo_rtree_foreach (cairo_rtree_t *rtree, + void (*func)(cairo_rtree_node_t *, void *data), + void *data) +{ + int i; + + if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) { + func(&rtree->root, data); + } else { + for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++) + _cairo_rtree_node_foreach (rtree->root.children[i], func, data); + } +} + +void +_cairo_rtree_fini (cairo_rtree_t *rtree) +{ + int i; + + if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) { + rtree->destroy (&rtree->root); + } else { + for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++) + _cairo_rtree_node_destroy (rtree, rtree->root.children[i]); + } + + _cairo_freepool_fini (&rtree->node_freepool); +} |