Quelle  cairo-rtree.c

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