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 #if __GNUC__ >= 4
 451   return __builtin_ctzl (x);
 452 #else /* not GCC 4+ */
 453   /* This algorithm is from _Hacker's Delight_ section 5.4. */
 454   int n = 1;
 455
 456 #define COUNT_STEP(BITS)                        \
 457     if (!(x & ((1ul << (BITS)) - 1)))           \
 458       {                                         \
 459         n += BITS;                              \
 460         x >>= BITS;                             \
 461       }
 462
 463 #if ULONG_MAX >> 31 >> 31 >> 2
 464   COUNT_STEP (64);
 465 #endif
 466 #if ULONG_MAX >> 31 >> 1
 467   COUNT_STEP (32);
 468 #endif
 469   COUNT_STEP (16);
 470   COUNT_STEP (8);
 471   COUNT_STEP (4);
 472   COUNT_STEP (2);
 473
 474   return n - (x & 1);
 475 #endif /* not GCC 4+ */
 476 }
 477
 478 /* Returns the least index of the in-use element in LEAF greater
 479    than or equal to IDX. */
 480 static inline int
 481 scan_in_use (struct leaf_node *leaf, unsigned int idx)
 482 {
 483   for (; idx < PTRS_PER_LEVEL; idx = (idx & ~(LONG_BITS - 1)) + LONG_BITS)
 484     {
 485       int ofs = idx % LONG_BITS;
 486       unsigned long int in_use = leaf->in_use[idx / LONG_BITS] >> ofs;
 487       if (!in_use)
 488         continue;
 489       return count_trailing_zeros (in_use) + idx;
 490     }
 491   return -1;
 492 }
 493
 494 /* Returns the address of element with the given KEY in LEAF,
 495    which is a node in SPAR. */
 496 static inline void *
 497 leaf_element (const struct sparse_array *spar, struct leaf_node *leaf,
 498               unsigned int key)
 499 {
 500   key &= LEVEL_MASK;
 501   return (char *) leaf + SIZEOF_ALIGNED (*leaf) + (spar->elem_size * key);
 502 }
 503
 504 /* Returns the size of a leaf node in SPAR. */
 505 static inline size_t
 506 leaf_size (const struct sparse_array *spar)
 507 {
 508   return SIZEOF_ALIGNED (struct leaf_node) + spar->elem_size * PTRS_PER_LEVEL;
 509 }
 510
 511 /* Finds and returns the leaf node in SPAR that contains KEY.
 512    Returns null if SPAR does not have a leaf node that contains
 513    KEY. */
 514 static struct leaf_node *
 515 find_leaf_node (const struct sparse_array *spar_, unsigned long int key)
 516 {
 517   struct sparse_array *spar = (struct sparse_array *) spar_;
 518   const union pointer *p;
 519   int level;
 520
 521   assert (index_in_range (spar, key));
 522
 523   /* Check the cache first. */
 524   if (key >> BITS_PER_LEVEL == spar->cache_ofs)
 525     return spar->cache;
 526
 527   /* Descend through internal nodes. */
 528   p = &spar->root;
 529   for (level = spar->height - 1; level > 0; level--)
 530     {
 531       if (p->internal == NULL)
 532         return NULL;
 533       p = &p->internal->down[(key >> (level * BITS_PER_LEVEL)) & LEVEL_MASK];
 534     }
 535
 536   /* Update cache. */
 537   spar->cache = p->leaf;
 538   spar->cache_ofs = key >> BITS_PER_LEVEL;
 539
 540   return p->leaf;
 541 }
 542
 543 /* Reduces SPAR's height to the minimum needed value by
 544    eliminating levels that contain only a single entry for all
 545    0-bits. */
 546 static void
 547 decrease_height (struct sparse_array *spar)
 548 {
 549   while (spar->height > 1
 550          && spar->root.internal->count == 1
 551          && spar->root.internal->down[0].internal)
 552     {
 553       struct internal_node *p = spar->root.internal;
 554       spar->height--;
 555       spar->root = p->down[0];
 556       pool_free (spar->pool, p);
 557     }
 558 }
 559
 560 /* Scans leaf node LEAF, which is in SPAR, for the in-use element
 561    with the least key greater than or equal to START.  If such an
 562    element is found, returns a pointer to it and stores its key
 563    in *FOUND; otherwise, returns a null pointer and does not
 564    modify *FOUND. */
 565 static void *
 566 scan_leaf (struct sparse_array *spar, struct leaf_node *leaf,
 567            unsigned long int start, unsigned long int *found)
 568 {
 569   int idx = scan_in_use (leaf, start & LEVEL_MASK);
 570   if (idx >= 0)
 571     {
 572       *found = (start & ~LEVEL_MASK) | idx;
 573       spar->cache = leaf;
 574       spar->cache_ofs = *found >> BITS_PER_LEVEL;
 575       return leaf_element (spar, leaf, idx);
 576     }
 577
 578   return NULL;
 579 }
 580
 581 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 582    for the in-use element with the least key greater than or
 583    equal to START.  If such an element is found, returns a
 584    pointer to it and stores its key in *FOUND; otherwise, returns
 585    a null pointer and does not modify *FOUND. */
 586 static inline void *
 587 scan_internal_node (struct sparse_array *spar, struct internal_node *node,
 588                     int level, unsigned long int start,
 589                     unsigned long int *found)
 590 {
 591   int shift = level * BITS_PER_LEVEL;
 592   int count = node->count;
 593   int i;
 594
 595   for (i = (start >> shift) & LEVEL_MASK; i < PTRS_PER_LEVEL; i++)
 596     {
 597       union pointer *q = &node->down[i];
 598       if (level > 1 ? q->internal != NULL : q->leaf != NULL)
 599         {
 600           void *element = do_scan (spar, q, level - 1, start, found);
 601           if (element)
 602             return element;
 603           if (--count == 0)
 604             return NULL;
 605         }
 606
 607       start &= ~((1ul << shift) - 1);
 608       start += 1ul << shift;
 609     }
 610   return NULL;
 611 }
 612
 613 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 614    for the in-use element with the least key greater than or
 615    equal to START.  If such an element is found, returns a
 616    pointer to it and stores its key in *FOUND; otherwise, returns
 617    a null pointer and does not modify *FOUND. */
 618 static void *
 619 do_scan (struct sparse_array *spar, union pointer *p, int level,
 620          unsigned long int start, unsigned long int *found)
 621 {
 622   return (level == 0
 623           ? scan_leaf (spar, p->leaf, start, found)
 624           : scan_internal_node (spar, p->internal, level, start, found));
 625 }
 626