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 /* Destroys range set RS. */
105 range_set_destroy (struct range_set *rs)
109 if (rs->pool != NULL)
110 pool_unregister (rs->pool, rs);
111 while (!range_set_is_empty (rs))
112 delete_node (rs, first_node (rs));
117 /* Inserts the region starting at START and extending for WIDTH
120 range_set_insert (struct range_set *rs,
121 unsigned long int start, unsigned long int width)
123 unsigned long int end = start + width;
124 struct range_set_node *node;
126 assert (width == 0 || start + width - 1 >= start);
131 /* Invalidate cache. */
134 node = find_node_le (rs, start);
137 if (start > node->end)
139 /* New region does not overlap NODE, but it might
140 overlap the next node. */
141 insert_just_before (rs, start, end, next_node (rs, node));
143 else if (end > node->end)
145 /* New region starts in the middle of NODE and
146 continues past its end, so extend NODE, then merge
147 it with any following node that it now potentially
150 merge_node_with_successors (rs, node);
154 /* New region is completely contained by NODE, so
155 there's nothing to do. */
160 /* New region starts before any existing region, but it
161 might overlap the first region. */
162 insert_just_before (rs, start, end, first_node (rs));
166 /* Inserts the region starting at START and extending for WIDTH
169 range_set_delete (struct range_set *rs,
170 unsigned long int start, unsigned long int width)
172 unsigned long int end = start + width;
173 struct range_set_node *node;
175 assert (width == 0 || start + width - 1 >= start);
180 /* Invalidate cache. */
183 node = find_node_le (rs, start);
185 node = first_node (rs);
187 while (node != NULL && end > node->start)
189 if (start <= node->start)
191 if (end >= node->end)
193 /* Region to delete covers entire node. */
194 node = delete_node_get_next (rs, node);
198 /* Region to delete covers only left part of node. */
203 else if (start < node->end)
207 /* Region to delete covers middle of the node, so
208 we have to split the node into two pieces. */
209 unsigned long int old_node_end = node->end;
211 insert_node (rs, end, old_node_end);
216 /* Region to delete covers only right part of
219 node = next_node (rs, node);
223 node = next_node (rs, node);
227 /* Scans RS for its first 1-bit and deletes up to REQUEST
228 contiguous 1-bits starting at that position. Unless RS is
229 completely empty, sets *START to the position of the first
230 1-bit deleted and *WIDTH to the number actually deleted, which
231 may be less than REQUEST if fewer contiguous 1-bits were
232 present, and returns true. If RS is completely empty, returns
235 range_set_allocate (struct range_set *rs, unsigned long int request,
236 unsigned long int *start, unsigned long int *width)
238 struct range_set_node *node;
239 unsigned long int node_width;
241 assert (request > 0);
243 node = first_node (rs);
246 node_width = node->end - node->start;
248 *start = node->start;
249 if (request < node_width)
252 node->start += request;
257 delete_node (rs, node);
265 /* Returns true if there is a 1-bit at the given POSITION in RS,
268 range_set_contains (const struct range_set *rs_, unsigned long int position)
270 struct range_set *rs = (struct range_set *) rs_;
271 if (position < rs->cache_end && position >= rs->cache_start)
272 return rs->cache_value;
275 struct range_set_node *node = find_node_le (rs, position);
278 if (position < node->end)
280 rs->cache_start = node->start;
281 rs->cache_end = node->end;
282 rs->cache_value = true;
287 struct range_set_node *next = next_node (rs, node);
288 rs->cache_start = node->end;
289 rs->cache_end = next != NULL ? next->start : ULONG_MAX;
290 rs->cache_value = false;
296 node = first_node (rs);
298 rs->cache_end = node != NULL ? node->start : ULONG_MAX;
299 rs->cache_value = false;
305 /* Returns true if RS contains no 1-bits, false otherwise. */
307 range_set_is_empty (const struct range_set *rs)
309 return bt_count (&rs->bt) == 0;
312 /* Returns the node representing the first contiguous region of
313 1-bits in RS, or a null pointer if RS is empty.
314 Any call to range_set_insert, range_set_delete, or
315 range_set_allocate invalidates the returned node. */
316 const struct range_set_node *
317 range_set_first (const struct range_set *rs)
319 return first_node (rs);
322 /* If NODE is nonnull, returns the node representing the next
323 contiguous region of 1-bits in RS following NODE, or a null
324 pointer if NODE is the last region in RS.
325 If NODE is null, returns the first region in RS, as for
327 Any call to range_set_insert, range_set_delete, or
328 range_set_allocate invalidates the returned node. */
329 const struct range_set_node *
330 range_set_next (const struct range_set *rs, const struct range_set_node *node)
333 ? next_node (rs, (struct range_set_node *) node)
337 /* Returns the position of the first 1-bit in NODE. */
339 range_set_node_get_start (const struct range_set_node *node)
344 /* Returns one past the position of the last 1-bit in NODE. */
346 range_set_node_get_end (const struct range_set_node *node)
351 /* Returns the number of contiguous 1-bits in NODE. */
353 range_set_node_get_width (const struct range_set_node *node)
355 return node->end - node->start;
358 /* Returns the range_set_node corresponding to the given
359 BT_NODE. Returns a null pointer if BT_NODE is null. */
360 static struct range_set_node *
361 bt_to_rs_node (const struct bt_node *bt_node)
363 return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
366 /* Compares `range_set_node's A and B and returns a strcmp-like
369 compare_range_set_nodes (const struct bt_node *a_,
370 const struct bt_node *b_,
371 const void *aux UNUSED)
373 const struct range_set_node *a = bt_to_rs_node (a_);
374 const struct range_set_node *b = bt_to_rs_node (b_);
376 return a->start < b->start ? -1 : a->start > b->start;
379 /* Returns the first range_set_node in RS,
380 or a null pointer if RS is empty. */
381 static struct range_set_node *
382 first_node (const struct range_set *rs)
384 return bt_to_rs_node (bt_first (&rs->bt));
387 /* Returns the next range_set_node in RS after NODE,
388 or a null pointer if NODE is the last node in RS. */
389 static struct range_set_node *
390 next_node (const struct range_set *rs, const struct range_set_node *node)
392 return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
395 /* Deletes NODE from RS and frees it. */
397 delete_node (struct range_set *rs, struct range_set_node *node)
399 bt_delete (&rs->bt, &node->bt_node);
403 /* Deletes NODE from RS, frees it, and returns the following
405 static struct range_set_node *
406 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
408 struct range_set_node *next = next_node (rs, node);
409 delete_node (rs, node);
413 /* Returns the node in RS that would be just before POSITION if a
414 range_set_node with `start' as POSITION were inserted.
415 Returns a null pointer if POSITION is before any existing node
416 in RS. If POSITION would duplicate an existing region's
417 start, returns that region. */
418 static struct range_set_node *
419 find_node_le (const struct range_set *rs, unsigned long int position)
421 struct range_set_node tmp;
422 tmp.start = position;
423 return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
426 /* Creates a new region with the given START and END, inserts the
427 region into RS, and returns the new region. */
428 static struct range_set_node *
429 insert_node (struct range_set *rs,
430 unsigned long int start, unsigned long int end)
432 struct range_set_node *node = xmalloc (sizeof *node);
433 struct bt_node *dummy;
436 dummy = bt_insert (&rs->bt, &node->bt_node);
437 assert (dummy == NULL);
441 /* Inserts the region START...END (exclusive) into RS given that
442 the new region is "just before" NODE, that is, if NODE is
443 nonnull, the new region is known not to overlap any node
444 preceding NODE, and START precedes NODE's start; if NODE is
445 null, then the new region is known to follow any and all
446 regions already in RS. */
448 insert_just_before (struct range_set *rs,
449 unsigned long int start, unsigned long int end,
450 struct range_set_node *node)
452 assert (node == NULL || start < node->start);
453 if (node != NULL && end >= node->start)
455 /* New region overlaps NODE, so just extend NODE. */
460 merge_node_with_successors (rs, node);
465 /* New region does not overlap NODE. */
466 insert_node (rs, start, end);
470 /* Merges NODE in RS with its successors. */
472 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
474 struct range_set_node *next;
476 while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
478 if (next->end > node->end)
479 node->end = next->end;
480 delete_node (rs, next);
484 /* Destroys range set RS.
485 Helper function for range_set_create_pool. */
487 destroy_pool (void *rs_)
489 struct range_set *rs = rs_;
491 range_set_destroy (rs);