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