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