src/libpspp/sparse-array.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 #include <config.h>
  18
  19 #include <libpspp/sparse-array.h>
  20
  21 #include <limits.h>
  22 #include <string.h>
  23
  24 #include <libpspp/assertion.h>
  25 #include <libpspp/misc.h>
  26 #include <libpspp/pool.h>
  27
  28 /* Sparse array data structure.
  29
  30    The sparse array is implemented in terms of a "radix tree", a
  31    multiway tree in which a set of bits drawn from the key
  32    determine the child chosen at each level during a search.  The
  33    most-significant bits determine a child of the root, the next
  34    bits determine a child of that child, and so on, until the
  35    least-significant bits determine a leaf node.
  36
  37    In this implementation, the branching factor at each level is
  38    held constant at 2**BITS_PER_LEVEL.  The tree is only made as
  39    tall as need be for the currently largest key, and nodes that
  40    would be entirely empty are not allocated at all.  The
  41    elements are stored in the leaf nodes. */
  42
  43 /* Number of bits from the key used as the index at each level. */
  44 #define BITS_PER_LEVEL 5
  45
  46 /* Branching factor. */
  47 #define PTRS_PER_LEVEL (1u << BITS_PER_LEVEL)
  48
  49 /* Maximum height. */
  50 #define LONG_BITS (sizeof (unsigned long int) * CHAR_BIT)
  51 #define MAX_HEIGHT DIV_RND_UP (LONG_BITS, BITS_PER_LEVEL)
  52
  53 /* Bit-mask for index. */
  54 #define LEVEL_MASK ((1ul << BITS_PER_LEVEL) - 1)
  55
  56 /* Pointer to an internal node or a leaf node.
  57    Pointers in internal nodes at level 1 point to leaf nodes;
  58    other pointers point to internal nodes. */
  59 union pointer
  60   {
  61     struct internal_node *internal;
  62     struct leaf_node *leaf;
  63   };
  64
  65 /* A sparse array. */
  66 struct sparse_array
  67   {
  68     struct pool *pool;          /* Pool used for allocations. */
  69     size_t elem_size;           /* Element size, rounded for alignment. */
  70     unsigned long count;        /* Number of elements in tree. */
  71
  72     /* Radix tree. */
  73     union pointer root;         /* Root of tree. */
  74     int height;                 /* 0=empty tree;
  75                                    1=root points to leaf,
  76                                    2=root points to internal node
  77                                      that points to leaves,
  78                                    and so on. */
  79
  80     /* Cache for speeding up access. */
  81     unsigned long int cache_ofs; /* Group of keys that cache points to,
  82                                     shifted right BITS_PER_LEVEL bits;
  83                                     ULONG_MAX for empty cache. */
  84     struct leaf_node *cache;    /* Cached leaf node, or a null
  85                                    pointer for a negative cache. */
  86   };
  87
  88 /* An internal node in the radix tree. */
  89 struct internal_node
  90   {
  91     int count;                  /* Number of nonnull children. */
  92     union pointer down[PTRS_PER_LEVEL]; /* Children. */
  93   };
  94
  95 /* A leaf node in the radix tree. */
  96 struct leaf_node
  97   {
  98     /* Bit-vector of elements that are in use. */
  99     unsigned long int in_use[DIV_RND_UP (PTRS_PER_LEVEL, LONG_BITS)];
 100     /* element_type elements[PTRS_PER_LEVEL]; */
 101   };
 102
 103 /* Returns SIZE rounded up to a safe alignment. */
 104 #define ALIGN_SIZE(SIZE) ROUND_UP (SIZE, sizeof (long int))
 105
 106 /* Returns the size of EXPR_OR_TYPE rounded up to a safe
 107    alignment. */
 108 #define SIZEOF_ALIGNED(EXPR_OR_TYPE) ALIGN_SIZE (sizeof (EXPR_OR_TYPE))
 109
 110 static inline bool index_in_range (const struct sparse_array *,
 111                                    unsigned long int);
 112 static inline bool is_in_use (const struct leaf_node *, unsigned int);
 113 static inline bool any_in_use (const struct leaf_node *);
 114 static inline void set_in_use (struct leaf_node *, unsigned int);
 115 static inline void unset_in_use (struct leaf_node *, unsigned int);
 116 static inline int scan_in_use (struct leaf_node *, unsigned int);
 117 static inline void *leaf_element (const struct sparse_array *,
 118                                   struct leaf_node *, unsigned int);
 119 static inline size_t leaf_size (const struct sparse_array *);
 120
 121 static struct leaf_node *find_leaf_node (const struct sparse_array *,
 122                                          unsigned long int);
 123 static void decrease_height (struct sparse_array *);
 124 static void *scan_leaf (struct sparse_array *, struct leaf_node *,
 125                         unsigned long int, unsigned long int *);
 126 static void *do_scan (struct sparse_array *, union pointer *, int,
 127                       unsigned long int, unsigned long int *);
 128 \f
 129 /* Creates and returns a new sparse array that will contain
 130    elements that are ELEM_SIZE bytes in size. */
 131 struct sparse_array *
 132 sparse_array_create (size_t elem_size)
 133 {
 134   return sparse_array_create_pool (NULL, elem_size);
 135 }
 136
 137 /* Creates and returns a new sparse array that will contain
 138    elements that are ELEM_SIZE bytes in size.  Data in the sparse
 139    array will be allocated from POOL, which may be null. */
 140 struct sparse_array *
 141 sparse_array_create_pool (struct pool *pool, size_t elem_size)
 142 {
 143   struct sparse_array *spar = pool_malloc (pool, sizeof *spar);
 144   spar->pool = pool;
 145   spar->elem_size = ALIGN_SIZE (elem_size);
 146   spar->height = 0;
 147   spar->root.leaf = NULL;
 148   spar->count = 0;
 149   spar->cache_ofs = ULONG_MAX;
 150   return spar;
 151 }
 152
 153 /* Destroys SPAR node pointed to by P at the given LEVEL. */
 154 static void
 155 do_destroy (struct sparse_array *spar, union pointer *p, int level)
 156 {
 157   if (level > 0)
 158     {
 159       struct internal_node *node = p->internal;
 160       int count = node->count;
 161       int i;
 162
 163       for (i = 0; ; i++)
 164         {
 165           union pointer *q = &p->internal->down[i];
 166           if (level > 1 ? q->internal != NULL : q->leaf != NULL)
 167             {
 168               do_destroy (spar, q, level - 1);
 169               if (--count == 0)
 170                 break;
 171             }
 172         }
 173       pool_free (spar->pool, p->internal);
 174     }
 175   else if (level == 0)
 176     pool_free (spar->pool, p->leaf);
 177 }
 178
 179 /* Destroys SPAR.
 180    Any elements in SPAR are deallocated.  Thus, if per-element
 181    destruction is necessary, it should be done before destroying
 182    the sparse array. */
 183 void
 184 sparse_array_destroy (struct sparse_array *spar)
 185 {
 186   do_destroy (spar, &spar->root, spar->height - 1);
 187   pool_free (spar->pool, spar);
 188 }
 189
 190 /* Returns the number of elements in SPAR. */
 191 unsigned long int
 192 sparse_array_count (const struct sparse_array *spar)
 193 {
 194   return spar->count;
 195 }
 196
 197 /* Increases SPAR's height by 1, allowing it to hold
 198    PTRS_PER_LEVEL times more elements. */
 199 static void
 200 increase_height (struct sparse_array *spar)
 201 {
 202   assert (spar->height < MAX_HEIGHT);
 203   spar->height++;
 204   if (spar->height == 1)
 205     spar->root.leaf = pool_zalloc (spar->pool, leaf_size (spar));
 206   else
 207     {
 208       struct internal_node *new_root;
 209       new_root = pool_zalloc (spar->pool, sizeof *new_root);
 210       new_root->count = 1;
 211       new_root->down[0] = spar->root;
 212       spar->root.internal = new_root;
 213     }
 214 }
 215
 216 /* Finds the leaf node in SPAR that contains the element for KEY.
 217    SPAR must be tall enough to hold KEY.
 218    Creates the leaf if it doesn't already exist. */
 219 static struct leaf_node *
 220 create_leaf_node (struct sparse_array *spar, unsigned long int key)
 221 {
 222   union pointer *p;
 223   int *count = NULL;
 224   int level;
 225
 226   assert (index_in_range (spar, key));
 227
 228   /* Short-circuit everything if KEY is in the leaf cache. */
 229   if (key >> BITS_PER_LEVEL == spar->cache_ofs && spar->cache != NULL)
 230     return spar->cache;
 231
 232   /* Descend through internal nodes. */
 233   p = &spar->root;
 234   for (level = spar->height - 1; level > 0; level--)
 235     {
 236       if (p->internal == NULL)
 237         {
 238           p->internal = pool_zalloc (spar->pool, sizeof *p->internal);
 239           ++*count;
 240         }
 241
 242       count = &p->internal->count;
 243       p = &p->internal->down[(key >> (level * BITS_PER_LEVEL)) & LEVEL_MASK];
 244     }
 245
 246   /* Create leaf if necessary. */
 247   if (p->leaf == NULL)
 248     {
 249       p->leaf = pool_zalloc (spar->pool, leaf_size (spar));
 250       ++*count;
 251     }
 252
 253   /* Update cache. */
 254   spar->cache = p->leaf;
 255   spar->cache_ofs = key >> BITS_PER_LEVEL;
 256
 257   return p->leaf;
 258 }
 259
 260 /* Inserts into SPAR an element with the given KEY, which must not
 261    already exist in SPAR.
 262    Returns the new element for the caller to initialize. */
 263 void *
 264 sparse_array_insert (struct sparse_array *spar, unsigned long int key)
 265 {
 266   struct leaf_node *leaf;
 267
 268   while (!index_in_range (spar, key))
 269     increase_height (spar);
 270
 271   spar->count++;
 272
 273   leaf = create_leaf_node (spar, key);
 274   assert (!is_in_use (leaf, key));
 275   set_in_use (leaf, key);
 276   return leaf_element (spar, leaf, key);
 277 }
 278
 279 /* Finds and returns the element in SPAR with the given KEY.
 280    Returns a null pointer if KEY does not exist in SPAR. */
 281 void *
 282 sparse_array_get (const struct sparse_array *spar, unsigned long int key)
 283 {
 284   if (index_in_range (spar, key))
 285     {
 286       struct leaf_node *leaf = find_leaf_node (spar, key);
 287       if (leaf != NULL && is_in_use (leaf, key))
 288         return leaf_element (spar, leaf, key);
 289     }
 290   return NULL;
 291 }
 292
 293 /* Removes the element with the given KEY from SPAR.
 294    Returns true if an element was removed, false if SPAR hadn't
 295    contained an element with the given KEY.
 296
 297    If elements need to be destructed, then the caller should have
 298    already taken care of it before calling this function; the
 299    element's content must be considered freed and of
 300    indeterminate value after it is removed. */
 301 bool
 302 sparse_array_remove (struct sparse_array *spar, unsigned long int key)
 303 {
 304   union pointer *path[MAX_HEIGHT], **last;
 305   struct leaf_node *leaf;
 306   union pointer *p;
 307   int level;
 308
 309   if (!index_in_range (spar, key))
 310     return false;
 311
 312   /* Find and free element in leaf. */
 313   leaf = find_leaf_node (spar, key);
 314   if (leaf == NULL || !is_in_use (leaf, key))
 315     return false;
 316 #if ASSERT_LEVEL >= 10
 317   memset (leaf_element (spar, leaf, key), 0xcc, spar->elem_size);
 318 #endif
 319   unset_in_use (leaf, key);
 320   spar->count--;
 321   if (any_in_use (leaf))
 322     return true;
 323
 324   /* The leaf node is empty.
 325      Retrace the path of internal nodes traversed to the leaf. */
 326   p = &spar->root;
 327   last = path;
 328   for (level = spar->height - 1; level > 0; level--)
 329     {
 330       *last++ = p;
 331       p = &p->internal->down[(key >> (level * BITS_PER_LEVEL)) & LEVEL_MASK];
 332     }
 333
 334   /* Free the leaf node and prune it from the tree. */
 335   spar->cache_ofs = ULONG_MAX;
 336   pool_free (spar->pool, leaf);
 337   p->leaf = NULL;
 338
 339   /* Update counts in the internal nodes above the leaf.
 340      Free any internal nodes that become empty. */
 341   while (last > path)
 342     {
 343       p = *--last;
 344       if (--p->internal->count > 0)
 345         {
 346           if (p == &spar->root)
 347             decrease_height (spar);
 348           return true;
 349         }
 350
 351       pool_free (spar->pool, p->internal);
 352       p->internal = NULL;
 353     }
 354   spar->height = 0;
 355   return true;
 356 }
 357
 358 /* Scans SPAR in increasing order of keys for in-use elements.
 359    If SKIP is NULL, the scan starts from key 0;
 360    otherwise, it starts just after key *SKIP.
 361    If an element is found, returns it and stores the element's
 362    key into *FOUND; otherwise, returns a null pointer and does
 363    not modify *FOUND. */
 364 void *
 365 sparse_array_scan (const struct sparse_array *spar_, unsigned long int *skip,
 366                    unsigned long int *found)
 367 {
 368   struct sparse_array *spar = (struct sparse_array *) spar_;
 369   unsigned long int start;
 370
 371   /* Find our starting point. */
 372   if (skip != NULL)
 373     {
 374       start = *skip + 1;
 375       if (start == 0)
 376         return NULL;
 377     }
 378   else
 379     start = 0;
 380
 381   /* Check the cache. */
 382   if (start >> BITS_PER_LEVEL == spar->cache_ofs)
 383     {
 384       void *p = scan_leaf (spar, spar->cache, start, found);
 385       if (p)
 386         return p;
 387       start &= ~LEVEL_MASK;
 388       start += PTRS_PER_LEVEL;
 389       if (start == 0)
 390         return NULL;
 391     }
 392
 393   /* Do the scan. */
 394   if (!index_in_range (spar, start))
 395     return NULL;
 396   return do_scan (spar, &spar->root, spar->height - 1, start, found);
 397 }
 398 \f
 399 /* Returns true iff KEY is in the range of keys currently
 400    represented by SPAR. */
 401 static inline bool
 402 index_in_range (const struct sparse_array *spar, unsigned long int key)
 403 {
 404   return (spar->height == 0 ? false
 405           : spar->height >= MAX_HEIGHT ? true
 406           : key < (1ul << (spar->height * BITS_PER_LEVEL)));
 407 }
 408
 409 /* Returns true iff LEAF contains an in-use element with the
 410    given KEY. */
 411 static inline bool
 412 is_in_use (const struct leaf_node *leaf, unsigned int key)
 413 {
 414   key &= LEVEL_MASK;
 415   return (leaf->in_use[key / LONG_BITS] & (1ul << (key % LONG_BITS))) != 0;
 416 }
 417
 418 /* Returns true iff LEAF contains any in-use elements. */
 419 static inline bool
 420 any_in_use (const struct leaf_node *leaf)
 421 {
 422   size_t i;
 423   for (i = 0; i < sizeof leaf->in_use / sizeof *leaf->in_use; i++)
 424     if (leaf->in_use[i])
 425       return true;
 426   return false;
 427 }
 428
 429 /* Marks element KEY in LEAF as in-use. */
 430 static inline void
 431 set_in_use (struct leaf_node *leaf, unsigned int key)
 432 {
 433   key &= LEVEL_MASK;
 434   leaf->in_use[key / LONG_BITS] |= 1ul << (key % LONG_BITS);
 435 }
 436
 437 /* Marks element KEY in LEAF as not in-use. */
 438 static inline void
 439 unset_in_use (struct leaf_node *leaf, unsigned int key)
 440 {
 441   key &= LEVEL_MASK;
 442   leaf->in_use[key / LONG_BITS] &= ~(1ul << (key % LONG_BITS));
 443 }
 444
 445 /* Returns the number of trailing 0-bits in X.
 446    Undefined if X is zero. */
 447 static inline int
 448 count_trailing_zeros (unsigned long int x)
 449 {
 450   /* This algorithm is from _Hacker's Delight_ section 5.4. */
 451   int n = 1;
 452
 453 #define COUNT_STEP(BITS)                        \
 454     if (!(x & ((1ul << (BITS)) - 1)))           \
 455       {                                         \
 456         n += BITS;                              \
 457         x >>= BITS;                             \
 458       }
 459
 460 #if ULONG_MAX >> 31 >> 31 >> 2
 461   COUNT_STEP (64);
 462 #endif
 463 #if ULONG_MAX >> 31 >> 1
 464   COUNT_STEP (32);
 465 #endif
 466   COUNT_STEP (16);
 467   COUNT_STEP (8);
 468   COUNT_STEP (4);
 469   COUNT_STEP (2);
 470
 471   return n - (x & 1);
 472 }
 473
 474 /* Returns the least index of the in-use element in LEAF greater
 475    than or equal to IDX. */
 476 static inline int
 477 scan_in_use (struct leaf_node *leaf, unsigned int idx)
 478 {
 479   for (; idx < PTRS_PER_LEVEL; idx = (idx & ~(LONG_BITS - 1)) + LONG_BITS)
 480     {
 481       int ofs = idx % LONG_BITS;
 482       unsigned long int in_use = leaf->in_use[idx / LONG_BITS] >> ofs;
 483       if (!in_use)
 484         continue;
 485       return count_trailing_zeros (in_use) + idx;
 486     }
 487   return -1;
 488 }
 489
 490 /* Returns the address of element with the given KEY in LEAF,
 491    which is a node in SPAR. */
 492 static inline void *
 493 leaf_element (const struct sparse_array *spar, struct leaf_node *leaf,
 494               unsigned int key)
 495 {
 496   key &= LEVEL_MASK;
 497   return (char *) leaf + SIZEOF_ALIGNED (*leaf) + (spar->elem_size * key);
 498 }
 499
 500 /* Returns the size of a leaf node in SPAR. */
 501 static inline size_t
 502 leaf_size (const struct sparse_array *spar)
 503 {
 504   return SIZEOF_ALIGNED (struct leaf_node) + spar->elem_size * PTRS_PER_LEVEL;
 505 }
 506
 507 /* Finds and returns the leaf node in SPAR that contains KEY.
 508    Returns null if SPAR does not have a leaf node that contains
 509    KEY. */
 510 static struct leaf_node *
 511 find_leaf_node (const struct sparse_array *spar_, unsigned long int key)
 512 {
 513   struct sparse_array *spar = (struct sparse_array *) spar_;
 514   const union pointer *p;
 515   int level;
 516
 517   assert (index_in_range (spar, key));
 518
 519   /* Check the cache first. */
 520   if (key >> BITS_PER_LEVEL == spar->cache_ofs)
 521     return spar->cache;
 522
 523   /* Descend through internal nodes. */
 524   p = &spar->root;
 525   for (level = spar->height - 1; level > 0; level--)
 526     {
 527       if (p->internal == NULL)
 528         return NULL;
 529       p = &p->internal->down[(key >> (level * BITS_PER_LEVEL)) & LEVEL_MASK];
 530     }
 531
 532   /* Update cache. */
 533   spar->cache = p->leaf;
 534   spar->cache_ofs = key >> BITS_PER_LEVEL;
 535
 536   return p->leaf;
 537 }
 538
 539 /* Reduces SPAR's height to the minimum needed value by
 540    eliminating levels that contain only a single entry for all
 541    0-bits. */
 542 static void
 543 decrease_height (struct sparse_array *spar)
 544 {
 545   while (spar->height > 1
 546          && spar->root.internal->count == 1
 547          && spar->root.internal->down[0].internal)
 548     {
 549       struct internal_node *p = spar->root.internal;
 550       spar->height--;
 551       spar->root = p->down[0];
 552       pool_free (spar->pool, p);
 553     }
 554 }
 555
 556 /* Scans leaf node LEAF, which is in SPAR, for the in-use element
 557    with the least key greater than or equal to START.  If such an
 558    element is found, returns a pointer to it and stores its key
 559    in *FOUND; otherwise, returns a null pointer and does not
 560    modify *FOUND. */
 561 static void *
 562 scan_leaf (struct sparse_array *spar, struct leaf_node *leaf,
 563            unsigned long int start, unsigned long int *found)
 564 {
 565   int idx = scan_in_use (leaf, start & LEVEL_MASK);
 566   if (idx >= 0)
 567     {
 568       *found = (start & ~LEVEL_MASK) | idx;
 569       spar->cache = leaf;
 570       spar->cache_ofs = *found >> BITS_PER_LEVEL;
 571       return leaf_element (spar, leaf, idx);
 572     }
 573
 574   return NULL;
 575 }
 576
 577 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 578    for the in-use element with the least key greater than or
 579    equal to START.  If such an element is found, returns a
 580    pointer to it and stores its key in *FOUND; otherwise, returns
 581    a null pointer and does not modify *FOUND. */
 582 static inline void *
 583 scan_internal_node (struct sparse_array *spar, struct internal_node *node,
 584                     int level, unsigned long int start,
 585                     unsigned long int *found)
 586 {
 587   int shift = level * BITS_PER_LEVEL;
 588   int count = node->count;
 589   int i;
 590
 591   for (i = (start >> shift) & LEVEL_MASK; i < PTRS_PER_LEVEL; i++)
 592     {
 593       union pointer *q = &node->down[i];
 594       if (level > 1 ? q->internal != NULL : q->leaf != NULL)
 595         {
 596           void *element = do_scan (spar, q, level - 1, start, found);
 597           if (element)
 598             return element;
 599           if (--count == 0)
 600             return NULL;
 601         }
 602
 603       start &= ~((1ul << shift) - 1);
 604       start += 1ul << shift;
 605     }
 606   return NULL;
 607 }
 608
 609 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 610    for the in-use element with the least key greater than or
 611    equal to START.  If such an element is found, returns a
 612    pointer to it and stores its key in *FOUND; otherwise, returns
 613    a null pointer and does not modify *FOUND. */
 614 static void *
 615 do_scan (struct sparse_array *spar, union pointer *p, int level,
 616          unsigned long int start, unsigned long int *found)
 617 {
 618   return (level == 0
 619           ? scan_leaf (spar, p->leaf, start, found)
 620           : scan_internal_node (spar, p->internal, level, start, found));
 621 }
 622