{"thread":{"id":"35339","subject":"[PATCH v5 00/14] New hash table implementation","startedAt":"2013-11-14T19:08:37Z","lastAt":"2013-12-18T13:11:08Z","messageCount":20,"participants":["Karsten Blees","Jonathan Nieder"],"isPatch":true,"patchVersion":5,"patchTotal":14},"messages":[{"id":"230634","messageId":"52851FB5.4050406@gmail.com","threadId":"35339","inReplyTo":null,"subject":"[PATCH v5 00/14] New hash table implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:08:37Z","receivedAt":"2013-11-14T19:08:37Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Also here:\nhttps://github.com/kblees/git/commits/kb/hashmap-v5\n\nChanges since v3:\n- changed table resizing and grow / shrink thresholds (#02)\n- hashmap_free: changed free_function to boolean (#02, #06, #07, #09)\n- swapped xcalloc args (num elements, element size) (#02)\n- fixed pointer cast formatting \"(type*)\" -> \"(type *)\" (#02)\n- removed function pointer casts \"(*fn)(...)\" -> \"fn(...)\" (#02)\n- api-hashmap.txt: clarified removal / replacement of entries (#02)\n- update-index.c: fixed const-casts (#13, #14)\n\nKarsten\n\n\nJens Lehmann (1):\n submodule: don't access the .gitmodules cache entry after removing it\n\nKarsten Blees (13):\n add a hashtable implementation that supports O(1) removal\n buitin/describe.c: use new hash map implementation\n diffcore-rename.c: move code around to prepare for the next patch\n diffcore-rename.c: simplify finding exact renames\n diffcore-rename.c: use new hash map implementation\n name-hash.c: use new hash map implementation for directories\n name-hash.c: remove unreferenced directory entries\n name-hash.c: use new hash map implementation for cache entries\n name-hash.c: remove cache entries instead of marking them CE_UNHASHED\n remove old hash.[ch] implementation\n fix 'git update-index --verbose --again' output\n builtin/update-index.c: cleanup update_one\n read-cache.c: fix memory leaks caused by removed cache entries\n\n Documentation/technical/api-hash.txt | 52 -------\n Documentation/technical/api-hashmap.txt | 235 +++++++++++++++++++++++++++++\n Makefile | 5 +-\n builtin/describe.c | 53 +++----\n builtin/rm.c | 2 +-\n builtin/update-index.c | 39 +++--\n cache.h | 18 +--\n diffcore-rename.c | 185 ++++++++---------------\n hash.c | 110 --------------\n hash.h | 50 -------\n hashmap.c | 228 ++++++++++++++++++++++++++++\n hashmap.h | 71 +++++++++\n name-hash.c | 156 +++++++------------\n read-cache.c | 10 +-\n resolve-undo.c | 7 +-\n submodule.c | 25 +---\n t/t0011-hashmap.sh | 240 ++++++++++++++++++++++++++++++\n test-hashmap.c | 256 ++++++++++++++++++++++++++++++++\n unpack-trees.c | 3 +-\n 19 files changed, 1216 insertions(+), 529 deletions(-)\n delete mode 100644 Documentation/technical/api-hash.txt\n create mode 100644 Documentation/technical/api-hashmap.txt\n delete mode 100644 hash.c\n delete mode 100644 hash.h\n create mode 100644 hashmap.c\n create mode 100644 hashmap.h\n create mode 100755 t/t0011-hashmap.sh\n create mode 100644 test-hashmap.c\n\n--\n\ngit diff kb/hashmap-v4:\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex fc46e56..b2280f1 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -42,11 +42,6 @@ parameters that have the same hash code. When looking up an entry, the `key`\n and `keydata` parameters to hashmap_get and hashmap_remove are always passed\n as second and third argument, respectively. Otherwise, `keydata` is NULL.\n \n-`void (*hashmap_free_fn)(void *entry)`::\n-\n-\tUser-supplied function to free a hashmap_entry. If entries are simply\n-\tmalloc'ed memory, use stdlib's free() function.\n-\n Functions\n ---------\n \n@@ -76,14 +71,14 @@ If the total number of entries is known in advance, the `initial_size`\n parameter may be used to preallocate a sufficiently large table and thus\n prevent expensive resizing. If 0, the table is dynamically resized.\n \n-`void hashmap_free(struct hashmap *map, hashmap_free_fn free_function)`::\n+`void hashmap_free(struct hashmap *map, int free_entries)`::\n \n \tFrees a hashmap structure and allocated memory.\n +\n `map` is the hashmap to free.\n +\n-If `free_function` is specified (not NULL), it is called to free each\n-hashmap_entry in the map. If entries are simply malloc'ed, use stdlib's free().\n+If `free_entries` is true, each hashmap_entry in the map is freed as well\n+(using stdlib's free()).\n \n `void hashmap_entry_init(void *entry, int hash)`::\n \n@@ -127,17 +122,20 @@ call to `hashmap_get` or `hashmap_get_next`.\n \n `void *hashmap_put(struct hashmap *map, void *entry)`::\n \n-\tAdds or replaces a hashmap entry.\n+\tAdds or replaces a hashmap entry. If the hashmap contains duplicate\n+\tentries equal to the specified entry, only one of them will be replaced.\n +\n `map` is the hashmap structure.\n +\n-`entry` is the entry to add or update.\n+`entry` is the entry to add or replace.\n +\n-Returns the previous entry, or NULL if not found (i.e. the entry was added).\n+Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n \n `void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::\n \n-\tRemoves a hashmap entry matching the specified key.\n+\tRemoves a hashmap entry matching the specified key. If the hashmap\n+\tcontains duplicate entries equal to the specified key, only one of\n+\tthem will be removed.\n +\n `map` is the hashmap structure.\n +\n@@ -183,14 +181,14 @@ static int long2double_cmp(const struct long2double *e1, const struct long2doubl\n \treturn !(e1->key == e2->key);\n }\n \n-void long2double_init()\n+void long2double_init(void)\n {\n \thashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);\n }\n \n-void long2double_free()\n+void long2double_free(void)\n {\n-\thashmap_free(&map, free);\n+\thashmap_free(&map, 1);\n }\n \n static struct long2double *find_entry(long key)\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex acd992d..00313f3 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -559,7 +559,7 @@ static int do_reupdate(int ac, const char **av,\n \t\tconst struct cache_entry *ce = active_cache[pos];\n \t\tstruct cache_entry *old = NULL;\n \t\tint save_nr;\n-\t\tconst char *path;\n+\t\tchar *path;\n \n \t\tif (ce_stage(ce) || !ce_path_match(ce, &pathspec))\n \t\t\tcontinue;\n@@ -838,7 +838,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t\tupdate_one(p);\n \t\t\tif (set_executable_bit)\n \t\t\t\tchmod_path(set_executable_bit, p);\n-\t\t\tfree(p);\n+\t\t\tfree((char *)p);\n \t\t\tctx.argc--;\n \t\t\tctx.argv++;\n \t\t\tbreak;\n@@ -880,7 +880,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t\tupdate_one(p);\n \t\t\tif (set_executable_bit)\n \t\t\t\tchmod_path(set_executable_bit, p);\n-\t\t\tfree(p);\n+\t\t\tfree((char *)p);\n \t\t}\n \t\tstrbuf_release(&nbuf);\n \t\tstrbuf_release(&buf);\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex d996c6a..9b4f068 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -343,7 +343,7 @@ static int find_exact_renames(struct diff_options *options)\n \t\trenames += find_identical_files(&file_table, i, options);\n \n \t/* Free the hash data structure and entries */\n-\thashmap_free(&file_table, free);\n+\thashmap_free(&file_table, 1);\n \n \treturn renames;\n }\ndiff --git a/hashmap.c b/hashmap.c\nindex 3a9f8c1..d1b8056 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -29,7 +29,7 @@ unsigned int strihash(const char *str)\n unsigned int memhash(const void *buf, size_t len)\n {\n \tunsigned int hash = FNV32_BASE;\n-\tunsigned char *ucbuf = (unsigned char*) buf;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n \twhile (len--) {\n \t\tunsigned int c = *ucbuf++;\n \t\thash = (hash * FNV32_PRIME) ^ c;\n@@ -40,7 +40,7 @@ unsigned int memhash(const void *buf, size_t len)\n unsigned int memihash(const void *buf, size_t len)\n {\n \tunsigned int hash = FNV32_BASE;\n-\tunsigned char *ucbuf = (unsigned char*) buf;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n \twhile (len--) {\n \t\tunsigned int c = *ucbuf++;\n \t\tif (c >= 'a' && c <= 'z')\n@@ -52,17 +52,33 @@ unsigned int memihash(const void *buf, size_t len)\n \n #define HASHMAP_INITIAL_SIZE 64\n /* grow / shrink by 2^2 */\n-#define HASHMAP_GROW 2\n-/* grow if > 80% full (to 20%) */\n-#define HASHMAP_GROW_AT 1.25\n-/* shrink if < 16.6% full (to 66.6%) */\n-#define HASHMAP_SHRINK_AT 6\n+#define HASHMAP_RESIZE_BITS 2\n+/* load factor in percent */\n+#define HASHMAP_LOAD_FACTOR 80\n+\n+static void alloc_table(struct hashmap *map, unsigned int size)\n+{\n+\tmap->tablesize = size;\n+\tmap->table = xcalloc(size, sizeof(struct hashmap_entry *));\n+\n+\t/* calculate resize thresholds for new size */\n+\tmap->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100);\n+\tif (size <= HASHMAP_INITIAL_SIZE)\n+\t\tmap->shrink_at = 0;\n+\telse\n+\t\t/*\n+\t\t * The shrink-threshold must be slightly smaller than\n+\t\t * (grow-threshold / resize-factor) to prevent erratic resizing,\n+\t\t * thus we divide by (resize-factor + 1).\n+\t\t */\n+\t\tmap->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1);\n+}\n \n static inline int entry_equals(const struct hashmap *map,\n \t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2,\n \t\tconst void *keydata)\n {\n-\treturn (e1 == e2) || (e1->hash == e2->hash && !(*map->cmpfn)(e1, e2, keydata));\n+\treturn (e1 == e2) || (e1->hash == e2->hash && !map->cmpfn(e1, e2, keydata));\n }\n \n static inline unsigned int bucket(const struct hashmap *map,\n@@ -76,8 +92,7 @@ static void rehash(struct hashmap *map, unsigned int newsize)\n \tunsigned int i, oldsize = map->tablesize;\n \tstruct hashmap_entry **oldtable = map->table;\n \n-\tmap->tablesize = newsize;\n-\tmap->table = xcalloc(sizeof(struct hashmap_entry*), map->tablesize);\n+\talloc_table(map, newsize);\n \tfor (i = 0; i < oldsize; i++) {\n \t\tstruct hashmap_entry *e = oldtable[i];\n \t\twhile (e) {\n@@ -108,26 +123,28 @@ static int always_equal(const void *unused1, const void *unused2, const void *un\n void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n \t\tsize_t initial_size)\n {\n+\tunsigned int size = HASHMAP_INITIAL_SIZE;\n \tmap->size = 0;\n \tmap->cmpfn = equals_function ? equals_function : always_equal;\n+\n \t/* calculate initial table size and allocate the table */\n-\tmap->tablesize = HASHMAP_INITIAL_SIZE;\n-\tinitial_size *= HASHMAP_GROW_AT;\n-\twhile (initial_size > map->tablesize)\n-\t\tmap->tablesize <<= HASHMAP_GROW;\n-\tmap->table = xcalloc(sizeof(struct hashmap_entry*), map->tablesize);\n+\tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n+\t\t\t/ HASHMAP_LOAD_FACTOR);\n+\twhile (initial_size > size)\n+\t\tsize <<= HASHMAP_RESIZE_BITS;\n+\talloc_table(map, size);\n }\n \n-void hashmap_free(struct hashmap *map, hashmap_free_fn free_function)\n+void hashmap_free(struct hashmap *map, int free_entries)\n {\n \tif (!map || !map->table)\n \t\treturn;\n-\tif (free_function) {\n+\tif (free_entries) {\n \t\tstruct hashmap_iter iter;\n \t\tstruct hashmap_entry *e;\n \t\thashmap_iter_init(map, &iter);\n \t\twhile ((e = hashmap_iter_next(&iter)))\n-\t\t\t(*free_function)(e);\n+\t\t\tfree(e);\n \t}\n \tfree(map->table);\n \tmemset(map, 0, sizeof(*map));\n@@ -140,7 +157,7 @@ void *hashmap_get(const struct hashmap *map, const void *key, const void *keydat\n \n void *hashmap_get_next(const struct hashmap *map, const void *entry)\n {\n-\tstruct hashmap_entry *e = ((struct hashmap_entry*) entry)->next;\n+\tstruct hashmap_entry *e = ((struct hashmap_entry *) entry)->next;\n \tfor (; e; e = e->next)\n \t\tif (entry_equals(map, entry, e, NULL))\n \t\t\treturn e;\n@@ -152,13 +169,13 @@ void hashmap_add(struct hashmap *map, void *entry)\n \tunsigned int b = bucket(map, entry);\n \n \t/* add entry */\n-\t((struct hashmap_entry*) entry)->next = map->table[b];\n+\t((struct hashmap_entry *) entry)->next = map->table[b];\n \tmap->table[b] = entry;\n \n \t/* fix size and rehash if appropriate */\n \tmap->size++;\n-\tif (map->size * HASHMAP_GROW_AT > map->tablesize)\n-\t\trehash(map, map->tablesize << HASHMAP_GROW);\n+\tif (map->size > map->grow_at)\n+\t\trehash(map, map->tablesize << HASHMAP_RESIZE_BITS);\n }\n \n void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)\n@@ -175,9 +192,8 @@ void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)\n \n \t/* fix size and rehash if appropriate */\n \tmap->size--;\n-\tif (map->tablesize > HASHMAP_INITIAL_SIZE &&\n-\t map->size * HASHMAP_SHRINK_AT < map->tablesize)\n-\t\trehash(map, map->tablesize >> HASHMAP_GROW);\n+\tif (map->size < map->shrink_at)\n+\t\trehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);\n \treturn old;\n }\n \ndiff --git a/hashmap.h b/hashmap.h\nindex eea003a..f5b3b61 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -22,12 +22,11 @@ struct hashmap_entry {\n \n typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n \t\tconst void *keydata);\n-typedef void (*hashmap_free_fn)(void *entry);\n \n struct hashmap {\n \tstruct hashmap_entry **table;\n \thashmap_cmp_fn cmpfn;\n-\tunsigned int size, tablesize;\n+\tunsigned int size, tablesize, grow_at, shrink_at;\n };\n \n struct hashmap_iter {\n@@ -40,7 +39,7 @@ struct hashmap_iter {\n \n extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n \t\tsize_t initial_size);\n-extern void hashmap_free(struct hashmap *map, hashmap_free_fn free_function);\n+extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\n \ndiff --git a/name-hash.c b/name-hash.c\nindex 8871d8e..9a3bd3f 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -240,6 +240,6 @@ void free_name_hash(struct index_state *istate)\n \t\treturn;\n \tistate->name_hash_initialized = 0;\n \n-\thashmap_free(&istate->name_hash, NULL);\n-\thashmap_free(&istate->dir_hash, free);\n+\thashmap_free(&istate->name_hash, 0);\n+\thashmap_free(&istate->dir_hash, 1);\n }\ndiff --git a/t/t0011-hashmap.sh b/t/t0011-hashmap.sh\nindex 6c699d5..391e2b6 100755\n--- a/t/t0011-hashmap.sh\n+++ b/t/t0011-hashmap.sh\n@@ -221,13 +221,17 @@ test_expect_success 'grow / shrink' '\n \techo NULL >> expect\n \techo size >> in &&\n \techo 256 52 >> expect &&\n-\tfor n in $(test_seq 10)\n+\tfor n in $(test_seq 12)\n \tdo\n \t\techo remove key$n >> in &&\n \t\techo value$n >> expect\n \tdone &&\n \techo size >> in &&\n-\techo 64 42 >> expect &&\n+\techo 256 40 >> expect &&\n+\techo remove key40 >> in &&\n+\techo value40 >> expect &&\n+\techo size >> in &&\n+\techo 64 39 >> expect &&\n \tcat in | test-hashmap > out &&\n \ttest_cmp expect out\n \ndiff --git a/test-hashmap.c b/test-hashmap.c\nindex 333b7b3..7e86f88 100644\n--- a/test-hashmap.c\n+++ b/test-hashmap.c\n@@ -71,7 +71,7 @@ static unsigned int hash(unsigned int method, unsigned int i, const char *key)\n }\n \n /*\n- * Test insert performance of hashmap.[ch]\n+ * Test performance of hashmap.[ch]\n * Usage: time echo \"perfhashmap method rounds\" | test-hashmap\n */\n static void perf_hashmap(unsigned int method, unsigned int rounds)\n@@ -82,7 +82,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\n \tunsigned int *hashes;\n \tunsigned int i, j;\n \n-\tentries = malloc(TEST_SIZE * sizeof(struct test_entry*));\n+\tentries = malloc(TEST_SIZE * sizeof(struct test_entry *));\n \thashes = malloc(TEST_SIZE * sizeof(int));\n \tfor (i = 0; i < TEST_SIZE; i++) {\n \t\tsnprintf(buf, sizeof(buf), \"%i\", i);\n@@ -101,7 +101,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\n \t\t\t\thashmap_add(&map, entries[i]);\n \t\t\t}\n \n-\t\t\thashmap_free(&map, NULL);\n+\t\t\thashmap_free(&map, 0);\n \t\t}\n \t} else {\n \t\t/* test map lookups */\n@@ -122,7 +122,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\n \t\t\t}\n \t\t}\n \n-\t\thashmap_free(&map, NULL);\n+\t\thashmap_free(&map, 0);\n \t}\n }\n \n@@ -251,6 +251,6 @@ int main(int argc, char *argv[])\n \t\t}\n \t}\n \n-\thashmap_free(&map, free);\n+\thashmap_free(&map, 1);\n \treturn 0;\n }\n"},{"id":"230635","messageId":"528521BC.8080908@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 01/14] submodule: don't access the .gitmodules cache entry after removing it","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:17:16Z","receivedAt":"2013-11-14T19:17:16Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"From: Jens Lehmann \n\nCommit 5fee995244e introduced the stage_updated_gitmodules() function to\nadd submodule configuration updates to the index. It assumed that even\nafter calling remove_cache_entry_at() the same cache entry would still be\nvalid. This was true in the old days, as cache entries could never be\nfreed, but that is not so sure in the present as there is ongoing work to\nfree removed cache entries, which makes this code segfault.\n\nFix that by calling add_file_to_cache() instead of open coding it. Also\nremove the \"could not find .gitmodules in index\" warning, as that won't\nhappen in regular use cases (and by then just silently adding it to the\nindex we do the right thing).\n\nThanks-to: Karsten Blees \nSigned-off-by: Jens Lehmann \nSigned-off-by: Junio C Hamano \n---\n submodule.c | 25 +------------------------\n 1 file changed, 1 insertion(+), 24 deletions(-)\n\ndiff --git a/submodule.c b/submodule.c\nindex 1905d75..e388487 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -116,30 +116,7 @@ int remove_path_from_gitmodules(const char *path)\n \n void stage_updated_gitmodules(void)\n {\n-\tstruct strbuf buf = STRBUF_INIT;\n-\tstruct stat st;\n-\tint pos;\n-\tstruct cache_entry *ce;\n-\tint namelen = strlen(\".gitmodules\");\n-\n-\tpos = cache_name_pos(\".gitmodules\", namelen);\n-\tif (pos < 0) {\n-\t\twarning(_(\"could not find .gitmodules in index\"));\n-\t\treturn;\n-\t}\n-\tce = active_cache[pos];\n-\tce->ce_flags = namelen;\n-\tif (strbuf_read_file(&buf, \".gitmodules\", 0) < 0)\n-\t\tdie(_(\"reading updated .gitmodules failed\"));\n-\tif (lstat(\".gitmodules\", &st) < 0)\n-\t\tdie_errno(_(\"unable to stat updated .gitmodules\"));\n-\tfill_stat_cache_info(ce, &st);\n-\tce->ce_mode = ce_mode_from_stat(ce, st.st_mode);\n-\tif (remove_cache_entry_at(pos) < 0)\n-\t\tdie(_(\"unable to remove .gitmodules from index\"));\n-\tif (write_sha1_file(buf.buf, buf.len, blob_type, ce->sha1))\n-\t\tdie(_(\"adding updated .gitmodules failed\"));\n-\tif (add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE))\n+\tif (add_file_to_cache(\".gitmodules\", 0))\n \t\tdie(_(\"staging updated .gitmodules failed\"));\n }\n \n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230636","messageId":"528521E2.7090305@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 02/14] add a hashtable implementation that supports O(1) removal","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:17:54Z","receivedAt":"2013-11-14T19:17:54Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"The existing hashtable implementation (in hash.[ch]) uses open addressing\n(i.e. resolve hash collisions by distributing entries across the table).\nThus, removal is difficult to implement with less than O(n) complexity.\nResolving collisions of entries with identical hashes (e.g. via chaining)\nis left to the client code.\n\nAdd a hashtable implementation that supports O(1) removal and is slightly\neasier to use due to builtin entry chaining.\n\nSupports all basic operations init, free, get, add, remove and iteration.\n\nAlso includes ready-to-use hash functions based on the public domain FNV-1\nalgorithm (http://www.isthe.com/chongo/tech/comp/fnv).\n\nThe per-entry data structure (hashmap_entry) is piggybacked in front of\nthe client's data structure to save memory. See test-hashmap.c for usage\nexamples.\n\nThe hashtable is resized by a factor of four when 80% full. With these\nsettings, average memory consumption is about 2/3 of hash.[ch], and\ninsertion is about twice as fast due to less frequent resizing.\n\nLookups are also slightly faster, because entries are strictly confined to\ntheir bucket (i.e. no data of other buckets needs to be traversed).\n\nSigned-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n Documentation/technical/api-hashmap.txt | 235 ++++++++++++++++++++++\n Makefile | 3 +\n hashmap.c | 228 +++++++++++++++++++++\n hashmap.h | 71 +++++++\n t/t0011-hashmap.sh | 240 ++++++++++++++++++++++\n test-hashmap.c | 340 ++++++++++++++++++++++++++++++++\n 6 files changed, 1117 insertions(+)\n create mode 100644 Documentation/technical/api-hashmap.txt\n create mode 100644 hashmap.c\n create mode 100644 hashmap.h\n create mode 100755 t/t0011-hashmap.sh\n create mode 100644 test-hashmap.c\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nnew file mode 100644\nindex 0000000..b2280f1\n--- /dev/null\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -0,0 +1,235 @@\n+hashmap API\n+===========\n+\n+The hashmap API is a generic implementation of hash-based key-value mappings.\n+\n+Data Structures\n+---------------\n+\n+`struct hashmap`::\n+\n+\tThe hash table structure.\n++\n+The `size` member keeps track of the total number of entries. The `cmpfn`\n+member is a function used to compare two entries for equality. The `table` and\n+`tablesize` members store the hash table and its size, respectively.\n+\n+`struct hashmap_entry`::\n+\n+\tAn opaque structure representing an entry in the hash table, which must\n+\tbe used as first member of user data structures. Ideally it should be\n+\tfollowed by an int-sized member to prevent unused memory on 64-bit\n+\tsystems due to alignment.\n++\n+The `hash` member is the entry's hash code and the `next` member points to the\n+next entry in case of collisions (i.e. if multiple entries map to the same\n+bucket).\n+\n+`struct hashmap_iter`::\n+\n+\tAn iterator structure, to be used with hashmap_iter_* functions.\n+\n+Types\n+-----\n+\n+`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::\n+\n+\tUser-supplied function to test two hashmap entries for equality. Shall\n+\treturn 0 if the entries are equal.\n++\n+This function is always called with non-NULL `entry` / `entry_or_key`\n+parameters that have the same hash code. When looking up an entry, the `key`\n+and `keydata` parameters to hashmap_get and hashmap_remove are always passed\n+as second and third argument, respectively. Otherwise, `keydata` is NULL.\n+\n+Functions\n+---------\n+\n+`unsigned int strhash(const char *buf)`::\n+`unsigned int strihash(const char *buf)`::\n+`unsigned int memhash(const void *buf, size_t len)`::\n+`unsigned int memihash(const void *buf, size_t len)`::\n+\n+\tReady-to-use hash functions for strings, using the FNV-1 algorithm (see\n+\thttp://www.isthe.com/chongo/tech/comp/fnv).\n++\n+`strhash` and `strihash` take 0-terminated strings, while `memhash` and\n+`memihash` operate on arbitrary-length memory.\n++\n+`strihash` and `memihash` are case insensitive versions.\n+\n+`void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`::\n+\n+\tInitializes a hashmap structure.\n++\n+`map` is the hashmap to initialize.\n++\n+The `equals_function` can be specified to compare two entries for equality.\n+If NULL, entries are considered equal if their hash codes are equal.\n++\n+If the total number of entries is known in advance, the `initial_size`\n+parameter may be used to preallocate a sufficiently large table and thus\n+prevent expensive resizing. If 0, the table is dynamically resized.\n+\n+`void hashmap_free(struct hashmap *map, int free_entries)`::\n+\n+\tFrees a hashmap structure and allocated memory.\n++\n+`map` is the hashmap to free.\n++\n+If `free_entries` is true, each hashmap_entry in the map is freed as well\n+(using stdlib's free()).\n+\n+`void hashmap_entry_init(void *entry, int hash)`::\n+\n+\tInitializes a hashmap_entry structure.\n++\n+`entry` points to the entry to initialize.\n++\n+`hash` is the hash code of the entry.\n+\n+`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::\n+\n+\tReturns the hashmap entry for the specified key, or NULL if not found.\n++\n+`map` is the hashmap structure.\n++\n+`key` is a hashmap_entry structure (or user data structure that starts with\n+hashmap_entry) that has at least been initialized with the proper hash code\n+(via `hashmap_entry_init`).\n++\n+If an entry with matching hash code is found, `key` and `keydata` are passed\n+to `hashmap_cmp_fn` to decide whether the entry matches the key.\n+\n+`void *hashmap_get_next(const struct hashmap *map, const void *entry)`::\n+\n+\tReturns the next equal hashmap entry, or NULL if not found. This can be\n+\tused to iterate over duplicate entries (see `hashmap_add`).\n++\n+`map` is the hashmap structure.\n++\n+`entry` is the hashmap_entry to start the search from, obtained via a previous\n+call to `hashmap_get` or `hashmap_get_next`.\n+\n+`void hashmap_add(struct hashmap *map, void *entry)`::\n+\n+\tAdds a hashmap entry. This allows to add duplicate entries (i.e.\n+\tseparate values with the same key according to hashmap_cmp_fn).\n++\n+`map` is the hashmap structure.\n++\n+`entry` is the entry to add.\n+\n+`void *hashmap_put(struct hashmap *map, void *entry)`::\n+\n+\tAdds or replaces a hashmap entry. If the hashmap contains duplicate\n+\tentries equal to the specified entry, only one of them will be replaced.\n++\n+`map` is the hashmap structure.\n++\n+`entry` is the entry to add or replace.\n++\n+Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n+\n+`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::\n+\n+\tRemoves a hashmap entry matching the specified key. If the hashmap\n+\tcontains duplicate entries equal to the specified key, only one of\n+\tthem will be removed.\n++\n+`map` is the hashmap structure.\n++\n+`key` is a hashmap_entry structure (or user data structure that starts with\n+hashmap_entry) that has at least been initialized with the proper hash code\n+(via `hashmap_entry_init`).\n++\n+If an entry with matching hash code is found, `key` and `keydata` are\n+passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n++\n+Returns the removed entry, or NULL if not found.\n+\n+`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::\n+`void *hashmap_iter_next(struct hashmap_iter *iter)`::\n+`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::\n+\n+\tUsed to iterate over all entries of a hashmap.\n++\n+`hashmap_iter_init` initializes a `hashmap_iter` structure.\n++\n+`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no\n+more entries.\n++\n+`hashmap_iter_first` is a combination of both (i.e. initializes the iterator\n+and returns the first entry, if any).\n+\n+Usage example\n+-------------\n+\n+Here's a simple usage example that maps long keys to double values.\n+[source,c]\n+------------\n+struct hashmap map;\n+\n+struct long2double {\n+\tstruct hashmap_entry ent; /* must be the first member! */\n+\tlong key;\n+\tdouble value;\n+};\n+\n+static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)\n+{\n+\treturn !(e1->key == e2->key);\n+}\n+\n+void long2double_init(void)\n+{\n+\thashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);\n+}\n+\n+void long2double_free(void)\n+{\n+\thashmap_free(&map, 1);\n+}\n+\n+static struct long2double *find_entry(long key)\n+{\n+\tstruct long2double k;\n+\thashmap_entry_init(&k, memhash(&key, sizeof(long)));\n+\tk.key = key;\n+\treturn hashmap_get(&map, &k, NULL);\n+}\n+\n+double get_value(long key)\n+{\n+\tstruct long2double *e = find_entry(key);\n+\treturn e ? e->value : 0;\n+}\n+\n+void set_value(long key, double value)\n+{\n+\tstruct long2double *e = find_entry(key);\n+\tif (!e) {\n+\t\te = malloc(sizeof(struct long2double));\n+\t\thashmap_entry_init(e, memhash(&key, sizeof(long)));\n+\t\te->key = key;\n+\t\thashmap_add(&map, e);\n+\t}\n+\te->value = value;\n+}\n+------------\n+\n+Using variable-sized keys\n+-------------------------\n+\n+The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary\n+`hashmap_entry` structure as key to find the correct entry. If the key data is\n+variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable\n+to create a full-fledged entry structure on the heap and copy all the key data\n+into the structure.\n+\n+In this case, the `keydata` parameter can be used to pass\n+variable-sized key data directly to the comparison function, and the `key`\n+parameter can be a stripped-down, fixed size entry structure allocated on the\n+stack.\n+\n+See test-hashmap.c for an example using arbitrary-length strings as keys.\ndiff --git a/Makefile b/Makefile\nindex 504931f..75bb1a6 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -555,6 +555,7 @@ TEST_PROGRAMS_NEED_X += test-date\n TEST_PROGRAMS_NEED_X += test-delta\n TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n TEST_PROGRAMS_NEED_X += test-genrandom\n+TEST_PROGRAMS_NEED_X += test-hashmap\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-line-buffer\n TEST_PROGRAMS_NEED_X += test-match-trees\n@@ -673,6 +674,7 @@ LIB_H += gpg-interface.h\n LIB_H += graph.h\n LIB_H += grep.h\n LIB_H += hash.h\n+LIB_H += hashmap.h\n LIB_H += help.h\n LIB_H += http.h\n LIB_H += kwset.h\n@@ -804,6 +806,7 @@ LIB_OBJS += gpg-interface.o\n LIB_OBJS += graph.o\n LIB_OBJS += grep.o\n LIB_OBJS += hash.o\n+LIB_OBJS += hashmap.o\n LIB_OBJS += help.o\n LIB_OBJS += hex.o\n LIB_OBJS += ident.o\ndiff --git a/hashmap.c b/hashmap.c\nnew file mode 100644\nindex 0000000..d1b8056\n--- /dev/null\n+++ b/hashmap.c\n@@ -0,0 +1,228 @@\n+/*\n+ * Generic implementation of hash-based key value mappings.\n+ */\n+#include \"cache.h\"\n+#include \"hashmap.h\"\n+\n+#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n+#define FNV32_PRIME ((unsigned int) 0x01000193)\n+\n+unsigned int strhash(const char *str)\n+{\n+\tunsigned int c, hash = FNV32_BASE;\n+\twhile ((c = (unsigned char) *str++))\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\treturn hash;\n+}\n+\n+unsigned int strihash(const char *str)\n+{\n+\tunsigned int c, hash = FNV32_BASE;\n+\twhile ((c = (unsigned char) *str++)) {\n+\t\tif (c >= 'a' && c <= 'z')\n+\t\t\tc -= 'a' - 'A';\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n+unsigned int memhash(const void *buf, size_t len)\n+{\n+\tunsigned int hash = FNV32_BASE;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n+\twhile (len--) {\n+\t\tunsigned int c = *ucbuf++;\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n+unsigned int memihash(const void *buf, size_t len)\n+{\n+\tunsigned int hash = FNV32_BASE;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n+\twhile (len--) {\n+\t\tunsigned int c = *ucbuf++;\n+\t\tif (c >= 'a' && c <= 'z')\n+\t\t\tc -= 'a' - 'A';\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n+#define HASHMAP_INITIAL_SIZE 64\n+/* grow / shrink by 2^2 */\n+#define HASHMAP_RESIZE_BITS 2\n+/* load factor in percent */\n+#define HASHMAP_LOAD_FACTOR 80\n+\n+static void alloc_table(struct hashmap *map, unsigned int size)\n+{\n+\tmap->tablesize = size;\n+\tmap->table = xcalloc(size, sizeof(struct hashmap_entry *));\n+\n+\t/* calculate resize thresholds for new size */\n+\tmap->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100);\n+\tif (size <= HASHMAP_INITIAL_SIZE)\n+\t\tmap->shrink_at = 0;\n+\telse\n+\t\t/*\n+\t\t * The shrink-threshold must be slightly smaller than\n+\t\t * (grow-threshold / resize-factor) to prevent erratic resizing,\n+\t\t * thus we divide by (resize-factor + 1).\n+\t\t */\n+\t\tmap->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1);\n+}\n+\n+static inline int entry_equals(const struct hashmap *map,\n+\t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2,\n+\t\tconst void *keydata)\n+{\n+\treturn (e1 == e2) || (e1->hash == e2->hash && !map->cmpfn(e1, e2, keydata));\n+}\n+\n+static inline unsigned int bucket(const struct hashmap *map,\n+\t\tconst struct hashmap_entry *key)\n+{\n+\treturn key->hash & (map->tablesize - 1);\n+}\n+\n+static void rehash(struct hashmap *map, unsigned int newsize)\n+{\n+\tunsigned int i, oldsize = map->tablesize;\n+\tstruct hashmap_entry **oldtable = map->table;\n+\n+\talloc_table(map, newsize);\n+\tfor (i = 0; i < oldsize; i++) {\n+\t\tstruct hashmap_entry *e = oldtable[i];\n+\t\twhile (e) {\n+\t\t\tstruct hashmap_entry *next = e->next;\n+\t\t\tunsigned int b = bucket(map, e);\n+\t\t\te->next = map->table[b];\n+\t\t\tmap->table[b] = e;\n+\t\t\te = next;\n+\t\t}\n+\t}\n+\tfree(oldtable);\n+}\n+\n+static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,\n+\t\tconst struct hashmap_entry *key, const void *keydata)\n+{\n+\tstruct hashmap_entry **e = &map->table[bucket(map, key)];\n+\twhile (*e && !entry_equals(map, *e, key, keydata))\n+\t\te = &(*e)->next;\n+\treturn e;\n+}\n+\n+static int always_equal(const void *unused1, const void *unused2, const void *unused3)\n+{\n+\treturn 0;\n+}\n+\n+void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n+\t\tsize_t initial_size)\n+{\n+\tunsigned int size = HASHMAP_INITIAL_SIZE;\n+\tmap->size = 0;\n+\tmap->cmpfn = equals_function ? equals_function : always_equal;\n+\n+\t/* calculate initial table size and allocate the table */\n+\tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n+\t\t\t/ HASHMAP_LOAD_FACTOR);\n+\twhile (initial_size > size)\n+\t\tsize <<= HASHMAP_RESIZE_BITS;\n+\talloc_table(map, size);\n+}\n+\n+void hashmap_free(struct hashmap *map, int free_entries)\n+{\n+\tif (!map || !map->table)\n+\t\treturn;\n+\tif (free_entries) {\n+\t\tstruct hashmap_iter iter;\n+\t\tstruct hashmap_entry *e;\n+\t\thashmap_iter_init(map, &iter);\n+\t\twhile ((e = hashmap_iter_next(&iter)))\n+\t\t\tfree(e);\n+\t}\n+\tfree(map->table);\n+\tmemset(map, 0, sizeof(*map));\n+}\n+\n+void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)\n+{\n+\treturn *find_entry_ptr(map, key, keydata);\n+}\n+\n+void *hashmap_get_next(const struct hashmap *map, const void *entry)\n+{\n+\tstruct hashmap_entry *e = ((struct hashmap_entry *) entry)->next;\n+\tfor (; e; e = e->next)\n+\t\tif (entry_equals(map, entry, e, NULL))\n+\t\t\treturn e;\n+\treturn NULL;\n+}\n+\n+void hashmap_add(struct hashmap *map, void *entry)\n+{\n+\tunsigned int b = bucket(map, entry);\n+\n+\t/* add entry */\n+\t((struct hashmap_entry *) entry)->next = map->table[b];\n+\tmap->table[b] = entry;\n+\n+\t/* fix size and rehash if appropriate */\n+\tmap->size++;\n+\tif (map->size > map->grow_at)\n+\t\trehash(map, map->tablesize << HASHMAP_RESIZE_BITS);\n+}\n+\n+void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)\n+{\n+\tstruct hashmap_entry *old;\n+\tstruct hashmap_entry **e = find_entry_ptr(map, key, keydata);\n+\tif (!*e)\n+\t\treturn NULL;\n+\n+\t/* remove existing entry */\n+\told = *e;\n+\t*e = old->next;\n+\told->next = NULL;\n+\n+\t/* fix size and rehash if appropriate */\n+\tmap->size--;\n+\tif (map->size < map->shrink_at)\n+\t\trehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);\n+\treturn old;\n+}\n+\n+void *hashmap_put(struct hashmap *map, void *entry)\n+{\n+\tstruct hashmap_entry *old = hashmap_remove(map, entry, NULL);\n+\thashmap_add(map, entry);\n+\treturn old;\n+}\n+\n+void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)\n+{\n+\titer->map = map;\n+\titer->tablepos = 0;\n+\titer->next = NULL;\n+}\n+\n+void *hashmap_iter_next(struct hashmap_iter *iter)\n+{\n+\tstruct hashmap_entry *current = iter->next;\n+\tfor (;;) {\n+\t\tif (current) {\n+\t\t\titer->next = current->next;\n+\t\t\treturn current;\n+\t\t}\n+\n+\t\tif (iter->tablepos >= iter->map->tablesize)\n+\t\t\treturn NULL;\n+\n+\t\tcurrent = iter->map->table[iter->tablepos++];\n+\t}\n+}\ndiff --git a/hashmap.h b/hashmap.h\nnew file mode 100644\nindex 0000000..f5b3b61\n--- /dev/null\n+++ b/hashmap.h\n@@ -0,0 +1,71 @@\n+#ifndef HASHMAP_H\n+#define HASHMAP_H\n+\n+/*\n+ * Generic implementation of hash-based key-value mappings.\n+ * See Documentation/technical/api-hashmap.txt.\n+ */\n+\n+/* FNV-1 functions */\n+\n+extern unsigned int strhash(const char *buf);\n+extern unsigned int strihash(const char *buf);\n+extern unsigned int memhash(const void *buf, size_t len);\n+extern unsigned int memihash(const void *buf, size_t len);\n+\n+/* data structures */\n+\n+struct hashmap_entry {\n+\tstruct hashmap_entry *next;\n+\tunsigned int hash;\n+};\n+\n+typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n+\t\tconst void *keydata);\n+\n+struct hashmap {\n+\tstruct hashmap_entry **table;\n+\thashmap_cmp_fn cmpfn;\n+\tunsigned int size, tablesize, grow_at, shrink_at;\n+};\n+\n+struct hashmap_iter {\n+\tstruct hashmap *map;\n+\tstruct hashmap_entry *next;\n+\tunsigned int tablepos;\n+};\n+\n+/* hashmap functions */\n+\n+extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n+\t\tsize_t initial_size);\n+extern void hashmap_free(struct hashmap *map, int free_entries);\n+\n+/* hashmap_entry functions */\n+\n+static inline void hashmap_entry_init(void *entry, int hash)\n+{\n+\tstruct hashmap_entry *e = entry;\n+\te->hash = hash;\n+\te->next = NULL;\n+}\n+extern void *hashmap_get(const struct hashmap *map, const void *key,\n+\t\tconst void *keydata);\n+extern void *hashmap_get_next(const struct hashmap *map, const void *entry);\n+extern void hashmap_add(struct hashmap *map, void *entry);\n+extern void *hashmap_put(struct hashmap *map, void *entry);\n+extern void *hashmap_remove(struct hashmap *map, const void *key,\n+\t\tconst void *keydata);\n+\n+/* hashmap_iter functions */\n+\n+extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n+extern void *hashmap_iter_next(struct hashmap_iter *iter);\n+static inline void *hashmap_iter_first(struct hashmap *map,\n+\t\tstruct hashmap_iter *iter)\n+{\n+\thashmap_iter_init(map, iter);\n+\treturn hashmap_iter_next(iter);\n+}\n+\n+#endif\ndiff --git a/t/t0011-hashmap.sh b/t/t0011-hashmap.sh\nnew file mode 100755\nindex 0000000..391e2b6\n--- /dev/null\n+++ b/t/t0011-hashmap.sh\n@@ -0,0 +1,240 @@\n+#!/bin/sh\n+\n+test_description='test hashmap and string hash functions'\n+. ./test-lib.sh\n+\n+test_hashmap() {\n+\techo \"$1\" | test-hashmap $3 > actual &&\n+\techo \"$2\" > expect &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'hash functions' '\n+\n+test_hashmap \"hash key1\" \"2215982743 2215982743 116372151 116372151\" &&\n+test_hashmap \"hash key2\" \"2215982740 2215982740 116372148 116372148\" &&\n+test_hashmap \"hash fooBarFrotz\" \"1383912807 1383912807 3189766727 3189766727\" &&\n+test_hashmap \"hash foobarfrotz\" \"2862305959 2862305959 3189766727 3189766727\"\n+\n+'\n+\n+test_expect_success 'put' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+put foobarfrotz value4\n+size\" \"NULL\n+NULL\n+NULL\n+NULL\n+64 4\"\n+\n+'\n+\n+test_expect_success 'put (case insensitive)' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+size\" \"NULL\n+NULL\n+NULL\n+64 3\" ignorecase\n+\n+'\n+\n+test_expect_success 'replace' '\n+\n+test_hashmap \"put key1 value1\n+put key1 value2\n+put fooBarFrotz value3\n+put fooBarFrotz value4\n+size\" \"NULL\n+value1\n+NULL\n+value3\n+64 2\"\n+\n+'\n+\n+test_expect_success 'replace (case insensitive)' '\n+\n+test_hashmap \"put key1 value1\n+put Key1 value2\n+put fooBarFrotz value3\n+put foobarfrotz value4\n+size\" \"NULL\n+value1\n+NULL\n+value3\n+64 2\" ignorecase\n+\n+'\n+\n+test_expect_success 'get' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+put foobarfrotz value4\n+get key1\n+get key2\n+get fooBarFrotz\n+get notInMap\" \"NULL\n+NULL\n+NULL\n+NULL\n+value1\n+value2\n+value3\n+NULL\"\n+\n+'\n+\n+test_expect_success 'get (case insensitive)' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+get Key1\n+get keY2\n+get foobarfrotz\n+get notInMap\" \"NULL\n+NULL\n+NULL\n+value1\n+value2\n+value3\n+NULL\" ignorecase\n+\n+'\n+\n+test_expect_success 'add' '\n+\n+test_hashmap \"add key1 value1\n+add key1 value2\n+add fooBarFrotz value3\n+add fooBarFrotz value4\n+get key1\n+get fooBarFrotz\n+get notInMap\" \"value2\n+value1\n+value4\n+value3\n+NULL\"\n+\n+'\n+\n+test_expect_success 'add (case insensitive)' '\n+\n+test_hashmap \"add key1 value1\n+add Key1 value2\n+add fooBarFrotz value3\n+add foobarfrotz value4\n+get key1\n+get Foobarfrotz\n+get notInMap\" \"value2\n+value1\n+value4\n+value3\n+NULL\" ignorecase\n+\n+'\n+\n+test_expect_success 'remove' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+remove key1\n+remove key2\n+remove notInMap\n+size\" \"NULL\n+NULL\n+NULL\n+value1\n+value2\n+NULL\n+64 1\"\n+\n+'\n+\n+test_expect_success 'remove (case insensitive)' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+remove Key1\n+remove keY2\n+remove notInMap\n+size\" \"NULL\n+NULL\n+NULL\n+value1\n+value2\n+NULL\n+64 1\" ignorecase\n+\n+'\n+\n+test_expect_success 'iterate' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+iterate\" \"NULL\n+NULL\n+NULL\n+key2 value2\n+key1 value1\n+fooBarFrotz value3\"\n+\n+'\n+\n+test_expect_success 'iterate (case insensitive)' '\n+\n+test_hashmap \"put key1 value1\n+put key2 value2\n+put fooBarFrotz value3\n+iterate\" \"NULL\n+NULL\n+NULL\n+fooBarFrotz value3\n+key2 value2\n+key1 value1\" ignorecase\n+\n+'\n+\n+test_expect_success 'grow / shrink' '\n+\n+\trm -f in &&\n+\trm -f expect &&\n+\tfor n in $(test_seq 51)\n+\tdo\n+\t\techo put key$n value$n >> in &&\n+\t\techo NULL >> expect\n+\tdone &&\n+\techo size >> in &&\n+\techo 64 51 >> expect &&\n+\techo put key52 value52 >> in &&\n+\techo NULL >> expect\n+\techo size >> in &&\n+\techo 256 52 >> expect &&\n+\tfor n in $(test_seq 12)\n+\tdo\n+\t\techo remove key$n >> in &&\n+\t\techo value$n >> expect\n+\tdone &&\n+\techo size >> in &&\n+\techo 256 40 >> expect &&\n+\techo remove key40 >> in &&\n+\techo value40 >> expect &&\n+\techo size >> in &&\n+\techo 64 39 >> expect &&\n+\tcat in | test-hashmap > out &&\n+\ttest_cmp expect out\n+\n+'\n+\n+test_done\ndiff --git a/test-hashmap.c b/test-hashmap.c\nnew file mode 100644\nindex 0000000..581d296\n--- /dev/null\n+++ b/test-hashmap.c\n@@ -0,0 +1,340 @@\n+#include \"cache.h\"\n+#include \"hashmap.h\"\n+#include \n+\n+struct test_entry\n+{\n+\tstruct hashmap_entry ent;\n+\t/* key and value as two \\0-terminated strings */\n+\tchar key[FLEX_ARRAY];\n+};\n+\n+static const char *get_value(const struct test_entry *e)\n+{\n+\treturn e->key + strlen(e->key) + 1;\n+}\n+\n+static int test_entry_cmp(const struct test_entry *e1,\n+\t\tconst struct test_entry *e2, const char* key)\n+{\n+\treturn strcmp(e1->key, key ? key : e2->key);\n+}\n+\n+static int test_entry_cmp_icase(const struct test_entry *e1,\n+\t\tconst struct test_entry *e2, const char* key)\n+{\n+\treturn strcasecmp(e1->key, key ? key : e2->key);\n+}\n+\n+static struct test_entry *alloc_test_entry(int hash, char *key, int klen,\n+\t\tchar *value, int vlen)\n+{\n+\tstruct test_entry *entry = malloc(sizeof(struct test_entry) + klen\n+\t\t\t+ vlen + 2);\n+\thashmap_entry_init(entry, hash);\n+\tmemcpy(entry->key, key, klen + 1);\n+\tmemcpy(entry->key + klen + 1, value, vlen + 1);\n+\treturn entry;\n+}\n+\n+#define HASH_METHOD_FNV 0\n+#define HASH_METHOD_I 1\n+#define HASH_METHOD_IDIV10 2\n+#define HASH_METHOD_0 3\n+#define HASH_METHOD_X2 4\n+#define TEST_SPARSE 8\n+#define TEST_ADD 16\n+#define TEST_SIZE 100000\n+\n+static unsigned int hash(unsigned int method, unsigned int i, const char *key)\n+{\n+\tunsigned int hash;\n+\tswitch (method & 3)\n+\t{\n+\tcase HASH_METHOD_FNV:\n+\t\thash = strhash(key);\n+\t\tbreak;\n+\tcase HASH_METHOD_I:\n+\t\thash = i;\n+\t\tbreak;\n+\tcase HASH_METHOD_IDIV10:\n+\t\thash = i / 10;\n+\t\tbreak;\n+\tcase HASH_METHOD_0:\n+\t\thash = 0;\n+\t\tbreak;\n+\t}\n+\n+\tif (method & HASH_METHOD_X2)\n+\t\thash = 2 * hash;\n+\treturn hash;\n+}\n+\n+/*\n+ * Test performance of hashmap.[ch]\n+ * Usage: time echo \"perfhashmap method rounds\" | test-hashmap\n+ */\n+static void perf_hashmap(unsigned int method, unsigned int rounds)\n+{\n+\tstruct hashmap map;\n+\tchar buf[16];\n+\tstruct test_entry **entries;\n+\tunsigned int *hashes;\n+\tunsigned int i, j;\n+\n+\tentries = malloc(TEST_SIZE * sizeof(struct test_entry *));\n+\thashes = malloc(TEST_SIZE * sizeof(int));\n+\tfor (i = 0; i < TEST_SIZE; i++) {\n+\t\tsnprintf(buf, sizeof(buf), \"%i\", i);\n+\t\tentries[i] = alloc_test_entry(0, buf, strlen(buf), \"\", 0);\n+\t\thashes[i] = hash(method, i, entries[i]->key);\n+\t}\n+\n+\tif (method & TEST_ADD) {\n+\t\t/* test adding to the map */\n+\t\tfor (j = 0; j < rounds; j++) {\n+\t\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, 0);\n+\n+\t\t\t/* add entries */\n+\t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n+\t\t\t\thashmap_entry_init(entries[i], hashes[i]);\n+\t\t\t\thashmap_add(&map, entries[i]);\n+\t\t\t}\n+\n+\t\t\thashmap_free(&map, 0);\n+\t\t}\n+\t} else {\n+\t\t/* test map lookups */\n+\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, 0);\n+\n+\t\t/* fill the map (sparsely if specified) */\n+\t\tj = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;\n+\t\tfor (i = 0; i < j; i++) {\n+\t\t\thashmap_entry_init(entries[i], hashes[i]);\n+\t\t\thashmap_add(&map, entries[i]);\n+\t\t}\n+\n+\t\tfor (j = 0; j < rounds; j++) {\n+\t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n+\t\t\t\tstruct hashmap_entry key;\n+\t\t\t\thashmap_entry_init(&key, hashes[i]);\n+\t\t\t\thashmap_get(&map, &key, entries[i]->key);\n+\t\t\t}\n+\t\t}\n+\n+\t\thashmap_free(&map, 0);\n+\t}\n+}\n+\n+struct hash_entry\n+{\n+\tstruct hash_entry *next;\n+\tchar key[FLEX_ARRAY];\n+};\n+\n+/*\n+ * Test performance of hash.[ch]\n+ * Usage: time echo \"perfhash method rounds\" | test-hashmap\n+ */\n+static void perf_hash(unsigned int method, unsigned int rounds)\n+{\n+\tstruct hash_table map;\n+\tchar buf[16];\n+\tstruct hash_entry **entries, **res, *entry;\n+\tunsigned int *hashes;\n+\tunsigned int i, j;\n+\n+\tentries = malloc(TEST_SIZE * sizeof(struct hash_entry *));\n+\thashes = malloc(TEST_SIZE * sizeof(int));\n+\tfor (i = 0; i < TEST_SIZE; i++) {\n+\t\tsnprintf(buf, sizeof(buf), \"%i\", i);\n+\t\tentries[i] = malloc(sizeof(struct hash_entry) + strlen(buf) + 1);\n+\t\tstrcpy(entries[i]->key, buf);\n+\t\thashes[i] = hash(method, i, entries[i]->key);\n+\t}\n+\n+\tif (method & TEST_ADD) {\n+\t\t/* test adding to the map */\n+\t\tfor (j = 0; j < rounds; j++) {\n+\t\t\tinit_hash(&map);\n+\n+\t\t\t/* add entries */\n+\t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n+\t\t\t\tres = (struct hash_entry **) insert_hash(\n+\t\t\t\t\t\thashes[i], entries[i], &map);\n+\t\t\t\tif (res) {\n+\t\t\t\t\tentries[i]->next = *res;\n+\t\t\t\t\t*res = entries[i];\n+\t\t\t\t} else {\n+\t\t\t\t\tentries[i]->next = NULL;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tfree_hash(&map);\n+\t\t}\n+\t} else {\n+\t\t/* test map lookups */\n+\t\tinit_hash(&map);\n+\n+\t\t/* fill the map (sparsely if specified) */\n+\t\tj = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;\n+\t\tfor (i = 0; i < j; i++) {\n+\t\t\tres = (struct hash_entry **) insert_hash(hashes[i],\n+\t\t\t\t\tentries[i], &map);\n+\t\t\tif (res) {\n+\t\t\t\tentries[i]->next = *res;\n+\t\t\t\t*res = entries[i];\n+\t\t\t} else {\n+\t\t\t\tentries[i]->next = NULL;\n+\t\t\t}\n+\t\t}\n+\n+\t\tfor (j = 0; j < rounds; j++) {\n+\t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n+\t\t\t\tentry = lookup_hash(hashes[i], &map);\n+\t\t\t\twhile (entry) {\n+\t\t\t\t\tif (!strcmp(entries[i]->key, entry->key))\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tentry = entry->next;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tfree_hash(&map);\n+\n+\t}\n+}\n+\n+#define DELIM \" \\t\\r\\n\"\n+\n+/*\n+ * Read stdin line by line and print result of commands to stdout:\n+ *\n+ * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)\n+ * put key value -> NULL / old value\n+ * get key -> NULL / value\n+ * remove key -> NULL / old value\n+ * iterate -> key1 value1\\nkey2 value2\\n...\n+ * size -> tablesize numentries\n+ *\n+ * perfhashmap method rounds -> test hashmap.[ch] performance\n+ * perfhash method rounds -> test hash.[ch] performance\n+ */\n+int main(int argc, char *argv[])\n+{\n+\tchar line[1024];\n+\tstruct hashmap map;\n+\tint icase;\n+\n+\t/* init hash map */\n+\ticase = argc > 1 && !strcmp(\"ignorecase\", argv[1]);\n+\thashmap_init(&map, (hashmap_cmp_fn) (icase ? test_entry_cmp_icase\n+\t\t\t: test_entry_cmp), 0);\n+\n+\t/* process commands from stdin */\n+\twhile (fgets(line, sizeof(line), stdin)) {\n+\t\tchar *cmd, *p1 = NULL, *p2 = NULL;\n+\t\tint l1 = 0, l2 = 0, hash = 0;\n+\t\tstruct test_entry *entry;\n+\n+\t\t/* break line into command and up to two parameters */\n+\t\tcmd = strtok(line, DELIM);\n+\t\t/* ignore empty lines */\n+\t\tif (!cmd || *cmd == '#')\n+\t\t\tcontinue;\n+\n+\t\tp1 = strtok(NULL, DELIM);\n+\t\tif (p1) {\n+\t\t\tl1 = strlen(p1);\n+\t\t\thash = icase ? strihash(p1) : strhash(p1);\n+\t\t\tp2 = strtok(NULL, DELIM);\n+\t\t\tif (p2)\n+\t\t\t\tl2 = strlen(p2);\n+\t\t}\n+\n+\t\tif (!strcmp(\"hash\", cmd) && l1) {\n+\n+\t\t\t/* print results of different hash functions */\n+\t\t\tprintf(\"%u %u %u %u\\n\", strhash(p1), memhash(p1, l1),\n+\t\t\t\t\tstrihash(p1), memihash(p1, l1));\n+\n+\t\t} else if (!strcmp(\"add\", cmd) && l1 && l2) {\n+\n+\t\t\t/* create entry with key = p1, value = p2 */\n+\t\t\tentry = alloc_test_entry(hash, p1, l1, p2, l2);\n+\n+\t\t\t/* add to hashmap */\n+\t\t\thashmap_add(&map, entry);\n+\n+\t\t} else if (!strcmp(\"put\", cmd) && l1 && l2) {\n+\n+\t\t\t/* create entry with key = p1, value = p2 */\n+\t\t\tentry = alloc_test_entry(hash, p1, l1, p2, l2);\n+\n+\t\t\t/* add / replace entry */\n+\t\t\tentry = hashmap_put(&map, entry);\n+\n+\t\t\t/* print and free replaced entry, if any */\n+\t\t\tputs(entry ? get_value(entry) : \"NULL\");\n+\t\t\tfree(entry);\n+\n+\t\t} else if (!strcmp(\"get\", cmd) && l1) {\n+\n+\t\t\t/* setup static key */\n+\t\t\tstruct hashmap_entry key;\n+\t\t\thashmap_entry_init(&key, hash);\n+\n+\t\t\t/* lookup entry in hashmap */\n+\t\t\tentry = hashmap_get(&map, &key, p1);\n+\n+\t\t\t/* print result */\n+\t\t\tif (!entry)\n+\t\t\t\tputs(\"NULL\");\n+\t\t\twhile (entry) {\n+\t\t\t\tputs(get_value(entry));\n+\t\t\t\tentry = hashmap_get_next(&map, entry);\n+\t\t\t}\n+\n+\t\t} else if (!strcmp(\"remove\", cmd) && l1) {\n+\n+\t\t\t/* setup static key */\n+\t\t\tstruct hashmap_entry key;\n+\t\t\thashmap_entry_init(&key, hash);\n+\n+\t\t\t/* remove entry from hashmap */\n+\t\t\tentry = hashmap_remove(&map, &key, p1);\n+\n+\t\t\t/* print result and free entry*/\n+\t\t\tputs(entry ? get_value(entry) : \"NULL\");\n+\t\t\tfree(entry);\n+\n+\t\t} else if (!strcmp(\"iterate\", cmd)) {\n+\n+\t\t\tstruct hashmap_iter iter;\n+\t\t\thashmap_iter_init(&map, &iter);\n+\t\t\twhile ((entry = hashmap_iter_next(&iter)))\n+\t\t\t\tprintf(\"%s %s\\n\", entry->key, get_value(entry));\n+\n+\t\t} else if (!strcmp(\"size\", cmd)) {\n+\n+\t\t\t/* print table sizes */\n+\t\t\tprintf(\"%u %u\\n\", map.tablesize, map.size);\n+\n+\t\t} else if (!strcmp(\"perfhashmap\", cmd) && l1 && l2) {\n+\n+\t\t\tperf_hashmap(atoi(p1), atoi(p2));\n+\n+\t\t} else if (!strcmp(\"perfhash\", cmd) && l1 && l2) {\n+\n+\t\t\tperf_hash(atoi(p1), atoi(p2));\n+\n+\t\t} else {\n+\n+\t\t\tprintf(\"Unknown command %s\\n\", cmd);\n+\n+\t\t}\n+\t}\n+\n+\thashmap_free(&map, 1);\n+\treturn 0;\n+}\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230637","messageId":"5285220B.4020403@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 03/14] buitin/describe.c: use new hash map implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:18:35Z","receivedAt":"2013-11-14T19:18:35Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n builtin/describe.c | 53 ++++++++++++++++++++++++-----------------------------\n 1 file changed, 24 insertions(+), 29 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 6f62109..0b2cef4 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -6,7 +6,7 @@\n #include \"exec_cmd.h\"\n #include \"parse-options.h\"\n #include \"diff.h\"\n-#include \"hash.h\"\n+#include \"hashmap.h\"\n #include \"argv-array.h\"\n \n #define SEEN\t\t(1u << 0)\n@@ -25,7 +25,7 @@ static int longformat;\n static int first_parent;\n static int abbrev = -1; /* unspecified */\n static int max_candidates = 10;\n-static struct hash_table names;\n+static struct hashmap names;\n static int have_util;\n static const char *pattern;\n static int always;\n@@ -37,7 +37,7 @@ static const char *diff_index_args[] = {\n };\n \n struct commit_name {\n-\tstruct commit_name *next;\n+\tstruct hashmap_entry entry;\n \tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n@@ -50,6 +50,12 @@ static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n };\n \n+static int commit_name_cmp(const struct commit_name *cn1,\n+\t\tconst struct commit_name *cn2, const void *peeled)\n+{\n+\treturn hashcmp(cn1->peeled, peeled ? peeled : cn2->peeled);\n+}\n+\n static inline unsigned int hash_sha1(const unsigned char *sha1)\n {\n \tunsigned int hash;\n@@ -59,21 +65,9 @@ static inline unsigned int hash_sha1(const unsigned char *sha1)\n \n static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n {\n-\tstruct commit_name *n = lookup_hash(hash_sha1(peeled), &names);\n-\twhile (n && !!hashcmp(peeled, n->peeled))\n-\t\tn = n->next;\n-\treturn n;\n-}\n-\n-static int set_util(void *chain, void *data)\n-{\n-\tstruct commit_name *n;\n-\tfor (n = chain; n; n = n->next) {\n-\t\tstruct commit *c = lookup_commit_reference_gently(n->peeled, 1);\n-\t\tif (c)\n-\t\t\tc->util = n;\n-\t}\n-\treturn 0;\n+\tstruct commit_name key;\n+\thashmap_entry_init(&key, hash_sha1(peeled));\n+\treturn hashmap_get(&names, &key, peeled);\n }\n \n static int replace_name(struct commit_name *e,\n@@ -118,16 +112,10 @@ static void add_to_known_names(const char *path,\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n \t\tif (!e) {\n-\t\t\tvoid **pos;\n \t\t\te = xmalloc(sizeof(struct commit_name));\n \t\t\thashcpy(e->peeled, peeled);\n-\t\t\tpos = insert_hash(hash_sha1(peeled), e, &names);\n-\t\t\tif (pos) {\n-\t\t\t\te->next = *pos;\n-\t\t\t\t*pos = e;\n-\t\t\t} else {\n-\t\t\t\te->next = NULL;\n-\t\t\t}\n+\t\t\thashmap_entry_init(e, hash_sha1(peeled));\n+\t\t\thashmap_add(&names, e);\n \t\t\te->path = NULL;\n \t\t}\n \t\te->tag = tag;\n@@ -292,7 +280,14 @@ static void describe(const char *arg, int last_one)\n \t\tfprintf(stderr, _(\"searching to describe %s\\n\"), arg);\n \n \tif (!have_util) {\n-\t\tfor_each_hash(&names, set_util, NULL);\n+\t\tstruct hashmap_iter iter;\n+\t\tstruct commit *c;\n+\t\tstruct commit_name *n = hashmap_iter_first(&names, &iter);\n+\t\tfor (; n; n = hashmap_iter_next(&iter)) {\n+\t\t\tc = lookup_commit_reference_gently(n->peeled, 1);\n+\t\t\tif (c)\n+\t\t\t\tc->util = n;\n+\t\t}\n \t\thave_util = 1;\n \t}\n \n@@ -463,9 +458,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(args.argc, args.argv, prefix);\n \t}\n \n-\tinit_hash(&names);\n+\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);\n \tfor_each_rawref(get_name, NULL);\n-\tif (!names.nr && !always)\n+\tif (!names.size && !always)\n \t\tdie(_(\"No names found, cannot describe anything.\"));\n \n \tif (argc == 0) {\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230638","messageId":"52852228.9060206@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 04/14] diffcore-rename.c: move code around to prepare for the next patch","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:19:04Z","receivedAt":"2013-11-14T19:19:04Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"No actual code changes, just move hash_filespec up and outdent part of\nfind_identical_files.\n\nSigned-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n diffcore-rename.c | 98 +++++++++++++++++++++++++++----------------------------\n 1 file changed, 49 insertions(+), 49 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6c7a72f..008a60c 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -248,6 +248,18 @@ struct file_similarity {\n \tstruct file_similarity *next;\n };\n \n+static unsigned int hash_filespec(struct diff_filespec *filespec)\n+{\n+\tunsigned int hash;\n+\tif (!filespec->sha1_valid) {\n+\t\tif (diff_populate_filespec(filespec, 0))\n+\t\t\treturn 0;\n+\t\thash_sha1_file(filespec->data, filespec->size, \"blob\", filespec->sha1);\n+\t}\n+\tmemcpy(&hash, filespec->sha1, sizeof(hash));\n+\treturn hash;\n+}\n+\n static int find_identical_files(struct file_similarity *src,\n \t\t\t\tstruct file_similarity *dst,\n \t\t\t\tstruct diff_options *options)\n@@ -258,46 +270,46 @@ static int find_identical_files(struct file_similarity *src,\n \t * Walk over all the destinations ...\n \t */\n \tdo {\n-\t\tstruct diff_filespec *target = dst->filespec;\n-\t\tstruct file_similarity *p, *best;\n-\t\tint i = 100, best_score = -1;\n-\n-\t\t/*\n-\t\t * .. to find the best source match\n-\t\t */\n-\t\tbest = NULL;\n-\t\tfor (p = src; p; p = p->next) {\n-\t\t\tint score;\n-\t\t\tstruct diff_filespec *source = p->filespec;\n-\n-\t\t\t/* False hash collision? */\n-\t\t\tif (hashcmp(source->sha1, target->sha1))\n-\t\t\t\tcontinue;\n-\t\t\t/* Non-regular files? If so, the modes must match! */\n-\t\t\tif (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {\n-\t\t\t\tif (source->mode != target->mode)\n-\t\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t\t/* Give higher scores to sources that haven't been used already */\n-\t\t\tscore = !source->rename_used;\n-\t\t\tif (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)\n-\t\t\t\tcontinue;\n-\t\t\tscore += basename_same(source, target);\n-\t\t\tif (score > best_score) {\n-\t\t\t\tbest = p;\n-\t\t\t\tbest_score = score;\n-\t\t\t\tif (score == 2)\n-\t\t\t\t\tbreak;\n-\t\t\t}\n+\tstruct diff_filespec *target = dst->filespec;\n+\tstruct file_similarity *p, *best;\n+\tint i = 100, best_score = -1;\n \n-\t\t\t/* Too many identical alternatives? Pick one */\n-\t\t\tif (!--i)\n-\t\t\t\tbreak;\n+\t/*\n+\t * .. to find the best source match\n+\t */\n+\tbest = NULL;\n+\tfor (p = src; p; p = p->next) {\n+\t\tint score;\n+\t\tstruct diff_filespec *source = p->filespec;\n+\n+\t\t/* False hash collision? */\n+\t\tif (hashcmp(source->sha1, target->sha1))\n+\t\t\tcontinue;\n+\t\t/* Non-regular files? If so, the modes must match! */\n+\t\tif (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {\n+\t\t\tif (source->mode != target->mode)\n+\t\t\t\tcontinue;\n \t\t}\n-\t\tif (best) {\n-\t\t\trecord_rename_pair(dst->index, best->index, MAX_SCORE);\n-\t\t\trenames++;\n+\t\t/* Give higher scores to sources that haven't been used already */\n+\t\tscore = !source->rename_used;\n+\t\tif (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)\n+\t\t\tcontinue;\n+\t\tscore += basename_same(source, target);\n+\t\tif (score > best_score) {\n+\t\t\tbest = p;\n+\t\t\tbest_score = score;\n+\t\t\tif (score == 2)\n+\t\t\t\tbreak;\n \t\t}\n+\n+\t\t/* Too many identical alternatives? Pick one */\n+\t\tif (!--i)\n+\t\t\tbreak;\n+\t}\n+\tif (best) {\n+\t\trecord_rename_pair(dst->index, best->index, MAX_SCORE);\n+\t\trenames++;\n+\t}\n \t} while ((dst = dst->next) != NULL);\n \treturn renames;\n }\n@@ -343,18 +355,6 @@ static int find_same_files(void *ptr, void *data)\n \treturn ret;\n }\n \n-static unsigned int hash_filespec(struct diff_filespec *filespec)\n-{\n-\tunsigned int hash;\n-\tif (!filespec->sha1_valid) {\n-\t\tif (diff_populate_filespec(filespec, 0))\n-\t\t\treturn 0;\n-\t\thash_sha1_file(filespec->data, filespec->size, \"blob\", filespec->sha1);\n-\t}\n-\tmemcpy(&hash, filespec->sha1, sizeof(hash));\n-\treturn hash;\n-}\n-\n static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)\n {\n \tvoid **pos;\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230639","messageId":"52852246.8070800@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 05/14] diffcore-rename.c: simplify finding exact renames","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:19:34Z","receivedAt":"2013-11-14T19:19:34Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"The find_exact_renames function currently only uses the hash table for\ngrouping, i.e.:\n\n1. add sources\n2. add destinations\n3. iterate all buckets, per bucket:\n4. split sources from destinations\n5. iterate destinations, per destination:\n6. iterate sources to find best match\n\nThis can be simplified by utilizing the lookup functionality of the hash\ntable, i.e.:\n\n1. add sources\n2. iterate destinations, per destination:\n3. lookup sources matching the current destination\n4. iterate sources to find best match\n\nThis saves several iterations and file_similarity allocations for the\ndestinations.\n\nSigned-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n diffcore-rename.c | 75 +++++++++++++++----------------------------------------\n 1 file changed, 20 insertions(+), 55 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 008a60c..cfeb408 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -243,7 +243,7 @@ static int score_compare(const void *a_, const void *b_)\n }\n \n struct file_similarity {\n-\tint src_dst, index;\n+\tint index;\n \tstruct diff_filespec *filespec;\n \tstruct file_similarity *next;\n };\n@@ -260,25 +260,21 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)\n \treturn hash;\n }\n \n-static int find_identical_files(struct file_similarity *src,\n-\t\t\t\tstruct file_similarity *dst,\n+static int find_identical_files(struct hash_table *srcs,\n+\t\t\t\tint dst_index,\n \t\t\t\tstruct diff_options *options)\n {\n \tint renames = 0;\n \n-\t/*\n-\t * Walk over all the destinations ...\n-\t */\n-\tdo {\n-\tstruct diff_filespec *target = dst->filespec;\n+\tstruct diff_filespec *target = rename_dst[dst_index].two;\n \tstruct file_similarity *p, *best;\n \tint i = 100, best_score = -1;\n \n \t/*\n-\t * .. to find the best source match\n+\t * Find the best source match for specified destination.\n \t */\n \tbest = NULL;\n-\tfor (p = src; p; p = p->next) {\n+\tfor (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) {\n \t\tint score;\n \t\tstruct diff_filespec *source = p->filespec;\n \n@@ -307,61 +303,28 @@ static int find_identical_files(struct file_similarity *src,\n \t\t\tbreak;\n \t}\n \tif (best) {\n-\t\trecord_rename_pair(dst->index, best->index, MAX_SCORE);\n+\t\trecord_rename_pair(dst_index, best->index, MAX_SCORE);\n \t\trenames++;\n \t}\n-\t} while ((dst = dst->next) != NULL);\n \treturn renames;\n }\n \n-static void free_similarity_list(struct file_similarity *p)\n+static int free_similarity_list(void *p, void *unused)\n {\n \twhile (p) {\n \t\tstruct file_similarity *entry = p;\n-\t\tp = p->next;\n+\t\tp = entry->next;\n \t\tfree(entry);\n \t}\n+\treturn 0;\n }\n \n-static int find_same_files(void *ptr, void *data)\n-{\n-\tint ret;\n-\tstruct file_similarity *p = ptr;\n-\tstruct file_similarity *src = NULL, *dst = NULL;\n-\tstruct diff_options *options = data;\n-\n-\t/* Split the hash list up into sources and destinations */\n-\tdo {\n-\t\tstruct file_similarity *entry = p;\n-\t\tp = p->next;\n-\t\tif (entry->src_dst < 0) {\n-\t\t\tentry->next = src;\n-\t\t\tsrc = entry;\n-\t\t} else {\n-\t\t\tentry->next = dst;\n-\t\t\tdst = entry;\n-\t\t}\n-\t} while (p);\n-\n-\t/*\n-\t * If we have both sources *and* destinations, see if\n-\t * we can match them up\n-\t */\n-\tret = (src && dst) ? find_identical_files(src, dst, options) : 0;\n-\n-\t/* Free the hashes and return the number of renames found */\n-\tfree_similarity_list(src);\n-\tfree_similarity_list(dst);\n-\treturn ret;\n-}\n-\n-static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)\n+static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec)\n {\n \tvoid **pos;\n \tunsigned int hash;\n \tstruct file_similarity *entry = xmalloc(sizeof(*entry));\n \n-\tentry->src_dst = src_dst;\n \tentry->index = index;\n \tentry->filespec = filespec;\n \tentry->next = NULL;\n@@ -385,24 +348,26 @@ static void insert_file_table(struct hash_table *table, int src_dst, int index,\n */\n static int find_exact_renames(struct diff_options *options)\n {\n-\tint i;\n+\tint i, renames = 0;\n \tstruct hash_table file_table;\n \n+\t/* Add all sources to the hash table */\n \tinit_hash(&file_table);\n-\tpreallocate_hash(&file_table, rename_src_nr + rename_dst_nr);\n+\tpreallocate_hash(&file_table, rename_src_nr);\n \tfor (i = 0; i < rename_src_nr; i++)\n-\t\tinsert_file_table(&file_table, -1, i, rename_src[i].p->one);\n+\t\tinsert_file_table(&file_table, i, rename_src[i].p->one);\n \n+\t/* Walk the destinations and find best source match */\n \tfor (i = 0; i < rename_dst_nr; i++)\n-\t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n+\t\trenames += find_identical_files(&file_table, i, options);\n \n-\t/* Find the renames */\n-\ti = for_each_hash(&file_table, find_same_files, options);\n+\t/* Free source file_similarity chains */\n+\tfor_each_hash(&file_table, free_similarity_list, options);\n \n \t/* .. and free the hash data structure */\n \tfree_hash(&file_table);\n \n-\treturn i;\n+\treturn renames;\n }\n \n #define NUM_CANDIDATE_PER_DST 4\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230641","messageId":"5285227A.6020001@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 06/14] diffcore-rename.c: use new hash map implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:20:26Z","receivedAt":"2013-11-14T19:20:26Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n diffcore-rename.c | 48 +++++++++++++-----------------------------------\n 1 file changed, 13 insertions(+), 35 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex cfeb408..9b4f068 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -4,7 +4,7 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n-#include \"hash.h\"\n+#include \"hashmap.h\"\n #include \"progress.h\"\n \n /* Table of rename/copy destinations */\n@@ -243,9 +243,9 @@ static int score_compare(const void *a_, const void *b_)\n }\n \n struct file_similarity {\n+\tstruct hashmap_entry entry;\n \tint index;\n \tstruct diff_filespec *filespec;\n-\tstruct file_similarity *next;\n };\n \n static unsigned int hash_filespec(struct diff_filespec *filespec)\n@@ -260,21 +260,22 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)\n \treturn hash;\n }\n \n-static int find_identical_files(struct hash_table *srcs,\n+static int find_identical_files(struct hashmap *srcs,\n \t\t\t\tint dst_index,\n \t\t\t\tstruct diff_options *options)\n {\n \tint renames = 0;\n \n \tstruct diff_filespec *target = rename_dst[dst_index].two;\n-\tstruct file_similarity *p, *best;\n+\tstruct file_similarity *p, *best, dst;\n \tint i = 100, best_score = -1;\n \n \t/*\n \t * Find the best source match for specified destination.\n \t */\n \tbest = NULL;\n-\tfor (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) {\n+\thashmap_entry_init(&dst, hash_filespec(target));\n+\tfor (p = hashmap_get(srcs, &dst, NULL); p; p = hashmap_get_next(srcs, p)) {\n \t\tint score;\n \t\tstruct diff_filespec *source = p->filespec;\n \n@@ -309,34 +310,15 @@ static int find_identical_files(struct hash_table *srcs,\n \treturn renames;\n }\n \n-static int free_similarity_list(void *p, void *unused)\n+static void insert_file_table(struct hashmap *table, int index, struct diff_filespec *filespec)\n {\n-\twhile (p) {\n-\t\tstruct file_similarity *entry = p;\n-\t\tp = entry->next;\n-\t\tfree(entry);\n-\t}\n-\treturn 0;\n-}\n-\n-static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec)\n-{\n-\tvoid **pos;\n-\tunsigned int hash;\n \tstruct file_similarity *entry = xmalloc(sizeof(*entry));\n \n \tentry->index = index;\n \tentry->filespec = filespec;\n-\tentry->next = NULL;\n-\n-\thash = hash_filespec(filespec);\n-\tpos = insert_hash(hash, entry, table);\n \n-\t/* We already had an entry there? */\n-\tif (pos) {\n-\t\tentry->next = *pos;\n-\t\t*pos = entry;\n-\t}\n+\thashmap_entry_init(entry, hash_filespec(filespec));\n+\thashmap_add(table, entry);\n }\n \n /*\n@@ -349,11 +331,10 @@ static void insert_file_table(struct hash_table *table, int index, struct diff_f\n static int find_exact_renames(struct diff_options *options)\n {\n \tint i, renames = 0;\n-\tstruct hash_table file_table;\n+\tstruct hashmap file_table;\n \n \t/* Add all sources to the hash table */\n-\tinit_hash(&file_table);\n-\tpreallocate_hash(&file_table, rename_src_nr);\n+\thashmap_init(&file_table, NULL, rename_src_nr);\n \tfor (i = 0; i < rename_src_nr; i++)\n \t\tinsert_file_table(&file_table, i, rename_src[i].p->one);\n \n@@ -361,11 +342,8 @@ static int find_exact_renames(struct diff_options *options)\n \tfor (i = 0; i < rename_dst_nr; i++)\n \t\trenames += find_identical_files(&file_table, i, options);\n \n-\t/* Free source file_similarity chains */\n-\tfor_each_hash(&file_table, free_similarity_list, options);\n-\n-\t/* .. and free the hash data structure */\n-\tfree_hash(&file_table);\n+\t/* Free the hash data structure and entries */\n+\thashmap_free(&file_table, 1);\n \n \treturn renames;\n }\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230642","messageId":"5285229A.7060902@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 07/14] name-hash.c: use new hash map implementation for directories","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:20:58Z","receivedAt":"2013-11-14T19:20:58Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n cache.h | 3 ++-\n name-hash.c | 77 +++++++++++++++----------------------------------------------\n 2 files changed, 20 insertions(+), 60 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d1f3c71..84e9ad6 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -4,6 +4,7 @@\n #include \"git-compat-util.h\"\n #include \"strbuf.h\"\n #include \"hash.h\"\n+#include \"hashmap.h\"\n #include \"advice.h\"\n #include \"gettext.h\"\n #include \"convert.h\"\n@@ -278,7 +279,7 @@ struct index_state {\n \tunsigned name_hash_initialized : 1,\n \t\t initialized : 1;\n \tstruct hash_table name_hash;\n-\tstruct hash_table dir_hash;\n+\tstruct hashmap dir_hash;\n };\n \n extern struct index_state the_index;\ndiff --git a/name-hash.c b/name-hash.c\nindex e5b6e1a..c75fadf 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -8,49 +8,28 @@\n #define NO_THE_INDEX_COMPATIBILITY_MACROS\n #include \"cache.h\"\n \n-/*\n- * This removes bit 5 if bit 6 is set.\n- *\n- * That will make US-ASCII characters hash to their upper-case\n- * equivalent. We could easily do this one whole word at a time,\n- * but that's for future worries.\n- */\n-static inline unsigned char icase_hash(unsigned char c)\n-{\n-\treturn c & ~((c & 0x40) >> 1);\n-}\n-\n-static unsigned int hash_name(const char *name, int namelen)\n-{\n-\tunsigned int hash = 0x123;\n-\n-\twhile (namelen--) {\n-\t\tunsigned char c = *name++;\n-\t\tc = icase_hash(c);\n-\t\thash = hash*101 + c;\n-\t}\n-\treturn hash;\n-}\n-\n struct dir_entry {\n-\tstruct dir_entry *next;\n+\tstruct hashmap_entry ent;\n \tstruct dir_entry *parent;\n \tstruct cache_entry *ce;\n \tint nr;\n \tunsigned int namelen;\n };\n \n+static int dir_entry_cmp(const struct dir_entry *e1,\n+\t\tconst struct dir_entry *e2, const char *name)\n+{\n+\treturn e1->namelen != e2->namelen || strncasecmp(e1->ce->name,\n+\t\t\tname ? name : e2->ce->name, e1->namelen);\n+}\n+\n static struct dir_entry *find_dir_entry(struct index_state *istate,\n \t\tconst char *name, unsigned int namelen)\n {\n-\tunsigned int hash = hash_name(name, namelen);\n-\tstruct dir_entry *dir;\n-\n-\tfor (dir = lookup_hash(hash, &istate->dir_hash); dir; dir = dir->next)\n-\t\tif (dir->namelen == namelen &&\n-\t\t !strncasecmp(dir->ce->name, name, namelen))\n-\t\t\treturn dir;\n-\treturn NULL;\n+\tstruct dir_entry key;\n+\thashmap_entry_init(&key, memihash(name, namelen));\n+\tkey.namelen = namelen;\n+\treturn hashmap_get(&istate->dir_hash, &key, name);\n }\n \n static struct dir_entry *hash_dir_entry(struct index_state *istate,\n@@ -84,18 +63,11 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \tdir = find_dir_entry(istate, ce->name, namelen);\n \tif (!dir) {\n \t\t/* not found, create it and add to hash table */\n-\t\tvoid **pdir;\n-\t\tunsigned int hash = hash_name(ce->name, namelen);\n-\n \t\tdir = xcalloc(1, sizeof(struct dir_entry));\n+\t\thashmap_entry_init(dir, memihash(ce->name, namelen));\n \t\tdir->namelen = namelen;\n \t\tdir->ce = ce;\n-\n-\t\tpdir = insert_hash(hash, dir, &istate->dir_hash);\n-\t\tif (pdir) {\n-\t\t\tdir->next = *pdir;\n-\t\t\t*pdir = dir;\n-\t\t}\n+\t\thashmap_add(&istate->dir_hash, dir);\n \n \t\t/* recursively add missing parent directories */\n \t\tdir->parent = hash_dir_entry(istate, ce, namelen);\n@@ -134,7 +106,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \t\treturn;\n \tce->ce_flags |= CE_HASHED;\n \tce->next = NULL;\n-\thash = hash_name(ce->name, ce_namelen(ce));\n+\thash = memihash(ce->name, ce_namelen(ce));\n \tpos = insert_hash(hash, ce, &istate->name_hash);\n \tif (pos) {\n \t\tce->next = *pos;\n@@ -153,6 +125,7 @@ static void lazy_init_name_hash(struct index_state *istate)\n \t\treturn;\n \tif (istate->cache_nr)\n \t\tpreallocate_hash(&istate->name_hash, istate->cache_nr);\n+\thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n \tistate->name_hash_initialized = 1;\n@@ -247,7 +220,7 @@ struct cache_entry *index_dir_exists(struct index_state *istate, const char *nam\n \n struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)\n {\n-\tunsigned int hash = hash_name(name, namelen);\n+\tunsigned int hash = memihash(name, namelen);\n \tstruct cache_entry *ce;\n \n \tlazy_init_name_hash(istate);\n@@ -270,26 +243,12 @@ struct cache_entry *index_name_exists(struct index_state *istate, const char *na\n \treturn index_file_exists(istate, name, namelen, icase);\n }\n \n-static int free_dir_entry(void *entry, void *unused)\n-{\n-\tstruct dir_entry *dir = entry;\n-\twhile (dir) {\n-\t\tstruct dir_entry *next = dir->next;\n-\t\tfree(dir);\n-\t\tdir = next;\n-\t}\n-\treturn 0;\n-}\n-\n void free_name_hash(struct index_state *istate)\n {\n \tif (!istate->name_hash_initialized)\n \t\treturn;\n \tistate->name_hash_initialized = 0;\n-\tif (ignore_case)\n-\t\t/* free directory entries */\n-\t\tfor_each_hash(&istate->dir_hash, free_dir_entry, NULL);\n \n \tfree_hash(&istate->name_hash);\n-\tfree_hash(&istate->dir_hash);\n+\thashmap_free(&istate->dir_hash, 1);\n }\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230643","messageId":"528522B6.2050302@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 08/14] name-hash.c: remove unreferenced directory entries","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:21:26Z","receivedAt":"2013-11-14T19:21:26Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"The new hashmap implementation supports remove, so remove and free\ndirectory entries that are no longer referenced by active cache entries.\n\nSigned-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n name-hash.c | 15 ++++++++-------\n 1 file changed, 8 insertions(+), 7 deletions(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex c75fadf..effe96d 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -86,15 +86,16 @@ static void add_dir_entry(struct index_state *istate, struct cache_entry *ce)\n static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)\n {\n \t/*\n-\t * Release reference to the directory entry (and parents if 0).\n-\t *\n-\t * Note: we do not remove / free the entry because there's no\n-\t * hash.[ch]::remove_hash and dir->next may point to other entries\n-\t * that are still valid, so we must not free the memory.\n+\t * Release reference to the directory entry. If 0, remove and continue\n+\t * with parent directory.\n \t */\n \tstruct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));\n-\twhile (dir && dir->nr && !(--dir->nr))\n-\t\tdir = dir->parent;\n+\twhile (dir && !(--dir->nr)) {\n+\t\tstruct dir_entry *parent = dir->parent;\n+\t\thashmap_remove(&istate->dir_hash, dir, NULL);\n+\t\tfree(dir);\n+\t\tdir = parent;\n+\t}\n }\n \n static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230644","messageId":"528522D6.9000309@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 09/14] name-hash.c: use new hash map implementation for cache entries","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:21:58Z","receivedAt":"2013-11-14T19:21:58Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Note: the \"ce->next = NULL;\" in unpack-trees.c::do_add_entry can safely be\nremoved, as ce->next (now ce->ent.next) is always properly initialized in\nname-hash.c::hash_index_entry.\n\nSigned-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n cache.h | 8 +++++---\n name-hash.c | 24 ++++++++----------------\n unpack-trees.c | 1 -\n 3 files changed, 13 insertions(+), 20 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 84e9ad6..cedc7ae 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -131,12 +131,12 @@ struct stat_data {\n };\n \n struct cache_entry {\n+\tstruct hashmap_entry ent;\n \tstruct stat_data ce_stat_data;\n \tunsigned int ce_mode;\n \tunsigned int ce_flags;\n \tunsigned int ce_namelen;\n \tunsigned char sha1[20];\n-\tstruct cache_entry *next;\n \tchar name[FLEX_ARRAY]; /* more */\n };\n \n@@ -203,7 +203,9 @@ static inline void copy_cache_entry(struct cache_entry *dst,\n \tunsigned int state = dst->ce_flags & CE_STATE_MASK;\n \n \t/* Don't copy hash chain and name */\n-\tmemcpy(dst, src, offsetof(struct cache_entry, next));\n+\tmemcpy(&dst->ce_stat_data, &src->ce_stat_data,\n+\t\t\toffsetof(struct cache_entry, name) -\n+\t\t\toffsetof(struct cache_entry, ce_stat_data));\n \n \t/* Restore the hash state */\n \tdst->ce_flags = (dst->ce_flags & ~CE_STATE_MASK) | state;\n@@ -278,7 +280,7 @@ struct index_state {\n \tstruct cache_time timestamp;\n \tunsigned name_hash_initialized : 1,\n \t\t initialized : 1;\n-\tstruct hash_table name_hash;\n+\tstruct hashmap name_hash;\n \tstruct hashmap dir_hash;\n };\n \ndiff --git a/name-hash.c b/name-hash.c\nindex effe96d..488eccf 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -100,19 +100,11 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)\n \n static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n {\n-\tvoid **pos;\n-\tunsigned int hash;\n-\n \tif (ce->ce_flags & CE_HASHED)\n \t\treturn;\n \tce->ce_flags |= CE_HASHED;\n-\tce->next = NULL;\n-\thash = memihash(ce->name, ce_namelen(ce));\n-\tpos = insert_hash(hash, ce, &istate->name_hash);\n-\tif (pos) {\n-\t\tce->next = *pos;\n-\t\t*pos = ce;\n-\t}\n+\thashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));\n+\thashmap_add(&istate->name_hash, ce);\n \n \tif (ignore_case && !(ce->ce_flags & CE_UNHASHED))\n \t\tadd_dir_entry(istate, ce);\n@@ -124,8 +116,7 @@ static void lazy_init_name_hash(struct index_state *istate)\n \n \tif (istate->name_hash_initialized)\n \t\treturn;\n-\tif (istate->cache_nr)\n-\t\tpreallocate_hash(&istate->name_hash, istate->cache_nr);\n+\thashmap_init(&istate->name_hash, NULL, istate->cache_nr);\n \thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n@@ -221,18 +212,19 @@ struct cache_entry *index_dir_exists(struct index_state *istate, const char *nam\n \n struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)\n {\n-\tunsigned int hash = memihash(name, namelen);\n \tstruct cache_entry *ce;\n+\tstruct hashmap_entry key;\n \n \tlazy_init_name_hash(istate);\n-\tce = lookup_hash(hash, &istate->name_hash);\n \n+\thashmap_entry_init(&key, memihash(name, namelen));\n+\tce = hashmap_get(&istate->name_hash, &key, NULL);\n \twhile (ce) {\n \t\tif (!(ce->ce_flags & CE_UNHASHED)) {\n \t\t\tif (same_name(ce, name, namelen, icase))\n \t\t\t\treturn ce;\n \t\t}\n-\t\tce = ce->next;\n+\t\tce = hashmap_get_next(&istate->name_hash, ce);\n \t}\n \treturn NULL;\n }\n@@ -250,6 +242,6 @@ void free_name_hash(struct index_state *istate)\n \t\treturn;\n \tistate->name_hash_initialized = 0;\n \n-\tfree_hash(&istate->name_hash);\n+\thashmap_free(&istate->name_hash, 0);\n \thashmap_free(&istate->dir_hash, 1);\n }\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex ad3e9a0..f8985d4 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -110,7 +110,6 @@ static void do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,\n \tif (set & CE_REMOVE)\n \t\tset |= CE_WT_REMOVE;\n \n-\tce->next = NULL;\n \tce->ce_flags = (ce->ce_flags & ~clear) | set;\n \tadd_index_entry(&o->result, ce,\n \t\t\tADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230645","messageId":"528522F3.4040209@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 10/14] name-hash.c: remove cache entries instead of marking them CE_UNHASHED","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:22:27Z","receivedAt":"2013-11-14T19:22:27Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"The new hashmap implementation supports remove, so really remove unused\ncache entries from the name hashmap instead of just marking them.\n\nThe CE_UNHASHED flag and CE_STATE_MASK are no longer needed.\n\nKeep the CE_HASHED flag to prevent adding entries twice.\n\nSigned-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n cache.h | 6 ++----\n name-hash.c | 46 ++++++++++++++++++++++------------------------\n read-cache.c | 2 +-\n unpack-trees.c | 2 +-\n 4 files changed, 26 insertions(+), 30 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex cedc7ae..05b8011 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -160,7 +160,6 @@ struct cache_entry {\n #define CE_ADDED (1 << 19)\n \n #define CE_HASHED (1 << 20)\n-#define CE_UNHASHED (1 << 21)\n #define CE_WT_REMOVE (1 << 22) /* remove in work directory */\n #define CE_CONFLICTED (1 << 23)\n \n@@ -196,11 +195,10 @@ struct pathspec;\n * Copy the sha1 and stat state of a cache entry from one to\n * another. But we never change the name, or the hash state!\n */\n-#define CE_STATE_MASK (CE_HASHED | CE_UNHASHED)\n static inline void copy_cache_entry(struct cache_entry *dst,\n \t\t\t\t const struct cache_entry *src)\n {\n-\tunsigned int state = dst->ce_flags & CE_STATE_MASK;\n+\tunsigned int state = dst->ce_flags & CE_HASHED;\n \n \t/* Don't copy hash chain and name */\n \tmemcpy(&dst->ce_stat_data, &src->ce_stat_data,\n@@ -208,7 +206,7 @@ static inline void copy_cache_entry(struct cache_entry *dst,\n \t\t\toffsetof(struct cache_entry, ce_stat_data));\n \n \t/* Restore the hash state */\n-\tdst->ce_flags = (dst->ce_flags & ~CE_STATE_MASK) | state;\n+\tdst->ce_flags = (dst->ce_flags & ~CE_HASHED) | state;\n }\n \n static inline unsigned create_ce_flags(unsigned stage)\ndiff --git a/name-hash.c b/name-hash.c\nindex 488eccf..9a3bd3f 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -106,17 +106,29 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \thashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));\n \thashmap_add(&istate->name_hash, ce);\n \n-\tif (ignore_case && !(ce->ce_flags & CE_UNHASHED))\n+\tif (ignore_case)\n \t\tadd_dir_entry(istate, ce);\n }\n \n+static int cache_entry_cmp(const struct cache_entry *ce1,\n+\t\tconst struct cache_entry *ce2, const void *remove)\n+{\n+\t/*\n+\t * For remove_name_hash, find the exact entry (pointer equality); for\n+\t * index_name_exists, find all entries with matching hash code and\n+\t * decide whether the entry matches in same_name.\n+\t */\n+\treturn remove ? !(ce1 == ce2) : 0;\n+}\n+\n static void lazy_init_name_hash(struct index_state *istate)\n {\n \tint nr;\n \n \tif (istate->name_hash_initialized)\n \t\treturn;\n-\thashmap_init(&istate->name_hash, NULL, istate->cache_nr);\n+\thashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,\n+\t\t\tistate->cache_nr);\n \thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n@@ -125,31 +137,19 @@ static void lazy_init_name_hash(struct index_state *istate)\n \n void add_name_hash(struct index_state *istate, struct cache_entry *ce)\n {\n-\t/* if already hashed, add reference to directory entries */\n-\tif (ignore_case && (ce->ce_flags & CE_STATE_MASK) == CE_STATE_MASK)\n-\t\tadd_dir_entry(istate, ce);\n-\n-\tce->ce_flags &= ~CE_UNHASHED;\n \tif (istate->name_hash_initialized)\n \t\thash_index_entry(istate, ce);\n }\n \n-/*\n- * We don't actually *remove* it, we can just mark it invalid so that\n- * we won't find it in lookups.\n- *\n- * Not only would we have to search the lists (simple enough), but\n- * we'd also have to rehash other hash buckets in case this makes the\n- * hash bucket empty (common). So it's much better to just mark\n- * it.\n- */\n void remove_name_hash(struct index_state *istate, struct cache_entry *ce)\n {\n-\t/* if already hashed, release reference to directory entries */\n-\tif (ignore_case && (ce->ce_flags & CE_STATE_MASK) == CE_HASHED)\n-\t\tremove_dir_entry(istate, ce);\n+\tif (!istate->name_hash_initialized || !(ce->ce_flags & CE_HASHED))\n+\t\treturn;\n+\tce->ce_flags &= ~CE_HASHED;\n+\thashmap_remove(&istate->name_hash, ce, ce);\n \n-\tce->ce_flags |= CE_UNHASHED;\n+\tif (ignore_case)\n+\t\tremove_dir_entry(istate, ce);\n }\n \n static int slow_same_name(const char *name1, int len1, const char *name2, int len2)\n@@ -220,10 +220,8 @@ struct cache_entry *index_file_exists(struct index_state *istate, const char *na\n \thashmap_entry_init(&key, memihash(name, namelen));\n \tce = hashmap_get(&istate->name_hash, &key, NULL);\n \twhile (ce) {\n-\t\tif (!(ce->ce_flags & CE_UNHASHED)) {\n-\t\t\tif (same_name(ce, name, namelen, icase))\n-\t\t\t\treturn ce;\n-\t\t}\n+\t\tif (same_name(ce, name, namelen, icase))\n+\t\t\treturn ce;\n \t\tce = hashmap_get_next(&istate->name_hash, ce);\n \t}\n \treturn NULL;\ndiff --git a/read-cache.c b/read-cache.c\nindex 33dd676..00af9ad 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -58,7 +58,7 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n\n \n \tnew = xmalloc(cache_entry_size(namelen));\n \tcopy_cache_entry(new, old);\n-\tnew->ce_flags &= ~CE_STATE_MASK;\n+\tnew->ce_flags &= ~CE_HASHED;\n \tnew->ce_namelen = namelen;\n \tmemcpy(new->name, new_name, namelen + 1);\n \ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex f8985d4..82b652f 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -105,7 +105,7 @@ void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,\n static void do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,\n \t\t\t unsigned int set, unsigned int clear)\n {\n-\tclear |= CE_HASHED | CE_UNHASHED;\n+\tclear |= CE_HASHED;\n \n \tif (set & CE_REMOVE)\n \t\tset |= CE_WT_REMOVE;\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230646","messageId":"52852320.9010401@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 11/14] remove old hash.[ch] implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:23:12Z","receivedAt":"2013-11-14T19:23:12Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \nSigned-off-by: Junio C Hamano \n---\n Documentation/technical/api-hash.txt | 52 -----------------\n Makefile | 2 -\n cache.h | 1 -\n hash.c | 110 -----------------------------------\n hash.h | 50 ----------------\n test-hashmap.c | 84 --------------------------\n 6 files changed, 299 deletions(-)\n delete mode 100644 Documentation/technical/api-hash.txt\n delete mode 100644 hash.c\n delete mode 100644 hash.h\n\ndiff --git a/Documentation/technical/api-hash.txt b/Documentation/technical/api-hash.txt\ndeleted file mode 100644\nindex e5061e0..0000000\n--- a/Documentation/technical/api-hash.txt\n+++ /dev/null\n@@ -1,52 +0,0 @@\n-hash API\n-========\n-\n-The hash API is a collection of simple hash table functions. Users are expected\n-to implement their own hashing.\n-\n-Data Structures\n----------------\n-\n-`struct hash_table`::\n-\n-\tThe hash table structure. The `array` member points to the hash table\n-\tentries. The `size` member counts the total number of valid and invalid\n-\tentries in the table. The `nr` member keeps track of the number of\n-\tvalid entries.\n-\n-`struct hash_table_entry`::\n-\n-\tAn opaque structure representing an entry in the hash table. The `hash`\n-\tmember is the entry's hash key and the `ptr` member is the entry's\n-\tvalue.\n-\n-Functions\n----------\n-\n-`init_hash`::\n-\n-\tInitialize the hash table.\n-\n-`free_hash`::\n-\n-\tRelease memory associated with the hash table.\n-\n-`insert_hash`::\n-\n-\tInsert a pointer into the hash table. If an entry with that hash\n-\talready exists, a pointer to the existing entry's value is returned.\n-\tOtherwise NULL is returned. This allows callers to implement\n-\tchaining, etc.\n-\n-`lookup_hash`::\n-\n-\tLookup an entry in the hash table. If an entry with that hash exists\n-\tthe entry's value is returned. Otherwise NULL is returned.\n-\n-`for_each_hash`::\n-\n-\tCall a function for each entry in the hash table. The function is\n-\texpected to take the entry's value as its only argument and return an\n-\tint. If the function returns a negative int the loop is aborted\n-\timmediately. Otherwise, the return value is accumulated and the sum\n-\treturned upon completion of the loop.\ndiff --git a/Makefile b/Makefile\nindex 75bb1a6..d566768 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -673,7 +673,6 @@ LIB_H += git-compat-util.h\n LIB_H += gpg-interface.h\n LIB_H += graph.h\n LIB_H += grep.h\n-LIB_H += hash.h\n LIB_H += hashmap.h\n LIB_H += help.h\n LIB_H += http.h\n@@ -805,7 +804,6 @@ LIB_OBJS += gettext.o\n LIB_OBJS += gpg-interface.o\n LIB_OBJS += graph.o\n LIB_OBJS += grep.o\n-LIB_OBJS += hash.o\n LIB_OBJS += hashmap.o\n LIB_OBJS += help.o\n LIB_OBJS += hex.o\ndiff --git a/cache.h b/cache.h\nindex 05b8011..27067b8 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -3,7 +3,6 @@\n \n #include \"git-compat-util.h\"\n #include \"strbuf.h\"\n-#include \"hash.h\"\n #include \"hashmap.h\"\n #include \"advice.h\"\n #include \"gettext.h\"\ndiff --git a/hash.c b/hash.c\ndeleted file mode 100644\nindex 749ecfe..0000000\n--- a/hash.c\n+++ /dev/null\n@@ -1,110 +0,0 @@\n-/*\n- * Some generic hashing helpers.\n- */\n-#include \"cache.h\"\n-#include \"hash.h\"\n-\n-/*\n- * Look up a hash entry in the hash table. Return the pointer to\n- * the existing entry, or the empty slot if none existed. The caller\n- * can then look at the (*ptr) to see whether it existed or not.\n- */\n-static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table)\n-{\n-\tunsigned int size = table->size, nr = hash % size;\n-\tstruct hash_table_entry *array = table->array;\n-\n-\twhile (array[nr].ptr) {\n-\t\tif (array[nr].hash == hash)\n-\t\t\tbreak;\n-\t\tnr++;\n-\t\tif (nr >= size)\n-\t\t\tnr = 0;\n-\t}\n-\treturn array + nr;\n-}\n-\n-\n-/*\n- * Insert a new hash entry pointer into the table.\n- *\n- * If that hash entry already existed, return the pointer to\n- * the existing entry (and the caller can create a list of the\n- * pointers or do anything else). If it didn't exist, return\n- * NULL (and the caller knows the pointer has been inserted).\n- */\n-static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table)\n-{\n-\tstruct hash_table_entry *entry = lookup_hash_entry(hash, table);\n-\n-\tif (!entry->ptr) {\n-\t\tentry->ptr = ptr;\n-\t\tentry->hash = hash;\n-\t\ttable->nr++;\n-\t\treturn NULL;\n-\t}\n-\treturn &entry->ptr;\n-}\n-\n-static void grow_hash_table(struct hash_table *table)\n-{\n-\tunsigned int i;\n-\tunsigned int old_size = table->size, new_size;\n-\tstruct hash_table_entry *old_array = table->array, *new_array;\n-\n-\tnew_size = alloc_nr(old_size);\n-\tnew_array = xcalloc(sizeof(struct hash_table_entry), new_size);\n-\ttable->size = new_size;\n-\ttable->array = new_array;\n-\ttable->nr = 0;\n-\tfor (i = 0; i < old_size; i++) {\n-\t\tunsigned int hash = old_array[i].hash;\n-\t\tvoid *ptr = old_array[i].ptr;\n-\t\tif (ptr)\n-\t\t\tinsert_hash_entry(hash, ptr, table);\n-\t}\n-\tfree(old_array);\n-}\n-\n-void *lookup_hash(unsigned int hash, const struct hash_table *table)\n-{\n-\tif (!table->array)\n-\t\treturn NULL;\n-\treturn lookup_hash_entry(hash, table)->ptr;\n-}\n-\n-void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)\n-{\n-\tunsigned int nr = table->nr;\n-\tif (nr >= table->size/2)\n-\t\tgrow_hash_table(table);\n-\treturn insert_hash_entry(hash, ptr, table);\n-}\n-\n-int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data)\n-{\n-\tint sum = 0;\n-\tunsigned int i;\n-\tunsigned int size = table->size;\n-\tstruct hash_table_entry *array = table->array;\n-\n-\tfor (i = 0; i < size; i++) {\n-\t\tvoid *ptr = array->ptr;\n-\t\tarray++;\n-\t\tif (ptr) {\n-\t\t\tint val = fn(ptr, data);\n-\t\t\tif (val < 0)\n-\t\t\t\treturn val;\n-\t\t\tsum += val;\n-\t\t}\n-\t}\n-\treturn sum;\n-}\n-\n-void free_hash(struct hash_table *table)\n-{\n-\tfree(table->array);\n-\ttable->array = NULL;\n-\ttable->size = 0;\n-\ttable->nr = 0;\n-}\ndiff --git a/hash.h b/hash.h\ndeleted file mode 100644\nindex 1d43ac0..0000000\n--- a/hash.h\n+++ /dev/null\n@@ -1,50 +0,0 @@\n-#ifndef HASH_H\n-#define HASH_H\n-\n-/*\n- * These are some simple generic hash table helper functions.\n- * Not necessarily suitable for all users, but good for things\n- * where you want to just keep track of a list of things, and\n- * have a good hash to use on them.\n- *\n- * It keeps the hash table at roughly 50-75% free, so the memory\n- * cost of the hash table itself is roughly\n- *\n- *\t3 * 2*sizeof(void *) * nr_of_objects\n- *\n- * bytes.\n- *\n- * FIXME: on 64-bit architectures, we waste memory. It would be\n- * good to have just 32-bit pointers, requiring a special allocator\n- * for hashed entries or something.\n- */\n-struct hash_table_entry {\n-\tunsigned int hash;\n-\tvoid *ptr;\n-};\n-\n-struct hash_table {\n-\tunsigned int size, nr;\n-\tstruct hash_table_entry *array;\n-};\n-\n-extern void *lookup_hash(unsigned int hash, const struct hash_table *table);\n-extern void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table);\n-extern int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data);\n-extern void free_hash(struct hash_table *table);\n-\n-static inline void init_hash(struct hash_table *table)\n-{\n-\ttable->size = 0;\n-\ttable->nr = 0;\n-\ttable->array = NULL;\n-}\n-\n-static inline void preallocate_hash(struct hash_table *table, unsigned int elts)\n-{\n-\tassert(table->size == 0 && table->nr == 0 && table->array == NULL);\n-\ttable->size = elts * 2;\n-\ttable->array = xcalloc(sizeof(struct hash_table_entry), table->size);\n-}\n-\n-#endif\ndiff --git a/test-hashmap.c b/test-hashmap.c\nindex 581d296..7e86f88 100644\n--- a/test-hashmap.c\n+++ b/test-hashmap.c\n@@ -126,85 +126,6 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\n \t}\n }\n \n-struct hash_entry\n-{\n-\tstruct hash_entry *next;\n-\tchar key[FLEX_ARRAY];\n-};\n-\n-/*\n- * Test performance of hash.[ch]\n- * Usage: time echo \"perfhash method rounds\" | test-hashmap\n- */\n-static void perf_hash(unsigned int method, unsigned int rounds)\n-{\n-\tstruct hash_table map;\n-\tchar buf[16];\n-\tstruct hash_entry **entries, **res, *entry;\n-\tunsigned int *hashes;\n-\tunsigned int i, j;\n-\n-\tentries = malloc(TEST_SIZE * sizeof(struct hash_entry *));\n-\thashes = malloc(TEST_SIZE * sizeof(int));\n-\tfor (i = 0; i < TEST_SIZE; i++) {\n-\t\tsnprintf(buf, sizeof(buf), \"%i\", i);\n-\t\tentries[i] = malloc(sizeof(struct hash_entry) + strlen(buf) + 1);\n-\t\tstrcpy(entries[i]->key, buf);\n-\t\thashes[i] = hash(method, i, entries[i]->key);\n-\t}\n-\n-\tif (method & TEST_ADD) {\n-\t\t/* test adding to the map */\n-\t\tfor (j = 0; j < rounds; j++) {\n-\t\t\tinit_hash(&map);\n-\n-\t\t\t/* add entries */\n-\t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n-\t\t\t\tres = (struct hash_entry **) insert_hash(\n-\t\t\t\t\t\thashes[i], entries[i], &map);\n-\t\t\t\tif (res) {\n-\t\t\t\t\tentries[i]->next = *res;\n-\t\t\t\t\t*res = entries[i];\n-\t\t\t\t} else {\n-\t\t\t\t\tentries[i]->next = NULL;\n-\t\t\t\t}\n-\t\t\t}\n-\n-\t\t\tfree_hash(&map);\n-\t\t}\n-\t} else {\n-\t\t/* test map lookups */\n-\t\tinit_hash(&map);\n-\n-\t\t/* fill the map (sparsely if specified) */\n-\t\tj = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;\n-\t\tfor (i = 0; i < j; i++) {\n-\t\t\tres = (struct hash_entry **) insert_hash(hashes[i],\n-\t\t\t\t\tentries[i], &map);\n-\t\t\tif (res) {\n-\t\t\t\tentries[i]->next = *res;\n-\t\t\t\t*res = entries[i];\n-\t\t\t} else {\n-\t\t\t\tentries[i]->next = NULL;\n-\t\t\t}\n-\t\t}\n-\n-\t\tfor (j = 0; j < rounds; j++) {\n-\t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n-\t\t\t\tentry = lookup_hash(hashes[i], &map);\n-\t\t\t\twhile (entry) {\n-\t\t\t\t\tif (!strcmp(entries[i]->key, entry->key))\n-\t\t\t\t\t\tbreak;\n-\t\t\t\t\tentry = entry->next;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t}\n-\n-\t\tfree_hash(&map);\n-\n-\t}\n-}\n-\n #define DELIM \" \\t\\r\\n\"\n \n /*\n@@ -218,7 +139,6 @@ static void perf_hash(unsigned int method, unsigned int rounds)\n * size -> tablesize numentries\n *\n * perfhashmap method rounds -> test hashmap.[ch] performance\n- * perfhash method rounds -> test hash.[ch] performance\n */\n int main(int argc, char *argv[])\n {\n@@ -324,10 +244,6 @@ int main(int argc, char *argv[])\n \n \t\t\tperf_hashmap(atoi(p1), atoi(p2));\n \n-\t\t} else if (!strcmp(\"perfhash\", cmd) && l1 && l2) {\n-\n-\t\t\tperf_hash(atoi(p1), atoi(p2));\n-\n \t\t} else {\n \n \t\t\tprintf(\"Unknown command %s\\n\", cmd);\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230647","messageId":"5285233E.4010205@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 12/14] fix 'git update-index --verbose --again' output","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:23:42Z","receivedAt":"2013-11-14T19:23:42Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"'git update-index --verbose' consistently reports paths relative to the\nwork-tree root. The only exception is the '--again' option, which reports\npaths relative to the current working directory.\n\nChange do_reupdate to use non-prefixed paths.\n\nSigned-off-by: Karsten Blees \n---\n builtin/update-index.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex e3a10d7..d180d80 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -579,7 +579,7 @@ static int do_reupdate(int ac, const char **av,\n \t\t * or worse yet 'allow_replace', active_nr may decrease.\n \t\t */\n \t\tsave_nr = active_nr;\n-\t\tupdate_one(ce->name + prefix_length, prefix, prefix_length);\n+\t\tupdate_one(ce->name, NULL, 0);\n \t\tif (save_nr != active_nr)\n \t\t\tgoto redo;\n \t}\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230648","messageId":"52852358.9020808@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 13/14] builtin/update-index.c: cleanup update_one","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:24:08Z","receivedAt":"2013-11-14T19:24:08Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"do_reupdate calls update_one with a cache_entry.name, there's no need for\nthe extra sanitation / normalization that happens in prefix_path.\ncmd_update_index calls update_one with an already prefixed path, no need to\nprefix_path twice.\n\nRemove the extra prefix_path from update_one. Also remove the now unused\n'prefix' and 'prefix_length' parameters.\n\nAs of d089eba \"setup: sanitize absolute and funny paths in get_pathspec()\",\nprefix_path uncoditionally returns a copy, even if the passed in path isn't\nchanged. Lets unconditionally free() the result.\n\nSigned-off-by: Karsten Blees \n---\n builtin/update-index.c | 36 +++++++++++++++---------------------\n 1 file changed, 15 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex d180d80..c8f0d5f 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -274,36 +274,32 @@ static void chmod_path(int flip, const char *path)\n \tdie(\"git update-index: cannot chmod %cx '%s'\", flip, path);\n }\n \n-static void update_one(const char *path, const char *prefix, int prefix_length)\n+static void update_one(const char *path)\n {\n-\tconst char *p = prefix_path(prefix, prefix_length, path);\n-\tif (!verify_path(p)) {\n+\tif (!verify_path(path)) {\n \t\tfprintf(stderr, \"Ignoring path %s\\n\", path);\n-\t\tgoto free_return;\n+\t\treturn;\n \t}\n \tif (mark_valid_only) {\n-\t\tif (mark_ce_flags(p, CE_VALID, mark_valid_only == MARK_FLAG))\n+\t\tif (mark_ce_flags(path, CE_VALID, mark_valid_only == MARK_FLAG))\n \t\t\tdie(\"Unable to mark file %s\", path);\n-\t\tgoto free_return;\n+\t\treturn;\n \t}\n \tif (mark_skip_worktree_only) {\n-\t\tif (mark_ce_flags(p, CE_SKIP_WORKTREE, mark_skip_worktree_only == MARK_FLAG))\n+\t\tif (mark_ce_flags(path, CE_SKIP_WORKTREE, mark_skip_worktree_only == MARK_FLAG))\n \t\t\tdie(\"Unable to mark file %s\", path);\n-\t\tgoto free_return;\n+\t\treturn;\n \t}\n \n \tif (force_remove) {\n-\t\tif (remove_file_from_cache(p))\n+\t\tif (remove_file_from_cache(path))\n \t\t\tdie(\"git update-index: unable to remove %s\", path);\n \t\treport(\"remove '%s'\", path);\n-\t\tgoto free_return;\n+\t\treturn;\n \t}\n-\tif (process_path(p))\n+\tif (process_path(path))\n \t\tdie(\"Unable to process path %s\", path);\n \treport(\"add '%s'\", path);\n- free_return:\n-\tif (p < path || p > path + strlen(path))\n-\t\tfree((char *)p);\n }\n \n static void read_index_info(int line_termination)\n@@ -579,7 +575,7 @@ static int do_reupdate(int ac, const char **av,\n \t\t * or worse yet 'allow_replace', active_nr may decrease.\n \t\t */\n \t\tsave_nr = active_nr;\n-\t\tupdate_one(ce->name, NULL, 0);\n+\t\tupdate_one(ce->name);\n \t\tif (save_nr != active_nr)\n \t\t\tgoto redo;\n \t}\n@@ -836,11 +832,10 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \n \t\t\tsetup_work_tree();\n \t\t\tp = prefix_path(prefix, prefix_length, path);\n-\t\t\tupdate_one(p, NULL, 0);\n+\t\t\tupdate_one(p);\n \t\t\tif (set_executable_bit)\n \t\t\t\tchmod_path(set_executable_bit, p);\n-\t\t\tif (p < path || p > path + strlen(path))\n-\t\t\t\tfree((char *)p);\n+\t\t\tfree((char *)p);\n \t\t\tctx.argc--;\n \t\t\tctx.argv++;\n \t\t\tbreak;\n@@ -879,11 +874,10 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t\t\tstrbuf_swap(&buf, &nbuf);\n \t\t\t}\n \t\t\tp = prefix_path(prefix, prefix_length, buf.buf);\n-\t\t\tupdate_one(p, NULL, 0);\n+\t\t\tupdate_one(p);\n \t\t\tif (set_executable_bit)\n \t\t\t\tchmod_path(set_executable_bit, p);\n-\t\t\tif (p < buf.buf || p > buf.buf + buf.len)\n-\t\t\t\tfree((char *)p);\n+\t\t\tfree((char *)p);\n \t\t}\n \t\tstrbuf_release(&nbuf);\n \t\tstrbuf_release(&buf);\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230649","messageId":"52852375.8040008@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"[PATCH v5 14/14] read-cache.c: fix memory leaks caused by removed cache entries","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:24:37Z","receivedAt":"2013-11-14T19:24:37Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"When cache_entry structs are removed from index_state.cache, they are not\nproperly freed. Freeing those entries wasn't possible before because we\ncouldn't remove them from index_state.name_hash.\n\nNow that we _do_ remove the entries from name_hash, we can also free them.\nAdd 'free(cache_entry)' to all call sites of name-hash.c::remove_name_hash\nin read-cache.c (we could free() directly in remove_name_hash(), but\nname-hash.c isn't concerned with cache_entry allocation at all).\n\nAccessing a cache_entry after removing it from the index is now no longer\nallowed, as the memory has been freed. The following functions need minor\nfixes (typically by copying ce->name before use):\n - builtin/rm.c::cmd_rm\n - builtin/update-index.c::do_reupdate\n - read-cache.c::read_index_unmerged\n - resolve-undo.c::unmerge_index_entry_at\n\nSigned-off-by: Karsten Blees \n---\n builtin/rm.c | 2 +-\n builtin/update-index.c | 5 ++++-\n read-cache.c | 8 ++++++--\n resolve-undo.c | 7 +++++--\n 4 files changed, 16 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/rm.c b/builtin/rm.c\nindex 3a0e0ea..171f37c 100644\n--- a/builtin/rm.c\n+++ b/builtin/rm.c\n@@ -311,7 +311,7 @@ int cmd_rm(int argc, const char **argv, const char *prefix)\n \t\tif (!match_pathspec_depth(&pathspec, ce->name, ce_namelen(ce), 0, seen))\n \t\t\tcontinue;\n \t\tALLOC_GROW(list.entry, list.nr + 1, list.alloc);\n-\t\tlist.entry[list.nr].name = ce->name;\n+\t\tlist.entry[list.nr].name = xstrdup(ce->name);\n \t\tlist.entry[list.nr].is_submodule = S_ISGITLINK(ce->ce_mode);\n \t\tif (list.entry[list.nr++].is_submodule &&\n \t\t !is_staging_gitmodules_ok())\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex c8f0d5f..00313f3 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -559,6 +559,7 @@ static int do_reupdate(int ac, const char **av,\n \t\tconst struct cache_entry *ce = active_cache[pos];\n \t\tstruct cache_entry *old = NULL;\n \t\tint save_nr;\n+\t\tchar *path;\n \n \t\tif (ce_stage(ce) || !ce_path_match(ce, &pathspec))\n \t\t\tcontinue;\n@@ -575,7 +576,9 @@ static int do_reupdate(int ac, const char **av,\n \t\t * or worse yet 'allow_replace', active_nr may decrease.\n \t\t */\n \t\tsave_nr = active_nr;\n-\t\tupdate_one(ce->name);\n+\t\tpath = xstrdup(ce->name);\n+\t\tupdate_one(path);\n+\t\tfree(path);\n \t\tif (save_nr != active_nr)\n \t\t\tgoto redo;\n \t}\ndiff --git a/read-cache.c b/read-cache.c\nindex 00af9ad..3f735f3 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -47,6 +47,7 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache\n \tstruct cache_entry *old = istate->cache[nr];\n \n \tremove_name_hash(istate, old);\n+\tfree(old);\n \tset_index_entry(istate, nr, ce);\n \tistate->cache_changed = 1;\n }\n@@ -478,6 +479,7 @@ int remove_index_entry_at(struct index_state *istate, int pos)\n \n \trecord_resolve_undo(istate, ce);\n \tremove_name_hash(istate, ce);\n+\tfree(ce);\n \tistate->cache_changed = 1;\n \tistate->cache_nr--;\n \tif (pos >= istate->cache_nr)\n@@ -499,8 +501,10 @@ void remove_marked_cache_entries(struct index_state *istate)\n \tunsigned int i, j;\n \n \tfor (i = j = 0; i < istate->cache_nr; i++) {\n-\t\tif (ce_array[i]->ce_flags & CE_REMOVE)\n+\t\tif (ce_array[i]->ce_flags & CE_REMOVE) {\n \t\t\tremove_name_hash(istate, ce_array[i]);\n+\t\t\tfree(ce_array[i]);\n+\t\t}\n \t\telse\n \t\t\tce_array[j++] = ce_array[i];\n \t}\n@@ -1894,7 +1898,7 @@ int read_index_unmerged(struct index_state *istate)\n \t\tnew_ce->ce_mode = ce->ce_mode;\n \t\tif (add_index_entry(istate, new_ce, 0))\n \t\t\treturn error(\"%s: cannot drop to stage #0\",\n-\t\t\t\t ce->name);\n+\t\t\t\t new_ce->name);\n \t\ti = index_name_pos(istate, new_ce->name, len);\n \t}\n \treturn unmerged;\ndiff --git a/resolve-undo.c b/resolve-undo.c\nindex c09b006..49ebaaf 100644\n--- a/resolve-undo.c\n+++ b/resolve-undo.c\n@@ -119,6 +119,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tstruct string_list_item *item;\n \tstruct resolve_undo_info *ru;\n \tint i, err = 0, matched;\n+\tchar *name;\n \n \tif (!istate->resolve_undo)\n \t\treturn pos;\n@@ -138,20 +139,22 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tif (!ru)\n \t\treturn pos;\n \tmatched = ce->ce_flags & CE_MATCHED;\n+\tname = xstrdup(ce->name);\n \tremove_index_entry_at(istate, pos);\n \tfor (i = 0; i < 3; i++) {\n \t\tstruct cache_entry *nce;\n \t\tif (!ru->mode[i])\n \t\t\tcontinue;\n \t\tnce = make_cache_entry(ru->mode[i], ru->sha1[i],\n-\t\t\t\t ce->name, i + 1, 0);\n+\t\t\t\t name, i + 1, 0);\n \t\tif (matched)\n \t\t\tnce->ce_flags |= CE_MATCHED;\n \t\tif (add_index_entry(istate, nce, ADD_CACHE_OK_TO_ADD)) {\n \t\t\terr = 1;\n-\t\t\terror(\"cannot unmerge '%s'\", ce->name);\n+\t\t\terror(\"cannot unmerge '%s'\", name);\n \t\t}\n \t}\n+\tfree(name);\n \tif (err)\n \t\treturn pos;\n \tfree(ru);\n-- \n1.8.5.rc0.333.g5394214\n"},{"id":"230653","messageId":"528549BB.20507@gmail.com","threadId":"35339","inReplyTo":"52851FB5.4050406@gmail.com","subject":"Re: [PATCH v5 00/14] New hash table implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T22:07:55Z","receivedAt":"2013-11-14T22:07:55Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 14.11.2013 20:08, schrieb Karsten Blees:\n> Changes since v3:\n\ns/v3/v4/\n"},{"id":"231989","messageId":"20131214020413.GB2311@google.com","threadId":"35339","inReplyTo":"528521E2.7090305@gmail.com","subject":"Re: [PATCH v5 02/14] add a hashtable implementation that supports O(1) removal","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2013-12-14T02:04:13Z","receivedAt":"2013-12-14T02:04:13Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nKarsten Blees wrote:\n\n> test-hashmap.c | 340 ++++++++++++++++++++++++++++++++\n\nHere come two small tweaks on top (meant for squashing in or applying\nto the series, whichever is more convenient).\n\nThanks,\nJonathan Nieder (2):\n Add test-hashmap to .gitignore\n Drop unnecessary #includes from test-hashmap\n\n .gitignore | 1 +\n test-hashmap.c | 3 +--\n 2 files changed, 2 insertions(+), 2 deletions(-)\n"},{"id":"231990","messageId":"20131214020526.GC2311@google.com","threadId":"35339","inReplyTo":"20131214020413.GB2311@google.com","subject":"[PATCH 1/2] Add test-hashmap to .gitignore","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2013-12-14T02:05:26Z","receivedAt":"2013-12-14T02:05:26Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Prevent the \"test-hashmap\" program from being accidentally tracked\nwith \"git add\" or cluttering \"git status\" output.\n\nSigned-off-by: Jonathan Nieder \n---\n .gitignore | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/.gitignore b/.gitignore\nindex b5f9def..dc600f9 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -182,6 +182,7 @@\n /test-dump-cache-tree\n /test-scrap-cache-tree\n /test-genrandom\n+/test-hashmap\n /test-index-version\n /test-line-buffer\n /test-match-trees\n-- \n1.8.5.1\n"},{"id":"231991","messageId":"20131214020640.GD2311@google.com","threadId":"35339","inReplyTo":"20131214020413.GB2311@google.com","subject":"[PATCH 2/2] Drop unnecessary #includes from test-hashmap","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2013-12-14T02:06:40Z","receivedAt":"2013-12-14T02:06:40Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Per Documentation/CodingGuidelines most C files in git start with\na #include of git-compat-util.h or another header file that includes\nit, such as cache.h or builtin.h. This file doesn't need anything\nbeyond \"git-compat-util.h\", so use that.\n\nRemove a #include of the system header since it is already\nincluded by \"git-compat-util.h\".\n\nSigned-off-by: Jonathan Nieder \n---\n test-hashmap.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/test-hashmap.c b/test-hashmap.c\nindex 7e86f88..f5183fb 100644\n--- a/test-hashmap.c\n+++ b/test-hashmap.c\n@@ -1,6 +1,5 @@\n-#include \"cache.h\"\n+#include \"git-compat-util.h\"\n #include \"hashmap.h\"\n-#include \n \n struct test_entry\n {\n-- \n1.8.5.1\n"},{"id":"232145","messageId":"52B19EEC.5020904@gmail.com","threadId":"35339","inReplyTo":"20131214020413.GB2311@google.com","subject":"Re: [PATCH v5 02/14] add a hashtable implementation that supports O(1) removal","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-12-18T13:11:08Z","receivedAt":"2013-12-18T13:11:08Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 14.12.2013 03:04, schrieb Jonathan Nieder:\n> Hi,\n> \n> Karsten Blees wrote:\n> \n>> test-hashmap.c | 340 ++++++++++++++++++++++++++++++++\n> \n> Here come two small tweaks on top (meant for squashing in or applying\n> to the series, whichever is more convenient).\n> \n> Thanks,\n> Jonathan Nieder (2):\n> Add test-hashmap to .gitignore\n> Drop unnecessary #includes from test-hashmap\n> \n> .gitignore | 1 +\n> test-hashmap.c | 3 +--\n> 2 files changed, 2 insertions(+), 2 deletions(-)\n> \nThanks, these two make perfect sense.\n\nI'm too damn slow again (merged to next two days ago), but FWIW:\nAcked-by: Karsten Blees \n"}]}