diff options
| -rw-r--r-- | map.c | 298 | ||||
| -rw-r--r-- | map.h | 34 |
2 files changed, 332 insertions, 0 deletions
@@ -0,0 +1,298 @@ +/* Crit-bit tree based map which supports lookups based on unique + * prefixes as well as ordered iteration. + * + * Based on public domain code from Rusty Russel, Adam Langley + * and D. J. Bernstein. + * + * Further information about the data structure can be found at: + * http://cr.yp.to/critbit.htm + * http://github.com/agl/critbit + * http://ccodearchive.net/info/strmap.html + */ +#include <stdlib.h> +#include <string.h> +#include <errno.h> +#include <inttypes.h> +#include "map.h" + +typedef struct Node Node; + +struct Map { /* struct holding either an item with value v and key u.s or an internal node */ + union { + Node *n; + const char *s; + } u; + void *v; /* value stored in the map, if non NULL u.s holds the corresponding key */ +}; + +struct Node { + Map child[2]; /* These point to strings or nodes. */ + size_t byte_num; /* The byte number where first bit differs. */ + uint8_t bit_num; /* The bit where these children differ. */ +}; + +/* Closest key to this in a non-empty map. */ +static Map *closest(Map *n, const char *key) +{ + size_t len = strlen(key); + const uint8_t *bytes = (const uint8_t *)key; + + /* Anything with NULL value is an internal node. */ + while (!n->v) { + uint8_t direction = 0; + + if (n->u.n->byte_num < len) { + uint8_t c = bytes[n->u.n->byte_num]; + direction = (c >> n->u.n->bit_num) & 1; + } + n = &n->u.n->child[direction]; + } + return n; +} + +void *map_get(const Map *map, const char *key) +{ + /* Not empty map? */ + if (map->u.n) { + Map *n = closest((Map *)map, key); + if (strcmp(key, n->u.s) == 0) + return n->v; + } + return NULL; +} + +void *map_closest(const Map *map, const char *prefix) +{ + errno = 0; + void *v = map_get(map, prefix); + if (v) + return v; + const Map *m = map_prefix(map, prefix); + if (!m->v) + errno = ENOENT; + return m->v; +} + +bool map_put(Map *map, const char *k, const void *value) +{ + size_t len = strlen(k); + const uint8_t *bytes = (const uint8_t *)k; + Map *n; + Node *newn; + size_t byte_num; + uint8_t bit_num, new_dir; + char *key; + + if (!value) { + errno = EINVAL; + return false; + } + + if (!(key = strdup(k))) { + errno = ENOMEM; + return false; + } + + /* Empty map? */ + if (!map->u.n) { + map->u.s = key; + map->v = (void *)value; + return true; + } + + /* Find closest existing key. */ + n = closest(map, key); + + /* Find where they differ. */ + for (byte_num = 0; n->u.s[byte_num] == key[byte_num]; byte_num++) { + if (key[byte_num] == '\0') { + /* All identical! */ + free(key); + return false; + } + } + + /* Find which bit differs */ + uint8_t diff = (uint8_t)n->u.s[byte_num] ^ bytes[byte_num]; + /* TODO: bit_num = 31 - __builtin_clz(diff); ? */ + for (bit_num = 0; diff >>= 1; bit_num++); + + /* Which direction do we go at this bit? */ + new_dir = ((bytes[byte_num]) >> bit_num) & 1; + + /* Allocate new node. */ + newn = malloc(sizeof(*newn)); + if (!newn) { + free(key); + errno = ENOMEM; + return false; + } + newn->byte_num = byte_num; + newn->bit_num = bit_num; + newn->child[new_dir].v = (void *)value; + newn->child[new_dir].u.s = key; + + /* Find where to insert: not closest, but first which differs! */ + n = map; + while (!n->v) { + uint8_t direction = 0; + + if (n->u.n->byte_num > byte_num) + break; + /* Subtle: bit numbers are "backwards" for comparison */ + if (n->u.n->byte_num == byte_num && n->u.n->bit_num < bit_num) + break; + + if (n->u.n->byte_num < len) { + uint8_t c = bytes[n->u.n->byte_num]; + direction = (c >> n->u.n->bit_num) & 1; + } + n = &n->u.n->child[direction]; + } + + newn->child[!new_dir] = *n; + n->u.n = newn; + n->v = NULL; + return true; +} + +void *map_delete(Map *map, const char *key) +{ + size_t len = strlen(key); + const uint8_t *bytes = (const uint8_t *)key; + Map *parent = NULL, *n; + void *value = NULL; + uint8_t direction; + + /* Empty map? */ + if (!map->u.n) { + errno = ENOENT; + return NULL; + } + + /* Find closest, but keep track of parent. */ + n = map; + /* Anything with NULL value is a node. */ + while (!n->v) { + uint8_t c = 0; + + parent = n; + if (n->u.n->byte_num < len) { + c = bytes[n->u.n->byte_num]; + direction = (c >> n->u.n->bit_num) & 1; + } else { + direction = 0; + } + n = &n->u.n->child[direction]; + } + + /* Did we find it? */ + if (strcmp(key, n->u.s)) { + errno = ENOENT; + return false; + } + + free((char*)n->u.s); + value = n->v; + + if (!parent) { + /* We deleted last node. */ + map->u.n = NULL; + } else { + Node *old = parent->u.n; + /* Raise other node to parent. */ + *parent = old->child[!direction]; + free(old); + } + + return value; +} + +static bool iterate(Map n, bool (*handle)(const char *, void *, void *), const void *data) +{ + if (n.v) + return handle(n.u.s, n.v, (void *)data); + + return iterate(n.u.n->child[0], handle, data) + && iterate(n.u.n->child[1], handle, data); +} + +void map_iterate(const Map *map, bool (*handle)(const char *, void *, void *), const void *data) +{ + /* Empty map? */ + if (!map->u.n) + return; + + iterate(*map, handle, data); +} + +const Map *map_prefix(const Map *map, const char *prefix) +{ + const Map *n, *top; + size_t len = strlen(prefix); + const uint8_t *bytes = (const uint8_t *)prefix; + + /* Empty map -> return empty map. */ + if (!map->u.n) + return map; + + top = n = map; + + /* We walk to find the top, but keep going to check prefix matches. */ + while (!n->v) { + uint8_t c = 0, direction; + + if (n->u.n->byte_num < len) + c = bytes[n->u.n->byte_num]; + + direction = (c >> n->u.n->bit_num) & 1; + n = &n->u.n->child[direction]; + if (c) + top = n; + } + + if (strncmp(n->u.s, prefix, len)) { + /* Convenient return for prefixes which do not appear in map. */ + static const Map empty_map; + return &empty_map; + } + + return top; +} + +static void clear(Map n) +{ + if (!n.v) { + clear(n.u.n->child[0]); + clear(n.u.n->child[1]); + free(n.u.n); + } else { + free((char*)n.u.s); + } +} + +void map_clear(Map *map) +{ + if (map->u.n) + clear(*map); + map->u.n = NULL; + map->v = NULL; +} + +bool map_empty(const Map *map) +{ + return map->u.n == NULL; +} + +Map *map_new(void) +{ + return calloc(1, sizeof(Map)); +} + +void map_free(Map *map) +{ + if (!map) + return; + map_clear(map); + free(map); +} @@ -0,0 +1,34 @@ +#ifndef MAP_H +#define MAP_H + +#include <stdbool.h> + +typedef struct Map Map; + +/* Allocate a new map. */ +Map *map_new(void); +/* Retrieves a value, or NULL if it isn't in the map */ +void *map_get(const Map*, const char *key); +/* Returns the corresponding value if the given prefix is unique. + * Otherwise NULL, if no such prefix exists then errno is set to ENOENT. */ +void *map_closest(const Map*, const char *prefix); +/* Place a member in the map. This returns false if we run out of memory + * (errno = ENOMEM), or if that key already appears in the map (errno = EEXIST). */ +bool map_put(Map*, const char *key, const void *value); +/* Remove a member from the map. Returns the removed entry or NULL + * if there was no entry found using the given key*/ +void *map_delete(Map*, const char *key); +/* Ordered iteration over a map, call handle for every entry. If handle + * returns false, the iteration will stop. */ +void map_iterate(const Map*, bool (*handle)(const char *key, void *value, void *data), const void *data); +/* Return a submap matching a prefix. This returns a pointer into the + * original map, so don't alter the map while using the return value. */ +const Map *map_prefix(const Map*, const char *prefix); +/* Test whether the map is empty i.e. contains no elements */ +bool map_empty(const Map*); +/* Remove every member from the map. The map will be empty after this. */ +void map_clear(Map*); +/* Release all memory associated with this map */ +void map_free(Map*); + +#endif |