commit c547226bb32624565150e711fab331be13ca8b1e
parent 188488f7f0727e749a2be3d8282f4b776bf92a06
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 17 Feb 2023 20:23:43 +0100
Rename and refactor to use optional assert
Diffstat:
| M | Makefile | | | 59 | +++++++++++++++++++++++++++++++++-------------------------- |
| A | include/hashmap.h | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| D | include/map.h | | | 48 | ------------------------------------------------ |
| A | libhashmap.abi | | | 15 | +++++++++++++++ |
| A | libhashmap.lds | | | 17 | +++++++++++++++++ |
| D | libmap.api | | | 15 | --------------- |
| D | libmap.lds | | | 17 | ----------------- |
| A | src/hashmap.c | | | 258 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| D | src/map.c | | | 252 | ------------------------------------------------------------------------------- |
| M | src/test.c | | | 15 | ++++++++------- |
10 files changed, 421 insertions(+), 365 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,14 +1,20 @@
-CFLAGS = -I include -g
-LDLIBS =
-DEPFLAGS = -MT $@ -MMD -MP -MF build/$*.d
+PREFIX ?= /usr/local
+INCLUDEDIR ?= /include
+LIBDIR ?= /lib
-_SRCS = map.c
-SRCS = $(_SRCS:%.c=src/%.c)
-OBJS = $(_SRCS:%.c=build/%.o)
-DEPS = $(_SRCS:%.c=build/%.d)
-PI_OBJS = $(_SRCS:%.c=build/%.pi.o)
+CFLAGS = -I include -Wno-prototype -Wunused-function -Wunused-variable
-.PHONY: all clean
+ifeq "$(LIBMAP_DEBUG)" "1"
+CFLAGS += -g
+endif
+
+ifeq "$(LIBMAP_ASSERT)" "1"
+CFLAGS += -DLIBMAP_ASSERT_ENABLE=1
+endif
+
+ifeq "$(LIBMAP_HANDLE_ERR)" "1"
+CFLAGS += -DLIBMAP_HANDLE_ERRS=1
+endif
all: build/libmap.so build/libmap.a build/test
@@ -18,25 +24,26 @@ clean:
build:
mkdir build
-build/%.o: src/%.c build/%.d | build
- $(CC) -c -o $@ $< $(DEPFLAGS) $(CFLAGS)
-
-build/%.pi.o: src/%.c build/%.d | build
- $(CC) -c -o $@ $< $(DEPFLAGS) $(CFLAGS) -fPIC
-
-build/%.d: | build;
+build/libmap.a: src/hashmap.c include/hashmap.h | build
+ $(CC) -o build/tmp.o src/hashmap.c $(CFLAGS) -r
+ objcopy --keep-global-symbols=libhashmap.abi build/tmp.o build/fixed.o
+ $(AR) rcs $@ build/fixed.o
-include $(DEPS)
-
-build/libmap.a: $(OBJS) | build
- $(CC) -o build/tmp.o $^ $(CFLAGS) -r
- objcopy --keep-global-symbols=libmap.api build/tmp.o build/fixed.o
- ar rcs $@ build/fixed.o
-
-build/libmap.so: $(PI_OBJS) | build
- $(CC) -o build/tmp.so $(PI_OBJS) $(CFLAGS) -shared
- objcopy --keep-global-symbols=libmap.api build/tmp.so $@
+build/libmap.so: src/hashmap.c include/hashmap.h | build
+ $(CC) -o $@ src/hashmap.c -fPIC $(CFLAGS) -shared \
+ -Wl,-version-script libhashmap.lds
build/test: src/test.c build/libmap.a | build
$(CC) -o $@ $^ -I include -g
+install:
+ install -m 644 include/hashmap.h -t "$(DESTDIR)$(PREFIX)$(INCLUDEDIR)"
+ install -m 755 build/libmap.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+ install -m 755 build/libmap.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+
+uninstall:
+ rm -f "$(DESTDIR)$(PREFIX)$(INCLUDEDIR)/hashmap.h"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libmap.a"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libmap.so"
+
+.PHONY: all clean install uninstall
diff --git a/include/hashmap.h b/include/hashmap.h
@@ -0,0 +1,90 @@
+#pragma once
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+#ifdef LIBHASHMAP_ASSERT_ENABLE
+
+#include <stdio.h>
+
+#define LIBHASHMAP_ASSERT(x) libhashmap_assert((x), __FILE__, __LINE__, #x)
+
+static inline void libhashmap_assert(int cond,
+ const char *file, int line, const char *condstr)
+{
+ if (cond) return;
+
+ fprintf(stderr, "libhashmap: Assertion failed at %s:%i (%s)\n",
+ file, line, condstr);
+ abort();
+}
+
+#else
+#define LIBHASHMAP_ASSERT(x)
+#endif
+
+#ifdef LIBHASHMAP_HANDLE_ERRS
+
+#include <errno.h>
+#include <stdio.h>
+
+#define LIBHASHMAP_HANDLE_ERR(x) libhashmap_err(__FILE__, __LINE__, x)
+
+static inline void libhashmap_err(const char *file, int line, const char *info)
+{
+ fprintf(stderr, "libhashmap: %s at %s:%i: %s\n",
+ info, file, line, strerror(errno));
+ exit(1);
+}
+
+#else
+#define LIBHASHMAP_HANDLE_ERR(x)
+#endif
+
+
+#define HASHMAP_ITER(map, iter) \
+ hashmap_iter_init(iter); hashmap_iter_next(map, iter);
+
+typedef uint32_t (*map_hash_func)(const void *data, size_t size);
+
+struct hashmap_link {
+ uint8_t *key;
+ size_t key_size;
+ uint8_t *value;
+ size_t value_size;
+ struct hashmap_link *next;
+};
+
+struct hashmap_iter {
+ struct hashmap_link *link;
+ size_t bucket;
+};
+
+struct hashmap {
+ map_hash_func hash;
+ struct hashmap_link **buckets;
+ size_t size;
+};
+
+bool hashmap_init(struct hashmap *map, size_t size, map_hash_func hasher);
+void hashmap_deinit(struct hashmap *map);
+
+struct hashmap *hashmap_alloc(size_t size, map_hash_func hasher);
+void hashmap_free(struct hashmap *map);
+
+void hashmap_clear(struct hashmap *map);
+
+struct hashmap_link *hashmap_get(struct hashmap *map, const void *key, size_t size);
+struct hashmap_link *hashmap_pop(struct hashmap *map, const void *key, size_t size);
+
+void hashmap_link_set(struct hashmap_link *link, void *key, size_t key_size,
+ void *value, size_t value_size);
+void hashmap_set(struct hashmap *map, void *key, size_t key_size,
+ void *value, size_t value_size);
+
+void hashmap_iter_init(struct hashmap_iter *iter);
+bool hashmap_iter_next(struct hashmap *map, struct hashmap_iter *iter);
+
+uint32_t hashmap_str_hasher(const void *data, size_t size);
+
diff --git a/include/map.h b/include/map.h
@@ -1,48 +0,0 @@
-#pragma once
-
-#include <stdbool.h>
-#include <stdlib.h>
-#include <stdio.h>
-#include <stdint.h>
-
-#define MAP_ITER(map, iter) map_iter_init(iter); map_iter_next(map, iter);
-
-typedef uint32_t (*map_hash_func)(const char *data, size_t size);
-
-struct map_link {
- char *key;
- size_t key_size;
- char *value;
- size_t value_size;
- struct map_link *next;
-};
-
-struct map_iter {
- struct map_link *link;
- size_t bucket;
-};
-
-struct map {
- map_hash_func hash;
- size_t size;
- struct map_link **buckets;
-};
-
-void map_init(struct map *map, size_t size, map_hash_func hasher);
-void map_deinit(struct map *map);
-
-void map_clear(struct map *map);
-
-struct map_link *map_get(struct map *map, const void *key, size_t size);
-struct map_link *map_pop(struct map *map, const void *key, size_t size);
-
-void map_link_set(struct map_link *link, void *key, size_t key_size,
- void *value, size_t value_size);
-void map_set(struct map *map, void *key, size_t key_size,
- void *value, size_t value_size);
-
-void map_iter_init(struct map_iter *iter);
-bool map_iter_next(struct map *map, struct map_iter *iter);
-
-uint32_t map_str_hash(const char *data, size_t size);
-
diff --git a/libhashmap.abi b/libhashmap.abi
@@ -0,0 +1,15 @@
+hashmap_init
+hashmap_deinit
+
+hashmap_clear
+
+hashmap_get
+hashmap_pop
+
+hashmap_link_set
+hashmap_set
+
+hashmap_iter_init
+hashmap_iter_next
+
+hashmap_str_hasher
diff --git a/libhashmap.lds b/libhashmap.lds
@@ -0,0 +1,17 @@
+LIBHASHMAP_1.0 {
+ hashmap_init;
+ hashmap_deinit;
+
+ hashmap_clear;
+
+ hashmap_get;
+ hashmap_pop;
+
+ hashmap_link_set;
+ hashmap_set;
+
+ hashmap_iter_init;
+ hashmap_iter_next;
+
+ hashmap_str_hasher;
+};
diff --git a/libmap.api b/libmap.api
@@ -1,15 +0,0 @@
-map_init
-map_deinit
-
-map_clear
-
-map_get
-map_pop
-
-map_link_set
-map_set
-
-map_iter_init
-map_iter_next
-
-map_str_hash
diff --git a/libmap.lds b/libmap.lds
@@ -1,17 +0,0 @@
-LIBMAP_1.0 {
- map_init;
- map_deinit;
-
- map_clear;
-
- map_get;
- map_pop;
-
- map_link_set;
- map_set;
-
- map_iter_init;
- map_iter_next;
-
- map_str_hash;
-};
diff --git a/src/hashmap.c b/src/hashmap.c
@@ -0,0 +1,258 @@
+#include "hashmap.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+static size_t hashmap_key_bucket(struct hashmap *map,
+ const void *key, size_t size);
+static bool hashmap_key_cmp(const void *a, size_t asize,
+ const void *b, size_t bsize);
+
+static struct hashmap_link **hashmap_get_linkp(struct hashmap *map,
+ const void *key, size_t size);
+static struct hashmap_link *hashmap_link_alloc(void *key, size_t key_size,
+ void *value, size_t value_size);
+
+size_t
+hashmap_key_bucket(struct hashmap *map, const void *key, size_t size)
+{
+ LIBHASHMAP_ASSERT(map != NULL && key != NULL);
+
+ return map->hash(key, size) % map->size;
+}
+
+bool
+hashmap_key_cmp(const void *a, size_t asize, const void *b, size_t bsize)
+{
+ LIBHASHMAP_ASSERT(a != NULL && asize != 0 && b != NULL && bsize != 0);
+
+ return asize == bsize && !memcmp(a, b, asize);
+}
+
+struct hashmap_link **
+hashmap_get_linkp(struct hashmap *map, const void *key, size_t size)
+{
+ struct hashmap_link **iter, *link;
+
+ LIBHASHMAP_ASSERT(map != NULL);
+
+ iter = &map->buckets[hashmap_key_bucket(map, key, size)];
+ while (*iter != NULL) {
+ link = *iter;
+ if (hashmap_key_cmp(link->key, link->key_size, key, size))
+ return iter;
+ iter = &(*iter)->next;
+ }
+
+ return NULL;
+}
+
+struct hashmap_link *
+hashmap_link_alloc(void *key, size_t key_size, void *value, size_t value_size)
+{
+ struct hashmap_link *link;
+
+ LIBHASHMAP_ASSERT(key != NULL && value != NULL);
+
+ link = malloc(sizeof(struct hashmap_link));
+ if (!link) {
+ LIBHASHMAP_HANDLE_ERR("malloc");
+ return NULL;
+ }
+ link->key = key;
+ link->key_size = key_size;
+ link->value = value;
+ link->value_size = value_size;
+ link->next = NULL;
+
+ return link;
+}
+
+bool
+hashmap_init(struct hashmap *map, size_t size, map_hash_func hasher)
+{
+ LIBHASHMAP_ASSERT(map != NULL && size != 0 && hasher != NULL);
+
+ map->buckets = calloc(size, sizeof(struct hashmap_link *));
+ if (!map->buckets) {
+ LIBHASHMAP_HANDLE_ERR("calloc");
+ return false;
+ }
+ map->size = size;
+ map->hash = hasher;
+
+ return true;
+}
+
+void
+hashmap_deinit(struct hashmap *map)
+{
+ LIBHASHMAP_ASSERT(map != NULL);
+
+ hashmap_clear(map);
+ free(map->buckets);
+}
+
+struct hashmap *
+hashmap_alloc(size_t size, map_hash_func hasher)
+{
+ struct hashmap *map;
+
+ map = malloc(sizeof(struct hashmap));
+ if (!map) {
+ LIBHASHMAP_HANDLE_ERR("malloc");
+ return NULL;
+ }
+
+ if (!hashmap_init(map, size, hasher)) {
+ free(map);
+ return NULL;
+ }
+
+ return map;
+}
+
+void
+hashmap_free(struct hashmap *map)
+{
+ hashmap_deinit(map);
+ free(map);
+}
+
+void
+hashmap_clear(struct hashmap *map)
+{
+ struct hashmap_iter iter;
+ struct hashmap_link *prev;
+ int i;
+
+ LIBHASHMAP_ASSERT(map != NULL);
+
+ prev = NULL;
+ for (HASHMAP_ITER(map, &iter)) {
+ free(iter.link->key);
+ free(iter.link->value);
+ free(prev);
+ prev = iter.link;
+ }
+ free(prev);
+
+ for (i = 0; i < map->size; i++)
+ map->buckets[i] = NULL;
+}
+
+struct hashmap_link *
+hashmap_get(struct hashmap *map, const void *key, size_t size)
+{
+ struct hashmap_link **iter;
+
+ LIBHASHMAP_ASSERT(map != NULL);
+
+ iter = hashmap_get_linkp(map, key, size);
+
+ return iter ? *iter : NULL;
+}
+
+struct hashmap_link *
+hashmap_pop(struct hashmap *map, const void *key, size_t size)
+{
+ struct hashmap_link **iter;
+
+ LIBHASHMAP_ASSERT(map != NULL);
+
+ iter = hashmap_get_linkp(map, key, size);
+ if (iter) {
+ *iter = (*iter)->next;
+ return *iter;
+ }
+
+ return NULL;
+}
+
+void
+hashmap_link_set(struct hashmap_link *link, void *key, size_t key_size,
+ void *value, size_t value_size)
+{
+ LIBHASHMAP_ASSERT(link != NULL);
+
+ free(link->key);
+ link->key = key;
+ link->key_size = key_size;
+
+ free(link->value);
+ link->value = value;
+ link->value_size = value_size;
+}
+
+void
+hashmap_set(struct hashmap *map, void *key, size_t key_size,
+ void *value, size_t value_size)
+{
+ struct hashmap_link **iter;
+
+ LIBHASHMAP_ASSERT(map != NULL);
+
+ iter = hashmap_get_linkp(map, key, key_size);
+ if (iter == NULL) {
+ iter = &map->buckets[hashmap_key_bucket(map, key, key_size)];
+ while (*iter) iter = &((*iter)->next);
+ }
+
+ if (*iter) {
+ hashmap_link_set(*iter, key, key_size, value, value_size);
+ } else {
+ *iter = hashmap_link_alloc(key, key_size, value, value_size);
+ }
+}
+
+void
+hashmap_iter_init(struct hashmap_iter *iter)
+{
+ LIBHASHMAP_ASSERT(iter != NULL);
+
+ iter->bucket = 0;
+ iter->link = NULL;
+}
+
+bool
+hashmap_iter_next(struct hashmap *map, struct hashmap_iter *iter)
+{
+ int i;
+
+ LIBHASHMAP_ASSERT(map != NULL && iter != NULL);
+
+ 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;
+ int i;
+
+ LIBHASHMAP_ASSERT(data != NULL && size > 0);
+
+ hash = 0;
+ for (i = 0; i < size; i++)
+ hash = 31 * hash + ((uint8_t *) data)[i];
+
+ return hash;
+}
+
diff --git a/src/map.c b/src/map.c
@@ -1,252 +0,0 @@
-#include "map.h"
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-
-#define ASSERT(x) assert((x), __FILE__, __LINE__, #x)
-#define OOM_CHECK(x) assert((x) != NULL, __FILE__, __LINE__, "Out of Memory")
-
-static void assert(int cond, const char *file, int line, const char *condstr);
-static void *memdup(const void *src, size_t size);
-
-static size_t map_key_bucket(struct map *map,
- const void *key, size_t size);
-static bool map_key_cmp(const void *a, size_t asize,
- const void *b, size_t bsize);
-
-static struct map_link **map_get_linkp(struct map *map,
- const void *key, size_t size);
-static struct map_link *map_link_alloc(void *key, size_t key_size,
- void *value, size_t value_size);
-
-void
-assert(int cond, const char *file, int line, const char *condstr)
-{
- if (cond) return;
-
- fprintf(stderr, "CMAP: Assertion failed at %s:%i (%s)\n",
- file, line, condstr);
- exit(1);
-}
-
-void *
-memdup(const void *src, size_t size)
-{
- void *alloc;
-
- alloc = malloc(size);
- if (!alloc) return NULL;
- memcpy(alloc, src, size);
-
- return alloc;
-}
-
-size_t
-map_key_bucket(struct map *map, const void *key, size_t size)
-{
- ASSERT(map != NULL && key != NULL);
-
- return map->hash(key, size) % map->size;
-}
-
-bool
-map_key_cmp(const void *a, size_t asize, const void *b, size_t bsize)
-{
- ASSERT(a != NULL && asize != 0 && b != NULL && bsize != 0);
-
- return asize == bsize && !memcmp(a, b, asize);
-}
-
-struct map_link **
-map_get_linkp(struct map *map, const void *key, size_t size)
-{
- struct map_link **iter, *link;
-
- ASSERT(map != NULL);
-
- iter = &map->buckets[map_key_bucket(map, key, size)];
- while (*iter != NULL) {
- link = *iter;
- if (map_key_cmp(link->key, link->key_size, key, size))
- return iter;
- iter = &(*iter)->next;
- }
-
- return NULL;
-}
-
-struct map_link *
-map_link_alloc(void *key, size_t key_size, void *value, size_t value_size)
-{
- struct map_link *link;
-
- ASSERT(key != NULL && value != NULL);
-
- link = malloc(sizeof(struct map_link));
- OOM_CHECK(link);
- link->key = key;
- link->key_size = key_size;
- link->value = value;
- link->value_size = value_size;
- link->next = NULL;
-
- return link;
-}
-
-void
-map_init(struct map *map, size_t size, map_hash_func hasher)
-{
- ASSERT(map != NULL && size != 0 && hasher != NULL);
-
- map->buckets = calloc(size, sizeof(struct map_link *));
- OOM_CHECK(map->buckets);
- map->size = size;
- map->hash = hasher;
-}
-
-void
-map_deinit(struct map *map)
-{
- ASSERT(map != NULL);
-
- map_clear(map);
- free(map->buckets);
-}
-
-void
-map_clear(struct map *map)
-{
- struct map_iter iter;
- struct map_link *prev;
- int i;
-
- ASSERT(map != NULL);
-
- prev = NULL;
- for (MAP_ITER(map, &iter)) {
- free(iter.link->key);
- free(iter.link->value);
- free(prev);
- prev = iter.link;
- }
- free(prev);
-
- for (i = 0; i < map->size; i++)
- map->buckets[i] = NULL;
-}
-
-struct map_link *
-map_get(struct map *map, const void *key, size_t size)
-{
- struct map_link **iter;
-
- ASSERT(map != NULL);
-
- iter = map_get_linkp(map, key, size);
-
- return iter ? *iter : NULL;
-}
-
-struct map_link *
-map_pop(struct map *map, const void *key, size_t size)
-{
- struct map_link **iter;
-
- ASSERT(map != NULL);
-
- iter = map_get_linkp(map, key, size);
- if (iter) {
- *iter = (*iter)->next;
- return *iter;
- }
-
- return NULL;
-}
-
-void
-map_link_set(struct map_link *link, void *key, size_t key_size,
- void *value, size_t value_size)
-{
- ASSERT(link != NULL);
-
- free(link->key);
- link->key = key;
- link->key_size = key_size;
-
- free(link->value);
- link->value = value;
- link->value_size = value_size;
-}
-
-void
-map_set(struct map *map, void *key, size_t key_size,
- void *value, size_t value_size)
-{
- struct map_link **iter, *link;
-
- ASSERT(map != NULL);
-
- iter = map_get_linkp(map, key, key_size);
- if (iter == NULL) {
- iter = &map->buckets[map_key_bucket(map, key, key_size)];
- while (*iter) iter = &((*iter)->next);
- }
-
- if (*iter) {
- map_link_set(*iter, key, key_size, value, value_size);
- } else {
- *iter = map_link_alloc(key, key_size, value, value_size);
- }
-}
-
-void
-map_iter_init(struct map_iter *iter)
-{
- ASSERT(iter != NULL);
-
- iter->bucket = 0;
- iter->link = NULL;
-}
-
-bool
-map_iter_next(struct map *map, struct map_iter *iter)
-{
- int i;
-
- ASSERT(map != NULL && iter != NULL);
-
- 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
-map_str_hash(const char *data, size_t size)
-{
- uint32_t hash;
- int i;
-
- ASSERT(data != NULL && size > 0);
-
- hash = 0;
- for (i = 0; i < size; i++)
- hash = 31 * hash + data[i];
-
- return hash;
-}
-
diff --git a/src/test.c b/src/test.c
@@ -1,4 +1,4 @@
-#include "map.h"
+#include "hashmap.h"
#include <stdlib.h>
#include <stdio.h>
@@ -7,23 +7,24 @@
int
main(int argc, const char **argv)
{
- struct map map;
- struct map_iter iter;
+ struct hashmap hashmap;
+ struct hashmap_iter iter;
void *key, *value;
int i;
- map_init(&map, 10, map_str_hash);
+ hashmap_init(&hashmap, 10, hashmap_str_hasher);
for (i = 1; i < argc; i++) {
key = strdup(argv[i]);
value = malloc(sizeof(int));
memcpy(value, &i, sizeof(int));
- map_set(&map, key, strlen(key) + 1, value, sizeof(int));
+ hashmap_set(&hashmap, key, strlen(key) + 1,
+ value, sizeof(int));
}
- for (MAP_ITER(&map, &iter)) {
+ for (HASHMAP_ITER(&hashmap, &iter)) {
printf("%s: %i\n", iter.link->key, *(int*)iter.link->value);
}
- map_deinit(&map);
+ hashmap_deinit(&hashmap);
}
