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 a balanced binary tree. */
18
19 /* If you add routines in this file, please add a corresponding
20 test to range-set-test.c. This test program should achieve
21 100% coverage of lines and branches in this code, as reported
22 by "gcov -b". */
23
24 #include <config.h>
25
26 #include "libpspp/range-set.h"
27
28 #include <limits.h>
29 #include <stdlib.h>
30
31 #include "libpspp/assertion.h"
32 #include "libpspp/compiler.h"
33 #include "libpspp/pool.h"
34
35 #include "gl/minmax.h"
36 #include "gl/xalloc.h"
37
38 static int compare_range_set_nodes (const struct bt_node *,
39 const struct bt_node *,
40 const void *aux);
41 static void delete_node (struct range_set *, struct range_set_node *);
42 static struct range_set_node *delete_node_get_next (struct range_set *,
43 struct range_set_node *);
44 static struct range_set_node *find_node_le (const struct range_set *,
45 unsigned long int position);
46 static struct range_set_node *insert_node (struct range_set *,
47 unsigned long int start,
48 unsigned long int end);
49 static void insert_just_before (struct range_set *,
50 unsigned long int start, unsigned long int end,
51 struct range_set_node *);
52 static void merge_node_with_successors (struct range_set *,
53 struct range_set_node *);
54 static void destroy_pool (void *);
55
56 /* Creates and returns a new, empty range set. */
57 struct range_set *
range_set_create(void)58 range_set_create (void)
59 {
60 return range_set_create_pool (NULL);
61 }
62
63 /* Creates and returns a new, empty range set in the given
64 POOL. */
65 struct range_set *
range_set_create_pool(struct pool * pool)66 range_set_create_pool (struct pool *pool)
67 {
68 struct range_set *rs = xmalloc (sizeof *rs);
69 rs->pool = pool;
70 if (pool != NULL)
71 pool_register (pool, destroy_pool, rs);
72 bt_init (&rs->bt, compare_range_set_nodes, NULL);
73 rs->cache_end = 0;
74 return rs;
75 }
76
77 /* Creates and returns a clone of OLD range set in the given POOL
78 (which may be null). */
79 struct range_set *
range_set_clone(const struct range_set * old,struct pool * pool)80 range_set_clone (const struct range_set *old, struct pool *pool)
81 {
82 struct range_set *new;
83 struct range_set_node *node;
84
85 new = range_set_create_pool (pool);
86 for (node = range_set_first__ (old); node != NULL;
87 node = range_set_next__ (old, node))
88 insert_node (new, node->start, node->end);
89 return new;
90 }
91
92 /* Destroys range set RS. */
93 void
range_set_destroy(struct range_set * rs)94 range_set_destroy (struct range_set *rs)
95 {
96 if (rs != NULL)
97 {
98 if (rs->pool != NULL)
99 pool_unregister (rs->pool, rs);
100 while (!range_set_is_empty (rs))
101 delete_node (rs, range_set_first__ (rs));
102 free (rs);
103 }
104 }
105
106 /* Inserts the region starting at START and extending for WIDTH
107 into RS. */
108 void
range_set_set1(struct range_set * rs,unsigned long int start,unsigned long int width)109 range_set_set1 (struct range_set *rs,
110 unsigned long int start, unsigned long int width)
111 {
112 unsigned long int end = start + width;
113 struct range_set_node *node;
114
115 assert (width == 0 || start + width - 1 >= start);
116
117 if (width == 0)
118 return;
119
120 /* Invalidate cache. */
121 rs->cache_end = 0;
122
123 node = find_node_le (rs, start);
124 if (node != NULL)
125 {
126 if (start > node->end)
127 {
128 /* New region does not overlap NODE, but it might
129 overlap the next node. */
130 insert_just_before (rs, start, end, range_set_next__ (rs, node));
131 }
132 else if (end > node->end)
133 {
134 /* New region starts in the middle of NODE and
135 continues past its end, so extend NODE, then merge
136 it with any following node that it now potentially
137 overlaps. */
138 node->end = end;
139 merge_node_with_successors (rs, node);
140 }
141 else
142 {
143 /* New region is completely contained by NODE, so
144 there's nothing to do. */
145 }
146 }
147 else
148 {
149 /* New region starts before any existing region, but it
150 might overlap the first region. */
151 insert_just_before (rs, start, end, range_set_first__ (rs));
152 }
153 }
154
155 /* Deletes the region starting at START and extending for WIDTH
156 from RS. */
157 void
range_set_set0(struct range_set * rs,unsigned long int start,unsigned long int width)158 range_set_set0 (struct range_set *rs,
159 unsigned long int start, unsigned long int width)
160 {
161 unsigned long int end = start + width;
162 struct range_set_node *node;
163
164 assert (width == 0 || start + width - 1 >= start);
165
166 if (width == 0)
167 return;
168
169 /* Invalidate cache. */
170 rs->cache_end = 0;
171
172 node = find_node_le (rs, start);
173 if (node == NULL)
174 node = range_set_first__ (rs);
175
176 while (node != NULL && end > node->start)
177 {
178 if (start <= node->start)
179 {
180 if (end >= node->end)
181 {
182 /* Region to delete covers entire node. */
183 node = delete_node_get_next (rs, node);
184 }
185 else
186 {
187 /* Region to delete covers only left part of node. */
188 node->start = end;
189 break;
190 }
191 }
192 else if (start < node->end)
193 {
194 if (end < node->end)
195 {
196 /* Region to delete covers middle of the node, so
197 we have to split the node into two pieces. */
198 unsigned long int old_node_end = node->end;
199 node->end = start;
200 insert_node (rs, end, old_node_end);
201 break;
202 }
203 else
204 {
205 /* Region to delete covers only right part of
206 node. */
207 node->end = start;
208 node = range_set_next__ (rs, node);
209 }
210 }
211 else
212 node = range_set_next__ (rs, node);
213 }
214 }
215
216 /* Scans RS for its first 1-bit and deletes up to REQUEST
217 contiguous 1-bits starting at that position. Unless RS is
218 completely empty, sets *START to the position of the first
219 1-bit deleted and *WIDTH to the number actually deleted, which
220 may be less than REQUEST if fewer contiguous 1-bits were
221 present, and returns true. If RS is completely empty, returns
222 false. */
223 bool
range_set_allocate(struct range_set * rs,unsigned long int request,unsigned long int * start,unsigned long int * width)224 range_set_allocate (struct range_set *rs, unsigned long int request,
225 unsigned long int *start, unsigned long int *width)
226 {
227 struct range_set_node *node;
228 unsigned long int node_width;
229
230 assert (request > 0);
231
232 node = range_set_first__ (rs);
233 if (node == NULL)
234 return false;
235 node_width = node->end - node->start;
236
237 *start = node->start;
238 if (request < node_width)
239 {
240 *width = request;
241 node->start += request;
242 }
243 else
244 {
245 *width = node_width;
246 delete_node (rs, node);
247 }
248
249 rs->cache_end = 0;
250
251 return true;
252 }
253
254 /* Scans RS for and deletes the first contiguous run of REQUEST
255 1-bits. If successful, sets *START to the position of the
256 first 1-bit deleted and returns true If RS does not contain a
257 run of REQUEST or more contiguous 1-bits, returns false and
258 does not modify RS. */
259 bool
range_set_allocate_fully(struct range_set * rs,unsigned long int request,unsigned long int * start)260 range_set_allocate_fully (struct range_set *rs, unsigned long int request,
261 unsigned long int *start)
262 {
263 struct range_set_node *node;
264
265 assert (request > 0);
266
267 for (node = range_set_first__ (rs); node != NULL;
268 node = range_set_next__ (rs, node))
269 {
270 unsigned long int node_width = node->end - node->start;
271 if (node_width >= request)
272 {
273 *start = node->start;
274 if (node_width > request)
275 node->start += request;
276 else
277 delete_node (rs, node);
278 rs->cache_end = 0;
279 return true;
280 }
281 }
282 return false;
283 }
284
285 /* Returns true if there is a 1-bit at the given POSITION in RS,
286 false otherwise. */
287 bool
range_set_contains(const struct range_set * rs_,unsigned long int position)288 range_set_contains (const struct range_set *rs_, unsigned long int position)
289 {
290 struct range_set *rs = CONST_CAST (struct range_set *, rs_);
291 if (position < rs->cache_end && position >= rs->cache_start)
292 return rs->cache_value;
293 else
294 {
295 struct range_set_node *node = find_node_le (rs, position);
296 if (node != NULL)
297 {
298 if (position < node->end)
299 {
300 rs->cache_start = node->start;
301 rs->cache_end = node->end;
302 rs->cache_value = true;
303 return true;
304 }
305 else
306 {
307 struct range_set_node *next = range_set_next__ (rs, node);
308 rs->cache_start = node->end;
309 rs->cache_end = next != NULL ? next->start : ULONG_MAX;
310 rs->cache_value = false;
311 return false;
312 }
313 }
314 else
315 {
316 node = range_set_first__ (rs);
317 rs->cache_start = 0;
318 rs->cache_end = node != NULL ? node->start : ULONG_MAX;
319 rs->cache_value = false;
320 return false;
321 }
322 }
323 }
324
325 /* Returns the smallest position of a 1-bit greater than or
326 equal to START. Returns ULONG_MAX if there is no 1-bit with
327 position greater than or equal to START. */
328 unsigned long int
range_set_scan(const struct range_set * rs_,unsigned long int start)329 range_set_scan (const struct range_set *rs_, unsigned long int start)
330 {
331 struct range_set *rs = CONST_CAST (struct range_set *, rs_);
332 unsigned long int retval = ULONG_MAX;
333 struct bt_node *bt_node;
334
335 if (start < rs->cache_end && start >= rs->cache_start && rs->cache_value)
336 return start;
337 bt_node = rs->bt.root;
338 while (bt_node != NULL)
339 {
340 struct range_set_node *node = range_set_node_from_bt__ (bt_node);
341 if (start < node->start)
342 {
343 retval = node->start;
344 bt_node = node->bt_node.down[0];
345 }
346 else if (start >= node->end)
347 bt_node = node->bt_node.down[1];
348 else
349 {
350 rs->cache_start = node->start;
351 rs->cache_end = node->end;
352 rs->cache_value = true;
353 return start;
354 }
355 }
356 return retval;
357 }
358
359 /* Compares `range_set_node's A and B and returns a strcmp-like
360 return value. */
361 static int
compare_range_set_nodes(const struct bt_node * a_,const struct bt_node * b_,const void * aux UNUSED)362 compare_range_set_nodes (const struct bt_node *a_,
363 const struct bt_node *b_,
364 const void *aux UNUSED)
365 {
366 const struct range_set_node *a = range_set_node_from_bt__ (a_);
367 const struct range_set_node *b = range_set_node_from_bt__ (b_);
368
369 return a->start < b->start ? -1 : a->start > b->start;
370 }
371
372 /* Deletes NODE from RS and frees it. */
373 static void
delete_node(struct range_set * rs,struct range_set_node * node)374 delete_node (struct range_set *rs, struct range_set_node *node)
375 {
376 bt_delete (&rs->bt, &node->bt_node);
377 free (node);
378 }
379
380 /* Deletes NODE from RS, frees it, and returns the following
381 node. */
382 static struct range_set_node *
delete_node_get_next(struct range_set * rs,struct range_set_node * node)383 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
384 {
385 struct range_set_node *next = range_set_next__ (rs, node);
386 delete_node (rs, node);
387 return next;
388 }
389
390 /* Returns the node in RS that would be just before POSITION if a
391 range_set_node with `start' as POSITION were inserted.
392 Returns a null pointer if POSITION is before any existing node
393 in RS. If POSITION would duplicate an existing region's
394 start, returns that region. */
395 static struct range_set_node *
find_node_le(const struct range_set * rs,unsigned long int position)396 find_node_le (const struct range_set *rs, unsigned long int position)
397 {
398 struct range_set_node tmp;
399 tmp.start = position;
400 return range_set_node_from_bt__ (bt_find_le (&rs->bt, &tmp.bt_node));
401 }
402
403 /* Creates a new region with the given START and END, inserts the
404 region into RS, and returns the new region. */
405 static struct range_set_node *
insert_node(struct range_set * rs,unsigned long int start,unsigned long int end)406 insert_node (struct range_set *rs,
407 unsigned long int start, unsigned long int end)
408 {
409 struct range_set_node *node = xmalloc (sizeof *node);
410 struct bt_node *dummy;
411 node->start = start;
412 node->end = end;
413 dummy = bt_insert (&rs->bt, &node->bt_node);
414 assert (dummy == NULL);
415 return node;
416 }
417
418 /* Inserts the region START...END (exclusive) into RS given that
419 the new region is "just before" NODE, that is, if NODE is
420 nonnull, the new region is known not to overlap any node
421 preceding NODE, and START precedes NODE's start; if NODE is
422 null, then the new region is known to follow any and all
423 regions already in RS. */
424 static void
insert_just_before(struct range_set * rs,unsigned long int start,unsigned long int end,struct range_set_node * node)425 insert_just_before (struct range_set *rs,
426 unsigned long int start, unsigned long int end,
427 struct range_set_node *node)
428 {
429 assert (node == NULL || start < node->start);
430 if (node != NULL && end >= node->start)
431 {
432 /* New region overlaps NODE, so just extend NODE. */
433 node->start = start;
434 if (end > node->end)
435 {
436 node->end = end;
437 merge_node_with_successors (rs, node);
438 }
439 }
440 else
441 {
442 /* New region does not overlap NODE. */
443 insert_node (rs, start, end);
444 }
445 }
446
447 /* Merges NODE in RS with its successors. */
448 static void
merge_node_with_successors(struct range_set * rs,struct range_set_node * node)449 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
450 {
451 struct range_set_node *next;
452
453 while ((next = range_set_next__ (rs, node)) != NULL
454 && node->end >= next->start)
455 {
456 if (next->end > node->end)
457 node->end = next->end;
458 delete_node (rs, next);
459 }
460 }
461
462 /* Destroys range set RS.
463 Helper function for range_set_create_pool. */
464 static void
destroy_pool(void * rs_)465 destroy_pool (void *rs_)
466 {
467 struct range_set *rs = rs_;
468 rs->pool = NULL;
469 range_set_destroy (rs);
470 }
471