pintos-os.org Git - pspp/blob - 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 }