+static void *
+do_scan_forward (struct sparse_array *spar, union pointer *p, int level,
+ unsigned long int start, unsigned long int *found)
+{
+ if (level == 0)
+ {
+ int idx = scan_in_use_forward (p->leaf, start);
+ if (idx >= 0)
+ {
+ unsigned long int key = *found = (start & ~LEVEL_MASK) | idx;
+ return cache_leaf_element (spar, p->leaf, key);
+ }
+ }
+ return scan_internal_node_forward (spar, p->internal, level, start, found);
+}
+
+static void *
+scan_forward (const struct sparse_array *spar_, unsigned long int start,
+ unsigned long int *found)
+{
+ struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
+
+ /* Check the cache. */
+ if (start >> BITS_PER_LEVEL == spar->cache_ofs)
+ {
+ int idx = scan_in_use_forward (spar->cache, start);
+ if (idx >= 0)
+ {
+ *found = (start & ~LEVEL_MASK) | idx;
+ return leaf_element (spar, spar->cache, idx);
+ }
+ start = (start & ~LEVEL_MASK) + PTRS_PER_LEVEL;
+ if (start == 0)
+ return NULL;
+ }
+
+ /* Do the scan. */
+ if (!index_in_range (spar, start))
+ return NULL;
+ return do_scan_forward (spar, &spar->root, spar->height - 1, start, found);
+}
+
+/* Scans P, which is at LEVEL and within SPAR, and its subnodes,
+ for the in-use element with the greatest key less than or
+ equal to START. If such an element is found, returns a
+ pointer to it and stores its key in *FOUND; otherwise, returns
+ a null pointer and does not modify *FOUND. */