Flush the journal after every write.
[pspp] / 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 }