pintos-os.org Git - pspp/blob - src/libpspp/range-tower.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 an augmented binary tree.
  18
  19    Beyond the usual features of a bitmap, a range tower can efficiently
  20    implement a "splice" operation that shifts ranges of bits left or right.
  21    This feature does cost memory and time, so use a range tower only if this
  22    feature is actually needed.  Otherwise, use a range set (see range-set.h),
  23    which can do everything that a range tower can do except the "splice"
  24    operation.
  25
  26    Each operation has O(lg N) cost, where N is the number of contiguous regions
  27    of 1-bits in the bitmap.  Also, a cache reduces the second and subsequent
  28    containment tests within a single contiguous region to O(1).  */
  29
  30 #ifndef LIBPSPP_RANGE_TOWER_H
  31 #define LIBPSPP_RANGE_TOWER_H
  32
  33 #include <limits.h>
  34 #include <stdbool.h>
  35 #include "libpspp/abt.h"
  36 #include "libpspp/cast.h"
  37
  38 /* A tower of ranges. */
  39 struct range_tower
  40   {
  41     struct pool *pool;          /* Pool for freeing range_tower. */
  42     struct abt abt;             /* Tree of range_tower_nodes. */
  43
  44     /* Cache. */
  45     unsigned long int cache_start; /* Start of region. */
  46     unsigned long int cache_end;   /* One past end of region. */
  47     bool cache_value;              /* Is the region in the tower? */
  48   };
  49
  50 /* A node in the range tower. */
  51 struct range_tower_node
  52   {
  53     struct abt_node abt_node;        /* Augmented binary tree node. */
  54     unsigned long int n_zeros;       /* Number of leading zeros. */
  55     unsigned long int n_ones;        /* Number of ones following the zeros. */
  56     unsigned long int subtree_width; /* n_zeros + n_ones + sum of descendants. */
  57   };
  58
  59 struct range_tower *range_tower_create (void);
  60 struct range_tower *range_tower_create_pool (struct pool *);
  61 struct range_tower *range_tower_clone (const struct range_tower *,
  62                                        struct pool *);
  63 void range_tower_destroy (struct range_tower *);
  64
  65 void range_tower_splice (struct range_tower *,
  66                          unsigned long int start,
  67                          unsigned long int old_width,
  68                          unsigned long int new_width);
  69
  70 void range_tower_set1 (struct range_tower *,
  71                        unsigned long int start, unsigned long int width);
  72 void range_tower_set0 (struct range_tower *,
  73                        unsigned long int start, unsigned long int width);
  74
  75 void range_tower_insert1 (struct range_tower *,
  76                           unsigned long int start, unsigned long int width);
  77 void range_tower_insert0 (struct range_tower *,
  78                           unsigned long int start, unsigned long int width);
  79
  80 void range_tower_delete (struct range_tower *,
  81                          unsigned long int start, unsigned long int width);
  82
  83 void range_tower_move (struct range_tower *,
  84                        unsigned long int old_start,
  85                        unsigned long int new_start,
  86                        unsigned long int width);
  87
  88 bool range_tower_contains (const struct range_tower *,
  89                            unsigned long int position);
  90 unsigned long int range_tower_scan (const struct range_tower *,
  91                                     unsigned long int start);
  92
  93 static inline bool range_tower_is_empty (const struct range_tower *);
  94
  95 #define RANGE_TOWER_FOR_EACH(NODE, START, RANGE_TOWER)                  \
  96         for ((NODE) = range_tower_first (RANGE_TOWER), (START) = 0;     \
  97              (NODE) && ((START) += (NODE)->n_zeros, true);              \
  98              (START) += (NODE)->n_ones,                                 \
  99                (NODE) = range_tower_next (RANGE_TOWER, NODE))
 100
 101 static inline const struct range_tower_node *range_tower_first (
 102   const struct range_tower *);
 103 static inline const struct range_tower_node *range_tower_next (
 104   const struct range_tower *, const struct range_tower_node *);
 105 static inline const struct range_tower_node *range_tower_last (
 106   const struct range_tower *);
 107 static inline const struct range_tower_node *range_tower_prev (
 108   const struct range_tower *, const struct range_tower_node *);
 109 unsigned long int range_tower_node_get_start (const struct range_tower_node *);
 110 unsigned long int range_tower_node_get_end (const struct range_tower_node *);
 111 static inline unsigned long int range_tower_node_get_width (
 112   const struct range_tower_node *);
 113 \f
 114 /* Inline functions. */
 115
 116 static inline struct range_tower_node *range_tower_node_from_abt__ (
 117   const struct abt_node *);
 118 static inline struct range_tower_node *range_tower_next__ (
 119   const struct range_tower *, const struct range_tower_node *);
 120 static inline struct range_tower_node *range_tower_first__ (
 121   const struct range_tower *);
 122 static inline struct range_tower_node *range_tower_prev__ (
 123   const struct range_tower *, const struct range_tower_node *);
 124 static inline struct range_tower_node *range_tower_last__ (
 125   const struct range_tower *);
 126
 127 /* Returns true if RS contains no 1-bits, false otherwise. */
 128 static inline bool
 129 range_tower_is_empty (const struct range_tower *rs)
 130 {
 131   const struct range_tower_node *node =
 132     abt_data (rs->abt.root, struct range_tower_node, abt_node);
 133
 134   return node->n_zeros == ULONG_MAX;
 135 }
 136
 137 /* Returns the node representing the first contiguous region of
 138    1-bits in RS, or a null pointer if RS is empty.
 139    Any call to range_tower_set1, range_tower_set0, or
 140    range_tower_allocate invalidates the returned node. */
 141 static inline const struct range_tower_node *
 142 range_tower_first (const struct range_tower *rs)
 143 {
 144   const struct range_tower_node *node = range_tower_first__ (rs);
 145   return node->n_ones ? node : NULL;
 146 }
 147
 148 /* If NODE is nonnull, returns the node representing the next
 149    contiguous region of 1-bits in RS following NODE, or a null
 150    pointer if NODE is the last region in RS.
 151    If NODE is null, returns the first region in RS, as for
 152    range_tower_first.
 153    Any call to range_tower_set1, range_tower_set0, or
 154    range_tower_allocate invalidates the returned node. */
 155 static inline const struct range_tower_node *
 156 range_tower_next (const struct range_tower *rs,
 157                   const struct range_tower_node *node)
 158 {
 159   if (node != NULL)
 160     {
 161       const struct range_tower_node *next = range_tower_next__ (rs, node);
 162       return next != NULL && next->n_ones ? next : NULL;
 163     }
 164   else
 165     return range_tower_first (rs);
 166 }
 167
 168 /* Returns the node representing the last contiguous region of
 169    1-bits in RS, or a null pointer if RS is empty.
 170    Any call to range_tower_set1, range_tower_set0, or
 171    range_tower_allocate invalidates the returned node. */
 172 static inline const struct range_tower_node *
 173 range_tower_last (const struct range_tower *rs)
 174 {
 175   const struct range_tower_node *node = range_tower_last__ (rs);
 176   return node->n_ones ? node : range_tower_prev__(rs, node);
 177 }
 178
 179 /* If NODE is nonnull, returns the node representing the previous
 180    contiguous region of 1-bits in RS following NODE, or a null
 181    pointer if NODE is the first region in RS.
 182    If NODE is null, returns the last region in RS, as for
 183    range_tower_last.
 184    Any call to range_tower_set1, range_tower_set0, or
 185    range_tower_allocate invalidates the returned node. */
 186 static inline const struct range_tower_node *
 187 range_tower_prev (const struct range_tower *rs,
 188                   const struct range_tower_node *node)
 189 {
 190   return node != NULL ? range_tower_prev__ (rs, node) : range_tower_last (rs);
 191 }
 192
 193 /* Returns the number of contiguous 1-bits in NODE. */
 194 static inline unsigned long int
 195 range_tower_node_get_width (const struct range_tower_node *node)
 196 {
 197   return node->n_ones;
 198 }
 199 \f
 200 /* Internal helper functions. */
 201
 202 /* Returns the range_tower_node corresponding to the given
 203    ABT_NODE.  Returns a null pointer if ABT_NODE is null. */
 204 static inline struct range_tower_node *
 205 range_tower_node_from_abt__ (const struct abt_node *abt_node)
 206 {
 207   return (abt_node
 208           ? abt_data (abt_node, struct range_tower_node, abt_node)
 209           : NULL);
 210 }
 211
 212 /* Returns the next range_tower_node in RS after NODE,
 213    or a null pointer if NODE is the last node in RS. */
 214 static inline struct range_tower_node *
 215 range_tower_next__ (const struct range_tower *rs,
 216                     const struct range_tower_node *node)
 217 {
 218   return range_tower_node_from_abt__ (abt_next (&rs->abt, &node->abt_node));
 219 }
 220
 221 /* Returns the first range_tower_node in RS,
 222    or a null pointer if RS is empty. */
 223 static inline struct range_tower_node *
 224 range_tower_first__ (const struct range_tower *rs)
 225 {
 226   return range_tower_node_from_abt__ (abt_first (&rs->abt));
 227 }
 228
 229 /* Returns the previous range_tower_node in RS after NODE,
 230    or a null pointer if NODE is the first node in RS. */
 231 static inline struct range_tower_node *
 232 range_tower_prev__ (const struct range_tower *rs,
 233                     const struct range_tower_node *node)
 234 {
 235   return range_tower_node_from_abt__ (abt_prev (&rs->abt, &node->abt_node));
 236 }
 237
 238 /* Returns the last range_tower_node in RS,
 239    or a null pointer if RS is empty. */
 240 static inline struct range_tower_node *
 241 range_tower_last__ (const struct range_tower *rs)
 242 {
 243   return range_tower_node_from_abt__ (abt_last (&rs->abt));
 244 }
 245
 246 struct range_tower_node *range_tower_lookup (
 247   const struct range_tower *, unsigned long int position,
 248   unsigned long int *node_start);
 249
 250 #endif /* libpspp/range-tower.h */