src/cairo-rtree-private.h

   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-private.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     void **owner;
  56     cairo_list_t link;
  57     uint16_t pinned;
  58     uint16_t state;
  59     uint16_t x, y;
  60     uint16_t width, height;
  61 } cairo_rtree_node_t;
  62
  63 typedef struct _cairo_rtree {
  64     cairo_rtree_node_t root;
  65     int min_size;
  66     cairo_list_t pinned;
  67     cairo_list_t available;
  68     cairo_list_t evictable;
  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
 103 cairo_private cairo_int_status_t
 104 _cairo_rtree_insert (cairo_rtree_t           *rtree,
 105                      int                      width,
 106                      int                      height,
 107                      cairo_rtree_node_t     **out);
 108
 109 cairo_private cairo_int_status_t
 110 _cairo_rtree_evict_random (cairo_rtree_t         *rtree,
 111                            int                    width,
 112                            int                    height,
 113                            cairo_rtree_node_t   **out);
 114
 115 static inline void *
 116 _cairo_rtree_pin (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
 117 {
 118     if (! node->pinned) {
 119         cairo_list_move (&node->link, &rtree->pinned);
 120         node->pinned = 1;
 121     }
 122
 123     return node;
 124 }
 125
 126 cairo_private void
 127 _cairo_rtree_unpin (cairo_rtree_t *rtree);
 128
 129 cairo_private void
 130 _cairo_rtree_reset (cairo_rtree_t *rtree);
 131
 132 cairo_private void
 133 _cairo_rtree_fini (cairo_rtree_t *rtree);
 134
 135 #endif /* CAIRO_RTREE_PRIVATE_H */