AOSP: e2fsdroid/libext2fs: move hashmap into libext2fs

Also update it so that hash key can be arbitrary length instead of
null terminated string.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>

Google-Bug-Id: 64109868
Change-Id: Icb0d91d5d753e86edaffcacb043b6f1aa429a528
From AOSP commit: 9491100ffb74b13a10b5b0425b7691c3449ac2e6

5 files changed, 125 insertions, 0 deletions

diff --git a/lib/blkid/dev.c b/lib/blkid/dev.c
index d35513e4..1d62dd88 100644
--- a/lib/blkid/dev.c
+++ b/lib/blkid/dev.c
@@ -13,6 +13,7 @@
 #include "config.h"
 #include <stdlib.h>
 #include <string.h>
+#include <stdint.h>
 
 #include "blkidP.h"
 
diff --git a/lib/ext2fs/Android.bp b/lib/ext2fs/Android.bp
index 427d93be..06a750eb 100644
--- a/lib/ext2fs/Android.bp
+++ b/lib/ext2fs/Android.bp
@@ -47,6 +47,7 @@ cc_library {
         "get_pathname.c",
         "getsize.c",
         "getsectsize.c",
+        "hashmap.c",
         "i_block.c",
         "icount.c",
         "imager.c",
diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index cb81882b..36046d68 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -93,6 +93,7 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
 	get_pathname.o \
 	getsize.o \
 	getsectsize.o \
+	hashmap.o \
 	i_block.o \
 	icount.o \
 	ind_block.o \
@@ -172,6 +173,7 @@ SRCS= ext2_err.c \
 	$(srcdir)/get_pathname.c \
 	$(srcdir)/getsize.c \
 	$(srcdir)/getsectsize.c \
+	$(srcdir)/hashmap.c \
 	$(srcdir)/i_block.c \
 	$(srcdir)/icount.c \
 	$(srcdir)/ind_block.c \
diff --git a/lib/ext2fs/hashmap.c b/lib/ext2fs/hashmap.c
new file mode 100644
index 00000000..ade5d89e
--- /dev/null
+++ b/lib/ext2fs/hashmap.c
@@ -0,0 +1,83 @@
+#include "hashmap.h"
+#include <string.h>
+
+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);
+	h->size = size;
+	h->free = free_fct;
+	h->hash = hash_fct;
+	h->first = h->last = NULL;
+	return h;
+}
+
+void 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));
+
+	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;
+}
+
+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)
+{
+	for (size_t 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);
+}
diff --git a/lib/ext2fs/hashmap.h b/lib/ext2fs/hashmap.h
new file mode 100644
index 00000000..71271866
--- /dev/null
+++ b/lib/ext2fs/hashmap.h
@@ -0,0 +1,38 @@
+#ifndef HASHMAP_H
+# define HASHMAP_H
+
+# include <stdlib.h>
+# include <stdint.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;
+	struct ext2fs_hashmap_entry {
+		void *data;
+		const void *key;
+		size_t key_len;
+		struct ext2fs_hashmap_entry *next;
+		struct ext2fs_hashmap_entry *list_next;
+		struct ext2fs_hashmap_entry *list_prev;
+	} *entries[0];
+};
+
+struct ext2fs_hashmap *ext2fs_hashmap_create(
+				uint32_t(*hash_fct)(const void*, size_t),
+				void(*free_fct)(void*), size_t size);
+void ext2fs_hashmap_add(struct ext2fs_hashmap *h, void *data, const void *key,
+			size_t key_len);
+void *ext2fs_hashmap_lookup(struct ext2fs_hashmap *h, const void *key,
+			    size_t key_len);
+void *ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap *h,
+				   struct ext2fs_hashmap_entry **it);
+void ext2fs_hashmap_del(struct ext2fs_hashmap *h,
+			struct ext2fs_hashmap_entry *e);
+void ext2fs_hashmap_free(struct ext2fs_hashmap *h);
+
+uint32_t ext2fs_djb2_hash(const void *str, size_t size);
+
+#endif /* !HASHMAP_H */