pintos-os.org Git - pspp/blob - src/libpspp/range-set.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* Bitmap, implemented as a balanced binary tree.
  18
  19    Each operation has O(lg N) cost, where N is the number of
  20    contiguous regions of 1-bits in the bitmap.  Also, a cache
  21    reduces the second and subsequent containment tests within a
  22    single contiguous region to O(1). */
  23
  24 #ifndef LIBPSPP_RANGE_SET_H
  25 #define LIBPSPP_RANGE_SET_H
  26
  27 #include <stdbool.h>
  28 #include "libpspp/bt.h"
  29 #include "libpspp/cast.h"
  30
  31 /* A set of ranges. */
  32 struct range_set
  33   {
  34     struct pool *pool;                  /* Pool for freeing range_set. */
  35     struct bt bt;                       /* Tree of range_set_nodes. */
  36
  37     /* Cache. */
  38     unsigned long int cache_start;      /* Start of region. */
  39     unsigned long int cache_end;        /* One past end of region. */
  40     bool cache_value;                   /* Is the region in the set? */
  41   };
  42
  43 /* A node in the range set. */
  44 struct range_set_node
  45   {
  46     struct bt_node bt_node;             /* Binary tree node. */
  47     unsigned long int start;            /* Start of region. */
  48     unsigned long int end;              /* One past end of region. */
  49   };
  50
  51 struct range_set *range_set_create (void);
  52 struct range_set *range_set_create_pool (struct pool *);
  53 struct range_set *range_set_clone (const struct range_set *, struct pool *);
  54 void range_set_destroy (struct range_set *);
  55
  56 void range_set_set1 (struct range_set *,
  57                      unsigned long int start, unsigned long int width);
  58 void range_set_set0 (struct range_set *,
  59                      unsigned long int start, unsigned long int width);
  60 bool range_set_allocate (struct range_set *, unsigned long int request,
  61                          unsigned long int *start, unsigned long int *width);
  62 bool range_set_allocate_fully (struct range_set *, unsigned long int request,
  63                                unsigned long int *start);
  64 bool range_set_contains (const struct range_set *, unsigned long int position);
  65 unsigned long int range_set_scan (const struct range_set *,
  66                                   unsigned long int start);
  67
  68 static inline bool range_set_is_empty (const struct range_set *);
  69
  70 #define RANGE_SET_FOR_EACH(NODE, RANGE_SET)             \
  71         for ((NODE) = range_set_first (RANGE_SET);      \
  72              (NODE) != NULL;                            \
  73              (NODE) = range_set_next (RANGE_SET, NODE))
  74
  75 static inline const struct range_set_node *range_set_first (
  76   const struct range_set *);
  77 static inline const struct range_set_node *range_set_next (
  78   const struct range_set *, const struct range_set_node *);
  79 static inline const struct range_set_node *range_set_last (
  80   const struct range_set *);
  81 static inline const struct range_set_node *range_set_prev (
  82   const struct range_set *, const struct range_set_node *);
  83 static inline unsigned long int range_set_node_get_start (
  84   const struct range_set_node *);
  85 static inline unsigned long int range_set_node_get_end (
  86   const struct range_set_node *);
  87 static inline unsigned long int range_set_node_get_width (
  88   const struct range_set_node *);
  89 \f
  90 /* Inline functions. */
  91
  92 static inline struct range_set_node *range_set_node_from_bt__ (
  93   const struct bt_node *);
  94 static inline struct range_set_node *range_set_next__ (
  95   const struct range_set *, const struct range_set_node *);
  96 static inline struct range_set_node *range_set_first__ (
  97   const struct range_set *);
  98 static inline struct range_set_node *range_set_prev__ (
  99   const struct range_set *, const struct range_set_node *);
 100 static inline struct range_set_node *range_set_last__ (
 101   const struct range_set *);
 102
 103 /* Returns true if RS contains no 1-bits, false otherwise. */
 104 static inline bool
 105 range_set_is_empty (const struct range_set *rs)
 106 {
 107   return bt_count (&rs->bt) == 0;
 108 }
 109
 110 /* Returns the node representing the first contiguous region of
 111    1-bits in RS, or a null pointer if RS is empty.
 112    Any call to range_set_set1, range_set_set0, or
 113    range_set_allocate invalidates the returned node. */
 114 static inline const struct range_set_node *
 115 range_set_first (const struct range_set *rs)
 116 {
 117   return range_set_first__ (rs);
 118 }
 119
 120 /* If NODE is nonnull, returns the node representing the next
 121    contiguous region of 1-bits in RS following NODE, or a null
 122    pointer if NODE is the last region in RS.
 123    If NODE is null, returns the first region in RS, as for
 124    range_set_first.
 125    Any call to range_set_set1, range_set_set0, or
 126    range_set_allocate invalidates the returned node. */
 127 static inline const struct range_set_node *
 128 range_set_next (const struct range_set *rs, const struct range_set_node *node)
 129 {
 130   return (node != NULL
 131           ? range_set_next__ (rs, CONST_CAST (struct range_set_node *, node))
 132           : range_set_first__ (rs));
 133 }
 134
 135 /* Returns the node representing the last contiguous region of
 136    1-bits in RS, or a null pointer if RS is empty.
 137    Any call to range_set_set1, range_set_set0, or
 138    range_set_allocate invalidates the returned node. */
 139 static inline const struct range_set_node *
 140 range_set_last (const struct range_set *rs)
 141 {
 142   return range_set_last__ (rs);
 143 }
 144
 145 /* If NODE is nonnull, returns the node representing the previous
 146    contiguous region of 1-bits in RS following NODE, or a null
 147    pointer if NODE is the first region in RS.
 148    If NODE is null, returns the last region in RS, as for
 149    range_set_last.
 150    Any call to range_set_set1, range_set_set0, or
 151    range_set_allocate invalidates the returned node. */
 152 static inline const struct range_set_node *
 153 range_set_prev (const struct range_set *rs, const struct range_set_node *node)
 154 {
 155   return (node != NULL
 156           ? range_set_prev__ (rs, CONST_CAST (struct range_set_node *, node))
 157           : range_set_last__ (rs));
 158 }
 159
 160 /* Returns the position of the first 1-bit in NODE. */
 161 static inline unsigned long int
 162 range_set_node_get_start (const struct range_set_node *node)
 163 {
 164   return node->start;
 165 }
 166
 167 /* Returns one past the position of the last 1-bit in NODE. */
 168 static inline unsigned long int
 169 range_set_node_get_end (const struct range_set_node *node)
 170 {
 171   return node->end;
 172 }
 173
 174 /* Returns the number of contiguous 1-bits in NODE. */
 175 static inline unsigned long int
 176 range_set_node_get_width (const struct range_set_node *node)
 177 {
 178   return node->end - node->start;
 179 }
 180 \f
 181 /* Internal helper functions. */
 182
 183 /* Returns the range_set_node corresponding to the given
 184    BT_NODE.  Returns a null pointer if BT_NODE is null. */
 185 static inline struct range_set_node *
 186 range_set_node_from_bt__ (const struct bt_node *bt_node)
 187 {
 188   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
 189 }
 190
 191 /* Returns the next range_set_node in RS after NODE,
 192    or a null pointer if NODE is the last node in RS. */
 193 static inline struct range_set_node *
 194 range_set_next__ (const struct range_set *rs,
 195                   const struct range_set_node *node)
 196 {
 197   return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
 198 }
 199
 200 /* Returns the first range_set_node in RS,
 201    or a null pointer if RS is empty. */
 202 static inline struct range_set_node *
 203 range_set_first__ (const struct range_set *rs)
 204 {
 205   return range_set_node_from_bt__ (bt_first (&rs->bt));
 206 }
 207
 208 /* Returns the previous range_set_node in RS after NODE,
 209    or a null pointer if NODE is the first node in RS. */
 210 static inline struct range_set_node *
 211 range_set_prev__ (const struct range_set *rs,
 212                   const struct range_set_node *node)
 213 {
 214   return range_set_node_from_bt__ (bt_prev (&rs->bt, &node->bt_node));
 215 }
 216
 217 /* Returns the last range_set_node in RS,
 218    or a null pointer if RS is empty. */
 219 static inline struct range_set_node *
 220 range_set_last__ (const struct range_set *rs)
 221 {
 222   return range_set_node_from_bt__ (bt_last (&rs->bt));
 223 }
 224
 225 #endif /* libpspp/range-set.h */