New Slovenian localisation from http://translationproject.org
[pspp] / src / libpspp / range-tower.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-tower-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-tower.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 void reaugment_range_tower_node (struct abt_node *, const void *aux);
39 static void delete_node (struct range_tower *, struct range_tower_node *);
40
41 static void destroy_pool (void *);
42
43 static void
44 print_structure (const struct abt_node *node_)
45 {
46   struct range_tower_node *node;
47
48   if (node_ == NULL)
49     return;
50   node = abt_data (node_, struct range_tower_node, abt_node);
51   printf ("%lu+%lu/%d", node->n_zeros, node->n_ones, node->abt_node.level);
52   if (node->abt_node.down[0] || node->abt_node.down[1])
53     {
54       printf ("(");
55       print_structure (node->abt_node.down[0]);
56       printf (",");
57       print_structure (node->abt_node.down[1]);
58       printf (")");
59     }
60 }
61
62 /* Prints the regions in RT to stdout. */
63 static void UNUSED
64 print_regions (const char *title, const struct range_tower *rt)
65 {
66   const struct range_tower_node *node;
67
68   printf ("%s:", title);
69   for (node = range_tower_first__ (rt); node != NULL;
70        node = range_tower_next__ (rt, node))
71     printf (" (%lu,%lu)", node->n_zeros, node->n_ones);
72   printf ("\n");
73   printf ("structure:");
74   print_structure (rt->abt.root);
75   printf ("\n");
76 }
77
78 static struct range_tower_node *
79 range_tower_node_from_abt_node (const struct abt_node *abt_node)
80 {
81   return abt_data (abt_node, struct range_tower_node, abt_node);
82 }
83
84 /* Returns the total width (zeros and ones) of the nodes in the subtree rooted
85    at P, or 0 if P is null. */
86 static unsigned long int
87 subtree_width (const struct abt_node *p)
88 {
89   return p != NULL ? range_tower_node_from_abt_node (p)->subtree_width : 0;
90 }
91
92 /* Returns the position of the first 1-bit in NODE.
93
94    The performance of this function is O(lg n) in the number of nodes in the
95    range tower.  It is often possible to avoid calling this function, either by
96    taking advantage of the NODE_START parameter to tower_lookup or by
97    incrementally keeping track of height while iterating through a tower.  In
98    the former case the asymptotic performance is no different, since
99    tower_lookup is also O(lg n), but in the latter case performance improves
100    from O(lg n) to O(1). */
101 unsigned long int
102 range_tower_node_get_start (const struct range_tower_node *node)
103 {
104   const struct abt_node *p = &node->abt_node;
105   unsigned long start = subtree_width (p->down[0]) + range_tower_node_from_abt_node (p)->n_zeros;
106   while (p->up != NULL)
107     {
108       if (p == p->up->down[1])
109         {
110           const struct range_tower_node *up
111             = range_tower_node_from_abt_node (p->up);
112           start += subtree_width (p->up->down[0]) + up->n_zeros + up->n_ones;
113         }
114       p = p->up;
115     }
116   return start;
117 }
118
119 /* Returns one past the position of the last 1-bit in NODE.
120
121    Like range_tower_node_get_start(), the performance of this function is O(lg
122    n) in the number of nodes in the range tower. */
123 unsigned long int
124 range_tower_node_get_end (const struct range_tower_node *node)
125 {
126   return range_tower_node_get_start (node) + node->n_ones;
127 }
128
129 /* Creates and returns a new, empty range tower. */
130 struct range_tower *
131 range_tower_create (void)
132 {
133   return range_tower_create_pool (NULL);
134 }
135
136 static struct range_tower *
137 range_tower_create_pool__ (struct pool *pool)
138 {
139   struct range_tower *rt = xmalloc (sizeof *rt);
140
141   rt->pool = pool;
142   if (pool != NULL)
143     pool_register (pool, destroy_pool, rt);
144
145   abt_init (&rt->abt, NULL, reaugment_range_tower_node, NULL);
146   rt->cache_end = 0;
147
148   return rt;
149 }
150
151 /* Creates and returns a new, empty range tower in the given POOL. */
152 struct range_tower *
153 range_tower_create_pool (struct pool *pool)
154 {
155   struct range_tower_node *node;
156   struct range_tower *rt;
157
158   rt = range_tower_create_pool__ (pool);
159
160   node = xmalloc (sizeof *node);
161   node->n_zeros = ULONG_MAX;
162   node->n_ones = 0;
163   abt_insert_after (&rt->abt, NULL, &node->abt_node);
164
165   return rt;
166 }
167
168 /* Creates and returns a clone of OLD range tower in the given POOL
169    (which may be null). */
170 struct range_tower *
171 range_tower_clone (const struct range_tower *old, struct pool *pool)
172 {
173   const struct range_tower_node *old_node;
174   struct abt_node *prev_node;
175   struct range_tower *new;
176
177   new = range_tower_create_pool__ (pool);
178   prev_node = NULL;
179   for (old_node = range_tower_first__ (old); old_node != NULL;
180        old_node = range_tower_next__ (old, old_node))
181     {
182       struct range_tower_node *new_node;
183
184       new_node = xmalloc (sizeof *new_node);
185       new_node->n_zeros = old_node->n_zeros;
186       new_node->n_ones = old_node->n_ones;
187
188       abt_insert_after (&new->abt, prev_node, &new_node->abt_node);
189       prev_node = &new_node->abt_node;
190     }
191   return new;
192 }
193
194 /* Destroys range tower RT. */
195 void
196 range_tower_destroy (struct range_tower *rt)
197 {
198   if (rt != NULL)
199     {
200       if (rt->pool != NULL)
201         pool_unregister (rt->pool, rt);
202       while (!abt_is_empty (&rt->abt))
203         delete_node (rt, range_tower_first__ (rt));
204       free (rt);
205     }
206 }
207
208 /* Sets the WIDTH bits starting at START in RT to 1-bits. */
209 void
210 range_tower_set1 (struct range_tower *rt,
211                     unsigned long int start, unsigned long int width)
212 {
213   struct range_tower_node *node;
214   unsigned long int node_start;
215
216   assert (width == 0 || start + width - 1 >= start);
217
218   node = range_tower_lookup (rt, start, &node_start);
219   while (width > 0)
220     {
221       unsigned long int node_ofs = start - node_start;
222
223       if (node_ofs >= node->n_zeros)
224         {
225           /* There are already some 1-bits here, so skip them. */
226           unsigned long ones_left = (node->n_zeros + node->n_ones) - node_ofs;
227           if (width <= ones_left)
228             return;
229
230           start += ones_left;
231           width -= ones_left;
232           node_start += node->n_zeros + node->n_ones;
233           node_ofs = 0;
234           node = range_tower_next__ (rt, node);
235         }
236
237       /* Invalidate cache. */
238       rt->cache_end = 0;
239
240       if (node_ofs == 0)
241         {
242           if (node_start > 0)
243             {
244               struct range_tower_node *prev = range_tower_prev__ (rt, node);
245               if (width >= node->n_zeros)
246                 {
247                   /* All zeros in NODE are replaced by ones.  Change NODE's
248                      entire width into PREV's trailing ones, e.g. 00001111
249                      00001111 becomes 0000111111111111. */
250                   int node_width = node->n_zeros + node->n_ones;
251                   abt_delete (&rt->abt, &node->abt_node);
252                   prev->n_ones += node_width;
253                   abt_reaugmented (&rt->abt, &prev->abt_node);
254                   if (width <= node_width)
255                     return;
256
257                   /* Go around again with NODE replaced by PREV's new
258                      successor. */
259                   width -= node_width;
260                   start += node_width;
261                   node = range_tower_next__ (rt, prev);
262                   node_start += node_width;
263                 }
264               else
265                 {
266                   /* Leading zeros in NODE change into trailing ones in PREV,
267                      but trailing zeros in NODE remain, e.g. 00001111 00001111
268                      becomes 0000111111 001111.  */
269                   node->n_zeros -= width;
270                   abt_reaugmented (&rt->abt, &node->abt_node);
271
272                   prev->n_ones += width;
273                   abt_reaugmented (&rt->abt, &prev->abt_node);
274                   return;
275                 }
276             }
277           else
278             {
279               if (width >= node->n_zeros)
280                 {
281                   /* All zeros in NODE are replaced by ones, e.g. 00001111
282                      becomes 11111111. */
283                   node->n_ones += node->n_zeros;
284                   node->n_zeros = 0;
285                   if (width <= node->n_ones)
286                     return;
287
288                   start += node->n_ones;
289                   node_start += node->n_ones;
290                   width -= node->n_ones;
291                   node = range_tower_next__ (rt, node);
292                 }
293               else
294                 {
295                   /* Leading zeros in NODE (which starts at offset 0) are
296                      replaced by ones, but some zeros remain.  This requires a
297                      node split, e.g. 00001111 becomes 11 001111. */
298                   struct range_tower_node *new_node;
299
300                   node->n_zeros -= width;
301                   abt_reaugmented (&rt->abt, &node->abt_node);
302
303                   new_node = xmalloc (sizeof *new_node);
304                   new_node->n_zeros = 0;
305                   new_node->n_ones = width;
306                   abt_insert_before (&rt->abt, &node->abt_node,
307                                      &new_node->abt_node);
308                   return;
309                 }
310             }
311         }
312       else
313         {
314           unsigned long int zeros_left = node->n_zeros - node_ofs;
315           if (width >= zeros_left)
316             {
317               /* Trailing zeros in NODE are replaced by ones, but leading
318                  zeros remain, e.g. 00001111 becomes 00111111. */
319               node->n_zeros -= zeros_left;
320               node->n_ones += zeros_left;
321               if (width <= node->n_ones)
322                 return;
323               start += node->n_ones;
324               width -= node->n_ones;
325               node_start += node->n_zeros + node->n_ones;
326               node = range_tower_next__ (rt, node);
327             }
328           else
329             {
330               /* Zeros that are neither leading or trailing turn into ones.
331                  Split the node into two nodes, e.g. 00001111 becomes 011
332                  01111.  */
333               struct range_tower_node *new_node;
334
335               new_node = xmalloc (sizeof *new_node);
336               new_node->n_ones = node->n_ones;
337               new_node->n_zeros = zeros_left - width;
338
339               node->n_zeros = node_ofs;
340               node->n_ones = width;
341               abt_reaugmented (&rt->abt, &node->abt_node);
342
343               abt_insert_after (&rt->abt, &node->abt_node,
344                                 &new_node->abt_node);
345               return;
346             }
347         }
348     }
349 }
350
351 /* Sets the WIDTH bits starting at START in RT to 0-bits. */
352 void
353 range_tower_set0 (struct range_tower *rt,
354                     unsigned long int start, unsigned long int width)
355 {
356   struct range_tower_node *node;
357   unsigned long int node_start;
358
359   assert (width == 0 || start + width - 1 >= start);
360
361   node = range_tower_lookup (rt, start, &node_start);
362   while (width > 0)
363     {
364       unsigned long int node_ofs = start - node_start;
365
366       if (node_ofs < node->n_zeros)
367         {
368           /* Deleting zeros is a no-op, so skip them. */
369           unsigned long zeros_left = node->n_zeros - node_ofs;
370           if (zeros_left >= width)
371             {
372               /* We are deleting only existing zeros.  Nothing to do. */
373               return;
374             }
375
376           width -= zeros_left;
377           start += zeros_left;
378           node_ofs = node->n_zeros;
379         }
380
381       rt->cache_end = 0;
382
383       if (node_ofs == node->n_zeros)
384         {
385           if (node->n_ones > width)
386             {
387               /* DELTA leading ones within NODE turn into zeros, but some ones
388                  remain, e.g. 00001111 becomes 00111111.  No reaugmentation
389                  because n_zeros + n_ones doesn't change. */
390               node->n_zeros += width;
391               node->n_ones -= width;
392               return;
393             }
394           else
395             {
396               /* All ones in NODE turn into zeros, so merge NODE with the
397                  following node, e.g. 00001111 00001111 becomes
398                  0000000000001111, and then do it again with the merged
399                  node. */
400               unsigned long int next_zeros, next_ones;
401               struct range_tower_node *next;
402
403               next = range_tower_next__ (rt, node);
404               if (next == NULL)
405                 {
406                   node->n_zeros += node->n_ones;
407                   node->n_ones = 0;
408                   return;
409                 }
410
411               next_zeros = next->n_zeros;
412               next_ones = next->n_ones;
413               abt_delete (&rt->abt, &next->abt_node);
414
415               node->n_zeros += node->n_ones + next_zeros;
416               node->n_ones = next_ones;
417               abt_reaugmented (&rt->abt, &node->abt_node);
418             }
419         }
420       else if (node_ofs + width >= node->n_zeros + node->n_ones)
421         {
422           /* Trailing ones in NODE turn into zeros, but leading ones remain,
423              e.g. 000011{11} 00001111 becomes 000011 {00}00001111.  Give the
424              trailing ones to the next node as zeros and go around again with
425              the next node. */
426           struct range_tower_node *next;
427           unsigned long int delta;
428
429           delta = node->n_ones - (node_ofs - node->n_zeros);
430           node->n_ones -= delta;
431           abt_reaugmented (&rt->abt, &node->abt_node);
432
433           next = range_tower_next__ (rt, node);
434           if (next == NULL)
435             {
436               struct range_tower_node *new_node;
437
438               new_node = xmalloc (sizeof *new_node);
439               new_node->n_zeros = delta;
440               new_node->n_ones = 0;
441
442               abt_insert_before (&rt->abt, NULL, &new_node->abt_node);
443               return;
444             }
445
446           next->n_zeros += delta;
447           abt_reaugmented (&rt->abt, &next->abt_node);
448
449           node_start += node->n_zeros + node->n_ones;
450           start = node_start;
451           node = next;
452         }
453       else
454         {
455           /* Ones that are neither leading or trailing turn into zeros,
456              e.g. 00001111 becomes 00001 001.  Split the node into two nodes
457              and we're done. */
458           unsigned long int end = start + width;
459           struct range_tower_node *new_node;
460
461           new_node = xmalloc (sizeof *new_node);
462           new_node->n_zeros = width;
463           new_node->n_ones = (node_start + node->n_zeros + node->n_ones) - end;
464
465           node->n_ones = node_ofs - node->n_zeros;
466           abt_reaugmented (&rt->abt, &node->abt_node);
467
468           abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
469           return;
470         }
471     }
472 }
473
474 static void
475 range_tower_delete__ (struct range_tower *rt,
476                       unsigned long int start, unsigned long int width)
477 {
478   struct range_tower_node *node;
479   unsigned long int node_start;
480
481   rt->cache_end = 0;
482   node = range_tower_lookup (rt, start, &node_start);
483   for (;;)
484     {
485       unsigned long int node_ofs = start - node_start;
486
487       if (node_ofs < node->n_zeros)
488         {
489           if (node_ofs + width < node->n_zeros)
490             {
491               node->n_zeros -= width;
492               abt_reaugmented (&rt->abt, &node->abt_node);
493               break;
494             }
495           else if (node_ofs > 0)
496             {
497               width -= node->n_zeros - node_ofs;
498               node->n_zeros = node_ofs;
499               abt_reaugmented (&rt->abt, &node->abt_node);
500               if (width == 0)
501                 break;
502               /* Continue with 1-bits. */
503             }
504           else if (width < node->n_zeros + node->n_ones)
505             {
506               struct range_tower_node *prev = range_tower_prev__ (rt, node);
507               unsigned long int ones_left;
508
509               ones_left = (node->n_zeros + node->n_ones) - width;
510               if (prev != NULL)
511                 {
512                   abt_delete (&rt->abt, &node->abt_node);
513                   prev->n_ones += ones_left;
514                   abt_reaugmented (&rt->abt, &prev->abt_node);
515                 }
516               else
517                 {
518                   node->n_zeros = 0;
519                   node->n_ones = ones_left;
520                   abt_reaugmented (&rt->abt, &node->abt_node);
521                 }
522               break;
523             }
524           else
525             {
526               /* Delete entire node. */
527               struct range_tower_node *next = range_tower_next__ (rt, node);
528
529               width -= node->n_zeros + node->n_ones;
530               abt_delete (&rt->abt, &node->abt_node);
531               if (next == NULL)
532                 break;
533
534               node = next;
535               continue;
536             }
537         }
538
539       if (node_ofs + width < node->n_zeros + node->n_ones)
540         {
541           node->n_ones -= width;
542           abt_reaugmented (&rt->abt, &node->abt_node);
543           break;
544         }
545       else if (node_ofs > node->n_zeros)
546         {
547           unsigned long int ones_ofs = node_ofs - node->n_zeros;
548           width -= node->n_ones - ones_ofs;
549           node->n_ones = ones_ofs;
550           abt_reaugmented (&rt->abt, &node->abt_node);
551           if (width == 0)
552             break;
553           /* continue with next node */
554           node_start += node->n_zeros + node->n_ones;
555           node = range_tower_next__ (rt, node);
556         }
557       else
558         {
559           /* Merge with next node */
560           struct range_tower_node *next = range_tower_next__ (rt, node);
561           if (next != NULL)
562             {
563               unsigned long int next_zeros = next->n_zeros;
564               unsigned long int next_ones = next->n_ones;
565
566               abt_delete (&rt->abt, &next->abt_node);
567
568               width -= node->n_ones;
569
570               node->n_zeros += next_zeros;
571               node->n_ones = next_ones;
572               abt_reaugmented (&rt->abt, &node->abt_node);
573
574               if (width == 0)
575                 break;
576             }
577           else
578             {
579               node->n_ones = 0;
580               abt_reaugmented (&rt->abt, &node->abt_node);
581               break;
582             }
583         }
584     }
585 }
586
587 void
588 range_tower_delete (struct range_tower *rt,
589                     unsigned long int start, unsigned long int width)
590 {
591   struct range_tower_node *node;
592
593   if (width == 0)
594     return;
595
596   assert (start + width - 1 >= start);
597
598   range_tower_delete__ (rt, start, width);
599
600   node = range_tower_last__ (rt);
601   if (node != NULL && node->n_ones == 0)
602     {
603       node->n_zeros += width;
604       abt_reaugmented (&rt->abt, &node->abt_node);
605     }
606   else
607     {
608       struct range_tower_node *new_node;
609
610       new_node = xmalloc (sizeof *new_node);
611       new_node->n_zeros = width;
612       new_node->n_ones = 0;
613
614       abt_insert_before (&rt->abt, NULL, &new_node->abt_node);
615     }
616 }
617
618 static struct range_tower_node *
619 range_tower_insert0__ (struct range_tower *rt, struct range_tower_node *node,
620                        unsigned long int *node_startp,
621                        unsigned long int start, unsigned long int width)
622 {
623   unsigned long int node_ofs = start - *node_startp;
624
625   if (node_ofs <= node->n_zeros)
626     {
627       /* 00+00+001111 => 0000001111. */
628       node->n_zeros += width;
629       abt_reaugmented (&rt->abt, &node->abt_node);
630
631       return node;
632     }
633   else
634     {
635       /* 000011+00+11 => 000011 0011. */
636       struct range_tower_node *new_node;
637
638       new_node = xmalloc (sizeof *new_node);
639       new_node->n_zeros = width;
640       new_node->n_ones = node->n_zeros + node->n_ones - node_ofs;
641
642       node->n_ones -= new_node->n_ones;
643       abt_reaugmented (&rt->abt, &node->abt_node);
644       abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
645
646       *node_startp += node->n_zeros + node->n_ones;
647       return new_node;
648     }
649 }
650
651 void
652 range_tower_insert0 (struct range_tower *rt,
653                      unsigned long int start, unsigned long int width)
654 {
655   if (width == 0)
656     return;
657
658   assert (width == 0 || start + width - 1 >= start);
659
660   if (start + width == ULONG_MAX)
661     range_tower_set0 (rt, start, width);
662   else
663     {
664       struct range_tower_node *node;
665       unsigned long int node_start;
666
667       range_tower_delete__ (rt, ULONG_MAX - width, width);
668
669       node = range_tower_lookup (rt, start, &node_start);
670       range_tower_insert0__ (rt, node, &node_start, start, width);
671     }
672 }
673
674 static struct range_tower_node *
675 range_tower_insert1__ (struct range_tower *rt, struct range_tower_node *node,
676                        unsigned long int *node_startp,
677                        unsigned long int start, unsigned long int width)
678 {
679
680   unsigned long int node_start = *node_startp;
681   unsigned long int node_ofs = start - node_start;
682
683   if (node_ofs >= node->n_zeros)
684     {
685       node->n_ones += width;
686       abt_reaugmented (&rt->abt, &node->abt_node);
687       return node;
688     }
689   else if (node_ofs == 0 && node_start > 0)
690     {
691       struct range_tower_node *prev = range_tower_prev__ (rt, node);
692
693       prev->n_ones += width;
694       abt_reaugmented (&rt->abt, &prev->abt_node);
695
696       *node_startp += width;
697       return node;
698     }
699   else
700     {
701       /* 00001111 => 0+11+0001111 => 011 0001111 */
702       struct range_tower_node *new_node;
703
704       new_node = xmalloc (sizeof *new_node);
705       new_node->n_zeros = node->n_zeros - node_ofs;
706       new_node->n_ones = node->n_ones;
707
708       node->n_zeros = node_ofs;
709       node->n_ones = width;
710       abt_reaugmented (&rt->abt, &node->abt_node);
711
712       abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
713
714       *node_startp += node->n_zeros + node->n_ones;
715       return new_node;
716     }
717 }
718
719 void
720 range_tower_insert1 (struct range_tower *rt,
721                      unsigned long int start, unsigned long int width)
722 {
723   struct range_tower_node *node;
724   unsigned long int node_start;
725
726   if (width == 0)
727     return;
728
729   range_tower_delete__ (rt, ULONG_MAX - width, width);
730
731   assert (width == 0 || start + width - 1 >= start);
732
733   node = range_tower_lookup (rt, start, &node_start);
734   range_tower_insert1__ (rt, node, &node_start, start, width);
735 }
736
737 void
738 range_tower_move (struct range_tower *rt,
739                   unsigned long int old_start,
740                   unsigned long int new_start,
741                   unsigned long int width)
742 {
743   unsigned long int node_start;
744   int i;
745
746   if (width == 0 || old_start == new_start)
747     return;
748
749   assert (old_start + width - 1 >= old_start);
750   assert (new_start + width - 1 >= new_start);
751
752   i = 0;
753   do
754     {
755       struct range_tower_node *node;
756       unsigned long int node_ofs;
757       unsigned long int zeros, ones;
758
759       node = range_tower_lookup (rt, old_start, &node_start);
760       node_ofs = old_start - node_start;
761
762       if (node_ofs >= node->n_zeros)
763         {
764           unsigned long int max_ones;
765
766           zeros = 0;
767           max_ones = (node->n_zeros + node->n_ones) - node_ofs;
768           ones = MIN (width, max_ones);
769         }
770       else
771         {
772           unsigned long int max_zeros;
773
774           max_zeros = node->n_zeros - node_ofs;
775           zeros = MIN (width, max_zeros);
776           if (zeros < width)
777             ones = MIN (width - zeros, node->n_ones);
778           else
779             ones = 0;
780         }
781
782       node->n_zeros -= zeros;
783       node->n_ones -= ones;
784       abt_reaugmented (&rt->abt, &node->abt_node);
785
786       if (node->n_zeros == 0)
787         {
788           if (node->n_ones == 0)
789             abt_delete (&rt->abt, &node->abt_node);
790           else if (node_start > 0)
791             {
792               /* Merge with previous. */
793               unsigned long int n_ones = node->n_ones;
794               struct range_tower_node *prev = range_tower_prev__ (rt, node);
795
796               abt_delete (&rt->abt, &node->abt_node);
797               prev->n_ones += n_ones;
798               abt_reaugmented (&rt->abt, &prev->abt_node);
799             }
800         }
801       else if (node->n_ones == 0)
802         {
803           struct range_tower_node *next = range_tower_next__ (rt, node);
804           if (next != NULL)
805             {
806               /* Merge with next. */
807               unsigned long int n_zeros = node->n_zeros;
808
809               abt_delete (&rt->abt, &node->abt_node);
810               next->n_zeros += n_zeros;
811               abt_reaugmented (&rt->abt, &next->abt_node);
812             }
813         }
814
815       if (new_start < old_start)
816         {
817           node = range_tower_lookup (rt, new_start, &node_start);
818           if (zeros)
819             {
820               node = range_tower_insert0__ (rt, node, &node_start,
821                                             new_start, zeros);
822               old_start += zeros;
823               new_start += zeros;
824             }
825
826           if (ones)
827             {
828               node = range_tower_insert1__ (rt, node, &node_start,
829                                             new_start, ones);
830               old_start += ones;
831               new_start += ones;
832             }
833         }
834       else
835         {
836           unsigned long int remaining = width - (zeros + ones);
837
838           if (new_start + remaining < ULONG_MAX - (zeros + ones))
839             {
840               node = range_tower_lookup (rt, new_start + remaining,
841                                          &node_start);
842               if (zeros)
843                 {
844                   node = range_tower_insert0__ (rt, node, &node_start,
845                                                 new_start + remaining, zeros);
846                   new_start += zeros;
847                 }
848
849               if (ones)
850                 {
851                   node = range_tower_insert1__ (rt, node, &node_start,
852                                                 new_start + remaining, ones);
853                   new_start += ones;
854                 }
855             }
856           else
857             {
858               node = range_tower_last__ (rt);
859               if (zeros)
860                 {
861                   if (node->n_ones)
862                     {
863                       struct range_tower_node *new_node;
864
865                       new_node = xmalloc (sizeof *new_node);
866                       new_node->n_zeros = zeros;
867                       new_node->n_ones = 0;
868
869                       abt_insert_after (&rt->abt, &node->abt_node,
870                                         &new_node->abt_node);
871
872                       node_start += node->n_zeros + node->n_ones;
873                       node = new_node;
874                     }
875                   else
876                     {
877                       node->n_zeros += zeros;
878                       abt_reaugmented (&rt->abt, &node->abt_node);
879                     }
880                 }
881               if (ones)
882                 {
883                   node->n_ones += ones;
884                   abt_reaugmented (&rt->abt, &node->abt_node);
885                 }
886
887               new_start += zeros + ones;
888             }
889         }
890       width -= zeros + ones;
891     }
892   while (width > 0);
893 }
894
895 /* Returns true if there is a 1-bit at the given POSITION in RT,
896    false otherwise. */
897 bool
898 range_tower_contains (const struct range_tower *rt_, unsigned long int position)
899 {
900   struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
901   if (position >= rt->cache_end || position < rt->cache_start)
902     {
903       struct range_tower_node *node;
904       unsigned long int node_start;
905
906       node = range_tower_lookup (rt, position, &node_start);
907       if (position < node_start + node->n_zeros)
908         {
909           rt->cache_start = node_start;
910           rt->cache_end = node_start + node->n_zeros;
911           rt->cache_value = false;
912         }
913       else
914         {
915           rt->cache_start = node_start + node->n_zeros;
916           rt->cache_end = rt->cache_start + node->n_ones;
917           rt->cache_value = true;
918         }
919     }
920   return rt->cache_value;
921 }
922
923 /* Returns the smallest position of a 1-bit greater than or
924    equal to START.  Returns ULONG_MAX if there is no 1-bit with
925    position greater than or equal to START. */
926 unsigned long int
927 range_tower_scan (const struct range_tower *rt_, unsigned long int start)
928 {
929   struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
930
931   if (start < rt->cache_end && start >= rt->cache_start && rt->cache_value)
932     return start;
933
934   if (start != ULONG_MAX)
935     {
936       struct range_tower_node *node;
937       unsigned long int node_start;
938
939       node = range_tower_lookup (rt, start, &node_start);
940       if (node->n_ones)
941         {
942           rt->cache_start = node_start + node->n_zeros;
943           rt->cache_end = rt->cache_start + node->n_ones;
944           rt->cache_value = true;
945           return MAX (start, rt->cache_start);
946         }
947       else
948         {
949           rt->cache_start = node_start;
950           rt->cache_end = ULONG_MAX;
951           rt->cache_value = false;
952         }
953     }
954   return ULONG_MAX;
955 }
956 \f
957 /* Recalculates the subtree_width of NODE based on its LEFT and
958    RIGHT children's "subtree_width"s. */
959 static void
960 reaugment_range_tower_node (struct abt_node *node_, const void *aux UNUSED)
961 {
962   struct range_tower_node *node = range_tower_node_from_abt_node (node_);
963
964   node->subtree_width = node->n_zeros + node->n_ones;
965   if (node->abt_node.down[0] != NULL)
966     {
967       struct range_tower_node *left;
968
969       left = range_tower_node_from_abt_node (node->abt_node.down[0]);
970       node->subtree_width += left->subtree_width;
971     }
972   if (node->abt_node.down[1] != NULL)
973     {
974       struct range_tower_node *right;
975
976       right = range_tower_node_from_abt_node (node->abt_node.down[1]);
977       node->subtree_width += right->subtree_width;
978     }
979 }
980
981 /* Deletes NODE from RT and frees it. */
982 static void
983 delete_node (struct range_tower *rt, struct range_tower_node *node)
984 {
985   abt_delete (&rt->abt, &node->abt_node);
986   free (node);
987 }
988
989 struct range_tower_node *
990 range_tower_lookup (const struct range_tower *rt, unsigned long int position,
991                     unsigned long int *node_start)
992 {
993   const struct range_tower_node *node;
994   const struct abt_node *abt_node;
995
996   abt_node = rt->abt.root;
997   node = range_tower_node_from_abt_node (abt_node);
998   *node_start = subtree_width (abt_node->down[0]);
999   for (;;)
1000     {
1001       unsigned long int left_width = subtree_width (abt_node->down[0]);
1002
1003       if (position < left_width)
1004         {
1005           abt_node = abt_node->down[0];
1006           *node_start -= left_width - subtree_width (abt_node->down[0]);
1007         }
1008       else
1009         {
1010           unsigned long int node_width = node->n_zeros + node->n_ones;
1011
1012           position -= left_width;
1013           if (position < node_width)
1014             return CONST_CAST (struct range_tower_node *, node);
1015
1016           position -= node_width;
1017           abt_node = abt_node->down[1];
1018           left_width = subtree_width (abt_node->down[0]);
1019           *node_start += node_width + left_width;
1020         }
1021       node = range_tower_node_from_abt_node (abt_node);
1022     }
1023 }
1024
1025 /* Destroys range tower RT.
1026    Helper function for range_tower_create_pool. */
1027 static void
1028 destroy_pool (void *rt_)
1029 {
1030   struct range_tower *rt = rt_;
1031   rt->pool = NULL;
1032   range_tower_destroy (rt);
1033 }