From 1852910ef0fd7393da62b88aee66ee092208748e Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 27 Apr 2024 12:41:58 +0200 Subject: Adding upstream version 5.3.1. Signed-off-by: Daniel Baumann --- lib/generic/map.c | 355 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 355 insertions(+) create mode 100644 lib/generic/map.c (limited to 'lib/generic/map.c') diff --git a/lib/generic/map.c b/lib/generic/map.c new file mode 100644 index 0000000..9fc3e34 --- /dev/null +++ b/lib/generic/map.c @@ -0,0 +1,355 @@ +/* + * critbit89 - A crit-bit tree implementation for strings in C89 + * Written by Jonas Gehring + * Implemented key-value storing by Marek Vavrusa + * SPDX-License-Identifier: GPL-3.0-or-later + * + * The code makes the assumption that malloc returns pointers aligned at at + * least a two-byte boundary. Since the C standard requires that malloc return + * pointers that can store any type, there are no commonly-used toolchains for + * which this assumption is false. + * + * See https://github.com/agl/critbit/blob/master/critbit.pdf for reference. + */ + +#include +#include +#include + +#include "map.h" +#include "lib/utils.h" + + /* Exports */ +#if defined _WIN32 || defined __CYGWIN__ + #define EXPORT __attribute__ ((dllexport)) +#else + #define EXPORT __attribute__ ((visibility ("default"))) +#endif + +#ifdef _MSC_VER /* MSVC */ + typedef unsigned __int8 uint8_t; + typedef unsigned __int32 uint32_t; + #ifdef _WIN64 + typedef signed __int64 intptr_t; + #else + typedef _W64 signed int intptr_t; + #endif +#else /* Not MSVC */ + #include +#endif + +typedef struct { + void* value; + uint8_t key[]; +} cb_data_t; + +typedef struct { + void *child[2]; + uint32_t byte; + uint8_t otherbits; +} cb_node_t; + +/* Return true if ptr is internal node. */ +static inline int ref_is_internal(const uint8_t *p) +{ + return 1 & (intptr_t)p; +} + +/* Get internal node. */ +static inline cb_node_t *ref_get_internal(uint8_t *p) +{ + return (cb_node_t *)(p - 1); +} + +/* Static helper functions */ +static void cbt_traverse_delete(map_t *map, void *top) +{ + uint8_t *p = top; + if (ref_is_internal(p)) { + cb_node_t *q = ref_get_internal(p); + cbt_traverse_delete(map, q->child[0]); + cbt_traverse_delete(map, q->child[1]); + mm_free(map->pool, q); + } else { + mm_free(map->pool, p); + } +} + +static int cbt_traverse_prefixed(void *top, + int (*callback)(const char *, void *, void *), void *baton) +{ + uint8_t *p = top; + cb_data_t *x = (cb_data_t *)top; + + if (ref_is_internal(p)) { + cb_node_t *q = ref_get_internal(p); + int ret = 0; + + ret = cbt_traverse_prefixed(q->child[0], callback, baton); + if (ret != 0) { + return ret; + } + ret = cbt_traverse_prefixed(q->child[1], callback, baton); + if (ret != 0) { + return ret; + } + return 0; + } + + return (callback)((const char *)x->key, x->value, baton); +} + +static cb_data_t *cbt_make_data(map_t *map, const uint8_t *str, size_t len, void *value) +{ + cb_data_t *x = mm_alloc(map->pool, sizeof(cb_data_t) + len); + if (x != NULL) { + x->value = value; + memcpy(x->key, str, len); + } + return x; +} + +/*! Like map_contains, but also set the value, if passed and found. */ +static int cbt_get(map_t *map, const char *str, void **value) +{ + const uint8_t *ubytes = (void *)str; + const size_t ulen = strlen(str); + uint8_t *p = map->root; + cb_data_t *x = NULL; + + if (p == NULL) { + return 0; + } + + while (ref_is_internal(p)) { + cb_node_t *q = ref_get_internal(p); + uint8_t c = 0; + int direction; + + if (q->byte < ulen) { + c = ubytes[q->byte]; + } + direction = (1 + (q->otherbits | c)) >> 8; + + p = q->child[direction]; + } + + x = (cb_data_t *)p; + if (strcmp(str, (const char *)x->key) == 0) { + if (value != NULL) { + *value = x->value; + } + return 1; + } + + return 0; +} + +/*! Returns non-zero if map contains str */ +EXPORT int map_contains(map_t *map, const char *str) +{ + return cbt_get(map, str, NULL); +} + +EXPORT void *map_get(map_t *map, const char *str) +{ + void *v = NULL; + cbt_get(map, str, &v); + return v; +} + +EXPORT int map_set(map_t *map, const char *str, void *val) +{ + const uint8_t *const ubytes = (void *)str; + const size_t ulen = strlen(str); + uint8_t *p = map->root; + uint8_t c = 0, *x = NULL; + uint32_t newbyte = 0; + uint32_t newotherbits = 0; + int direction = 0, newdirection = 0; + cb_node_t *newnode = NULL; + cb_data_t *data = NULL; + void **wherep = NULL; + + if (p == NULL) { + map->root = cbt_make_data(map, (const uint8_t *)str, ulen + 1, val); + if (map->root == NULL) { + return ENOMEM; + } + return 0; + } + + while (ref_is_internal(p)) { + cb_node_t *q = ref_get_internal(p); + c = 0; + if (q->byte < ulen) { + c = ubytes[q->byte]; + } + direction = (1 + (q->otherbits | c)) >> 8; + + p = q->child[direction]; + } + + data = (cb_data_t *)p; + for (newbyte = 0; newbyte < ulen; ++newbyte) { + if (data->key[newbyte] != ubytes[newbyte]) { + newotherbits = data->key[newbyte] ^ ubytes[newbyte]; + goto different_byte_found; + } + } + + if (data->key[newbyte] != 0) { + newotherbits = data->key[newbyte]; + goto different_byte_found; + } + data->value = val; + return 1; + +different_byte_found: + newotherbits |= newotherbits >> 1; + newotherbits |= newotherbits >> 2; + newotherbits |= newotherbits >> 4; + newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255; + c = data->key[newbyte]; + newdirection = (1 + (newotherbits | c)) >> 8; + + newnode = mm_alloc(map->pool, sizeof(cb_node_t)); + if (newnode == NULL) { + return ENOMEM; + } + + x = (uint8_t *)cbt_make_data(map, ubytes, ulen + 1, val); + if (x == NULL) { + mm_free(map->pool, newnode); + return ENOMEM; + } + + newnode->byte = newbyte; + newnode->otherbits = newotherbits; + newnode->child[1 - newdirection] = x; + + /* Insert into map */ + wherep = &map->root; + for (;;) { + cb_node_t *q; + p = *wherep; + if (!ref_is_internal(p)) { + break; + } + + q = ref_get_internal(p); + if (q->byte > newbyte) { + break; + } + if (q->byte == newbyte && q->otherbits > newotherbits) { + break; + } + + c = 0; + if (q->byte < ulen) { + c = ubytes[q->byte]; + } + direction = (1 + (q->otherbits | c)) >> 8; + wherep = q->child + direction; + } + + newnode->child[newdirection] = *wherep; + *wherep = (void *)(1 + (char *)newnode); + return 0; +} + +/*! Deletes str from the map, returns 0 on success */ +EXPORT int map_del(map_t *map, const char *str) +{ + const uint8_t *ubytes = (void *)str; + const size_t ulen = strlen(str); + uint8_t *p = map->root; + void **wherep = NULL, **whereq = NULL; + cb_node_t *q = NULL; + cb_data_t *data = NULL; + int direction = 0; + + if (map->root == NULL) { + return 1; + } + wherep = &map->root; + + while (ref_is_internal(p)) { + uint8_t c = 0; + whereq = wherep; + q = ref_get_internal(p); + + if (q->byte < ulen) { + c = ubytes[q->byte]; + } + direction = (1 + (q->otherbits | c)) >> 8; + wherep = q->child + direction; + p = *wherep; + } + + data = (cb_data_t *)p; + if (strcmp(str, (const char *)data->key) != 0) { + return 1; + } + mm_free(map->pool, p); + + if (!whereq) { + map->root = NULL; + return 0; + } + + *whereq = q->child[1 - direction]; + mm_free(map->pool, q); + return 0; +} + +/*! Clears the given map */ +EXPORT void map_clear(map_t *map) +{ + if (map->root) { + cbt_traverse_delete(map, map->root); + } + map->root = NULL; +} + +/*! Calls callback for all strings in map with the given prefix */ +EXPORT int map_walk_prefixed(map_t *map, const char *prefix, + int (*callback)(const char *, void *, void *), void *baton) +{ + if (!map) { + return 0; + } + + const uint8_t *ubytes = (void *)prefix; + const size_t ulen = strlen(prefix); + uint8_t *p = map->root; + uint8_t *top = p; + cb_data_t *data = NULL; + + if (p == NULL) { + return 0; + } + + while (ref_is_internal(p)) { + cb_node_t *q = ref_get_internal(p); + uint8_t c = 0; + int direction; + + if (q->byte < ulen) { + c = ubytes[q->byte]; + } + direction = (1 + (q->otherbits | c)) >> 8; + + p = q->child[direction]; + if (q->byte < ulen) { + top = p; + } + } + + data = (cb_data_t *)p; + if (strlen((const char *)data->key) < ulen || memcmp(data->key, prefix, ulen) != 0) { + return 0; /* No strings match */ + } + + return cbt_traverse_prefixed(top, callback, baton); +} -- cgit v1.2.3