1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009 Free Software Foundation, Inc.
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.
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.
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/>. */
17 /* Bitmap, implemented as a balanced binary tree. */
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
26 #include <libpspp/range-set.h>
31 #include <libpspp/assertion.h>
32 #include <libpspp/bt.h>
33 #include <libpspp/compiler.h>
34 #include <libpspp/pool.h>
38 /* A set of ranges. */
41 struct pool *pool; /* Pool for freeing range_set. */
42 struct bt bt; /* Tree of range_set_nodes. */
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 set? */
50 /* A node in the range set. */
53 struct bt_node bt_node; /* Binary tree node. */
54 unsigned long int start; /* Start of region. */
55 unsigned long int end; /* One past end of region. */
58 static struct range_set_node *bt_to_rs_node (const struct bt_node *);
59 static int compare_range_set_nodes (const struct bt_node *,
60 const struct bt_node *,
62 static struct range_set_node *first_node (const struct range_set *);
63 static struct range_set_node *next_node (const struct range_set *,
64 const struct range_set_node *);
65 static void delete_node (struct range_set *, struct range_set_node *);
66 static struct range_set_node *delete_node_get_next (struct range_set *,
67 struct range_set_node *);
68 static struct range_set_node *find_node_le (const struct range_set *,
69 unsigned long int position);
70 static struct range_set_node *insert_node (struct range_set *,
71 unsigned long int start,
72 unsigned long int end);
73 static void insert_just_before (struct range_set *,
74 unsigned long int start, unsigned long int end,
75 struct range_set_node *);
76 static void merge_node_with_successors (struct range_set *,
77 struct range_set_node *);
78 static void destroy_pool (void *);
80 /* Creates and returns a new, empty range set. */
82 range_set_create (void)
84 return range_set_create_pool (NULL);
87 /* Creates and returns a new, empty range set in the given
90 range_set_create_pool (struct pool *pool)
92 struct range_set *rs = xmalloc (sizeof *rs);
95 pool_register (pool, destroy_pool, rs);
96 bt_init (&rs->bt, compare_range_set_nodes, NULL);
101 /* Creates and returns a clone of OLD range set in the given POOL
102 (which may be null). */
104 range_set_clone (const struct range_set *old, struct pool *pool)
106 struct range_set *new;
107 struct range_set_node *node;
109 new = range_set_create_pool (pool);
110 for (node = first_node (old); node != NULL; node = next_node (old, node))
111 insert_node (new, node->start, node->end);
115 /* Destroys range set RS. */
117 range_set_destroy (struct range_set *rs)
121 if (rs->pool != NULL)
122 pool_unregister (rs->pool, rs);
123 while (!range_set_is_empty (rs))
124 delete_node (rs, first_node (rs));
129 /* Inserts the region starting at START and extending for WIDTH
132 range_set_insert (struct range_set *rs,
133 unsigned long int start, unsigned long int width)
135 unsigned long int end = start + width;
136 struct range_set_node *node;
138 assert (width == 0 || start + width - 1 >= start);
143 /* Invalidate cache. */
146 node = find_node_le (rs, start);
149 if (start > node->end)
151 /* New region does not overlap NODE, but it might
152 overlap the next node. */
153 insert_just_before (rs, start, end, next_node (rs, node));
155 else if (end > node->end)
157 /* New region starts in the middle of NODE and
158 continues past its end, so extend NODE, then merge
159 it with any following node that it now potentially
162 merge_node_with_successors (rs, node);
166 /* New region is completely contained by NODE, so
167 there's nothing to do. */
172 /* New region starts before any existing region, but it
173 might overlap the first region. */
174 insert_just_before (rs, start, end, first_node (rs));
178 /* Inserts the region starting at START and extending for WIDTH
181 range_set_delete (struct range_set *rs,
182 unsigned long int start, unsigned long int width)
184 unsigned long int end = start + width;
185 struct range_set_node *node;
187 assert (width == 0 || start + width - 1 >= start);
192 /* Invalidate cache. */
195 node = find_node_le (rs, start);
197 node = first_node (rs);
199 while (node != NULL && end > node->start)
201 if (start <= node->start)
203 if (end >= node->end)
205 /* Region to delete covers entire node. */
206 node = delete_node_get_next (rs, node);
210 /* Region to delete covers only left part of node. */
215 else if (start < node->end)
219 /* Region to delete covers middle of the node, so
220 we have to split the node into two pieces. */
221 unsigned long int old_node_end = node->end;
223 insert_node (rs, end, old_node_end);
228 /* Region to delete covers only right part of
231 node = next_node (rs, node);
235 node = next_node (rs, node);
239 /* Scans RS for its first 1-bit and deletes up to REQUEST
240 contiguous 1-bits starting at that position. Unless RS is
241 completely empty, sets *START to the position of the first
242 1-bit deleted and *WIDTH to the number actually deleted, which
243 may be less than REQUEST if fewer contiguous 1-bits were
244 present, and returns true. If RS is completely empty, returns
247 range_set_allocate (struct range_set *rs, unsigned long int request,
248 unsigned long int *start, unsigned long int *width)
250 struct range_set_node *node;
251 unsigned long int node_width;
253 assert (request > 0);
255 node = first_node (rs);
258 node_width = node->end - node->start;
260 *start = node->start;
261 if (request < node_width)
264 node->start += request;
269 delete_node (rs, node);
277 /* Scans RS for and deletes the first contiguous run of REQUEST
278 1-bits. If successful, sets *START to the position of the
279 first 1-bit deleted and returns true If RS does not contain a
280 run of REQUEST or more contiguous 1-bits, returns false and
281 does not modify RS. */
283 range_set_allocate_fully (struct range_set *rs, unsigned long int request,
284 unsigned long int *start)
286 struct range_set_node *node;
288 assert (request > 0);
290 for (node = first_node (rs); node != NULL; node = next_node (rs, node))
292 unsigned long int node_width = node->end - node->start;
293 if (node_width >= request)
295 *start = node->start;
296 if (node_width > request)
297 node->start += request;
299 delete_node (rs, node);
307 /* Returns true if there is a 1-bit at the given POSITION in RS,
310 range_set_contains (const struct range_set *rs_, unsigned long int position)
312 struct range_set *rs = (struct range_set *) rs_;
313 if (position < rs->cache_end && position >= rs->cache_start)
314 return rs->cache_value;
317 struct range_set_node *node = find_node_le (rs, position);
320 if (position < node->end)
322 rs->cache_start = node->start;
323 rs->cache_end = node->end;
324 rs->cache_value = true;
329 struct range_set_node *next = next_node (rs, node);
330 rs->cache_start = node->end;
331 rs->cache_end = next != NULL ? next->start : ULONG_MAX;
332 rs->cache_value = false;
338 node = first_node (rs);
340 rs->cache_end = node != NULL ? node->start : ULONG_MAX;
341 rs->cache_value = false;
347 /* Returns true if RS contains no 1-bits, false otherwise. */
349 range_set_is_empty (const struct range_set *rs)
351 return bt_count (&rs->bt) == 0;
354 /* Returns the node representing the first contiguous region of
355 1-bits in RS, or a null pointer if RS is empty.
356 Any call to range_set_insert, range_set_delete, or
357 range_set_allocate invalidates the returned node. */
358 const struct range_set_node *
359 range_set_first (const struct range_set *rs)
361 return first_node (rs);
364 /* If NODE is nonnull, returns the node representing the next
365 contiguous region of 1-bits in RS following NODE, or a null
366 pointer if NODE is the last region in RS.
367 If NODE is null, returns the first region in RS, as for
369 Any call to range_set_insert, range_set_delete, or
370 range_set_allocate invalidates the returned node. */
371 const struct range_set_node *
372 range_set_next (const struct range_set *rs, const struct range_set_node *node)
375 ? next_node (rs, (struct range_set_node *) node)
379 /* Returns the position of the first 1-bit in NODE. */
381 range_set_node_get_start (const struct range_set_node *node)
386 /* Returns one past the position of the last 1-bit in NODE. */
388 range_set_node_get_end (const struct range_set_node *node)
393 /* Returns the number of contiguous 1-bits in NODE. */
395 range_set_node_get_width (const struct range_set_node *node)
397 return node->end - node->start;
400 /* Returns the range_set_node corresponding to the given
401 BT_NODE. Returns a null pointer if BT_NODE is null. */
402 static struct range_set_node *
403 bt_to_rs_node (const struct bt_node *bt_node)
405 return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
408 /* Compares `range_set_node's A and B and returns a strcmp-like
411 compare_range_set_nodes (const struct bt_node *a_,
412 const struct bt_node *b_,
413 const void *aux UNUSED)
415 const struct range_set_node *a = bt_to_rs_node (a_);
416 const struct range_set_node *b = bt_to_rs_node (b_);
418 return a->start < b->start ? -1 : a->start > b->start;
421 /* Returns the first range_set_node in RS,
422 or a null pointer if RS is empty. */
423 static struct range_set_node *
424 first_node (const struct range_set *rs)
426 return bt_to_rs_node (bt_first (&rs->bt));
429 /* Returns the next range_set_node in RS after NODE,
430 or a null pointer if NODE is the last node in RS. */
431 static struct range_set_node *
432 next_node (const struct range_set *rs, const struct range_set_node *node)
434 return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
437 /* Deletes NODE from RS and frees it. */
439 delete_node (struct range_set *rs, struct range_set_node *node)
441 bt_delete (&rs->bt, &node->bt_node);
445 /* Deletes NODE from RS, frees it, and returns the following
447 static struct range_set_node *
448 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
450 struct range_set_node *next = next_node (rs, node);
451 delete_node (rs, node);
455 /* Returns the node in RS that would be just before POSITION if a
456 range_set_node with `start' as POSITION were inserted.
457 Returns a null pointer if POSITION is before any existing node
458 in RS. If POSITION would duplicate an existing region's
459 start, returns that region. */
460 static struct range_set_node *
461 find_node_le (const struct range_set *rs, unsigned long int position)
463 struct range_set_node tmp;
464 tmp.start = position;
465 return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
468 /* Creates a new region with the given START and END, inserts the
469 region into RS, and returns the new region. */
470 static struct range_set_node *
471 insert_node (struct range_set *rs,
472 unsigned long int start, unsigned long int end)
474 struct range_set_node *node = xmalloc (sizeof *node);
475 struct bt_node *dummy;
478 dummy = bt_insert (&rs->bt, &node->bt_node);
479 assert (dummy == NULL);
483 /* Inserts the region START...END (exclusive) into RS given that
484 the new region is "just before" NODE, that is, if NODE is
485 nonnull, the new region is known not to overlap any node
486 preceding NODE, and START precedes NODE's start; if NODE is
487 null, then the new region is known to follow any and all
488 regions already in RS. */
490 insert_just_before (struct range_set *rs,
491 unsigned long int start, unsigned long int end,
492 struct range_set_node *node)
494 assert (node == NULL || start < node->start);
495 if (node != NULL && end >= node->start)
497 /* New region overlaps NODE, so just extend NODE. */
502 merge_node_with_successors (rs, node);
507 /* New region does not overlap NODE. */
508 insert_node (rs, start, end);
512 /* Merges NODE in RS with its successors. */
514 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
516 struct range_set_node *next;
518 while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
520 if (next->end > node->end)
521 node->end = next->end;
522 delete_node (rs, next);
526 /* Destroys range set RS.
527 Helper function for range_set_create_pool. */
529 destroy_pool (void *rs_)
531 struct range_set *rs = rs_;
533 range_set_destroy (rs);