src/libpspp/range-set.c

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