Remove debug printfs that escaped from my local tree.
[pspp-builds.git] / 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 */