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