summaryrefslogtreecommitdiffstats
path: root/lib/ext2fs/hashmap.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:49:25 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:49:25 +0000
commit464df1d5e5ab1322e2dd0a7796939fff1aeefa9a (patch)
tree6a403684e0978f0287d7f0ec0e5aab1fd31a59e1 /lib/ext2fs/hashmap.c
parentInitial commit. (diff)
downloade2fsprogs-464df1d5e5ab1322e2dd0a7796939fff1aeefa9a.tar.xz
e2fsprogs-464df1d5e5ab1322e2dd0a7796939fff1aeefa9a.zip
Adding upstream version 1.47.0.upstream/1.47.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'lib/ext2fs/hashmap.c')
-rw-r--r--lib/ext2fs/hashmap.c109
1 files changed, 109 insertions, 0 deletions
diff --git a/lib/ext2fs/hashmap.c b/lib/ext2fs/hashmap.c
new file mode 100644
index 0000000..697b2bc
--- /dev/null
+++ b/lib/ext2fs/hashmap.c
@@ -0,0 +1,109 @@
+#include "hashmap.h"
+#include <string.h>
+
+struct ext2fs_hashmap {
+ uint32_t size;
+ uint32_t(*hash)(const void *key, size_t len);
+ void(*free)(void*);
+ struct ext2fs_hashmap_entry *first;
+ struct ext2fs_hashmap_entry *last;
+#if __GNUC_PREREQ (4, 8)
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wpedantic"
+#endif
+ struct ext2fs_hashmap_entry *entries[0];
+#if __GNUC_PREREQ (4, 8)
+#pragma GCC diagnostic pop
+#endif
+};
+
+uint32_t ext2fs_djb2_hash(const void *str, size_t size)
+{
+ int c;
+ const char *s = str;
+ uint32_t hash = 5381;
+
+ while (size-- > 0) {
+ c = *s++;
+ hash = ((hash << 5) + hash) + c;
+ }
+ return hash;
+}
+
+struct ext2fs_hashmap *ext2fs_hashmap_create(
+ uint32_t(*hash_fct)(const void*, size_t),
+ void(*free_fct)(void*), size_t size)
+{
+ struct ext2fs_hashmap *h = calloc(sizeof(struct ext2fs_hashmap) +
+ sizeof(struct ext2fs_hashmap_entry) * size, 1);
+ if (!h)
+ return NULL;
+
+ h->size = size;
+ h->free = free_fct;
+ h->hash = hash_fct;
+ h->first = h->last = NULL;
+ return h;
+}
+
+int ext2fs_hashmap_add(struct ext2fs_hashmap *h,
+ void *data, const void *key, size_t key_len)
+{
+ uint32_t hash = h->hash(key, key_len) % h->size;
+ struct ext2fs_hashmap_entry *e = malloc(sizeof(*e));
+
+ if (!e)
+ return -1;
+
+ e->data = data;
+ e->key = key;
+ e->key_len = key_len;
+ e->next = h->entries[hash];
+ h->entries[hash] = e;
+
+ e->list_prev = NULL;
+ e->list_next = h->first;
+ if (h->first)
+ h->first->list_prev = e;
+ h->first = e;
+ if (!h->last)
+ h->last = e;
+
+ return 0;
+}
+
+void *ext2fs_hashmap_lookup(struct ext2fs_hashmap *h, const void *key,
+ size_t key_len)
+{
+ struct ext2fs_hashmap_entry *iter;
+ uint32_t hash = h->hash(key, key_len) % h->size;
+
+ for (iter = h->entries[hash]; iter; iter = iter->next)
+ if (iter->key_len == key_len && !memcmp(iter->key, key, key_len))
+ return iter->data;
+ return NULL;
+}
+
+void *ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap *h,
+ struct ext2fs_hashmap_entry **it)
+{
+ *it = *it ? (*it)->list_next : h->first;
+ return *it ? (*it)->data : NULL;
+}
+
+void ext2fs_hashmap_free(struct ext2fs_hashmap *h)
+{
+ size_t i;
+
+ for (i = 0; i < h->size; ++i) {
+ struct ext2fs_hashmap_entry *it = h->entries[i];
+ while (it) {
+ struct ext2fs_hashmap_entry *tmp = it->next;
+ if (h->free)
+ h->free(it->data);
+ free(it);
+ it = tmp;
+ }
+ }
+ free(h);
+}