{"thread":{"id":"37047","subject":"[PATCH v1 0/4] hashmap improvements","startedAt":"2014-07-02T22:18:40Z","lastAt":"2014-07-11T22:21:37Z","messageCount":12,"participants":["Karsten Blees","Matthieu Moy","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"245357","messageId":"53B48540.5070600@gmail.com","threadId":"37047","inReplyTo":null,"subject":"[PATCH v1 0/4] hashmap improvements","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-02T22:18:40Z","receivedAt":"2014-07-02T22:18:40Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Here are a few small hashmap improvements, partly resulting from recent\ndiscussion of the config-cache topic.\n\nKarsten Blees (4):\n  hashmap: factor out getting an int hash code from a SHA1\n  hashmap: improve struct hashmap member documentation\n  hashmap: add simplified hashmap_get_from_hash() API\n  hashmap: add string interning API\n\n Documentation/technical/api-hashmap.txt | 54 ++++++++++++++++++++++++++++++---\n builtin/describe.c                      | 13 ++------\n decorate.c                              |  5 +--\n diffcore-rename.c                       | 11 +++----\n hashmap.c                               | 38 +++++++++++++++++++++++\n hashmap.h                               | 27 +++++++++++++++++\n khash.h                                 | 11 ++-----\n name-hash.c                             |  5 ++-\n object.c                                | 13 +-------\n pack-objects.c                          |  5 ++-\n t/t0011-hashmap.sh                      | 13 ++++++++\n test-hashmap.c                          | 25 ++++++++++-----\n 12 files changed, 159 insertions(+), 61 deletions(-)\n\n-- \n1.9.4.msysgit.0.dirty\n"},{"id":"245359","messageId":"53B485A4.20609@gmail.com","threadId":"37047","inReplyTo":"53B48540.5070600@gmail.com","subject":"[PATCH v1 1/4] hashmap: factor out getting an int hash code from a, SHA1","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-02T22:20:20Z","receivedAt":"2014-07-02T22:20:20Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Copying the first bytes of a SHA1 is duplicated in six places, however,\nthe implications (wrong byte order on little-endian systems) is documented\nonly once.\n\nAdd a properly documented API for this.\n\nSigned-off-by: Karsten Blees <blees@dcon.de>\n---\n Documentation/technical/api-hashmap.txt |  9 +++++++++\n builtin/describe.c                      | 11 ++---------\n decorate.c                              |  5 +----\n diffcore-rename.c                       |  4 +---\n hashmap.h                               | 11 +++++++++++\n khash.h                                 | 11 ++---------\n object.c                                | 13 +------------\n pack-objects.c                          |  5 ++---\n 8 files changed, 29 insertions(+), 40 deletions(-)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex b977ae8..4689968 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -58,6 +58,15 @@ Functions\n +\n `strihash` and `memihash` are case insensitive versions.\n \n+`unsigned int sha1hash(const unsigned char *sha1)`::\n+\n+\tConverts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n+\tfor use in hash tables. Cryptographic hashes are supposed to have\n+\tuniform distribution, so in contrast to `memhash()`, this just copies\n+\tthe first `sizeof(int)` bytes without shuffling any bits. Note that\n+\tthe results will be different on big-endian and little-endian\n+\tplatforms, so they should not be stored or transferred over the net!\n+\n `void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`::\n \n \tInitializes a hashmap structure.\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 24d740c..57e84c8 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -56,17 +56,10 @@ static int commit_name_cmp(const struct commit_name *cn1,\n \treturn hashcmp(cn1->peeled, peeled ? peeled : cn2->peeled);\n }\n \n-static inline unsigned int hash_sha1(const unsigned char *sha1)\n-{\n-\tunsigned int hash;\n-\tmemcpy(&hash, sha1, sizeof(hash));\n-\treturn hash;\n-}\n-\n static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n {\n \tstruct commit_name key;\n-\thashmap_entry_init(&key, hash_sha1(peeled));\n+\thashmap_entry_init(&key, sha1hash(peeled));\n \treturn hashmap_get(&names, &key, peeled);\n }\n \n@@ -114,7 +107,7 @@ static void add_to_known_names(const char *path,\n \t\tif (!e) {\n \t\t\te = xmalloc(sizeof(struct commit_name));\n \t\t\thashcpy(e->peeled, peeled);\n-\t\t\thashmap_entry_init(e, hash_sha1(peeled));\n+\t\t\thashmap_entry_init(e, sha1hash(peeled));\n \t\t\thashmap_add(&names, e);\n \t\t\te->path = NULL;\n \t\t}\ndiff --git a/decorate.c b/decorate.c\nindex 7cb5d29..b2aac90 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -8,10 +8,7 @@\n \n static unsigned int hash_obj(const struct object *obj, unsigned int n)\n {\n-\tunsigned int hash;\n-\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n+\treturn sha1hash(obj->sha1) % n;\n }\n \n static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 749a35d..6fa97d4 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -242,14 +242,12 @@ struct file_similarity {\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+\treturn sha1hash(filespec->sha1);\n }\n \n static int find_identical_files(struct hashmap *srcs,\ndiff --git a/hashmap.h b/hashmap.h\nindex a816ad4..ed5425a 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -13,6 +13,17 @@ extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n extern unsigned int memihash(const void *buf, size_t len);\n \n+static inline unsigned int sha1hash(const unsigned char *sha1)\n+{\n+\t/*\n+\t * Equivalent to 'return *(int *)sha1;', but safe on platforms that\n+\t * don't support unaligned reads.\n+\t */\n+\tunsigned int hash;\n+\tmemcpy(&hash, sha1, sizeof(hash));\n+\treturn hash;\n+}\n+\n /* data structures */\n \n struct hashmap_entry {\ndiff --git a/khash.h b/khash.h\nindex 57ff603..06c7906 100644\n--- a/khash.h\n+++ b/khash.h\n@@ -320,19 +320,12 @@ static const double __ac_HASH_UPPER = 0.77;\n \t\tcode;\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t} }\n \n-static inline khint_t __kh_oid_hash(const unsigned char *oid)\n-{\n-\tkhint_t hash;\n-\tmemcpy(&hash, oid, sizeof(hash));\n-\treturn hash;\n-}\n-\n #define __kh_oid_cmp(a, b) (hashcmp(a, b) == 0)\n \n-KHASH_INIT(sha1, const unsigned char *, void *, 1, __kh_oid_hash, __kh_oid_cmp)\n+KHASH_INIT(sha1, const unsigned char *, void *, 1, sha1hash, __kh_oid_cmp)\n typedef kh_sha1_t khash_sha1;\n \n-KHASH_INIT(sha1_pos, const unsigned char *, int, 1, __kh_oid_hash, __kh_oid_cmp)\n+KHASH_INIT(sha1_pos, const unsigned char *, int, 1, sha1hash, __kh_oid_cmp)\n typedef kh_sha1_pos_t khash_sha1_pos;\n \n #endif /* __AC_KHASH_H */\ndiff --git a/object.c b/object.c\nindex 57a0890..73acaea 100644\n--- a/object.c\n+++ b/object.c\n@@ -50,18 +50,7 @@ int type_from_string(const char *str)\n  */\n static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)\n {\n-\tunsigned int hash;\n-\n-\t/*\n-\t * Since the sha1 is essentially random, we just take the\n-\t * required number of bits directly from the first\n-\t * sizeof(unsigned int) bytes of sha1.  First we have to copy\n-\t * the bytes into a properly aligned integer.  If we cared\n-\t * about getting consistent results across architectures, we\n-\t * would have to call ntohl() here, too.\n-\t */\n-\tmemcpy(&hash, sha1, sizeof(unsigned int));\n-\treturn hash & (n - 1);\n+\treturn sha1hash(sha1) & (n - 1);\n }\n \n /*\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 4f36c32..9992f3e 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -7,10 +7,9 @@ static uint32_t locate_object_entry_hash(struct packing_data *pdata,\n \t\t\t\t\t const unsigned char *sha1,\n \t\t\t\t\t int *found)\n {\n-\tuint32_t i, hash, mask = (pdata->index_size - 1);\n+\tuint32_t i, mask = (pdata->index_size - 1);\n \n-\tmemcpy(&hash, sha1, sizeof(uint32_t));\n-\ti = hash & mask;\n+\ti = sha1hash(sha1) & mask;\n \n \twhile (pdata->index[i] > 0) {\n \t\tuint32_t pos = pdata->index[i] - 1;\n-- \n1.9.4.msysgit.0.dirty\n"},{"id":"245360","messageId":"53B485E1.1070701@gmail.com","threadId":"37047","inReplyTo":"53B48540.5070600@gmail.com","subject":"[PATCH v1 2/4] hashmap: improve struct hashmap member documentation","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-02T22:21:21Z","receivedAt":"2014-07-02T22:21:21Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Signed-off-by: Karsten Blees <blees@dcon.de>\n---\n Documentation/technical/api-hashmap.txt | 16 ++++++++++++----\n 1 file changed, 12 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex 4689968..dc21a7c 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -8,11 +8,19 @@ Data Structures\n \n `struct hashmap`::\n \n-\tThe hash table structure.\n+\tThe hash table structure. Members can be used as follows, but should\n+\tnot be modified directly:\n +\n-The `size` member keeps track of the total number of entries. The `cmpfn`\n-member is a function used to compare two entries for equality. The `table` and\n-`tablesize` members store the hash table and its size, respectively.\n+The `size` member keeps track of the total number of entries (0 means the\n+hashmap is empty).\n++\n+`tablesize` is the allocated size of the hash table. A non-0 value indicates\n+that the hashmap is initialized. It may also be useful for statistical purposes\n+(i.e. `size / tablesize` is the current load factor).\n++\n+`cmpfn` stores the comparison function specified in `hashmap_init()`. In\n+advanced scenarios, it may be useful to change this, e.g. to switch between\n+case-sensitive and case-insensitive lookup.\n \n `struct hashmap_entry`::\n \n-- \n1.9.4.msysgit.0.dirty\n"},{"id":"245361","messageId":"53B48613.60509@gmail.com","threadId":"37047","inReplyTo":"53B48540.5070600@gmail.com","subject":"[PATCH v1 3/4] hashmap: add simplified hashmap_get_from_hash() API","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-02T22:22:11Z","receivedAt":"2014-07-02T22:22:11Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Hashmap entries are typically looked up by just a key. The hashmap_get()\nAPI expects an initialized entry structure instead, to support compound\nkeys. This flexibility is currently only needed by find_dir_entry() in\nname-hash.c (and compat/win32/fscache.c in the msysgit fork). All other\n(currently five) call sites of hashmap_get() have to set up a near emtpy\nentry structure, resulting in duplicate code like this:\n\n  struct hashmap_entry keyentry;\n  hashmap_entry_init(&keyentry, hash(key));\n  return hashmap_get(map, &keyentry, key);\n\nAdd a hashmap_get_from_hash() API that allows hashmap lookups by just\nspecifying the key and its hash code, i.e.:\n\n  return hashmap_get_from_hash(map, hash(key), key);\n\nSigned-off-by: Karsten Blees <blees@dcon.de>\n---\n Documentation/technical/api-hashmap.txt | 14 ++++++++++++++\n builtin/describe.c                      |  4 +---\n diffcore-rename.c                       |  7 +++----\n hashmap.h                               |  8 ++++++++\n name-hash.c                             |  5 ++---\n test-hashmap.c                          | 11 +++--------\n 6 files changed, 31 insertions(+), 18 deletions(-)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex dc21a7c..f9215d6 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -118,6 +118,20 @@ hashmap_entry) that has at least been initialized with the proper hash code\n If an entry with matching hash code is found, `key` and `keydata` are passed\n to `hashmap_cmp_fn` to decide whether the entry matches the key.\n \n+`void *hashmap_get_from_hash(const struct hashmap *map, unsigned int hash, const void *keydata)`::\n+\n+\tReturns the hashmap entry for the specified hash code and key data,\n+\tor NULL if not found.\n++\n+`map` is the hashmap structure.\n++\n+`hash` is the hash code of the entry to look up.\n++\n+If an entry with matching hash code is found, `keydata` is passed to\n+`hashmap_cmp_fn` to decide whether the entry matches the key. The\n+`entry_or_key` parameter points to a bogus hashmap_entry structure that\n+should not be used in the comparison.\n+\n `void *hashmap_get_next(const struct hashmap *map, const void *entry)`::\n \n \tReturns the next equal hashmap entry, or NULL if not found. This can be\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 57e84c8..ee6a3b9 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -58,9 +58,7 @@ static int commit_name_cmp(const struct commit_name *cn1,\n \n static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n {\n-\tstruct commit_name key;\n-\thashmap_entry_init(&key, sha1hash(peeled));\n-\treturn hashmap_get(&names, &key, peeled);\n+\treturn hashmap_get_from_hash(&names, sha1hash(peeled), peeled);\n }\n \n static int replace_name(struct commit_name *e,\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6fa97d4..2e44a37 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -257,15 +257,14 @@ static int find_identical_files(struct hashmap *srcs,\n \tint renames = 0;\n \n \tstruct diff_filespec *target = rename_dst[dst_index].two;\n-\tstruct file_similarity *p, *best, dst;\n+\tstruct file_similarity *p, *best = NULL;\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-\thashmap_entry_init(&dst, hash_filespec(target));\n-\tfor (p = hashmap_get(srcs, &dst, NULL); p; p = hashmap_get_next(srcs, p)) {\n+\tp = hashmap_get_from_hash(srcs, hash_filespec(target), NULL);\n+\tfor (; p; p = hashmap_get_next(srcs, p)) {\n \t\tint score;\n \t\tstruct diff_filespec *source = p->filespec;\n \ndiff --git a/hashmap.h b/hashmap.h\nindex ed5425a..12f0668 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -68,6 +68,14 @@ extern void *hashmap_put(struct hashmap *map, void *entry);\n extern void *hashmap_remove(struct hashmap *map, const void *key,\n \t\tconst void *keydata);\n \n+static inline void *hashmap_get_from_hash(const struct hashmap *map,\n+\t\tunsigned int hash, const void *keydata)\n+{\n+\tstruct hashmap_entry key;\n+\thashmap_entry_init(&key, hash);\n+\treturn hashmap_get(map, &key, keydata);\n+}\n+\n /* hashmap_iter functions */\n \n extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\ndiff --git a/name-hash.c b/name-hash.c\nindex 49fd508..702cd05 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -213,12 +213,11 @@ struct cache_entry *index_dir_exists(struct index_state *istate, const char *nam\n struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)\n {\n \tstruct cache_entry *ce;\n-\tstruct hashmap_entry key;\n \n \tlazy_init_name_hash(istate);\n \n-\thashmap_entry_init(&key, memihash(name, namelen));\n-\tce = hashmap_get(&istate->name_hash, &key, NULL);\n+\tce = hashmap_get_from_hash(&istate->name_hash,\n+\t\t\t\t   memihash(name, namelen), NULL);\n \twhile (ce) {\n \t\tif (same_name(ce, name, namelen, icase))\n \t\t\treturn ce;\ndiff --git a/test-hashmap.c b/test-hashmap.c\nindex f5183fb..3c9f67b 100644\n--- a/test-hashmap.c\n+++ b/test-hashmap.c\n@@ -115,9 +115,8 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\n \n \t\tfor (j = 0; j < rounds; j++) {\n \t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n-\t\t\t\tstruct hashmap_entry key;\n-\t\t\t\thashmap_entry_init(&key, hashes[i]);\n-\t\t\t\thashmap_get(&map, &key, entries[i]->key);\n+\t\t\t\thashmap_get_from_hash(&map, hashes[i],\n+\t\t\t\t\t\t      entries[i]->key);\n \t\t\t}\n \t\t}\n \n@@ -199,12 +198,8 @@ int main(int argc, char *argv[])\n \n \t\t} else if (!strcmp(\"get\", cmd) && l1) {\n \n-\t\t\t/* setup static key */\n-\t\t\tstruct hashmap_entry key;\n-\t\t\thashmap_entry_init(&key, hash);\n-\n \t\t\t/* lookup entry in hashmap */\n-\t\t\tentry = hashmap_get(&map, &key, p1);\n+\t\t\tentry = hashmap_get_from_hash(&map, hash, p1);\n \n \t\t\t/* print result */\n \t\t\tif (!entry)\n-- \n1.9.4.msysgit.0.dirty\n"},{"id":"245362","messageId":"53B4863E.1020701@gmail.com","threadId":"37047","inReplyTo":"53B48540.5070600@gmail.com","subject":"[PATCH v1 4/4] hashmap: add string interning API","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-02T22:22:54Z","receivedAt":"2014-07-02T22:22:54Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Interning short strings with high probability of duplicates can reduce the\nmemory footprint and speed up comparisons.\n\nAdd strintern() and memintern() APIs that use a hashmap to manage the pool\nof unique, interned strings.\n\nNote: strintern(getenv()) could be used to sanitize git's use of getenv(),\nin case we ever encounter a platform where a call to getenv() invalidates\nprevious getenv() results (which is allowed by POSIX).\n\nSigned-off-by: Karsten Blees <blees@dcon.de>\n---\n Documentation/technical/api-hashmap.txt | 15 +++++++++++++\n hashmap.c                               | 38 +++++++++++++++++++++++++++++++++\n hashmap.h                               |  8 +++++++\n t/t0011-hashmap.sh                      | 13 +++++++++++\n test-hashmap.c                          | 14 ++++++++++++\n 5 files changed, 88 insertions(+)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex f9215d6..00c4c29 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -193,6 +193,21 @@ more entries.\n `hashmap_iter_first` is a combination of both (i.e. initializes the iterator\n and returns the first entry, if any).\n \n+`const char *strintern(const char *string)`::\n+`const void *memintern(const void *data, size_t len)`::\n+\n+\tReturns the unique, interned version of the specified string or data,\n+\tsimilar to the `String.intern` API in Java and .NET, respectively.\n+\tInterned strings remain valid for the entire lifetime of the process.\n++\n+Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned\n+strings / data must not be modified or freed.\n++\n+Interned strings are best used for short strings with high probability of\n+duplicates.\n++\n+Uses a hashmap to store the pool of interned strings.\n+\n Usage example\n -------------\n \ndiff --git a/hashmap.c b/hashmap.c\nindex d1b8056..f693839 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -226,3 +226,41 @@ void *hashmap_iter_next(struct hashmap_iter *iter)\n \t\tcurrent = iter->map->table[iter->tablepos++];\n \t}\n }\n+\n+struct pool_entry {\n+\tstruct hashmap_entry ent;\n+\tsize_t len;\n+\tunsigned char data[FLEX_ARRAY];\n+};\n+\n+static int pool_entry_cmp(const struct pool_entry *e1,\n+\t\t\t  const struct pool_entry *e2,\n+\t\t\t  const unsigned char *keydata)\n+{\n+\treturn e1->data != keydata &&\n+\t       (e1->len != e2->len || memcmp(e1->data, keydata, e1->len));\n+}\n+\n+const void *memintern(const void *data, size_t len)\n+{\n+\tstatic struct hashmap map;\n+\tstruct pool_entry key, *e;\n+\n+\t/* initialize string pool hashmap */\n+\tif (!map.tablesize)\n+\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, 0);\n+\n+\t/* lookup interned string in pool */\n+\thashmap_entry_init(&key, memhash(data, len));\n+\tkey.len = len;\n+\te = hashmap_get(&map, &key, data);\n+\tif (!e) {\n+\t\t/* not found: create it */\n+\t\te = xmallocz(sizeof(struct pool_entry) + len);\n+\t\thashmap_entry_init(e, key.ent.hash);\n+\t\te->len = len;\n+\t\tmemcpy(e->data, data, len);\n+\t\thashmap_add(&map, e);\n+\t}\n+\treturn e->data;\n+}\ndiff --git a/hashmap.h b/hashmap.h\nindex 12f0668..507884b 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -87,4 +87,12 @@ static inline void *hashmap_iter_first(struct hashmap *map,\n \treturn hashmap_iter_next(iter);\n }\n \n+/* string interning */\n+\n+extern const void *memintern(const void *data, size_t len);\n+static inline const char *strintern(const char *string)\n+{\n+\treturn memintern(string, strlen(string));\n+}\n+\n #endif\ndiff --git a/t/t0011-hashmap.sh b/t/t0011-hashmap.sh\nindex 391e2b6..f97c805 100755\n--- a/t/t0011-hashmap.sh\n+++ b/t/t0011-hashmap.sh\n@@ -237,4 +237,17 @@ test_expect_success 'grow / shrink' '\n \n '\n \n+test_expect_success 'string interning' '\n+\n+test_hashmap \"intern value1\n+intern Value1\n+intern value2\n+intern value2\n+\" \"value1\n+Value1\n+value2\n+value2\"\n+\n+'\n+\n test_done\ndiff --git a/test-hashmap.c b/test-hashmap.c\nindex 3c9f67b..07aa7ec 100644\n--- a/test-hashmap.c\n+++ b/test-hashmap.c\n@@ -234,6 +234,20 @@ int main(int argc, char *argv[])\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(\"intern\", cmd) && l1) {\n+\n+\t\t\t/* test that strintern works */\n+\t\t\tconst char *i1 = strintern(p1);\n+\t\t\tconst char *i2 = strintern(p1);\n+\t\t\tif (strcmp(i1, p1))\n+\t\t\t\tprintf(\"strintern(%s) returns %s\\n\", p1, i1);\n+\t\t\telse if (i1 == p1)\n+\t\t\t\tprintf(\"strintern(%s) returns input pointer\\n\", p1);\n+\t\t\telse if (i1 != i2)\n+\t\t\t\tprintf(\"strintern(%s) != strintern(%s)\", i1, i2);\n+\t\t\telse\n+\t\t\t\tprintf(\"%s\\n\", i1);\n+\n \t\t} else if (!strcmp(\"perfhashmap\", cmd) && l1 && l2) {\n \n \t\t\tperf_hashmap(atoi(p1), atoi(p2));\n-- \n1.9.4.msysgit.0.dirty\n"},{"id":"245368","messageId":"vpqpphmc3em.fsf@anie.imag.fr","threadId":"37047","inReplyTo":"53B4863E.1020701@gmail.com","subject":"Re: [PATCH v1 4/4] hashmap: add string interning API","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2014-07-03T07:22:41Z","receivedAt":"2014-07-03T07:22:41Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> --- a/t/t0011-hashmap.sh\n> +++ b/t/t0011-hashmap.sh\n> @@ -237,4 +237,17 @@ test_expect_success 'grow / shrink' '\n>  \n>  '\n>  \n> +test_expect_success 'string interning' '\n> +\n> +test_hashmap \"intern value1\n> +intern Value1\n> +intern value2\n> +intern value2\n> +\" \"value1\n> +Value1\n> +value2\n> +value2\"\n> +\n> +'\n\nIndentation is broken here, but it's consistant with the current style\nof the file. You may want a \"modernize style\" patch before yours and\nthen indent properly, but that shouldn't block inclusion.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"245369","messageId":"vpqk37uc3dn.fsf@anie.imag.fr","threadId":"37047","inReplyTo":"53B48540.5070600@gmail.com","subject":"Re: [PATCH v1 0/4] hashmap improvements","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2014-07-03T07:23:16Z","receivedAt":"2014-07-03T07:23:16Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Here are a few small hashmap improvements, partly resulting from recent\n> discussion of the config-cache topic.\n>\n> Karsten Blees (4):\n>   hashmap: factor out getting an int hash code from a SHA1\n>   hashmap: improve struct hashmap member documentation\n>   hashmap: add simplified hashmap_get_from_hash() API\n>   hashmap: add string interning API\n\nThe patch series look good to me (but that's not a detailed review,\njust a moderately quick look).\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"245479","messageId":"xmqqoax1dqxb.fsf@gitster.dls.corp.google.com","threadId":"37047","inReplyTo":"53B485A4.20609@gmail.com","subject":"Re: [PATCH v1 1/4] hashmap: factor out getting an int hash code from a, SHA1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-07T17:22:56Z","receivedAt":"2014-07-07T17:22:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Copying the first bytes of a SHA1 is duplicated in six places, however,\n> the implications (wrong byte order on little-endian systems) is documented\n> only once.\n\ns/wrong /different /; but other than that I think this is a good\nchange.\n\n> +`unsigned int sha1hash(const unsigned char *sha1)`::\n> +\n> +\tConverts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n> +\tfor use in hash tables. Cryptographic hashes are supposed to have\n> +\tuniform distribution, so in contrast to `memhash()`, this just copies\n> +\tthe first `sizeof(int)` bytes without shuffling any bits. Note that\n> +\tthe results will be different on big-endian and little-endian\n> +\tplatforms, so they should not be stored or transferred over the net!\n\nTone down with s/!/./, perhaps?\n\nAnother thing we may want to caution against is to use it as a\ntie-breaker that affects the final outcome the user can observe, but\nthat may be something that goes without saying.  I dunno..\n\n> diff --git a/hashmap.h b/hashmap.h\n> index a816ad4..ed5425a 100644\n> --- a/hashmap.h\n> +++ b/hashmap.h\n> @@ -13,6 +13,17 @@ extern unsigned int strihash(const char *buf);\n>  extern unsigned int memhash(const void *buf, size_t len);\n>  extern unsigned int memihash(const void *buf, size_t len);\n>  \n> +static inline unsigned int sha1hash(const unsigned char *sha1)\n> +{\n> +\t/*\n> +\t * Equivalent to 'return *(int *)sha1;', but safe on platforms that\n> +\t * don't support unaligned reads.\n> +\t */\n\ns/int/unsigned &/; other than that, the explanation is good.\n\n> +\tunsigned int hash;\n> +\tmemcpy(&hash, sha1, sizeof(hash));\n> +\treturn hash;\n> +}\n> +\n"},{"id":"245481","messageId":"xmqqk37pdpzb.fsf@gitster.dls.corp.google.com","threadId":"37047","inReplyTo":"53B48613.60509@gmail.com","subject":"Re: [PATCH v1 3/4] hashmap: add simplified hashmap_get_from_hash() API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-07T17:43:20Z","receivedAt":"2014-07-07T17:43:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Hashmap entries are typically looked up by just a key. The hashmap_get()\n> API expects an initialized entry structure instead, to support compound\n> keys. This flexibility is currently only needed by find_dir_entry() in\n> name-hash.c (and compat/win32/fscache.c in the msysgit fork). All other\n> (currently five) call sites of hashmap_get() have to set up a near emtpy\n\ns/emtpy/empty/;\n\n> entry structure, resulting in duplicate code like this:\n>\n>   struct hashmap_entry keyentry;\n>   hashmap_entry_init(&keyentry, hash(key));\n>   return hashmap_get(map, &keyentry, key);\n>\n> Add a hashmap_get_from_hash() API that allows hashmap lookups by just\n> specifying the key and its hash code, i.e.:\n>\n>   return hashmap_get_from_hash(map, hash(key), key);\n\nWhile I think the *_get_from_hash() is an improvement over the\nthree-line sequence, I find it somewhat strange that callers of it\nstill must compute the hash code themselves, instead of letting the\nhashmap itself to apply the user supplied hash function to the key\nto derive it.  After all, the map must know how to compare two\nentries via a user-supplied cmpfn given at the map initialization\ntime, and the algorithm to derive the hash code falls into the same\ncategory, in the sense that both must stay the same during the\nlifetime of a hashmap, no?  Unless there is a situation where you\nneed to be able to initialize a hashmap_entry without knowing which\nhashmap the entry will eventually be stored, it feels dubious API\nthat exposes to the outside callers hashmap_entry_init() that takes\nthe hash code without taking the hashmap itself.\n\nIn other words, why isn't hashmap_get() more like this:\n\n        void *hashmap_get(const struct hashmap *map, const void *key)\n        {\n                struct hashmap_entry keyentry;\n                hashmap_entry_init(&keyentry, map->hash(key));\n                return *find_entry_ptr(map, &keyentry, key);\n        }\n\nwith hashmap_entry_init() purely a static helper in hashmap.c?\n"},{"id":"245482","messageId":"xmqqfviddpxc.fsf@gitster.dls.corp.google.com","threadId":"37047","inReplyTo":"53B4863E.1020701@gmail.com","subject":"Re: [PATCH v1 4/4] hashmap: add string interning API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-07T17:44:31Z","receivedAt":"2014-07-07T17:44:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Interning short strings with high probability of duplicates can reduce the\n> memory footprint and speed up comparisons.\n>\n> Add strintern() and memintern() APIs that use a hashmap to manage the pool\n> of unique, interned strings.\n>\n> Note: strintern(getenv()) could be used to sanitize git's use of getenv(),\n> in case we ever encounter a platform where a call to getenv() invalidates\n> previous getenv() results (which is allowed by POSIX).\n\nI think the attribute name/value strings are already interned, so\nthey may want to be converted to use this (or vice-versa).\n\n>\n> Signed-off-by: Karsten Blees <blees@dcon.de>\n> ---\n>  Documentation/technical/api-hashmap.txt | 15 +++++++++++++\n>  hashmap.c                               | 38 +++++++++++++++++++++++++++++++++\n>  hashmap.h                               |  8 +++++++\n>  t/t0011-hashmap.sh                      | 13 +++++++++++\n>  test-hashmap.c                          | 14 ++++++++++++\n>  5 files changed, 88 insertions(+)\n>\n> diff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\n> index f9215d6..00c4c29 100644\n> --- a/Documentation/technical/api-hashmap.txt\n> +++ b/Documentation/technical/api-hashmap.txt\n> @@ -193,6 +193,21 @@ more entries.\n>  `hashmap_iter_first` is a combination of both (i.e. initializes the iterator\n>  and returns the first entry, if any).\n>  \n> +`const char *strintern(const char *string)`::\n> +`const void *memintern(const void *data, size_t len)`::\n> +\n> +\tReturns the unique, interned version of the specified string or data,\n> +\tsimilar to the `String.intern` API in Java and .NET, respectively.\n> +\tInterned strings remain valid for the entire lifetime of the process.\n> ++\n> +Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned\n> +strings / data must not be modified or freed.\n> ++\n> +Interned strings are best used for short strings with high probability of\n> +duplicates.\n> ++\n> +Uses a hashmap to store the pool of interned strings.\n> +\n>  Usage example\n>  -------------\n>  \n> diff --git a/hashmap.c b/hashmap.c\n> index d1b8056..f693839 100644\n> --- a/hashmap.c\n> +++ b/hashmap.c\n> @@ -226,3 +226,41 @@ void *hashmap_iter_next(struct hashmap_iter *iter)\n>  \t\tcurrent = iter->map->table[iter->tablepos++];\n>  \t}\n>  }\n> +\n> +struct pool_entry {\n> +\tstruct hashmap_entry ent;\n> +\tsize_t len;\n> +\tunsigned char data[FLEX_ARRAY];\n> +};\n> +\n> +static int pool_entry_cmp(const struct pool_entry *e1,\n> +\t\t\t  const struct pool_entry *e2,\n> +\t\t\t  const unsigned char *keydata)\n> +{\n> +\treturn e1->data != keydata &&\n> +\t       (e1->len != e2->len || memcmp(e1->data, keydata, e1->len));\n> +}\n> +\n> +const void *memintern(const void *data, size_t len)\n> +{\n> +\tstatic struct hashmap map;\n> +\tstruct pool_entry key, *e;\n> +\n> +\t/* initialize string pool hashmap */\n> +\tif (!map.tablesize)\n> +\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, 0);\n> +\n> +\t/* lookup interned string in pool */\n> +\thashmap_entry_init(&key, memhash(data, len));\n> +\tkey.len = len;\n> +\te = hashmap_get(&map, &key, data);\n> +\tif (!e) {\n> +\t\t/* not found: create it */\n> +\t\te = xmallocz(sizeof(struct pool_entry) + len);\n> +\t\thashmap_entry_init(e, key.ent.hash);\n> +\t\te->len = len;\n> +\t\tmemcpy(e->data, data, len);\n> +\t\thashmap_add(&map, e);\n> +\t}\n> +\treturn e->data;\n> +}\n> diff --git a/hashmap.h b/hashmap.h\n> index 12f0668..507884b 100644\n> --- a/hashmap.h\n> +++ b/hashmap.h\n> @@ -87,4 +87,12 @@ static inline void *hashmap_iter_first(struct hashmap *map,\n>  \treturn hashmap_iter_next(iter);\n>  }\n>  \n> +/* string interning */\n> +\n> +extern const void *memintern(const void *data, size_t len);\n> +static inline const char *strintern(const char *string)\n> +{\n> +\treturn memintern(string, strlen(string));\n> +}\n> +\n>  #endif\n> diff --git a/t/t0011-hashmap.sh b/t/t0011-hashmap.sh\n> index 391e2b6..f97c805 100755\n> --- a/t/t0011-hashmap.sh\n> +++ b/t/t0011-hashmap.sh\n> @@ -237,4 +237,17 @@ test_expect_success 'grow / shrink' '\n>  \n>  '\n>  \n> +test_expect_success 'string interning' '\n> +\n> +test_hashmap \"intern value1\n> +intern Value1\n> +intern value2\n> +intern value2\n> +\" \"value1\n> +Value1\n> +value2\n> +value2\"\n> +\n> +'\n> +\n>  test_done\n> diff --git a/test-hashmap.c b/test-hashmap.c\n> index 3c9f67b..07aa7ec 100644\n> --- a/test-hashmap.c\n> +++ b/test-hashmap.c\n> @@ -234,6 +234,20 @@ int main(int argc, char *argv[])\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(\"intern\", cmd) && l1) {\n> +\n> +\t\t\t/* test that strintern works */\n> +\t\t\tconst char *i1 = strintern(p1);\n> +\t\t\tconst char *i2 = strintern(p1);\n> +\t\t\tif (strcmp(i1, p1))\n> +\t\t\t\tprintf(\"strintern(%s) returns %s\\n\", p1, i1);\n> +\t\t\telse if (i1 == p1)\n> +\t\t\t\tprintf(\"strintern(%s) returns input pointer\\n\", p1);\n> +\t\t\telse if (i1 != i2)\n> +\t\t\t\tprintf(\"strintern(%s) != strintern(%s)\", i1, i2);\n> +\t\t\telse\n> +\t\t\t\tprintf(\"%s\\n\", i1);\n> +\n>  \t\t} else if (!strcmp(\"perfhashmap\", cmd) && l1 && l2) {\n>  \n>  \t\t\tperf_hashmap(atoi(p1), atoi(p2));\n"},{"id":"245821","messageId":"53C036F7.5070104@gmail.com","threadId":"37047","inReplyTo":"xmqqk37pdpzb.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v1 3/4] hashmap: add simplified hashmap_get_from_hash() API","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-11T19:11:51Z","receivedAt":"2014-07-11T19:11:51Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 07.07.2014 19:43, schrieb Junio C Hamano:\n> Karsten Blees <karsten.blees@gmail.com> writes:\n> \n>> Hashmap entries are typically looked up by just a key. The hashmap_get()\n>> API expects an initialized entry structure instead, to support compound\n>> keys. This flexibility is currently only needed by find_dir_entry() in\n>> name-hash.c (and compat/win32/fscache.c in the msysgit fork). All other\n>> (currently five) call sites of hashmap_get() have to set up a near emtpy\n> \n> s/emtpy/empty/;\n> \n>> entry structure, resulting in duplicate code like this:\n>>\n>>   struct hashmap_entry keyentry;\n>>   hashmap_entry_init(&keyentry, hash(key));\n>>   return hashmap_get(map, &keyentry, key);\n>>\n>> Add a hashmap_get_from_hash() API that allows hashmap lookups by just\n>> specifying the key and its hash code, i.e.:\n>>\n>>   return hashmap_get_from_hash(map, hash(key), key);\n> \n> While I think the *_get_from_hash() is an improvement over the\n> three-line sequence, I find it somewhat strange that callers of it\n> still must compute the hash code themselves, instead of letting the\n> hashmap itself to apply the user supplied hash function to the key\n> to derive it.  After all, the map must know how to compare two\n> entries via a user-supplied cmpfn given at the map initialization\n> time, and the algorithm to derive the hash code falls into the same\n> category, in the sense that both must stay the same during the\n> lifetime of a hashmap, no?  Unless there is a situation where you\n> need to be able to initialize a hashmap_entry without knowing which\n> hashmap the entry will eventually be stored, it feels dubious API\n> that exposes to the outside callers hashmap_entry_init() that takes\n> the hash code without taking the hashmap itself.\n> \n> In other words, why isn't hashmap_get() more like this:\n> \n>         void *hashmap_get(const struct hashmap *map, const void *key)\n>         {\n>                 struct hashmap_entry keyentry;\n>                 hashmap_entry_init(&keyentry, map->hash(key));\n>                 return *find_entry_ptr(map, &keyentry, key);\n>         }\n> \n> with hashmap_entry_init() purely a static helper in hashmap.c?\n> \n\n1. Performance\n\nCalculating hash codes is the most expensive operation when working with\nhash tables (unless you already have a good hash such as sha1). And using\nhash tables as a cache of some sort is probably the most common use case.\nSo you'll often have code like this:\n\n1  unsigned int h = hash(key);\n2  struct my_entry *e = hashmap_get_from_hash(&map, hash, key);\n3  if (!e) {\n4    e = malloc(sizeof(*e));\n5    hashmap_entry_init(e, h);\n6    e->key = key;\n6    hashmap_add(&map, e);\n7  }\n\nNote that the hash code from line 1 can be reused in line 5. You cannot do\nthat if calculating the hash code is buried in the implementation.\n\nCallbacks cannot be inlined either...\n\n\n2. Simplicity\n\nMost APIs take a user defined hashmap_entry structure, so you'd either need\ntwo hash functions, or a hash function that can distinguish between the\n'entry' and 'key-only' case, e.g.\n\n  unsigned int my_hash(const struct my_entry *entry, const void *keydata)\n  {\n    if (keydata)\n      return strhash(keydata);\n    else\n      return strhash(entry->key);\n  }\n\nHashmap clients will typically provide small, type safe wrappers around the\nhashmap API. That's perfect for calculating the hash code without breaking\nencapsulation. IMO there's no need to make things more complex by requiring\nanother callback.\n\n\n3. Compound keys\n\nThe key doesn't always consist of just a single word. E.g. for struct\ndir_entry, the key is [char *name, int len]. So an API like this:\n\n  void *hashmap_get(const struct hashmap *map, const void *key)\n\nwon't do in the general case (unless you require clients to define their\nown key structure in addition to the entry structure...).\n"},{"id":"245839","messageId":"xmqq8unz35am.fsf@gitster.dls.corp.google.com","threadId":"37047","inReplyTo":"53C036F7.5070104@gmail.com","subject":"Re: [PATCH v1 3/4] hashmap: add simplified hashmap_get_from_hash() API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-11T22:21:37Z","receivedAt":"2014-07-11T22:21:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n>> In other words, why isn't hashmap_get() more like this:\n>>  ...\n>> with hashmap_entry_init() purely a static helper in hashmap.c?\n>> \n> 1. Performance\n\nOK.\n\n> 2. Simplicity\n>\n> Hashmap clients will typically provide small, type safe wrappers around the\n> hashmap API.\n\nOK.\n\n> 3. Compound keys\n>\n> The key doesn't always consist of just a single word. E.g. for struct\n> dir_entry, the key is [char *name, int len]. So an API like this:\n>\n>   void *hashmap_get(const struct hashmap *map, const void *key)\n>\n> won't do in the general case (unless you require clients to define their\n> own key structure in addition to the entry structure...).\n\nYeah, I was being silly.  Thanks.\n"}]}