Remove LIB_CLOSE variables from linker options.
[pspp] / src / libpspp / range-set.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 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/bt.h>
33 #include <libpspp/compiler.h>
34 #include <libpspp/pool.h>
35
36 #include "xalloc.h"
37
38 /* A set of ranges. */
39 struct range_set
40   {
41     struct pool *pool;                  /* Pool for freeing range_set. */
42     struct bt bt;                       /* Tree of range_set_nodes. */
43
44     /* Cache. */
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? */
48   };
49
50 /* A node in the range set. */
51 struct range_set_node
52   {
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. */
56   };
57
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 *,
61                                     const void *aux);
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 *);
79
80 /* Creates and returns a new, empty range set. */
81 struct range_set *
82 range_set_create (void)
83 {
84   return range_set_create_pool (NULL);
85 }
86
87 /* Creates and returns a new, empty range set in the given
88    POOL. */
89 struct range_set *
90 range_set_create_pool (struct pool *pool)
91 {
92   struct range_set *rs = xmalloc (sizeof *rs);
93   rs->pool = pool;
94   if (pool != NULL)
95     pool_register (pool, destroy_pool, rs);
96   bt_init (&rs->bt, compare_range_set_nodes, NULL);
97   rs->cache_end = 0;
98   return rs;
99 }
100
101 /* Creates and returns a clone of OLD range set in the given POOL
102    (which may be null). */
103 struct range_set *
104 range_set_clone (const struct range_set *old, struct pool *pool)
105 {
106   struct range_set *new;
107   struct range_set_node *node;
108
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);
112   return new;
113 }
114
115 /* Destroys range set RS. */
116 void
117 range_set_destroy (struct range_set *rs)
118 {
119   if (rs != NULL)
120     {
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));
125       free (rs);
126     }
127 }
128
129 /* Inserts the region starting at START and extending for WIDTH
130    into RS. */
131 void
132 range_set_insert (struct range_set *rs,
133                   unsigned long int start, unsigned long int width)
134 {
135   unsigned long int end = start + width;
136   struct range_set_node *node;
137
138   assert (width == 0 || start + width - 1 >= start);
139
140   if (width == 0)
141     return;
142
143   /* Invalidate cache. */
144   rs->cache_end = 0;
145
146   node = find_node_le (rs, start);
147   if (node != NULL)
148     {
149       if (start > node->end)
150         {
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));
154         }
155       else if (end > node->end)
156         {
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
160              overlaps. */
161           node->end = end;
162           merge_node_with_successors (rs, node);
163         }
164       else
165         {
166           /* New region is completely contained by NODE, so
167              there's nothing to do. */
168         }
169     }
170   else
171     {
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));
175     }
176 }
177
178 /* Inserts the region starting at START and extending for WIDTH
179    from RS. */
180 void
181 range_set_delete (struct range_set *rs,
182                   unsigned long int start, unsigned long int width)
183 {
184   unsigned long int end = start + width;
185   struct range_set_node *node;
186
187   assert (width == 0 || start + width - 1 >= start);
188
189   if (width == 0)
190     return;
191
192   /* Invalidate cache. */
193   rs->cache_end = 0;
194
195   node = find_node_le (rs, start);
196   if (node == NULL)
197     node = first_node (rs);
198
199   while (node != NULL && end > node->start)
200     {
201       if (start <= node->start)
202         {
203           if (end >= node->end)
204             {
205               /* Region to delete covers entire node. */
206               node = delete_node_get_next (rs, node);
207             }
208           else
209             {
210               /* Region to delete covers only left part of node. */
211               node->start = end;
212               break;
213             }
214         }
215       else if (start < node->end)
216         {
217           if (end < node->end)
218             {
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;
222               node->end = start;
223               insert_node (rs, end, old_node_end);
224               break;
225             }
226           else
227             {
228               /* Region to delete covers only right part of
229                  node. */
230               node->end = start;
231               node = next_node (rs, node);
232             }
233         }
234       else
235         node = next_node (rs, node);
236     }
237 }
238
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
245    false. */
246 bool
247 range_set_allocate (struct range_set *rs, unsigned long int request,
248                     unsigned long int *start, unsigned long int *width)
249 {
250   struct range_set_node *node;
251   unsigned long int node_width;
252
253   assert (request > 0);
254
255   node = first_node (rs);
256   if (node == NULL)
257     return false;
258   node_width = node->end - node->start;
259
260   *start = node->start;
261   if (request < node_width)
262     {
263       *width = request;
264       node->start += request;
265     }
266   else
267     {
268       *width = node_width;
269       delete_node (rs, node);
270     }
271
272   rs->cache_end = 0;
273
274   return true;
275 }
276
277 /* Returns true if there is a 1-bit at the given POSITION in RS,
278    false otherwise. */
279 bool
280 range_set_contains (const struct range_set *rs_, unsigned long int position)
281 {
282   struct range_set *rs = (struct range_set *) rs_;
283   if (position < rs->cache_end && position >= rs->cache_start)
284     return rs->cache_value;
285   else
286     {
287       struct range_set_node *node = find_node_le (rs, position);
288       if (node != NULL)
289         {
290           if (position < node->end)
291             {
292               rs->cache_start = node->start;
293               rs->cache_end = node->end;
294               rs->cache_value = true;
295               return true;
296             }
297           else
298             {
299               struct range_set_node *next = next_node (rs, node);
300               rs->cache_start = node->end;
301               rs->cache_end = next != NULL ? next->start : ULONG_MAX;
302               rs->cache_value = false;
303               return false;
304             }
305         }
306       else
307         {
308           node = first_node (rs);
309           rs->cache_start = 0;
310           rs->cache_end = node != NULL ? node->start : ULONG_MAX;
311           rs->cache_value = false;
312           return false;
313         }
314     }
315 }
316
317 /* Returns true if RS contains no 1-bits, false otherwise. */
318 bool
319 range_set_is_empty (const struct range_set *rs)
320 {
321   return bt_count (&rs->bt) == 0;
322 }
323
324 /* Returns the node representing the first contiguous region of
325    1-bits in RS, or a null pointer if RS is empty.
326    Any call to range_set_insert, range_set_delete, or
327    range_set_allocate invalidates the returned node. */
328 const struct range_set_node *
329 range_set_first (const struct range_set *rs)
330 {
331   return first_node (rs);
332 }
333
334 /* If NODE is nonnull, returns the node representing the next
335    contiguous region of 1-bits in RS following NODE, or a null
336    pointer if NODE is the last region in RS.
337    If NODE is null, returns the first region in RS, as for
338    range_set_first.
339    Any call to range_set_insert, range_set_delete, or
340    range_set_allocate invalidates the returned node. */
341 const struct range_set_node *
342 range_set_next (const struct range_set *rs, const struct range_set_node *node)
343 {
344   return (node != NULL
345           ? next_node (rs, (struct range_set_node *) node)
346           : first_node (rs));
347 }
348
349 /* Returns the position of the first 1-bit in NODE. */
350 unsigned long int
351 range_set_node_get_start (const struct range_set_node *node)
352 {
353   return node->start;
354 }
355
356 /* Returns one past the position of the last 1-bit in NODE. */
357 unsigned long int
358 range_set_node_get_end (const struct range_set_node *node)
359 {
360   return node->end;
361 }
362
363 /* Returns the number of contiguous 1-bits in NODE. */
364 unsigned long int
365 range_set_node_get_width (const struct range_set_node *node)
366 {
367   return node->end - node->start;
368 }
369 \f
370 /* Returns the range_set_node corresponding to the given
371    BT_NODE.  Returns a null pointer if BT_NODE is null. */
372 static struct range_set_node *
373 bt_to_rs_node (const struct bt_node *bt_node)
374 {
375   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
376 }
377
378 /* Compares `range_set_node's A and B and returns a strcmp-like
379    return value. */
380 static int
381 compare_range_set_nodes (const struct bt_node *a_,
382                          const struct bt_node *b_,
383                          const void *aux UNUSED)
384 {
385   const struct range_set_node *a = bt_to_rs_node (a_);
386   const struct range_set_node *b = bt_to_rs_node (b_);
387
388   return a->start < b->start ? -1 : a->start > b->start;
389 }
390
391 /* Returns the first range_set_node in RS,
392    or a null pointer if RS is empty. */
393 static struct range_set_node *
394 first_node (const struct range_set *rs)
395 {
396   return bt_to_rs_node (bt_first (&rs->bt));
397 }
398
399 /* Returns the next range_set_node in RS after NODE,
400    or a null pointer if NODE is the last node in RS. */
401 static struct range_set_node *
402 next_node (const struct range_set *rs, const struct range_set_node *node)
403 {
404   return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
405 }
406
407 /* Deletes NODE from RS and frees it. */
408 static void
409 delete_node (struct range_set *rs, struct range_set_node *node)
410 {
411   bt_delete (&rs->bt, &node->bt_node);
412   free (node);
413 }
414
415 /* Deletes NODE from RS, frees it, and returns the following
416    node. */
417 static struct range_set_node *
418 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
419 {
420   struct range_set_node *next = next_node (rs, node);
421   delete_node (rs, node);
422   return next;
423 }
424
425 /* Returns the node in RS that would be just before POSITION if a
426    range_set_node with `start' as POSITION were inserted.
427    Returns a null pointer if POSITION is before any existing node
428    in RS.  If POSITION would duplicate an existing region's
429    start, returns that region. */
430 static struct range_set_node *
431 find_node_le (const struct range_set *rs, unsigned long int position)
432 {
433   struct range_set_node tmp;
434   tmp.start = position;
435   return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
436 }
437
438 /* Creates a new region with the given START and END, inserts the
439    region into RS, and returns the new region. */
440 static struct range_set_node *
441 insert_node (struct range_set *rs,
442              unsigned long int start, unsigned long int end)
443 {
444   struct range_set_node *node = xmalloc (sizeof *node);
445   struct bt_node *dummy;
446   node->start = start;
447   node->end = end;
448   dummy = bt_insert (&rs->bt, &node->bt_node);
449   assert (dummy == NULL);
450   return node;
451 }
452
453 /* Inserts the region START...END (exclusive) into RS given that
454    the new region is "just before" NODE, that is, if NODE is
455    nonnull, the new region is known not to overlap any node
456    preceding NODE, and START precedes NODE's start; if NODE is
457    null, then the new region is known to follow any and all
458    regions already in RS. */
459 static void
460 insert_just_before (struct range_set *rs,
461                     unsigned long int start, unsigned long int end,
462                     struct range_set_node *node)
463 {
464   assert (node == NULL || start < node->start);
465   if (node != NULL && end >= node->start)
466     {
467       /* New region overlaps NODE, so just extend NODE. */
468       node->start = start;
469       if (end > node->end)
470         {
471           node->end = end;
472           merge_node_with_successors (rs, node);
473         }
474     }
475   else
476     {
477       /* New region does not overlap NODE. */
478       insert_node (rs, start, end);
479     }
480 }
481
482 /* Merges NODE in RS with its successors. */
483 static void
484 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
485 {
486   struct range_set_node *next;
487
488   while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
489     {
490       if (next->end > node->end)
491         node->end = next->end;
492       delete_node (rs, next);
493     }
494 }
495
496 /* Destroys range set RS.
497    Helper function for range_set_create_pool. */
498 static void
499 destroy_pool (void *rs_)
500 {
501   struct range_set *rs = rs_;
502   rs->pool = NULL;
503   range_set_destroy (rs);
504 }