diff options
Diffstat (limited to 'hashmap.c')
| -rw-r--r-- | hashmap.c | 120 |
1 files changed, 82 insertions, 38 deletions
@@ -1,7 +1,7 @@ /* * Generic implementation of hash-based key value mappings. */ -#include "cache.h" +#include "git-compat-util.h" #include "hashmap.h" #define FNV32_BASE ((unsigned int) 0x811c9dc5) @@ -51,7 +51,7 @@ unsigned int memihash(const void *buf, size_t len) } /* - * Incoporate another chunk of data into a memihash + * Incorporate another chunk of data into a memihash * computation. */ unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len) @@ -76,7 +76,7 @@ unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len) static void alloc_table(struct hashmap *map, unsigned int size) { map->tablesize = size; - map->table = xcalloc(size, sizeof(struct hashmap_entry *)); + CALLOC_ARRAY(map->table, size); /* calculate resize thresholds for new size */ map->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100); @@ -92,8 +92,9 @@ static void alloc_table(struct hashmap *map, unsigned int size) } static inline int entry_equals(const struct hashmap *map, - const struct hashmap_entry *e1, const struct hashmap_entry *e2, - const void *keydata) + const struct hashmap_entry *e1, + const struct hashmap_entry *e2, + const void *keydata) { return (e1 == e2) || (e1->hash == e2->hash && @@ -101,7 +102,7 @@ static inline int entry_equals(const struct hashmap *map, } static inline unsigned int bucket(const struct hashmap *map, - const struct hashmap_entry *key) + const struct hashmap_entry *key) { return key->hash & (map->tablesize - 1); } @@ -113,6 +114,7 @@ int hashmap_bucket(const struct hashmap *map, unsigned int hash) static void rehash(struct hashmap *map, unsigned int newsize) { + /* map->table MUST NOT be NULL when this function is called */ unsigned int i, oldsize = map->tablesize; struct hashmap_entry **oldtable = map->table; @@ -133,22 +135,23 @@ static void rehash(struct hashmap *map, unsigned int newsize) static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map, const struct hashmap_entry *key, const void *keydata) { + /* map->table MUST NOT be NULL when this function is called */ struct hashmap_entry **e = &map->table[bucket(map, key)]; while (*e && !entry_equals(map, *e, key, keydata)) e = &(*e)->next; return e; } -static int always_equal(const void *unused_cmp_data, - const void *unused1, - const void *unused2, - const void *unused_keydata) +static int always_equal(const void *cmp_data UNUSED, + const struct hashmap_entry *entry1 UNUSED, + const struct hashmap_entry *entry2 UNUSED, + const void *keydata UNUSED) { return 0; } void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, - const void *cmpfn_data, size_t initial_size) + const void *cmpfn_data, size_t initial_size) { unsigned int size = HASHMAP_INITIAL_SIZE; @@ -171,41 +174,70 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, map->do_count_items = 1; } -void hashmap_free(struct hashmap *map, int free_entries) +static void free_individual_entries(struct hashmap *map, ssize_t entry_offset) +{ + struct hashmap_iter iter; + struct hashmap_entry *e; + + hashmap_iter_init(map, &iter); + while ((e = hashmap_iter_next(&iter))) + /* + * like container_of, but using caller-calculated + * offset (caller being hashmap_clear_and_free) + */ + free((char *)e - entry_offset); +} + +void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset) { if (!map || !map->table) return; - if (free_entries) { - struct hashmap_iter iter; - struct hashmap_entry *e; - hashmap_iter_init(map, &iter); - while ((e = hashmap_iter_next(&iter))) - free(e); - } + if (entry_offset >= 0) /* called by hashmap_clear_entries */ + free_individual_entries(map, entry_offset); + memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *)); + map->shrink_at = 0; + map->private_size = 0; +} + +void hashmap_clear_(struct hashmap *map, ssize_t entry_offset) +{ + if (!map || !map->table) + return; + if (entry_offset >= 0) /* called by hashmap_clear_and_free */ + free_individual_entries(map, entry_offset); free(map->table); memset(map, 0, sizeof(*map)); } -void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata) +struct hashmap_entry *hashmap_get(const struct hashmap *map, + const struct hashmap_entry *key, + const void *keydata) { + if (!map->table) + return NULL; return *find_entry_ptr(map, key, keydata); } -void *hashmap_get_next(const struct hashmap *map, const void *entry) +struct hashmap_entry *hashmap_get_next(const struct hashmap *map, + const struct hashmap_entry *entry) { - struct hashmap_entry *e = ((struct hashmap_entry *) entry)->next; + struct hashmap_entry *e = entry->next; for (; e; e = e->next) if (entry_equals(map, entry, e, NULL)) return e; return NULL; } -void hashmap_add(struct hashmap *map, void *entry) +void hashmap_add(struct hashmap *map, struct hashmap_entry *entry) { - unsigned int b = bucket(map, entry); + unsigned int b; + + if (!map->table) + alloc_table(map, HASHMAP_INITIAL_SIZE); + b = bucket(map, entry); /* add entry */ - ((struct hashmap_entry *) entry)->next = map->table[b]; + entry->next = map->table[b]; map->table[b] = entry; /* fix size and rehash if appropriate */ @@ -216,10 +248,16 @@ void hashmap_add(struct hashmap *map, void *entry) } } -void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata) +struct hashmap_entry *hashmap_remove(struct hashmap *map, + const struct hashmap_entry *key, + const void *keydata) { struct hashmap_entry *old; - struct hashmap_entry **e = find_entry_ptr(map, key, keydata); + struct hashmap_entry **e; + + if (!map->table) + return NULL; + e = find_entry_ptr(map, key, keydata); if (!*e) return NULL; @@ -238,7 +276,8 @@ void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata) return old; } -void *hashmap_put(struct hashmap *map, void *entry) +struct hashmap_entry *hashmap_put(struct hashmap *map, + struct hashmap_entry *entry) { struct hashmap_entry *old = hashmap_remove(map, entry, NULL); hashmap_add(map, entry); @@ -252,7 +291,7 @@ void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter) iter->next = NULL; } -void *hashmap_iter_next(struct hashmap_iter *iter) +struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter) { struct hashmap_entry *current = iter->next; for (;;) { @@ -274,11 +313,16 @@ struct pool_entry { unsigned char data[FLEX_ARRAY]; }; -static int pool_entry_cmp(const void *unused_cmp_data, - const struct pool_entry *e1, - const struct pool_entry *e2, - const unsigned char *keydata) +static int pool_entry_cmp(const void *cmp_data UNUSED, + const struct hashmap_entry *eptr, + const struct hashmap_entry *entry_or_key, + const void *keydata) { + const struct pool_entry *e1, *e2; + + e1 = container_of(eptr, const struct pool_entry, ent); + e2 = container_of(entry_or_key, const struct pool_entry, ent); + return e1->data != keydata && (e1->len != e2->len || memcmp(e1->data, keydata, e1->len)); } @@ -290,18 +334,18 @@ const void *memintern(const void *data, size_t len) /* initialize string pool hashmap */ if (!map.tablesize) - hashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0); + hashmap_init(&map, pool_entry_cmp, NULL, 0); /* lookup interned string in pool */ - hashmap_entry_init(&key, memhash(data, len)); + hashmap_entry_init(&key.ent, memhash(data, len)); key.len = len; - e = hashmap_get(&map, &key, data); + e = hashmap_get_entry(&map, &key, ent, data); if (!e) { /* not found: create it */ FLEX_ALLOC_MEM(e, data, data, len); - hashmap_entry_init(e, key.ent.hash); + hashmap_entry_init(&e->ent, key.ent.hash); e->len = len; - hashmap_add(&map, e); + hashmap_add(&map, &e->ent); } return e->data; } |