src/libpspp/sparse-array.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2010, 2011 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 "gl/count-one-bits.h"
  30 #include "gl/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;
 538
 539       in_use = leaf->in_use[idx / LONG_BITS] << (LONG_BITS - 1 - ofs);
 540       if (in_use)
 541         return idx - count_leading_zeros (in_use);
 542       if (idx < LONG_BITS)
 543         return -1;
 544       idx = (idx | LONG_MASK) - LONG_BITS;
 545     }
 546 }
 547
 548 /* Returns the address of element with the given KEY in LEAF,
 549    which is a node in SPAR. */
 550 static inline void *
 551 leaf_element (const struct sparse_array *spar, struct leaf_node *leaf,
 552               unsigned int key)
 553 {
 554   key &= LEVEL_MASK;
 555   return (char *) leaf + SIZEOF_ALIGNED (*leaf) + (spar->elem_size * key);
 556 }
 557
 558 /* As leaf_element, returns the address of element with the given
 559    KEY in LEAF, which is a node in SPAR.  Also, updates SPAR's
 560    cache to contain LEAF. */
 561 static void *
 562 cache_leaf_element (struct sparse_array *spar, struct leaf_node *leaf,
 563                     unsigned long int key)
 564 {
 565   spar->cache = leaf;
 566   spar->cache_ofs = key >> BITS_PER_LEVEL;
 567   return leaf_element (spar, leaf, key);
 568 }
 569
 570 /* Returns the size of a leaf node in SPAR. */
 571 static inline size_t
 572 leaf_size (const struct sparse_array *spar)
 573 {
 574   return SIZEOF_ALIGNED (struct leaf_node) + spar->elem_size * PTRS_PER_LEVEL;
 575 }
 576
 577 /* Finds and returns the leaf node in SPAR that contains KEY.
 578    Returns null if SPAR does not have a leaf node that contains
 579    KEY. */
 580 static struct leaf_node *
 581 find_leaf_node (const struct sparse_array *spar_, unsigned long int key)
 582 {
 583   struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
 584   const union pointer *p;
 585   int level;
 586
 587   /* Check the cache first. */
 588   if (key >> BITS_PER_LEVEL == spar->cache_ofs)
 589     return spar->cache;
 590
 591   if (!index_in_range (spar, key))
 592     return NULL;
 593
 594   /* Descend through internal nodes. */
 595   p = &spar->root;
 596   for (level = spar->height - 1; level > 0; level--)
 597     {
 598       if (p->internal == NULL)
 599         return NULL;
 600       p = &p->internal->down[(key >> (level * BITS_PER_LEVEL)) & LEVEL_MASK];
 601     }
 602
 603   /* Update cache. */
 604   spar->cache = p->leaf;
 605   spar->cache_ofs = key >> BITS_PER_LEVEL;
 606
 607   return p->leaf;
 608 }
 609
 610 /* Reduces SPAR's height to the minimum needed value by
 611    eliminating levels that contain only a single entry for all
 612    0-bits. */
 613 static void
 614 decrease_height (struct sparse_array *spar)
 615 {
 616   while (spar->height > 1
 617          && spar->root.internal->count == 1
 618          && spar->root.internal->down[0].internal)
 619     {
 620       struct internal_node *p = spar->root.internal;
 621       spar->height--;
 622       spar->root = p->down[0];
 623       pool_free (spar->pool, p);
 624     }
 625 }
 626
 627 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 628    for the in-use element with the least key greater than or
 629    equal to START.  If such an element is found, returns a
 630    pointer to it and stores its key in *FOUND; otherwise, returns
 631    a null pointer and does not modify *FOUND. */
 632 static inline void *
 633 scan_internal_node_forward (struct sparse_array *spar,
 634                             struct internal_node *node,
 635                             int level, unsigned long int start,
 636                             unsigned long int *found)
 637 {
 638   int shift = level * BITS_PER_LEVEL;
 639   int count = node->count;
 640   int i;
 641
 642   for (i = (start >> shift) & LEVEL_MASK; i < PTRS_PER_LEVEL; i++)
 643     {
 644       union pointer *q = &node->down[i];
 645       if (level > 1 ? q->internal != NULL : q->leaf != NULL)
 646         {
 647           void *element = do_scan_forward (spar, q, level - 1, start, found);
 648           if (element)
 649             return element;
 650           if (--count == 0)
 651             return NULL;
 652         }
 653
 654       start &= ~((1ul << shift) - 1);
 655       start += 1ul << shift;
 656     }
 657   return NULL;
 658 }
 659
 660 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 661    for the in-use element with the least key greater than or
 662    equal to START.  If such an element is found, returns a
 663    pointer to it and stores its key in *FOUND; otherwise, returns
 664    a null pointer and does not modify *FOUND. */
 665 static void *
 666 do_scan_forward (struct sparse_array *spar, union pointer *p, int level,
 667                  unsigned long int start, unsigned long int *found)
 668 {
 669   if (level == 0)
 670     {
 671       int idx = scan_in_use_forward (p->leaf, start);
 672       if (idx >= 0)
 673         {
 674           unsigned long int key = *found = (start & ~LEVEL_MASK) | idx;
 675           return cache_leaf_element (spar, p->leaf, key);
 676         }
 677     }
 678   return scan_internal_node_forward (spar, p->internal, level, start, found);
 679 }
 680
 681 static void *
 682 scan_forward (const struct sparse_array *spar_, unsigned long int start,
 683               unsigned long int *found)
 684 {
 685   struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
 686
 687   /* Check the cache. */
 688   if (start >> BITS_PER_LEVEL == spar->cache_ofs)
 689     {
 690       int idx = scan_in_use_forward (spar->cache, start);
 691       if (idx >= 0)
 692         {
 693           *found = (start & ~LEVEL_MASK) | idx;
 694           return leaf_element (spar, spar->cache, idx);
 695         }
 696       start = (start & ~LEVEL_MASK) + PTRS_PER_LEVEL;
 697       if (start == 0)
 698         return NULL;
 699     }
 700
 701   /* Do the scan. */
 702   if (!index_in_range (spar, start))
 703     return NULL;
 704   return do_scan_forward (spar, &spar->root, spar->height - 1, start, found);
 705 }
 706
 707 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 708    for the in-use element with the greatest key less than or
 709    equal to START.  If such an element is found, returns a
 710    pointer to it and stores its key in *FOUND; otherwise, returns
 711    a null pointer and does not modify *FOUND. */
 712 static inline void *
 713 scan_internal_node_reverse (struct sparse_array *spar,
 714                             struct internal_node *node,
 715                             int level, unsigned long int start,
 716                             unsigned long int *found)
 717 {
 718   int shift = level * BITS_PER_LEVEL;
 719   int count = node->count;
 720   int i;
 721
 722   for (i = (start >> shift) & LEVEL_MASK; i >= 0; i--)
 723     {
 724       union pointer *q = &node->down[i];
 725       if (level > 1 ? q->internal != NULL : q->leaf != NULL)
 726         {
 727           void *element = do_scan_reverse (spar, q, level - 1, start, found);
 728           if (element)
 729             return element;
 730           if (--count == 0)
 731             return NULL;
 732         }
 733
 734       start |= (1ul << shift) - 1;
 735       start -= 1ul << shift;
 736     }
 737   return NULL;
 738 }
 739
 740 /* Scans P, which is at LEVEL and within SPAR, and its subnodes,
 741    for the in-use element with the greatest key less than or
 742    equal to START.  If such an element is found, returns a
 743    pointer to it and stores its key in *FOUND; otherwise, returns
 744    a null pointer and does not modify *FOUND. */
 745 static void *
 746 do_scan_reverse (struct sparse_array *spar, union pointer *p, int level,
 747                  unsigned long int start, unsigned long int *found)
 748 {
 749   if (level == 0)
 750     {
 751       int idx = scan_in_use_reverse (p->leaf, start);
 752       if (idx >= 0)
 753         {
 754           unsigned long int key = *found = (start & ~LEVEL_MASK) | idx;
 755           return cache_leaf_element (spar, p->leaf, key);
 756         }
 757       else
 758         return NULL;
 759     }
 760   return scan_internal_node_reverse (spar, p->internal, level, start, found);
 761 }
 762
 763 static void *
 764 scan_reverse (const struct sparse_array *spar_, unsigned long int start,
 765               unsigned long int *found)
 766 {
 767   struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
 768
 769   /* Check the cache. */
 770   if (start >> BITS_PER_LEVEL == spar->cache_ofs)
 771     {
 772       int idx = scan_in_use_reverse (spar->cache, start);
 773       if (idx >= 0)
 774         {
 775           *found = (start & ~LEVEL_MASK) | idx;
 776           return leaf_element (spar, spar->cache, idx);
 777         }
 778       start |= LEVEL_MASK;
 779       if (start < PTRS_PER_LEVEL)
 780         return NULL;
 781       start -= PTRS_PER_LEVEL;
 782     }
 783   else
 784     {
 785       if (spar->height == 0)
 786         return NULL;
 787       else if (spar->height < MAX_HEIGHT)
 788         {
 789           unsigned long int max_key;
 790           max_key = (1ul << (spar->height * BITS_PER_LEVEL)) - 1;
 791           start = MIN (start, max_key);
 792         }
 793     }
 794   return do_scan_reverse (spar, &spar->root, spar->height - 1, start, found);
 795 }