From 576e5a70230f8313ed084dc87062c2f30dcd2489 Mon Sep 17 00:00:00 2001 From: Egor Date: Sun, 22 Oct 2023 23:04:17 +0300 Subject: [PATCH] combine trie.h and map_dynarr.h into map.h --- Makefile | 8 ++-- src/common.h | 6 +-- src/map.h | 82 ++++++++++++++++++++++++++++++++++++++ src/map_dynarr.c | 2 +- src/map_dynarr.h | 34 ---------------- src/{trie.c => map_trie.c} | 3 +- src/trie.h | 44 -------------------- 7 files changed, 91 insertions(+), 88 deletions(-) create mode 100644 src/map.h delete mode 100644 src/map_dynarr.h rename src/{trie.c => map_trie.c} (99%) delete mode 100644 src/trie.h diff --git a/Makefile b/Makefile index a964cf9..fb4bd7a 100644 --- a/Makefile +++ b/Makefile @@ -8,7 +8,6 @@ SOURCES := \ src/netsock.c \ src/passwd.c \ src/util.c -SOURCES += src/trie.c HEADERS := \ src/common.h \ src/config.h \ @@ -18,12 +17,15 @@ HEADERS := \ src/netpoll.h \ src/netsock.h \ src/passwd.h \ - src/trie.h \ - src/map_dynarr.h \ + src/map.h \ src/util.h -include config.mk +SOURCES += src/map_trie.c +#SOURCES += src/map_dynarr.c +#CFLAGS += -DUSE_MAP_DYNARR +#CFLAGS.w32 += -DUSE_MAP_DYNARR .PHONY: all clean all: $(TARGET) $(if $(CC.w32),$(TARGET).exe,) setpass clean: diff --git a/src/common.h b/src/common.h index 5f89599..7062f1d 100644 --- a/src/common.h +++ b/src/common.h @@ -3,11 +3,7 @@ #include "netsock.h" #include "netpoll.h" #include "config.h" -#ifdef USE_MAP_DYNARR -#include "map_dynarr.h" -#else -#include "trie.h" -#endif +#include "map.h" #include #ifdef HAS_TLS #include diff --git a/src/map.h b/src/map.h new file mode 100644 index 0000000..b7a5c7c --- /dev/null +++ b/src/map.h @@ -0,0 +1,82 @@ +#ifndef MAP_H_ +#define MAP_H_ +#include +#if defined(__has_c_attribute) +# if __has_c_attribute(nodiscard) +# define NODISCARD [[nodiscard]] +# else +# define NODISCARD +# endif +#else +# define NODISCARD +#endif + +#ifdef USE_MAP_DYNARR +/* all complexity is in terms of n = number of elements */ +struct map_dynarr_value { + char *key; + void *value; +}; +struct map_dynarr { + struct map_dynarr_value *ptr; + size_t len, cap; +}; +typedef struct map_dynarr map_t; +struct trie_find { + char *key; + struct { void *value; } *n, _n; + map_t *_root; + int _cap; +}; +#else +/* all complexity is in terms of n = strlen(key) and s = size of the character set */ +struct trie_node { + unsigned char key; + unsigned char len; + unsigned char cap; + void *value; + struct trie_node *parent; + struct trie_node *data[1]; +}; +typedef struct trie_node *map_t; +struct trie_find { + struct trie_node *n; + size_t len; + size_t cap; + char key[1]; +}; +#endif + +/* A map abstract data type with following properties: + * - keys are lexicographically-sorted unique NUL-terminated strings + * - values are non-NULL pointers + * - a NULL value is synonymous with absence of a key + * - keys are owned by the map, values are not. + * - traversal can fail with memory allocation errors (sadly) + * - the map can't be modified during traversal + * + * A map is created by allocating and zero-initializing an object of type + * map_t. All map functions take a pointer to map_t. + */ + +/* Return the associated value for a given key. + * Trie complexity: O(n log s) + * Dynarr complexity: O(log n) */ +void *map_get(map_t *root, const char *key); +/* Associate a new value with a given key. + * Returns 0 on success, -1 on allocation error. + * If oldvalue is not NULL, it receives the old value of key. + * Trie complexity: O(ns) + * Dynarr complexity: O(n) */ +NODISCARD int map_set(map_t *root, const char *key, const void *value, void **oldvalue); +/* Remove a key. + * Same as associating a key to NULL. No allocation failures. */ +#define map_unset(root, key, oldvalue) ((void)map_set((root), (key), 0, (oldvalue))) +/* Removes all keys from the map and frees any associated memory. + * The map_t is reset to zero-initialized state and can be used again. + * Trie complexity: O(ns) + * Dynarr complexity: O(n) */ +void map_free(map_t *root); +NODISCARD int trie_findfirst(struct trie_find **pf, map_t *root); +NODISCARD int trie_findnext(struct trie_find **pf); +#endif diff --git a/src/map_dynarr.c b/src/map_dynarr.c index 55c0c5b..6d92ada 100644 --- a/src/map_dynarr.c +++ b/src/map_dynarr.c @@ -1,4 +1,4 @@ -#include "map_dynarr.h" +#include "map.h" #include #include static int ent_find(map_t *root, const char *key, int *found) diff --git a/src/map_dynarr.h b/src/map_dynarr.h deleted file mode 100644 index be06882..0000000 --- a/src/map_dynarr.h +++ /dev/null @@ -1,34 +0,0 @@ -#ifndef MAP_DYNARR_H_ -#define MAP_DYNARR_H_ -#include -#if defined(__has_c_attribute) -# if __has_c_attribute(nodiscard) -# define NODISCARD [[nodiscard]] -# else -# define NODISCARD -# endif -#else -# define NODISCARD -#endif -struct map_dynarr_value { - char *key; - void *value; -}; -struct map_dynarr { - struct map_dynarr_value *ptr; - size_t len, cap; -}; -typedef struct map_dynarr map_t; -void *map_get(map_t *root, const char *key); -NODISCARD int map_set(map_t *root, const char *key, const void *value, void **oldvalue); -#define map_unset(root, key, oldvalue) ((void)map_set((root), (key), 0, (oldvalue))) -void map_free(map_t *root); -struct trie_find { - char *key; - struct { void *value; } *n, _n; - map_t *_root; - int _cap; -}; -NODISCARD int trie_findfirst(struct trie_find **pf, map_t *root); -NODISCARD int trie_findnext(struct trie_find **pf); -#endif diff --git a/src/trie.c b/src/map_trie.c similarity index 99% rename from src/trie.c rename to src/map_trie.c index d9b2f75..36ed58c 100644 --- a/src/trie.c +++ b/src/map_trie.c @@ -1,4 +1,4 @@ -#include "trie.h" +#include "map.h" #include #include #define trie_is_end(e, n) ((e) >= (n)->len) @@ -132,6 +132,7 @@ void map_free(map_t *root) { n = p; } } + *root = 0; } int trie_findnext(struct trie_find **pf) { struct trie_find *f = *pf; diff --git a/src/trie.h b/src/trie.h deleted file mode 100644 index 20a26d8..0000000 --- a/src/trie.h +++ /dev/null @@ -1,44 +0,0 @@ -#ifndef TRIE_H_ -#define TRIE_H_ -#include -#ifdef __cplusplus -extern "C" { -#endif -#if defined(__has_c_attribute) -# if __has_c_attribute(nodiscard) -# define NODISCARD [[nodiscard]] -# else -# define NODISCARD -# endif -#else -# define NODISCARD -#endif -// all complexity is in terms of n = strlen(key) and s = size of the character set -struct trie_node { - unsigned char key; - unsigned char len; - unsigned char cap; - void *value; - struct trie_node *parent; - struct trie_node *data[1]; -}; -typedef struct trie_node *map_t; -// get value from trie O(n log s) -void *map_get(map_t *root, const char *key); -// set value in trie O(ns) -NODISCARD int map_set(map_t *root, const char *key, const void *value, void **oldvalue); -#define map_unset(root, key, oldvalue) ((void)map_set((root), (key), 0, (oldvalue))) -// free a trie -void map_free(map_t *root); -struct trie_find { - struct trie_node *n; - size_t len; - size_t cap; - char key[1]; -}; -NODISCARD int trie_findfirst(struct trie_find **pf, map_t *root); -NODISCARD int trie_findnext(struct trie_find **pf); -#ifdef __cplusplus -} -#endif -#endif -- 2.56.0