src/cairo-rtree.c

   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 }