Merge branch 'en/strmap'

[thirdparty/git.git] / hashmap.c

diff --git a/hashmap.c b/hashmap.c
index 09813e1a46676c1475c1ad903f1d9358bf56827e..5009471800e8c61b50bfd670a7714daaa26a01c7 100644 (file)
--- a/hashmap.c
+++ b/hashmap.c
@@ -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,6 +135,7 @@ 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;
@@ -148,7 +151,7 @@ static int always_equal(const void *unused_cmp_data,
 }
 
 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,22 +174,37 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
        map->do_count_items = 1;
 }
 
-void hashmap_free_(struct hashmap *map, ssize_t entry_offset)
+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 (entry_offset >= 0) { /* called by hashmap_free_entries */
-               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_free_entries)
-                        */
-                       free((char *)e - entry_offset);
-       }
+       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));
 }
@@ -195,11 +213,13 @@ 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);
 }
 
 struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
-                       const struct hashmap_entry *entry)
+                                      const struct hashmap_entry *entry)
 {
        struct hashmap_entry *e = entry->next;
        for (; e; e = e->next)
@@ -210,8 +230,12 @@ struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
 
 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 */
        entry->next = map->table[b];
        map->table[b] = entry;
@@ -225,11 +249,15 @@ void hashmap_add(struct hashmap *map, struct hashmap_entry *entry)
 }
 
 struct hashmap_entry *hashmap_remove(struct hashmap *map,
-                                       const struct hashmap_entry *key,
-                                       const void *keydata)
+                                    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;
 
@@ -249,7 +277,7 @@ struct hashmap_entry *hashmap_remove(struct hashmap *map,
 }
 
 struct hashmap_entry *hashmap_put(struct hashmap *map,
-                               struct hashmap_entry *entry)
+                                 struct hashmap_entry *entry)
 {
        struct hashmap_entry *old = hashmap_remove(map, entry, NULL);
        hashmap_add(map, entry);