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 unsigned long int range_set_node_get_start (
  74   const struct range_set_node *);
  75 static inline unsigned long int range_set_node_get_end (
  76   const struct range_set_node *);
  77 static inline unsigned long int range_set_node_get_width (
  78   const struct range_set_node *);
  79 \f
  80 /* Inline functions. */
  81
  82 static inline struct range_set_node *range_set_node_from_bt__ (
  83   const struct bt_node *);
  84 static inline struct range_set_node *range_set_next__ (
  85   const struct range_set *, const struct range_set_node *);
  86 static inline struct range_set_node *range_set_first__ (
  87   const struct range_set *);
  88
  89 /* Returns true if RS contains no 1-bits, false otherwise. */
  90 static inline bool
  91 range_set_is_empty (const struct range_set *rs)
  92 {
  93   return bt_count (&rs->bt) == 0;
  94 }
  95
  96 /* Returns the node representing the first contiguous region of
  97    1-bits in RS, or a null pointer if RS is empty.
  98    Any call to range_set_insert, range_set_delete, or
  99    range_set_allocate invalidates the returned node. */
 100 static inline const struct range_set_node *
 101 range_set_first (const struct range_set *rs)
 102 {
 103   return range_set_first__ (rs);
 104 }
 105
 106 /* If NODE is nonnull, returns the node representing the next
 107    contiguous region of 1-bits in RS following NODE, or a null
 108    pointer if NODE is the last region in RS.
 109    If NODE is null, returns the first region in RS, as for
 110    range_set_first.
 111    Any call to range_set_insert, range_set_delete, or
 112    range_set_allocate invalidates the returned node. */
 113 static inline const struct range_set_node *
 114 range_set_next (const struct range_set *rs, const struct range_set_node *node)
 115 {
 116   return (node != NULL
 117           ? range_set_next__ (rs, (struct range_set_node *) node)
 118           : range_set_first__ (rs));
 119 }
 120
 121 /* Returns the position of the first 1-bit in NODE. */
 122 static inline unsigned long int
 123 range_set_node_get_start (const struct range_set_node *node)
 124 {
 125   return node->start;
 126 }
 127
 128 /* Returns one past the position of the last 1-bit in NODE. */
 129 static inline unsigned long int
 130 range_set_node_get_end (const struct range_set_node *node)
 131 {
 132   return node->end;
 133 }
 134
 135 /* Returns the number of contiguous 1-bits in NODE. */
 136 static inline unsigned long int
 137 range_set_node_get_width (const struct range_set_node *node)
 138 {
 139   return node->end - node->start;
 140 }
 141 \f
 142 /* Internal helper functions. */
 143
 144 /* Returns the range_set_node corresponding to the given
 145    BT_NODE.  Returns a null pointer if BT_NODE is null. */
 146 static inline struct range_set_node *
 147 range_set_node_from_bt__ (const struct bt_node *bt_node)
 148 {
 149   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
 150 }
 151
 152 /* Returns the next range_set_node in RS after NODE,
 153    or a null pointer if NODE is the last node in RS. */
 154 static inline struct range_set_node *
 155 range_set_next__ (const struct range_set *rs,
 156                   const struct range_set_node *node)
 157 {
 158   return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
 159 }
 160
 161 /* Returns the first range_set_node in RS,
 162    or a null pointer if RS is empty. */
 163 static inline struct range_set_node *
 164 range_set_first__ (const struct range_set *rs)
 165 {
 166   return range_set_node_from_bt__ (bt_first (&rs->bt));
 167 }
 168
 169 #endif /* libpspp/range-set.h */