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 /* Destroys range set RS. */
 104 void
 105 range_set_destroy (struct range_set *rs)
 106 {
 107   if (rs != NULL)
 108     {
 109       if (rs->pool != NULL)
 110         pool_unregister (rs->pool, rs);
 111       while (!range_set_is_empty (rs))
 112         delete_node (rs, first_node (rs));
 113       free (rs);
 114     }
 115 }
 116
 117 /* Inserts the region starting at START and extending for WIDTH
 118    into RS. */
 119 void
 120 range_set_insert (struct range_set *rs,
 121                   unsigned long int start, unsigned long int width)
 122 {
 123   unsigned long int end = start + width;
 124   struct range_set_node *node;
 125
 126   assert (width == 0 || start + width - 1 >= start);
 127
 128   if (width == 0)
 129     return;
 130
 131   /* Invalidate cache. */
 132   rs->cache_end = 0;
 133
 134   node = find_node_le (rs, start);
 135   if (node != NULL)
 136     {
 137       if (start > node->end)
 138         {
 139           /* New region does not overlap NODE, but it might
 140              overlap the next node. */
 141           insert_just_before (rs, start, end, next_node (rs, node));
 142         }
 143       else if (end > node->end)
 144         {
 145           /* New region starts in the middle of NODE and
 146              continues past its end, so extend NODE, then merge
 147              it with any following node that it now potentially
 148              overlaps. */
 149           node->end = end;
 150           merge_node_with_successors (rs, node);
 151         }
 152       else
 153         {
 154           /* New region is completely contained by NODE, so
 155              there's nothing to do. */
 156         }
 157     }
 158   else
 159     {
 160       /* New region starts before any existing region, but it
 161          might overlap the first region. */
 162       insert_just_before (rs, start, end, first_node (rs));
 163     }
 164 }
 165
 166 /* Inserts the region starting at START and extending for WIDTH
 167    from RS. */
 168 void
 169 range_set_delete (struct range_set *rs,
 170                   unsigned long int start, unsigned long int width)
 171 {
 172   unsigned long int end = start + width;
 173   struct range_set_node *node;
 174
 175   assert (width == 0 || start + width - 1 >= start);
 176
 177   if (width == 0)
 178     return;
 179
 180   /* Invalidate cache. */
 181   rs->cache_end = 0;
 182
 183   node = find_node_le (rs, start);
 184   if (node == NULL)
 185     node = first_node (rs);
 186
 187   while (node != NULL && end > node->start)
 188     {
 189       if (start <= node->start)
 190         {
 191           if (end >= node->end)
 192             {
 193               /* Region to delete covers entire node. */
 194               node = delete_node_get_next (rs, node);
 195             }
 196           else
 197             {
 198               /* Region to delete covers only left part of node. */
 199               node->start = end;
 200               break;
 201             }
 202         }
 203       else if (start < node->end)
 204         {
 205           if (end < node->end)
 206             {
 207               /* Region to delete covers middle of the node, so
 208                  we have to split the node into two pieces. */
 209               unsigned long int old_node_end = node->end;
 210               node->end = start;
 211               insert_node (rs, end, old_node_end);
 212               break;
 213             }
 214           else
 215             {
 216               /* Region to delete covers only right part of
 217                  node. */
 218               node->end = start;
 219               node = next_node (rs, node);
 220             }
 221         }
 222       else
 223         node = next_node (rs, node);
 224     }
 225 }
 226
 227 /* Scans RS for its first 1-bit and deletes up to REQUEST
 228    contiguous 1-bits starting at that position.  Unless RS is
 229    completely empty, sets *START to the position of the first
 230    1-bit deleted and *WIDTH to the number actually deleted, which
 231    may be less than REQUEST if fewer contiguous 1-bits were
 232    present, and returns true.  If RS is completely empty, returns
 233    false. */
 234 bool
 235 range_set_allocate (struct range_set *rs, unsigned long int request,
 236                     unsigned long int *start, unsigned long int *width)
 237 {
 238   struct range_set_node *node;
 239   unsigned long int node_width;
 240
 241   assert (request > 0);
 242
 243   node = first_node (rs);
 244   if (node == NULL)
 245     return false;
 246   node_width = node->end - node->start;
 247
 248   *start = node->start;
 249   if (request < node_width)
 250     {
 251       *width = request;
 252       node->start += request;
 253     }
 254   else
 255     {
 256       *width = node_width;
 257       delete_node (rs, node);
 258     }
 259
 260   rs->cache_end = 0;
 261
 262   return true;
 263 }
 264
 265 /* Returns true if there is a 1-bit at the given POSITION in RS,
 266    false otherwise. */
 267 bool
 268 range_set_contains (const struct range_set *rs_, unsigned long int position)
 269 {
 270   struct range_set *rs = (struct range_set *) rs_;
 271   if (position < rs->cache_end && position >= rs->cache_start)
 272     return rs->cache_value;
 273   else
 274     {
 275       struct range_set_node *node = find_node_le (rs, position);
 276       if (node != NULL)
 277         {
 278           if (position < node->end)
 279             {
 280               rs->cache_start = node->start;
 281               rs->cache_end = node->end;
 282               rs->cache_value = true;
 283               return true;
 284             }
 285           else
 286             {
 287               struct range_set_node *next = next_node (rs, node);
 288               rs->cache_start = node->end;
 289               rs->cache_end = next != NULL ? next->start : ULONG_MAX;
 290               rs->cache_value = false;
 291               return false;
 292             }
 293         }
 294       else
 295         {
 296           node = first_node (rs);
 297           rs->cache_start = 0;
 298           rs->cache_end = node != NULL ? node->start : ULONG_MAX;
 299           rs->cache_value = false;
 300           return false;
 301         }
 302     }
 303 }
 304
 305 /* Returns true if RS contains no 1-bits, false otherwise. */
 306 bool
 307 range_set_is_empty (const struct range_set *rs)
 308 {
 309   return bt_count (&rs->bt) == 0;
 310 }
 311
 312 /* Returns the node representing the first contiguous region of
 313    1-bits in RS, or a null pointer if RS is empty.
 314    Any call to range_set_insert, range_set_delete, or
 315    range_set_allocate invalidates the returned node. */
 316 const struct range_set_node *
 317 range_set_first (const struct range_set *rs)
 318 {
 319   return first_node (rs);
 320 }
 321
 322 /* If NODE is nonnull, returns the node representing the next
 323    contiguous region of 1-bits in RS following NODE, or a null
 324    pointer if NODE is the last region in RS.
 325    If NODE is null, returns the first region in RS, as for
 326    range_set_first.
 327    Any call to range_set_insert, range_set_delete, or
 328    range_set_allocate invalidates the returned node. */
 329 const struct range_set_node *
 330 range_set_next (const struct range_set *rs, const struct range_set_node *node)
 331 {
 332   return (node != NULL
 333           ? next_node (rs, (struct range_set_node *) node)
 334           : first_node (rs));
 335 }
 336
 337 /* Returns the position of the first 1-bit in NODE. */
 338 unsigned long int
 339 range_set_node_get_start (const struct range_set_node *node)
 340 {
 341   return node->start;
 342 }
 343
 344 /* Returns one past the position of the last 1-bit in NODE. */
 345 unsigned long int
 346 range_set_node_get_end (const struct range_set_node *node)
 347 {
 348   return node->end;
 349 }
 350
 351 /* Returns the number of contiguous 1-bits in NODE. */
 352 unsigned long int
 353 range_set_node_get_width (const struct range_set_node *node)
 354 {
 355   return node->end - node->start;
 356 }
 357 \f
 358 /* Returns the range_set_node corresponding to the given
 359    BT_NODE.  Returns a null pointer if BT_NODE is null. */
 360 static struct range_set_node *
 361 bt_to_rs_node (const struct bt_node *bt_node)
 362 {
 363   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
 364 }
 365
 366 /* Compares `range_set_node's A and B and returns a strcmp-like
 367    return value. */
 368 static int
 369 compare_range_set_nodes (const struct bt_node *a_,
 370                          const struct bt_node *b_,
 371                          const void *aux UNUSED)
 372 {
 373   const struct range_set_node *a = bt_to_rs_node (a_);
 374   const struct range_set_node *b = bt_to_rs_node (b_);
 375
 376   return a->start < b->start ? -1 : a->start > b->start;
 377 }
 378
 379 /* Returns the first range_set_node in RS,
 380    or a null pointer if RS is empty. */
 381 static struct range_set_node *
 382 first_node (const struct range_set *rs)
 383 {
 384   return bt_to_rs_node (bt_first (&rs->bt));
 385 }
 386
 387 /* Returns the next range_set_node in RS after NODE,
 388    or a null pointer if NODE is the last node in RS. */
 389 static struct range_set_node *
 390 next_node (const struct range_set *rs, const struct range_set_node *node)
 391 {
 392   return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
 393 }
 394
 395 /* Deletes NODE from RS and frees it. */
 396 static void
 397 delete_node (struct range_set *rs, struct range_set_node *node)
 398 {
 399   bt_delete (&rs->bt, &node->bt_node);
 400   free (node);
 401 }
 402
 403 /* Deletes NODE from RS, frees it, and returns the following
 404    node. */
 405 static struct range_set_node *
 406 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
 407 {
 408   struct range_set_node *next = next_node (rs, node);
 409   delete_node (rs, node);
 410   return next;
 411 }
 412
 413 /* Returns the node in RS that would be just before POSITION if a
 414    range_set_node with `start' as POSITION were inserted.
 415    Returns a null pointer if POSITION is before any existing node
 416    in RS.  If POSITION would duplicate an existing region's
 417    start, returns that region. */
 418 static struct range_set_node *
 419 find_node_le (const struct range_set *rs, unsigned long int position)
 420 {
 421   struct range_set_node tmp;
 422   tmp.start = position;
 423   return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
 424 }
 425
 426 /* Creates a new region with the given START and END, inserts the
 427    region into RS, and returns the new region. */
 428 static struct range_set_node *
 429 insert_node (struct range_set *rs,
 430              unsigned long int start, unsigned long int end)
 431 {
 432   struct range_set_node *node = xmalloc (sizeof *node);
 433   struct bt_node *dummy;
 434   node->start = start;
 435   node->end = end;
 436   dummy = bt_insert (&rs->bt, &node->bt_node);
 437   assert (dummy == NULL);
 438   return node;
 439 }
 440
 441 /* Inserts the region START...END (exclusive) into RS given that
 442    the new region is "just before" NODE, that is, if NODE is
 443    nonnull, the new region is known not to overlap any node
 444    preceding NODE, and START precedes NODE's start; if NODE is
 445    null, then the new region is known to follow any and all
 446    regions already in RS. */
 447 static void
 448 insert_just_before (struct range_set *rs,
 449                     unsigned long int start, unsigned long int end,
 450                     struct range_set_node *node)
 451 {
 452   assert (node == NULL || start < node->start);
 453   if (node != NULL && end >= node->start)
 454     {
 455       /* New region overlaps NODE, so just extend NODE. */
 456       node->start = start;
 457       if (end > node->end)
 458         {
 459           node->end = end;
 460           merge_node_with_successors (rs, node);
 461         }
 462     }
 463   else
 464     {
 465       /* New region does not overlap NODE. */
 466       insert_node (rs, start, end);
 467     }
 468 }
 469
 470 /* Merges NODE in RS with its successors. */
 471 static void
 472 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
 473 {
 474   struct range_set_node *next;
 475
 476   while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
 477     {
 478       if (next->end > node->end)
 479         node->end = next->end;
 480       delete_node (rs, next);
 481     }
 482 }
 483
 484 /* Destroys range set RS.
 485    Helper function for range_set_create_pool. */
 486 static void
 487 destroy_pool (void *rs_)
 488 {
 489   struct range_set *rs = rs_;
 490   rs->pool = NULL;
 491   range_set_destroy (rs);
 492 }