From 20ce6fa81cd9f55dca3212699d5949f8ebe7d95b Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sat, 30 Aug 2025 00:01:15 +0300 Subject: add hashmap example + Doesn't quite work yet because expansion isn't implemented yet --- example_hashmap/old/conts.h | 14 +++ example_hashmap/old/main.c | 40 +++++++ example_hashmap/old/map.h | 250 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 304 insertions(+) create mode 100644 example_hashmap/old/conts.h create mode 100644 example_hashmap/old/main.c create mode 100644 example_hashmap/old/map.h (limited to 'example_hashmap/old') diff --git a/example_hashmap/old/conts.h b/example_hashmap/old/conts.h new file mode 100644 index 0000000..fb0094b --- /dev/null +++ b/example_hashmap/old/conts.h @@ -0,0 +1,14 @@ +#ifndef CONTS_H +#define CONTS_H + +#define CONTS_JOIN2(a, b) a##_##b +#define CONTS_JOIN(a, b) CONTS_JOIN2(a, b) + +#define CONTAINER_OF(ptr, type, member) \ + (type *)((char *)(ptr) - offsetof(type, member)) + +#define foreach(name, i, s)\ + for (CONTS_JOIN(name, iter) i = CONTS_JOIN(name, begin)(s);\ + !CONTS_JOIN(name, end)(s, i);\ + i = CONTS_JOIN(name, next)(i)) +#endif /* CONTS_H */ diff --git a/example_hashmap/old/main.c b/example_hashmap/old/main.c new file mode 100644 index 0000000..6c42787 --- /dev/null +++ b/example_hashmap/old/main.c @@ -0,0 +1,40 @@ +#include +#include + +#define MAP_KEY int +#define MAP_TYPE int +#define MAP_HASH(a) CONTS_MAP_NO_HASH(a) +#define MAP_CMP(a, b) ((a) - (b)) +#define MAP_NAME ints +#include + +int main() +{ + /* heuristic, but if we know how many elements we'll need, we should + * give it to the create function. */ + struct ints ints = ints_create(0); + for (int i = 0; i < 1000000; ++i) { + ints_insert(&ints, i, i); + } + assert(ints_len(&ints) == 1000000); + + for (int i = 0; i < 1000000; ++i) { + int *v = ints_find(&ints, i); + assert(v && *v == i); + } + + size_t count = 0; + foreach(ints, iter, &ints) { + assert(iter->key == iter->data); + count++; + } + + assert(count == 1000000); + + for (int i = 0; i < 1000000; ++i) { + ints_remove(&ints, i); + } + + assert(ints_len(&ints) == 0); + ints_destroy(&ints); +} diff --git a/example_hashmap/old/map.h b/example_hashmap/old/map.h new file mode 100644 index 0000000..db1e386 --- /dev/null +++ b/example_hashmap/old/map.h @@ -0,0 +1,250 @@ +#ifndef MAP_KEY +#error "Need map key" +#endif + +#ifndef MAP_TYPE +#error "Need map type" +#endif + +#ifndef MAP_CMP +#error "Need map cmp" +#endif + +#ifndef MAP_HASH +#error "Need map hash" +#endif + +#ifndef MAP_NAME +#error "Need map name" +#endif + +#include +#include +#include + +#include "conts.h" + +#define MAP(a) CONTS_JOIN(MAP_NAME, a) + +#define MAP_TUPLE MAP(tuple) +#define MAP_NODE MAP(node) +#define MAP_BUCKET MAP(bucket) +#define MAP_ROOT MAP_NAME + +#ifndef CONTS_MAP_H +#define CONTS_MAP_H + +static inline size_t conts_map_generic_hash(const char *s, size_t l) +{ + /* djb2 */ + size_t hash = 5381; + for (size_t i = 0; i < l; ++i) + hash = ((hash << 5) + hash) + s[i]; + + return hash; +} + +#define CONTS_MAP_NO_HASH(a) (a) +#define CONTS_MAP_STR_HASH(a) conts_map_generic_hash(a, strlen(a)) + +/* fast modulo pow2 */ +#define CONTS_BUCKET_IDX(hash, pow2, bucket) \ + ((hash) & (((pow2) << bucket) - 1)) + +#endif /* CONTS_MAP_H */ + +static inline size_t MAP(generic_hash)(MAP_KEY *key) +{ + return conts_map_generic_hash((const char *)key, sizeof(*key)); +} + +struct MAP_TUPLE { + MAP_KEY key; + MAP_TYPE data; +}; + +typedef struct MAP_TUPLE *MAP(iter); + +struct MAP_NODE { + struct MAP_BUCKET *bucket; + size_t hash; + struct MAP_TUPLE t; +}; + +struct MAP_BUCKET { + size_t size; /* bucket size */ + struct MAP_BUCKET *next; + struct MAP_NODE nodes[]; +}; + +struct MAP_ROOT { + size_t len; /* number of items */ + size_t count; /* bucket count */ + size_t pow2; /* how many nodes in smallest bucket */ + struct MAP_BUCKET **buckets; +}; + +static inline struct MAP_ROOT MAP(create)(size_t count) +{ + size_t pow2 = 1; + while (pow2 < count) + pow2 <<= 1; + + return (struct MAP_ROOT){ + .len = 0, + .count = 0, + .pow2 = pow2, + .buckets = NULL + }; +} + +static inline void MAP(destroy)(struct MAP_ROOT *root) +{ + for (size_t i = 0; i < root->count; ++i) + free(root->buckets[i]); + + free(root->buckets); +} + +static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key, MAP_TYPE data) +{ + size_t hash = MAP_HASH(key); + /* look through buckets in order */ + for (size_t b = 0; b < root->count; ++b) { + struct MAP_BUCKET *bucket = root->buckets[b]; + size_t idx = CONTS_BUCKET_IDX(hash, root->pow2, b); + + struct MAP_NODE *node = &bucket->nodes[idx]; + /* free to use this slot */ + if (!node->bucket) { + node->bucket = bucket; + node->hash = hash; + node->t.data = data; + node->t.key = key; + root->len++; + return &node->t.data; + } + + /* there already exists a node like this */ + if (node->hash == hash && MAP_CMP(node->t.key, key) == 0) + return &node->t.data; + } + + /* no bucket available, create new one */ + size_t size = root->pow2 << root->count; + size_t bytes = sizeof(struct MAP_BUCKET) + sizeof(struct MAP_NODE) * size; + struct MAP_BUCKET *bucket = calloc(1, bytes); + bucket->size = size; + + size_t buckets_bytes = sizeof(struct MAP_BUCKET *) * (root->count + 1); + root->buckets = realloc(root->buckets, buckets_bytes); + if (root->count != 0) + root->buckets[root->count - 1]->next = bucket; + + root->buckets[root->count] = bucket; + + /* populate node */ + size_t idx = CONTS_BUCKET_IDX(hash, root->pow2, root->count); + struct MAP_NODE *node = &bucket->nodes[idx]; + node->bucket = bucket; + node->hash = hash; + node->t.key = key; + node->t.data = data; + root->count++; + root->len++; + return &node->t.data; +} + +static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key) +{ + if (root->len == 0) + return NULL; + + size_t hash = MAP_HASH(key); + for (size_t b = 0; b < root->count; ++b) { + struct MAP_BUCKET *bucket = root->buckets[b]; + size_t idx = CONTS_BUCKET_IDX(hash, root->pow2, b); + + struct MAP_NODE *node = &bucket->nodes[idx]; + if (node->hash != hash) + continue; + + if (MAP_CMP(node->t.key, key) != 0) + continue; + + return &node->t.data; + } + + return NULL; +} + +static inline void MAP(remove_found)(struct MAP_ROOT *root, MAP_TYPE *data) +{ + struct MAP_TUPLE *tuple = CONTAINER_OF(data, struct MAP_TUPLE, data); + struct MAP_NODE *node = CONTAINER_OF(tuple, struct MAP_NODE, t); + node->bucket = NULL; + root->len--; +} + +static inline void MAP(remove)(struct MAP_ROOT *root, MAP_KEY key) +{ + MAP_TYPE *found = MAP(find)(root, key); + if (!found) + return; + + MAP(remove_found)(root, found); +} + +static inline struct MAP_TUPLE *MAP(find_next)(struct MAP_BUCKET *bucket, struct MAP_TUPLE *tuple) +{ + struct MAP_NODE *node = CONTAINER_OF(tuple, struct MAP_NODE, t); + size_t idx = node - bucket->nodes; + for (; idx < bucket->size; ++idx) { + struct MAP_NODE *candidate = &bucket->nodes[idx]; + if (candidate->bucket) + return &candidate->t; + } + + struct MAP_BUCKET *next = bucket->next; + if (!next) + return NULL; + + return MAP(find_next)(next, &next->nodes[0].t); +} + +static inline struct MAP_TUPLE *MAP(begin)(struct MAP_ROOT *root) +{ + if (root->len == 0) + return NULL; + + struct MAP_BUCKET *bucket = root->buckets[0]; + return MAP(find_next)(bucket, &bucket->nodes[0].t); +} + +static inline struct MAP_TUPLE *MAP(next)(struct MAP_TUPLE *t) +{ + struct MAP_NODE *node = CONTAINER_OF(t, struct MAP_NODE, t); + return MAP(find_next)(node->bucket, &(node + 1)->t); +} + +static inline bool MAP(end)(struct MAP_ROOT *root, struct MAP_TUPLE *t) +{ + (void)root; + return t == NULL; +} + +static inline size_t MAP(len)(struct MAP_ROOT *root) +{ + return root->len; +} + +#undef MAP +#undef MAP_NODE +#undef MAP_TUPLE +#undef MAP_BUCKET +#undef MAP_ROOT +#undef MAP_KEY +#undef MAP_TYPE +#undef MAP_CMP +#undef MAP_HASH +#undef MAP_NAME -- cgit v1.2.3