commit f9fcb3e2c918a1274a14501d3a85dafd23e495cb
parent bd2e5f7bdd17d757a17301587206eb1cb3af3ad5
Author: Louis Burda <quent.burda@gmail.com>
Date: Tue, 21 Mar 2023 02:19:50 +0100
Rename to hmap and add value union on key side
Diffstat:
M | Makefile | | | 40 | ++++++++++++++++++++++++---------------- |
D | include/hashmap.h | | | 94 | ------------------------------------------------------------------------------- |
A | include/hmap.h | | | 108 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
D | libhashmap.api | | | 25 | ------------------------- |
D | libhashmap.lds | | | 27 | --------------------------- |
A | libhmap.api | | | 25 | +++++++++++++++++++++++++ |
A | libhmap.lds | | | 27 | +++++++++++++++++++++++++++ |
D | src/hashmap.c | | | 280 | ------------------------------------------------------------------------------- |
A | src/hmap.c | | | 302 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
M | src/test.c | | | 30 | ++++++++++++++++-------------- |
10 files changed, 502 insertions(+), 456 deletions(-)
diff --git a/Makefile b/Makefile
@@ -2,14 +2,22 @@ PREFIX ?= /usr/local
INCLDIR ?= /include
LIBDIR ?= /lib
-CFLAGS = -I include -I lib/liballoc/include -Wno-prototype -Wunused-function
-CFLAGS += -Wunused-variable -Wconversion
+CFLAGS = -Wno-prototype -Wunused-function -Wunused-variable -Wconversion
+CFLAGS += -I include -I lib/liballoc/include
ifeq "$(DEBUG)" "1"
CFLAGS += -g
endif
-all: build/libhashmap.so build/libhashmap.a build/test
+ifeq "$(ASSERT_ARGS)" "1"
+CFLAGS += -DLIBHMAP_ASSERT_ARGS=1
+endif
+
+ifeq "$(ASSERT_ALLOC)" "1"
+CFLAGS += -DLIBHMAP_ASSERT_ALLLOC=1
+endif
+
+all: build/libhmap.so build/libhmap.a build/test
clean:
rm -rf build
@@ -20,26 +28,26 @@ build:
lib/liballoc/build/liballoc.a:
make -C lib/liballoc build/liballoc.a
-build/libhashmap.a: src/hashmap.c include/hashmap.h | build
- $(CC) -o build/tmp.o src/hashmap.c $(CFLAGS) -r
- objcopy --keep-global-symbols=libhashmap.api build/tmp.o build/fixed.o
+build/libhmap.a: src/hmap.c include/hmap.h libhmap.api | build
+ $(CC) -o build/tmp.o src/hmap.c $(CFLAGS) -r
+ objcopy --keep-global-symbols=libhmap.api build/tmp.o build/fixed.o
$(AR) rcs $@ build/fixed.o
-build/libhashmap.so: src/hashmap.c include/hashmap.h | build
- $(CC) -o $@ src/hashmap.c -fPIC $(CFLAGS) -shared \
- -Wl,-version-script libhashmap.lds
+build/libhmap.so: src/hmap.c include/hmap.h libhmap.lds | build
+ $(CC) -o $@ src/hmap.c -fPIC $(CFLAGS) -shared \
+ -Wl,-version-script libhmap.lds
-build/test: src/test.c build/libhashmap.a lib/liballoc/build/liballoc.a | build
+build/test: src/test.c build/libhmap.a lib/liballoc/build/liballoc.a | build
$(CC) -o $@ $^ -I include -I lib/liballoc/include -g
install:
- install -m 644 include/hashmap.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
- install -m 755 build/libhashmap.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
- install -m 755 build/libhashmap.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+ install -m 644 include/hmap.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
+ install -m 755 build/libhmap.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+ install -m 755 build/libhmap.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
uninstall:
- rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/hashmap.h"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhashmap.a"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhashmap.so"
+ rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/hmap.h"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhmap.a"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhmap.so"
.PHONY: all clean install uninstall
diff --git a/include/hashmap.h b/include/hashmap.h
@@ -1,94 +0,0 @@
-#pragma once
-
-#include "allocator.h"
-
-#include <stdint.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include <sys/types.h>
-
-#define HASHMAP_ITER(map, iter) \
- hashmap_iter_init(iter); hashmap_iter_next(map, iter);
-
-#define HASHMAP_STRERR_INIT \
- [HMAP_OK] = "Success", \
- [HMAP_KEY_EXISTS] = "Key exists", \
- [HMAP_KEY_MISSING] = "Key missing"
-
-typedef uint32_t (*hashmap_hash_func)(const void *data, size_t size);
-typedef bool (*hashmap_keycmp_func)(const void *key1, size_t size1,
- const void *key2, size_t size2);
-
-enum {
- HMAP_OK,
- HMAP_KEY_EXISTS,
- HMAP_KEY_MISSING,
-};
-
-struct hashmap_val {
- union {
- char c;
- float f;
- int i;
- unsigned int u;
- void *p;
- };
-};
-
-struct hashmap_link {
- void *key;
- size_t keysize;
- struct hashmap_val value;
- struct hashmap_link *next;
-};
-
-struct hashmap_iter {
- struct hashmap_link *link;
- size_t bucket;
-};
-
-struct hashmap {
- hashmap_hash_func hash;
- hashmap_keycmp_func keycmp;
- struct hashmap_link **buckets;
- size_t size;
- const struct allocator *allocator;
-};
-
-int hashmap_init(struct hashmap *map, size_t size, hashmap_hash_func hasher,
- hashmap_keycmp_func keycmp, const struct allocator *allocator);
-void hashmap_deinit(struct hashmap *map);
-
-int hashmap_alloc(struct hashmap **map, size_t size, hashmap_hash_func hasher,
- hashmap_keycmp_func keycmp, const struct allocator *allocator);
-void hashmap_free(struct hashmap *map);
-
-int hashmap_copy(struct hashmap *dst, const struct hashmap *src);
-void hashmap_swap(struct hashmap *m1, struct hashmap *m2);
-void hashmap_clear(struct hashmap *map);
-
-struct hashmap_link **hashmap_link_get(struct hashmap *map,
- const void *key, size_t size);
-struct hashmap_link **hashmap_link_pos(struct hashmap *map,
- const void *key, size_t size);
-struct hashmap_link *hashmap_link_pop(struct hashmap *map,
- const void *key, size_t size);
-void hashmap_link_set(struct hashmap *map, struct hashmap_link *link,
- void *key, size_t keysize, struct hashmap_val value);
-int hashmap_link_alloc(struct hashmap *map, struct hashmap_link **out,
- void *key, size_t keysize, struct hashmap_val value);
-
-struct hashmap_link *hashmap_get(struct hashmap *map,
- const void *key, size_t size);
-void hashmap_rm(struct hashmap *map, const void *key, size_t size);
-int hashmap_set(struct hashmap *map, void *key, size_t keysize,
- struct hashmap_val value);
-int hashmap_add(struct hashmap *map, void *key, size_t keysize,
- struct hashmap_val value);
-
-void hashmap_iter_init(struct hashmap_iter *iter);
-bool hashmap_iter_next(const struct hashmap *map, struct hashmap_iter *iter);
-
-uint32_t hashmap_str_hasher(const void *data, size_t size);
-bool hashmap_default_keycmp(const void *key1, size_t size1,
- const void *key2, size_t size2);
diff --git a/include/hmap.h b/include/hmap.h
@@ -0,0 +1,108 @@
+#pragma once
+
+#include "allocator.h"
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#define HMAP_ITER(map, iter) \
+ hmap_iter_init(iter); hmap_iter_next(map, iter);
+
+#define HMAP_STRERR_INIT \
+ [HMAP_OK] = "Success", \
+ [HMAP_KEY_EXISTS] = "Key exists", \
+ [HMAP_KEY_MISSING] = "Key missing"
+
+#ifdef LIBHMAP_ASSERT_ARGS
+#define LIBHMAP_ABORT_ON_ARGS(cond) do { if (cond) abort(); } while (0)
+#else
+#define LIBHMAP_ABORT_ON_ARGS(cond)
+#endif
+
+#ifdef LIBHMAP_ASSERT_ALLOC
+#define LIBHMAP_ABORT_ON_ALLOC(cond) do { if (cond) abort(); } while (0)
+#else
+#define LIBHMAP_ABORT_ON_ALLOC(cond)
+#endif
+
+struct hmap_key;
+
+typedef uint32_t (*hmap_hash_func)(struct hmap_key key);
+typedef bool (*hmap_keycmp_func)(struct hmap_key k1, struct hmap_key k2);
+
+enum {
+ HMAP_OK,
+ HMAP_KEY_EXISTS,
+ HMAP_KEY_MISSING,
+};
+
+struct hmap_key {
+ union {
+ char c;
+ float f;
+ int i;
+ unsigned int u;
+ const void *p;
+ void *_p;
+ };
+};
+
+struct hmap_val {
+ union {
+ char c;
+ float f;
+ int i;
+ unsigned int u;
+ const void *p;
+ void *_p;
+ };
+};
+
+struct hmap_link {
+ struct hmap_key key;
+ struct hmap_val value;
+ struct hmap_link *next;
+};
+
+struct hmap_iter {
+ struct hmap_link *link;
+ size_t bucket;
+};
+
+struct hmap {
+ hmap_hash_func hash;
+ hmap_keycmp_func keycmp;
+ struct hmap_link **buckets;
+ size_t bucketcnt;
+ const struct allocator *allocator;
+};
+
+int hmap_init(struct hmap *map, size_t size, hmap_hash_func hasher,
+ hmap_keycmp_func keycmp, const struct allocator *allocator);
+void hmap_deinit(struct hmap *map);
+
+int hmap_alloc(struct hmap **map, size_t size, hmap_hash_func hasher,
+ hmap_keycmp_func keycmp, const struct allocator *allocator);
+void hmap_free(struct hmap *map);
+
+int hmap_copy(struct hmap *dst, const struct hmap *src);
+void hmap_swap(struct hmap *m1, struct hmap *m2);
+void hmap_clear(struct hmap *map);
+
+struct hmap_link **hmap_link_get(struct hmap *map, struct hmap_key key);
+struct hmap_link **hmap_link_pos(struct hmap *map, struct hmap_key key);
+struct hmap_link *hmap_link_pop(struct hmap *map, struct hmap_key key);
+int hmap_link_alloc(struct hmap *map, struct hmap_link **out,
+ struct hmap_key key, struct hmap_val value);
+
+struct hmap_link *hmap_get(struct hmap *map, struct hmap_key key);
+void hmap_rm(struct hmap *map, struct hmap_key key);
+int hmap_set(struct hmap *map, struct hmap_key key, struct hmap_val value);
+int hmap_add(struct hmap *map, struct hmap_key key, struct hmap_val value);
+
+void hmap_iter_init(struct hmap_iter *iter);
+bool hmap_iter_next(const struct hmap *map, struct hmap_iter *iter);
+
+uint32_t hmap_str_hash(struct hmap_key key);
+bool hmap_str_keycmp(struct hmap_key k1, struct hmap_key k2);
diff --git a/libhashmap.api b/libhashmap.api
@@ -1,25 +0,0 @@
-hashmap_init
-hashmap_deinit
-hashmap_alloc
-hashmap_free
-
-hashmap_copy
-hashmap_swap
-hashmap_clear
-
-hashmap_link_get
-hashmap_link_pos
-hashmap_link_pop
-hashmap_link_set
-hashmap_link_alloc
-
-hashmap_get
-hashmap_rm
-hashmap_set
-hashmap_add
-
-hashmap_iter_init
-hashmap_iter_next
-
-hashmap_str_hasher
-hashmap_default_keycmp
diff --git a/libhashmap.lds b/libhashmap.lds
@@ -1,27 +0,0 @@
-LIBHASHMAP_1.3.2 {
- hashmap_init;
- hashmap_deinit;
- hashmap_alloc;
- hashmap_free;
-
- hashmap_copy;
- hashmap_swap;
- hashmap_clear;
-
- hashmap_link_get;
- hashmap_link_pos;
- hashmap_link_pop;
- hashmap_link_set;
- hashmap_link_add;
- hashmap_link_alloc;
-
- hashmap_get;
- hashmap_rm;
- hashmap_set;
-
- hashmap_iter_init;
- hashmap_iter_next;
-
- hashmap_str_hasher;
- hashmap_default_keycmp;
-};
diff --git a/libhmap.api b/libhmap.api
@@ -0,0 +1,25 @@
+hmap_init
+hmap_deinit
+hmap_alloc
+hmap_free
+
+hmap_copy
+hmap_swap
+hmap_clear
+
+hmap_link_get
+hmap_link_pos
+hmap_link_pop
+hmap_link_set
+hmap_link_alloc
+
+hmap_get
+hmap_rm
+hmap_set
+hmap_add
+
+hmap_iter_init
+hmap_iter_next
+
+hmap_str_hash
+hmap_str_keycmp
diff --git a/libhmap.lds b/libhmap.lds
@@ -0,0 +1,27 @@
+LIBHMAP_1.0.0 {
+ hmap_init;
+ hmap_deinit;
+ hmap_alloc;
+ hmap_free;
+
+ hmap_copy;
+ hmap_swap;
+ hmap_clear;
+
+ hmap_link_get;
+ hmap_link_pos;
+ hmap_link_pop;
+ hmap_link_set;
+ hmap_link_add;
+ hmap_link_alloc;
+
+ hmap_get;
+ hmap_rm;
+ hmap_set;
+
+ hmap_iter_init;
+ hmap_iter_next;
+
+ hmap_str_hash;
+ hmap_str_keycmp;
+};
diff --git a/src/hashmap.c b/src/hashmap.c
@@ -1,280 +0,0 @@
-#include "hashmap.h"
-
-#include <errno.h>
-#include <string.h>
-
-static inline size_t
-hashmap_key_bucket(struct hashmap *map, const void *key, size_t size)
-{
- return map->hash(key, size) % map->size;
-}
-
-int
-hashmap_init(struct hashmap *map, size_t size, hashmap_hash_func hasher,
- hashmap_keycmp_func keycmp, const struct allocator *allocator)
-{
- int rc;
-
- map->allocator = allocator;
- map->keycmp = keycmp;
- map->size = size;
- map->hash = hasher;
- rc = map->allocator->alloc((void **)&map->buckets,
- sizeof(void *) * size);
- if (rc) return -rc;
- memset(map->buckets, 0, size * sizeof(void *));
-
- return 0;
-}
-
-void
-hashmap_deinit(struct hashmap *map)
-{
- hashmap_clear(map);
- map->allocator->free(map->buckets);
-}
-
-int
-hashmap_alloc(struct hashmap **map, size_t size, hashmap_hash_func hasher,
- hashmap_keycmp_func keycmp, const struct allocator *allocator)
-{
- int rc;
-
- rc = allocator->alloc((void **)map, sizeof(struct hashmap));
- if (rc) return -rc;
-
- rc = hashmap_init(*map, size, hasher, keycmp, allocator);
- if (rc) {
- allocator->free(*map);
- return rc;
- }
-
- return 0;
-}
-
-void
-hashmap_free(struct hashmap *map)
-{
- const struct allocator *allocator;
-
- allocator = map->allocator;
- hashmap_deinit(map);
- allocator->free(map);
-}
-
-int
-hashmap_copy(struct hashmap *dst, const struct hashmap *src)
-{
- struct hashmap_iter iter;
- int rc;
-
- for (HASHMAP_ITER(src, &iter)) {
- rc = hashmap_set(dst, iter.link->key,
- iter.link->keysize, iter.link->value);
- if (rc) return rc;
- }
-
- return 0;
-}
-
-void
-hashmap_swap(struct hashmap *m1, struct hashmap *m2)
-{
- struct hashmap tmp;
-
- memcpy(&tmp, m1, sizeof(struct hashmap));
- memcpy(m1, m2, sizeof(struct hashmap));
- memcpy(m2, &tmp, sizeof(struct hashmap));
-}
-
-void
-hashmap_clear(struct hashmap *map)
-{
- struct hashmap_iter iter;
- struct hashmap_link *prev;
- size_t i;
-
- prev = NULL;
- for (HASHMAP_ITER(map, &iter)) {
- map->allocator->free(prev);
- prev = iter.link;
- }
- map->allocator->free(prev);
-
- for (i = 0; i < map->size; i++)
- map->buckets[i] = NULL;
-}
-
-struct hashmap_link **
-hashmap_link_get(struct hashmap *map, const void *key, size_t keysize)
-{
- struct hashmap_link **iter, *link;
-
- iter = &map->buckets[hashmap_key_bucket(map, key, keysize)];
- while (*iter != NULL) {
- link = *iter;
- if (map->keycmp(link->key, link->keysize, key, keysize))
- return iter;
- iter = &(*iter)->next;
- }
-
- return NULL;
-}
-
-struct hashmap_link **
-hashmap_link_pos(struct hashmap *map, const void *key, size_t keysize)
-{
- struct hashmap_link **iter, *link;
-
- iter = &map->buckets[hashmap_key_bucket(map, key, keysize)];
- while (*iter != NULL) {
- link = *iter;
- if (map->keycmp(link->key, link->keysize, key, keysize))
- return iter;
- iter = &(*iter)->next;
- }
-
- return iter;
-}
-
-struct hashmap_link *
-hashmap_link_pop(struct hashmap *map, const void *key, size_t keysize)
-{
- struct hashmap_link **iter;
-
- iter = hashmap_link_get(map, key, keysize);
- if (iter) {
- *iter = (*iter)->next;
- return *iter;
- }
-
- return NULL;
-}
-
-void
-hashmap_link_set(struct hashmap *map, struct hashmap_link *link,
- void *key, size_t keysize, struct hashmap_val value)
-{
- link->key = key;
- link->keysize = keysize;
- link->value = value;
-}
-
-int
-hashmap_link_alloc(struct hashmap *map, struct hashmap_link **out,
- void *key, size_t keysize, struct hashmap_val value)
-{
- struct hashmap_link *link;
- int rc;
-
- rc = map->allocator->alloc((void **)&link, sizeof(struct hashmap_link));
- if (rc) return -rc;
- link->key = key;
- link->keysize = keysize;
- link->value = value;
- link->next = NULL;
- *out = link;
-
- return 0;
-}
-
-struct hashmap_link *
-hashmap_get(struct hashmap *map, const void *key, size_t keysize)
-{
- struct hashmap_link **iter;
-
- iter = hashmap_link_get(map, key, keysize);
-
- return iter ? *iter : NULL;
-}
-
-void
-hashmap_rm(struct hashmap *map, const void *key, size_t keysize)
-{
- struct hashmap_link *link;
-
- link = hashmap_link_pop(map, key, keysize);
- if (!link) return;
- map->allocator->free(link);
-}
-
-int
-hashmap_set(struct hashmap *map, void *key, size_t keysize,
- struct hashmap_val value)
-{
- struct hashmap_link **iter;
-
- iter = hashmap_link_pos(map, key, keysize);
- if (!*iter) return HMAP_KEY_MISSING;
-
- hashmap_link_set(map, *iter, key, keysize, value);
-
- return 0;
-}
-
-int
-hashmap_add(struct hashmap *map, void *key, size_t keysize,
- struct hashmap_val value)
-{
- struct hashmap_link **iter;
- int rc;
-
- iter = hashmap_link_pos(map, key, keysize);
- if (*iter) return HMAP_KEY_EXISTS;
-
- rc = hashmap_link_alloc(map, iter, key, keysize, value);
- if (rc) return rc;
-
- return 0;
-}
-
-void
-hashmap_iter_init(struct hashmap_iter *iter)
-{
- iter->bucket = 0;
- iter->link = NULL;
-}
-
-bool
-hashmap_iter_next(const struct hashmap *map, struct hashmap_iter *iter)
-{
- size_t i;
-
- if (iter->link && iter->link->next) {
- iter->link = iter->link->next;
- return true;
- }
-
- i = iter->bucket + (iter->link ? 1 : 0);
- for (; i < map->size; i++) {
- if (map->buckets[i]) {
- iter->bucket = i;
- iter->link = map->buckets[i];
- return true;
- }
- }
-
- iter->link = NULL;
-
- return false;
-}
-
-uint32_t
-hashmap_str_hasher(const void *data, size_t size)
-{
- uint32_t hash;
- size_t i;
-
- hash = 5381;
- for (i = 0; i < size; i++)
- hash = 33 * hash + ((uint8_t *) data)[i];
-
- return hash;
-}
-
-bool
-hashmap_default_keycmp(const void *key1, size_t size1,
- const void *key2, size_t size2)
-{
- return size1 == size2 && !memcmp(key1, key2, size1);
-}
diff --git a/src/hmap.c b/src/hmap.c
@@ -0,0 +1,302 @@
+#include "hmap.h"
+
+#include <errno.h>
+#include <string.h>
+
+static inline size_t
+hmap_key_bucket(struct hmap *map, struct hmap_key key)
+{
+ return map->hash(key) % map->bucketcnt;
+}
+
+int
+hmap_init(struct hmap *map, size_t size, hmap_hash_func hasher,
+ hmap_keycmp_func keycmp, const struct allocator *allocator)
+{
+ int rc;
+
+ LIBHMAP_ABORT_ON_ARGS(!map || !size || !hasher || !keycmp || !allocator);
+
+ map->allocator = allocator;
+ map->keycmp = keycmp;
+ map->bucketcnt = size;
+ map->hash = hasher;
+ rc = map->allocator->alloc((void **)&map->buckets,
+ sizeof(void *) * size);
+ if (rc) return -rc;
+ memset(map->buckets, 0, size * sizeof(void *));
+
+ return 0;
+}
+
+void
+hmap_deinit(struct hmap *map)
+{
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ hmap_clear(map);
+
+ map->allocator->free(map->buckets);
+}
+
+int
+hmap_alloc(struct hmap **map, size_t size, hmap_hash_func hasher,
+ hmap_keycmp_func keycmp, const struct allocator *allocator)
+{
+ int rc;
+
+ LIBHMAP_ABORT_ON_ARGS(!allocator)
+
+ rc = allocator->alloc((void **)map, sizeof(struct hmap));
+ if (rc) return -rc;
+
+ rc = hmap_init(*map, size, hasher, keycmp, allocator);
+ if (rc) return rc;
+
+ return 0;
+}
+
+void
+hmap_free(struct hmap *map)
+{
+ const struct allocator *allocator;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ allocator = map->allocator;
+ hmap_deinit(map);
+ allocator->free(map);
+}
+
+int
+hmap_copy(struct hmap *dst, const struct hmap *src)
+{
+ struct hmap_iter iter;
+ int rc;
+
+ LIBHMAP_ABORT_ON_ARGS(!dst || !src);
+
+ for (HMAP_ITER(src, &iter)) {
+ rc = hmap_set(dst, iter.link->key, iter.link->value);
+ if (rc) return rc;
+ }
+
+ return 0;
+}
+
+void
+hmap_swap(struct hmap *m1, struct hmap *m2)
+{
+ struct hmap tmp;
+
+ LIBHMAP_ABORT_ON_ARGS(!m1 || !m2);
+
+ memcpy(&tmp, m1, sizeof(struct hmap));
+ memcpy(m1, m2, sizeof(struct hmap));
+ memcpy(m2, &tmp, sizeof(struct hmap));
+}
+
+void
+hmap_clear(struct hmap *map)
+{
+ struct hmap_iter iter;
+ struct hmap_link *prev;
+ size_t i;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ prev = NULL;
+ for (HMAP_ITER(map, &iter)) {
+ map->allocator->free(prev);
+ prev = iter.link;
+ }
+ map->allocator->free(prev);
+
+ for (i = 0; i < map->bucketcnt; i++)
+ map->buckets[i] = NULL;
+}
+
+struct hmap_link **
+hmap_link_get(struct hmap *map, struct hmap_key key)
+{
+ struct hmap_link **iter, *link;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ iter = &map->buckets[hmap_key_bucket(map, key)];
+ while (*iter != NULL) {
+ link = *iter;
+ if (map->keycmp(link->key, key))
+ return iter;
+ iter = &(*iter)->next;
+ }
+
+ return NULL;
+}
+
+struct hmap_link **
+hmap_link_pos(struct hmap *map, struct hmap_key key)
+{
+ struct hmap_link **iter, *link;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ iter = &map->buckets[hmap_key_bucket(map, key)];
+ while (*iter != NULL) {
+ link = *iter;
+ if (map->keycmp(link->key, key))
+ return iter;
+ iter = &(*iter)->next;
+ }
+
+ return iter;
+}
+
+struct hmap_link *
+hmap_link_pop(struct hmap *map, struct hmap_key key)
+{
+ struct hmap_link **iter;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ iter = hmap_link_get(map, key);
+ if (iter) {
+ *iter = (*iter)->next;
+ return *iter;
+ }
+
+ return NULL;
+}
+
+int
+hmap_link_alloc(struct hmap *map, struct hmap_link **out,
+ struct hmap_key key, struct hmap_val value)
+{
+ struct hmap_link *link;
+ int rc;
+
+ LIBHMAP_ABORT_ON_ARGS(!map || !out);
+
+ rc = map->allocator->alloc((void **)&link, sizeof(struct hmap_link));
+ if (rc) return -rc;
+ link->key = key;
+ link->value = value;
+ link->next = NULL;
+ *out = link;
+
+ return 0;
+}
+
+struct hmap_link *
+hmap_get(struct hmap *map, struct hmap_key key)
+{
+ struct hmap_link **iter;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ iter = hmap_link_get(map, key);
+
+ return iter ? *iter : NULL;
+}
+
+void
+hmap_rm(struct hmap *map, struct hmap_key key)
+{
+ struct hmap_link *link;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ link = hmap_link_pop(map, key);
+ if (!link) return;
+ map->allocator->free(link);
+}
+
+int
+hmap_set(struct hmap *map, struct hmap_key key, struct hmap_val value)
+{
+ struct hmap_link **iter;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ iter = hmap_link_pos(map, key);
+ if (!*iter) return HMAP_KEY_MISSING;
+
+ (*iter)->value = value;
+
+ return 0;
+}
+
+int
+hmap_add(struct hmap *map, struct hmap_key key, struct hmap_val value)
+{
+ struct hmap_link **iter;
+ int rc;
+
+ LIBHMAP_ABORT_ON_ARGS(!map);
+
+ iter = hmap_link_pos(map, key);
+ if (*iter) return HMAP_KEY_EXISTS;
+
+ rc = hmap_link_alloc(map, iter, key, value);
+ if (rc) return rc;
+
+ return 0;
+}
+
+void
+hmap_iter_init(struct hmap_iter *iter)
+{
+ LIBHMAP_ABORT_ON_ARGS(!iter);
+
+ iter->bucket = 0;
+ iter->link = NULL;
+}
+
+bool
+hmap_iter_next(const struct hmap *map, struct hmap_iter *iter)
+{
+ size_t i;
+
+ LIBHMAP_ABORT_ON_ARGS(!map || !iter);
+
+ if (iter->link && iter->link->next) {
+ iter->link = iter->link->next;
+ return true;
+ }
+
+ i = iter->bucket + (iter->link ? 1 : 0);
+ for (; i < map->bucketcnt; i++) {
+ if (map->buckets[i]) {
+ iter->bucket = i;
+ iter->link = map->buckets[i];
+ return true;
+ }
+ }
+
+ iter->link = NULL;
+
+ return false;
+}
+
+uint32_t
+hmap_str_hash(struct hmap_key key)
+{
+ const char *c;
+ uint32_t hash;
+
+ LIBHMAP_ABORT_ON_ARGS(!key.p);
+
+ hash = 5381;
+ for (c = key.p; *c; c++)
+ hash = 33 * hash + (uint8_t) *c;
+
+ return hash;
+}
+
+bool
+hmap_str_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ LIBHMAP_ABORT_ON_ARGS(!k1.p || !k2.p);
+
+ return !strcmp(k1.p, k2.p);
+}
diff --git a/src/test.c b/src/test.c
@@ -1,40 +1,42 @@
-#include "hashmap.h"
+#include "hmap.h"
#include <err.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
-#define LIBHASHMAP_ERR(rc) errx(1, "libhashmap: %s", \
+#define LIBHMAP_ERR(rc) errx(1, "libhmap: %s", \
rc < 0 ? strerror(-rc) : hmap_err[rc])
static const char *hmap_err[] = {
- HASHMAP_STRERR_INIT
+ HMAP_STRERR_INIT
};
int
main(int argc, const char **argv)
{
- struct hashmap hashmap;
- struct hashmap_iter iter;
+ struct hmap hmap;
+ struct hmap_iter iter;
void *key;
int i, rc;
- rc = hashmap_init(&hashmap, 10, hashmap_str_hasher,
- hashmap_default_keycmp, &stdlib_heap_allocator);
- if (rc) LIBHASHMAP_ERR(rc);
+ rc = hmap_init(&hmap, 10, hmap_str_hash,
+ hmap_str_keycmp, &stdlib_heap_allocator);
+ if (rc) LIBHMAP_ERR(rc);
for (i = 1; i < argc; i++) {
key = strdup(argv[i]);
- rc = hashmap_add(&hashmap, key, strlen(key) + 1,
- (struct hashmap_val) {.i = i});
- if (rc) LIBHASHMAP_ERR(rc);
+ rc = hmap_add(&hmap, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.i = i});
+ if (rc) LIBHMAP_ERR(rc);
}
- for (HASHMAP_ITER(&hashmap, &iter)) {
- printf("%s: %i\n", (char *)iter.link->key,
+ for (HMAP_ITER(&hmap, &iter)) {
+ printf("%s: %i\n", (char *)iter.link->key.p,
iter.link->value.i);
}
- hashmap_deinit(&hashmap);
+ for (HMAP_ITER(&hmap, &iter))
+ free(iter.link->key.p);
+ hmap_deinit(&hmap);
}