1/* @ajax/mesh-omap: an ordered map from fixed-width keys (1..6 u64 words, compared word by word,
2 * first word first) to fixed-size values, kept in an AVL tree. It stands in for Rust's BTreeMap
3 * wherever the port needs its order: iteration, the first and last entries, and range queries
4 * (floor, ceiling, next, previous).
5 *
6 * Values live inside the tree's nodes; a pointer to one is valid until the map next changes.
7 * Iterating by key (first, then next after each key) stays correct when the loop removes or adds
8 * entries, which is how the port writes Rust's `retain` and `range(..).rev()` loops. */
9#ifndef MESH_OMAP_H
10#define MESH_OMAP_H
11
12#include <stdbool.h>
13#include <stddef.h>
14#include <stdint.h>
15
16#define MOMAP_MAX_KEY 6
17
18typedef struct momap momap;
19/* Releases what a value owns (not the value's own bytes). */
20typedef void (*momap_free_fn)(void *val);
21/* Copies src into dst (dst is uninitialised), deeply. */
22typedef void (*momap_copy_fn)(void *dst, const void *src);
23
24/* free_val and copy_val may be NULL: nothing to release, and a plain byte copy. */
25momap *momap_new(unsigned key_words, size_t val_size, momap_free_fn free_val, momap_copy_fn copy_val);
26void momap_free(momap *m); /* NULL is fine */
27void momap_clear(momap *m);
28momap *momap_clone(const momap *m);
29size_t momap_len(const momap *m);
30unsigned momap_key_words(const momap *m);
31size_t momap_val_size(const momap *m);
32
33/* The value under key, or NULL. */
34void *momap_get(const momap *m, const uint64_t *key);
35/* The value under key, inserted (zeroed) if absent; *fresh (if fresh) says which. */
36void *momap_put(momap *m, const uint64_t *key, bool *fresh);
37/* Removes key's entry, releasing its value; false if absent. */
38bool momap_del(momap *m, const uint64_t *key);
39/* Removes key's entry and moves its value into out (not released); false if absent. */
40bool momap_take(momap *m, const uint64_t *key, void *out);
41
42/* Navigation: the entry's value, its key copied into key_out (when not NULL), or NULL. */
43void *momap_first(const momap *m, uint64_t *key_out);
44void *momap_last(const momap *m, uint64_t *key_out);
45void *momap_next(const momap *m, const uint64_t *after, uint64_t *key_out);   /* smallest > after */
46void *momap_prev(const momap *m, const uint64_t *before, uint64_t *key_out);  /* largest < before */
47void *momap_floor(const momap *m, const uint64_t *at, uint64_t *key_out);     /* largest <= at */
48void *momap_ceil(const momap *m, const uint64_t *at, uint64_t *key_out);      /* smallest >= at */
49
50/* A cursor over every entry in key order, O(1) per step: for walks that don't change the map's keys
51 * (values may change). momap_iter_init then, while momap_iter_next gives a value, use it. */
52typedef struct {
53    const void *stack[96];
54    int top;
55    const momap *m;
56} momap_iter;
57void momap_iter_init(momap_iter *it, const momap *m);
58/* The next entry's value (its key in *key when key is not NULL), or NULL at the end. */
59void *momap_iter_next(momap_iter *it, const uint64_t **key);
60/* The same, copying a one-word key into *key. */
61void *momap_iter_next1(momap_iter *it, uint64_t *key);
62
63/* Moves every entry with key >= at into a new map (Rust's split_off). */
64momap *momap_split_off(momap *m, const uint64_t *at);
65
66/* One-word keys. */
67static inline void *momap_get1(const momap *m, uint64_t k) { return momap_get(m, &k); }
68static inline void *momap_put1(momap *m, uint64_t k, bool *fresh) { return momap_put(m, &k, fresh); }
69static inline bool momap_del1(momap *m, uint64_t k) { return momap_del(m, &k); }
70
71#endif