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); |
} |