1 /*
2 * critbit89 - A crit-bit map implementation for strings in C89
3 * Written by Jonas Gehring <jonas@jgehring.net>
4 * SPDX-License-Identifier: GPL-3.0-or-later
5 */
6
7 /**
8 * @file map.h
9 * @brief A Crit-bit tree key-value map implementation.
10 *
11 * @warning If the user provides a custom allocator, it must return addresses aligned to 2B boundary.
12 *
13 * # Example usage:
14 *
15 * @code{.c}
16 * map_t map = map_make(NULL);
17 *
18 * // Custom allocator (optional)
19 * map.malloc = &mymalloc;
20 * map.baton = &mymalloc_context;
21 *
22 * // Insert k-v pairs
23 * int values = { 42, 53, 64 };
24 * if (map_set(&map, "princess", &values[0]) != 0 ||
25 * map_set(&map, "prince", &values[1]) != 0 ||
26 * map_set(&map, "leia", &values[2]) != 0) {
27 * fail();
28 * }
29 *
30 * // Test membership
31 * if (map_contains(&map, "leia")) {
32 * success();
33 * }
34 *
35 * // Prefix search
36 * int i = 0;
37 * int count(const char *k, void *v, void *ext) { (*(int *)ext)++; return 0; }
38 * if (map_walk_prefixed(map, "princ", count, &i) == 0) {
39 * printf("%d matches\n", i);
40 * }
41 *
42 * // Delete
43 * if (map_del(&map, "badkey") != 0) {
44 * fail(); // No such key
45 * }
46 *
47 * // Clear the map
48 * map_clear(&map);
49 * @endcode
50 *
51 * \addtogroup generics
52 * @{
53 */
54
55 #pragma once
56
57 #include <stddef.h>
58
59 #ifdef __cplusplus
60 extern "C" {
61 #endif
62
63 struct knot_mm; /* avoid the unnecessary include */
64
65 /** Main data structure */
66 typedef struct {
67 void *root;
68 struct knot_mm *pool;
69 } map_t;
70
71 /** Creates an new empty critbit map. Pass NULL for malloc+free. */
map_make(struct knot_mm * pool)72 static inline map_t map_make(struct knot_mm *pool)
73 {
74 return (map_t){ .root = NULL, .pool = pool };
75 }
76
77 /** Returns non-zero if map contains str */
78 int map_contains(map_t *map, const char *str);
79
80 /** Returns value if map contains str. Note: NULL may mean two different things. */
81 void *map_get(map_t *map, const char *str);
82
83 /** Inserts str into map. Returns 0 if new, 1 if replaced, or ENOMEM. */
84 int map_set(map_t *map, const char *str, void *val);
85
86 /** Deletes str from the map, returns 0 on success */
87 int map_del(map_t *map, const char *str);
88
89 /** Clears the given map */
90 void map_clear(map_t *map);
91
92 /**
93 * Calls callback for all strings in map
94 * See @fn map_walk_prefixed() for documentation on parameters.
95 */
96 #define map_walk(map, callback, baton) \
97 map_walk_prefixed((map), "", (callback), (baton))
98
99 /**
100 * Calls callback for all strings in map with the given prefix.
101 * Returns value immediately if a callback returns nonzero.
102 *
103 * @param map
104 * @param prefix required string prefix (empty => all strings)
105 * @param callback callback parameters are (key, value, baton)
106 * @param baton passed uservalue
107 */
108 int map_walk_prefixed(map_t *map, const char *prefix,
109 int (*callback)(const char *, void *, void *), void *baton);
110
111
112 #ifdef __cplusplus
113 }
114 #endif
115
116 /** @} */
117