return NULL;
}
+void *intmap_before_(const struct intmap *map, intmap_index_t *indexp)
+{
+ const struct intmap *n, *prev = NULL;
+ intmap_index_t index = (*indexp) - 1;
+
+ /* Special case of overflow */
+ if (index == (intmap_index_t)-1ULL)
+ goto none_left;
+
+ /* Special case of empty map */
+ if (intmap_empty_(map))
+ goto none_left;
+
+ /* Follow down, until prefix differs. */
+ n = map;
+ while (!n->v) {
+ int crit = critbit(n);
+ u8 direction;
+ intmap_index_t prefix, idx;
+
+ idx = (index >> crit);
+ direction = idx & 1;
+
+ /* Leave critbit in place: we can't shift by 64 anyway */
+ idx |= 1;
+ prefix = n->u.n->prefix_and_critbit >> crit;
+
+ /* If this entire tree is less than index, take last */
+ if (idx > prefix)
+ return intmap_last_(n, indexp);
+ /* If this entire tree is greater than index, we're past it. */
+ else if (idx < prefix)
+ goto try_lesser_tree;
+
+ /* Remember lesser tree for backtracking */
+ if (direction)
+ prev = n;
+ n = &n->u.n->child[direction];
+ }
+
+ /* Found a predecessor? */
+ if (n->u.i <= index) {
+ errno = 0;
+ *indexp = n->u.i;
+ return n->v;
+ }
+
+try_lesser_tree:
+ /* If we ever took a lesser branch, go back to lesser branch */
+ if (prev)
+ return intmap_last_(&prev->u.n->child[0], indexp);
+
+none_left:
+ errno = ENOENT;
+ return NULL;
+}
+
void *intmap_last_(const struct intmap *map, intmap_index_t *indexp)
{
const struct intmap *n;
tcon_cast((smap), sintmap_canary, \
sintmap_after_(sintmap_unwrap_(smap), (indexp)))
+/**
+ * uintmap_before - get the closest preceding index in an unsigned intmap
+ * @umap: the typed intmap to iterate through.
+ * @indexp: the succeeding index (may not exist)
+ *
+ * Returns NULL if the there is no entry < @indexp, otherwise
+ * populates *@indexp and returns the highest entry < @indexp.
+ */
+#define uintmap_before(umap, indexp) \
+ tcon_cast((umap), uintmap_canary, \
+ intmap_before_(uintmap_unwrap_(umap), (indexp)))
+
+void *intmap_before_(const struct intmap *map, intmap_index_t *indexp);
+
+/**
+ * sintmap_before - get the closest preceding index in a signed intmap
+ * @smap: the typed intmap to iterate through.
+ * @indexp: the succeeding index (may not exist)
+ *
+ * Returns NULL if the there is no entry < @indexp, otherwise
+ * populates *@indexp and returns the highest entry < @indexp.
+ */
+#define sintmap_before(smap, indexp) \
+ tcon_cast((smap), sintmap_canary, \
+ sintmap_before_(sintmap_unwrap_(smap), (indexp)))
+
/**
* uintmap_last - get last value in an unsigned intmap
* @umap: the typed intmap to iterate through.
return ret;
}
+static inline void *sintmap_before_(const struct intmap *map,
+ sintmap_index_t *indexp)
+{
+ intmap_index_t i = SINTMAP_OFF(*indexp);
+ void *ret = intmap_before_(map, &i);
+ *indexp = SINTMAP_UNOFF(i);
+ return ret;
+}
+
static inline void *sintmap_last_(const struct intmap *map,
sintmap_index_t *indexp)
{
bool last = true;
/* Must be in order, must contain value. */
+ prev = 256;
+ for (v = uintmap_last(map, &i); v; v = uintmap_before(map, &i)) {
+ if (i >= prev)
+ return false;
+ if (*v != i)
+ return false;
+ prev = i;
+ }
+
prev = -1;
for (v = uintmap_first(map, &i); v; v = uintmap_after(map, &i)) {
if (i <= prev)
bool last = true;
/* Must be in order, must contain value. */
+ prev = 0x80000000ULL;
+ for (v = sintmap_last(map, &i); v; v = sintmap_before(map, &i)) {
+ if (i >= prev)
+ return false;
+ if (*v != i)
+ return false;
+ prev = i;
+ }
+
prev = -0x80000001ULL;
for (v = sintmap_first(map, &i); v; v = sintmap_after(map, &i)) {
if (i <= prev)
return last;
}
-int main(void)
+int main(int argc, char *argv[])
{
umap umap;
smap smap;
uintmap_init(&umap);
sintmap_init(&smap);
+ if (argc > 1)
+ srandom(atoi(argv[1]));
+
for (i = 0; i < NUM; i++) {
urandoms[i] = random();
srandoms[i] = random();
last = (uintmap_last(map, &last_idx) == v);
}
+ if (!last)
+ return false;
+
+ prev = INT_MAX;
+ for (v = uintmap_last(map, &i); v; v = uintmap_before(map, &i)) {
+ if ((int64_t)i >= prev)
+ return false;
+ if (*v != i)
+ return false;
+ prev = i;
+ last = (uintmap_first(map, &last_idx) == v);
+ }
+
if (!last)
return false;
prev = i;
}
+ if (!last)
+ return false;
+
+ prev = 0x80000001ULL;
+ for (v = sintmap_last(map, &i); v; v = sintmap_before(map, &i)) {
+ if (i >= prev)
+ return false;
+ if (*v != i)
+ return false;
+ prev = i;
+ last = (sintmap_first(map, &last_idx) == v);
+ }
if (!last)
return false;