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/compiler.h>
  33 #include <libpspp/pool.h>
  34
  35 #include "minmax.h"
  36 #include "xalloc.h"
  37
  38 static int compare_range_set_nodes (const struct bt_node *,
  39                                     const struct bt_node *,
  40                                     const void *aux);
  41 static void delete_node (struct range_set *, struct range_set_node *);
  42 static struct range_set_node *delete_node_get_next (struct range_set *,
  43                                                     struct range_set_node *);
  44 static struct range_set_node *find_node_le (const struct range_set *,
  45                                             unsigned long int position);
  46 static struct range_set_node *insert_node (struct range_set *,
  47                                            unsigned long int start,
  48                                            unsigned long int end);
  49 static void insert_just_before (struct range_set *,
  50                                 unsigned long int start, unsigned long int end,
  51                                 struct range_set_node *);
  52 static void merge_node_with_successors (struct range_set *,
  53                                         struct range_set_node *);
  54 static void destroy_pool (void *);
  55
  56 /* Creates and returns a new, empty range set. */
  57 struct range_set *
  58 range_set_create (void)
  59 {
  60   return range_set_create_pool (NULL);
  61 }
  62
  63 /* Creates and returns a new, empty range set in the given
  64    POOL. */
  65 struct range_set *
  66 range_set_create_pool (struct pool *pool)
  67 {
  68   struct range_set *rs = xmalloc (sizeof *rs);
  69   rs->pool = pool;
  70   if (pool != NULL)
  71     pool_register (pool, destroy_pool, rs);
  72   bt_init (&rs->bt, compare_range_set_nodes, NULL);
  73   rs->cache_end = 0;
  74   return rs;
  75 }
  76
  77 /* Creates and returns a clone of OLD range set in the given POOL
  78    (which may be null). */
  79 struct range_set *
  80 range_set_clone (const struct range_set *old, struct pool *pool)
  81 {
  82   struct range_set *new;
  83   struct range_set_node *node;
  84
  85   new = range_set_create_pool (pool);
  86   for (node = range_set_first__ (old); node != NULL;
  87        node = range_set_next__ (old, node))
  88     insert_node (new, node->start, node->end);
  89   return new;
  90 }
  91
  92 /* Destroys range set RS. */
  93 void
  94 range_set_destroy (struct range_set *rs)
  95 {
  96   if (rs != NULL)
  97     {
  98       if (rs->pool != NULL)
  99         pool_unregister (rs->pool, rs);
 100       while (!range_set_is_empty (rs))
 101         delete_node (rs, range_set_first__ (rs));
 102       free (rs);
 103     }
 104 }
 105
 106 /* Inserts the region starting at START and extending for WIDTH
 107    into RS. */
 108 void
 109 range_set_insert (struct range_set *rs,
 110                   unsigned long int start, unsigned long int width)
 111 {
 112   unsigned long int end = start + width;
 113   struct range_set_node *node;
 114
 115   assert (width == 0 || start + width - 1 >= start);
 116
 117   if (width == 0)
 118     return;
 119
 120   /* Invalidate cache. */
 121   rs->cache_end = 0;
 122
 123   node = find_node_le (rs, start);
 124   if (node != NULL)
 125     {
 126       if (start > node->end)
 127         {
 128           /* New region does not overlap NODE, but it might
 129              overlap the next node. */
 130           insert_just_before (rs, start, end, range_set_next__ (rs, node));
 131         }
 132       else if (end > node->end)
 133         {
 134           /* New region starts in the middle of NODE and
 135              continues past its end, so extend NODE, then merge
 136              it with any following node that it now potentially
 137              overlaps. */
 138           node->end = end;
 139           merge_node_with_successors (rs, node);
 140         }
 141       else
 142         {
 143           /* New region is completely contained by NODE, so
 144              there's nothing to do. */
 145         }
 146     }
 147   else
 148     {
 149       /* New region starts before any existing region, but it
 150          might overlap the first region. */
 151       insert_just_before (rs, start, end, range_set_first__ (rs));
 152     }
 153 }
 154
 155 /* Inserts the region starting at START and extending for WIDTH
 156    from RS. */
 157 void
 158 range_set_delete (struct range_set *rs,
 159                   unsigned long int start, unsigned long int width)
 160 {
 161   unsigned long int end = start + width;
 162   struct range_set_node *node;
 163
 164   assert (width == 0 || start + width - 1 >= start);
 165
 166   if (width == 0)
 167     return;
 168
 169   /* Invalidate cache. */
 170   rs->cache_end = 0;
 171
 172   node = find_node_le (rs, start);
 173   if (node == NULL)
 174     node = range_set_first__ (rs);
 175
 176   while (node != NULL && end > node->start)
 177     {
 178       if (start <= node->start)
 179         {
 180           if (end >= node->end)
 181             {
 182               /* Region to delete covers entire node. */
 183               node = delete_node_get_next (rs, node);
 184             }
 185           else
 186             {
 187               /* Region to delete covers only left part of node. */
 188               node->start = end;
 189               break;
 190             }
 191         }
 192       else if (start < node->end)
 193         {
 194           if (end < node->end)
 195             {
 196               /* Region to delete covers middle of the node, so
 197                  we have to split the node into two pieces. */
 198               unsigned long int old_node_end = node->end;
 199               node->end = start;
 200               insert_node (rs, end, old_node_end);
 201               break;
 202             }
 203           else
 204             {
 205               /* Region to delete covers only right part of
 206                  node. */
 207               node->end = start;
 208               node = range_set_next__ (rs, node);
 209             }
 210         }
 211       else
 212         node = range_set_next__ (rs, node);
 213     }
 214 }
 215
 216 /* Scans RS for its first 1-bit and deletes up to REQUEST
 217    contiguous 1-bits starting at that position.  Unless RS is
 218    completely empty, sets *START to the position of the first
 219    1-bit deleted and *WIDTH to the number actually deleted, which
 220    may be less than REQUEST if fewer contiguous 1-bits were
 221    present, and returns true.  If RS is completely empty, returns
 222    false. */
 223 bool
 224 range_set_allocate (struct range_set *rs, unsigned long int request,
 225                     unsigned long int *start, unsigned long int *width)
 226 {
 227   struct range_set_node *node;
 228   unsigned long int node_width;
 229
 230   assert (request > 0);
 231
 232   node = range_set_first__ (rs);
 233   if (node == NULL)
 234     return false;
 235   node_width = node->end - node->start;
 236
 237   *start = node->start;
 238   if (request < node_width)
 239     {
 240       *width = request;
 241       node->start += request;
 242     }
 243   else
 244     {
 245       *width = node_width;
 246       delete_node (rs, node);
 247     }
 248
 249   rs->cache_end = 0;
 250
 251   return true;
 252 }
 253
 254 /* Scans RS for and deletes the first contiguous run of REQUEST
 255    1-bits.  If successful, sets *START to the position of the
 256    first 1-bit deleted and returns true If RS does not contain a
 257    run of REQUEST or more contiguous 1-bits, returns false and
 258    does not modify RS. */
 259 bool
 260 range_set_allocate_fully (struct range_set *rs, unsigned long int request,
 261                           unsigned long int *start)
 262 {
 263   struct range_set_node *node;
 264
 265   assert (request > 0);
 266
 267   for (node = range_set_first__ (rs); node != NULL;
 268        node = range_set_next__ (rs, node))
 269     {
 270       unsigned long int node_width = node->end - node->start;
 271       if (node_width >= request)
 272         {
 273           *start = node->start;
 274           if (node_width > request)
 275             node->start += request;
 276           else
 277             delete_node (rs, node);
 278           rs->cache_end = 0;
 279           return true;
 280         }
 281     }
 282   return false;
 283 }
 284
 285 /* Returns true if there is a 1-bit at the given POSITION in RS,
 286    false otherwise. */
 287 bool
 288 range_set_contains (const struct range_set *rs_, unsigned long int position)
 289 {
 290   struct range_set *rs = (struct range_set *) rs_;
 291   if (position < rs->cache_end && position >= rs->cache_start)
 292     return rs->cache_value;
 293   else
 294     {
 295       struct range_set_node *node = find_node_le (rs, position);
 296       if (node != NULL)
 297         {
 298           if (position < node->end)
 299             {
 300               rs->cache_start = node->start;
 301               rs->cache_end = node->end;
 302               rs->cache_value = true;
 303               return true;
 304             }
 305           else
 306             {
 307               struct range_set_node *next = range_set_next__ (rs, node);
 308               rs->cache_start = node->end;
 309               rs->cache_end = next != NULL ? next->start : ULONG_MAX;
 310               rs->cache_value = false;
 311               return false;
 312             }
 313         }
 314       else
 315         {
 316           node = range_set_first__ (rs);
 317           rs->cache_start = 0;
 318           rs->cache_end = node != NULL ? node->start : ULONG_MAX;
 319           rs->cache_value = false;
 320           return false;
 321         }
 322     }
 323 }
 324 \f
 325 /* Compares `range_set_node's A and B and returns a strcmp-like
 326    return value. */
 327 static int
 328 compare_range_set_nodes (const struct bt_node *a_,
 329                          const struct bt_node *b_,
 330                          const void *aux UNUSED)
 331 {
 332   const struct range_set_node *a = range_set_node_from_bt__ (a_);
 333   const struct range_set_node *b = range_set_node_from_bt__ (b_);
 334
 335   return a->start < b->start ? -1 : a->start > b->start;
 336 }
 337
 338 /* Deletes NODE from RS and frees it. */
 339 static void
 340 delete_node (struct range_set *rs, struct range_set_node *node)
 341 {
 342   bt_delete (&rs->bt, &node->bt_node);
 343   free (node);
 344 }
 345
 346 /* Deletes NODE from RS, frees it, and returns the following
 347    node. */
 348 static struct range_set_node *
 349 delete_node_get_next (struct range_set *rs, struct range_set_node *node)
 350 {
 351   struct range_set_node *next = range_set_next__ (rs, node);
 352   delete_node (rs, node);
 353   return next;
 354 }
 355
 356 /* Returns the node in RS that would be just before POSITION if a
 357    range_set_node with `start' as POSITION were inserted.
 358    Returns a null pointer if POSITION is before any existing node
 359    in RS.  If POSITION would duplicate an existing region's
 360    start, returns that region. */
 361 static struct range_set_node *
 362 find_node_le (const struct range_set *rs, unsigned long int position)
 363 {
 364   struct range_set_node tmp;
 365   tmp.start = position;
 366   return range_set_node_from_bt__ (bt_find_le (&rs->bt, &tmp.bt_node));
 367 }
 368
 369 /* Creates a new region with the given START and END, inserts the
 370    region into RS, and returns the new region. */
 371 static struct range_set_node *
 372 insert_node (struct range_set *rs,
 373              unsigned long int start, unsigned long int end)
 374 {
 375   struct range_set_node *node = xmalloc (sizeof *node);
 376   struct bt_node *dummy;
 377   node->start = start;
 378   node->end = end;
 379   dummy = bt_insert (&rs->bt, &node->bt_node);
 380   assert (dummy == NULL);
 381   return node;
 382 }
 383
 384 /* Inserts the region START...END (exclusive) into RS given that
 385    the new region is "just before" NODE, that is, if NODE is
 386    nonnull, the new region is known not to overlap any node
 387    preceding NODE, and START precedes NODE's start; if NODE is
 388    null, then the new region is known to follow any and all
 389    regions already in RS. */
 390 static void
 391 insert_just_before (struct range_set *rs,
 392                     unsigned long int start, unsigned long int end,
 393                     struct range_set_node *node)
 394 {
 395   assert (node == NULL || start < node->start);
 396   if (node != NULL && end >= node->start)
 397     {
 398       /* New region overlaps NODE, so just extend NODE. */
 399       node->start = start;
 400       if (end > node->end)
 401         {
 402           node->end = end;
 403           merge_node_with_successors (rs, node);
 404         }
 405     }
 406   else
 407     {
 408       /* New region does not overlap NODE. */
 409       insert_node (rs, start, end);
 410     }
 411 }
 412
 413 /* Merges NODE in RS with its successors. */
 414 static void
 415 merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
 416 {
 417   struct range_set_node *next;
 418
 419   while ((next = range_set_next__ (rs, node)) != NULL
 420          && node->end >= next->start)
 421     {
 422       if (next->end > node->end)
 423         node->end = next->end;
 424       delete_node (rs, next);
 425     }
 426 }
 427
 428 /* Destroys range set RS.
 429    Helper function for range_set_create_pool. */
 430 static void
 431 destroy_pool (void *rs_)
 432 {
 433   struct range_set *rs = rs_;
 434   rs->pool = NULL;
 435   range_set_destroy (rs);
 436 }