gui: Fix behavior of print preview in psppire-output-window.
[pspp] / src / libpspp / range-set.c
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 *
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 *
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 *
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
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
109 range_set_insert (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
158 range_set_delete (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
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
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
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
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 \f
359 /* Compares `range_set_node's A and B and returns a strcmp-like
360    return value. */
361 static int
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
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 *
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 *
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 *
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
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
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
465 destroy_pool (void *rs_)
466 {
467   struct range_set *rs = rs_;
468   rs->pool = NULL;
469   range_set_destroy (rs);
470 }