src/libpspp/range-set.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* Bitmap, implemented as a balanced binary tree. */
  18
  19 /* If you add routines in this file, please add a corresponding
  20    test to range-set-test.c.  This test program should achieve
  21    100% coverage of lines and branches in this code, as reported
  22    by "gcov -b". */
  23
  24 #include <config.h>
  25
  26 #include <libpspp/range-set.h>
  27
  28 #include <limits.h>
  29 #include <stdlib.h>
  30
  31 #include <libpspp/assertion.h>
  32 #include <libpspp/bt.h>
  33 #include <libpspp/compiler.h>
  34 #include <libpspp/pool.h>
  35
  36 #include "xalloc.h"
  37
  38 /* A set of ranges. */
  39 struct range_set
  40   {
  41     struct pool *pool;                  /* Pool for freeing range_set. */
  42     struct bt bt;                       /* Tree of range_set_nodes. */
  43
  44     /* Cache. */
  45     unsigned long int cache_start;      /* Start of region. */
  46     unsigned long int cache_end;        /* One past end of region. */
  47     bool cache_value;                   /* Is the region in the set? */
  48   };
  49
  50 /* A node in the range set. */
  51 struct range_set_node
  52   {
  53     struct bt_node bt_node;             /* Binary tree node. */
  54     unsigned long int start;            /* Start of region. */
  55     unsigned long int end;              /* One past end of region. */
  56   };
  57
  58 static struct range_set_node *bt_to_rs_node (const struct bt_node *);
  59 static int compare_range_set_nodes (const struct bt_node *,
  60                                     const struct bt_node *,
  61                                     const void *aux);
  62 static struct range_set_node *first_node (const struct range_set *);
  63 static struct range_set_node *next_node (const struct range_set *,
  64                                          const struct range_set_node *);
  65 static void delete_node (struct range_set *, struct range_set_node *);
  66 static struct range_set_node *delete_node_get_next (struct range_set *,
  67                                                     struct range_set_node *);
  68 static struct range_set_node *find_node_le (const struct range_set *,
  69                                             unsigned long int position);
  70 static struct range_set_node *insert_node (struct range_set *,
  71                                            unsigned long int start,
  72                                            unsigned long int end);
  73 static void insert_just_before (struct range_set *,
  74                                 unsigned long int start, unsigned long int end,
  75                                 struct range_set_node *);
  76 static void merge_node_with_successors (struct range_set *,
  77                                         struct range_set_node *);
  78 static void destroy_pool (void *);
  79
  80 /* Creates and returns a new, empty range set. */
  81 struct range_set *
  82 range_set_create (void)
  83 {
  84   return range_set_create_pool (NULL);
  85 }
  86
  87 /* Creates and returns a new, empty range set in the given
  88    POOL. */
  89 struct range_set *
  90 range_set_create_pool (struct pool *pool)
  91 {
  92   struct range_set *rs = xmalloc (sizeof *rs);
  93   rs->pool = pool;
  94   if (pool != NULL)
  95     pool_register (pool, destroy_pool, rs);
  96   bt_init (&rs->bt, compare_range_set_nodes, NULL);
  97   rs->cache_end = 0;
  98   return rs;
  99 }
 100
 101 /* Creates and returns a clone of OLD range set in the given POOL
 102    (which may be null). */
 103 struct range_set *
 104 range_set_clone (const struct range_set *old, struct pool *pool)
 105 {
 106   struct range_set *new;
 107   struct range_set_node *node;
 108
 109   new = range_set_create_pool (pool);
 110   for (node = first_node (old); node != NULL; node = next_node (old, node))
 111     insert_node (new, node->start, node->end);
 112   return new;
 113 }
 114
 115 /* Destroys range set RS. */
 116 void
 117 range_set_destroy (struct range_set *rs)
 118 {
 119   if (rs != NULL)
 120     {
 121       if (rs->pool != NULL)
 122         pool_unregister (rs->pool, rs);
 123       while (!range_set_is_empty (rs))
 124         delete_node (rs, first_node (rs));
 125       free (rs);
 126     }
 127 }
 128
 129 /* Inserts the region starting at START and extending for WIDTH
 130    into RS. */
 131 void
 132 range_set_insert (struct range_set *rs,
 133                   unsigned long int start, unsigned long int width)
 134 {
 135   unsigned long int end = start + width;
 136   struct range_set_node *node;
 137
 138   assert (width == 0 || start + width - 1 >= start);
 139
 140   if (width == 0)
 141     return;
 142
 143   /* Invalidate cache. */
 144   rs->cache_end = 0;
 145
 146   node = find_node_le (rs, start);
 147   if (node != NULL)
 148     {
 149       if (start > node->end)
 150         {
 151           /* New region does not overlap NODE, but it might
 152              overlap the next node. */
 153           insert_just_before (rs, start, end, next_node (rs, node));
 154         }
 155       else if (end > node->end)
 156         {
 157           /* New region starts in the middle of NODE and
 158              continues past its end, so extend NODE, then merge
 159              it with any following node that it now potentially
 160              overlaps. */
 161           node->end = end;
 162           merge_node_with_successors (rs, node);
 163         }
 164       else
 165         {
 166           /* New region is completely contained by NODE, so
 167              there's nothing to do. */
 168         }
 169     }
 170   else
 171     {
 172       /* New region starts before any existing region, but it
 173          might overlap the first region. */
 174       insert_just_before (rs, start, end, first_node (rs));
 175     }
 176 }
 177
 178 /* Inserts the region starting at START and extending for WIDTH
 179    from RS. */
 180 void
 181 range_set_delete (struct range_set *rs,
 182                   unsigned long int start, unsigned long int width)
 183 {
 184   unsigned long int end = start + width;
 185   struct range_set_node *node;
 186
 187   assert (width == 0 || start + width - 1 >= start);
 188
 189   if (width == 0)
 190     return;
 191
 192   /* Invalidate cache. */
 193   rs->cache_end = 0;
 194
 195   node = find_node_le (rs, start);
 196   if (node == NULL)
 197     node = first_node (rs);
 198
 199   while (node != NULL && end > node->start)
 200     {
 201       if (start <= node->start)
 202         {
 203           if (end >= node->end)
 204             {
 205               /* Region to delete covers entire node. */
 206               node = delete_node_get_next (rs, node);
 207             }
 208           else
 209             {
 210               /* Region to delete covers only left part of node. */
 211               node->start = end;
 212               break;
 213             }
 214         }
 215       else if (start < node->end)
 216         {
 217           if (end < node->end)
 218             {
 219               /* Region to delete covers middle of the node, so
 220                  we have to split the node into two pieces. */
 221               unsigned long int old_node_end = node->end;
 222               node->end = start;
 223               insert_node (rs, end, old_node_end);
 224               break;
 225             }
 226           else
 227             {
 228               /* Region to delete covers only right part of
 229                  node. */
 230               node->end = start;
 231               node = next_node (rs, node);
 232             }
 233         }
 234       else
 235         node = next_node (rs, node);
 236     }
 237 }
 238
 239 /* Scans RS for its first 1-bit and deletes up to REQUEST
 240    contiguous 1-bits starting at that position.  Unless RS is
 241    completely empty, sets *START to the position of the first
 242    1-bit deleted and *WIDTH to the number actually deleted, which
 243    may be less than REQUEST if fewer contiguous 1-bits were
 244    present, and returns true.  If RS is completely empty, returns
 245    false. */
 246 bool
 247 range_set_allocate (struct range_set *rs, unsigned long int request,
 248                     unsigned long int *start, unsigned long int *width)
 249 {
 250   struct range_set_node *node;
 251   unsigned long int node_width;
 252
 253   assert (request > 0);
 254
 255   node = first_node (rs);
 256   if (node == NULL)
 257     return false;
 258   node_width = node->end - node->start;
 259
 260   *start = node->start;
 261   if (request < node_width)
 262     {
 263       *width = request;
 264       node->start += request;
 265     }
 266   else
 267     {
 268       *width = node_width;
 269       delete_node (rs, node);
 270     }
 271
 272   rs->cache_end = 0;
 273
 274   return true;
 275 }
 276
 277 /* Scans RS for and deletes the first contiguous run of REQUEST
 278    1-bits.  If successful, sets *START to the position of the
 279    first 1-bit deleted and returns true If RS does not contain a
 280    run of REQUEST or more contiguous 1-bits, returns false and
 281    does not modify RS. */
 282 bool
 283 range_set_allocate_fully (struct range_set *rs, unsigned long int request,
 284                           unsigned long int *start)
 285 {
 286   struct range_set_node *node;
 287
 288   assert (request > 0);
 289
 290   for (node = first_node (rs); node != NULL; node = next_node (rs, node))
 291     {
 292       unsigned long int node_width = node->end - node->start;
 293       if (node_width >= request)
 294         {
 295           *start = node->start;
 296           if (node_width > request)
 297             node->start += request;
 298           else
 299             delete_node (rs, node);
 300           rs->cache_end = 0;
 301           return true;
 302         }
 303     }
 304   return false;
 305 }
 306
 307 /* Returns true if there is a 1-bit at the given POSITION in RS,
 308    false otherwise. */
 309 bool
 310 range_set_contains (const struct range_set *rs_, unsigned long int position)
 311 {
 312   struct range_set *rs = (struct range_set *) rs_;
 313   if (position < rs->cache_end && position >= rs->cache_start)
 314     return rs->cache_value;
 315   else
 316     {
 317       struct range_set_node *node = find_node_le (rs, position);
 318       if (node != NULL)
 319         {
 320           if (position < node->end)
 321             {
 322               rs->cache_start = node->start;
 323               rs->cache_end = node->end;
 324               rs->cache_value = true;
 325               return true;
 326             }
 327           else
 328             {
 329               struct range_set_node *next = next_node (rs, node);
 330               rs->cache_start = node->end;
 331               rs->cache_end = next != NULL ? next->start : ULONG_MAX;
 332               rs->cache_value = false;
 333               return false;
 334             }
 335         }
 336       else
 337         {
 338           node = first_node (rs);
 339           rs->cache_start = 0;
 340           rs->cache_end = node != NULL ? node->start : ULONG_MAX;
 341           rs->cache_value = false;
 342           return false;
 343         }
 344     }
 345 }
 346
 347 /* Returns true if RS contains no 1-bits, false otherwise. */
 348 bool
 349 range_set_is_empty (const struct range_set *rs)
 350 {
 351   return bt_count (&rs->bt) == 0;
 352 }
 353
 354 /* Returns the node representing the first contiguous region of
 355    1-bits in RS, or a null pointer if RS is empty.
 356    Any call to range_set_insert, range_set_delete, or
 357    range_set_allocate invalidates the returned node. */
 358 const struct range_set_node *
 359 range_set_first (const struct range_set *rs)
 360 {
 361   return first_node (rs);
 362 }
 363
 364 /* If NODE is nonnull, returns the node representing the next
 365    contiguous region of 1-bits in RS following NODE, or a null
 366    pointer if NODE is the last region in RS.
 367    If NODE is null, returns the first region in RS, as for
 368    range_set_first.
 369    Any call to range_set_insert, range_set_delete, or
 370    range_set_allocate invalidates the returned node. */
 371 const struct range_set_node *
 372 range_set_next (const struct range_set *rs, const struct range_set_node *node)
 373 {
 374   return (node != NULL
 375           ? next_node (rs, (struct range_set_node *) node)
 376           : first_node (rs));
 377 }
 378
 379 /* Returns the position of the first 1-bit in NODE. */
 380 unsigned long int
 381 range_set_node_get_start (const struct range_set_node *node)
 382 {
 383   return node->start;
 384 }
 385
 386 /* Returns one past the position of the last 1-bit in NODE. */
 387 unsigned long int
 388 range_set_node_get_end (const struct range_set_node *node)
 389 {
 390   return node->end;
 391 }
 392
 393 /* Returns the number of contiguous 1-bits in NODE. */
 394 unsigned long int
 395 range_set_node_get_width (const struct range_set_node *node)
 396 {
 397   return node->end - node->start;
 398 }
 399 \f
 400 /* Returns the range_set_node corresponding to the given
 401    BT_NODE.  Returns a null pointer if BT_NODE is null. */
 402 static struct range_set_node *
 403 bt_to_rs_node (const struct bt_node *bt_node)
 404 {
 405   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
 406 }
 407
 408 /* Compares `range_set_node's A and B and returns a strcmp-like
 409    return value. */
 410 static int
 411 compare_range_set_nodes (const struct bt_node *a_,
 412                          const struct bt_node *b_,
 413                          const void *aux UNUSED)
 414 {
 415   const struct range_set_node *a = bt_to_rs_node (a_);
 416   const struct range_set_node *b = bt_to_rs_node (b_);
 417
 418   return a->start < b->start ? -1 : a->start > b->start;
 419 }
 420
 421 /* Returns the first range_set_node in RS,
 422    or a null pointer if RS is empty. */
 423 static struct range_set_node *
 424 first_node (const struct range_set *rs)
 425 {
 426   return bt_to_rs_node (bt_first (&rs->bt));
 427 }
 428
 429 /* Returns the next range_set_node in RS after NODE,
 430    or a null pointer if NODE is the last node in RS. */
 431 static struct range_set_node *
 432 next_node (const struct range_set *rs, const struct range_set_node *node)
 433 {
 434   return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
 435 }
 436
 437 /* Deletes NODE from RS and frees it. */
 438 static void
 439 delete_node (struct range_set *rs, struct range_set_node *node)
 440 {
 441   bt_delete (&rs->bt, &node->bt_node);
 442   free (node);
 443 }
 444
 445 /* Deletes NODE from RS, frees it, and returns the following
 446    node. */
 447 static struct range_set_node *
 448 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
 449 {
 450   struct range_set_node *next = next_node (rs, node);
 451   delete_node (rs, node);
 452   return next;
 453 }
 454
 455 /* Returns the node in RS that would be just before POSITION if a
 456    range_set_node with `start' as POSITION were inserted.
 457    Returns a null pointer if POSITION is before any existing node
 458    in RS.  If POSITION would duplicate an existing region's
 459    start, returns that region. */
 460 static struct range_set_node *
 461 find_node_le (const struct range_set *rs, unsigned long int position)
 462 {
 463   struct range_set_node tmp;
 464   tmp.start = position;
 465   return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
 466 }
 467
 468 /* Creates a new region with the given START and END, inserts the
 469    region into RS, and returns the new region. */
 470 static struct range_set_node *
 471 insert_node (struct range_set *rs,
 472              unsigned long int start, unsigned long int end)
 473 {
 474   struct range_set_node *node = xmalloc (sizeof *node);
 475   struct bt_node *dummy;
 476   node->start = start;
 477   node->end = end;
 478   dummy = bt_insert (&rs->bt, &node->bt_node);
 479   assert (dummy == NULL);
 480   return node;
 481 }
 482
 483 /* Inserts the region START...END (exclusive) into RS given that
 484    the new region is "just before" NODE, that is, if NODE is
 485    nonnull, the new region is known not to overlap any node
 486    preceding NODE, and START precedes NODE's start; if NODE is
 487    null, then the new region is known to follow any and all
 488    regions already in RS. */
 489 static void
 490 insert_just_before (struct range_set *rs,
 491                     unsigned long int start, unsigned long int end,
 492                     struct range_set_node *node)
 493 {
 494   assert (node == NULL || start < node->start);
 495   if (node != NULL && end >= node->start)
 496     {
 497       /* New region overlaps NODE, so just extend NODE. */
 498       node->start = start;
 499       if (end > node->end)
 500         {
 501           node->end = end;
 502           merge_node_with_successors (rs, node);
 503         }
 504     }
 505   else
 506     {
 507       /* New region does not overlap NODE. */
 508       insert_node (rs, start, end);
 509     }
 510 }
 511
 512 /* Merges NODE in RS with its successors. */
 513 static void
 514 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
 515 {
 516   struct range_set_node *next;
 517
 518   while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
 519     {
 520       if (next->end > node->end)
 521         node->end = next->end;
 522       delete_node (rs, next);
 523     }
 524 }
 525
 526 /* Destroys range set RS.
 527    Helper function for range_set_create_pool. */
 528 static void
 529 destroy_pool (void *rs_)
 530 {
 531   struct range_set *rs = rs_;
 532   rs->pool = NULL;
 533   range_set_destroy (rs);
 534 }