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