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