src/libpspp/range-set.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007 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 /* Returns true if there is a 1-bit at the given POSITION in RS,
 278    false otherwise. */
 279 bool
 280 range_set_contains (const struct range_set *rs_, unsigned long int position)
 281 {
 282   struct range_set *rs = (struct range_set *) rs_;
 283   if (position < rs->cache_end && position >= rs->cache_start)
 284     return rs->cache_value;
 285   else
 286     {
 287       struct range_set_node *node = find_node_le (rs, position);
 288       if (node != NULL)
 289         {
 290           if (position < node->end)
 291             {
 292               rs->cache_start = node->start;
 293               rs->cache_end = node->end;
 294               rs->cache_value = true;
 295               return true;
 296             }
 297           else
 298             {
 299               struct range_set_node *next = next_node (rs, node);
 300               rs->cache_start = node->end;
 301               rs->cache_end = next != NULL ? next->start : ULONG_MAX;
 302               rs->cache_value = false;
 303               return false;
 304             }
 305         }
 306       else
 307         {
 308           node = first_node (rs);
 309           rs->cache_start = 0;
 310           rs->cache_end = node != NULL ? node->start : ULONG_MAX;
 311           rs->cache_value = false;
 312           return false;
 313         }
 314     }
 315 }
 316
 317 /* Returns true if RS contains no 1-bits, false otherwise. */
 318 bool
 319 range_set_is_empty (const struct range_set *rs)
 320 {
 321   return bt_count (&rs->bt) == 0;
 322 }
 323
 324 /* Returns the node representing the first contiguous region of
 325    1-bits in RS, or a null pointer if RS is empty.
 326    Any call to range_set_insert, range_set_delete, or
 327    range_set_allocate invalidates the returned node. */
 328 const struct range_set_node *
 329 range_set_first (const struct range_set *rs)
 330 {
 331   return first_node (rs);
 332 }
 333
 334 /* If NODE is nonnull, returns the node representing the next
 335    contiguous region of 1-bits in RS following NODE, or a null
 336    pointer if NODE is the last region in RS.
 337    If NODE is null, returns the first region in RS, as for
 338    range_set_first.
 339    Any call to range_set_insert, range_set_delete, or
 340    range_set_allocate invalidates the returned node. */
 341 const struct range_set_node *
 342 range_set_next (const struct range_set *rs, const struct range_set_node *node)
 343 {
 344   return (node != NULL
 345           ? next_node (rs, (struct range_set_node *) node)
 346           : first_node (rs));
 347 }
 348
 349 /* Returns the position of the first 1-bit in NODE. */
 350 unsigned long int
 351 range_set_node_get_start (const struct range_set_node *node)
 352 {
 353   return node->start;
 354 }
 355
 356 /* Returns one past the position of the last 1-bit in NODE. */
 357 unsigned long int
 358 range_set_node_get_end (const struct range_set_node *node)
 359 {
 360   return node->end;
 361 }
 362
 363 /* Returns the number of contiguous 1-bits in NODE. */
 364 unsigned long int
 365 range_set_node_get_width (const struct range_set_node *node)
 366 {
 367   return node->end - node->start;
 368 }
 369 \f
 370 /* Returns the range_set_node corresponding to the given
 371    BT_NODE.  Returns a null pointer if BT_NODE is null. */
 372 static struct range_set_node *
 373 bt_to_rs_node (const struct bt_node *bt_node)
 374 {
 375   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
 376 }
 377
 378 /* Compares `range_set_node's A and B and returns a strcmp-like
 379    return value. */
 380 static int
 381 compare_range_set_nodes (const struct bt_node *a_,
 382                          const struct bt_node *b_,
 383                          const void *aux UNUSED)
 384 {
 385   const struct range_set_node *a = bt_to_rs_node (a_);
 386   const struct range_set_node *b = bt_to_rs_node (b_);
 387
 388   return a->start < b->start ? -1 : a->start > b->start;
 389 }
 390
 391 /* Returns the first range_set_node in RS,
 392    or a null pointer if RS is empty. */
 393 static struct range_set_node *
 394 first_node (const struct range_set *rs)
 395 {
 396   return bt_to_rs_node (bt_first (&rs->bt));
 397 }
 398
 399 /* Returns the next range_set_node in RS after NODE,
 400    or a null pointer if NODE is the last node in RS. */
 401 static struct range_set_node *
 402 next_node (const struct range_set *rs, const struct range_set_node *node)
 403 {
 404   return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
 405 }
 406
 407 /* Deletes NODE from RS and frees it. */
 408 static void
 409 delete_node (struct range_set *rs, struct range_set_node *node)
 410 {
 411   bt_delete (&rs->bt, &node->bt_node);
 412   free (node);
 413 }
 414
 415 /* Deletes NODE from RS, frees it, and returns the following
 416    node. */
 417 static struct range_set_node *
 418 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
 419 {
 420   struct range_set_node *next = next_node (rs, node);
 421   delete_node (rs, node);
 422   return next;
 423 }
 424
 425 /* Returns the node in RS that would be just before POSITION if a
 426    range_set_node with `start' as POSITION were inserted.
 427    Returns a null pointer if POSITION is before any existing node
 428    in RS.  If POSITION would duplicate an existing region's
 429    start, returns that region. */
 430 static struct range_set_node *
 431 find_node_le (const struct range_set *rs, unsigned long int position)
 432 {
 433   struct range_set_node tmp;
 434   tmp.start = position;
 435   return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
 436 }
 437
 438 /* Creates a new region with the given START and END, inserts the
 439    region into RS, and returns the new region. */
 440 static struct range_set_node *
 441 insert_node (struct range_set *rs,
 442              unsigned long int start, unsigned long int end)
 443 {
 444   struct range_set_node *node = xmalloc (sizeof *node);
 445   struct bt_node *dummy;
 446   node->start = start;
 447   node->end = end;
 448   dummy = bt_insert (&rs->bt, &node->bt_node);
 449   assert (dummy == NULL);
 450   return node;
 451 }
 452
 453 /* Inserts the region START...END (exclusive) into RS given that
 454    the new region is "just before" NODE, that is, if NODE is
 455    nonnull, the new region is known not to overlap any node
 456    preceding NODE, and START precedes NODE's start; if NODE is
 457    null, then the new region is known to follow any and all
 458    regions already in RS. */
 459 static void
 460 insert_just_before (struct range_set *rs,
 461                     unsigned long int start, unsigned long int end,
 462                     struct range_set_node *node)
 463 {
 464   assert (node == NULL || start < node->start);
 465   if (node != NULL && end >= node->start)
 466     {
 467       /* New region overlaps NODE, so just extend NODE. */
 468       node->start = start;
 469       if (end > node->end)
 470         {
 471           node->end = end;
 472           merge_node_with_successors (rs, node);
 473         }
 474     }
 475   else
 476     {
 477       /* New region does not overlap NODE. */
 478       insert_node (rs, start, end);
 479     }
 480 }
 481
 482 /* Merges NODE in RS with its successors. */
 483 static void
 484 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
 485 {
 486   struct range_set_node *next;
 487
 488   while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
 489     {
 490       if (next->end > node->end)
 491         node->end = next->end;
 492       delete_node (rs, next);
 493     }
 494 }
 495
 496 /* Destroys range set RS.
 497    Helper function for range_set_create_pool. */
 498 static void
 499 destroy_pool (void *rs_)
 500 {
 501   struct range_set *rs = rs_;
 502   rs->pool = NULL;
 503   range_set_destroy (rs);
 504 }