gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / range-tower.c
1 /* pspp - a program for statistical analysis.
2    Copyright (C) 2007, 2009, 2011, 2012, 2013 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                   delete_node (rt, 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               delete_node (rt, next);
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                   delete_node (rt, 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               delete_node (rt, 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               delete_node (rt, next);
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
745   if (width == 0 || old_start == new_start)
746     return;
747
748   assert (old_start + width - 1 >= old_start);
749   assert (new_start + width - 1 >= new_start);
750
751   do
752     {
753       struct range_tower_node *node;
754       unsigned long int node_ofs;
755       unsigned long int zeros, ones;
756
757       node = range_tower_lookup (rt, old_start, &node_start);
758       node_ofs = old_start - node_start;
759
760       if (node_ofs >= node->n_zeros)
761         {
762           unsigned long int max_ones;
763
764           zeros = 0;
765           max_ones = (node->n_zeros + node->n_ones) - node_ofs;
766           ones = MIN (width, max_ones);
767         }
768       else
769         {
770           unsigned long int max_zeros;
771
772           max_zeros = node->n_zeros - node_ofs;
773           zeros = MIN (width, max_zeros);
774           if (zeros < width)
775             ones = MIN (width - zeros, node->n_ones);
776           else
777             ones = 0;
778         }
779
780       node->n_zeros -= zeros;
781       node->n_ones -= ones;
782       abt_reaugmented (&rt->abt, &node->abt_node);
783
784       if (node->n_zeros == 0)
785         {
786           if (node->n_ones == 0)
787             delete_node (rt, node);
788           else if (node_start > 0)
789             {
790               /* Merge with previous. */
791               unsigned long int n_ones = node->n_ones;
792               struct range_tower_node *prev = range_tower_prev__ (rt, node);
793
794               delete_node (rt, node);
795               prev->n_ones += n_ones;
796               abt_reaugmented (&rt->abt, &prev->abt_node);
797             }
798         }
799       else if (node->n_ones == 0)
800         {
801           struct range_tower_node *next = range_tower_next__ (rt, node);
802           if (next != NULL)
803             {
804               /* Merge with next. */
805               unsigned long int n_zeros = node->n_zeros;
806
807               delete_node (rt, node);
808               next->n_zeros += n_zeros;
809               abt_reaugmented (&rt->abt, &next->abt_node);
810             }
811         }
812
813       if (new_start < old_start)
814         {
815           node = range_tower_lookup (rt, new_start, &node_start);
816           if (zeros)
817             {
818               node = range_tower_insert0__ (rt, node, &node_start,
819                                             new_start, zeros);
820               old_start += zeros;
821               new_start += zeros;
822             }
823
824           if (ones)
825             {
826               node = range_tower_insert1__ (rt, node, &node_start,
827                                             new_start, ones);
828               old_start += ones;
829               new_start += ones;
830             }
831         }
832       else
833         {
834           unsigned long int remaining = width - (zeros + ones);
835
836           if (new_start + remaining < ULONG_MAX - (zeros + ones))
837             {
838               node = range_tower_lookup (rt, new_start + remaining,
839                                          &node_start);
840               if (zeros)
841                 {
842                   node = range_tower_insert0__ (rt, node, &node_start,
843                                                 new_start + remaining, zeros);
844                   new_start += zeros;
845                 }
846
847               if (ones)
848                 {
849                   node = range_tower_insert1__ (rt, node, &node_start,
850                                                 new_start + remaining, ones);
851                   new_start += ones;
852                 }
853             }
854           else
855             {
856               node = range_tower_last__ (rt);
857               if (zeros)
858                 {
859                   if (node->n_ones)
860                     {
861                       struct range_tower_node *new_node;
862
863                       new_node = xmalloc (sizeof *new_node);
864                       new_node->n_zeros = zeros;
865                       new_node->n_ones = 0;
866
867                       abt_insert_after (&rt->abt, &node->abt_node,
868                                         &new_node->abt_node);
869
870                       node_start += node->n_zeros + node->n_ones;
871                       node = new_node;
872                     }
873                   else
874                     {
875                       node->n_zeros += zeros;
876                       abt_reaugmented (&rt->abt, &node->abt_node);
877                     }
878                 }
879               if (ones)
880                 {
881                   node->n_ones += ones;
882                   abt_reaugmented (&rt->abt, &node->abt_node);
883                 }
884
885               new_start += zeros + ones;
886             }
887         }
888       width -= zeros + ones;
889     }
890   while (width > 0);
891 }
892
893 /* Returns true if there is a 1-bit at the given POSITION in RT,
894    false otherwise. */
895 bool
896 range_tower_contains (const struct range_tower *rt_, unsigned long int position)
897 {
898   struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
899   if (position >= rt->cache_end || position < rt->cache_start)
900     {
901       struct range_tower_node *node;
902       unsigned long int node_start;
903
904       node = range_tower_lookup (rt, position, &node_start);
905       if (position < node_start + node->n_zeros)
906         {
907           rt->cache_start = node_start;
908           rt->cache_end = node_start + node->n_zeros;
909           rt->cache_value = false;
910         }
911       else
912         {
913           rt->cache_start = node_start + node->n_zeros;
914           rt->cache_end = rt->cache_start + node->n_ones;
915           rt->cache_value = true;
916         }
917     }
918   return rt->cache_value;
919 }
920
921 /* Returns the smallest position of a 1-bit greater than or
922    equal to START.  Returns ULONG_MAX if there is no 1-bit with
923    position greater than or equal to START. */
924 unsigned long int
925 range_tower_scan (const struct range_tower *rt_, unsigned long int start)
926 {
927   struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
928
929   if (start < rt->cache_end && start >= rt->cache_start && rt->cache_value)
930     return start;
931
932   if (start != ULONG_MAX)
933     {
934       struct range_tower_node *node;
935       unsigned long int node_start;
936
937       node = range_tower_lookup (rt, start, &node_start);
938       if (node->n_ones)
939         {
940           rt->cache_start = node_start + node->n_zeros;
941           rt->cache_end = rt->cache_start + node->n_ones;
942           rt->cache_value = true;
943           return MAX (start, rt->cache_start);
944         }
945       else
946         {
947           rt->cache_start = node_start;
948           rt->cache_end = ULONG_MAX;
949           rt->cache_value = false;
950         }
951     }
952   return ULONG_MAX;
953 }
954 \f
955 /* Recalculates the subtree_width of NODE based on its LEFT and
956    RIGHT children's "subtree_width"s. */
957 static void
958 reaugment_range_tower_node (struct abt_node *node_, const void *aux UNUSED)
959 {
960   struct range_tower_node *node = range_tower_node_from_abt_node (node_);
961
962   node->subtree_width = node->n_zeros + node->n_ones;
963   if (node->abt_node.down[0] != NULL)
964     {
965       struct range_tower_node *left;
966
967       left = range_tower_node_from_abt_node (node->abt_node.down[0]);
968       node->subtree_width += left->subtree_width;
969     }
970   if (node->abt_node.down[1] != NULL)
971     {
972       struct range_tower_node *right;
973
974       right = range_tower_node_from_abt_node (node->abt_node.down[1]);
975       node->subtree_width += right->subtree_width;
976     }
977 }
978
979 /* Deletes NODE from RT and frees it. */
980 static void
981 delete_node (struct range_tower *rt, struct range_tower_node *node)
982 {
983   abt_delete (&rt->abt, &node->abt_node);
984   free (node);
985 }
986
987 struct range_tower_node *
988 range_tower_lookup (const struct range_tower *rt, unsigned long int position,
989                     unsigned long int *node_start)
990 {
991   const struct range_tower_node *node;
992   const struct abt_node *abt_node;
993
994   abt_node = rt->abt.root;
995   node = range_tower_node_from_abt_node (abt_node);
996   *node_start = subtree_width (abt_node->down[0]);
997   for (;;)
998     {
999       unsigned long int left_width = subtree_width (abt_node->down[0]);
1000
1001       if (position < left_width)
1002         {
1003           abt_node = abt_node->down[0];
1004           *node_start -= left_width - subtree_width (abt_node->down[0]);
1005         }
1006       else
1007         {
1008           unsigned long int node_width = node->n_zeros + node->n_ones;
1009
1010           position -= left_width;
1011           if (position < node_width)
1012             return CONST_CAST (struct range_tower_node *, node);
1013
1014           position -= node_width;
1015           abt_node = abt_node->down[1];
1016           left_width = subtree_width (abt_node->down[0]);
1017           *node_start += node_width + left_width;
1018         }
1019       node = range_tower_node_from_abt_node (abt_node);
1020     }
1021 }
1022
1023 /* Destroys range tower RT.
1024    Helper function for range_tower_create_pool. */
1025 static void
1026 destroy_pool (void *rt_)
1027 {
1028   struct range_tower *rt = rt_;
1029   rt->pool = NULL;
1030   range_tower_destroy (rt);
1031 }