diff options
author | Jin Qian <jinqian@google.com> | 2018-01-19 17:44:07 -0800 |
---|---|---|
committer | Jin Qian <jinqian@google.com> | 2018-01-23 16:34:50 -0800 |
commit | 52b7292ce3fd9a82682618270536d2c70bcbd4d2 (patch) | |
tree | da107960e21216e695d250b951ea2c966faad3be /lib | |
parent | 0a10ff5d43dd8047631d6e7cdbadc4af70990268 (diff) | |
download | e2fsprogs-52b7292ce3fd9a82682618270536d2c70bcbd4d2.tar.gz |
e2fsdroid/libext2fs: move hashmap into libext2fs
Also update it so that hash key can be arbitrary length instead of
null terminated string.
Bug: 64109868
Change-Id: Icb0d91d5d753e86edaffcacb043b6f1aa429a528
Diffstat (limited to 'lib')
-rw-r--r-- | lib/ext2fs/Android.bp | 1 | ||||
-rw-r--r-- | lib/ext2fs/hashmap.c | 83 | ||||
-rw-r--r-- | lib/ext2fs/hashmap.h | 38 |
3 files changed, 122 insertions, 0 deletions
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/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 */ |