1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* Bitmap, implemented as a balanced binary tree. */
21 /* If you add routines in this file, please add a corresponding
22 test to range-set-test.c. This test program should achieve
23 100% coverage of lines and branches in this code, as reported
28 #include <libpspp/range-set.h>
33 #include <libpspp/assertion.h>
34 #include <libpspp/bt.h>
35 #include <libpspp/compiler.h>
36 #include <libpspp/pool.h>
40 /* A set of ranges. */
43 struct pool *pool; /* Pool for freeing range_set. */
44 struct bt bt; /* Tree of range_set_nodes. */
47 unsigned long int cache_start; /* Start of region. */
48 unsigned long int cache_end; /* One past end of region. */
49 bool cache_value; /* Is the region in the set? */
52 /* A node in the range set. */
55 struct bt_node bt_node; /* Binary tree node. */
56 unsigned long int start; /* Start of region. */
57 unsigned long int end; /* One past end of region. */
60 static struct range_set_node *bt_to_rs_node (const struct bt_node *);
61 static int compare_range_set_nodes (const struct bt_node *,
62 const struct bt_node *,
64 static struct range_set_node *first_node (const struct range_set *);
65 static struct range_set_node *next_node (const struct range_set *,
66 const struct range_set_node *);
67 static void delete_node (struct range_set *, struct range_set_node *);
68 static struct range_set_node *delete_node_get_next (struct range_set *,
69 struct range_set_node *);
70 static struct range_set_node *find_node_le (const struct range_set *,
71 unsigned long int position);
72 static struct range_set_node *insert_node (struct range_set *,
73 unsigned long int start,
74 unsigned long int end);
75 static void insert_just_before (struct range_set *,
76 unsigned long int start, unsigned long int end,
77 struct range_set_node *);
78 static void merge_node_with_successors (struct range_set *,
79 struct range_set_node *);
80 static void destroy_pool (void *);
82 /* Creates and returns a new, empty range set. */
84 range_set_create (void)
86 return range_set_create_pool (NULL);
89 /* Creates and returns a new, empty range set in the given
92 range_set_create_pool (struct pool *pool)
94 struct range_set *rs = xmalloc (sizeof *rs);
97 pool_register (pool, destroy_pool, rs);
98 bt_init (&rs->bt, compare_range_set_nodes, NULL);
103 /* Creates and returns a clone of OLD range set in the given POOL
104 (which may be null). */
106 range_set_clone (const struct range_set *old, struct pool *pool)
108 struct range_set *new;
109 struct range_set_node *node;
111 new = range_set_create_pool (pool);
112 for (node = first_node (old); node != NULL; node = next_node (old, node))
113 insert_node (new, node->start, node->end);
117 /* Destroys range set RS. */
119 range_set_destroy (struct range_set *rs)
123 if (rs->pool != NULL)
124 pool_unregister (rs->pool, rs);
125 while (!range_set_is_empty (rs))
126 delete_node (rs, first_node (rs));
131 /* Inserts the region starting at START and extending for WIDTH
134 range_set_insert (struct range_set *rs,
135 unsigned long int start, unsigned long int width)
137 unsigned long int end = start + width;
138 struct range_set_node *node;
140 assert (width == 0 || start + width - 1 >= start);
145 /* Invalidate cache. */
148 node = find_node_le (rs, start);
151 if (start > node->end)
153 /* New region does not overlap NODE, but it might
154 overlap the next node. */
155 insert_just_before (rs, start, end, next_node (rs, node));
157 else if (end > node->end)
159 /* New region starts in the middle of NODE and
160 continues past its end, so extend NODE, then merge
161 it with any following node that it now potentially
164 merge_node_with_successors (rs, node);
168 /* New region is completely contained by NODE, so
169 there's nothing to do. */
174 /* New region starts before any existing region, but it
175 might overlap the first region. */
176 insert_just_before (rs, start, end, first_node (rs));
180 /* Inserts the region starting at START and extending for WIDTH
183 range_set_delete (struct range_set *rs,
184 unsigned long int start, unsigned long int width)
186 unsigned long int end = start + width;
187 struct range_set_node *node;
189 assert (width == 0 || start + width - 1 >= start);
194 /* Invalidate cache. */
197 node = find_node_le (rs, start);
199 node = first_node (rs);
201 while (node != NULL && end > node->start)
203 if (start <= node->start)
205 if (end >= node->end)
207 /* Region to delete covers entire node. */
208 node = delete_node_get_next (rs, node);
212 /* Region to delete covers only left part of node. */
217 else if (start < node->end)
221 /* Region to delete covers middle of the node, so
222 we have to split the node into two pieces. */
223 unsigned long int old_node_end = node->end;
225 insert_node (rs, end, old_node_end);
230 /* Region to delete covers only right part of
233 node = next_node (rs, node);
237 node = next_node (rs, node);
241 /* Scans RS for its first 1-bit and deletes up to REQUEST
242 contiguous 1-bits starting at that position. Unless RS is
243 completely empty, sets *START to the position of the first
244 1-bit deleted and *WIDTH to the number actually deleted, which
245 may be less than REQUEST if fewer contiguous 1-bits were
246 present, and returns true. If RS is completely empty, returns
249 range_set_allocate (struct range_set *rs, unsigned long int request,
250 unsigned long int *start, unsigned long int *width)
252 struct range_set_node *node;
253 unsigned long int node_width;
255 assert (request > 0);
257 node = first_node (rs);
260 node_width = node->end - node->start;
262 *start = node->start;
263 if (request < node_width)
266 node->start += request;
271 delete_node (rs, node);
279 /* Returns true if there is a 1-bit at the given POSITION in RS,
282 range_set_contains (const struct range_set *rs_, unsigned long int position)
284 struct range_set *rs = (struct range_set *) rs_;
285 if (position < rs->cache_end && position >= rs->cache_start)
286 return rs->cache_value;
289 struct range_set_node *node = find_node_le (rs, position);
292 if (position < node->end)
294 rs->cache_start = node->start;
295 rs->cache_end = node->end;
296 rs->cache_value = true;
301 struct range_set_node *next = next_node (rs, node);
302 rs->cache_start = node->end;
303 rs->cache_end = next != NULL ? next->start : ULONG_MAX;
304 rs->cache_value = false;
310 node = first_node (rs);
312 rs->cache_end = node != NULL ? node->start : ULONG_MAX;
313 rs->cache_value = false;
319 /* Returns true if RS contains no 1-bits, false otherwise. */
321 range_set_is_empty (const struct range_set *rs)
323 return bt_count (&rs->bt) == 0;
326 /* Returns the node representing the first contiguous region of
327 1-bits in RS, or a null pointer if RS is empty.
328 Any call to range_set_insert, range_set_delete, or
329 range_set_allocate invalidates the returned node. */
330 const struct range_set_node *
331 range_set_first (const struct range_set *rs)
333 return first_node (rs);
336 /* If NODE is nonnull, returns the node representing the next
337 contiguous region of 1-bits in RS following NODE, or a null
338 pointer if NODE is the last region in RS.
339 If NODE is null, returns the first region in RS, as for
341 Any call to range_set_insert, range_set_delete, or
342 range_set_allocate invalidates the returned node. */
343 const struct range_set_node *
344 range_set_next (const struct range_set *rs, const struct range_set_node *node)
347 ? next_node (rs, (struct range_set_node *) node)
351 /* Returns the position of the first 1-bit in NODE. */
353 range_set_node_get_start (const struct range_set_node *node)
358 /* Returns one past the position of the last 1-bit in NODE. */
360 range_set_node_get_end (const struct range_set_node *node)
365 /* Returns the number of contiguous 1-bits in NODE. */
367 range_set_node_get_width (const struct range_set_node *node)
369 return node->end - node->start;
372 /* Returns the range_set_node corresponding to the given
373 BT_NODE. Returns a null pointer if BT_NODE is null. */
374 static struct range_set_node *
375 bt_to_rs_node (const struct bt_node *bt_node)
377 return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
380 /* Compares `range_set_node's A and B and returns a strcmp-like
383 compare_range_set_nodes (const struct bt_node *a_,
384 const struct bt_node *b_,
385 const void *aux UNUSED)
387 const struct range_set_node *a = bt_to_rs_node (a_);
388 const struct range_set_node *b = bt_to_rs_node (b_);
390 return a->start < b->start ? -1 : a->start > b->start;
393 /* Returns the first range_set_node in RS,
394 or a null pointer if RS is empty. */
395 static struct range_set_node *
396 first_node (const struct range_set *rs)
398 return bt_to_rs_node (bt_first (&rs->bt));
401 /* Returns the next range_set_node in RS after NODE,
402 or a null pointer if NODE is the last node in RS. */
403 static struct range_set_node *
404 next_node (const struct range_set *rs, const struct range_set_node *node)
406 return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
409 /* Deletes NODE from RS and frees it. */
411 delete_node (struct range_set *rs, struct range_set_node *node)
413 bt_delete (&rs->bt, &node->bt_node);
417 /* Deletes NODE from RS, frees it, and returns the following
419 static struct range_set_node *
420 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
422 struct range_set_node *next = next_node (rs, node);
423 delete_node (rs, node);
427 /* Returns the node in RS that would be just before POSITION if a
428 range_set_node with `start' as POSITION were inserted.
429 Returns a null pointer if POSITION is before any existing node
430 in RS. If POSITION would duplicate an existing region's
431 start, returns that region. */
432 static struct range_set_node *
433 find_node_le (const struct range_set *rs, unsigned long int position)
435 struct range_set_node tmp;
436 tmp.start = position;
437 return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
440 /* Creates a new region with the given START and END, inserts the
441 region into RS, and returns the new region. */
442 static struct range_set_node *
443 insert_node (struct range_set *rs,
444 unsigned long int start, unsigned long int end)
446 struct range_set_node *node = xmalloc (sizeof *node);
447 struct bt_node *dummy;
450 dummy = bt_insert (&rs->bt, &node->bt_node);
451 assert (dummy == NULL);
455 /* Inserts the region START...END (exclusive) into RS given that
456 the new region is "just before" NODE, that is, if NODE is
457 nonnull, the new region is known not to overlap any node
458 preceding NODE, and START precedes NODE's start; if NODE is
459 null, then the new region is known to follow any and all
460 regions already in RS. */
462 insert_just_before (struct range_set *rs,
463 unsigned long int start, unsigned long int end,
464 struct range_set_node *node)
466 assert (node == NULL || start < node->start);
467 if (node != NULL && end >= node->start)
469 /* New region overlaps NODE, so just extend NODE. */
474 merge_node_with_successors (rs, node);
479 /* New region does not overlap NODE. */
480 insert_node (rs, start, end);
484 /* Merges NODE in RS with its successors. */
486 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
488 struct range_set_node *next;
490 while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
492 if (next->end > node->end)
493 node->end = next->end;
494 delete_node (rs, next);
498 /* Destroys range set RS.
499 Helper function for range_set_create_pool. */
501 destroy_pool (void *rs_)
503 struct range_set *rs = rs_;
505 range_set_destroy (rs);