src/libpspp/range-set.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 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
  30 /* A set of ranges. */
  31 struct range_set
  32   {
  33     struct pool *pool;                  /* Pool for freeing range_set. */
  34     struct bt bt;                       /* Tree of range_set_nodes. */
  35
  36     /* Cache. */
  37     unsigned long int cache_start;      /* Start of region. */
  38     unsigned long int cache_end;        /* One past end of region. */
  39     bool cache_value;                   /* Is the region in the set? */
  40   };
  41
  42 /* A node in the range set. */
  43 struct range_set_node
  44   {
  45     struct bt_node bt_node;             /* Binary tree node. */
  46     unsigned long int start;            /* Start of region. */
  47     unsigned long int end;              /* One past end of region. */
  48   };
  49
  50 struct range_set *range_set_create (void);
  51 struct range_set *range_set_create_pool (struct pool *);
  52 struct range_set *range_set_clone (const struct range_set *, struct pool *);
  53 void range_set_destroy (struct range_set *);
  54
  55 void range_set_insert (struct range_set *,
  56                        unsigned long int start, unsigned long int width);
  57 void range_set_delete (struct range_set *,
  58                        unsigned long int start, unsigned long int width);
  59 bool range_set_allocate (struct range_set *, unsigned long int request,
  60                          unsigned long int *start, unsigned long int *width);
  61 bool range_set_allocate_fully (struct range_set *, unsigned long int request,
  62                                unsigned long int *start);
  63 bool range_set_contains (const struct range_set *, unsigned long int position);
  64 unsigned long int range_set_scan (const struct range_set *,
  65                                   unsigned long int start);
  66
  67 static inline bool range_set_is_empty (const struct range_set *);
  68
  69 static inline const struct range_set_node *range_set_first (
  70   const struct range_set *);
  71 static inline const struct range_set_node *range_set_next (
  72   const struct range_set *, const struct range_set_node *);
  73 static inline const struct range_set_node *range_set_last (
  74   const struct range_set *);
  75 static inline const struct range_set_node *range_set_prev (
  76   const struct range_set *, const struct range_set_node *);
  77 static inline unsigned long int range_set_node_get_start (
  78   const struct range_set_node *);
  79 static inline unsigned long int range_set_node_get_end (
  80   const struct range_set_node *);
  81 static inline unsigned long int range_set_node_get_width (
  82   const struct range_set_node *);
  83 \f
  84 /* Inline functions. */
  85
  86 static inline struct range_set_node *range_set_node_from_bt__ (
  87   const struct bt_node *);
  88 static inline struct range_set_node *range_set_next__ (
  89   const struct range_set *, const struct range_set_node *);
  90 static inline struct range_set_node *range_set_first__ (
  91   const struct range_set *);
  92 static inline struct range_set_node *range_set_prev__ (
  93   const struct range_set *, const struct range_set_node *);
  94 static inline struct range_set_node *range_set_last__ (
  95   const struct range_set *);
  96
  97 /* Returns true if RS contains no 1-bits, false otherwise. */
  98 static inline bool
  99 range_set_is_empty (const struct range_set *rs)
 100 {
 101   return bt_count (&rs->bt) == 0;
 102 }
 103
 104 /* Returns the node representing the first contiguous region of
 105    1-bits in RS, or a null pointer if RS is empty.
 106    Any call to range_set_insert, range_set_delete, or
 107    range_set_allocate invalidates the returned node. */
 108 static inline const struct range_set_node *
 109 range_set_first (const struct range_set *rs)
 110 {
 111   return range_set_first__ (rs);
 112 }
 113
 114 /* If NODE is nonnull, returns the node representing the next
 115    contiguous region of 1-bits in RS following NODE, or a null
 116    pointer if NODE is the last region in RS.
 117    If NODE is null, returns the first region in RS, as for
 118    range_set_first.
 119    Any call to range_set_insert, range_set_delete, or
 120    range_set_allocate invalidates the returned node. */
 121 static inline const struct range_set_node *
 122 range_set_next (const struct range_set *rs, const struct range_set_node *node)
 123 {
 124   return (node != NULL
 125           ? range_set_next__ (rs, (struct range_set_node *) node)
 126           : range_set_first__ (rs));
 127 }
 128
 129 /* Returns the node representing the last contiguous region of
 130    1-bits in RS, or a null pointer if RS is empty.
 131    Any call to range_set_insert, range_set_delete, or
 132    range_set_allocate invalidates the returned node. */
 133 static inline const struct range_set_node *
 134 range_set_last (const struct range_set *rs)
 135 {
 136   return range_set_last__ (rs);
 137 }
 138
 139 /* If NODE is nonnull, returns the node representing the previous
 140    contiguous region of 1-bits in RS following NODE, or a null
 141    pointer if NODE is the first region in RS.
 142    If NODE is null, returns the last region in RS, as for
 143    range_set_last.
 144    Any call to range_set_insert, range_set_delete, or
 145    range_set_allocate invalidates the returned node. */
 146 static inline const struct range_set_node *
 147 range_set_prev (const struct range_set *rs, const struct range_set_node *node)
 148 {
 149   return (node != NULL
 150           ? range_set_prev__ (rs, (struct range_set_node *) node)
 151           : range_set_last__ (rs));
 152 }
 153
 154 /* Returns the position of the first 1-bit in NODE. */
 155 static inline unsigned long int
 156 range_set_node_get_start (const struct range_set_node *node)
 157 {
 158   return node->start;
 159 }
 160
 161 /* Returns one past the position of the last 1-bit in NODE. */
 162 static inline unsigned long int
 163 range_set_node_get_end (const struct range_set_node *node)
 164 {
 165   return node->end;
 166 }
 167
 168 /* Returns the number of contiguous 1-bits in NODE. */
 169 static inline unsigned long int
 170 range_set_node_get_width (const struct range_set_node *node)
 171 {
 172   return node->end - node->start;
 173 }
 174 \f
 175 /* Internal helper functions. */
 176
 177 /* Returns the range_set_node corresponding to the given
 178    BT_NODE.  Returns a null pointer if BT_NODE is null. */
 179 static inline struct range_set_node *
 180 range_set_node_from_bt__ (const struct bt_node *bt_node)
 181 {
 182   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
 183 }
 184
 185 /* Returns the next range_set_node in RS after NODE,
 186    or a null pointer if NODE is the last node in RS. */
 187 static inline struct range_set_node *
 188 range_set_next__ (const struct range_set *rs,
 189                   const struct range_set_node *node)
 190 {
 191   return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
 192 }
 193
 194 /* Returns the first range_set_node in RS,
 195    or a null pointer if RS is empty. */
 196 static inline struct range_set_node *
 197 range_set_first__ (const struct range_set *rs)
 198 {
 199   return range_set_node_from_bt__ (bt_first (&rs->bt));
 200 }
 201
 202 /* Returns the previous range_set_node in RS after NODE,
 203    or a null pointer if NODE is the first node in RS. */
 204 static inline struct range_set_node *
 205 range_set_prev__ (const struct range_set *rs,
 206                   const struct range_set_node *node)
 207 {
 208   return range_set_node_from_bt__ (bt_prev (&rs->bt, &node->bt_node));
 209 }
 210
 211 /* Returns the last range_set_node in RS,
 212    or a null pointer if RS is empty. */
 213 static inline struct range_set_node *
 214 range_set_last__ (const struct range_set *rs)
 215 {
 216   return range_set_node_from_bt__ (bt_last (&rs->bt));
 217 }
 218
 219 #endif /* libpspp/range-set.h */