Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | 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. #ifndef CAIRO_RTREE_PRIVATE_H
  38. #define CAIRO_RTREE_PRIVATE_H
  39.  
  40. #include "cairo-compiler-private.h"
  41. #include "cairo-error-private.h"
  42. #include "cairo-types-private.h"
  43.  
  44. #include "cairo-freelist-private.h"
  45. #include "cairo-list-inline.h"
  46.  
  47. enum {
  48.     CAIRO_RTREE_NODE_AVAILABLE,
  49.     CAIRO_RTREE_NODE_DIVIDED,
  50.     CAIRO_RTREE_NODE_OCCUPIED,
  51. };
  52.  
  53. typedef struct _cairo_rtree_node {
  54.     struct _cairo_rtree_node *children[4], *parent;
  55.     cairo_list_t link;
  56.     uint16_t pinned;
  57.     uint16_t state;
  58.     uint16_t x, y;
  59.     uint16_t width, height;
  60. } cairo_rtree_node_t;
  61.  
  62. typedef struct _cairo_rtree {
  63.     cairo_rtree_node_t root;
  64.     int min_size;
  65.     cairo_list_t pinned;
  66.     cairo_list_t available;
  67.     cairo_list_t evictable;
  68.     void (*destroy) (cairo_rtree_node_t *);
  69.     cairo_freepool_t node_freepool;
  70. } cairo_rtree_t;
  71.  
  72. cairo_private cairo_rtree_node_t *
  73. _cairo_rtree_node_create (cairo_rtree_t          *rtree,
  74.                           cairo_rtree_node_t     *parent,
  75.                           int                     x,
  76.                           int                     y,
  77.                           int                     width,
  78.                           int                     height);
  79.  
  80. cairo_private cairo_status_t
  81. _cairo_rtree_node_insert (cairo_rtree_t *rtree,
  82.                           cairo_rtree_node_t *node,
  83.                           int width,
  84.                           int height,
  85.                           cairo_rtree_node_t **out);
  86.  
  87. cairo_private void
  88. _cairo_rtree_node_collapse (cairo_rtree_t *rtree, cairo_rtree_node_t *node);
  89.  
  90. cairo_private void
  91. _cairo_rtree_node_remove (cairo_rtree_t *rtree, cairo_rtree_node_t *node);
  92.  
  93. cairo_private void
  94. _cairo_rtree_node_destroy (cairo_rtree_t *rtree, cairo_rtree_node_t *node);
  95.  
  96. cairo_private void
  97. _cairo_rtree_init (cairo_rtree_t        *rtree,
  98.                    int                   width,
  99.                    int                   height,
  100.                    int                   min_size,
  101.                    int                   node_size,
  102.                    void (*destroy)(cairo_rtree_node_t *));
  103.  
  104. cairo_private cairo_int_status_t
  105. _cairo_rtree_insert (cairo_rtree_t           *rtree,
  106.                      int                      width,
  107.                      int                      height,
  108.                      cairo_rtree_node_t     **out);
  109.  
  110. cairo_private cairo_int_status_t
  111. _cairo_rtree_evict_random (cairo_rtree_t         *rtree,
  112.                            int                    width,
  113.                            int                    height,
  114.                            cairo_rtree_node_t   **out);
  115.  
  116. cairo_private void
  117. _cairo_rtree_foreach (cairo_rtree_t *rtree,
  118.                       void (*func)(cairo_rtree_node_t *, void *data),
  119.                       void *data);
  120.  
  121. static inline void *
  122. _cairo_rtree_pin (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
  123. {
  124.     assert (node->state == CAIRO_RTREE_NODE_OCCUPIED);
  125.     if (! node->pinned) {
  126.         cairo_list_move (&node->link, &rtree->pinned);
  127.         node->pinned = 1;
  128.     }
  129.  
  130.     return node;
  131. }
  132.  
  133. cairo_private void
  134. _cairo_rtree_unpin (cairo_rtree_t *rtree);
  135.  
  136. cairo_private void
  137. _cairo_rtree_reset (cairo_rtree_t *rtree);
  138.  
  139. cairo_private void
  140. _cairo_rtree_fini (cairo_rtree_t *rtree);
  141.  
  142. #endif /* CAIRO_RTREE_PRIVATE_H */
  143.