From b9e1bc37ac463431cc0b397e4cea8cf9c8bf4ab8 Mon Sep 17 00:00:00 2001 From: Egor Date: Tue, 21 Jan 2025 04:57:57 +0200 Subject: [PATCH] remove map_trie implementation --- Makefile | 10 +- config.example.mk | 1 - src/{map_dynarr.c => map.c} | 6 +- src/map.h | 37 ++------ src/map_trie.c | 181 ------------------------------------ 5 files changed, 12 insertions(+), 223 deletions(-) rename src/{map_dynarr.c => map.c} (86%) delete mode 100644 src/map_trie.c diff --git a/Makefile b/Makefile index 98312d4..2f1adfd 100644 --- a/Makefile +++ b/Makefile @@ -9,6 +9,7 @@ SOURCES := \ src/netpoll.c \ src/netsock.c \ src/passwd.c \ + src/map.c \ src/util.c \ src/crypt_blowfish.c HEADERS := \ @@ -34,15 +35,6 @@ CXXFLAGS += -DHAS_LUA $(shell pkg-config --cflags lua5.4) LDLIBS += $(shell pkg-config --libs lua5.4) endif -ifndef USE_MAP_DYNARR -SOURCES += src/map_trie.c -else -SOURCES += src/map_dynarr.c -CFLAGS += -DUSE_MAP_DYNARR -CXXFLAGS += -DUSE_MAP_DYNARR -CFLAGS.w32 += -DUSE_MAP_DYNARR -endif - .PHONY: all clean all: $(TARGET) $(if $(CC.w32),$(TARGET).exe,) setpass clean: diff --git a/config.example.mk b/config.example.mk index 66260b5..d446f2e 100644 --- a/config.example.mk +++ b/config.example.mk @@ -9,5 +9,4 @@ LDLIBS=-ltls CC.w32=i686-w64-mingw32-gcc CFLAGS.w32=$(WARNS) -DNETPOLL_USE_SELECT LDLIBS.w32=-lws2_32 -lbcrypt -USE_MAP_DYNARR=1 USE_LUA=1 diff --git a/src/map_dynarr.c b/src/map.c similarity index 86% rename from src/map_dynarr.c rename to src/map.c index ed4e4e4..3f95dbe 100644 --- a/src/map_dynarr.c +++ b/src/map.c @@ -35,7 +35,7 @@ int map_set(map_t *root, const char *key, const void *value, void **oldvalue) *oldvalue = root->ptr[i].value; if (!value) { free(root->ptr[i].key); - memmove(root->ptr+i, root->ptr+i+1, sizeof(struct map_dynarr_value)*(root->len-(i+1))); + memmove(root->ptr+i, root->ptr+i+1, sizeof(struct map_value)*(root->len-(i+1))); root->len--; } else { root->ptr[i].value = (void *)value; @@ -46,7 +46,7 @@ int map_set(map_t *root, const char *key, const void *value, void **oldvalue) if (value) { if (root->len == root->cap) { int ncap = root->cap ? root->cap*2 : 2; - struct map_dynarr_value *nptr = realloc(root->ptr, sizeof(struct map_dynarr_value)*ncap); + struct map_value *nptr = realloc(root->ptr, sizeof(struct map_value)*ncap); if (!nptr) return -1; root->ptr = nptr; @@ -57,7 +57,7 @@ int map_set(map_t *root, const char *key, const void *value, void **oldvalue) if (!nkey) return -1; memcpy(nkey, key, slen); - memmove(root->ptr+i+1, root->ptr+i, sizeof(struct map_dynarr_value)*(root->len-i)); + memmove(root->ptr+i+1, root->ptr+i, sizeof(struct map_value)*(root->len-i)); root->len++; root->ptr[i].key = nkey; root->ptr[i].value = (void *)value; diff --git a/src/map.h b/src/map.h index 751e8d2..0b67571 100644 --- a/src/map.h +++ b/src/map.h @@ -11,37 +11,19 @@ # define NODISCARD #endif -#ifdef USE_MAP_DYNARR /* all complexity is in terms of n = number of elements */ -typedef struct map_dynarr { - struct map_dynarr_value { - char *key; - void *value; - } *ptr; +struct map_value { + char *key; + void *value; +}; +typedef struct map { + struct map_value *ptr; size_t len, cap; } map_t; -typedef struct map_dynarr_iter { +typedef struct map_iter { map_t *root; size_t index; } map_iter_t; -#else -/* all complexity is in terms of n = strlen(key) and s = size of the character set */ -typedef struct map_trie_node { - unsigned char key; - unsigned char len; - unsigned char cap; - void *value; - struct map_trie_node *parent; - struct map_trie_node *data[1]; -} *map_t; -#define TRIE_MAX_KEY 256 -typedef struct map_trie_iter { - map_t *root; - struct map_trie_node *n; - size_t len; - char key[TRIE_MAX_KEY]; -} map_iter_t; -#endif /* A map abstract data type with following properties: * - keys are lexicographically-sorted unique NUL-terminated strings @@ -55,13 +37,11 @@ typedef struct map_trie_iter { */ /* 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. @@ -69,7 +49,6 @@ NODISCARD int map_set(map_t *root, const char *key, const void *value, void **ol #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); @@ -84,7 +63,7 @@ void map_free(map_t *root); */ NODISCARD int map_foriter(map_iter_t *f, const char **outkey, void *outvalue); #define map_foreach(rootp, outkey, outvalue) \ - for (map_iter_t map_itertmp = { .root = rootp }; map_foriter(&map_itertmp, outkey, outvalue); ) + for (map_iter_t map_itertmp = { .root = rootp, .index = 0 }; map_foriter(&map_itertmp, outkey, outvalue); ) /* Return a value from the map. * No guarantees about which one! * You don't get a key and the association is not removed. diff --git a/src/map_trie.c b/src/map_trie.c deleted file mode 100644 index 18c7705..0000000 --- a/src/map_trie.c +++ /dev/null @@ -1,181 +0,0 @@ -#include "map.h" -#include -#include -#define trie_is_end(e, n) ((e) >= (n)->len) -#define trie_is_found(e, n, k) (!trie_is_end((e), (n)) && (n)->data[(e)]->key == (k)) -#define trie_node_size(cap) (sizeof(struct map_trie_node)+sizeof(struct map_trie_node*)*((cap)-1)) -#define trie_data_size(len) (sizeof(struct map_trie_node*)*(len)) -// finds the entry for a child node O(log s) -// note that there are three cases to handle: -// - past the end pointer (key doesn't exist, larger than any existing key) -// - ent with different key (key doesn't exist, it should be inserted before this one) -// - ent with matching key (key exists) -static int ent_find(struct map_trie_node *n, int key) -{ - int lo = 0; - int hi = n->len; - while (lo != hi) { - int mid = (lo+hi)/2; - if (n->data[mid]->key == key) - return mid; - if (n->data[mid]->key > key) - hi = mid; - else - lo = mid+1; - } - return lo; -} -// get value from trie O(n log s) -void *map_get(map_t *root, const char *key) -{ - struct map_trie_node *n = *root; - if (!n) - return NULL; - while (*key) { - int ent = ent_find(n, (unsigned char)*key); - if (!trie_is_found(ent, n, *key)) - return NULL; - n = n->data[ent]; - key++; - } - return n->value; -} -// set value in trie O(ns) -int map_set(map_t *root, const char *key, const void *value, void **oldvalue) -{ - int rv = 0; - if (strlen(key)+1 > TRIE_MAX_KEY) - return -1; - if (oldvalue) - *oldvalue = NULL; - struct map_trie_node *n = *root; - if (!n) { // create root node - if (!value) - return 0; - n = malloc(trie_node_size(1)); - if (!n) - return -1; - memset(n, 0, trie_node_size(0)); - n->cap = 1; - *root = n; - } - while (*key) { // walk the trie to find the leaf - int ent = ent_find(n, (unsigned char)*key); - if (!trie_is_found(ent, n, *key)) { // create missing node - if (!value) // ...unless we're deleting - return 0; - int cap = key[1] ? 1 : 0; // if it's a leaf, use capacity of 0 - struct map_trie_node *node = malloc(trie_node_size(cap)); - if (!node) { - rv = -1; - goto cleanup; - } - memset(node, 0, trie_node_size(0)); - node->key = *key; - node->cap = cap; - if (n->len == n->cap) { // reallocate the node - n->cap = n->cap*2 + 1; // 0 1 3 7 15 31 63 127 255 - // we have to update parent's pointer, but ent_find needs that pointer to be valid. - // so we have to locate it *before* reallocing. - struct map_trie_node **pent = n->parent ? &n->parent->data[ent_find(n->parent, n->key)] : root; - struct map_trie_node *nn = realloc(n, trie_node_size(n->cap)); - if (!nn) { - free(node); - rv = -1; - goto cleanup; - } - if (n != nn) { // update pointers - n = nn; - *pent = n; - for (int i = 0; i < n->len; i++) - n->data[i]->parent = n; - } - } - // insert the new node - node->parent = n; - memmove(&n->data[ent+1], &n->data[ent], trie_data_size(n->len++ - ent)); - n->data[ent] = node; - n = node; - } else { - n = n->data[ent]; - } - key++; - } - if (oldvalue) - *oldvalue = n->value; - n->value = (void *)value; // discard const - if (!value) { - while (!n->value && !n->len) { // free no longer used nodes -cleanup: - if (n->parent) { - struct map_trie_node *p = n->parent; - int ent = ent_find(p, n->key); - memmove(&p->data[ent], &p->data[ent+1], trie_data_size(--p->len - ent)); - free(n); - n = p; - } else { - free(n); - *root = NULL; - break; - } - } - } - return rv; -} -// free a trie -void map_free(map_t *root) { - struct map_trie_node *n = *root; - while (n) { - if (n->len) { - n = n->data[--n->len]; - } else { - struct map_trie_node *p = n->parent; - free(n); - n = p; - } - } - *root = 0; -} -int map_foriter(map_iter_t *f, const char **outkey, void *outvalue) -{ - if (!f->n) { - if (!*f->root) - return 0; - f->n = *f->root; - f->len = 0; - if (outkey) - *outkey = f->key; - if (f->n->value) { - f->key[f->len] = '\0'; - if (outvalue) - *(void **)outvalue = f->n->value; - return 1; - } - } - int ent = 0; // go to the first child node - for (;;) { - if (!trie_is_end(ent, f->n)) { - f->n = f->n->data[ent]; - f->key[f->len++] = f->n->key; - if (f->n->value) { // found a value - f->key[f->len] = '\0'; - if (outvalue) - *(void **)outvalue = f->n->value; - return 1; - } - ent = 0; // no value, go to the first child - } else { // no more children, go to parent's next child - f->n = f->n->parent; - if (!f->n) - return 0; - f->len--; - ent = ent_find(f->n, (unsigned char)f->key[f->len] + 1); - } - } -} -void *map_pop(map_t *root) -{ - map_iter_t it = { .root = root }; - void *value; - return map_foriter(&it, 0, &value) ? value : 0; -} -- 2.56.0