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 | |
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
-rw-r--r-- | contrib/android/Android.bp | 1 | ||||
-rw-r--r-- | contrib/android/Android.mk | 1 | ||||
-rw-r--r-- | contrib/android/base_fs.c | 11 | ||||
-rw-r--r-- | contrib/android/base_fs.h | 2 | ||||
-rw-r--r-- | contrib/android/basefs_allocator.c | 21 | ||||
-rw-r--r-- | contrib/android/hashmap.c | 76 | ||||
-rw-r--r-- | contrib/android/hashmap.h | 32 | ||||
-rw-r--r-- | lib/ext2fs/Android.bp | 1 | ||||
-rw-r--r-- | lib/ext2fs/hashmap.c | 83 | ||||
-rw-r--r-- | lib/ext2fs/hashmap.h | 38 |
10 files changed, 140 insertions, 126 deletions
diff --git a/contrib/android/Android.bp b/contrib/android/Android.bp index f7fbf666..67844f98 100644 --- a/contrib/android/Android.bp +++ b/contrib/android/Android.bp @@ -16,7 +16,6 @@ cc_binary { "base_fs.c", "perms.c", "basefs_allocator.c", - "hashmap.c", ], target: { host: { diff --git a/contrib/android/Android.mk b/contrib/android/Android.mk index bdfdece5..68d925de 100644 --- a/contrib/android/Android.mk +++ b/contrib/android/Android.mk @@ -10,7 +10,6 @@ e2fsdroid_src_files := \ base_fs.c \ perms.c \ basefs_allocator.c \ - hashmap.c \ e2fsdroid_cflags := -W -Wall -Werror -Wno-error=macro-redefined diff --git a/contrib/android/base_fs.c b/contrib/android/base_fs.c index 2dcb5fe3..14203050 100644 --- a/contrib/android/base_fs.c +++ b/contrib/android/base_fs.c @@ -99,24 +99,25 @@ static void free_base_fs_entry(void *e) } } -struct hashmap *basefs_parse(const char *file, const char *mountpoint) +struct ext2fs_hashmap *basefs_parse(const char *file, const char *mountpoint) { int err; - struct hashmap *entries = NULL; + struct ext2fs_hashmap *entries = NULL; struct basefs_entry *entry; FILE *f = basefs_open(file); if (!f) return NULL; - entries = hashmap_create(djb2_hash, free_base_fs_entry, 1024); + entries = ext2fs_hashmap_create(ext2fs_djb2_hash, free_base_fs_entry, 1024); if (!entries) goto end; while ((entry = basefs_readline(f, mountpoint, &err))) - hashmap_add(entries, entry, entry->path); + ext2fs_hashmap_add(entries, entry, entry->path, + strlen(entry->path)); if (err) { fclose(f); - hashmap_free(entries); + ext2fs_hashmap_free(entries); return NULL; } end: diff --git a/contrib/android/base_fs.h b/contrib/android/base_fs.h index 94bae293..e9f46b4a 100644 --- a/contrib/android/base_fs.h +++ b/contrib/android/base_fs.h @@ -13,6 +13,6 @@ struct basefs_entry { extern struct fsmap_format base_fs_format; -struct hashmap *basefs_parse(const char *file, const char *mountpoint); +struct ext2fs_hashmap *basefs_parse(const char *file, const char *mountpoint); #endif /* !BASE_FS_H */ diff --git a/contrib/android/basefs_allocator.c b/contrib/android/basefs_allocator.c index 3d014a22..c44532f6 100644 --- a/contrib/android/basefs_allocator.c +++ b/contrib/android/basefs_allocator.c @@ -6,7 +6,7 @@ #include "base_fs.h" struct base_fs_allocator { - struct hashmap *entries; + struct ext2fs_hashmap *entries; struct basefs_entry *cur_entry; }; @@ -36,9 +36,9 @@ errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file, { errcode_t retval; struct basefs_entry *e; - struct hashmap_entry *it = NULL; + struct ext2fs_hashmap_entry *it = NULL; struct base_fs_allocator *allocator; - struct hashmap *entries = basefs_parse(file, mountpoint); + struct ext2fs_hashmap *entries = basefs_parse(file, mountpoint); if (!entries) return -1; @@ -49,7 +49,7 @@ errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file, retval = ext2fs_read_bitmaps(fs); if (retval) goto err_bitmap; - while ((e = hashmap_iter_in_order(entries, &it))) + while ((e = ext2fs_hashmap_iter_in_order(entries, &it))) fs_reserve_blocks_range(fs, e->head); allocator->cur_entry = NULL; @@ -64,7 +64,7 @@ errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file, err_bitmap: free(allocator); err_alloc: - hashmap_free(entries); + ext2fs_hashmap_free(entries); return EXIT_FAILURE; } @@ -97,10 +97,10 @@ static errcode_t basefs_block_allocator(ext2_filsys fs, blk64_t goal, void base_fs_alloc_cleanup(ext2_filsys fs) { struct basefs_entry *e; - struct hashmap_entry *it = NULL; + struct ext2fs_hashmap_entry *it = NULL; struct base_fs_allocator *allocator = fs->priv_data; - while ((e = hashmap_iter_in_order(allocator->entries, &it))) { + while ((e = ext2fs_hashmap_iter_in_order(allocator->entries, &it))) { fs_free_blocks_range(fs, e->head); delete_block_ranges(e->head); e->head = e->tail = NULL; @@ -108,7 +108,7 @@ void base_fs_alloc_cleanup(ext2_filsys fs) fs->priv_data = NULL; fs->get_alloc_block2 = NULL; - hashmap_free(allocator->entries); + ext2fs_hashmap_free(allocator->entries); free(allocator); } @@ -123,8 +123,9 @@ errcode_t base_fs_alloc_set_target(ext2_filsys fs, const char *target_path, return 0; if (allocator) - allocator->cur_entry = hashmap_lookup(allocator->entries, - target_path); + allocator->cur_entry = ext2fs_hashmap_lookup(allocator->entries, + target_path, + strlen(target_path)); return 0; } diff --git a/contrib/android/hashmap.c b/contrib/android/hashmap.c deleted file mode 100644 index eee00714..00000000 --- a/contrib/android/hashmap.c +++ /dev/null @@ -1,76 +0,0 @@ -#include "hashmap.h" -#include <string.h> - -uint32_t djb2_hash(const void *str) -{ - int c; - const char *s = str; - uint32_t hash = 5381; - - while ((c = *s++)) - hash = ((hash << 5) + hash) + c; - return hash; -} - -struct hashmap *hashmap_create(uint32_t(*hash_fct)(const void*), - void(*free_fct)(void*), size_t size) -{ - struct hashmap *h = calloc(sizeof(struct hashmap) + - sizeof(struct hashmap_entry) * size, 1); - h->size = size; - h->free = free_fct; - h->hash = hash_fct; - h->first = h->last = NULL; - return h; -} - -void hashmap_add(struct hashmap *h, void *data, const void *key) -{ - uint32_t hash = h->hash(key) % h->size; - struct hashmap_entry *e = malloc(sizeof(*e)); - - e->data = data; - e->key = key; - 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 *hashmap_lookup(struct hashmap *h, const void *key) -{ - struct hashmap_entry *iter; - uint32_t hash = h->hash(key) % h->size; - - for (iter = h->entries[hash]; iter; iter = iter->next) - if (!strcmp(iter->key, key)) - return iter->data; - return NULL; -} - -void *hashmap_iter_in_order(struct hashmap *h, struct hashmap_entry **it) -{ - *it = *it ? (*it)->list_next : h->first; - return *it ? (*it)->data : NULL; -} - -void hashmap_free(struct hashmap *h) -{ - for (size_t i = 0; i < h->size; ++i) { - struct hashmap_entry *it = h->entries[i]; - while (it) { - struct hashmap_entry *tmp = it->next; - if (h->free) - h->free(it->data); - free(it); - it = tmp; - } - } - free(h); -} diff --git a/contrib/android/hashmap.h b/contrib/android/hashmap.h deleted file mode 100644 index 70d0ed19..00000000 --- a/contrib/android/hashmap.h +++ /dev/null @@ -1,32 +0,0 @@ -#ifndef HASHMAP_H -# define HASHMAP_H - -# include <stdlib.h> -# include <stdint.h> - -struct hashmap { - uint32_t size; - uint32_t(*hash)(const void *key); - void(*free)(void*); - struct hashmap_entry *first; - struct hashmap_entry *last; - struct hashmap_entry { - void *data; - const void *key; - struct hashmap_entry *next; - struct hashmap_entry *list_next; - struct hashmap_entry *list_prev; - } *entries[0]; -}; - -struct hashmap *hashmap_create(uint32_t(*hash_fct)(const void*), - void(*free_fct)(void*), size_t size); -void hashmap_add(struct hashmap *h, void *data, const void *key); -void *hashmap_lookup(struct hashmap *h, const void *key); -void *hashmap_iter_in_order(struct hashmap *h, struct hashmap_entry **it); -void hashmap_del(struct hashmap *h, struct hashmap_entry *e); -void hashmap_free(struct hashmap *h); - -uint32_t djb2_hash(const void *str); - -#endif /* !HASHMAP_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/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 */ |