diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | Makefile | 10 | ||||
| -rw-r--r-- | map.c | 116 | ||||
| -rw-r--r-- | map.h | 20 | ||||
| -rw-r--r-- | test.c | 22 |
5 files changed, 170 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..76758b0 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +*.o +test diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..ef4e269 --- /dev/null +++ b/Makefile @@ -0,0 +1,10 @@ +CFLAGS=-Wall -Wextra -std=c99 -pedantic +OBJ=test.o map.o + +all: test + +test: $(OBJ) + $(CC) -o $@ $(CFLAGS) $(OBJ) + +clean: + rm -f test *.o @@ -0,0 +1,116 @@ +#include <stdlib.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> + +#include "map.h" + +void *alloc(size_t nmemb, size_t size) +{ + void *p; + p = calloc(nmemb, size); + if (p == NULL) { + perror("calloc"); + exit(1); + } + return p; +} + +void *ralloc(void *p, size_t size) +{ + p = realloc(p, size); + if (p == NULL) { + perror("realloc"); + exit(1); + } + return p; +} + +static size_t hash(const void *src, size_t len) +{ + const unsigned char *d = (const unsigned char *)src; + size_t h = 0xcbf29ce484222325; + size_t i; + for (i = 0; i < len; i++) { + h ^= d[i]; + h *= 0x100000001b3; + } + return h; +} + +void map_init(MAP *m) +{ + m->cap = 100; + m->len = 0; + m->list = alloc(m->cap, sizeof(NODE*)); +} + +static NODE *mapn_new(const void *key, size_t ksize, const void *val, size_t vsize) +{ + NODE *n; + n = alloc(1, sizeof(NODE)); + n->key = alloc(1, ksize); + n->ksize = ksize; + memcpy(n->key, key, ksize); + n->val = alloc(1, vsize); + n->vsize = vsize; + memcpy(n->val, val, vsize); + return n; +} + +static void mapn_setv(NODE *n, const void *val, size_t vsize) +{ + n->val = ralloc(n->val, vsize); + n->vsize = vsize; + memcpy(n->val, val, vsize); +} + +void map_set(MAP *m, const void *key, size_t ksize, const void *val, size_t vsize) +{ + size_t h; + NODE *n, *next; + h = hash(key, ksize); + h = h % m->cap; + n = m->list[h]; + if (n != NULL) { + if (n->ksize == ksize && memcmp(n->key, key, n->ksize) == 0) { + mapn_setv(n, val, vsize); + } else { + next = mapn_new(key, ksize, val, vsize); + n->next = next; + m->len++; + } + return; + } + n = mapn_new(key, ksize, val, vsize); + m->list[h] = n; + m->len++; +} + +int map_get(MAP *m, const void *key, size_t ksize, void **val, size_t *vsize) +{ + size_t h; + NODE *n; + int ok; + h = hash(key, ksize); + h = h % m->cap; + n = m->list[h]; + if (n == NULL) + return -1; + ok = 0; + while (1) { + if (n->ksize == ksize && memcmp(n->key, key, n->ksize) == 0) { + ok = 1; + break; + } + if (n->next == NULL) { + break; + } + n = n->next; + } + if (!ok) + return -1; + *val = n->val; + *vsize = n->vsize; + return 0; +} @@ -0,0 +1,20 @@ +#ifndef __HASH_H +#define __HASH_H + +typedef struct node { + void *key, *val; + size_t ksize, vsize; + struct node *next; +} NODE; + +typedef struct { + NODE **list; + size_t cap; + size_t len; +} MAP; + +void map_init(MAP *m); +void map_set(MAP *m, const void *key, size_t ksize, const void *val, size_t vsize); +int map_get(MAP *m, const void *key, size_t ksize, void **val, size_t *vsize); + +#endif @@ -0,0 +1,22 @@ +#include <stdio.h> +#include <string.h> + +#include "map.h" + +int main() +{ + MAP m; + const char *k1, *v1; + void *v2; + size_t size; + + map_init(&m); + k1 = "key1"; + v1 = "val1"; + map_set(&m, k1, strlen(k1), v1, strlen(v1)); + v1 = "qweqweqwe"; + map_set(&m, k1, strlen(k1), v1, strlen(v1)); + map_get(&m, k1, strlen(k1), &v2, &size); + fwrite(v2, 1, size, stdout); + putchar('\n'); +} |