{"thread":{"id":"34904","subject":"[PATCH/RFC 0/5] New hash table implementation","startedAt":"2013-09-10T23:27:00Z","lastAt":"2013-09-26T14:38:12Z","messageCount":24,"participants":["Karsten Blees","Junio C Hamano","Fredrik Gustafsson","Tay Ray Chuan","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"227393","messageId":"522FAAC4.2080601@gmail.com","threadId":"34904","inReplyTo":null,"subject":"[PATCH/RFC 0/5] New hash table implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-10T23:27:00Z","receivedAt":"2013-09-10T23:27:00Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Also here: https://github.com/kblees/git/tree/kb/hashmap\n\nHi,\n\nthis is a spin-off of my (very slowly progressing) msysgit fscache project. I needed to remove things from the hash table, which cannot be implemented efficiently in hash.[ch].\n\nSo I wrote hasmap.[ch], with these features:\n- O(1) remove\n- builtin entry chaining\n- ready-to-use FNV-1 hash functions\n- unit test\n- additions are ~twice as fast\n- uses less memory\n\nPatches 2 and 5 convert existing uses of hash.[ch] to hashmap.[ch].\nPatches 3 and 4 are useful optimizations of their own.\n\nI haven't found the time to tackle name-hash.c yet, this is where remove() could come into play (to replace the CE_UNHASHED flag).\n\nKarsten\n\n\nKarsten Blees (5):\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\n Makefile | 3 +\n builtin/describe.c | 53 +++++------\n diffcore-rename.c | 185 +++++++++++++-------------------------\n hashmap.c | 210 +++++++++++++++++++++++++++++++++++++++++++\n hashmap.h | 200 +++++++++++++++++++++++++++++++++++++++++\n t/t0011-hashmap.sh | 236 ++++++++++++++++++++++++++++++++++++++++++++++++\n test-hashmap.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 7 files changed, 995 insertions(+), 150 deletions(-)\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-- \n1.8.4.8243.gbcbdefd\n"},{"id":"227394","messageId":"522FAB19.3080704@gmail.com","threadId":"34904","inReplyTo":"522FAAC4.2080601@gmail.com","subject":"[PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-10T23:28:25Z","receivedAt":"2013-09-10T23:28:25Z","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 meant to be piggybacked\nin front of the client's data structure to save memory. See test-hashmap.c\nfor usage examples.\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\nSigned-off-by: Karsten Blees \n---\n Makefile | 3 +\n hashmap.c | 210 +++++++++++++++++++++++++++++++++++++++++++\n hashmap.h | 200 +++++++++++++++++++++++++++++++++++++++++\n t/t0011-hashmap.sh | 236 ++++++++++++++++++++++++++++++++++++++++++++++++\n test-hashmap.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 5 files changed, 907 insertions(+)\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/Makefile b/Makefile\nindex 3588ca1..e6ad011 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -562,6 +562,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@@ -681,6 +682,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@@ -811,6 +813,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..686ee6f\n--- /dev/null\n+++ b/hashmap.c\n@@ -0,0 +1,210 @@\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_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+\n+static inline int entry_equals(const hashmap *map, const hashmap_entry *e1,\n+\t\tconst hashmap_entry *e2)\n+{\n+\treturn (e1 == e2) || (e1->hash == e2->hash && !(*map->cmpfn)(e1, e2));\n+}\n+\n+static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)\n+{\n+\treturn key->hash & (map->tablesize - 1);\n+}\n+\n+static void rehash(hashmap *map, unsigned int newsize)\n+{\n+\tunsigned int i, oldsize = map->tablesize;\n+\thashmap_entry **oldtable = map->table;\n+\n+\tmap->tablesize = newsize;\n+\tmap->table = xcalloc(sizeof(hashmap_entry*), map->tablesize);\n+\tfor (i = 0; i < oldsize; i++) {\n+\t\thashmap_entry *e = oldtable[i];\n+\t\twhile (e) {\n+\t\t\thashmap_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 hashmap_entry **find_entry(const hashmap *map,\n+\t\tconst hashmap_entry *key)\n+{\n+\thashmap_entry **e = &map->table[bucket(map, key)];\n+\twhile (*e && !entry_equals(map, *e, key))\n+\t\te = &(*e)->next;\n+\treturn e;\n+}\n+\n+static int always_equal(const void *unused1, const void *unused2)\n+{\n+\treturn 0;\n+}\n+\n+void hashmap_init(hashmap *map, hashmap_cmp_fn equals_function,\n+\t\tsize_t initial_size)\n+{\n+\tmap->size = 0;\n+\tmap->cmpfn = equals_function ? equals_function : always_equal;\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(hashmap_entry*), map->tablesize);\n+}\n+\n+void hashmap_free(hashmap *map, hashmap_free_fn free_function)\n+{\n+\tif (!map || !map->table)\n+\t\treturn;\n+\tif (free_function) {\n+\t\thashmap_iter iter;\n+\t\thashmap_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}\n+\tfree(map->table);\n+\tmemset(map, 0, sizeof(*map));\n+}\n+\n+void *hashmap_get(const hashmap *map, const void *key)\n+{\n+\treturn *find_entry(map, key);\n+}\n+\n+void *hashmap_get_next(const hashmap *map, const void *entry)\n+{\n+\thashmap_entry *e = ((hashmap_entry*) entry)->next;\n+\tfor (; e; e = e->next)\n+\t\tif (entry_equals(map, entry, e))\n+\t\t\treturn e;\n+\treturn NULL;\n+}\n+\n+void hashmap_add(hashmap *map, void *entry)\n+{\n+\tunsigned int b = bucket(map, entry);\n+\n+\t/* add entry */\n+\t((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+}\n+\n+void *hashmap_remove(hashmap *map, const void *key)\n+{\n+\thashmap_entry *old;\n+\thashmap_entry **e = find_entry(map, key);\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->tablesize > HASHMAP_INITIAL_SIZE &&\n+\t\tmap->size * HASHMAP_SHRINK_AT < map->tablesize)\n+\t\trehash(map, map->tablesize >> HASHMAP_GROW);\n+\treturn old;\n+}\n+\n+void *hashmap_put(hashmap *map, void *entry)\n+{\n+\thashmap_entry *old = hashmap_remove(map, entry);\n+\thashmap_add(map, entry);\n+\treturn old;\n+}\n+\n+void hashmap_iter_init(hashmap *map, hashmap_iter *iter)\n+{\n+\titer->map = map;\n+\titer->tablepos = 0;\n+\titer->next = NULL;\n+}\n+\n+void *hashmap_iter_next(hashmap_iter *iter)\n+{\n+\thashmap_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..59f8489\n--- /dev/null\n+++ b/hashmap.h\n@@ -0,0 +1,200 @@\n+#ifndef HASHMAP_H\n+#define HASHMAP_H\n+\n+/*\n+ * Generic implementation of hash-based key value mappings.\n+ * Supports basic operations get, add/put, remove and iteration.\n+ *\n+ * Also contains a set of ready-to-use hash functions for strings, using the\n+ * FNV-1 algorithm (see http://www.isthe.com/chongo/tech/comp/fnv).\n+ */\n+\n+/*\n+ * Case-sensitive FNV-1 hash of 0-terminated string.\n+ * str: the string\n+ * returns hash code\n+ */\n+extern unsigned int strhash(const char *buf);\n+\n+/*\n+ * Case-insensitive FNV-1 hash of 0-terminated string.\n+ * str: the string\n+ * returns hash code\n+ */\n+extern unsigned int strihash(const char *buf);\n+\n+/*\n+ * Case-sensitive FNV-1 hash of a memory block.\n+ * buf: start of the memory block\n+ * len: length of the memory block\n+ * returns hash code\n+ */\n+extern unsigned int memhash(const void *buf, size_t len);\n+\n+/*\n+ * Case-insensitive FNV-1 hash of a memory block.\n+ * buf: start of the memory block\n+ * len: length of the memory block\n+ * returns hash code\n+ */\n+extern unsigned int memihash(const void *buf, size_t len);\n+\n+/*\n+ * Hashmap entry data structure, intended to be used as first member of user\n+ * data structures. Consists of a pointer and an int. Ideally it should be\n+ * followed by an int-sized member to prevent unused memory on 64-bit systems\n+ * due to alignment.\n+ */\n+typedef struct hashmap_entry {\n+\tstruct hashmap_entry *next;\n+\tunsigned int hash;\n+} hashmap_entry;\n+\n+/*\n+ * User-supplied function to test two hashmap entries for equality, shall\n+ * return 0 if the entries are equal. This function is always called with\n+ * non-NULL parameters that have the same hash code. When looking up an entry,\n+ * the key parameter to hashmap_get and hashmap_remove is always passed as\n+ * second argument.\n+ */\n+typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key);\n+\n+/*\n+ * User-supplied function to free a hashmap entry.\n+ */\n+typedef void (*hashmap_free_fn)(void *entry);\n+\n+/*\n+ * Hashmap data structure, use with hashmap_* functions.\n+ */\n+typedef struct hashmap {\n+\thashmap_entry **table;\n+\thashmap_cmp_fn cmpfn;\n+\tunsigned int size, tablesize;\n+} hashmap;\n+\n+/*\n+ * Hashmap iterator data structure, use with hasmap_iter_* functions.\n+ */\n+typedef struct hashmap_iter {\n+\thashmap *map;\n+\thashmap_entry *next;\n+\tunsigned int tablepos;\n+} hashmap_iter;\n+\n+/*\n+ * Initializes a hashmap_entry structure.\n+ * entry: pointer to the entry to initialize\n+ * hash: hash code of the entry\n+ * key_only: true if entry is a key-only structure, see hashmap_entry_is_key\n+ */\n+static inline void hashmap_entry_init(void *entry, int hash, int key_only)\n+{\n+\thashmap_entry *e = entry;\n+\te->hash = hash;\n+\te->next = key_only ? (hashmap_entry*) -1 : NULL;\n+}\n+\n+/*\n+ * Checks if hashmap_entry was initialized with the key_only flag. This is\n+ * useful if the entry structure is variable-sized (e.g. ending in a FLEX_ARRAY)\n+ * and the key is part of the variable portion. To prevent dynamic allocation of\n+ * a full-fledged entry structure for each lookup, a smaller, statically sized\n+ * structure can be used as key (i.e. replacing the FLEX_ARRAY member with a\n+ * char pointer). The hashmap_cmp_fn comparison function can then check whether\n+ * entry_or_key is a full-fledged entry or a key-only structure.\n+ * entry: pointer to the entry to check\n+ * returns 0 for key-value entries and non-0 for key-only entries\n+ */\n+static inline int hashmap_entry_is_key(const void *entry)\n+{\n+\tconst hashmap_entry *e = entry;\n+\treturn e->next == (hashmap_entry*) -1;\n+}\n+\n+/*\n+ * Initializes a hashmap structure.\n+ * map: hashmap to initialize\n+ * equals_function: optional function to test equality of hashmap entries. If\n+ * NULL, entries are considered equal if their hash codes are equal.\n+ * initial_size: optional number of initial entries, 0 if unknown\n+ */\n+extern void hashmap_init(hashmap *map, hashmap_cmp_fn equals_function,\n+\t\tsize_t initial_size);\n+\n+/*\n+ * Frees a hashmap structure and allocated memory.\n+ * map: hashmap to free\n+ * free_function: optional function to free the hashmap entries\n+ */\n+extern void hashmap_free(hashmap *map, hashmap_free_fn free_function);\n+\n+/*\n+ * Returns the hashmap entry for the specified key, or NULL if not found.\n+ * map: the hashmap\n+ * key: key of the entry to look up\n+ * returns matching hashmap entry, or NULL if not found\n+ */\n+extern void *hashmap_get(const hashmap *map, const void *key);\n+\n+/*\n+ * Returns the next equal hashmap entry if the map contains duplicates (see\n+ * hashmap_add).\n+ * map: the hashmap\n+ * entry: current entry, obtained via hashmap_get or hashmap_get_next\n+ * returns next equal hashmap entry, or NULL if not found\n+ */\n+extern void *hashmap_get_next(const hashmap *map, const void *entry);\n+\n+/*\n+ * Adds a hashmap entry. This allows to add duplicate entries (i.e. separate\n+ * values with the same key according to hashmap_cmp_fn).\n+ * map: the hashmap\n+ * entry: the entry to add\n+ */\n+extern void hashmap_add(hashmap *map, void *entry);\n+\n+/*\n+ * Adds or replaces a hashmap entry.\n+ * map: the hashmap\n+ * entry: the entry to add or replace\n+ * returns previous entry, or NULL if the entry is new\n+ */\n+extern void *hashmap_put(hashmap *map, void *entry);\n+\n+/*\n+ * Removes a hashmap entry matching the specified key.\n+ * map: the hashmap\n+ * key: key of the entry to remove\n+ * returns removed entry, or NULL if not found\n+ */\n+extern void *hashmap_remove(hashmap *map, const void *key);\n+\n+/*\n+ * Initializes a hashmap iterator structure.\n+ * map: the hashmap\n+ * iter: hashmap iterator structure\n+ */\n+extern void hashmap_iter_init(hashmap *map, hashmap_iter *iter);\n+\n+/**\n+ * Returns the next hashmap entry.\n+ * iter: hashmap iterator\n+ * returns next entry, or NULL if there are no more entries\n+ */\n+extern void *hashmap_iter_next(hashmap_iter *iter);\n+\n+/**\n+ * Initializes a hashmap iterator and returns the first hashmap entry.\n+ * map: the hashmap\n+ * iter: hashmap iterator\n+ * returns first entry, or NULL if there are no entries\n+ */\n+static inline void *hashmap_iter_first(hashmap *map,\n+\t\thashmap_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..6c699d5\n--- /dev/null\n+++ b/t/t0011-hashmap.sh\n@@ -0,0 +1,236 @@\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 10)\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+\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..a4b3440\n--- /dev/null\n+++ b/test-hashmap.c\n@@ -0,0 +1,258 @@\n+#include \"cache.h\"\n+#include \"hashmap.h\"\n+#include \n+\n+typedef struct test_entry\n+{\n+\thashmap_entry ent;\n+\t/* key and value as two \\0-terminated strings */\n+\tchar key[FLEX_ARRAY];\n+} test_entry;\n+\n+typedef struct test_key\n+{\n+\thashmap_entry ent;\n+\tchar *key;\n+} test_key;\n+\n+static const char *get_key(const test_entry *e)\n+{\n+\treturn hashmap_entry_is_key(e) ? ((test_key*) e)->key : e->key;\n+}\n+\n+static const char *get_value(const test_entry *e)\n+{\n+\treturn e->key + strlen(e->key) + 1;\n+}\n+\n+static int test_entry_cmp(const test_entry *e1, const test_entry *e2)\n+{\n+\treturn strcmp(e1->key, get_key(e2));\n+}\n+\n+static int test_entry_cmp_icase(const test_entry *e1, const test_entry *e2)\n+{\n+\treturn strcasecmp(e1->key, get_key(e2));\n+}\n+\n+static test_entry *alloc_test_entry(int hash, char *key, int klen, char *value,\n+\t\tint vlen)\n+{\n+\ttest_entry *entry = malloc(sizeof(test_entry) + klen + vlen + 2);\n+\thashmap_entry_init(entry, hash, 0);\n+\tmemcpy(entry->key, key, klen + 1);\n+\tmemcpy(entry->key + klen + 1, value, vlen + 1);\n+\treturn entry;\n+}\n+\n+/*\n+ * Test insert performance of hashmap.[ch]\n+ * Usage: time echo \"perfhashmap size rounds\" | test-hashmap\n+ */\n+static void perf_hashmap(unsigned int size, unsigned int rounds)\n+{\n+\thashmap map;\n+\tchar buf[16];\n+\ttest_entry **entries;\n+\tunsigned int i, j;\n+\n+\tentries = malloc(size * sizeof(test_entry*));\n+\tfor (i = 0; i < size; i++) {\n+\t\tsnprintf(buf, sizeof(buf), \"%i\", i);\n+\t\tentries[i] = alloc_test_entry(0, buf, strlen(buf), \"\", 0);\n+\t}\n+\n+\tfor (j = 0; j < rounds; j++) {\n+\t\t// initialize the map\n+\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, 0);\n+\n+\t\t// add entries\n+\t\tfor (i = 0; i < size; i++) {\n+\t\t\tunsigned int hash = strhash(entries[i]->key);\n+\t\t\thashmap_entry_init(entries[i], hash, 0);\n+\t\t\thashmap_add(&map, entries[i]);\n+\t\t}\n+\n+\t\thashmap_free(&map, NULL);\n+\t}\n+}\n+\n+typedef struct hash_entry\n+{\n+\tstruct hash_entry *next;\n+\tchar key[FLEX_ARRAY];\n+} hash_entry;\n+\n+/*\n+ * Test insert performance of hash.[ch]\n+ * Usage: time echo \"perfhashtable size rounds\" | test-hashmap\n+ */\n+static void perf_hashtable(unsigned int size, unsigned int rounds)\n+{\n+\tstruct hash_table map;\n+\tchar buf[16];\n+\thash_entry **entries, **res;\n+\tunsigned int i, j;\n+\n+\tentries = malloc(size * sizeof(hash_entry*));\n+\tfor (i = 0; i < size; i++) {\n+\t\tsnprintf(buf, sizeof(buf), \"%i\", i);\n+\t\tentries[i] = malloc(sizeof(hash_entry) + strlen(buf) + 1);\n+\t\tstrcpy(entries[i]->key, buf);\n+\t}\n+\n+\tfor (j = 0; j < rounds; j++) {\n+\t\t// initialize the map\n+\t\tinit_hash(&map);\n+\n+\t\t// add entries\n+\t\tfor (i = 0; i < size; i++) {\n+\t\t\tunsigned int hash = strhash(entries[i]->key);\n+\t\t\tres = (hash_entry**) insert_hash(hash, entries[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\tfree_hash(&map);\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 size rounds -> hashmap.[ch]: add entries times\n+ * perfhashtable size rounds -> hash.[ch]: add entries times\n+ */\n+int main(int argc, char *argv[])\n+{\n+\tchar line[1024];\n+\thashmap 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\ttest_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\ttest_key key;\n+\t\t\thashmap_entry_init(&key, hash, 1);\n+\t\t\tkey.key = p1;\n+\n+\t\t\t/* lookup entry in hashmap */\n+\t\t\tentry = hashmap_get(&map, &key);\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\ttest_key key;\n+\t\t\thashmap_entry_init(&key, hash, 1);\n+\t\t\tkey.key = p1;\n+\n+\t\t\t/* remove entry from hashmap */\n+\t\t\tentry = hashmap_remove(&map, &key);\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\thashmap_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\", get_key(entry), 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(\"perfhashtable\", cmd) && l1 && l2) {\n+\n+\t\t\tperf_hashtable(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, free);\n+\treturn 0;\n+}\n-- \n1.8.4.8243.gbcbdefd\n"},{"id":"227395","messageId":"522FAB38.2020004@gmail.com","threadId":"34904","inReplyTo":"522FAAC4.2080601@gmail.com","subject":"[PATCH/RFC 2/5] buitin/describe.c: use new hash map implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-10T23:28:56Z","receivedAt":"2013-09-10T23:28:56Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \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 7d73722..bbc7159 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 hashmap names;\n static int have_util;\n static const char *pattern;\n static int always;\n@@ -38,7 +38,7 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n-\tstruct commit_name *next;\n+\thashmap_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,11 @@ static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n };\n \n+static int commit_name_cmp(struct commit_name *cn1, struct commit_name *cn2)\n+{\n+\treturn hashcmp(cn1->peeled, cn2->peeled);\n+}\n+\n static inline unsigned int hash_sha1(const unsigned char *sha1)\n {\n \tunsigned int hash;\n@@ -59,21 +64,10 @@ 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), 0);\n+\thashcpy(key.peeled, peeled);\n+\treturn hashmap_get(&names, &key);\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), 0);\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\thashmap_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.4.8243.gbcbdefd\n"},{"id":"227396","messageId":"522FAB5E.1060607@gmail.com","threadId":"34904","inReplyTo":"522FAAC4.2080601@gmail.com","subject":"[PATCH/RFC 3/5] diffcore-rename.c: move code around to prepare for the next patch","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-10T23:29:34Z","receivedAt":"2013-09-10T23:29:34Z","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 \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.4.8243.gbcbdefd\n"},{"id":"227397","messageId":"522FAB80.9020406@gmail.com","threadId":"34904","inReplyTo":"522FAAC4.2080601@gmail.com","subject":"[PATCH/RFC 4/5] diffcore-rename.c: simplify finding exact renames","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-10T23:30:08Z","receivedAt":"2013-09-10T23:30:08Z","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 \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..82b7975 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;\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.4.8243.gbcbdefd\n"},{"id":"227398","messageId":"522FABA1.10306@gmail.com","threadId":"34904","inReplyTo":"522FAAC4.2080601@gmail.com","subject":"[PATCH/RFC 5/5] diffcore-rename.c: use new hash map implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-10T23:30:41Z","receivedAt":"2013-09-10T23:30:41Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \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 82b7975..6271af9 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+\thashmap_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(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), 0);\n+\tfor (p = hashmap_get(srcs, &dst); 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(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), 0);\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;\n-\tstruct hash_table file_table;\n+\thashmap 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, free);\n \n \treturn renames;\n }\n-- \n1.8.4.8243.gbcbdefd\n"},{"id":"227498","messageId":"xmqqtxhqrjzf.fsf@gitster.dls.corp.google.com","threadId":"34904","inReplyTo":"522FAB19.3080704@gmail.com","subject":"Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-11T23:56:04Z","receivedAt":"2013-09-11T23:56:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees writes:\n\n> +#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n> +#define FNV32_PRIME ((unsigned int) 0x01000193)\n> + ...\n> +static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)\n> +{\n> +\treturn key->hash & (map->tablesize - 1);\n> +}\n\nAs tablesize would hopefully be reasonably small, not worrying about\nplatforms' \"unsigned int\" being 64-bit (in which case it would be\nmore appropriate to compute with FNV64_PRIME) should be fine.\n\n> +static inline hashmap_entry **find_entry(const hashmap *map,\n> +\t\tconst hashmap_entry *key)\n> +{\n> +\thashmap_entry **e = &map->table[bucket(map, key)];\n> +\twhile (*e && !entry_equals(map, *e, key))\n> +\t\te = &(*e)->next;\n> +\treturn e;\n> +}\n\n(mental note) This finds the location the pointer to the entry is\nstored, not the entry itself.\n\n> +void *hashmap_get(const hashmap *map, const void *key)\n> +{\n> +\treturn *find_entry(map, key);\n> +}\n\n... which is consistent with this, and more importantly, it is\ncrucial for hashmap_remove()'s implementation, because...\n\n> +void *hashmap_remove(hashmap *map, const void *key)\n> +{\n> +\thashmap_entry *old;\n> +\thashmap_entry **e = find_entry(map, key);\n> +\tif (!*e)\n> +\t\treturn NULL;\n> +\n> +\t/* remove existing entry */\n> +\told = *e;\n> +\t*e = old->next;\n\n... this wants to update the linked list in place.\n\nLooking good.\n\nI however wonder if the singly linked linear chain is a really good\nalternative for the access pattern of the hashes we use, though. Do\nwe really want to trigger growth on the bucket load factor, not the\nlength of the longest chain, for example?\n\n> +\told->next = NULL;\n> +\n> +\t/* fix size and rehash if appropriate */\n> +\tmap->size--;\n> +\tif (map->tablesize > HASHMAP_INITIAL_SIZE &&\n> +\t\tmap->size * HASHMAP_SHRINK_AT < map->tablesize)\n> +\t\trehash(map, map->tablesize >> HASHMAP_GROW);\n\nPlease align the first two lines so that the first non-whitespace on\nthe second line of the condition part of the \"if\" statement\n(i.e. 'm') aligns with the first non-whitespace inside the '(' open\nparenthesis (i.e. 'm').\n"},{"id":"227503","messageId":"xmqqmwnir86z.fsf@gitster.dls.corp.google.com","threadId":"34904","inReplyTo":"522FAB19.3080704@gmail.com","subject":"Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-12T04:10:44Z","receivedAt":"2013-09-12T04:10:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees writes:\n\n> +/*\n> + * Hashmap entry data structure, intended to be used as first member of user\n> + * data structures. Consists of a pointer and an int. Ideally it should be\n\nIt is technically correct to say this is \"intended to be\" used, but\nto those who are using this API, it would be more helpful to say \"a\nuser data structure that uses this API *must* have this as its first\nmember field\".\n\n> + * followed by an int-sized member to prevent unused memory on 64-bit systems\n> + * due to alignment.\n> + */\n> +typedef struct hashmap_entry {\n> +\tstruct hashmap_entry *next;\n> +\tunsigned int hash;\n> +} hashmap_entry;\n> + ...\n> +typedef struct hashmap {\n> +\thashmap_entry **table;\n> +\thashmap_cmp_fn cmpfn;\n> +\tunsigned int size, tablesize;\n> +} hashmap;\n\nI forgot to mention in my previous message, but we find that the\ncode tends to be easier to read if we avoid using typedef'ed struct\nlike these. E.g. in 2/5 we see something like this:\n\n static int abbrev = -1; /* unspecified */\n static int max_candidates = 10;\n -static struct hash_table names;\n +static hashmap names;\n static int have_util;\n static const char *pattern;\n static int always;\n @@ -38,7 +38,7 @@ static const char *diff_index_args[] = {\n\n\n struct commit_name {\n -\tstruct commit_name *next;\n +\thashmap_entry entry;\n unsigned char peeled[20];\n\nThe version before the patch is preferrable.\n\nThanks.\n"},{"id":"228068","messageId":"524006FD.2010604@gmail.com","threadId":"34904","inReplyTo":"xmqqtxhqrjzf.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-23T09:16:45Z","receivedAt":"2013-09-23T09:16:45Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Sorry for the delay, I've been on vacation...\n\nAm 12.09.2013 01:56, schrieb Junio C Hamano:\n> Karsten Blees writes:\n> \n>> +#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n>> +#define FNV32_PRIME ((unsigned int) 0x01000193)\n>> + ...\n>> +static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)\n>> +{\n>> +\treturn key->hash & (map->tablesize - 1);\n>> +}\n> \n> As tablesize would hopefully be reasonably small, not worrying about\n> platforms' \"unsigned int\" being 64-bit (in which case it would be\n> more appropriate to compute with FNV64_PRIME) should be fine.\n> \n>> +static inline hashmap_entry **find_entry(const hashmap *map,\n>> +\t\tconst hashmap_entry *key)\n>> +{\n>> +\thashmap_entry **e = &map->table[bucket(map, key)];\n>> +\twhile (*e && !entry_equals(map, *e, key))\n>> +\t\te = &(*e)->next;\n>> +\treturn e;\n>> +}\n> \n> (mental note) This finds the location the pointer to the entry is\n> stored, not the entry itself.\n> \n\nWill rename to find_entry_ptr to make this clear\n\n>> +void *hashmap_get(const hashmap *map, const void *key)\n>> +{\n>> +\treturn *find_entry(map, key);\n>> +}\n> \n> ... which is consistent with this, and more importantly, it is\n> crucial for hashmap_remove()'s implementation, because...\n> \n>> +void *hashmap_remove(hashmap *map, const void *key)\n>> +{\n>> +\thashmap_entry *old;\n>> +\thashmap_entry **e = find_entry(map, key);\n>> +\tif (!*e)\n>> +\t\treturn NULL;\n>> +\n>> +\t/* remove existing entry */\n>> +\told = *e;\n>> +\t*e = old->next;\n> \n> ... this wants to update the linked list in place.\n> \n> Looking good.\n> \n> I however wonder if the singly linked linear chain is a really good\n> alternative for the access pattern of the hashes we use, though.\n\nI don't think it will make a big difference in lookup performance, especially with good hash codes (such as the first bytes of a sha1). In theory, chaining should be slightly faster, because entries are strictly confined to their buckets (i.e. no extraneous entries need to be traversed when looking up an entry). With uniform hash distribution, chaining should require (1 + loadfactor) comparisons to find an entry, while open addressing requires (1/(1 - loadfactor)) [1]. I'll add a performance test for lookups, though.\n\n[1] http://en.wikipedia.org/wiki/Hash_table#Performance_analysis\n\n> Do we really want to trigger growth on the bucket load factor, not the\n> length of the longest chain, for example?\n> \n\nWith good hashes and a load factor < 1, the longest 'chain' is 1. We only get chains in case of collisions, which however cannot necessarily be resolved by resizing. E.g. in the worst case, all entries have the same hash code, which deforms the hash table into a long linked list in a single bucket. Resizing won't change that.\n\nAn alternative would be to resize on the number of used buckets instead of total entries. I.e. with exceptionally bad hash codes and lots of collisions, we at least don't waste memory by making the table unnecessarily large. However, I don't think this is worth the extra effort.\n\n>> +\told->next = NULL;\n>> +\n>> +\t/* fix size and rehash if appropriate */\n>> +\tmap->size--;\n>> +\tif (map->tablesize > HASHMAP_INITIAL_SIZE &&\n>> +\t\tmap->size * HASHMAP_SHRINK_AT < map->tablesize)\n>> +\t\trehash(map, map->tablesize >> HASHMAP_GROW);\n> \n> Please align the first two lines so that the first non-whitespace on\n> the second line of the condition part of the \"if\" statement\n> (i.e. 'm') aligns with the first non-whitespace inside the '(' open\n> parenthesis (i.e. 'm').\n> \n\nWill do.\n"},{"id":"228069","messageId":"52400835.8090902@gmail.com","threadId":"34904","inReplyTo":"xmqqmwnir86z.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-23T09:21:57Z","receivedAt":"2013-09-23T09:21:57Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 12.09.2013 06:10, schrieb Junio C Hamano:\n> Karsten Blees writes:\n> \n>> +/*\n>> + * Hashmap entry data structure, intended to be used as first member of user\n>> + * data structures. Consists of a pointer and an int. Ideally it should be\n> \n> It is technically correct to say this is \"intended to be\" used, but\n> to those who are using this API, it would be more helpful to say \"a\n> user data structure that uses this API *must* have this as its first\n> member field\".\n> \n\nRight. I considered making the position in the user struct configurable via some offsetof() magic, but this would have just complicated things unnecessarily.\n\n>> + * followed by an int-sized member to prevent unused memory on 64-bit systems\n>> + * due to alignment.\n>> + */\n>> +typedef struct hashmap_entry {\n>> +\tstruct hashmap_entry *next;\n>> +\tunsigned int hash;\n>> +} hashmap_entry;\n>> + ...\n>> +typedef struct hashmap {\n>> +\thashmap_entry **table;\n>> +\thashmap_cmp_fn cmpfn;\n>> +\tunsigned int size, tablesize;\n>> +} hashmap;\n> \n> I forgot to mention in my previous message, but we find that the\n> code tends to be easier to read if we avoid using typedef'ed struct\n> like these. E.g. in 2/5 we see something like this:\n> \n> static int abbrev = -1; /* unspecified */\n> static int max_candidates = 10;\n> -static struct hash_table names;\n> +static hashmap names;\n> static int have_util;\n> static const char *pattern;\n> static int always;\n> @@ -38,7 +38,7 @@ static const char *diff_index_args[] = {\n> \n> \n> struct commit_name {\n> -\tstruct commit_name *next;\n> +\thashmap_entry entry;\n> unsigned char peeled[20];\n> \n> The version before the patch is preferrable.\n> \n\nOK\n"},{"id":"228150","messageId":"52416058.90008@gmail.com","threadId":"34904","inReplyTo":"522FAAC4.2080601@gmail.com","subject":"[PATCH v2 0/5] New hash table implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-24T09:50:16Z","receivedAt":"2013-09-24T09:50:16Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Also here: https://github.com/kblees/git/tree/kb/hashmap-v2\n\nChanges since initial version:\n- removed struct typedefs\n- clarified documentation of hashmap_entry\n- renamed find_entry -> find_entry_ptr\n- added performance tests for lookup\n\n\nI've also tried to resize the table based on the number of used buckets (instead of total entries). However, this doesn't work with hash functions that produce 'gaps'. E.g. a hash function that returns only even numbers would fill only every second bucket (i.e. max. 50% buckets used), and the 80% resize threshold is never reached.\n\n\nRegarding performance, I have to admit that the difference between the two implementations is far greater than I had anticipated. The following times (in seconds) are from Linux x64 (Debian Sarge) on a Core i7 860 @2.8GHz. All tests have been run with 1,000 rounds of 100,000 entries each.\n\nThe 'get 10% hits' test does 100,000 lookups on a table with 10,000 entries (i.e. 90% unsuccessful lookups).\n\nThe rows denote different hash functions with different qualities:\n- FNV: FNV-1 hash on stringified loop counter (i.e. fnv1(itoa(i))), as\n an example of a high quality / low collision hash\n- i: just the loop counter (i.e. 0, 1, 2,...), guaranteed collision free\n- i/10: every 10 entries share the same hash code, lots of collisions\n\nThe i and i/10 tests show that open addressing suffers badly from clustering, i.e. with adjacent hash codes, it degrades to linear search. The *2 versions provide for some space between used buckets to better compare it to the chaining version.\n\n\n | add | get 100% hits | get 10% hits\n | hash | hashmap | hash | hashmap | hash | hashmap\n--------+--------+---------+-------+---------+---------+--------\nFNV | 14.815 | 2.345 | 3.059 | 1.642 | 4.085 | 0.976\nFNV x2 | 14.409 | 2.706 | 2.888 | 1.959 | 3.905 | 1.393\ni | 7.432 | 1.593 | 1.364 | 1.142 | 413.023 | 0.589\ni x2 | 9.169 | 1.866 | 1.427 | 1.163 | 0.757 | 0.670\ni/10 | 1.800 | 1.555 | 5.365 | 6.465 | 32.918 | 1.052\ni/10 x2 | 1.892 | 1.555 | 5.386 | 6.474 | 1.123 | 1.206\n\nTests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n\n\nKarsten Blees (5):\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\n Makefile | 3 +\n builtin/describe.c | 53 ++++----\n diffcore-rename.c | 185 ++++++++++------------------\n hashmap.c | 211 +++++++++++++++++++++++++++++++\n hashmap.h | 200 ++++++++++++++++++++++++++++++\n t/t0011-hashmap.sh | 236 +++++++++++++++++++++++++++++++++++\n test-hashmap.c | 354 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 7 files changed, 1092 insertions(+), 150 deletions(-)\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..kb/hashmap-v2:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex bbc7159..5db5d89 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\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 hashmap names;\n+static struct hashmap names;\n static int have_util;\n static const char *pattern;\n static int always;\n@@ -38,7 +38,7 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n-\thashmap_entry entry;\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@@ -280,7 +280,7 @@ 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\thashmap_iter iter;\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)) {\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6271af9..2e70d31 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-\thashmap_entry entry;\n+\tstruct hashmap_entry entry;\n \tint index;\n \tstruct diff_filespec *filespec;\n };\n@@ -260,7 +260,7 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)\n \treturn hash;\n }\n \n-static int find_identical_files(hashmap *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@@ -310,7 +310,7 @@ static int find_identical_files(hashmap *srcs,\n \treturn renames;\n }\n \n-static void insert_file_table(hashmap *table, int index, struct diff_filespec *filespec)\n+static void insert_file_table(struct hashmap *table, int index, struct diff_filespec *filespec)\n {\n \tstruct file_similarity *entry = xmalloc(sizeof(*entry));\n \n@@ -331,7 +331,7 @@ static void insert_file_table(hashmap *table, int index, struct diff_filespec *f\n static int find_exact_renames(struct diff_options *options)\n {\n \tint i, renames;\n-\thashmap file_table;\n+\tstruct hashmap file_table;\n \n \t/* Add all sources to the hash table */\n \thashmap_init(&file_table, NULL, rename_src_nr);\ndiff --git a/hashmap.c b/hashmap.c\nindex 686ee6f..75a8578 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -58,28 +58,29 @@ unsigned int memihash(const void *buf, size_t len)\n /* shrink if < 16.6% full (to 66.6%) */\n #define HASHMAP_SHRINK_AT 6\n \n-static inline int entry_equals(const hashmap *map, const hashmap_entry *e1,\n-\t\tconst hashmap_entry *e2)\n+static inline int entry_equals(const struct hashmap *map,\n+\t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2)\n {\n \treturn (e1 == e2) || (e1->hash == e2->hash && !(*map->cmpfn)(e1, e2));\n }\n \n-static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)\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(hashmap *map, unsigned int newsize)\n+static void rehash(struct hashmap *map, unsigned int newsize)\n {\n \tunsigned int i, oldsize = map->tablesize;\n-\thashmap_entry **oldtable = map->table;\n+\tstruct hashmap_entry **oldtable = map->table;\n \n \tmap->tablesize = newsize;\n-\tmap->table = xcalloc(sizeof(hashmap_entry*), map->tablesize);\n+\tmap->table = xcalloc(sizeof(struct hashmap_entry*), map->tablesize);\n \tfor (i = 0; i < oldsize; i++) {\n-\t\thashmap_entry *e = oldtable[i];\n+\t\tstruct hashmap_entry *e = oldtable[i];\n \t\twhile (e) {\n-\t\t\thashmap_entry *next = e->next;\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@@ -89,10 +90,10 @@ static void rehash(hashmap *map, unsigned int newsize)\n \tfree(oldtable);\n }\n \n-static inline hashmap_entry **find_entry(const hashmap *map,\n-\t\tconst hashmap_entry *key)\n+static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,\n+\t\tconst struct hashmap_entry *key)\n {\n-\thashmap_entry **e = &map->table[bucket(map, key)];\n+\tstruct hashmap_entry **e = &map->table[bucket(map, key)];\n \twhile (*e && !entry_equals(map, *e, key))\n \t\te = &(*e)->next;\n \treturn e;\n@@ -103,7 +104,7 @@ static int always_equal(const void *unused1, const void *unused2)\n \treturn 0;\n }\n \n-void hashmap_init(hashmap *map, hashmap_cmp_fn equals_function,\n+void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n \t\tsize_t initial_size)\n {\n \tmap->size = 0;\n@@ -113,16 +114,16 @@ void hashmap_init(hashmap *map, hashmap_cmp_fn equals_function,\n \tinitial_size *= HASHMAP_GROW_AT;\n \twhile (initial_size > map->tablesize)\n \t\tmap->tablesize <<= HASHMAP_GROW;\n-\tmap->table = xcalloc(sizeof(hashmap_entry*), map->tablesize);\n+\tmap->table = xcalloc(sizeof(struct hashmap_entry*), map->tablesize);\n }\n \n-void hashmap_free(hashmap *map, hashmap_free_fn free_function)\n+void hashmap_free(struct hashmap *map, hashmap_free_fn free_function)\n {\n \tif (!map || !map->table)\n \t\treturn;\n \tif (free_function) {\n-\t\thashmap_iter iter;\n-\t\thashmap_entry *e;\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@@ -131,26 +132,26 @@ void hashmap_free(hashmap *map, hashmap_free_fn free_function)\n \tmemset(map, 0, sizeof(*map));\n }\n \n-void *hashmap_get(const hashmap *map, const void *key)\n+void *hashmap_get(const struct hashmap *map, const void *key)\n {\n-\treturn *find_entry(map, key);\n+\treturn *find_entry_ptr(map, key);\n }\n \n-void *hashmap_get_next(const hashmap *map, const void *entry)\n+void *hashmap_get_next(const struct hashmap *map, const void *entry)\n {\n-\thashmap_entry *e = ((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))\n \t\t\treturn e;\n \treturn NULL;\n }\n \n-void hashmap_add(hashmap *map, void *entry)\n+void hashmap_add(struct hashmap *map, void *entry)\n {\n \tunsigned int b = bucket(map, entry);\n \n \t/* add entry */\n-\t((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@@ -159,10 +160,10 @@ void hashmap_add(hashmap *map, void *entry)\n \t\trehash(map, map->tablesize << HASHMAP_GROW);\n }\n \n-void *hashmap_remove(hashmap *map, const void *key)\n+void *hashmap_remove(struct hashmap *map, const void *key)\n {\n-\thashmap_entry *old;\n-\thashmap_entry **e = find_entry(map, key);\n+\tstruct hashmap_entry *old;\n+\tstruct hashmap_entry **e = find_entry_ptr(map, key);\n \tif (!*e)\n \t\treturn NULL;\n \n@@ -174,28 +175,28 @@ void *hashmap_remove(hashmap *map, const void *key)\n \t/* fix size and rehash if appropriate */\n \tmap->size--;\n \tif (map->tablesize > HASHMAP_INITIAL_SIZE &&\n-\t\tmap->size * HASHMAP_SHRINK_AT < map->tablesize)\n+\t map->size * HASHMAP_SHRINK_AT < map->tablesize)\n \t\trehash(map, map->tablesize >> HASHMAP_GROW);\n \treturn old;\n }\n \n-void *hashmap_put(hashmap *map, void *entry)\n+void *hashmap_put(struct hashmap *map, void *entry)\n {\n-\thashmap_entry *old = hashmap_remove(map, entry);\n+\tstruct hashmap_entry *old = hashmap_remove(map, entry);\n \thashmap_add(map, entry);\n \treturn old;\n }\n \n-void hashmap_iter_init(hashmap *map, hashmap_iter *iter)\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(hashmap_iter *iter)\n+void *hashmap_iter_next(struct hashmap_iter *iter)\n {\n-\thashmap_entry *current = iter->next;\n+\tstruct hashmap_entry *current = iter->next;\n \tfor (;;) {\n \t\tif (current) {\n \t\t\titer->next = current->next;\ndiff --git a/hashmap.h b/hashmap.h\nindex 59f8489..98c4ebc 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -40,15 +40,15 @@ extern unsigned int memhash(const void *buf, size_t len);\n extern unsigned int memihash(const void *buf, size_t len);\n \n /*\n- * Hashmap entry data structure, intended to be used as first member of user\n- * data structures. Consists of a pointer and an int. Ideally it should be\n- * followed by an int-sized member to prevent unused memory on 64-bit systems\n- * due to alignment.\n+ * Hashmap entry data structure, must be used as first member of user data\n+ * structures. Consists of a pointer and an int. Ideally it should be followed\n+ * by an int-sized member to prevent unused memory on 64-bit systems due to\n+ * alignment.\n */\n-typedef struct hashmap_entry {\n+struct hashmap_entry {\n \tstruct hashmap_entry *next;\n \tunsigned int hash;\n-} hashmap_entry;\n+};\n \n /*\n * User-supplied function to test two hashmap entries for equality, shall\n@@ -67,20 +67,20 @@ typedef void (*hashmap_free_fn)(void *entry);\n /*\n * Hashmap data structure, use with hashmap_* functions.\n */\n-typedef struct hashmap {\n-\thashmap_entry **table;\n+struct hashmap {\n+\tstruct hashmap_entry **table;\n \thashmap_cmp_fn cmpfn;\n \tunsigned int size, tablesize;\n-} hashmap;\n+};\n \n /*\n * Hashmap iterator data structure, use with hasmap_iter_* functions.\n */\n-typedef struct hashmap_iter {\n-\thashmap *map;\n-\thashmap_entry *next;\n+struct hashmap_iter {\n+\tstruct hashmap *map;\n+\tstruct hashmap_entry *next;\n \tunsigned int tablepos;\n-} hashmap_iter;\n+};\n \n /*\n * Initializes a hashmap_entry structure.\n@@ -90,9 +90,9 @@ typedef struct hashmap_iter {\n */\n static inline void hashmap_entry_init(void *entry, int hash, int key_only)\n {\n-\thashmap_entry *e = entry;\n+\tstruct hashmap_entry *e = entry;\n \te->hash = hash;\n-\te->next = key_only ? (hashmap_entry*) -1 : NULL;\n+\te->next = key_only ? (struct hashmap_entry*) -1 : NULL;\n }\n \n /*\n@@ -108,8 +108,8 @@ static inline void hashmap_entry_init(void *entry, int hash, int key_only)\n */\n static inline int hashmap_entry_is_key(const void *entry)\n {\n-\tconst hashmap_entry *e = entry;\n-\treturn e->next == (hashmap_entry*) -1;\n+\tconst struct hashmap_entry *e = entry;\n+\treturn e->next == (struct hashmap_entry*) -1;\n }\n \n /*\n@@ -119,7 +119,7 @@ static inline int hashmap_entry_is_key(const void *entry)\n * NULL, entries are considered equal if their hash codes are equal.\n * initial_size: optional number of initial entries, 0 if unknown\n */\n-extern void hashmap_init(hashmap *map, hashmap_cmp_fn equals_function,\n+extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n \t\tsize_t initial_size);\n \n /*\n@@ -127,7 +127,7 @@ extern void hashmap_init(hashmap *map, hashmap_cmp_fn equals_function,\n * map: hashmap to free\n * free_function: optional function to free the hashmap entries\n */\n-extern void hashmap_free(hashmap *map, hashmap_free_fn free_function);\n+extern void hashmap_free(struct hashmap *map, hashmap_free_fn free_function);\n \n /*\n * Returns the hashmap entry for the specified key, or NULL if not found.\n@@ -135,7 +135,7 @@ extern void hashmap_free(hashmap *map, hashmap_free_fn free_function);\n * key: key of the entry to look up\n * returns matching hashmap entry, or NULL if not found\n */\n-extern void *hashmap_get(const hashmap *map, const void *key);\n+extern void *hashmap_get(const struct hashmap *map, const void *key);\n \n /*\n * Returns the next equal hashmap entry if the map contains duplicates (see\n@@ -144,7 +144,7 @@ extern void *hashmap_get(const hashmap *map, const void *key);\n * entry: current entry, obtained via hashmap_get or hashmap_get_next\n * returns next equal hashmap entry, or NULL if not found\n */\n-extern void *hashmap_get_next(const hashmap *map, const void *entry);\n+extern void *hashmap_get_next(const struct hashmap *map, const void *entry);\n \n /*\n * Adds a hashmap entry. This allows to add duplicate entries (i.e. separate\n@@ -152,7 +152,7 @@ extern void *hashmap_get_next(const hashmap *map, const void *entry);\n * map: the hashmap\n * entry: the entry to add\n */\n-extern void hashmap_add(hashmap *map, void *entry);\n+extern void hashmap_add(struct hashmap *map, void *entry);\n \n /*\n * Adds or replaces a hashmap entry.\n@@ -160,7 +160,7 @@ extern void hashmap_add(hashmap *map, void *entry);\n * entry: the entry to add or replace\n * returns previous entry, or NULL if the entry is new\n */\n-extern void *hashmap_put(hashmap *map, void *entry);\n+extern void *hashmap_put(struct hashmap *map, void *entry);\n \n /*\n * Removes a hashmap entry matching the specified key.\n@@ -168,21 +168,21 @@ extern void *hashmap_put(hashmap *map, void *entry);\n * key: key of the entry to remove\n * returns removed entry, or NULL if not found\n */\n-extern void *hashmap_remove(hashmap *map, const void *key);\n+extern void *hashmap_remove(struct hashmap *map, const void *key);\n \n /*\n * Initializes a hashmap iterator structure.\n * map: the hashmap\n * iter: hashmap iterator structure\n */\n-extern void hashmap_iter_init(hashmap *map, hashmap_iter *iter);\n+extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n \n /**\n * Returns the next hashmap entry.\n * iter: hashmap iterator\n * returns next entry, or NULL if there are no more entries\n */\n-extern void *hashmap_iter_next(hashmap_iter *iter);\n+extern void *hashmap_iter_next(struct hashmap_iter *iter);\n \n /**\n * Initializes a hashmap iterator and returns the first hashmap entry.\n@@ -190,8 +190,8 @@ extern void *hashmap_iter_next(hashmap_iter *iter);\n * iter: hashmap iterator\n * returns first entry, or NULL if there are no entries\n */\n-static inline void *hashmap_iter_first(hashmap *map,\n-\t\thashmap_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);\ndiff --git a/test-hashmap.c b/test-hashmap.c\nindex a4b3440..de94c6d 100644\n--- a/test-hashmap.c\n+++ b/test-hashmap.c\n@@ -2,113 +2,197 @@\n #include \"hashmap.h\"\n #include \n \n-typedef struct test_entry\n+struct test_entry\n {\n-\thashmap_entry ent;\n+\tstruct hashmap_entry ent;\n \t/* key and value as two \\0-terminated strings */\n \tchar key[FLEX_ARRAY];\n-} test_entry;\n+};\n \n-typedef struct test_key\n+struct test_key\n {\n-\thashmap_entry ent;\n+\tstruct hashmap_entry ent;\n \tchar *key;\n-} test_key;\n+};\n \n-static const char *get_key(const test_entry *e)\n+static const char *get_key(const struct test_entry *e)\n {\n-\treturn hashmap_entry_is_key(e) ? ((test_key*) e)->key : e->key;\n+\treturn hashmap_entry_is_key(e) ? ((struct test_key*) e)->key : e->key;\n }\n \n-static const char *get_value(const test_entry *e)\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 test_entry *e1, const test_entry *e2)\n+static int test_entry_cmp(const struct test_entry *e1,\n+\t\tconst struct test_entry *e2)\n {\n \treturn strcmp(e1->key, get_key(e2));\n }\n \n-static int test_entry_cmp_icase(const test_entry *e1, const test_entry *e2)\n+static int test_entry_cmp_icase(const struct test_entry *e1,\n+\t\tconst struct test_entry *e2)\n {\n \treturn strcasecmp(e1->key, get_key(e2));\n }\n \n-static test_entry *alloc_test_entry(int hash, char *key, int klen, char *value,\n-\t\tint vlen)\n+static struct test_entry *alloc_test_entry(int hash, char *key, int klen,\n+\t\tchar *value, int vlen)\n {\n-\ttest_entry *entry = malloc(sizeof(test_entry) + klen + vlen + 2);\n+\tstruct test_entry *entry = malloc(sizeof(struct test_entry) + klen\n+\t\t\t+ vlen + 2);\n \thashmap_entry_init(entry, hash, 0);\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 insert performance of hashmap.[ch]\n- * Usage: time echo \"perfhashmap size rounds\" | test-hashmap\n+ * Usage: time echo \"perfhashmap method rounds\" | test-hashmap\n */\n-static void perf_hashmap(unsigned int size, unsigned int rounds)\n+static void perf_hashmap(unsigned int method, unsigned int rounds)\n {\n-\thashmap map;\n+\tstruct hashmap map;\n \tchar buf[16];\n-\ttest_entry **entries;\n+\tstruct test_entry **entries;\n+\tunsigned int *hashes;\n \tunsigned int i, j;\n \n-\tentries = malloc(size * sizeof(test_entry*));\n-\tfor (i = 0; i < size; i++) {\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-\tfor (j = 0; j < rounds; j++) {\n-\t\t// initialize the map\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], 0);\n+\t\t\t\thashmap_add(&map, entries[i]);\n+\t\t\t}\n+\n+\t\t\thashmap_free(&map, NULL);\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// add entries\n-\t\tfor (i = 0; i < size; i++) {\n-\t\t\tunsigned int hash = strhash(entries[i]->key);\n-\t\t\thashmap_entry_init(entries[i], hash, 0);\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], 0);\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 test_key k;\n+\t\t\t\thashmap_entry_init(&k, hashes[i], 1);\n+\t\t\t\tk.key = entries[i]->key;\n+\t\t\t\thashmap_get(&map, &k);\n+\t\t\t}\n+\t\t}\n+\n \t\thashmap_free(&map, NULL);\n \t}\n }\n \n-typedef struct hash_entry\n+struct hash_entry\n {\n \tstruct hash_entry *next;\n \tchar key[FLEX_ARRAY];\n-} hash_entry;\n+};\n \n /*\n * Test insert performance of hash.[ch]\n- * Usage: time echo \"perfhashtable size rounds\" | test-hashmap\n+ * Usage: time echo \"perfhash method rounds\" | test-hashmap\n */\n-static void perf_hashtable(unsigned int size, unsigned int rounds)\n+static void perf_hash(unsigned int method, unsigned int rounds)\n {\n \tstruct hash_table map;\n \tchar buf[16];\n-\thash_entry **entries, **res;\n+\tstruct hash_entry **entries, **res, *entry;\n+\tunsigned int *hashes;\n \tunsigned int i, j;\n \n-\tentries = malloc(size * sizeof(hash_entry*));\n-\tfor (i = 0; i < size; i++) {\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(hash_entry) + strlen(buf) + 1);\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-\tfor (j = 0; j < rounds; j++) {\n-\t\t// initialize the map\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// add entries\n-\t\tfor (i = 0; i < size; i++) {\n-\t\t\tunsigned int hash = strhash(entries[i]->key);\n-\t\t\tres = (hash_entry**) insert_hash(hash, entries[i], &map);\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@@ -117,7 +201,19 @@ static void perf_hashtable(unsigned int size, unsigned int rounds)\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@@ -133,13 +229,13 @@ static void perf_hashtable(unsigned int size, unsigned int rounds)\n * iterate -> key1 value1\\nkey2 value2\\n...\n * size -> tablesize numentries\n *\n- * perfhashmap size rounds -> hashmap.[ch]: add entries times\n- * perfhashtable size rounds -> hash.[ch]: add entries times\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-\thashmap map;\n+\tstruct hashmap map;\n \tint icase;\n \n \t/* init hash map */\n@@ -151,7 +247,7 @@ int main(int argc, char *argv[])\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\ttest_entry *entry;\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@@ -197,7 +293,7 @@ int main(int argc, char *argv[])\n \t\t} else if (!strcmp(\"get\", cmd) && l1) {\n \n \t\t\t/* setup static key */\n-\t\t\ttest_key key;\n+\t\t\tstruct test_key key;\n \t\t\thashmap_entry_init(&key, hash, 1);\n \t\t\tkey.key = p1;\n \n@@ -215,7 +311,7 @@ int main(int argc, char *argv[])\n \t\t} else if (!strcmp(\"remove\", cmd) && l1) {\n \n \t\t\t/* setup static key */\n-\t\t\ttest_key key;\n+\t\t\tstruct test_key key;\n \t\t\thashmap_entry_init(&key, hash, 1);\n \t\t\tkey.key = p1;\n \n@@ -228,7 +324,7 @@ int main(int argc, char *argv[])\n \n \t\t} else if (!strcmp(\"iterate\", cmd)) {\n \n-\t\t\thashmap_iter iter;\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\", get_key(entry), get_value(entry));\n@@ -242,9 +338,9 @@ int main(int argc, char *argv[])\n \n \t\t\tperf_hashmap(atoi(p1), atoi(p2));\n \n-\t\t} else if (!strcmp(\"perfhashtable\", cmd) && l1 && l2) {\n+\t\t} else if (!strcmp(\"perfhash\", cmd) && l1 && l2) {\n \n-\t\t\tperf_hashtable(atoi(p1), atoi(p2));\n+\t\t\tperf_hash(atoi(p1), atoi(p2));\n \n \t\t} else {\n \n"},{"id":"228151","messageId":"5241609C.1010406@gmail.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"[PATCH v2 1/5] add a hashtable implementation that supports O(1) removal","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-24T09:51:24Z","receivedAt":"2013-09-24T09:51:24Z","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 \n---\n Makefile | 3 +\n hashmap.c | 211 +++++++++++++++++++++++++++++++\n hashmap.h | 200 ++++++++++++++++++++++++++++++\n t/t0011-hashmap.sh | 236 +++++++++++++++++++++++++++++++++++\n test-hashmap.c | 354 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 5 files changed, 1004 insertions(+)\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/Makefile b/Makefile\nindex 3588ca1..e6ad011 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -562,6 +562,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@@ -681,6 +682,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@@ -811,6 +813,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..75a8578\n--- /dev/null\n+++ b/hashmap.c\n@@ -0,0 +1,211 @@\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_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+\n+static inline int entry_equals(const struct hashmap *map,\n+\t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2)\n+{\n+\treturn (e1 == e2) || (e1->hash == e2->hash && !(*map->cmpfn)(e1, e2));\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+\tmap->tablesize = newsize;\n+\tmap->table = xcalloc(sizeof(struct hashmap_entry*), map->tablesize);\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)\n+{\n+\tstruct hashmap_entry **e = &map->table[bucket(map, key)];\n+\twhile (*e && !entry_equals(map, *e, key))\n+\t\te = &(*e)->next;\n+\treturn e;\n+}\n+\n+static int always_equal(const void *unused1, const void *unused2)\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+\tmap->size = 0;\n+\tmap->cmpfn = equals_function ? equals_function : always_equal;\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+}\n+\n+void hashmap_free(struct hashmap *map, hashmap_free_fn free_function)\n+{\n+\tif (!map || !map->table)\n+\t\treturn;\n+\tif (free_function) {\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}\n+\tfree(map->table);\n+\tmemset(map, 0, sizeof(*map));\n+}\n+\n+void *hashmap_get(const struct hashmap *map, const void *key)\n+{\n+\treturn *find_entry_ptr(map, key);\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))\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 * HASHMAP_GROW_AT > map->tablesize)\n+\t\trehash(map, map->tablesize << HASHMAP_GROW);\n+}\n+\n+void *hashmap_remove(struct hashmap *map, const void *key)\n+{\n+\tstruct hashmap_entry *old;\n+\tstruct hashmap_entry **e = find_entry_ptr(map, key);\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->tablesize > HASHMAP_INITIAL_SIZE &&\n+\t map->size * HASHMAP_SHRINK_AT < map->tablesize)\n+\t\trehash(map, map->tablesize >> HASHMAP_GROW);\n+\treturn old;\n+}\n+\n+void *hashmap_put(struct hashmap *map, void *entry)\n+{\n+\tstruct hashmap_entry *old = hashmap_remove(map, entry);\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..98c4ebc\n--- /dev/null\n+++ b/hashmap.h\n@@ -0,0 +1,200 @@\n+#ifndef HASHMAP_H\n+#define HASHMAP_H\n+\n+/*\n+ * Generic implementation of hash-based key value mappings.\n+ * Supports basic operations get, add/put, remove and iteration.\n+ *\n+ * Also contains a set of ready-to-use hash functions for strings, using the\n+ * FNV-1 algorithm (see http://www.isthe.com/chongo/tech/comp/fnv).\n+ */\n+\n+/*\n+ * Case-sensitive FNV-1 hash of 0-terminated string.\n+ * str: the string\n+ * returns hash code\n+ */\n+extern unsigned int strhash(const char *buf);\n+\n+/*\n+ * Case-insensitive FNV-1 hash of 0-terminated string.\n+ * str: the string\n+ * returns hash code\n+ */\n+extern unsigned int strihash(const char *buf);\n+\n+/*\n+ * Case-sensitive FNV-1 hash of a memory block.\n+ * buf: start of the memory block\n+ * len: length of the memory block\n+ * returns hash code\n+ */\n+extern unsigned int memhash(const void *buf, size_t len);\n+\n+/*\n+ * Case-insensitive FNV-1 hash of a memory block.\n+ * buf: start of the memory block\n+ * len: length of the memory block\n+ * returns hash code\n+ */\n+extern unsigned int memihash(const void *buf, size_t len);\n+\n+/*\n+ * Hashmap entry data structure, must be used as first member of user data\n+ * structures. Consists of a pointer and an int. Ideally it should be followed\n+ * by an int-sized member to prevent unused memory on 64-bit systems due to\n+ * alignment.\n+ */\n+struct hashmap_entry {\n+\tstruct hashmap_entry *next;\n+\tunsigned int hash;\n+};\n+\n+/*\n+ * User-supplied function to test two hashmap entries for equality, shall\n+ * return 0 if the entries are equal. This function is always called with\n+ * non-NULL parameters that have the same hash code. When looking up an entry,\n+ * the key parameter to hashmap_get and hashmap_remove is always passed as\n+ * second argument.\n+ */\n+typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key);\n+\n+/*\n+ * User-supplied function to free a hashmap entry.\n+ */\n+typedef void (*hashmap_free_fn)(void *entry);\n+\n+/*\n+ * Hashmap data structure, use with hashmap_* functions.\n+ */\n+struct hashmap {\n+\tstruct hashmap_entry **table;\n+\thashmap_cmp_fn cmpfn;\n+\tunsigned int size, tablesize;\n+};\n+\n+/*\n+ * Hashmap iterator data structure, use with hasmap_iter_* functions.\n+ */\n+struct hashmap_iter {\n+\tstruct hashmap *map;\n+\tstruct hashmap_entry *next;\n+\tunsigned int tablepos;\n+};\n+\n+/*\n+ * Initializes a hashmap_entry structure.\n+ * entry: pointer to the entry to initialize\n+ * hash: hash code of the entry\n+ * key_only: true if entry is a key-only structure, see hashmap_entry_is_key\n+ */\n+static inline void hashmap_entry_init(void *entry, int hash, int key_only)\n+{\n+\tstruct hashmap_entry *e = entry;\n+\te->hash = hash;\n+\te->next = key_only ? (struct hashmap_entry*) -1 : NULL;\n+}\n+\n+/*\n+ * Checks if hashmap_entry was initialized with the key_only flag. This is\n+ * useful if the entry structure is variable-sized (e.g. ending in a FLEX_ARRAY)\n+ * and the key is part of the variable portion. To prevent dynamic allocation of\n+ * a full-fledged entry structure for each lookup, a smaller, statically sized\n+ * structure can be used as key (i.e. replacing the FLEX_ARRAY member with a\n+ * char pointer). The hashmap_cmp_fn comparison function can then check whether\n+ * entry_or_key is a full-fledged entry or a key-only structure.\n+ * entry: pointer to the entry to check\n+ * returns 0 for key-value entries and non-0 for key-only entries\n+ */\n+static inline int hashmap_entry_is_key(const void *entry)\n+{\n+\tconst struct hashmap_entry *e = entry;\n+\treturn e->next == (struct hashmap_entry*) -1;\n+}\n+\n+/*\n+ * Initializes a hashmap structure.\n+ * map: hashmap to initialize\n+ * equals_function: optional function to test equality of hashmap entries. If\n+ * NULL, entries are considered equal if their hash codes are equal.\n+ * initial_size: optional number of initial entries, 0 if unknown\n+ */\n+extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n+\t\tsize_t initial_size);\n+\n+/*\n+ * Frees a hashmap structure and allocated memory.\n+ * map: hashmap to free\n+ * free_function: optional function to free the hashmap entries\n+ */\n+extern void hashmap_free(struct hashmap *map, hashmap_free_fn free_function);\n+\n+/*\n+ * Returns the hashmap entry for the specified key, or NULL if not found.\n+ * map: the hashmap\n+ * key: key of the entry to look up\n+ * returns matching hashmap entry, or NULL if not found\n+ */\n+extern void *hashmap_get(const struct hashmap *map, const void *key);\n+\n+/*\n+ * Returns the next equal hashmap entry if the map contains duplicates (see\n+ * hashmap_add).\n+ * map: the hashmap\n+ * entry: current entry, obtained via hashmap_get or hashmap_get_next\n+ * returns next equal hashmap entry, or NULL if not found\n+ */\n+extern void *hashmap_get_next(const struct hashmap *map, const void *entry);\n+\n+/*\n+ * Adds a hashmap entry. This allows to add duplicate entries (i.e. separate\n+ * values with the same key according to hashmap_cmp_fn).\n+ * map: the hashmap\n+ * entry: the entry to add\n+ */\n+extern void hashmap_add(struct hashmap *map, void *entry);\n+\n+/*\n+ * Adds or replaces a hashmap entry.\n+ * map: the hashmap\n+ * entry: the entry to add or replace\n+ * returns previous entry, or NULL if the entry is new\n+ */\n+extern void *hashmap_put(struct hashmap *map, void *entry);\n+\n+/*\n+ * Removes a hashmap entry matching the specified key.\n+ * map: the hashmap\n+ * key: key of the entry to remove\n+ * returns removed entry, or NULL if not found\n+ */\n+extern void *hashmap_remove(struct hashmap *map, const void *key);\n+\n+/*\n+ * Initializes a hashmap iterator structure.\n+ * map: the hashmap\n+ * iter: hashmap iterator structure\n+ */\n+extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n+\n+/**\n+ * Returns the next hashmap entry.\n+ * iter: hashmap iterator\n+ * returns next entry, or NULL if there are no more entries\n+ */\n+extern void *hashmap_iter_next(struct hashmap_iter *iter);\n+\n+/**\n+ * Initializes a hashmap iterator and returns the first hashmap entry.\n+ * map: the hashmap\n+ * iter: hashmap iterator\n+ * returns first entry, or NULL if there are no entries\n+ */\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..6c699d5\n--- /dev/null\n+++ b/t/t0011-hashmap.sh\n@@ -0,0 +1,236 @@\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 10)\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+\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..de94c6d\n--- /dev/null\n+++ b/test-hashmap.c\n@@ -0,0 +1,354 @@\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+struct test_key\n+{\n+\tstruct hashmap_entry ent;\n+\tchar *key;\n+};\n+\n+static const char *get_key(const struct test_entry *e)\n+{\n+\treturn hashmap_entry_is_key(e) ? ((struct test_key*) e)->key : e->key;\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)\n+{\n+\treturn strcmp(e1->key, get_key(e2));\n+}\n+\n+static int test_entry_cmp_icase(const struct test_entry *e1,\n+\t\tconst struct test_entry *e2)\n+{\n+\treturn strcasecmp(e1->key, get_key(e2));\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, 0);\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 insert 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], 0);\n+\t\t\t\thashmap_add(&map, entries[i]);\n+\t\t\t}\n+\n+\t\t\thashmap_free(&map, NULL);\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], 0);\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 test_key k;\n+\t\t\t\thashmap_entry_init(&k, hashes[i], 1);\n+\t\t\t\tk.key = entries[i]->key;\n+\t\t\t\thashmap_get(&map, &k);\n+\t\t\t}\n+\t\t}\n+\n+\t\thashmap_free(&map, NULL);\n+\t}\n+}\n+\n+struct hash_entry\n+{\n+\tstruct hash_entry *next;\n+\tchar key[FLEX_ARRAY];\n+};\n+\n+/*\n+ * Test insert 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 test_key key;\n+\t\t\thashmap_entry_init(&key, hash, 1);\n+\t\t\tkey.key = p1;\n+\n+\t\t\t/* lookup entry in hashmap */\n+\t\t\tentry = hashmap_get(&map, &key);\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 test_key key;\n+\t\t\thashmap_entry_init(&key, hash, 1);\n+\t\t\tkey.key = p1;\n+\n+\t\t\t/* remove entry from hashmap */\n+\t\t\tentry = hashmap_remove(&map, &key);\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\", get_key(entry), 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, free);\n+\treturn 0;\n+}\n-- \n1.8.4.5.gef01589.dirty\n"},{"id":"228152","messageId":"524160D0.2010907@gmail.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"[PATCH v2 2/5] buitin/describe.c: use new hash map implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-24T09:52:16Z","receivedAt":"2013-09-24T09:52:16Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \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 7d73722..5db5d89 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@@ -38,7 +38,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,11 @@ static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n };\n \n+static int commit_name_cmp(struct commit_name *cn1, struct commit_name *cn2)\n+{\n+\treturn hashcmp(cn1->peeled, cn2->peeled);\n+}\n+\n static inline unsigned int hash_sha1(const unsigned char *sha1)\n {\n \tunsigned int hash;\n@@ -59,21 +64,10 @@ 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), 0);\n+\thashcpy(key.peeled, peeled);\n+\treturn hashmap_get(&names, &key);\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), 0);\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.4.5.gef01589.dirty\n"},{"id":"228153","messageId":"524160F5.9000103@gmail.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"[PATCH v2 3/5] diffcore-rename.c: move code around to prepare for the next patch","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-24T09:52:53Z","receivedAt":"2013-09-24T09:52:53Z","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 \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.4.5.gef01589.dirty\n"},{"id":"228154","messageId":"5241611E.6090703@gmail.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"[PATCH v2 4/5] diffcore-rename.c: simplify finding exact renames","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-24T09:53:34Z","receivedAt":"2013-09-24T09:53: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 \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..82b7975 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;\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.4.5.gef01589.dirty\n"},{"id":"228155","messageId":"52416141.40907@gmail.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"[PATCH v2 5/5] diffcore-rename.c: use new hash map implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-24T09:54:09Z","receivedAt":"2013-09-24T09:54:09Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees \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 82b7975..2e70d31 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), 0);\n+\tfor (p = hashmap_get(srcs, &dst); 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), 0);\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;\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, free);\n \n \treturn renames;\n }\n-- \n1.8.4.5.gef01589.dirty\n"},{"id":"228157","messageId":"20130924101832.GC25070@paksenarrion.iveqy.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-09-24T10:18:32Z","receivedAt":"2013-09-24T10:18:32Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"On Tue, Sep 24, 2013 at 11:50:16AM +0200, Karsten Blees wrote:\n> Regarding performance, I have to admit that the difference between the two implementations is far greater than I had anticipated. The following times (in seconds) are from Linux x64 (Debian Sarge) on a Core i7 860 @2.8GHz. All tests have been run with 1,000 rounds of 100,000 entries each.\n> \n> The 'get 10% hits' test does 100,000 lookups on a table with 10,000 entries (i.e. 90% unsuccessful lookups).\n> \n> The rows denote different hash functions with different qualities:\n> - FNV: FNV-1 hash on stringified loop counter (i.e. fnv1(itoa(i))), as\n> an example of a high quality / low collision hash\n> - i: just the loop counter (i.e. 0, 1, 2,...), guaranteed collision free\n> - i/10: every 10 entries share the same hash code, lots of collisions\n> \n> The i and i/10 tests show that open addressing suffers badly from clustering, i.e. with adjacent hash codes, it degrades to linear search. The *2 versions provide for some space between used buckets to better compare it to the chaining version.\n> \n> \n> | add | get 100% hits | get 10% hits\n> | hash | hashmap | hash | hashmap | hash | hashmap\n> --------+--------+---------+-------+---------+---------+--------\n> FNV | 14.815 | 2.345 | 3.059 | 1.642 | 4.085 | 0.976\n> FNV x2 | 14.409 | 2.706 | 2.888 | 1.959 | 3.905 | 1.393\n> i | 7.432 | 1.593 | 1.364 | 1.142 | 413.023 | 0.589\n> i x2 | 9.169 | 1.866 | 1.427 | 1.163 | 0.757 | 0.670\n> i/10 | 1.800 | 1.555 | 5.365 | 6.465 | 32.918 | 1.052\n> i/10 x2 | 1.892 | 1.555 | 5.386 | 6.474 | 1.123 | 1.206\n> \n> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n> \n\nSo I did this improved hash implementation a few months back. Although I\ncould do a test like this and see an improvement, I failed to see an\nimprovement in actual git usage.\n\nHopefully it was just me doing something wrong, but I abandonned the\nidea of a better hashmap since I couldn't see any major performance\nboost using git and the current implementation is really simple and easy\nto maintain.\n\nSo my question to you is, does your hashmap speed up git? And does it\nspeed it up enough to justify that your implementation is the double\namount of code than the current?\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n"},{"id":"228161","messageId":"CALUzUxqX=zgkQg84jYQABKa=Lq=7BUee6824H+Xfye4XBnUZqA@mail.gmail.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2013-09-24T11:16:10Z","receivedAt":"2013-09-24T11:16:10Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Hi Karsten,\n\nOn Tue, Sep 24, 2013 at 5:50 PM, Karsten Blees wrote:\n>\n> | add | get 100% hits | get 10% hits\n> | hash | hashmap | hash | hashmap | hash | hashmap\n> --------+--------+---------+-------+---------+---------+--------\n> FNV | 14.815 | 2.345 | 3.059 | 1.642 | 4.085 | 0.976\n> FNV x2 | 14.409 | 2.706 | 2.888 | 1.959 | 3.905 | 1.393\n> i | 7.432 | 1.593 | 1.364 | 1.142 | 413.023 | 0.589\n> i x2 | 9.169 | 1.866 | 1.427 | 1.163 | 0.757 | 0.670\n> i/10 | 1.800 | 1.555 | 5.365 | 6.465 | 32.918 | 1.052\n> i/10 x2 | 1.892 | 1.555 | 5.386 | 6.474 | 1.123 | 1.206\n>\n> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n\nI'm not sure if I'm reading the numbers right, but they look impressive!\n\nIf it's not too much trouble, could you put together an API document,\nalong the lines of Documentation/technical/api-hash.txt? I could give\na stab at replacing patience and histogram diff's hash implementation\nwith yours.\n\n-- \nCheers,\nRay Chuan\n"},{"id":"228270","messageId":"20130926101648.GD6615@paksenarrion.iveqy.com","threadId":"34904","inReplyTo":"52416058.90008@gmail.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-09-26T10:16:48Z","receivedAt":"2013-09-26T10:16:48Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"On Tue, Sep 24, 2013 at 11:50:16AM +0200, Karsten Blees wrote:\n> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n\nSo I'm still curious about the actual performance improvements for git.\nI runned git describe on the linux kernel with both the old hashmap and\nthis new one:\n\nWith old hashmap\n================\niveqy@minilla:/srv/slask/linux$ time ../git/git describe\nv3.12-rc2-83-g4b97280\n\nreal 0m0.236s\nuser 0m0.216s\nsys 0m0.020s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe\nv3.12-rc2-83-g4b97280\n\nreal 0m0.236s\nuser 0m0.220s\nsys 0m0.016s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe\nv3.12-rc2-83-g4b97280\n\nreal 0m0.236s\nuser 0m0.212s\nsys 0m0.024s\n\nWith new hashmap\n================\niveqy@minilla:/srv/slask/linux$ time ../git/git describe\nv3.12-rc2-83-g4b97280\n\nreal 0m0.236s\nuser 0m0.216s\nsys 0m0.020s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe\nv3.12-rc2-83-g4b97280\n\nreal 0m0.235s\nuser 0m0.216s\nsys 0m0.020s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe\nv3.12-rc2-83-g4b97280\n\nreal 0m0.235s\nuser 0m0.208s\nsys 0m0.028s\n\n\nI can't see any improvements at all here. What do I miss? Am I running\ngit describe in the wrong way? Does linux.git have too few tags to be\nimportant?\n\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n"},{"id":"228272","messageId":"CACsJy8BQDwHJiDyaOfcmOSg+=jpj-NyCTtw1vLwppSwYxF5hhA@mail.gmail.com","threadId":"34904","inReplyTo":"20130926101648.GD6615@paksenarrion.iveqy.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-26T10:26:27Z","receivedAt":"2013-09-26T10:26:27Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 26, 2013 at 5:16 PM, Fredrik Gustafsson wrote:\n> On Tue, Sep 24, 2013 at 11:50:16AM +0200, Karsten Blees wrote:\n>> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n>\n> So I'm still curious about the actual performance improvements for git.\n> I runned git describe on the linux kernel with both the old hashmap and\n> this new one:\n>\n> ...\n>\n> I can't see any improvements at all here. What do I miss? Am I running\n> git describe in the wrong way? Does linux.git have too few tags to be\n> important?\n\nI wonder if it makes any difference if there are a lot more refs. I\nhear gerrit creates a lot but don't know how many. linux-2.6 has ~350\nrefs. How about increasing the number of refs to 3500 refs?\n-- \nDuy\n"},{"id":"228273","messageId":"20130926110818.GE6615@paksenarrion.iveqy.com","threadId":"34904","inReplyTo":"CACsJy8BQDwHJiDyaOfcmOSg+=jpj-NyCTtw1vLwppSwYxF5hhA@mail.gmail.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Fredrik Gustafsson","fromEmail":"iveqy@iveqy.com","sentAt":"2013-09-26T11:08:18Z","receivedAt":"2013-09-26T11:08:18Z","isPatch":true,"sender":{"key":"iveqy@iveqy.com","avatar":"https://avatars.githubusercontent.com/u/761743?v=4"},"body":"On Thu, Sep 26, 2013 at 05:26:27PM +0700, Duy Nguyen wrote:\n> On Thu, Sep 26, 2013 at 5:16 PM, Fredrik Gustafsson wrote:\n> > On Tue, Sep 24, 2013 at 11:50:16AM +0200, Karsten Blees wrote:\n> >> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n> >\n> > So I'm still curious about the actual performance improvements for git.\n> > I runned git describe on the linux kernel with both the old hashmap and\n> > this new one:\n> >\n> > ...\n> >\n> > I can't see any improvements at all here. What do I miss? Am I running\n> > git describe in the wrong way? Does linux.git have too few tags to be\n> > important?\n> \n> I wonder if it makes any difference if there are a lot more refs. I\n> hear gerrit creates a lot but don't know how many. linux-2.6 has ~350\n> refs. How about increasing the number of refs to 3500 refs?\n\nSo I runned:\nfor i in $(git rev-list HEAD ); do git tag \"tag$i\" $i ; done\n\nin my linux repo and aborted it after a while:\niveqy@minilla:/srv/slask/linux$ git tag | wc -l\n9323\n\nSo it's a few at least. Not sure how those artificial tagnames would\nhurt or improve the performance.\n\nOld hashtable\n=============\niveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD \nv3.12-rc2-83-g4b97280\n\nreal 0m0.384s\nuser 0m0.288s\nsys 0m0.092s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD \nv3.12-rc2-83-g4b97280\n\nreal 0m0.383s\nuser 0m0.284s\nsys 0m0.100s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD \nv3.12-rc2-83-g4b97280\n\nreal 0m0.386s\nuser 0m0.312s\nsys 0m0.072s\n\n\nNew hashtable\n=============\niveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD \nv3.12-rc2-83-g4b97280\n\nreal 0m0.382s\nuser 0m0.300s\nsys 0m0.084s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD \nv3.12-rc2-83-g4b97280\n\nreal 0m0.382s\nuser 0m0.288s\nsys 0m0.092s\niveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD \nv3.12-rc2-83-g4b97280\n\nreal 0m0.384s\nuser 0m0.296s\nsys 0m0.088s\n\n\n-- \nMed vänliga hälsningar\nFredrik Gustafsson\n\ntel: 0733-608274\ne-post: iveqy@iveqy.com\n"},{"id":"228274","messageId":"CACsJy8C_Rr=2tsi_8TmGnHy85qBND1tNby7Nou4O4eqFTOBzgg@mail.gmail.com","threadId":"34904","inReplyTo":"20130926110818.GE6615@paksenarrion.iveqy.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-26T11:14:20Z","receivedAt":"2013-09-26T11:14:20Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 26, 2013 at 6:08 PM, Fredrik Gustafsson wrote:\n> On Thu, Sep 26, 2013 at 05:26:27PM +0700, Duy Nguyen wrote:\n>> On Thu, Sep 26, 2013 at 5:16 PM, Fredrik Gustafsson wrote:\n>> > On Tue, Sep 24, 2013 at 11:50:16AM +0200, Karsten Blees wrote:\n>> >> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n>> >\n>> > So I'm still curious about the actual performance improvements for git.\n>> > I runned git describe on the linux kernel with both the old hashmap and\n>> > this new one:\n>> >\n>> > ...\n>> >\n>> > I can't see any improvements at all here. What do I miss? Am I running\n>> > git describe in the wrong way? Does linux.git have too few tags to be\n>> > important?\n>>\n>> I wonder if it makes any difference if there are a lot more refs. I\n>> hear gerrit creates a lot but don't know how many. linux-2.6 has ~350\n>> refs. How about increasing the number of refs to 3500 refs?\n>\n> So I runned:\n> for i in $(git rev-list HEAD ); do git tag \"tag$i\" $i ; done\n>\n> in my linux repo and aborted it after a while:\n> iveqy@minilla:/srv/slask/linux$ git tag | wc -l\n> 9323\n>\n> So it's a few at least. Not sure how those artificial tagnames would\n> hurt or improve the performance.\n>\n> Old hashtable\n> =============\n> iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD\n> v3.12-rc2-83-g4b97280\n>\n> real 0m0.384s\n> user 0m0.288s\n> sys 0m0.092s\n> iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD\n> v3.12-rc2-83-g4b97280\n>\n> real 0m0.383s\n> user 0m0.284s\n> sys 0m0.100s\n> iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD\n> v3.12-rc2-83-g4b97280\n>\n> real 0m0.386s\n> user 0m0.312s\n> sys 0m0.072s\n>\n>\n> New hashtable\n> =============\n> iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD\n> v3.12-rc2-83-g4b97280\n>\n> real 0m0.382s\n> user 0m0.300s\n> sys 0m0.084s\n> iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD\n> v3.12-rc2-83-g4b97280\n>\n> real 0m0.382s\n> user 0m0.288s\n> sys 0m0.092s\n> iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD\n> v3.12-rc2-83-g4b97280\n>\n> real 0m0.384s\n> user 0m0.296s\n> sys 0m0.088s\n\nOK I have to say I don't see any justification for more code then.\n-- \nDuy\n"},{"id":"228277","messageId":"52443CE8.6000902@gmail.com","threadId":"34904","inReplyTo":"20130926101648.GD6615@paksenarrion.iveqy.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-26T13:55:52Z","receivedAt":"2013-09-26T13:55:52Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 26.09.2013 12:16, schrieb Fredrik Gustafsson:\n> On Tue, Sep 24, 2013 at 11:50:16AM +0200, Karsten Blees wrote:\n>> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n> \n> So I'm still curious about the actual performance improvements for git.\n> I runned git describe on the linux kernel with both the old hashmap and\n> this new one:\n> \n\nPerformance was never the primary issue, the intention of the performance tests was to ensure that the new implementation doesn't *slow down* git.\n\n>From the original PATCH/RFC:\n- O(1) remove\n- builtin entry chaining\n- ready-to-use FNV-1 hash functions\n- unit test\n- additions are ~twice as fast\n- uses less memory\n\nSo, the new implementation allows us to get rid of workarounds such as the CE_UNHASHED flag, duplicate entry chaining code and hash_name() implementations. It also addresses the memory usage FIXME in hash.h.\n\nThe simplified API may help prevent bugs such as the broken entry chaining in name-hash.c (see commits 2548183, 395c735, 2092678).\n\nMaybe we can also replace some of the custom hash table implementations in attr.c, decorate.c, fast-import.c and object.c (to name just a few...).\n"},{"id":"228278","messageId":"524446D4.3010006@gmail.com","threadId":"34904","inReplyTo":"CALUzUxqX=zgkQg84jYQABKa=Lq=7BUee6824H+Xfye4XBnUZqA@mail.gmail.com","subject":"Re: [PATCH v2 0/5] New hash table implementation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-09-26T14:38:12Z","receivedAt":"2013-09-26T14:38:12Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 24.09.2013 13:16, schrieb Tay Ray Chuan:\n> Hi Karsten,\n> \n> On Tue, Sep 24, 2013 at 5:50 PM, Karsten Blees wrote:\n>>\n>> | add | get 100% hits | get 10% hits\n>> | hash | hashmap | hash | hashmap | hash | hashmap\n>> --------+--------+---------+-------+---------+---------+--------\n>> FNV | 14.815 | 2.345 | 3.059 | 1.642 | 4.085 | 0.976\n>> FNV x2 | 14.409 | 2.706 | 2.888 | 1.959 | 3.905 | 1.393\n>> i | 7.432 | 1.593 | 1.364 | 1.142 | 413.023 | 0.589\n>> i x2 | 9.169 | 1.866 | 1.427 | 1.163 | 0.757 | 0.670\n>> i/10 | 1.800 | 1.555 | 5.365 | 6.465 | 32.918 | 1.052\n>> i/10 x2 | 1.892 | 1.555 | 5.386 | 6.474 | 1.123 | 1.206\n>>\n>> Tests can be reproduced with 'time echo \"perfhash[map] 1000\" | ./test-hashmap', see test-hashmap.c for definition of method flags.\n> \n> I'm not sure if I'm reading the numbers right, but they look impressive!\n> \n\nThe numbers are for 100 million additions / lookups (1,000 rounds á 100,000 entries). Considering everything else that happens in git, the hash table performance should be insignificant, though.\n\n> If it's not too much trouble, could you put together an API document,\n> along the lines of Documentation/technical/api-hash.txt?\n\nYes, I had already planned to port the documentation to asciidoc. Although in my experience, API documentation in the header file tends to better stay in sync with code changes (but this only makes real sense with extraction tools such as doxygen).\n\n> I could give\n> a stab at replacing patience and histogram diff's hash implementation\n> with yours.\n> \n\nOpen addressing (i.e. distributing conflicting entries to other buckes) *may* be faster *if* all data fits into the table (i.e. no pointers to the data are used). Scanning such a table (without following pointers) has very high locality and thus may benefit from accessing fewer CPU cache lines. The patience implementation seems to fall into this category (although the entry struct is fairly large, and it also uses the *2 trick to defeat bad hash codes (which wouldn't be necessary with chaining)).\n\nBoth patience and histogram use preallocated, fixed-size hash tables, and thus won't benefit from faster inserts (the 'add' performance numbers are for dynamically resized hash tables).\n\nSo, converting patience/histogram is probably not worth the trouble for performance reasons alone. If it also simplifies the algorithms and/or reduces memory usage - fine.\n\nCiao,\nKarsten\n"}]}