commit a05990442b383cc70caa9a9543a2725c361f3b47
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 13 Feb 2022 00:01:40 +0100
Core functionality
Diffstat:
A | .gitignore | | | 5 | +++++ |
A | Makefile | | | 42 | ++++++++++++++++++++++++++++++++++++++++++ |
A | include/map.h | | | 48 | ++++++++++++++++++++++++++++++++++++++++++++++++ |
A | libmap.api | | | 15 | +++++++++++++++ |
A | src/map.c | | | 252 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
A | src/test.c | | | 29 | +++++++++++++++++++++++++++++ |
6 files changed, 391 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,5 @@
+compile_commands.json
+build
+.cache
+vgcore*
+test
diff --git a/Makefile b/Makefile
@@ -0,0 +1,42 @@
+CFLAGS = -I include -g
+LDLIBS =
+DEPFLAGS = -MT $@ -MMD -MP -MF build/$*.d
+
+_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)
+
+.PHONY: all clean
+
+all: build/libmap.so build/libmap.a build/test
+
+clean:
+ rm -rf build
+
+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;
+
+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/test: src/test.c build/libmap.a | build
+ $(CC) -o $@ $^ -I include -g
+
diff --git a/include/map.h b/include/map.h
@@ -0,0 +1,48 @@
+#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/libmap.api b/libmap.api
@@ -0,0 +1,15 @@
+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/map.c b/src/map.c
@@ -0,0 +1,252 @@
+#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
@@ -0,0 +1,29 @@
+#include "map.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+int
+main(int argc, const char **argv)
+{
+ struct map map;
+ struct map_iter iter;
+ void *key, *value;
+ int i;
+
+ map_init(&map, 10, map_str_hash);
+
+ 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));
+ }
+
+ for (MAP_ITER(&map, &iter)) {
+ printf("%s: %i\n", iter.link->key, *(int*)iter.link->value);
+ }
+
+ map_deinit(&map);
+}