{"thread":{"id":"46284","subject":"[PATCH 0/2] Introduce data field in hashmap and migrate docs to header","startedAt":"2017-06-29T01:13:43Z","lastAt":"2017-07-05T09:00:10Z","messageCount":26,"participants":["Stefan Beller","Jeff Hostetler","Junio C Hamano","Jonathan Nieder","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"323471","messageId":"20170629011334.11173-1-sbeller@google.com","threadId":"46284","inReplyTo":null,"subject":"[PATCH 0/2] Introduce data field in hashmap and migrate docs to header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T01:13:32Z","receivedAt":"2017-06-29T01:13:43Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"https://public-inbox.org/git/xmqqpodnvmmw.fsf@gitster.mtv.corp.google.com/\nfor context why we need a new data field.  Implement that.\n\nOnce upon a time we had a long discussion where to put documentation best.\nThe answer was header files as there documentation has less chance\nto become stale and be out of date.  Improve the docs by\n* migrating them to the header\n* clarifying how the compare function is to be used\n* how the arguments to hashmap_get/remove should be used.\n\nThanks,\nStefan\n\nStefan Beller (2):\n  hashmap.h: compare function has access to a data field\n  hashmap: migrate documentation from Documentation/technical into\n    header\n\n Documentation/technical/api-hashmap.txt | 309 --------------------------------\n attr.c                                  |   4 +-\n builtin/describe.c                      |   6 +-\n builtin/difftool.c                      |  20 ++-\n builtin/fast-export.c                   |   5 +-\n config.c                                |   7 +-\n convert.c                               |   3 +-\n diffcore-rename.c                       |   2 +-\n hashmap.c                               |  17 +-\n hashmap.h                               | 256 +++++++++++++++++++++++---\n name-hash.c                             |  12 +-\n oidset.c                                |   5 +-\n patch-ids.c                             |   6 +-\n refs.c                                  |   4 +-\n remote.c                                |   7 +-\n sha1_file.c                             |   5 +-\n sub-process.c                           |   5 +-\n sub-process.h                           |   6 +-\n submodule-config.c                      |  10 +-\n t/helper/test-hashmap.c                 |  15 +-\n 20 files changed, 325 insertions(+), 379 deletions(-)\n delete mode 100644 Documentation/technical/api-hashmap.txt\n\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323472","messageId":"20170629011334.11173-2-sbeller@google.com","threadId":"46284","inReplyTo":"20170629011334.11173-1-sbeller@google.com","subject":"[PATCH 1/2] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T01:13:33Z","receivedAt":"2017-06-29T01:13:48Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"When using the hashmap a common need is to have access to arbitrary data\nin the compare function. A couple of times we abuse the keydata field\nto pass in the data needed. This happens for example in patch-ids.c.\n\nThis patch changes the function signature of the compare function\nto have one more void pointer available. The pointer given for each\ninvocation of the compare function must be defined in the init function\nof the hashmap and is just passed through.\n\nDocumentation of this new feature is deferred to a later patch.\n\nWhile at it improve the naming of the fields of all compare functions used\nby hashmaps by ensuring unused parameters are prefixed with 'unused_' and\nnaming the parameters what they are (instead of 'unused' make it\n'unused_keydata').\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n attr.c                  |  4 ++--\n builtin/describe.c      |  6 ++++--\n builtin/difftool.c      | 20 ++++++++++++--------\n builtin/fast-export.c   |  5 +++--\n config.c                |  7 +++++--\n convert.c               |  3 ++-\n diffcore-rename.c       |  2 +-\n hashmap.c               | 17 ++++++++++++-----\n hashmap.h               |  9 ++++++---\n name-hash.c             | 12 ++++++++----\n oidset.c                |  5 +++--\n patch-ids.c             |  6 ++++--\n refs.c                  |  4 ++--\n remote.c                |  7 +++++--\n sha1_file.c             |  5 +++--\n sub-process.c           |  5 +++--\n sub-process.h           |  6 ++++--\n submodule-config.c      | 10 ++++++----\n t/helper/test-hashmap.c | 15 ++++++++++-----\n 19 files changed, 95 insertions(+), 53 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex 37454999d2..2f51417675 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -78,7 +78,7 @@ struct attr_hash_entry {\n /* attr_hashmap comparison function */\n static int attr_hash_entry_cmp(const struct attr_hash_entry *a,\n \t\t\t       const struct attr_hash_entry *b,\n-\t\t\t       void *unused)\n+\t\t\t       void *unused_keydata, void *unused_data)\n {\n \treturn (a->keylen != b->keylen) || strncmp(a->key, b->key, a->keylen);\n }\n@@ -86,7 +86,7 @@ static int attr_hash_entry_cmp(const struct attr_hash_entry *a,\n /* Initialize an 'attr_hashmap' object */\n static void attr_hashmap_init(struct attr_hashmap *map)\n {\n-\thashmap_init(&map->map, (hashmap_cmp_fn) attr_hash_entry_cmp, 0);\n+\thashmap_init(&map->map, (hashmap_cmp_fn) attr_hash_entry_cmp, NULL, 0);\n }\n \n /*\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 70eb144608..a6c5a969a0 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -55,7 +55,9 @@ static const char *prio_names[] = {\n };\n \n static int commit_name_cmp(const struct commit_name *cn1,\n-\t\tconst struct commit_name *cn2, const void *peeled)\n+\t\t\t   const struct commit_name *cn2,\n+\t\t\t   const void *peeled,\n+\t\t\t   const void *unused_data)\n {\n \treturn oidcmp(&cn1->peeled, peeled ? peeled : &cn2->peeled);\n }\n@@ -501,7 +503,7 @@ 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-\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);\n+\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, NULL, 0);\n \tfor_each_rawref(get_name, NULL);\n \tif (!names.size && !always)\n \t\tdie(_(\"No names found, cannot describe anything.\"));\ndiff --git a/builtin/difftool.c b/builtin/difftool.c\nindex 9199227f6e..80786a95ab 100644\n--- a/builtin/difftool.c\n+++ b/builtin/difftool.c\n@@ -131,7 +131,9 @@ struct working_tree_entry {\n };\n \n static int working_tree_entry_cmp(struct working_tree_entry *a,\n-\t\t\t\t  struct working_tree_entry *b, void *keydata)\n+\t\t\t\t  struct working_tree_entry *b,\n+\t\t\t\t  void *unused_keydata,\n+\t\t\t\t  void *unused_data)\n {\n \treturn strcmp(a->path, b->path);\n }\n@@ -146,7 +148,8 @@ struct pair_entry {\n \tconst char path[FLEX_ARRAY];\n };\n \n-static int pair_cmp(struct pair_entry *a, struct pair_entry *b, void *keydata)\n+static int pair_cmp(struct pair_entry *a, struct pair_entry *b,\n+\t\t    void *unused_keydata, void *unused_data)\n {\n \treturn strcmp(a->path, b->path);\n }\n@@ -174,7 +177,8 @@ struct path_entry {\n \tchar path[FLEX_ARRAY];\n };\n \n-static int path_entry_cmp(struct path_entry *a, struct path_entry *b, void *key)\n+static int path_entry_cmp(struct path_entry *a, struct path_entry *b,\n+\t\t\t  void *key, void *unused_data)\n {\n \treturn strcmp(a->path, key ? key : b->path);\n }\n@@ -367,9 +371,9 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,\n \twtdir_len = wtdir.len;\n \n \thashmap_init(&working_tree_dups,\n-\t\t     (hashmap_cmp_fn)working_tree_entry_cmp, 0);\n-\thashmap_init(&submodules, (hashmap_cmp_fn)pair_cmp, 0);\n-\thashmap_init(&symlinks2, (hashmap_cmp_fn)pair_cmp, 0);\n+\t\t     (hashmap_cmp_fn)working_tree_entry_cmp, NULL, 0);\n+\thashmap_init(&submodules, (hashmap_cmp_fn)pair_cmp, NULL, 0);\n+\thashmap_init(&symlinks2, (hashmap_cmp_fn)pair_cmp, NULL, 0);\n \n \tchild.no_stdin = 1;\n \tchild.git_cmd = 1;\n@@ -580,9 +584,9 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,\n \t * files through the symlink.\n \t */\n \thashmap_init(&wt_modified, (hashmap_cmp_fn)path_entry_cmp,\n-\t\t     wtindex.cache_nr);\n+\t\t     NULL, wtindex.cache_nr);\n \thashmap_init(&tmp_modified, (hashmap_cmp_fn)path_entry_cmp,\n-\t\t     wtindex.cache_nr);\n+\t\t     NULL, wtindex.cache_nr);\n \n \tfor (i = 0; i < wtindex.cache_nr; i++) {\n \t\tstruct hashmap_entry dummy;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 12d501bfde..fa389fe252 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -94,7 +94,8 @@ struct anonymized_entry {\n };\n \n static int anonymized_entry_cmp(const void *va, const void *vb,\n-\t\t\t\tconst void *data)\n+\t\t\t\tconst void *unused_keydata,\n+\t\t\t\tconst void *unused_data)\n {\n \tconst struct anonymized_entry *a = va, *b = vb;\n \treturn a->orig_len != b->orig_len ||\n@@ -113,7 +114,7 @@ static const void *anonymize_mem(struct hashmap *map,\n \tstruct anonymized_entry key, *ret;\n \n \tif (!map->cmpfn)\n-\t\thashmap_init(map, anonymized_entry_cmp, 0);\n+\t\thashmap_init(map, anonymized_entry_cmp, NULL, 0);\n \n \thashmap_entry_init(&key, memhash(orig, *len));\n \tkey.orig = orig;\ndiff --git a/config.c b/config.c\nindex 1cd40a5fe6..aa0198a5fd 100644\n--- a/config.c\n+++ b/config.c\n@@ -1754,14 +1754,17 @@ static int configset_add_value(struct config_set *cs, const char *key, const cha\n }\n \n static int config_set_element_cmp(const struct config_set_element *e1,\n-\t\t\t\t const struct config_set_element *e2, const void *unused)\n+\t\t\t\t const struct config_set_element *e2,\n+\t\t\t\t const void *unused_keydata,\n+\t\t\t\t const void *unused_data)\n {\n \treturn strcmp(e1->key, e2->key);\n }\n \n void git_configset_init(struct config_set *cs)\n {\n-\thashmap_init(&cs->config_hash, (hashmap_cmp_fn)config_set_element_cmp, 0);\n+\thashmap_init(&cs->config_hash, (hashmap_cmp_fn)config_set_element_cmp,\n+\t\t     NULL, 0);\n \tcs->hash_initialized = 1;\n \tcs->list.nr = 0;\n \tcs->list.alloc = 0;\ndiff --git a/convert.c b/convert.c\nindex 7d2a519daf..deaf0ba7b3 100644\n--- a/convert.c\n+++ b/convert.c\n@@ -583,7 +583,8 @@ static int apply_multi_file_filter(const char *path, const char *src, size_t len\n \n \tif (!subprocess_map_initialized) {\n \t\tsubprocess_map_initialized = 1;\n-\t\thashmap_init(&subprocess_map, (hashmap_cmp_fn) cmd2process_cmp, 0);\n+\t\thashmap_init(&subprocess_map, (hashmap_cmp_fn) cmd2process_cmp,\n+\t\t\t     NULL, 0);\n \t\tentry = NULL;\n \t} else {\n \t\tentry = (struct cmd2process *)subprocess_find_entry(&subprocess_map, cmd);\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1e4678b7d7..786f389498 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -341,7 +341,7 @@ static int find_exact_renames(struct diff_options *options)\n \t/* Add all sources to the hash table in reverse order, because\n \t * later on they will be retrieved in LIFO order.\n \t */\n-\thashmap_init(&file_table, NULL, rename_src_nr);\n+\thashmap_init(&file_table, NULL, NULL, rename_src_nr);\n \tfor (i = rename_src_nr-1; i >= 0; i--)\n \t\tinsert_file_table(&file_table, i, rename_src[i].p->one);\n \ndiff --git a/hashmap.c b/hashmap.c\nindex 7d1044eb5d..82d70b329b 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -95,7 +95,9 @@ static inline int entry_equals(const struct hashmap *map,\n \t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2,\n \t\tconst void *keydata)\n {\n-\treturn (e1 == e2) || (e1->hash == e2->hash && !map->cmpfn(e1, e2, keydata));\n+\treturn (e1 == e2) ||\n+\t       (e1->hash == e2->hash &&\n+\t\t!map->cmpfn(e1, e2, keydata, map->data));\n }\n \n static inline unsigned int bucket(const struct hashmap *map,\n@@ -140,19 +142,23 @@ static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,\n \treturn e;\n }\n \n-static int always_equal(const void *unused1, const void *unused2, const void *unused3)\n+static int always_equal(const void *unused1,\n+\t\t\tconst void *unused2,\n+\t\t\tconst void *unused_keydata,\n+\t\t\tconst void *unused_data)\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+\t\tconst void *data, size_t initial_size)\n {\n \tunsigned int size = HASHMAP_INITIAL_SIZE;\n \n \tmemset(map, 0, sizeof(*map));\n \n \tmap->cmpfn = equals_function ? equals_function : always_equal;\n+\tmap->data = data;\n \n \t/* calculate initial table size and allocate the table */\n \tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n@@ -262,7 +268,8 @@ struct pool_entry {\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+\t\t\t  const unsigned char *keydata,\n+\t\t\t  const void *unused_data)\n {\n \treturn e1->data != keydata &&\n \t       (e1->len != e2->len || memcmp(e1->data, keydata, e1->len));\n@@ -275,7 +282,7 @@ const void *memintern(const void *data, size_t len)\n \n \t/* initialize string pool hashmap */\n \tif (!map.tablesize)\n-\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, 0);\n+\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0);\n \n \t/* lookup interned string in pool */\n \thashmap_entry_init(&key, memhash(data, len));\ndiff --git a/hashmap.h b/hashmap.h\nindex de6022a3a9..1c26bbad5b 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -33,11 +33,12 @@ struct hashmap_entry {\n };\n \n typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n-\t\tconst void *keydata);\n+\t\tconst void *keydata, const void *cbdata);\n \n struct hashmap {\n \tstruct hashmap_entry **table;\n \thashmap_cmp_fn cmpfn;\n+\tconst void *data;\n \tunsigned int size, tablesize, grow_at, shrink_at;\n \tunsigned disallow_rehash : 1;\n };\n@@ -50,8 +51,10 @@ struct hashmap_iter {\n \n /* hashmap functions */\n \n-extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n-\t\tsize_t initial_size);\n+extern void hashmap_init(struct hashmap *map,\n+\t\t\t hashmap_cmp_fn equals_function,\n+\t\t\t const void *data,\n+\t\t\t size_t initial_size);\n extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\ndiff --git a/name-hash.c b/name-hash.c\nindex 39309efb7f..4e9eac925a 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -17,7 +17,9 @@ struct dir_entry {\n };\n \n static int dir_entry_cmp(const struct dir_entry *e1,\n-\t\tconst struct dir_entry *e2, const char *name)\n+\t\t\t const struct dir_entry *e2,\n+\t\t\t const char *name,\n+\t\t\t const void *unused_data)\n {\n \treturn e1->namelen != e2->namelen || strncasecmp(e1->name,\n \t\t\tname ? name : e2->name, e1->namelen);\n@@ -108,7 +110,9 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n }\n \n static int cache_entry_cmp(const struct cache_entry *ce1,\n-\t\tconst struct cache_entry *ce2, const void *remove)\n+\t\t\t   const struct cache_entry *ce2,\n+\t\t\t   const void *remove,\n+\t\t\t   const void *unused_data)\n {\n \t/*\n \t * For remove_name_hash, find the exact entry (pointer equality); for\n@@ -571,9 +575,9 @@ static void lazy_init_name_hash(struct index_state *istate)\n \tif (istate->name_hash_initialized)\n \t\treturn;\n \thashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,\n-\t\t\tistate->cache_nr);\n+\t\t\tNULL, istate->cache_nr);\n \thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,\n-\t\t\tistate->cache_nr);\n+\t\t\tNULL, istate->cache_nr);\n \n \tif (lookup_lazy_params(istate)) {\n \t\thashmap_disallow_rehash(&istate->dir_hash, 1);\ndiff --git a/oidset.c b/oidset.c\nindex ac169f05d3..f20e6e4df3 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -7,7 +7,8 @@ struct oidset_entry {\n };\n \n static int oidset_hashcmp(const void *va, const void *vb,\n-\t\t\t  const void *vkey)\n+\t\t\t  const void *vkey,\n+\t\t\t  const void *unused_data)\n {\n \tconst struct oidset_entry *a = va, *b = vb;\n \tconst struct object_id *key = vkey;\n@@ -30,7 +31,7 @@ int oidset_insert(struct oidset *set, const struct object_id *oid)\n \tstruct oidset_entry *entry;\n \n \tif (!set->map.cmpfn)\n-\t\thashmap_init(&set->map, oidset_hashcmp, 0);\n+\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n \n \tif (oidset_contains(set, oid))\n \t\treturn 1;\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 9c0ab9e67a..b9b2ebbad0 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -37,6 +37,7 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n  */\n static int patch_id_cmp(struct patch_id *a,\n \t\t\tstruct patch_id *b,\n+\t\t\tconst void *unused_keydata,\n \t\t\tstruct diff_options *opt)\n {\n \tif (is_null_oid(&a->patch_id) &&\n@@ -57,7 +58,8 @@ int init_patch_ids(struct patch_ids *ids)\n \tids->diffopts.detect_rename = 0;\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n-\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n+\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n+\t\t     &ids->diffopts, 256);\n \treturn 0;\n }\n \n@@ -93,7 +95,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n \tif (init_patch_id_entry(&patch, commit, ids))\n \t\treturn NULL;\n \n-\treturn hashmap_get(&ids->patches, &patch, &ids->diffopts);\n+\treturn hashmap_get(&ids->patches, &patch, NULL);\n }\n \n struct patch_id *add_commit_patch_id(struct commit *commit,\ndiff --git a/refs.c b/refs.c\nindex 88658ba769..71e0170feb 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1526,7 +1526,7 @@ struct ref_store_hash_entry\n };\n \n static int ref_store_hash_cmp(const void *entry, const void *entry_or_key,\n-\t\t\t      const void *keydata)\n+\t\t\t      const void *keydata, const void *unused_data)\n {\n \tconst struct ref_store_hash_entry *e1 = entry, *e2 = entry_or_key;\n \tconst char *name = keydata ? keydata : e2->name;\n@@ -1608,7 +1608,7 @@ static void register_ref_store_map(struct hashmap *map,\n \t\t\t\t   const char *name)\n {\n \tif (!map->tablesize)\n-\t\thashmap_init(map, ref_store_hash_cmp, 0);\n+\t\thashmap_init(map, ref_store_hash_cmp, NULL, 0);\n \n \tif (hashmap_put(map, alloc_ref_store_hash_entry(name, refs)))\n \t\tdie(\"BUG: %s ref_store '%s' initialized twice\", type, name);\ndiff --git a/remote.c b/remote.c\nindex d87482573d..b5e05890ee 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -133,7 +133,10 @@ struct remotes_hash_key {\n \tint len;\n };\n \n-static int remotes_hash_cmp(const struct remote *a, const struct remote *b, const struct remotes_hash_key *key)\n+static int remotes_hash_cmp(const struct remote *a,\n+\t\t\t    const struct remote *b,\n+\t\t\t    const struct remotes_hash_key *key,\n+\t\t\t    const void *unused_data)\n {\n \tif (key)\n \t\treturn strncmp(a->name, key->str, key->len) || a->name[key->len];\n@@ -144,7 +147,7 @@ static int remotes_hash_cmp(const struct remote *a, const struct remote *b, cons\n static inline void init_remotes_hash(void)\n {\n \tif (!remotes_hash.cmpfn)\n-\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, 0);\n+\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, NULL, 0);\n }\n \n static struct remote *make_remote(const char *name, int len)\ndiff --git a/sha1_file.c b/sha1_file.c\nindex fb1fd809dc..b748db31ed 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2390,7 +2390,8 @@ static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,\n }\n \n static int delta_base_cache_hash_cmp(const void *va, const void *vb,\n-\t\t\t\t     const void *vkey)\n+\t\t\t\t     const void *vkey,\n+\t\t\t\t     const void *unused_data)\n {\n \tconst struct delta_base_cache_entry *a = va, *b = vb;\n \tconst struct delta_base_cache_key *key = vkey;\n@@ -2472,7 +2473,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tlist_add_tail(&ent->lru, &delta_base_cache_lru);\n \n \tif (!delta_base_cache.cmpfn)\n-\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, 0);\n+\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);\n \thashmap_entry_init(ent, pack_entry_hash(p, base_offset));\n \thashmap_add(&delta_base_cache, ent);\n }\ndiff --git a/sub-process.c b/sub-process.c\nindex 92f8aea70a..68b53cf48a 100644\n--- a/sub-process.c\n+++ b/sub-process.c\n@@ -6,8 +6,9 @@\n #include \"pkt-line.h\"\n \n int cmd2process_cmp(const struct subprocess_entry *e1,\n-\t\t\t   const struct subprocess_entry *e2,\n-\t\t\t   const void *unused)\n+\t\t    const struct subprocess_entry *e2,\n+\t\t    const void *unused_keydata,\n+\t\t    const void *unused_data)\n {\n \treturn strcmp(e1->cmd, e2->cmd);\n }\ndiff --git a/sub-process.h b/sub-process.h\nindex d9a45cd359..a19b4d9936 100644\n--- a/sub-process.h\n+++ b/sub-process.h\n@@ -20,8 +20,10 @@ struct subprocess_entry {\n \n /* subprocess functions */\n \n-int cmd2process_cmp(const struct subprocess_entry *e1,\n-\tconst struct subprocess_entry *e2, const void *unused);\n+extern int cmd2process_cmp(const struct subprocess_entry *e1,\n+\t\t\t   const struct subprocess_entry *e2,\n+\t\t\t   const void *unused_keydata,\n+\t\t\t   const void *unused_data);\n \n typedef int(*subprocess_start_fn)(struct subprocess_entry *entry);\n int subprocess_start(struct hashmap *hashmap, struct subprocess_entry *entry, const char *cmd,\ndiff --git a/submodule-config.c b/submodule-config.c\nindex d8f8d5ea32..5c2fc489b8 100644\n--- a/submodule-config.c\n+++ b/submodule-config.c\n@@ -36,7 +36,8 @@ static int is_cache_init;\n \n static int config_path_cmp(const struct submodule_entry *a,\n \t\t\t   const struct submodule_entry *b,\n-\t\t\t   const void *unused)\n+\t\t\t   const void *unused_keydata,\n+\t\t\t   const void *unused_data)\n {\n \treturn strcmp(a->config->path, b->config->path) ||\n \t       hashcmp(a->config->gitmodules_sha1, b->config->gitmodules_sha1);\n@@ -44,7 +45,8 @@ static int config_path_cmp(const struct submodule_entry *a,\n \n static int config_name_cmp(const struct submodule_entry *a,\n \t\t\t   const struct submodule_entry *b,\n-\t\t\t   const void *unused)\n+\t\t\t   const void *unused_keydata,\n+\t\t\t   const void *unused_data)\n {\n \treturn strcmp(a->config->name, b->config->name) ||\n \t       hashcmp(a->config->gitmodules_sha1, b->config->gitmodules_sha1);\n@@ -52,8 +54,8 @@ static int config_name_cmp(const struct submodule_entry *a,\n \n static void cache_init(struct submodule_cache *cache)\n {\n-\thashmap_init(&cache->for_path, (hashmap_cmp_fn) config_path_cmp, 0);\n-\thashmap_init(&cache->for_name, (hashmap_cmp_fn) config_name_cmp, 0);\n+\thashmap_init(&cache->for_path, (hashmap_cmp_fn) config_path_cmp, NULL, 0);\n+\thashmap_init(&cache->for_name, (hashmap_cmp_fn) config_name_cmp, NULL, 0);\n }\n \n static void free_one_config(struct submodule_entry *entry)\ndiff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c\nindex 7aa9440e27..72cdc4a6b1 100644\n--- a/t/helper/test-hashmap.c\n+++ b/t/helper/test-hashmap.c\n@@ -14,13 +14,17 @@ static const char *get_value(const struct test_entry *e)\n }\n \n static int test_entry_cmp(const struct test_entry *e1,\n-\t\tconst struct test_entry *e2, const char* key)\n+\t\t\t  const struct test_entry *e2,\n+\t\t\t  const char* key,\n+\t\t\t  const void *unused_data)\n {\n \treturn strcmp(e1->key, key ? key : e2->key);\n }\n \n static int test_entry_cmp_icase(const struct test_entry *e1,\n-\t\tconst struct test_entry *e2, const char* key)\n+\t\t\t\tconst struct test_entry *e2,\n+\t\t\t\tconst char* key,\n+\t\t\t\tconst void *unused_data)\n {\n \treturn strcasecmp(e1->key, key ? key : e2->key);\n }\n@@ -92,7 +96,8 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\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+\t\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp,\n+\t\t\t\t     NULL, 0);\n \n \t\t\t/* add entries */\n \t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n@@ -104,7 +109,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\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+\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, NULL, 0);\n \n \t\t/* fill the map (sparsely if specified) */\n \t\tj = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;\n@@ -147,7 +152,7 @@ int cmd_main(int argc, const char **argv)\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+\t\t\t: test_entry_cmp), NULL, 0);\n \n \t/* process commands from stdin */\n \twhile (fgets(line, sizeof(line), stdin)) {\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323473","messageId":"20170629011334.11173-3-sbeller@google.com","threadId":"46284","inReplyTo":"20170629011334.11173-1-sbeller@google.com","subject":"[PATCH 2/2] hashmap: migrate documentation from Documentation/technical into header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T01:13:34Z","receivedAt":"2017-06-29T01:13:51Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"While at it, clarify the use of `key`, `keydata`, `entry_or_key` as well\nas documenting the new data pointer for the compare function.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/technical/api-hashmap.txt | 309 --------------------------------\n hashmap.h                               | 249 +++++++++++++++++++++++--\n 2 files changed, 231 insertions(+), 327 deletions(-)\n delete mode 100644 Documentation/technical/api-hashmap.txt\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\ndeleted file mode 100644\nindex ccc634bbd7..0000000000\n--- a/Documentation/technical/api-hashmap.txt\n+++ /dev/null\n@@ -1,309 +0,0 @@\n-hashmap API\n-===========\n-\n-The hashmap API is a generic implementation of hash-based key-value mappings.\n-\n-Data Structures\n----------------\n-\n-`struct hashmap`::\n-\n-\tThe hash table structure. 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 (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-When `disallow_rehash` is set, automatic rehashes are prevented during inserts\n-and deletes.\n-\n-`struct hashmap_entry`::\n-\n-\tAn opaque structure representing an entry in the hash table, which must\n-\tbe used as first member of user data structures. Ideally it should be\n-\tfollowed by an int-sized member to prevent unused memory on 64-bit\n-\tsystems due to alignment.\n-+\n-The `hash` member is the entry's hash code and the `next` member points to the\n-next entry in case of collisions (i.e. if multiple entries map to the same\n-bucket).\n-\n-`struct hashmap_iter`::\n-\n-\tAn iterator structure, to be used with hashmap_iter_* functions.\n-\n-Types\n------\n-\n-`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::\n-\n-\tUser-supplied function to test two hashmap entries for equality. Shall\n-\treturn 0 if the entries are equal.\n-+\n-This function is always called with non-NULL `entry` / `entry_or_key`\n-parameters that have the same hash code. When looking up an entry, the `key`\n-and `keydata` parameters to hashmap_get and hashmap_remove are always passed\n-as second and third argument, respectively. Otherwise, `keydata` is NULL.\n-\n-Functions\n----------\n-\n-`unsigned int strhash(const char *buf)`::\n-`unsigned int strihash(const char *buf)`::\n-`unsigned int memhash(const void *buf, size_t len)`::\n-`unsigned int memihash(const void *buf, size_t len)`::\n-`unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)`::\n-\n-\tReady-to-use hash functions for strings, using the FNV-1 algorithm (see\n-\thttp://www.isthe.com/chongo/tech/comp/fnv).\n-+\n-`strhash` and `strihash` take 0-terminated strings, while `memhash` and\n-`memihash` operate on arbitrary-length memory.\n-+\n-`strihash` and `memihash` are case insensitive versions.\n-+\n-`memihash_cont` is a variant of `memihash` that allows a computation to be\n-continued with another chunk of data.\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.\n-+\n-`map` is the hashmap to initialize.\n-+\n-The `equals_function` can be specified to compare two entries for equality.\n-If NULL, entries are considered equal if their hash codes are equal.\n-+\n-If the total number of entries is known in advance, the `initial_size`\n-parameter may be used to preallocate a sufficiently large table and thus\n-prevent expensive resizing. If 0, the table is dynamically resized.\n-\n-`void hashmap_free(struct hashmap *map, int free_entries)`::\n-\n-\tFrees a hashmap structure and allocated memory.\n-+\n-`map` is the hashmap to free.\n-+\n-If `free_entries` is true, each hashmap_entry in the map is freed as well\n-(using stdlib's free()).\n-\n-`void hashmap_entry_init(void *entry, unsigned int hash)`::\n-\n-\tInitializes a hashmap_entry structure.\n-+\n-`entry` points to the entry to initialize.\n-+\n-`hash` is the hash code of the entry.\n-+\n-The hashmap_entry structure does not hold references to external resources,\n-and it is safe to just discard it once you are done with it (i.e. if\n-your structure was allocated with xmalloc(), you can just free(3) it,\n-and if it is on stack, you can just let it go out of scope).\n-\n-`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::\n-\n-\tReturns the hashmap entry for the specified key, or NULL if not found.\n-+\n-`map` is the hashmap structure.\n-+\n-`key` is a hashmap_entry structure (or user data structure that starts with\n-hashmap_entry) that has at least been initialized with the proper hash code\n-(via `hashmap_entry_init`).\n-+\n-If an entry with matching hash code is found, `key` and `keydata` are passed\n-to `hashmap_cmp_fn` to decide whether the entry matches the key.\n-\n-`void *hashmap_get_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\n-\tused to iterate over duplicate entries (see `hashmap_add`).\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the hashmap_entry to start the search from, obtained via a previous\n-call to `hashmap_get` or `hashmap_get_next`.\n-\n-`void hashmap_add(struct hashmap *map, void *entry)`::\n-\n-\tAdds a hashmap entry. This allows to add duplicate entries (i.e.\n-\tseparate values with the same key according to hashmap_cmp_fn).\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the entry to add.\n-\n-`void *hashmap_put(struct hashmap *map, void *entry)`::\n-\n-\tAdds or replaces a hashmap entry. If the hashmap contains duplicate\n-\tentries equal to the specified entry, only one of them will be replaced.\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the entry to add or replace.\n-+\n-Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n-\n-`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::\n-\n-\tRemoves a hashmap entry matching the specified key. If the hashmap\n-\tcontains duplicate entries equal to the specified key, only one of\n-\tthem will be removed.\n-+\n-`map` is the hashmap structure.\n-+\n-`key` is a hashmap_entry structure (or user data structure that starts with\n-hashmap_entry) that has at least been initialized with the proper hash code\n-(via `hashmap_entry_init`).\n-+\n-If an entry with matching hash code is found, `key` and `keydata` are\n-passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n-+\n-Returns the removed entry, or NULL if not found.\n-\n-`void hashmap_disallow_rehash(struct hashmap *map, unsigned value)`::\n-\n-\tDisallow/allow automatic rehashing of the hashmap during inserts\n-\tand deletes.\n-+\n-This is useful if the caller knows that the hashmap will be accessed\n-by multiple threads.\n-+\n-The caller is still responsible for any necessary locking; this simply\n-prevents unexpected rehashing.  The caller is also responsible for properly\n-sizing the initial hashmap to ensure good performance.\n-+\n-A call to allow rehashing does not force a rehash; that might happen\n-with the next insert or delete.\n-\n-`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::\n-`void *hashmap_iter_next(struct hashmap_iter *iter)`::\n-`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::\n-\n-\tUsed to iterate over all entries of a hashmap. Note that it is\n-\tnot safe to add or remove entries to the hashmap while\n-\titerating.\n-+\n-`hashmap_iter_init` initializes a `hashmap_iter` structure.\n-+\n-`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no\n-more entries.\n-+\n-`hashmap_iter_first` is a combination of both (i.e. initializes the iterator\n-and returns the first entry, if any).\n-\n-`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-Here's a simple usage example that maps long keys to double values.\n-------------\n-struct hashmap map;\n-\n-struct long2double {\n-\tstruct hashmap_entry ent; /* must be the first member! */\n-\tlong key;\n-\tdouble value;\n-};\n-\n-static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)\n-{\n-\treturn !(e1->key == e2->key);\n-}\n-\n-void long2double_init(void)\n-{\n-\thashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);\n-}\n-\n-void long2double_free(void)\n-{\n-\thashmap_free(&map, 1);\n-}\n-\n-static struct long2double *find_entry(long key)\n-{\n-\tstruct long2double k;\n-\thashmap_entry_init(&k, memhash(&key, sizeof(long)));\n-\tk.key = key;\n-\treturn hashmap_get(&map, &k, NULL);\n-}\n-\n-double get_value(long key)\n-{\n-\tstruct long2double *e = find_entry(key);\n-\treturn e ? e->value : 0;\n-}\n-\n-void set_value(long key, double value)\n-{\n-\tstruct long2double *e = find_entry(key);\n-\tif (!e) {\n-\t\te = malloc(sizeof(struct long2double));\n-\t\thashmap_entry_init(e, memhash(&key, sizeof(long)));\n-\t\te->key = key;\n-\t\thashmap_add(&map, e);\n-\t}\n-\te->value = value;\n-}\n-------------\n-\n-Using variable-sized keys\n--------------------------\n-\n-The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary\n-`hashmap_entry` structure as key to find the correct entry. If the key data is\n-variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable\n-to create a full-fledged entry structure on the heap and copy all the key data\n-into the structure.\n-\n-In this case, the `keydata` parameter can be used to pass\n-variable-sized key data directly to the comparison function, and the `key`\n-parameter can be a stripped-down, fixed size entry structure allocated on the\n-stack.\n-\n-See test-hashmap.c for an example using arbitrary-length strings as keys.\ndiff --git a/hashmap.h b/hashmap.h\nindex 1c26bbad5b..cd8c6f8ad3 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -3,11 +3,18 @@\n \n /*\n  * Generic implementation of hash-based key-value mappings.\n- * See Documentation/technical/api-hashmap.txt.\n+ *\n  */\n \n-/* FNV-1 functions */\n-\n+/*\n+ * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see\n+ * http://www.isthe.com/chongo/tech/comp/fnv).\n+ * `strhash` and `strihash` take 0-terminated strings, while `memhash` and\n+ * `memihash` operate on arbitrary-length memory.\n+ * `strihash` and `memihash` are case insensitive versions.\n+ * `memihash_cont` is a variant of `memihash` that allows a computation to be\n+ * continued with another chunk of data.\n+ */\n extern unsigned int strhash(const char *buf);\n extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n@@ -16,6 +23,15 @@ extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_\n \n static inline unsigned int sha1hash(const unsigned char *sha1)\n {\n+\t/*\n+\t * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n+\t * for use in hash tables. Cryptographic hashes are supposed to have\n+\t * uniform distribution, so in contrast to `memhash()`, this just copies\n+\t * the first `sizeof(int)` bytes without shuffling any bits. Note that\n+\t * the results will be different on big-endian and little-endian\n+\t * platforms, so they should not be stored or transferred over the net.\n+\t */\n+\n \t/*\n \t * Equivalent to 'return *(unsigned int *)sha1;', but safe on\n \t * platforms that don't support unaligned reads.\n@@ -25,62 +41,228 @@ static inline unsigned int sha1hash(const unsigned char *sha1)\n \treturn hash;\n }\n \n-/* data structures */\n-\n+/*\n+ * struct hashmap_entry is an opaque structure representing an entry in the\n+ * hash table, which must be used as first member of user data structures.\n+ * Ideally it should be followed by an int-sized member to prevent unused\n+ * memory on 64-bit systems due to alignment.\n+ */\n struct hashmap_entry {\n+\t/*\n+\t * next points to the next entry in case of collisions (i.e. if\n+\t * multiple entries map to the same bucket)\n+\t */\n \tstruct hashmap_entry *next;\n+\n+\t/* entry's hash code */\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.\n+ *\n+ * This function is always called with non-NULL `entry` and `entry_or_key`\n+ * parameters that have the same hash code.\n+ *\n+ * When looking up an entry, the `key` and `keydata` parameters to hashmap_get\n+ * and hashmap_remove are always passed\n+ * as second `entry_or_key` and third argument `keydata`, respectively.\n+ * Otherwise, `keydata` is NULL.\n+ *\n+ * There are two modes for this function to be used:\n+ * (a) When looking for an exact match of a given `entry`, then `keydata`\n+ *     ought to be NULL, and this function should cast `entry` and\n+ *     `entry_or_key` to the user entries and check for equality.\n+ * (b) When it is too expensive to allocate such a user entry (either because\n+ *     it is large or varialbe sized, such that it is not on the stack),\n+ *     Then the relevant data to check for equality should be passed via\n+ *     ` keydata`.\n+ *\n+ * Resulting from these modes, this function should compare `keydata` to `entry`\n+ * when `keydata` is not NULL. `entry_or_key` may be a bogus hashmap_entry (see\n+ * hashmap_get_from_hash).\n+ *\n+ * When `keydata` is NULL,`entry_or_key` is guaranteed to be a valid user supplied\n+ * entry, such that the comparision should be made between `entry` and\n+ * `entry_or_key`, both cast to the user type.\n+ *\n+ * The `data` entry is the pointer given in the init function and is always\n+ * given.\n+ */\n typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n-\t\tconst void *keydata, const void *cbdata);\n+\t\tconst void *keydata, const void *data);\n \n+/*\n+ * struct hashmap is the hash table structure. Members can be used as follows,\n+ * but should not be modified directly.\n+ */\n struct hashmap {\n \tstruct hashmap_entry **table;\n+\n+\t/* Stores the comparison function specified in `hashmap_init()`. */\n \thashmap_cmp_fn cmpfn;\n \tconst void *data;\n-\tunsigned int size, tablesize, grow_at, shrink_at;\n-\tunsigned disallow_rehash : 1;\n-};\n \n-struct hashmap_iter {\n-\tstruct hashmap *map;\n-\tstruct hashmap_entry *next;\n-\tunsigned int tablepos;\n+\t/* total number of entries (0 means the hashmap is empty) */\n+\tunsigned int size;\n+\n+\t/*\n+\t * tablesize is the allocated size of the hash table. A non-0 value\n+\t * indicates that the hashmap is initialized. It may also be useful\n+\t * for statistical purposes (i.e. `size / tablesize` is the current\n+\t * load factor).\n+\t */\n+\tunsigned int tablesize;\n+\n+\tunsigned int grow_at;\n+\tunsigned int shrink_at;\n+\n+\t/* Prevent automatic rehashes during inserts and deletes when set. */\n+\tunsigned disallow_rehash : 1;\n };\n \n /* hashmap functions */\n \n+/*\n+ * Initializes a hashmap structure.\n+ *\n+ * `map` is the hashmap to initialize.\n+ *\n+ * The `equals_function` can be specified to compare two entries for equality.\n+ * If NULL, entries are considered equal if their hash codes are equal.\n+ *\n+ * When the compare function needs specific user supplied `data`, it should\n+ * be given in `data`. It will be passed to the compare function in each call.\n+ *\n+ * If the total number of entries is known in advance, the `initial_size`\n+ * parameter may be used to preallocate a sufficiently large table and thus\n+ * prevent expensive resizing. If 0, the table is dynamically resized.\n+ */\n extern void hashmap_init(struct hashmap *map,\n \t\t\t hashmap_cmp_fn equals_function,\n \t\t\t const void *data,\n \t\t\t size_t initial_size);\n+\n+/*\n+ * Frees a hashmap structure and allocated memory.\n+ *\n+ * If `free_entries` is true, each hashmap_entry in the map is freed as well.\n+ */\n extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\n \n+/*\n+ * Initializes a hashmap_entry structure.\n+ *\n+ * `entry` points to the entry to initialize.\n+ * `hash` is the hash code of the entry.\n+ *\n+ * The hashmap_entry structure does not hold references to external resources,\n+ * and it is safe to just discard it once you are done with it (i.e. if\n+ * your structure was allocated with xmalloc(), you can just free(3) it,\n+ * and if it is on stack, you can just let it go out of scope).\n+ */\n static inline void hashmap_entry_init(void *entry, unsigned int hash)\n {\n \tstruct hashmap_entry *e = entry;\n \te->hash = hash;\n \te->next = NULL;\n }\n+\n+/*\n+ * Returns the hashmap entry for the specified key, or NULL if not found.\n+ *\n+ * `map` is the hashmap structure.\n+ * `key` is a user data structure that starts with hashmap_entry that has at\n+ *  least been initialized with the proper hash code (via `hashmap_entry_init`).\n+ * `keydata` is a data structure that holds just enough information to check\n+ * for equality to a given entry.\n+ *\n+ * One of `key` or `keydata` shall be NULL.\n+ *\n+ * If an entry with matching hash code is found, `key` and `keydata` are passed\n+ * to `hashmap_cmp_fn` to decide whether the entry matches the key.\n+ */\n extern void *hashmap_get(const struct hashmap *map, const void *key,\n-\t\tconst void *keydata);\n+\t\t\t const void *keydata);\n+\n+/*\n+ * Returns the next equal hashmap entry, or NULL if not found. This can be\n+ * used to iterate over duplicate entries (see `hashmap_add`).\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the hashmap_entry to start the search from, obtained via a previous\n+ * call to `hashmap_get` or `hashmap_get_next`.\n+ */\n 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.\n+ * separate values with the same key according to hashmap_cmp_fn).\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the entry to add.\n+ */\n extern void hashmap_add(struct hashmap *map, void *entry);\n+\n+/*\n+ * Adds or replaces a hashmap entry. If the hashmap contains duplicate\n+ * entries equal to the specified entry, only one of them will be replaced.\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the entry to add or replace.\n+ * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n+ */\n extern void *hashmap_put(struct hashmap *map, void *entry);\n+\n+/*\n+ * Removes a hashmap entry matching the specified key. If the hashmap\n+ * contains duplicate entries equal to the specified key, only one of\n+ * them will be removed.\n+ *\n+ * `map` is the hashmap structure.\n+ * `key` is a user data structure that starts with hashmap_entry that has at\n+ *  least been initialized with the proper hash code (via `hashmap_entry_init`).\n+ * `keydata` is a data structure that holds just enough information to check\n+ * for equality to a given entry.\n+ *\n+ * One of `key` or `keydata` shall be NULL.\n+ *\n+ * If an entry with matching hash code is found, `key` and `keydata` are\n+ * passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n+ *\n+ * Returns the removed entry, or NULL if not found.\n+ */\n extern void *hashmap_remove(struct hashmap *map, const void *key,\n \t\tconst void *keydata);\n \n+/*\n+ * Returns the hashmap entry for the specified hash code and key data,\n+ * or NULL if not found.\n+ *\n+ * `map` is the hashmap structure.\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 static inline void *hashmap_get_from_hash(const struct hashmap *map,\n-\t\tunsigned int hash, const void *keydata)\n+\t\t\t\t\t  unsigned int hash,\n+\t\t\t\t\t  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+/*\n+ * Returns the `bucket` an entry is stored in.\n+ * Useful for multithreaded read access.\n+ */\n int hashmap_bucket(const struct hashmap *map, unsigned int hash);\n \n /*\n@@ -91,7 +273,7 @@ int hashmap_bucket(const struct hashmap *map, unsigned int hash);\n  * manner appropriate to their usage.  This simply\n  * prevents the table from being unexpectedly re-mapped.\n  *\n- * If is up to the caller to ensure that the hashmap is\n+ * It is up to the caller to ensure that the hashmap is\n  * initialized to a reasonable size to prevent poor\n  * performance.\n  *\n@@ -104,10 +286,28 @@ static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)\n \tmap->disallow_rehash = value;\n }\n \n-/* hashmap_iter functions */\n \n+/*\n+ * hashmap_iter functions\n+ *\n+ * Used to iterate over all entries of a hashmap. Note that it is\n+ * not safe to add or remove entries to the hashmap while\n+ * iterating.\n+ */\n+\n+struct hashmap_iter {\n+\tstruct hashmap *map;\n+\tstruct hashmap_entry *next;\n+\tunsigned int tablepos;\n+};\n+\n+/* Initializes a `hashmap_iter` structure. */\n extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n+\n+/* Returns the next hashmap_entry, or NULL if there are no more entries. */\n extern void *hashmap_iter_next(struct hashmap_iter *iter);\n+\n+/* Initializes the iterator and returns the first entry, if any). */\n static inline void *hashmap_iter_first(struct hashmap *map,\n \t\tstruct hashmap_iter *iter)\n {\n@@ -115,8 +315,21 @@ static inline void *hashmap_iter_first(struct hashmap *map,\n \treturn hashmap_iter_next(iter);\n }\n \n-/* string interning */\n+/* String interning */\n \n+/*\n+ * Returns the unique, interned version of the specified string or data,\n+ * similar to the `String.intern` API in Java and .NET, respectively.\n+ * Interned 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 extern const void *memintern(const void *data, size_t len);\n static inline const char *strintern(const char *string)\n {\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323476","messageId":"0749bca3-a2b7-7314-b9fb-2217390b919e@jeffhostetler.com","threadId":"46284","inReplyTo":"20170629011334.11173-3-sbeller@google.com","subject":"Re: [PATCH 2/2] hashmap: migrate documentation from Documentation/technical into header","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-06-29T13:25:07Z","receivedAt":"2017-06-29T13:25:13Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 6/28/2017 9:13 PM, Stefan Beller wrote:\n> While at it, clarify the use of `key`, `keydata`, `entry_or_key` as well\n> as documenting the new data pointer for the compare function.\n> \n> Signed-off-by: Stefan Beller <sbeller@google.com>\n> ---\n>   Documentation/technical/api-hashmap.txt | 309 --------------------------------\n>   hashmap.h                               | 249 +++++++++++++++++++++++--\n>   2 files changed, 231 insertions(+), 327 deletions(-)\n>   delete mode 100644 Documentation/technical/api-hashmap.txt\n > ...\n\nThis looks very nice. Thank you!\n\nJeff\n"},{"id":"323485","messageId":"xmqqvaneu0qy.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"20170629011334.11173-2-sbeller@google.com","subject":"Re: [PATCH 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-29T18:06:45Z","receivedAt":"2017-06-29T18:06:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> When using the hashmap a common need is to have access to arbitrary data\n> in the compare function. A couple of times we abuse the keydata field\n> to pass in the data needed. This happens for example in patch-ids.c.\n\nIt is not \"arbitrary data\"; it is very important to streess that we\nare not just passing random crud, but adding a mechansim to\ntailor/curry the function in a way that is fixed throughout the\nlifetime of a hashmap.\n\nI haven't looked at the use of keydata in patch-ids.c and friends to\ndecide if that \"abuse\" claim is correct; if it were the case, should\nwe expect that a follow-up patch to clean up the existing mess by\nusing the new mechanism?  Or does fixing the \"abuse\" take another\nmechanism that is different from this one?\n\n> While at it improve the naming of the fields of all compare functions used\n> by hashmaps by ensuring unused parameters are prefixed with 'unused_' and\n> naming the parameters what they are (instead of 'unused' make it\n> 'unused_keydata').\n>\n> Signed-off-by: Stefan Beller <sbeller@google.com>\n> ---\n\n> diff --git a/hashmap.h b/hashmap.h\n> index de6022a3a9..1c26bbad5b 100644\n> --- a/hashmap.h\n> +++ b/hashmap.h\n> @@ -33,11 +33,12 @@ struct hashmap_entry {\n>  };\n>  \n>  typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n> -\t\tconst void *keydata);\n> +\t\tconst void *keydata, const void *cbdata);\n\nAs I view the new \"data\" thing the C's (read: poor-man's) way to\ncutomize the function, I would have tweaked the function signature\nby giving the customization data at the front, i.e.\n\n\tfn(fndata, entry, entry_or_key, keydata);\n\nas I think the way we wish to be able to express it in\na better language would have been something like:\n\n\t(partial_apply(fn, fndata))(entry, entry_or_key, keydata)\n\nBut what you did is OK, too.\n\n> +extern void hashmap_init(struct hashmap *map,\n> +\t\t\t hashmap_cmp_fn equals_function,\n> +\t\t\t const void *data,\n> +\t\t\t size_t initial_size);\n\nAnd this does match my expectation ;-).\n"},{"id":"323486","messageId":"xmqqr2y2u0jq.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"xmqqvaneu0qy.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-29T18:11:05Z","receivedAt":"2017-06-29T18:11:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> I haven't looked at the use of keydata in patch-ids.c and friends to\n> decide if that \"abuse\" claim is correct; if it were the case, should\n> we expect that a follow-up patch to clean up the existing mess by\n> using the new mechanism?  Or does fixing the \"abuse\" take another\n> mechanism that is different from this one?\n\nI see that you corrected patch-ids.c \"while at it\".  That may make\nit harder to revert only that \"while at it\", I suspect.\n\nThanks.\n"},{"id":"323489","messageId":"CAGZ79kaP3rDRNVQRk3_egZrY54Ra3eaOGCPpufp+y936=6kPQw@mail.gmail.com","threadId":"46284","inReplyTo":"xmqqr2y2u0jq.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T18:20:51Z","receivedAt":"2017-06-29T18:20:56Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jun 29, 2017 at 11:11 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n>\n>> I haven't looked at the use of keydata in patch-ids.c and friends to\n>> decide if that \"abuse\" claim is correct; if it were the case, should\n>> we expect that a follow-up patch to clean up the existing mess by\n>> using the new mechanism?  Or does fixing the \"abuse\" take another\n>> mechanism that is different from this one?\n>\n> I see that you corrected patch-ids.c \"while at it\".  That may make\n> it harder to revert only that \"while at it\", I suspect.\n>\n> Thanks.\n\nYes it was a last minute squash before sending it out, as the fix was only\ntwo lines whereas the conversion is a lot. If it were separated I could have\nclaimed the introduction to be a rather mechanical patch, but I did not\nmake use of coccinelle or such, so the likelihood for errors is just as high.\n\nSo I decided to squash them.\n\nThanks,\nStefan\n"},{"id":"323499","messageId":"20170629211832.GB68015@aiede.mtv.corp.google.com","threadId":"46284","inReplyTo":"20170629011334.11173-3-sbeller@google.com","subject":"Re: [PATCH 2/2] hashmap: migrate documentation from Documentation/technical into header","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-06-29T21:18:32Z","receivedAt":"2017-06-29T21:18:44Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Stefan Beller wrote:\n\n> Subject: hashmap: migrate documentation from Documentation/technical into header\n>\n> While at it, clarify the use of `key`, `keydata`, `entry_or_key` as well\n> as documenting the new data pointer for the compare function.\n>\n> Signed-off-by: Stefan Beller <sbeller@google.com>\n> ---\n>  Documentation/technical/api-hashmap.txt | 309 --------------------------------\n>  hashmap.h                               | 249 +++++++++++++++++++++++--\n>  2 files changed, 231 insertions(+), 327 deletions(-)\n>  delete mode 100644 Documentation/technical/api-hashmap.txt\n\nYay, I love this.\n\n[...]\n> --- a/Documentation/technical/api-hashmap.txt\n> +++ /dev/null\n> @@ -1,309 +0,0 @@\n\nVerified that these docs have all been migrated to the header, except\nwhere noted below.\n\n[...]\n> -`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::\n> -\n> -\tUser-supplied function to test two hashmap entries for equality. Shall\n> -\treturn 0 if the entries are equal.\n> -+\n> -This function is always called with non-NULL `entry` / `entry_or_key`\n> -parameters that have the same hash code. When looking up an entry, the `key`\n> -and `keydata` parameters to hashmap_get and hashmap_remove are always passed\n> -as second and third argument, respectively. Otherwise, `keydata` is NULL.\n\nThis was really heard to read in the preimage.  Thanks for cleaning it up.\n\n[...]\n> -Usage example\n> --------------\n> -\n> -Here's a simple usage example that maps long keys to double values.\n\nWhat happened to this?  I think it would be useful to include in a\nlong comment at the top of the header.  A worked example like this\nmakes it easier to get one's bearings and know which functions to look\nat.\n\n[...]\n> -Using variable-sized keys\n> --------------------------\n\nSame question: should this discussion go in the hashmap_get()\ndocstring, with a pointer from hashmap_remove()?  Or should it go in\ntest-hashmap.c, with a pointer in the docstrings of both?\n\n[...]\n> +++ b/hashmap.h\n> @@ -3,11 +3,18 @@\n>  \n>  /*\n>   * Generic implementation of hash-based key-value mappings.\n> - * See Documentation/technical/api-hashmap.txt.\n> + *\n>   */\n\nnit: why the blank line?\n\n>  \n> -/* FNV-1 functions */\n> -\n> +/*\n> + * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see\n> + * http://www.isthe.com/chongo/tech/comp/fnv).\n> + * `strhash` and `strihash` take 0-terminated strings, while `memhash` and\n> + * `memihash` operate on arbitrary-length memory.\n> + * `strihash` and `memihash` are case insensitive versions.\n> + * `memihash_cont` is a variant of `memihash` that allows a computation to be\n> + * continued with another chunk of data.\n> + */\n>  extern unsigned int strhash(const char *buf);\n>  extern unsigned int strihash(const char *buf);\n>  extern unsigned int memhash(const void *buf, size_t len);\n> @@ -16,6 +23,15 @@ extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_\n>  \n>  static inline unsigned int sha1hash(const unsigned char *sha1)\n>  {\n> +\t/*\n> +\t * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n> +\t * for use in hash tables. Cryptographic hashes are supposed to have\n> +\t * uniform distribution, so in contrast to `memhash()`, this just copies\n> +\t * the first `sizeof(int)` bytes without shuffling any bits. Note that\n> +\t * the results will be different on big-endian and little-endian\n> +\t * platforms, so they should not be stored or transferred over the net.\n> +\t */\n\nThis comment should go in front of the function instead of in its body, like this:\n\n\t/*\n\t * Converts a crypto [...]\n\t */\n\tstatic inline unsigned int sha1hash(...\n\nbecause it is describing the purpose and usage of the function and not\nits implementation.\n\n[...]\n> +/*\n> + * User-supplied function to test two hashmap entries for equality. Shall\n> + * return 0 if the entries are equal.\n> + *\n> + * This function is always called with non-NULL `entry` and `entry_or_key`\n> + * parameters that have the same hash code.\n> + *\n> + * When looking up an entry, the `key` and `keydata` parameters to hashmap_get\n> + * and hashmap_remove are always passed\n> + * as second `entry_or_key` and third argument `keydata`, respectively.\n> + * Otherwise, `keydata` is NULL.\n\nstrange wrapping\n\n> + *\n> + * There are two modes for this function to be used:\n> + * (a) When looking for an exact match of a given `entry`, then `keydata`\n> + *     ought to be NULL, and this function should cast `entry` and\n> + *     `entry_or_key` to the user entries and check for equality.\n\nWhat does it mean that `keydata` ought to be NULL?  Are you saying it\nwill be NULL, or that someone has to ensure it's NULL, or something\nelse?\n\n> + * (b) When it is too expensive to allocate such a user entry (either because\n> + *     it is large or varialbe sized, such that it is not on the stack),\n> + *     Then the relevant data to check for equality should be passed via\n> + *     ` keydata`.\n\nstray space in \"` keydata`\".\n\n> + *\n> + * Resulting from these modes, this function should compare `keydata` to `entry`\n> + * when `keydata` is not NULL. `entry_or_key` may be a bogus hashmap_entry (see\n> + * hashmap_get_from_hash).\n\nWhat is meant by a bogus hashmap_entry here?  (See also below.)\n\n[...]\n> +/*\n> + * struct hashmap is the hash table structure. Members can be used as follows,\n> + * but should not be modified directly.\n> + */\n>  struct hashmap {\n[...]\n> +\t/* Prevent automatic rehashes during inserts and deletes when set. */\n> +\tunsigned disallow_rehash : 1;\n>  };\n\nPlease add a reference to hashmap_disallow_rehash so people know how\nto set this.\n\n>  \n>  /* hashmap functions */\n>  \n> +/*\n> + * Initializes a hashmap structure.\n> + *\n> + * `map` is the hashmap to initialize.\n> + *\n> + * The `equals_function` can be specified to compare two entries for equality.\n> + * If NULL, entries are considered equal if their hash codes are equal.\n> + *\n> + * When the compare function needs specific user supplied `data`, it should\n\nnit: it's not user supplied so much as caller supplied.  Maybe this\ncan say something like\n\n\tThe `data` parameter can be used to provide additional data (a callback\n\tcookie) that will be passed to `equals_function` each time it is called.\n\tThis allows a single `equals_function` to implement multiple comparison\n\tfunctions.\n\n[...]\n> +/*\n> + * Frees a hashmap structure and allocated memory.\n> + *\n> + * If `free_entries` is true, each hashmap_entry in the map is freed as well.\n> + */\n\nnit: Documentation/technical said the hashmap_entrys get freed using\nfree().  Can't hurt to carry that note over, to save the reader from\nhunting down whether the struct hashmap allows setting a custom free\nfunction.\n\n[...]\n> +/*\n> + * Returns the hashmap entry for the specified key, or NULL if not found.\n> + *\n> + * `map` is the hashmap structure.\n> + * `key` is a user data structure that starts with hashmap_entry that has at\n> + *  least been initialized with the proper hash code (via `hashmap_entry_init`).\n\nnit: strange alignment (extra space before \"least\").\n\nShould these argument lists be formatted as a list somehow (e.g. leading\n\"- \" bullets, or with a blank line between them?  (I don't have a\nstrong opinion, just noticed they can be hard to read with everything\nrun together.)\n\n> + * `keydata` is a data structure that holds just enough information to check\n> + * for equality to a given entry.\n> + *\n> + * One of `key` or `keydata` shall be NULL.\n> + *\n> + * If an entry with matching hash code is found, `key` and `keydata` are passed\n> + * to `hashmap_cmp_fn` to decide whether the entry matches the key.\n> + */\n>  extern void *hashmap_get(const struct hashmap *map, const void *key,\n[...]\n> + * Removes a hashmap entry matching the specified key. If the hashmap\n> + * contains duplicate entries equal to the specified key, only one of\n> + * them will be removed.\n> + *\n> + * `map` is the hashmap structure.\n> + * `key` is a user data structure that starts with hashmap_entry that has at\n> + *  least been initialized with the proper hash code (via `hashmap_entry_init`).\n\nnit: strange alignment again\n\n[...]\n>  extern void *hashmap_remove(struct hashmap *map, const void *key,\n[...]\n> +/*\n> + * Returns the hashmap entry for the specified hash code and key data,\n> + * or NULL if not found.\n> + *\n> + * `map` is the hashmap structure.\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\nWhat is going on with this note about bogus entry_or_key?  I have no\nidea what it is trying to say, neither in the preimage nor the\npostimage.\n\n> + */\n>  static inline void *hashmap_get_from_hash(const struct hashmap *map,\n> -\t\tunsigned int hash, const void *keydata)\n> +\t\t\t\t\t  unsigned int hash,\n> +\t\t\t\t\t  const void *keydata)\n\nIn Documentation/technical, hashmap_get_from_hash was immediately\nafter hashmap_get, making it more discoverable.\n\nShould the descriptions of these two functions mention each other to\nbring about a similar effect?\n\n[...]\n> @@ -91,7 +273,7 @@ int hashmap_bucket(const struct hashmap *map, unsigned int hash);\n>   * manner appropriate to their usage.  This simply\n>   * prevents the table from being unexpectedly re-mapped.\n>   *\n> - * If is up to the caller to ensure that the hashmap is\n> + * It is up to the caller to ensure that the hashmap is\n>   * initialized to a reasonable size to prevent poor\n>   * performance.\n>   *\n\nThe Documentation/technical/ text says:\n\n\tA call to allow rehashing does not force a rehash; that might happen\n\twith the next insert or delete.\n\nwhich I find easier on the eyes than\n\n\t * When value=0, allow future rehahses.  This DOES NOT force\n\t * a rehash now.\n\nWhy not make this comment use the full description from\nDocumentation/technical/ verbatim?\n\n> @@ -104,10 +286,28 @@ static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)\n[...]\n> -/* hashmap_iter functions */\n>  \n> +/*\n> + * hashmap_iter functions\n> + *\n> + * Used to iterate over all entries of a hashmap. Note that it is\n> + * not safe to add or remove entries to the hashmap while\n> + * iterating.\n> + */\n> +\n> +struct hashmap_iter {\n\nnit: might be simpler to associate this comment with the struct:\n\n\t/*\n\t * Used to iterate over ...\n\t */\n\tstruct hashmap_iter {\n\t\t...\n\t}\n\nThat way, the scope of what the comment is describing is clearer.\nWhen looking up the functions, I'm likely to look up the hashmap_iter\ntype they use, so I'd end up reading this comment anyway.\n\n> +\tstruct hashmap *map;\n> +\tstruct hashmap_entry *next;\n> +\tunsigned int tablepos;\n> +};\n> +\n> +/* Initializes a `hashmap_iter` structure. */\n>  extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n> +\n> +/* Returns the next hashmap_entry, or NULL if there are no more entries. */\n>  extern void *hashmap_iter_next(struct hashmap_iter *iter);\n> +\n> +/* Initializes the iterator and returns the first entry, if any). */\n\nStray paren?\n\nProbably worth mentioning this is a convenience wrapper for iter_init\n+ iter_next, like the Documentation/technical/ text did.\n\n>  static inline void *hashmap_iter_first(struct hashmap *map,\n\nThe rest looks good.\n\nThanks and hope that helps,\nJonathan\n"},{"id":"323511","messageId":"CAGZ79kb8PJpEu+Wq_+JG208xXcJpoPMJe26xXN-Gck3L0G2yrw@mail.gmail.com","threadId":"46284","inReplyTo":"20170629211832.GB68015@aiede.mtv.corp.google.com","subject":"Re: [PATCH 2/2] hashmap: migrate documentation from Documentation/technical into header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T23:41:20Z","receivedAt":"2017-06-29T23:41:26Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Took all suggestions so far, but the last one:\n\n>\n> Probably worth mentioning this is a convenience wrapper for iter_init\n> + iter_next, like the Documentation/technical/ text did.\n\nNo. The code to observe that this is a convenience wrapper\nIS RIGHT THERE (it's a header file), and I find this header a\nbit bloated already. So I'll keep it as a one liner.\n"},{"id":"323513","messageId":"20170629235336.28460-2-sbeller@google.com","threadId":"46284","inReplyTo":"20170629235336.28460-1-sbeller@google.com","subject":"[PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T23:53:35Z","receivedAt":"2017-06-29T23:53:50Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"When using the hashmap a common need is to have access to arbitrary data\nin the compare function. A couple of times we abuse the keydata field\nto pass in the data needed. This happens for example in patch-ids.c.\n\nThis patch changes the function signature of the compare function\nto have one more void pointer available. The pointer given for each\ninvocation of the compare function must be defined in the init function\nof the hashmap and is just passed through.\n\nDocumentation of this new feature is deferred to a later patch.\n\nWhile at it improve the naming of the fields of all compare functions used\nby hashmaps by ensuring unused parameters are prefixed with 'unused_' and\nnaming the parameters what they are (instead of 'unused' make it\n'unused_keydata').\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n attr.c                  |  4 ++--\n builtin/describe.c      |  6 ++++--\n builtin/difftool.c      | 20 ++++++++++++--------\n builtin/fast-export.c   |  5 +++--\n config.c                |  7 +++++--\n convert.c               |  3 ++-\n diffcore-rename.c       |  2 +-\n hashmap.c               | 17 ++++++++++++-----\n hashmap.h               |  9 ++++++---\n name-hash.c             | 12 ++++++++----\n oidset.c                |  5 +++--\n patch-ids.c             |  6 ++++--\n refs.c                  |  4 ++--\n remote.c                |  7 +++++--\n sha1_file.c             |  5 +++--\n sub-process.c           |  5 +++--\n sub-process.h           |  6 ++++--\n submodule-config.c      | 10 ++++++----\n t/helper/test-hashmap.c | 15 ++++++++++-----\n 19 files changed, 95 insertions(+), 53 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex 37454999d2..2f51417675 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -78,7 +78,7 @@ struct attr_hash_entry {\n /* attr_hashmap comparison function */\n static int attr_hash_entry_cmp(const struct attr_hash_entry *a,\n \t\t\t       const struct attr_hash_entry *b,\n-\t\t\t       void *unused)\n+\t\t\t       void *unused_keydata, void *unused_data)\n {\n \treturn (a->keylen != b->keylen) || strncmp(a->key, b->key, a->keylen);\n }\n@@ -86,7 +86,7 @@ static int attr_hash_entry_cmp(const struct attr_hash_entry *a,\n /* Initialize an 'attr_hashmap' object */\n static void attr_hashmap_init(struct attr_hashmap *map)\n {\n-\thashmap_init(&map->map, (hashmap_cmp_fn) attr_hash_entry_cmp, 0);\n+\thashmap_init(&map->map, (hashmap_cmp_fn) attr_hash_entry_cmp, NULL, 0);\n }\n \n /*\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 70eb144608..a6c5a969a0 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -55,7 +55,9 @@ static const char *prio_names[] = {\n };\n \n static int commit_name_cmp(const struct commit_name *cn1,\n-\t\tconst struct commit_name *cn2, const void *peeled)\n+\t\t\t   const struct commit_name *cn2,\n+\t\t\t   const void *peeled,\n+\t\t\t   const void *unused_data)\n {\n \treturn oidcmp(&cn1->peeled, peeled ? peeled : &cn2->peeled);\n }\n@@ -501,7 +503,7 @@ 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-\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);\n+\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, NULL, 0);\n \tfor_each_rawref(get_name, NULL);\n \tif (!names.size && !always)\n \t\tdie(_(\"No names found, cannot describe anything.\"));\ndiff --git a/builtin/difftool.c b/builtin/difftool.c\nindex 9199227f6e..80786a95ab 100644\n--- a/builtin/difftool.c\n+++ b/builtin/difftool.c\n@@ -131,7 +131,9 @@ struct working_tree_entry {\n };\n \n static int working_tree_entry_cmp(struct working_tree_entry *a,\n-\t\t\t\t  struct working_tree_entry *b, void *keydata)\n+\t\t\t\t  struct working_tree_entry *b,\n+\t\t\t\t  void *unused_keydata,\n+\t\t\t\t  void *unused_data)\n {\n \treturn strcmp(a->path, b->path);\n }\n@@ -146,7 +148,8 @@ struct pair_entry {\n \tconst char path[FLEX_ARRAY];\n };\n \n-static int pair_cmp(struct pair_entry *a, struct pair_entry *b, void *keydata)\n+static int pair_cmp(struct pair_entry *a, struct pair_entry *b,\n+\t\t    void *unused_keydata, void *unused_data)\n {\n \treturn strcmp(a->path, b->path);\n }\n@@ -174,7 +177,8 @@ struct path_entry {\n \tchar path[FLEX_ARRAY];\n };\n \n-static int path_entry_cmp(struct path_entry *a, struct path_entry *b, void *key)\n+static int path_entry_cmp(struct path_entry *a, struct path_entry *b,\n+\t\t\t  void *key, void *unused_data)\n {\n \treturn strcmp(a->path, key ? key : b->path);\n }\n@@ -367,9 +371,9 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,\n \twtdir_len = wtdir.len;\n \n \thashmap_init(&working_tree_dups,\n-\t\t     (hashmap_cmp_fn)working_tree_entry_cmp, 0);\n-\thashmap_init(&submodules, (hashmap_cmp_fn)pair_cmp, 0);\n-\thashmap_init(&symlinks2, (hashmap_cmp_fn)pair_cmp, 0);\n+\t\t     (hashmap_cmp_fn)working_tree_entry_cmp, NULL, 0);\n+\thashmap_init(&submodules, (hashmap_cmp_fn)pair_cmp, NULL, 0);\n+\thashmap_init(&symlinks2, (hashmap_cmp_fn)pair_cmp, NULL, 0);\n \n \tchild.no_stdin = 1;\n \tchild.git_cmd = 1;\n@@ -580,9 +584,9 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,\n \t * files through the symlink.\n \t */\n \thashmap_init(&wt_modified, (hashmap_cmp_fn)path_entry_cmp,\n-\t\t     wtindex.cache_nr);\n+\t\t     NULL, wtindex.cache_nr);\n \thashmap_init(&tmp_modified, (hashmap_cmp_fn)path_entry_cmp,\n-\t\t     wtindex.cache_nr);\n+\t\t     NULL, wtindex.cache_nr);\n \n \tfor (i = 0; i < wtindex.cache_nr; i++) {\n \t\tstruct hashmap_entry dummy;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 12d501bfde..fa389fe252 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -94,7 +94,8 @@ struct anonymized_entry {\n };\n \n static int anonymized_entry_cmp(const void *va, const void *vb,\n-\t\t\t\tconst void *data)\n+\t\t\t\tconst void *unused_keydata,\n+\t\t\t\tconst void *unused_data)\n {\n \tconst struct anonymized_entry *a = va, *b = vb;\n \treturn a->orig_len != b->orig_len ||\n@@ -113,7 +114,7 @@ static const void *anonymize_mem(struct hashmap *map,\n \tstruct anonymized_entry key, *ret;\n \n \tif (!map->cmpfn)\n-\t\thashmap_init(map, anonymized_entry_cmp, 0);\n+\t\thashmap_init(map, anonymized_entry_cmp, NULL, 0);\n \n \thashmap_entry_init(&key, memhash(orig, *len));\n \tkey.orig = orig;\ndiff --git a/config.c b/config.c\nindex 1cd40a5fe6..aa0198a5fd 100644\n--- a/config.c\n+++ b/config.c\n@@ -1754,14 +1754,17 @@ static int configset_add_value(struct config_set *cs, const char *key, const cha\n }\n \n static int config_set_element_cmp(const struct config_set_element *e1,\n-\t\t\t\t const struct config_set_element *e2, const void *unused)\n+\t\t\t\t const struct config_set_element *e2,\n+\t\t\t\t const void *unused_keydata,\n+\t\t\t\t const void *unused_data)\n {\n \treturn strcmp(e1->key, e2->key);\n }\n \n void git_configset_init(struct config_set *cs)\n {\n-\thashmap_init(&cs->config_hash, (hashmap_cmp_fn)config_set_element_cmp, 0);\n+\thashmap_init(&cs->config_hash, (hashmap_cmp_fn)config_set_element_cmp,\n+\t\t     NULL, 0);\n \tcs->hash_initialized = 1;\n \tcs->list.nr = 0;\n \tcs->list.alloc = 0;\ndiff --git a/convert.c b/convert.c\nindex 7d2a519daf..deaf0ba7b3 100644\n--- a/convert.c\n+++ b/convert.c\n@@ -583,7 +583,8 @@ static int apply_multi_file_filter(const char *path, const char *src, size_t len\n \n \tif (!subprocess_map_initialized) {\n \t\tsubprocess_map_initialized = 1;\n-\t\thashmap_init(&subprocess_map, (hashmap_cmp_fn) cmd2process_cmp, 0);\n+\t\thashmap_init(&subprocess_map, (hashmap_cmp_fn) cmd2process_cmp,\n+\t\t\t     NULL, 0);\n \t\tentry = NULL;\n \t} else {\n \t\tentry = (struct cmd2process *)subprocess_find_entry(&subprocess_map, cmd);\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1e4678b7d7..786f389498 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -341,7 +341,7 @@ static int find_exact_renames(struct diff_options *options)\n \t/* Add all sources to the hash table in reverse order, because\n \t * later on they will be retrieved in LIFO order.\n \t */\n-\thashmap_init(&file_table, NULL, rename_src_nr);\n+\thashmap_init(&file_table, NULL, NULL, rename_src_nr);\n \tfor (i = rename_src_nr-1; i >= 0; i--)\n \t\tinsert_file_table(&file_table, i, rename_src[i].p->one);\n \ndiff --git a/hashmap.c b/hashmap.c\nindex 7d1044eb5d..82d70b329b 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -95,7 +95,9 @@ static inline int entry_equals(const struct hashmap *map,\n \t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2,\n \t\tconst void *keydata)\n {\n-\treturn (e1 == e2) || (e1->hash == e2->hash && !map->cmpfn(e1, e2, keydata));\n+\treturn (e1 == e2) ||\n+\t       (e1->hash == e2->hash &&\n+\t\t!map->cmpfn(e1, e2, keydata, map->data));\n }\n \n static inline unsigned int bucket(const struct hashmap *map,\n@@ -140,19 +142,23 @@ static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,\n \treturn e;\n }\n \n-static int always_equal(const void *unused1, const void *unused2, const void *unused3)\n+static int always_equal(const void *unused1,\n+\t\t\tconst void *unused2,\n+\t\t\tconst void *unused_keydata,\n+\t\t\tconst void *unused_data)\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+\t\tconst void *data, size_t initial_size)\n {\n \tunsigned int size = HASHMAP_INITIAL_SIZE;\n \n \tmemset(map, 0, sizeof(*map));\n \n \tmap->cmpfn = equals_function ? equals_function : always_equal;\n+\tmap->data = data;\n \n \t/* calculate initial table size and allocate the table */\n \tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n@@ -262,7 +268,8 @@ struct pool_entry {\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+\t\t\t  const unsigned char *keydata,\n+\t\t\t  const void *unused_data)\n {\n \treturn e1->data != keydata &&\n \t       (e1->len != e2->len || memcmp(e1->data, keydata, e1->len));\n@@ -275,7 +282,7 @@ const void *memintern(const void *data, size_t len)\n \n \t/* initialize string pool hashmap */\n \tif (!map.tablesize)\n-\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, 0);\n+\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0);\n \n \t/* lookup interned string in pool */\n \thashmap_entry_init(&key, memhash(data, len));\ndiff --git a/hashmap.h b/hashmap.h\nindex de6022a3a9..1c26bbad5b 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -33,11 +33,12 @@ struct hashmap_entry {\n };\n \n typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n-\t\tconst void *keydata);\n+\t\tconst void *keydata, const void *cbdata);\n \n struct hashmap {\n \tstruct hashmap_entry **table;\n \thashmap_cmp_fn cmpfn;\n+\tconst void *data;\n \tunsigned int size, tablesize, grow_at, shrink_at;\n \tunsigned disallow_rehash : 1;\n };\n@@ -50,8 +51,10 @@ struct hashmap_iter {\n \n /* hashmap functions */\n \n-extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n-\t\tsize_t initial_size);\n+extern void hashmap_init(struct hashmap *map,\n+\t\t\t hashmap_cmp_fn equals_function,\n+\t\t\t const void *data,\n+\t\t\t size_t initial_size);\n extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\ndiff --git a/name-hash.c b/name-hash.c\nindex 39309efb7f..4e9eac925a 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -17,7 +17,9 @@ struct dir_entry {\n };\n \n static int dir_entry_cmp(const struct dir_entry *e1,\n-\t\tconst struct dir_entry *e2, const char *name)\n+\t\t\t const struct dir_entry *e2,\n+\t\t\t const char *name,\n+\t\t\t const void *unused_data)\n {\n \treturn e1->namelen != e2->namelen || strncasecmp(e1->name,\n \t\t\tname ? name : e2->name, e1->namelen);\n@@ -108,7 +110,9 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n }\n \n static int cache_entry_cmp(const struct cache_entry *ce1,\n-\t\tconst struct cache_entry *ce2, const void *remove)\n+\t\t\t   const struct cache_entry *ce2,\n+\t\t\t   const void *remove,\n+\t\t\t   const void *unused_data)\n {\n \t/*\n \t * For remove_name_hash, find the exact entry (pointer equality); for\n@@ -571,9 +575,9 @@ static void lazy_init_name_hash(struct index_state *istate)\n \tif (istate->name_hash_initialized)\n \t\treturn;\n \thashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,\n-\t\t\tistate->cache_nr);\n+\t\t\tNULL, istate->cache_nr);\n \thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,\n-\t\t\tistate->cache_nr);\n+\t\t\tNULL, istate->cache_nr);\n \n \tif (lookup_lazy_params(istate)) {\n \t\thashmap_disallow_rehash(&istate->dir_hash, 1);\ndiff --git a/oidset.c b/oidset.c\nindex ac169f05d3..f20e6e4df3 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -7,7 +7,8 @@ struct oidset_entry {\n };\n \n static int oidset_hashcmp(const void *va, const void *vb,\n-\t\t\t  const void *vkey)\n+\t\t\t  const void *vkey,\n+\t\t\t  const void *unused_data)\n {\n \tconst struct oidset_entry *a = va, *b = vb;\n \tconst struct object_id *key = vkey;\n@@ -30,7 +31,7 @@ int oidset_insert(struct oidset *set, const struct object_id *oid)\n \tstruct oidset_entry *entry;\n \n \tif (!set->map.cmpfn)\n-\t\thashmap_init(&set->map, oidset_hashcmp, 0);\n+\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n \n \tif (oidset_contains(set, oid))\n \t\treturn 1;\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 9c0ab9e67a..b9b2ebbad0 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -37,6 +37,7 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n  */\n static int patch_id_cmp(struct patch_id *a,\n \t\t\tstruct patch_id *b,\n+\t\t\tconst void *unused_keydata,\n \t\t\tstruct diff_options *opt)\n {\n \tif (is_null_oid(&a->patch_id) &&\n@@ -57,7 +58,8 @@ int init_patch_ids(struct patch_ids *ids)\n \tids->diffopts.detect_rename = 0;\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n-\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n+\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n+\t\t     &ids->diffopts, 256);\n \treturn 0;\n }\n \n@@ -93,7 +95,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n \tif (init_patch_id_entry(&patch, commit, ids))\n \t\treturn NULL;\n \n-\treturn hashmap_get(&ids->patches, &patch, &ids->diffopts);\n+\treturn hashmap_get(&ids->patches, &patch, NULL);\n }\n \n struct patch_id *add_commit_patch_id(struct commit *commit,\ndiff --git a/refs.c b/refs.c\nindex 88658ba769..71e0170feb 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1526,7 +1526,7 @@ struct ref_store_hash_entry\n };\n \n static int ref_store_hash_cmp(const void *entry, const void *entry_or_key,\n-\t\t\t      const void *keydata)\n+\t\t\t      const void *keydata, const void *unused_data)\n {\n \tconst struct ref_store_hash_entry *e1 = entry, *e2 = entry_or_key;\n \tconst char *name = keydata ? keydata : e2->name;\n@@ -1608,7 +1608,7 @@ static void register_ref_store_map(struct hashmap *map,\n \t\t\t\t   const char *name)\n {\n \tif (!map->tablesize)\n-\t\thashmap_init(map, ref_store_hash_cmp, 0);\n+\t\thashmap_init(map, ref_store_hash_cmp, NULL, 0);\n \n \tif (hashmap_put(map, alloc_ref_store_hash_entry(name, refs)))\n \t\tdie(\"BUG: %s ref_store '%s' initialized twice\", type, name);\ndiff --git a/remote.c b/remote.c\nindex d87482573d..b5e05890ee 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -133,7 +133,10 @@ struct remotes_hash_key {\n \tint len;\n };\n \n-static int remotes_hash_cmp(const struct remote *a, const struct remote *b, const struct remotes_hash_key *key)\n+static int remotes_hash_cmp(const struct remote *a,\n+\t\t\t    const struct remote *b,\n+\t\t\t    const struct remotes_hash_key *key,\n+\t\t\t    const void *unused_data)\n {\n \tif (key)\n \t\treturn strncmp(a->name, key->str, key->len) || a->name[key->len];\n@@ -144,7 +147,7 @@ static int remotes_hash_cmp(const struct remote *a, const struct remote *b, cons\n static inline void init_remotes_hash(void)\n {\n \tif (!remotes_hash.cmpfn)\n-\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, 0);\n+\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, NULL, 0);\n }\n \n static struct remote *make_remote(const char *name, int len)\ndiff --git a/sha1_file.c b/sha1_file.c\nindex fb1fd809dc..b748db31ed 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2390,7 +2390,8 @@ static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,\n }\n \n static int delta_base_cache_hash_cmp(const void *va, const void *vb,\n-\t\t\t\t     const void *vkey)\n+\t\t\t\t     const void *vkey,\n+\t\t\t\t     const void *unused_data)\n {\n \tconst struct delta_base_cache_entry *a = va, *b = vb;\n \tconst struct delta_base_cache_key *key = vkey;\n@@ -2472,7 +2473,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tlist_add_tail(&ent->lru, &delta_base_cache_lru);\n \n \tif (!delta_base_cache.cmpfn)\n-\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, 0);\n+\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);\n \thashmap_entry_init(ent, pack_entry_hash(p, base_offset));\n \thashmap_add(&delta_base_cache, ent);\n }\ndiff --git a/sub-process.c b/sub-process.c\nindex 92f8aea70a..68b53cf48a 100644\n--- a/sub-process.c\n+++ b/sub-process.c\n@@ -6,8 +6,9 @@\n #include \"pkt-line.h\"\n \n int cmd2process_cmp(const struct subprocess_entry *e1,\n-\t\t\t   const struct subprocess_entry *e2,\n-\t\t\t   const void *unused)\n+\t\t    const struct subprocess_entry *e2,\n+\t\t    const void *unused_keydata,\n+\t\t    const void *unused_data)\n {\n \treturn strcmp(e1->cmd, e2->cmd);\n }\ndiff --git a/sub-process.h b/sub-process.h\nindex d9a45cd359..a19b4d9936 100644\n--- a/sub-process.h\n+++ b/sub-process.h\n@@ -20,8 +20,10 @@ struct subprocess_entry {\n \n /* subprocess functions */\n \n-int cmd2process_cmp(const struct subprocess_entry *e1,\n-\tconst struct subprocess_entry *e2, const void *unused);\n+extern int cmd2process_cmp(const struct subprocess_entry *e1,\n+\t\t\t   const struct subprocess_entry *e2,\n+\t\t\t   const void *unused_keydata,\n+\t\t\t   const void *unused_data);\n \n typedef int(*subprocess_start_fn)(struct subprocess_entry *entry);\n int subprocess_start(struct hashmap *hashmap, struct subprocess_entry *entry, const char *cmd,\ndiff --git a/submodule-config.c b/submodule-config.c\nindex d8f8d5ea32..5c2fc489b8 100644\n--- a/submodule-config.c\n+++ b/submodule-config.c\n@@ -36,7 +36,8 @@ static int is_cache_init;\n \n static int config_path_cmp(const struct submodule_entry *a,\n \t\t\t   const struct submodule_entry *b,\n-\t\t\t   const void *unused)\n+\t\t\t   const void *unused_keydata,\n+\t\t\t   const void *unused_data)\n {\n \treturn strcmp(a->config->path, b->config->path) ||\n \t       hashcmp(a->config->gitmodules_sha1, b->config->gitmodules_sha1);\n@@ -44,7 +45,8 @@ static int config_path_cmp(const struct submodule_entry *a,\n \n static int config_name_cmp(const struct submodule_entry *a,\n \t\t\t   const struct submodule_entry *b,\n-\t\t\t   const void *unused)\n+\t\t\t   const void *unused_keydata,\n+\t\t\t   const void *unused_data)\n {\n \treturn strcmp(a->config->name, b->config->name) ||\n \t       hashcmp(a->config->gitmodules_sha1, b->config->gitmodules_sha1);\n@@ -52,8 +54,8 @@ static int config_name_cmp(const struct submodule_entry *a,\n \n static void cache_init(struct submodule_cache *cache)\n {\n-\thashmap_init(&cache->for_path, (hashmap_cmp_fn) config_path_cmp, 0);\n-\thashmap_init(&cache->for_name, (hashmap_cmp_fn) config_name_cmp, 0);\n+\thashmap_init(&cache->for_path, (hashmap_cmp_fn) config_path_cmp, NULL, 0);\n+\thashmap_init(&cache->for_name, (hashmap_cmp_fn) config_name_cmp, NULL, 0);\n }\n \n static void free_one_config(struct submodule_entry *entry)\ndiff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c\nindex 7aa9440e27..72cdc4a6b1 100644\n--- a/t/helper/test-hashmap.c\n+++ b/t/helper/test-hashmap.c\n@@ -14,13 +14,17 @@ static const char *get_value(const struct test_entry *e)\n }\n \n static int test_entry_cmp(const struct test_entry *e1,\n-\t\tconst struct test_entry *e2, const char* key)\n+\t\t\t  const struct test_entry *e2,\n+\t\t\t  const char* key,\n+\t\t\t  const void *unused_data)\n {\n \treturn strcmp(e1->key, key ? key : e2->key);\n }\n \n static int test_entry_cmp_icase(const struct test_entry *e1,\n-\t\tconst struct test_entry *e2, const char* key)\n+\t\t\t\tconst struct test_entry *e2,\n+\t\t\t\tconst char* key,\n+\t\t\t\tconst void *unused_data)\n {\n \treturn strcasecmp(e1->key, key ? key : e2->key);\n }\n@@ -92,7 +96,8 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\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+\t\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp,\n+\t\t\t\t     NULL, 0);\n \n \t\t\t/* add entries */\n \t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n@@ -104,7 +109,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\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+\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, NULL, 0);\n \n \t\t/* fill the map (sparsely if specified) */\n \t\tj = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;\n@@ -147,7 +152,7 @@ int cmd_main(int argc, const char **argv)\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+\t\t\t: test_entry_cmp), NULL, 0);\n \n \t/* process commands from stdin */\n \twhile (fgets(line, sizeof(line), stdin)) {\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323514","messageId":"20170629235336.28460-3-sbeller@google.com","threadId":"46284","inReplyTo":"20170629235336.28460-1-sbeller@google.com","subject":"[PATCHv2 2/2] hashmap: migrate documentation from Documentation/technical into header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T23:53:36Z","receivedAt":"2017-06-29T23:53:52Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"While at it, clarify the use of `key`, `keydata`, `entry_or_key` as well\nas documenting the new data pointer for the compare function.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/technical/api-hashmap.txt | 309 ----------------------------\n hashmap.h                               | 351 +++++++++++++++++++++++++++++---\n 2 files changed, 318 insertions(+), 342 deletions(-)\n delete mode 100644 Documentation/technical/api-hashmap.txt\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\ndeleted file mode 100644\nindex ccc634bbd7..0000000000\n--- a/Documentation/technical/api-hashmap.txt\n+++ /dev/null\n@@ -1,309 +0,0 @@\n-hashmap API\n-===========\n-\n-The hashmap API is a generic implementation of hash-based key-value mappings.\n-\n-Data Structures\n----------------\n-\n-`struct hashmap`::\n-\n-\tThe hash table structure. 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 (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-When `disallow_rehash` is set, automatic rehashes are prevented during inserts\n-and deletes.\n-\n-`struct hashmap_entry`::\n-\n-\tAn opaque structure representing an entry in the hash table, which must\n-\tbe used as first member of user data structures. Ideally it should be\n-\tfollowed by an int-sized member to prevent unused memory on 64-bit\n-\tsystems due to alignment.\n-+\n-The `hash` member is the entry's hash code and the `next` member points to the\n-next entry in case of collisions (i.e. if multiple entries map to the same\n-bucket).\n-\n-`struct hashmap_iter`::\n-\n-\tAn iterator structure, to be used with hashmap_iter_* functions.\n-\n-Types\n------\n-\n-`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::\n-\n-\tUser-supplied function to test two hashmap entries for equality. Shall\n-\treturn 0 if the entries are equal.\n-+\n-This function is always called with non-NULL `entry` / `entry_or_key`\n-parameters that have the same hash code. When looking up an entry, the `key`\n-and `keydata` parameters to hashmap_get and hashmap_remove are always passed\n-as second and third argument, respectively. Otherwise, `keydata` is NULL.\n-\n-Functions\n----------\n-\n-`unsigned int strhash(const char *buf)`::\n-`unsigned int strihash(const char *buf)`::\n-`unsigned int memhash(const void *buf, size_t len)`::\n-`unsigned int memihash(const void *buf, size_t len)`::\n-`unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)`::\n-\n-\tReady-to-use hash functions for strings, using the FNV-1 algorithm (see\n-\thttp://www.isthe.com/chongo/tech/comp/fnv).\n-+\n-`strhash` and `strihash` take 0-terminated strings, while `memhash` and\n-`memihash` operate on arbitrary-length memory.\n-+\n-`strihash` and `memihash` are case insensitive versions.\n-+\n-`memihash_cont` is a variant of `memihash` that allows a computation to be\n-continued with another chunk of data.\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.\n-+\n-`map` is the hashmap to initialize.\n-+\n-The `equals_function` can be specified to compare two entries for equality.\n-If NULL, entries are considered equal if their hash codes are equal.\n-+\n-If the total number of entries is known in advance, the `initial_size`\n-parameter may be used to preallocate a sufficiently large table and thus\n-prevent expensive resizing. If 0, the table is dynamically resized.\n-\n-`void hashmap_free(struct hashmap *map, int free_entries)`::\n-\n-\tFrees a hashmap structure and allocated memory.\n-+\n-`map` is the hashmap to free.\n-+\n-If `free_entries` is true, each hashmap_entry in the map is freed as well\n-(using stdlib's free()).\n-\n-`void hashmap_entry_init(void *entry, unsigned int hash)`::\n-\n-\tInitializes a hashmap_entry structure.\n-+\n-`entry` points to the entry to initialize.\n-+\n-`hash` is the hash code of the entry.\n-+\n-The hashmap_entry structure does not hold references to external resources,\n-and it is safe to just discard it once you are done with it (i.e. if\n-your structure was allocated with xmalloc(), you can just free(3) it,\n-and if it is on stack, you can just let it go out of scope).\n-\n-`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::\n-\n-\tReturns the hashmap entry for the specified key, or NULL if not found.\n-+\n-`map` is the hashmap structure.\n-+\n-`key` is a hashmap_entry structure (or user data structure that starts with\n-hashmap_entry) that has at least been initialized with the proper hash code\n-(via `hashmap_entry_init`).\n-+\n-If an entry with matching hash code is found, `key` and `keydata` are passed\n-to `hashmap_cmp_fn` to decide whether the entry matches the key.\n-\n-`void *hashmap_get_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\n-\tused to iterate over duplicate entries (see `hashmap_add`).\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the hashmap_entry to start the search from, obtained via a previous\n-call to `hashmap_get` or `hashmap_get_next`.\n-\n-`void hashmap_add(struct hashmap *map, void *entry)`::\n-\n-\tAdds a hashmap entry. This allows to add duplicate entries (i.e.\n-\tseparate values with the same key according to hashmap_cmp_fn).\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the entry to add.\n-\n-`void *hashmap_put(struct hashmap *map, void *entry)`::\n-\n-\tAdds or replaces a hashmap entry. If the hashmap contains duplicate\n-\tentries equal to the specified entry, only one of them will be replaced.\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the entry to add or replace.\n-+\n-Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n-\n-`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::\n-\n-\tRemoves a hashmap entry matching the specified key. If the hashmap\n-\tcontains duplicate entries equal to the specified key, only one of\n-\tthem will be removed.\n-+\n-`map` is the hashmap structure.\n-+\n-`key` is a hashmap_entry structure (or user data structure that starts with\n-hashmap_entry) that has at least been initialized with the proper hash code\n-(via `hashmap_entry_init`).\n-+\n-If an entry with matching hash code is found, `key` and `keydata` are\n-passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n-+\n-Returns the removed entry, or NULL if not found.\n-\n-`void hashmap_disallow_rehash(struct hashmap *map, unsigned value)`::\n-\n-\tDisallow/allow automatic rehashing of the hashmap during inserts\n-\tand deletes.\n-+\n-This is useful if the caller knows that the hashmap will be accessed\n-by multiple threads.\n-+\n-The caller is still responsible for any necessary locking; this simply\n-prevents unexpected rehashing.  The caller is also responsible for properly\n-sizing the initial hashmap to ensure good performance.\n-+\n-A call to allow rehashing does not force a rehash; that might happen\n-with the next insert or delete.\n-\n-`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::\n-`void *hashmap_iter_next(struct hashmap_iter *iter)`::\n-`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::\n-\n-\tUsed to iterate over all entries of a hashmap. Note that it is\n-\tnot safe to add or remove entries to the hashmap while\n-\titerating.\n-+\n-`hashmap_iter_init` initializes a `hashmap_iter` structure.\n-+\n-`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no\n-more entries.\n-+\n-`hashmap_iter_first` is a combination of both (i.e. initializes the iterator\n-and returns the first entry, if any).\n-\n-`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-Here's a simple usage example that maps long keys to double values.\n-------------\n-struct hashmap map;\n-\n-struct long2double {\n-\tstruct hashmap_entry ent; /* must be the first member! */\n-\tlong key;\n-\tdouble value;\n-};\n-\n-static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)\n-{\n-\treturn !(e1->key == e2->key);\n-}\n-\n-void long2double_init(void)\n-{\n-\thashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);\n-}\n-\n-void long2double_free(void)\n-{\n-\thashmap_free(&map, 1);\n-}\n-\n-static struct long2double *find_entry(long key)\n-{\n-\tstruct long2double k;\n-\thashmap_entry_init(&k, memhash(&key, sizeof(long)));\n-\tk.key = key;\n-\treturn hashmap_get(&map, &k, NULL);\n-}\n-\n-double get_value(long key)\n-{\n-\tstruct long2double *e = find_entry(key);\n-\treturn e ? e->value : 0;\n-}\n-\n-void set_value(long key, double value)\n-{\n-\tstruct long2double *e = find_entry(key);\n-\tif (!e) {\n-\t\te = malloc(sizeof(struct long2double));\n-\t\thashmap_entry_init(e, memhash(&key, sizeof(long)));\n-\t\te->key = key;\n-\t\thashmap_add(&map, e);\n-\t}\n-\te->value = value;\n-}\n-------------\n-\n-Using variable-sized keys\n--------------------------\n-\n-The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary\n-`hashmap_entry` structure as key to find the correct entry. If the key data is\n-variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable\n-to create a full-fledged entry structure on the heap and copy all the key data\n-into the structure.\n-\n-In this case, the `keydata` parameter can be used to pass\n-variable-sized key data directly to the comparison function, and the `key`\n-parameter can be a stripped-down, fixed size entry structure allocated on the\n-stack.\n-\n-See test-hashmap.c for an example using arbitrary-length strings as keys.\ndiff --git a/hashmap.h b/hashmap.h\nindex 1c26bbad5b..2e0adbe5df 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -3,17 +3,123 @@\n \n /*\n  * Generic implementation of hash-based key-value mappings.\n- * See Documentation/technical/api-hashmap.txt.\n+ *\n+ * An example that maps long to a string:\n+ * For the sake of the example this allows to lookup exact values, too\n+ * (i.e. it is operated as a set, the value is part of the key)\n+ * -------------------------------------\n+ *\n+ * struct hashmap map;\n+ * struct long2string {\n+ *     struct hashmap_entry ent; // must be the first member!\n+ *     long key;\n+ *     char value[FLEX_ARRAY];   // be careful with allocating on stack!\n+ * };\n+ *\n+ * #define COMPARE_VALUE 1\n+ *\n+ * static int long2string_cmp(const struct long2string *e1,\n+ *                            const struct long2string *e2,\n+ *                            const void *keydata, const void *userdata)\n+ * {\n+ *     char *string = keydata;\n+ *     unsigned *flags = (unsigned*)userdata;\n+ *\n+ *     if (flags & COMPARE_VALUE)\n+ *         return !(e1->key == e2->key) || (keydata ?\n+ *                  strcmp(e1->value, keydata) : strcmp(e1->value, e2->value));\n+ *     else\n+ *         return !(e1->key == e2->key);\n+ * }\n+ *\n+ * int main(int argc, char **argv)\n+ * {\n+ *     long key;\n+ *     char *value, *action;\n+ *\n+ *     unsigned flags = ALLOW_DUPLICATE_KEYS;\n+ *\n+ *     hashmap_init(&map, (hashmap_cmp_fn) long2string_cmp, &flags, 0);\n+ *\n+ *     while (scanf(\"%s %l %s\", action, key, value)) {\n+ *\n+ *         if (!strcmp(\"add\", action)) {\n+ *             struct long2string *e;\n+ *             e = malloc(sizeof(struct long2string) + strlen(value));\n+ *             hashmap_entry_init(e, memhash(&key, sizeof(long)));\n+ *             e->key = key;\n+ *             memcpy(e->value, value, strlen(value));\n+ *             hashmap_add(&map, e);\n+ *         }\n+ *\n+ *         if (!strcmp(\"print_all_by_key\", action)) {\n+ *             flags &= ~COMPARE_VALUE;\n+ *\n+ *             struct long2string k;\n+ *             hashmap_entry_init(&k, memhash(&key, sizeof(long)));\n+ *             k.key = key;\n+ *\n+ *             struct long2string *e = hashmap_get(&map, &k, NULL);\n+ *             if (e) {\n+ *                 printf(\"first: %l %s\\n\", e->key, e->value);\n+ *                 while (e = hashmap_get_next(&map, e))\n+ *                     printf(\"found more: %l %s\\n\", e->key, e->value);\n+ *             }\n+ *         }\n+ *\n+ *         if (!strcmp(\"has_exact_match\", action)) {\n+ *             flags |= COMPARE_VALUE;\n+ *\n+ *             struct long2string *e;\n+ *             e = malloc(sizeof(struct long2string) + strlen(value));\n+ *             hashmap_entry_init(e, memhash(&key, sizeof(long)));\n+ *             e->key = key;\n+ *             memcpy(e->value, value, strlen(value));\n+ *\n+ *             printf(\"%s found\\n\", hashmap_get(&map, e, NULL) ? \"\" : \"not\");\n+ *         }\n+ *\n+ *         if (!strcmp(\"has_exact_match_no_heap_alloc\", action)) {\n+ *             flags |= COMPARE_VALUE;\n+ *\n+ *             struct long2string e;\n+ *             hashmap_entry_init(e, memhash(&key, sizeof(long)));\n+ *             e.key = key;\n+ *\n+ *             printf(\"%s found\\n\", hashmap_get(&map, e, value) ? \"\" : \"not\");\n+ *         }\n+ *\n+ *         if (!strcmp(\"end\", action)) {\n+ *             hashmap_free(&map, 1);\n+ *             break;\n+ *         }\n+ *     }\n+ * }\n  */\n \n-/* FNV-1 functions */\n-\n+/*\n+ * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see\n+ * http://www.isthe.com/chongo/tech/comp/fnv).\n+ * `strhash` and `strihash` take 0-terminated strings, while `memhash` and\n+ * `memihash` operate on arbitrary-length memory.\n+ * `strihash` and `memihash` are case insensitive versions.\n+ * `memihash_cont` is a variant of `memihash` that allows a computation to be\n+ * continued with another chunk of data.\n+ */\n extern unsigned int strhash(const char *buf);\n extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n extern unsigned int memihash(const void *buf, size_t len);\n extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);\n \n+/*\n+ * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n+ * for use in hash tables. Cryptographic hashes are supposed to have\n+ * uniform distribution, so in contrast to `memhash()`, this just copies\n+ * the first `sizeof(int)` bytes without shuffling any bits. Note that\n+ * the results will be different on big-endian and little-endian\n+ * platforms, so they should not be stored or transferred over the net.\n+ */\n static inline unsigned int sha1hash(const unsigned char *sha1)\n {\n \t/*\n@@ -25,89 +131,255 @@ static inline unsigned int sha1hash(const unsigned char *sha1)\n \treturn hash;\n }\n \n-/* data structures */\n-\n+/*\n+ * struct hashmap_entry is an opaque structure representing an entry in the\n+ * hash table, which must be used as first member of user data structures.\n+ * Ideally it should be followed by an int-sized member to prevent unused\n+ * memory on 64-bit systems due to alignment.\n+ */\n struct hashmap_entry {\n+\t/*\n+\t * next points to the next entry in case of collisions (i.e. if\n+\t * multiple entries map to the same bucket)\n+\t */\n \tstruct hashmap_entry *next;\n+\n+\t/* entry's hash code */\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.\n+ *\n+ * This function is always called with non-NULL `entry` and `entry_or_key`\n+ * parameters that have the same hash code.\n+ *\n+ * When looking up an entry, the `key` and `keydata` parameters to hashmap_get\n+ * and hashmap_remove are always passed as second `entry_or_key` and third\n+ * argument `keydata`, respectively. Otherwise, `keydata` is NULL.\n+ *\n+ * When it is too expensive to allocate a user entry (either because it is\n+ * large or varialbe sized, such that it is not on the stack), then the\n+ * relevant data to check for equality should be passed via `keydata`.\n+ * In this case `key` can be a stripped down version of the user key data\n+ * or even just a hashmap_entry having the correct hash.\n+ *\n+ * The `data` entry is the pointer given in the init function and is always\n+ * given.\n+ */\n typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n-\t\tconst void *keydata, const void *cbdata);\n+\t\tconst void *keydata, const void *data);\n \n+/*\n+ * struct hashmap is the hash table structure. Members can be used as follows,\n+ * but should not be modified directly.\n+ */\n struct hashmap {\n \tstruct hashmap_entry **table;\n+\n+\t/* Stores the comparison function specified in `hashmap_init()`. */\n \thashmap_cmp_fn cmpfn;\n \tconst void *data;\n-\tunsigned int size, tablesize, grow_at, shrink_at;\n-\tunsigned disallow_rehash : 1;\n-};\n \n-struct hashmap_iter {\n-\tstruct hashmap *map;\n-\tstruct hashmap_entry *next;\n-\tunsigned int tablepos;\n+\t/* total number of entries (0 means the hashmap is empty) */\n+\tunsigned int size;\n+\n+\t/*\n+\t * tablesize is the allocated size of the hash table. A non-0 value\n+\t * indicates that the hashmap is initialized. It may also be useful\n+\t * for statistical purposes (i.e. `size / tablesize` is the current\n+\t * load factor).\n+\t */\n+\tunsigned int tablesize;\n+\n+\tunsigned int grow_at;\n+\tunsigned int shrink_at;\n+\n+\t/* See `hashmap_disallow_rehash`. */\n+\tunsigned disallow_rehash : 1;\n };\n \n /* hashmap functions */\n \n+/*\n+ * Initializes a hashmap structure.\n+ *\n+ * `map` is the hashmap to initialize.\n+ *\n+ * The `equals_function` can be specified to compare two entries for equality.\n+ * If NULL, entries are considered equal if their hash codes are equal.\n+ *\n+ * The `data` parameter can be used to provide additional data (a callback\n+ * cookie) that will be passed to `equals_function` each time it is called.\n+ * This allows a single `equals_function` to implement multiple comparison\n+ * functions.\n+ *\n+ * If the total number of entries is known in advance, the `initial_size`\n+ * parameter may be used to preallocate a sufficiently large table and thus\n+ * prevent expensive resizing. If 0, the table is dynamically resized.\n+ */\n extern void hashmap_init(struct hashmap *map,\n \t\t\t hashmap_cmp_fn equals_function,\n \t\t\t const void *data,\n \t\t\t size_t initial_size);\n+\n+/*\n+ * Frees a hashmap structure and allocated memory.\n+ *\n+ * If `free_entries` is true, each hashmap_entry in the map is freed as well\n+ * using stdlibs free().\n+ */\n extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\n \n+/*\n+ * Initializes a hashmap_entry structure.\n+ *\n+ * `entry` points to the entry to initialize.\n+ * `hash` is the hash code of the entry.\n+ *\n+ * The hashmap_entry structure does not hold references to external resources,\n+ * and it is safe to just discard it once you are done with it (i.e. if\n+ * your structure was allocated with xmalloc(), you can just free(3) it,\n+ * and if it is on stack, you can just let it go out of scope).\n+ */\n static inline void hashmap_entry_init(void *entry, unsigned int hash)\n {\n \tstruct hashmap_entry *e = entry;\n \te->hash = hash;\n \te->next = NULL;\n }\n+\n+/*\n+ * Returns the hashmap entry for the specified key, or NULL if not found.\n+ *\n+ * `map` is the hashmap structure.\n+ *\n+ * `key` is a user data structure that starts with hashmap_entry that has at\n+ * least been initialized with the proper hash code (via `hashmap_entry_init`).\n+ *\n+ * `keydata` is a data structure that holds just enough information to check\n+ * for equality to a given entry.\n+ *\n+ * If the key data is variable-sized (e.g. a FLEX_ARRAY string) or quite large,\n+ * it is undesirable to create a full-fledged entry structure on the heap and\n+ * copy all the key data into the structure.\n+ *\n+ * In this case, the `keydata` parameter can be used to pass\n+ * variable-sized key data directly to the comparison function, and the `key`\n+ * parameter can be a stripped-down, fixed size entry structure allocated on the\n+ * stack.\n+ *\n+ * 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 extern void *hashmap_get(const struct hashmap *map, const void *key,\n-\t\tconst void *keydata);\n-extern void *hashmap_get_next(const struct hashmap *map, const void *entry);\n-extern void hashmap_add(struct hashmap *map, void *entry);\n-extern void *hashmap_put(struct hashmap *map, void *entry);\n-extern void *hashmap_remove(struct hashmap *map, const void *key,\n-\t\tconst void *keydata);\n+\t\t\t const void *keydata);\n \n+/*\n+ * Returns the hashmap entry for the specified hash code and key data,\n+ * or NULL if not found.\n+ *\n+ * `map` is the hashmap structure.\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 of `hashmap_cmp_fn` points to a hashmap_entry\n+ * structure that should not be used in the comparison.\n+ */\n static inline void *hashmap_get_from_hash(const struct hashmap *map,\n-\t\tunsigned int hash, const void *keydata)\n+\t\t\t\t\t  unsigned int hash,\n+\t\t\t\t\t  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+/*\n+ * Returns the next equal hashmap entry, or NULL if not found. This can be\n+ * used to iterate over duplicate entries (see `hashmap_add`).\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the hashmap_entry to start the search from, obtained via a previous\n+ * call to `hashmap_get` or `hashmap_get_next`.\n+ */\n+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.\n+ * separate values with the same key according to hashmap_cmp_fn).\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the entry to add.\n+ */\n+extern void hashmap_add(struct hashmap *map, void *entry);\n+\n+/*\n+ * Adds or replaces a hashmap entry. If the hashmap contains duplicate\n+ * entries equal to the specified entry, only one of them will be replaced.\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the entry to add or replace.\n+ * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n+ */\n+extern void *hashmap_put(struct hashmap *map, void *entry);\n+\n+/*\n+ * Removes a hashmap entry matching the specified key. If the hashmap contains\n+ * duplicate entries equal to the specified key, only one of them will be\n+ * removed. Returns the removed entry, or NULL if not found.\n+ *\n+ * Argument explanation is the same as in `hashmap_get`.\n+ */\n+extern void *hashmap_remove(struct hashmap *map, const void *key,\n+\t\tconst void *keydata);\n+\n+/*\n+ * Returns the `bucket` an entry is stored in.\n+ * Useful for multithreaded read access.\n+ */\n int hashmap_bucket(const struct hashmap *map, unsigned int hash);\n \n /*\n  * Disallow/allow rehashing of the hashmap.\n- * This is useful if the caller knows that the hashmap\n- * needs multi-threaded access.  The caller is still\n- * required to guard/lock searches and inserts in a\n- * manner appropriate to their usage.  This simply\n- * prevents the table from being unexpectedly re-mapped.\n+ * This is useful if the caller knows that the hashmap needs multi-threaded\n+ * access.  The caller is still required to guard/lock searches and inserts\n+ * in a manner appropriate to their usage.  This simply prevents the table\n+ * from being unexpectedly re-mapped.\n  *\n- * If is up to the caller to ensure that the hashmap is\n- * initialized to a reasonable size to prevent poor\n- * performance.\n+ * It is up to the caller to ensure that the hashmap is initialized to a\n+ * reasonable size to prevent poor performance.\n  *\n- * When value=1, prevent future rehashes on adds and deleted.\n- * When value=0, allow future rehahses.  This DOES NOT force\n- * a rehash now.\n+ * A call to allow rehashing does not force a rehash; that might happen\n+ * with the next insert or delete.\n  */\n static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)\n {\n \tmap->disallow_rehash = value;\n }\n \n-/* hashmap_iter functions */\n+/*\n+ * Used to iterate over all entries of a hashmap. Note that it is\n+ * not safe to add or remove entries to the hashmap while\n+ * iterating.\n+ */\n+struct hashmap_iter {\n+\tstruct hashmap *map;\n+\tstruct hashmap_entry *next;\n+\tunsigned int tablepos;\n+};\n \n+/* Initializes a `hashmap_iter` structure. */\n extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n+\n+/* Returns the next hashmap_entry, or NULL if there are no more entries. */\n extern void *hashmap_iter_next(struct hashmap_iter *iter);\n+\n+/* Initializes the iterator and returns the first entry, if any. */\n static inline void *hashmap_iter_first(struct hashmap *map,\n \t\tstruct hashmap_iter *iter)\n {\n@@ -115,8 +387,21 @@ static inline void *hashmap_iter_first(struct hashmap *map,\n \treturn hashmap_iter_next(iter);\n }\n \n-/* string interning */\n+/* String interning */\n \n+/*\n+ * Returns the unique, interned version of the specified string or data,\n+ * similar to the `String.intern` API in Java and .NET, respectively.\n+ * Interned 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 extern const void *memintern(const void *data, size_t len);\n static inline const char *strintern(const char *string)\n {\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323515","messageId":"20170629235336.28460-1-sbeller@google.com","threadId":"46284","inReplyTo":"20170629011334.11173-1-sbeller@google.com","subject":"[PATCHv2 0/2] Introduce data field in hashmap and migrate docs to header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-29T23:53:34Z","receivedAt":"2017-06-29T23:53:55Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"v2:\n\naddressed all but the last point of Jonathan Nieder.\n\nThanks,\nStefan\n\nv1:\n\nhttps://public-inbox.org/git/xmqqpodnvmmw.fsf@gitster.mtv.corp.google.com/\nfor context why we need a new data field.  Implement that.\n\nOnce upon a time we had a long discussion where to put documentation best.\nThe answer was header files as there documentation has less chance\nto become stale and be out of date.  Improve the docs by\n* migrating them to the header\n* clarifying how the compare function is to be used\n* how the arguments to hashmap_get/remove should be used.\n\nThanks,\nStefan\n\nStefan Beller (2):\n  hashmap.h: compare function has access to a data field\n  hashmap: migrate documentation from Documentation/technical into\n    header\n\n Documentation/technical/api-hashmap.txt | 309 ---------------------------\n attr.c                                  |   4 +-\n builtin/describe.c                      |   6 +-\n builtin/difftool.c                      |  20 +-\n builtin/fast-export.c                   |   5 +-\n config.c                                |   7 +-\n convert.c                               |   3 +-\n diffcore-rename.c                       |   2 +-\n hashmap.c                               |  17 +-\n hashmap.h                               | 358 ++++++++++++++++++++++++++++----\n name-hash.c                             |  12 +-\n oidset.c                                |   5 +-\n patch-ids.c                             |   6 +-\n refs.c                                  |   4 +-\n remote.c                                |   7 +-\n sha1_file.c                             |   5 +-\n sub-process.c                           |   5 +-\n sub-process.h                           |   6 +-\n submodule-config.c                      |  10 +-\n t/helper/test-hashmap.c                 |  15 +-\n 20 files changed, 412 insertions(+), 394 deletions(-)\n delete mode 100644 Documentation/technical/api-hashmap.txt\n\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323578","messageId":"xmqqshihs7xv.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"CAGZ79kaP3rDRNVQRk3_egZrY54Ra3eaOGCPpufp+y936=6kPQw@mail.gmail.com","subject":"Re: [PATCH 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-30T17:26:36Z","receivedAt":"2017-06-30T17:26:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> Yes it was a last minute squash before sending it out, as the fix was only\n> two lines whereas the conversion is a lot. If it were separated I could have\n> claimed the introduction to be a rather mechanical patch, but I did not\n> make use of coccinelle or such, so the likelihood for errors is just as high.\n>\n> So I decided to squash them.\n\nI somehow think that logic leads to a suboptimal workflow.  If they\nwere separated, somebody else could have done an independent\nmechanical conversion to verify the result matches yours, which\nwould give us more confidence.  When such an independent mechanical\nconversion does not match, we need one round-trip to ask you if it\nwas a misconversion or a manual tweak.\n\nIn any case, I think I've looked at it long enough to be reasonably\nOK with the conversion result myself, so let's move it forward.  Of\ncourse I welcome independent eyeballing by others.\n\nThanks.\n"},{"id":"323580","messageId":"xmqqlgo9s7li.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"20170629235336.28460-2-sbeller@google.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-30T17:34:01Z","receivedAt":"2017-06-30T17:34:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> When using the hashmap a common need is to have access to arbitrary data\n> in the compare function. A couple of times we abuse the keydata field\n> to pass in the data needed. This happens for example in patch-ids.c.\n\nIt is not \"arbitrary data\"; it is very important to streess that we\nare not just passing random crud, but adding a mechanism to\ntailor/curry the function in a way that is fixed throughout the\nlifetime of a hashmap.\n\n> diff --git a/hashmap.h b/hashmap.h\n> index de6022a3a9..1c26bbad5b 100644\n> --- a/hashmap.h\n> +++ b/hashmap.h\n> @@ -33,11 +33,12 @@ struct hashmap_entry {\n>  };\n>  \n>  typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n> -\t\tconst void *keydata);\n> +\t\tconst void *keydata, const void *cbdata);\n\nAs I view the new \"data\" thing the C's (read: poor-man's) way to\ncutomize the function, I would have tweaked the function signature\nby giving the customization data at the front, i.e.\n\n\tfn(fndata, entry, entry_or_key, keydata);\n\nThat would hopefully make it more obvious that the new thing is\npairs with fn, not with other arguments (and entry-or-key and\nkeydata pairs, instead of three old arguments standing as equals).\n\nAs I think the way we wish to be able to express it in a better\nlanguage would have been something like:\n\n\t(partial_apply(fn, fndata))(entry, entry_or_key, keydata)\n\nthat order would match what is going on better.\n"},{"id":"323581","messageId":"xmqqh8yxs7by.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"20170629235336.28460-2-sbeller@google.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-30T17:39:45Z","receivedAt":"2017-06-30T17:39:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> diff --git a/patch-ids.c b/patch-ids.c\n> index 9c0ab9e67a..b9b2ebbad0 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -37,6 +37,7 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n>   */\n>  static int patch_id_cmp(struct patch_id *a,\n>  \t\t\tstruct patch_id *b,\n> +\t\t\tconst void *unused_keydata,\n>  \t\t\tstruct diff_options *opt)\n>  {\n>  \tif (is_null_oid(&a->patch_id) &&\n> @@ -57,7 +58,8 @@ int init_patch_ids(struct patch_ids *ids)\n>  \tids->diffopts.detect_rename = 0;\n>  \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n>  \tdiff_setup_done(&ids->diffopts);\n> -\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n> +\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n> +\t\t     &ids->diffopts, 256);\n>  \treturn 0;\n>  }\n>  \n> @@ -93,7 +95,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n>  \tif (init_patch_id_entry(&patch, commit, ids))\n>  \t\treturn NULL;\n>  \n> -\treturn hashmap_get(&ids->patches, &patch, &ids->diffopts);\n> +\treturn hashmap_get(&ids->patches, &patch, NULL);\n>  }\n\nThis actually makes me wonder if we can demonstrate an existing\nbreakage in tests.  The old code used to pass NULL to the diffopts,\ncausing it to be passed down through commit_patch_id() function down\nto diff_tree_oid() or diff_root_tree_oid().  When the codepath\ntriggers the issue that Peff warned about in his old article (was it\nabout rehashing or something?) that makes two entries compared\n(i.e. not using keydata, because we are not comparing an existing\nentry with a key and data only to see if that already exists in the\nhashmap), wouldn't that cause ll_diff_tree_oid() that is called from\ndiff_tree_oid() to dereference NULL?\n\nThanks.\n"},{"id":"323582","messageId":"CAGZ79kbu2hqc41eBk_AtoeTviJGT4TTV7M6cYp0h4q=gJs2wRg@mail.gmail.com","threadId":"46284","inReplyTo":"xmqqlgo9s7li.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T17:41:40Z","receivedAt":"2017-06-30T17:41:46Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 30, 2017 at 10:34 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <sbeller@google.com> writes:\n>\n>> When using the hashmap a common need is to have access to arbitrary data\n>> in the compare function. A couple of times we abuse the keydata field\n>> to pass in the data needed. This happens for example in patch-ids.c.\n>\n> It is not \"arbitrary data\"; it is very important to streess that we\n> are not just passing random crud, but adding a mechanism to\n> tailor/curry the function in a way that is fixed throughout the\n> lifetime of a hashmap.\n\nAh yes, I forgot to fix patch1, when spending all time on the docs in p2.\n\n>\n>> diff --git a/hashmap.h b/hashmap.h\n>> index de6022a3a9..1c26bbad5b 100644\n>> --- a/hashmap.h\n>> +++ b/hashmap.h\n>> @@ -33,11 +33,12 @@ struct hashmap_entry {\n>>  };\n>>\n>>  typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n>> -             const void *keydata);\n>> +             const void *keydata, const void *cbdata);\n>\n> As I view the new \"data\" thing the C's (read: poor-man's) way to\n> cutomize the function, I would have tweaked the function signature\n> by giving the customization data at the front, i.e.\n>\n>         fn(fndata, entry, entry_or_key, keydata);\n>\n> That would hopefully make it more obvious that the new thing is\n> pairs with fn, not with other arguments (and entry-or-key and\n> keydata pairs, instead of three old arguments standing as equals).\n\nOk, let me redo the patch to have fndata at the front.\n\nLooking at other places (that have a similar mechanism mechanically,\nbut are semantically different), such as the callback functions for\nthe diff machinery, we have the user provided pointer at the end\nof the list. But that is because the diff_options are the objects that\nshould be in front row (they are bound to the callback more than\nsome caller needed data).\n\n    typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,\n          struct diff_options *options, void *data);\n\n    typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options\n*opt, void *data);\n\nThanks!\n\n> As I think the way we wish to be able to express it in a better\n> language would have been something like:\n>\n>         (partial_apply(fn, fndata))(entry, entry_or_key, keydata)\n>\n> that order would match what is going on better.\n"},{"id":"323585","messageId":"CAGZ79kbWXuC2y97+nOsgvNhCCqg=2+VgOOvTbUn1LGpH4f0=PQ@mail.gmail.com","threadId":"46284","inReplyTo":"xmqqh8yxs7by.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T18:00:19Z","receivedAt":"2017-06-30T18:00:27Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 30, 2017 at 10:39 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <sbeller@google.com> writes:\n>\n>> diff --git a/patch-ids.c b/patch-ids.c\n>> index 9c0ab9e67a..b9b2ebbad0 100644\n>> --- a/patch-ids.c\n>> +++ b/patch-ids.c\n>> @@ -37,6 +37,7 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n>>   */\n>>  static int patch_id_cmp(struct patch_id *a,\n>>                       struct patch_id *b,\n>> +                     const void *unused_keydata,\n>>                       struct diff_options *opt)\n>>  {\n>>       if (is_null_oid(&a->patch_id) &&\n>> @@ -57,7 +58,8 @@ int init_patch_ids(struct patch_ids *ids)\n>>       ids->diffopts.detect_rename = 0;\n>>       DIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n>>       diff_setup_done(&ids->diffopts);\n>> -     hashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n>> +     hashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n>> +                  &ids->diffopts, 256);\n>>       return 0;\n>>  }\n>>\n>> @@ -93,7 +95,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n>>       if (init_patch_id_entry(&patch, commit, ids))\n>>               return NULL;\n>>\n>> -     return hashmap_get(&ids->patches, &patch, &ids->diffopts);\n>> +     return hashmap_get(&ids->patches, &patch, NULL);\n>>  }\n\n+cc Peff\n\n>\n> This actually makes me wonder if we can demonstrate an existing\n> breakage in tests.  The old code used to pass NULL to the diffopts,\n> causing it to be passed down through commit_patch_id() function down\n> to diff_tree_oid() or diff_root_tree_oid().  When the codepath\n> triggers the issue that Peff warned about in his old article (was it\n> about rehashing or something?)  that makes two entries compared\n> (i.e. not using keydata, because we are not comparing an existing\n> entry with a key and data only to see if that already exists in the\n> hashmap), wouldn't that cause ll_diff_tree_oid() that is called from\n> diff_tree_oid() to dereference NULL?\n>\n> Thanks.\n\nI am at a loss here after re-reading your answer over and over,\nbut I think you are asking if patch_id_cmp can break, as\nwe have a callchain like\n\n  patch_id_cmp\n    commit_patch_id\n      (diff_root_tree_oid)\n        diff_tree_oid\n          ll_diff_tree_oid\n\npassing diff_options down there, and patch_id_cmp may have\ngotten NULL.\n\nThe answer is no, it was safe. (by accident?)\n\nThat is because we never use hashmap_get_next\non the hashmap that uses patch_id_cmp as the compare\nfunction.\n\nhashmap_get_next is the only function that does not pass\non a keydata, any other has valid caller provided keydata.\n\nThanks,\nStefan\n"},{"id":"323590","messageId":"xmqqzicpqpyh.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"CAGZ79kbWXuC2y97+nOsgvNhCCqg=2+VgOOvTbUn1LGpH4f0=PQ@mail.gmail.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-30T18:40:22Z","receivedAt":"2017-06-30T18:40:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> I am at a loss here after re-reading your answer over and over,\n> but I think you are asking if patch_id_cmp can break, as\n> we have a callchain like\n>\n>   patch_id_cmp\n>     commit_patch_id\n>       (diff_root_tree_oid)\n>         diff_tree_oid\n>           ll_diff_tree_oid\n>\n> passing diff_options down there, and patch_id_cmp may have\n> gotten NULL.\n>\n> The answer is no, it was safe. (by accident?)\n>\n> That is because we never use hashmap_get_next\n> on the hashmap that uses patch_id_cmp as the compare\n> function.\n>\n> hashmap_get_next is the only function that does not pass\n> on a keydata, any other has valid caller provided keydata.\n\nAh, thanks for clarifying.  I think I misread the earlier\ndiscussion.  So unless somebody goes in to patch-ids.c and adds a\ncall to do get_next, we won't see a breakage, and it is not worth to\ndo a test-patch-ids.c that peeks into the hashmap patch-ids.c uses\nand does get_next() only to demonstrate a potential future breakage.\n\nOK.\n"},{"id":"323592","messageId":"xmqqo9t5qpma.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"CAGZ79kbu2hqc41eBk_AtoeTviJGT4TTV7M6cYp0h4q=gJs2wRg@mail.gmail.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-30T18:47:41Z","receivedAt":"2017-06-30T18:47:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> Ok, let me redo the patch to have fndata at the front.\n>\n> Looking at other places (that have a similar mechanism mechanically,\n> but are semantically different), such as the callback functions for\n> the diff machinery, we have the user provided pointer at the end\n> of the list. But that is because the diff_options are the objects that\n> should be in front row (they are bound to the callback more than\n> some caller needed data).\n\nQuite honestly, I do not care too deeply about an API specific to a\nparticular area like \"diff\" that passes its \"configuration\" data\nthat everybody in the API knows, i.e. diff_options.  If the\nconvention for ordinary functions in the API is to pass that in a\nparticular location in the parameter list, I would think it is good\nfor a application-supplied callback function to follow that pattern.\nAfter all, it is to configure the behaviour of the \"diff\" and the\ncaller-supplied callback could have been part of a (hypothetically\nricher) API implementation.\n\nBut I view a comparison function that is given to hashmap that is\nsupplied by the caller a bit differently.  It is not about\n\"hashing\", so the reason to have the data close to function pointer\nis stronger there.\n"},{"id":"323593","messageId":"CAGZ79kbqLS-DxOPe+uG9UssD9s3f7JT5qp1YKMPqFMcOGoLL3A@mail.gmail.com","threadId":"46284","inReplyTo":"xmqqo9t5qpma.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCHv2 1/2] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T18:57:42Z","receivedAt":"2017-06-30T18:57:48Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 30, 2017 at 11:47 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <sbeller@google.com> writes:\n>\n>> Ok, let me redo the patch to have fndata at the front.\n>>\n>> Looking at other places (that have a similar mechanism mechanically,\n>> but are semantically different), such as the callback functions for\n>> the diff machinery, we have the user provided pointer at the end\n>> of the list. But that is because the diff_options are the objects that\n>> should be in front row (they are bound to the callback more than\n>> some caller needed data).\n>\n> Quite honestly, I do not care too deeply about an API specific to a\n> particular area like \"diff\" that passes its \"configuration\" data\n> that everybody in the API knows, i.e. diff_options.  If the\n> convention for ordinary functions in the API is to pass that in a\n> particular location in the parameter list, I would think it is good\n> for a application-supplied callback function to follow that pattern.\n> After all, it is to configure the behaviour of the \"diff\" and the\n> caller-supplied callback could have been part of a (hypothetically\n> richer) API implementation.\n>\n> But I view a comparison function that is given to hashmap that is\n> supplied by the caller a bit differently.  It is not about\n> \"hashing\", so the reason to have the data close to function pointer\n> is stronger there.\n\nYes I agree with that, I forgot to say so.\n\nI just cited the example to see if we have a preference in the project\nalready and that's about it, but as it is different, we can put the fndata\nfirst.\n\nThanks,\nStefan\n"},{"id":"323594","messageId":"20170630191407.5381-1-sbeller@google.com","threadId":"46284","inReplyTo":"20170629235336.28460-1-sbeller@google.com","subject":"[PATCHv3 0/3] Introduce data field in hashmap and migrate docs to header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T19:14:04Z","receivedAt":"2017-06-30T19:14:19Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"v3:\n\n* fixed first patch to call the data 'caller provided' instead of arbitrary.\n* moved the position of the caller provided data to first position\n* split up the rather mechanical change of function signature with\n  fixing the API usage of patch-ids.c\n\nv2:\n\naddressed all but the last point of Jonathan Nieder.\n\nThanks,\nStefan\n\nv1:\n\nhttps://public-inbox.org/git/xmqqpodnvmmw.fsf@gitster.mtv.corp.google.com/\nfor context why we need a new data field.  Implement that.\n\nOnce upon a time we had a long discussion where to put documentation best.\nThe answer was header files as there documentation has less chance\nto become stale and be out of date.  Improve the docs by\n* migrating them to the header\n* clarifying how the compare function is to be used\n* how the arguments to hashmap_get/remove should be used.\n\nThanks,\nStefan\n\nStefan Beller (3):\n  hashmap.h: compare function has access to a data field\n  patch-ids.c: use hashmap correctly\n  hashmap: migrate documentation from Documentation/technical into\n    header\n\n Documentation/technical/api-hashmap.txt | 309 ---------------------------\n attr.c                                  |   7 +-\n builtin/describe.c                      |   8 +-\n builtin/difftool.c                      |  24 ++-\n builtin/fast-export.c                   |   7 +-\n config.c                                |   9 +-\n convert.c                               |   3 +-\n diffcore-rename.c                       |   2 +-\n hashmap.c                               |  17 +-\n hashmap.h                               | 360 ++++++++++++++++++++++++++++----\n name-hash.c                             |  16 +-\n oidset.c                                |   5 +-\n patch-ids.c                             |  10 +-\n refs.c                                  |   5 +-\n remote.c                                |   7 +-\n sha1_file.c                             |   5 +-\n sub-process.c                           |   7 +-\n sub-process.h                           |   6 +-\n submodule-config.c                      |  14 +-\n t/helper/test-hashmap.c                 |  19 +-\n 20 files changed, 431 insertions(+), 409 deletions(-)\n delete mode 100644 Documentation/technical/api-hashmap.txt\n\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323595","messageId":"20170630191407.5381-2-sbeller@google.com","threadId":"46284","inReplyTo":"20170630191407.5381-1-sbeller@google.com","subject":"[PATCHv3 1/3] hashmap.h: compare function has access to a data field","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T19:14:05Z","receivedAt":"2017-06-30T19:14:22Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"When using the hashmap a common need is to have access to caller provided\ndata in the compare function. A couple of times we abuse the keydata field\nto pass in the data needed. This happens for example in patch-ids.c.\n\nThis patch changes the function signature of the compare function\nto have one more void pointer available. The pointer given for each\ninvocation of the compare function must be defined in the init function\nof the hashmap and is just passed through.\n\nDocumentation of this new feature is deferred to a later patch.\nThis is a rather mechanical conversion, just adding the new pass-through\nparameter.  However while at it improve the naming of the fields of all\ncompare functions used by hashmaps by ensuring unused parameters are\nprefixed with 'unused_' and naming the parameters what they are (instead\nof 'unused' make it 'unused_keydata').\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n attr.c                  |  7 ++++---\n builtin/describe.c      |  8 +++++---\n builtin/difftool.c      | 24 +++++++++++++++---------\n builtin/fast-export.c   |  7 ++++---\n config.c                |  9 ++++++---\n convert.c               |  3 ++-\n diffcore-rename.c       |  2 +-\n hashmap.c               | 17 ++++++++++++-----\n hashmap.h               | 12 ++++++++----\n name-hash.c             | 16 ++++++++++------\n oidset.c                |  5 +++--\n patch-ids.c             |  6 ++++--\n refs.c                  |  5 +++--\n remote.c                |  7 +++++--\n sha1_file.c             |  5 +++--\n sub-process.c           |  7 ++++---\n sub-process.h           |  6 ++++--\n submodule-config.c      | 14 ++++++++------\n t/helper/test-hashmap.c | 19 ++++++++++++-------\n 19 files changed, 113 insertions(+), 66 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex 37454999d2..56961f0236 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -76,9 +76,10 @@ struct attr_hash_entry {\n };\n \n /* attr_hashmap comparison function */\n-static int attr_hash_entry_cmp(const struct attr_hash_entry *a,\n+static int attr_hash_entry_cmp(void *unused_cmp_data,\n+\t\t\t       const struct attr_hash_entry *a,\n \t\t\t       const struct attr_hash_entry *b,\n-\t\t\t       void *unused)\n+\t\t\t       void *unused_keydata)\n {\n \treturn (a->keylen != b->keylen) || strncmp(a->key, b->key, a->keylen);\n }\n@@ -86,7 +87,7 @@ static int attr_hash_entry_cmp(const struct attr_hash_entry *a,\n /* Initialize an 'attr_hashmap' object */\n static void attr_hashmap_init(struct attr_hashmap *map)\n {\n-\thashmap_init(&map->map, (hashmap_cmp_fn) attr_hash_entry_cmp, 0);\n+\thashmap_init(&map->map, (hashmap_cmp_fn) attr_hash_entry_cmp, NULL, 0);\n }\n \n /*\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 70eb144608..8868f00ed0 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -54,8 +54,10 @@ static const char *prio_names[] = {\n \tN_(\"head\"), N_(\"lightweight\"), N_(\"annotated\"),\n };\n \n-static int commit_name_cmp(const struct commit_name *cn1,\n-\t\tconst struct commit_name *cn2, const void *peeled)\n+static int commit_name_cmp(const void *unused_cmp_data,\n+\t\t\t   const struct commit_name *cn1,\n+\t\t\t   const struct commit_name *cn2,\n+\t\t\t   const void *peeled)\n {\n \treturn oidcmp(&cn1->peeled, peeled ? peeled : &cn2->peeled);\n }\n@@ -501,7 +503,7 @@ 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-\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);\n+\thashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, NULL, 0);\n \tfor_each_rawref(get_name, NULL);\n \tif (!names.size && !always)\n \t\tdie(_(\"No names found, cannot describe anything.\"));\ndiff --git a/builtin/difftool.c b/builtin/difftool.c\nindex 9199227f6e..a1a26ba891 100644\n--- a/builtin/difftool.c\n+++ b/builtin/difftool.c\n@@ -130,8 +130,10 @@ struct working_tree_entry {\n \tchar path[FLEX_ARRAY];\n };\n \n-static int working_tree_entry_cmp(struct working_tree_entry *a,\n-\t\t\t\t  struct working_tree_entry *b, void *keydata)\n+static int working_tree_entry_cmp(const void *unused_cmp_data,\n+\t\t\t\t  struct working_tree_entry *a,\n+\t\t\t\t  struct working_tree_entry *b,\n+\t\t\t\t  void *unused_keydata)\n {\n \treturn strcmp(a->path, b->path);\n }\n@@ -146,7 +148,9 @@ struct pair_entry {\n \tconst char path[FLEX_ARRAY];\n };\n \n-static int pair_cmp(struct pair_entry *a, struct pair_entry *b, void *keydata)\n+static int pair_cmp(const void *unused_cmp_data,\n+\t\t    struct pair_entry *a, struct pair_entry *b,\n+\t\t    void *unused_keydata)\n {\n \treturn strcmp(a->path, b->path);\n }\n@@ -174,7 +178,9 @@ struct path_entry {\n \tchar path[FLEX_ARRAY];\n };\n \n-static int path_entry_cmp(struct path_entry *a, struct path_entry *b, void *key)\n+static int path_entry_cmp(const void *unused_cmp_data,\n+\t\t\t  struct path_entry *a, struct path_entry *b,\n+\t\t\t  void *key)\n {\n \treturn strcmp(a->path, key ? key : b->path);\n }\n@@ -367,9 +373,9 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,\n \twtdir_len = wtdir.len;\n \n \thashmap_init(&working_tree_dups,\n-\t\t     (hashmap_cmp_fn)working_tree_entry_cmp, 0);\n-\thashmap_init(&submodules, (hashmap_cmp_fn)pair_cmp, 0);\n-\thashmap_init(&symlinks2, (hashmap_cmp_fn)pair_cmp, 0);\n+\t\t     (hashmap_cmp_fn)working_tree_entry_cmp, NULL, 0);\n+\thashmap_init(&submodules, (hashmap_cmp_fn)pair_cmp, NULL, 0);\n+\thashmap_init(&symlinks2, (hashmap_cmp_fn)pair_cmp, NULL, 0);\n \n \tchild.no_stdin = 1;\n \tchild.git_cmd = 1;\n@@ -580,9 +586,9 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,\n \t * files through the symlink.\n \t */\n \thashmap_init(&wt_modified, (hashmap_cmp_fn)path_entry_cmp,\n-\t\t     wtindex.cache_nr);\n+\t\t     NULL, wtindex.cache_nr);\n \thashmap_init(&tmp_modified, (hashmap_cmp_fn)path_entry_cmp,\n-\t\t     wtindex.cache_nr);\n+\t\t     NULL, wtindex.cache_nr);\n \n \tfor (i = 0; i < wtindex.cache_nr; i++) {\n \t\tstruct hashmap_entry dummy;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 12d501bfde..d412c0a8f3 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -93,8 +93,9 @@ struct anonymized_entry {\n \tsize_t anon_len;\n };\n \n-static int anonymized_entry_cmp(const void *va, const void *vb,\n-\t\t\t\tconst void *data)\n+static int anonymized_entry_cmp(const void *unused_cmp_data,\n+\t\t\t\tconst void *va, const void *vb,\n+\t\t\t\tconst void *unused_keydata)\n {\n \tconst struct anonymized_entry *a = va, *b = vb;\n \treturn a->orig_len != b->orig_len ||\n@@ -113,7 +114,7 @@ static const void *anonymize_mem(struct hashmap *map,\n \tstruct anonymized_entry key, *ret;\n \n \tif (!map->cmpfn)\n-\t\thashmap_init(map, anonymized_entry_cmp, 0);\n+\t\thashmap_init(map, anonymized_entry_cmp, NULL, 0);\n \n \thashmap_entry_init(&key, memhash(orig, *len));\n \tkey.orig = orig;\ndiff --git a/config.c b/config.c\nindex 1cd40a5fe6..4a31e31ac3 100644\n--- a/config.c\n+++ b/config.c\n@@ -1753,15 +1753,18 @@ static int configset_add_value(struct config_set *cs, const char *key, const cha\n \treturn 0;\n }\n \n-static int config_set_element_cmp(const struct config_set_element *e1,\n-\t\t\t\t const struct config_set_element *e2, const void *unused)\n+static int config_set_element_cmp(const void *unused_cmp_data,\n+\t\t\t\t  const struct config_set_element *e1,\n+\t\t\t\t  const struct config_set_element *e2,\n+\t\t\t\t  const void *unused_keydata)\n {\n \treturn strcmp(e1->key, e2->key);\n }\n \n void git_configset_init(struct config_set *cs)\n {\n-\thashmap_init(&cs->config_hash, (hashmap_cmp_fn)config_set_element_cmp, 0);\n+\thashmap_init(&cs->config_hash, (hashmap_cmp_fn)config_set_element_cmp,\n+\t\t     NULL, 0);\n \tcs->hash_initialized = 1;\n \tcs->list.nr = 0;\n \tcs->list.alloc = 0;\ndiff --git a/convert.c b/convert.c\nindex 7d2a519daf..deaf0ba7b3 100644\n--- a/convert.c\n+++ b/convert.c\n@@ -583,7 +583,8 @@ static int apply_multi_file_filter(const char *path, const char *src, size_t len\n \n \tif (!subprocess_map_initialized) {\n \t\tsubprocess_map_initialized = 1;\n-\t\thashmap_init(&subprocess_map, (hashmap_cmp_fn) cmd2process_cmp, 0);\n+\t\thashmap_init(&subprocess_map, (hashmap_cmp_fn) cmd2process_cmp,\n+\t\t\t     NULL, 0);\n \t\tentry = NULL;\n \t} else {\n \t\tentry = (struct cmd2process *)subprocess_find_entry(&subprocess_map, cmd);\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1e4678b7d7..786f389498 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -341,7 +341,7 @@ static int find_exact_renames(struct diff_options *options)\n \t/* Add all sources to the hash table in reverse order, because\n \t * later on they will be retrieved in LIFO order.\n \t */\n-\thashmap_init(&file_table, NULL, rename_src_nr);\n+\thashmap_init(&file_table, NULL, NULL, rename_src_nr);\n \tfor (i = rename_src_nr-1; i >= 0; i--)\n \t\tinsert_file_table(&file_table, i, rename_src[i].p->one);\n \ndiff --git a/hashmap.c b/hashmap.c\nindex 7d1044eb5d..9b6a12859b 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -95,7 +95,9 @@ static inline int entry_equals(const struct hashmap *map,\n \t\tconst struct hashmap_entry *e1, const struct hashmap_entry *e2,\n \t\tconst void *keydata)\n {\n-\treturn (e1 == e2) || (e1->hash == e2->hash && !map->cmpfn(e1, e2, keydata));\n+\treturn (e1 == e2) ||\n+\t       (e1->hash == e2->hash &&\n+\t\t!map->cmpfn(map->cmpfn_data, e1, e2, keydata));\n }\n \n static inline unsigned int bucket(const struct hashmap *map,\n@@ -140,19 +142,23 @@ static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,\n \treturn e;\n }\n \n-static int always_equal(const void *unused1, const void *unused2, const void *unused3)\n+static int always_equal(const void *unused_cmp_data,\n+\t\t\tconst void *unused1,\n+\t\t\tconst void *unused2,\n+\t\t\tconst void *unused_keydata)\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+\t\tconst void *cmpfn_data, size_t initial_size)\n {\n \tunsigned int size = HASHMAP_INITIAL_SIZE;\n \n \tmemset(map, 0, sizeof(*map));\n \n \tmap->cmpfn = equals_function ? equals_function : always_equal;\n+\tmap->cmpfn_data = cmpfn_data;\n \n \t/* calculate initial table size and allocate the table */\n \tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n@@ -260,7 +266,8 @@ struct pool_entry {\n \tunsigned char data[FLEX_ARRAY];\n };\n \n-static int pool_entry_cmp(const struct pool_entry *e1,\n+static int pool_entry_cmp(const void *unused_cmp_data,\n+\t\t\t  const struct pool_entry *e1,\n \t\t\t  const struct pool_entry *e2,\n \t\t\t  const unsigned char *keydata)\n {\n@@ -275,7 +282,7 @@ const void *memintern(const void *data, size_t len)\n \n \t/* initialize string pool hashmap */\n \tif (!map.tablesize)\n-\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, 0);\n+\t\thashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0);\n \n \t/* lookup interned string in pool */\n \thashmap_entry_init(&key, memhash(data, len));\ndiff --git a/hashmap.h b/hashmap.h\nindex de6022a3a9..aaf09e047e 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -32,12 +32,14 @@ struct hashmap_entry {\n \tunsigned int hash;\n };\n \n-typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n-\t\tconst void *keydata);\n+typedef int (*hashmap_cmp_fn)(const void *hashmap_cmp_fn_data,\n+\t\t\t      const void *entry, const void *entry_or_key,\n+\t\t\t      const void *keydata);\n \n struct hashmap {\n \tstruct hashmap_entry **table;\n \thashmap_cmp_fn cmpfn;\n+\tconst void *cmpfn_data;\n \tunsigned int size, tablesize, grow_at, shrink_at;\n \tunsigned disallow_rehash : 1;\n };\n@@ -50,8 +52,10 @@ struct hashmap_iter {\n \n /* hashmap functions */\n \n-extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n-\t\tsize_t initial_size);\n+extern void hashmap_init(struct hashmap *map,\n+\t\t\t hashmap_cmp_fn equals_function,\n+\t\t\t const void *equals_function_data,\n+\t\t\t size_t initial_size);\n extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\ndiff --git a/name-hash.c b/name-hash.c\nindex 39309efb7f..0e10f3eab8 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -16,8 +16,10 @@ struct dir_entry {\n \tchar name[FLEX_ARRAY];\n };\n \n-static int dir_entry_cmp(const struct dir_entry *e1,\n-\t\tconst struct dir_entry *e2, const char *name)\n+static int dir_entry_cmp(const void *unused_cmp_data,\n+\t\t\t const struct dir_entry *e1,\n+\t\t\t const struct dir_entry *e2,\n+\t\t\t const char *name)\n {\n \treturn e1->namelen != e2->namelen || strncasecmp(e1->name,\n \t\t\tname ? name : e2->name, e1->namelen);\n@@ -107,8 +109,10 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \t\tadd_dir_entry(istate, ce);\n }\n \n-static int cache_entry_cmp(const struct cache_entry *ce1,\n-\t\tconst struct cache_entry *ce2, const void *remove)\n+static int cache_entry_cmp(const void *unused_cmp_data,\n+\t\t\t   const struct cache_entry *ce1,\n+\t\t\t   const struct cache_entry *ce2,\n+\t\t\t   const void *remove)\n {\n \t/*\n \t * For remove_name_hash, find the exact entry (pointer equality); for\n@@ -571,9 +575,9 @@ static void lazy_init_name_hash(struct index_state *istate)\n \tif (istate->name_hash_initialized)\n \t\treturn;\n \thashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,\n-\t\t\tistate->cache_nr);\n+\t\t\tNULL, istate->cache_nr);\n \thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,\n-\t\t\tistate->cache_nr);\n+\t\t\tNULL, istate->cache_nr);\n \n \tif (lookup_lazy_params(istate)) {\n \t\thashmap_disallow_rehash(&istate->dir_hash, 1);\ndiff --git a/oidset.c b/oidset.c\nindex ac169f05d3..a6a08ba52a 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -6,7 +6,8 @@ struct oidset_entry {\n \tstruct object_id oid;\n };\n \n-static int oidset_hashcmp(const void *va, const void *vb,\n+static int oidset_hashcmp(const void *unused_cmp_data,\n+\t\t\t  const void *va, const void *vb,\n \t\t\t  const void *vkey)\n {\n \tconst struct oidset_entry *a = va, *b = vb;\n@@ -30,7 +31,7 @@ int oidset_insert(struct oidset *set, const struct object_id *oid)\n \tstruct oidset_entry *entry;\n \n \tif (!set->map.cmpfn)\n-\t\thashmap_init(&set->map, oidset_hashcmp, 0);\n+\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n \n \tif (oidset_contains(set, oid))\n \t\treturn 1;\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 9c0ab9e67a..815c115811 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -35,7 +35,8 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n  * the side of safety.  The actual value being negative does not have\n  * any significance; only that it is non-zero matters.\n  */\n-static int patch_id_cmp(struct patch_id *a,\n+static int patch_id_cmp(const void *unused_cmp_data,\n+\t\t\tstruct patch_id *a,\n \t\t\tstruct patch_id *b,\n \t\t\tstruct diff_options *opt)\n {\n@@ -57,7 +58,8 @@ int init_patch_ids(struct patch_ids *ids)\n \tids->diffopts.detect_rename = 0;\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n-\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n+\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n+\t\t     NULL, 256);\n \treturn 0;\n }\n \ndiff --git a/refs.c b/refs.c\nindex 88658ba769..eef1a7b67d 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1525,7 +1525,8 @@ struct ref_store_hash_entry\n \tchar name[FLEX_ARRAY];\n };\n \n-static int ref_store_hash_cmp(const void *entry, const void *entry_or_key,\n+static int ref_store_hash_cmp(const void *unused_cmp_data,\n+\t\t\t      const void *entry, const void *entry_or_key,\n \t\t\t      const void *keydata)\n {\n \tconst struct ref_store_hash_entry *e1 = entry, *e2 = entry_or_key;\n@@ -1608,7 +1609,7 @@ static void register_ref_store_map(struct hashmap *map,\n \t\t\t\t   const char *name)\n {\n \tif (!map->tablesize)\n-\t\thashmap_init(map, ref_store_hash_cmp, 0);\n+\t\thashmap_init(map, ref_store_hash_cmp, NULL, 0);\n \n \tif (hashmap_put(map, alloc_ref_store_hash_entry(name, refs)))\n \t\tdie(\"BUG: %s ref_store '%s' initialized twice\", type, name);\ndiff --git a/remote.c b/remote.c\nindex d87482573d..60d0043921 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -133,7 +133,10 @@ struct remotes_hash_key {\n \tint len;\n };\n \n-static int remotes_hash_cmp(const struct remote *a, const struct remote *b, const struct remotes_hash_key *key)\n+static int remotes_hash_cmp(const void *unused_cmp_data,\n+\t\t\t    const struct remote *a,\n+\t\t\t    const struct remote *b,\n+\t\t\t    const struct remotes_hash_key *key)\n {\n \tif (key)\n \t\treturn strncmp(a->name, key->str, key->len) || a->name[key->len];\n@@ -144,7 +147,7 @@ static int remotes_hash_cmp(const struct remote *a, const struct remote *b, cons\n static inline void init_remotes_hash(void)\n {\n \tif (!remotes_hash.cmpfn)\n-\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, 0);\n+\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, NULL, 0);\n }\n \n static struct remote *make_remote(const char *name, int len)\ndiff --git a/sha1_file.c b/sha1_file.c\nindex fb1fd809dc..8c523a5b74 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2389,7 +2389,8 @@ static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,\n \treturn a->p == b->p && a->base_offset == b->base_offset;\n }\n \n-static int delta_base_cache_hash_cmp(const void *va, const void *vb,\n+static int delta_base_cache_hash_cmp(const void *unused_cmp_data,\n+\t\t\t\t     const void *va, const void *vb,\n \t\t\t\t     const void *vkey)\n {\n \tconst struct delta_base_cache_entry *a = va, *b = vb;\n@@ -2472,7 +2473,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tlist_add_tail(&ent->lru, &delta_base_cache_lru);\n \n \tif (!delta_base_cache.cmpfn)\n-\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, 0);\n+\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);\n \thashmap_entry_init(ent, pack_entry_hash(p, base_offset));\n \thashmap_add(&delta_base_cache, ent);\n }\ndiff --git a/sub-process.c b/sub-process.c\nindex 92f8aea70a..a3cfab1a9d 100644\n--- a/sub-process.c\n+++ b/sub-process.c\n@@ -5,9 +5,10 @@\n #include \"sigchain.h\"\n #include \"pkt-line.h\"\n \n-int cmd2process_cmp(const struct subprocess_entry *e1,\n-\t\t\t   const struct subprocess_entry *e2,\n-\t\t\t   const void *unused)\n+int cmd2process_cmp(const void *unused_cmp_data,\n+\t\t    const struct subprocess_entry *e1,\n+\t\t    const struct subprocess_entry *e2,\n+\t\t    const void *unused_keydata)\n {\n \treturn strcmp(e1->cmd, e2->cmd);\n }\ndiff --git a/sub-process.h b/sub-process.h\nindex d9a45cd359..96a2cca360 100644\n--- a/sub-process.h\n+++ b/sub-process.h\n@@ -20,8 +20,10 @@ struct subprocess_entry {\n \n /* subprocess functions */\n \n-int cmd2process_cmp(const struct subprocess_entry *e1,\n-\tconst struct subprocess_entry *e2, const void *unused);\n+extern int cmd2process_cmp(const void *unused_cmp_data,\n+\t\t\t   const struct subprocess_entry *e1,\n+\t\t\t   const struct subprocess_entry *e2,\n+\t\t\t   const void *unused_keydata);\n \n typedef int(*subprocess_start_fn)(struct subprocess_entry *entry);\n int subprocess_start(struct hashmap *hashmap, struct subprocess_entry *entry, const char *cmd,\ndiff --git a/submodule-config.c b/submodule-config.c\nindex d8f8d5ea32..0e1126183d 100644\n--- a/submodule-config.c\n+++ b/submodule-config.c\n@@ -34,17 +34,19 @@ enum lookup_type {\n static struct submodule_cache the_submodule_cache;\n static int is_cache_init;\n \n-static int config_path_cmp(const struct submodule_entry *a,\n+static int config_path_cmp(const void *unused_cmp_data,\n+\t\t\t   const struct submodule_entry *a,\n \t\t\t   const struct submodule_entry *b,\n-\t\t\t   const void *unused)\n+\t\t\t   const void *unused_keydata)\n {\n \treturn strcmp(a->config->path, b->config->path) ||\n \t       hashcmp(a->config->gitmodules_sha1, b->config->gitmodules_sha1);\n }\n \n-static int config_name_cmp(const struct submodule_entry *a,\n+static int config_name_cmp(const void *unused_cmp_data,\n+\t\t\t   const struct submodule_entry *a,\n \t\t\t   const struct submodule_entry *b,\n-\t\t\t   const void *unused)\n+\t\t\t   const void *unused_keydata)\n {\n \treturn strcmp(a->config->name, b->config->name) ||\n \t       hashcmp(a->config->gitmodules_sha1, b->config->gitmodules_sha1);\n@@ -52,8 +54,8 @@ static int config_name_cmp(const struct submodule_entry *a,\n \n static void cache_init(struct submodule_cache *cache)\n {\n-\thashmap_init(&cache->for_path, (hashmap_cmp_fn) config_path_cmp, 0);\n-\thashmap_init(&cache->for_name, (hashmap_cmp_fn) config_name_cmp, 0);\n+\thashmap_init(&cache->for_path, (hashmap_cmp_fn) config_path_cmp, NULL, 0);\n+\thashmap_init(&cache->for_name, (hashmap_cmp_fn) config_name_cmp, NULL, 0);\n }\n \n static void free_one_config(struct submodule_entry *entry)\ndiff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c\nindex 7aa9440e27..095d7395f3 100644\n--- a/t/helper/test-hashmap.c\n+++ b/t/helper/test-hashmap.c\n@@ -13,14 +13,18 @@ static const char *get_value(const struct test_entry *e)\n \treturn e->key + strlen(e->key) + 1;\n }\n \n-static int test_entry_cmp(const struct test_entry *e1,\n-\t\tconst struct test_entry *e2, const char* key)\n+static int test_entry_cmp(const void *unused_cmp_data,\n+\t\t\t  const struct test_entry *e1,\n+\t\t\t  const struct test_entry *e2,\n+\t\t\t  const char* key)\n {\n \treturn strcmp(e1->key, key ? key : e2->key);\n }\n \n-static int test_entry_cmp_icase(const struct test_entry *e1,\n-\t\tconst struct test_entry *e2, const char* key)\n+static int test_entry_cmp_icase(const void *unused_cmp_data,\n+\t\t\t\tconst struct test_entry *e1,\n+\t\t\t\tconst struct test_entry *e2,\n+\t\t\t\tconst char* key)\n {\n \treturn strcasecmp(e1->key, key ? key : e2->key);\n }\n@@ -92,7 +96,8 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\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+\t\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp,\n+\t\t\t\t     NULL, 0);\n \n \t\t\t/* add entries */\n \t\t\tfor (i = 0; i < TEST_SIZE; i++) {\n@@ -104,7 +109,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)\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+\t\thashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, NULL, 0);\n \n \t\t/* fill the map (sparsely if specified) */\n \t\tj = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;\n@@ -147,7 +152,7 @@ int cmd_main(int argc, const char **argv)\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+\t\t\t: test_entry_cmp), NULL, 0);\n \n \t/* process commands from stdin */\n \twhile (fgets(line, sizeof(line), stdin)) {\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323596","messageId":"20170630191407.5381-3-sbeller@google.com","threadId":"46284","inReplyTo":"20170630191407.5381-1-sbeller@google.com","subject":"[PATCHv3 2/3] patch-ids.c: use hashmap correctly","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T19:14:06Z","receivedAt":"2017-06-30T19:14:24Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"As eluded to in the previous patch, the code in patch-ids.c is using\nthe hashmaps API wrong.\n\nLuckily we do not have a bug, as all hashmap functionality that we use\nhere (hashmap_get) passes through the keydata.  If hashmap_get_next were\nto be used, a bug would occur as that passes NULL for the key_data.\n\nSo instead use the hashmap API correctly and provide the caller required\ndata in the compare function via the first argument that always gets\npassed and was setup via the hashmap_init function.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n patch-ids.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 815c115811..b4166b0f38 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -35,10 +35,10 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n  * the side of safety.  The actual value being negative does not have\n  * any significance; only that it is non-zero matters.\n  */\n-static int patch_id_cmp(const void *unused_cmp_data,\n+static int patch_id_cmp(struct diff_options *opt,\n \t\t\tstruct patch_id *a,\n \t\t\tstruct patch_id *b,\n-\t\t\tstruct diff_options *opt)\n+\t\t\tconst void *unused_keydata)\n {\n \tif (is_null_oid(&a->patch_id) &&\n \t    commit_patch_id(a->commit, opt, &a->patch_id, 0))\n@@ -59,7 +59,7 @@ int init_patch_ids(struct patch_ids *ids)\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n \thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n-\t\t     NULL, 256);\n+\t\t     &ids->diffopts, 256);\n \treturn 0;\n }\n \n@@ -95,7 +95,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n \tif (init_patch_id_entry(&patch, commit, ids))\n \t\treturn NULL;\n \n-\treturn hashmap_get(&ids->patches, &patch, &ids->diffopts);\n+\treturn hashmap_get(&ids->patches, &patch, NULL);\n }\n \n struct patch_id *add_commit_patch_id(struct commit *commit,\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323597","messageId":"20170630191407.5381-4-sbeller@google.com","threadId":"46284","inReplyTo":"20170630191407.5381-1-sbeller@google.com","subject":"[PATCHv3 3/3] hashmap: migrate documentation from Documentation/technical into header","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-06-30T19:14:07Z","receivedAt":"2017-06-30T19:14:35Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"While at it, clarify the use of `key`, `keydata`, `entry_or_key` as well\nas documenting the new data pointer for the compare function.\n\nRework the example.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/technical/api-hashmap.txt | 309 ----------------------------\n hashmap.h                               | 348 +++++++++++++++++++++++++++++---\n 2 files changed, 316 insertions(+), 341 deletions(-)\n delete mode 100644 Documentation/technical/api-hashmap.txt\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\ndeleted file mode 100644\nindex ccc634bbd7..0000000000\n--- a/Documentation/technical/api-hashmap.txt\n+++ /dev/null\n@@ -1,309 +0,0 @@\n-hashmap API\n-===========\n-\n-The hashmap API is a generic implementation of hash-based key-value mappings.\n-\n-Data Structures\n----------------\n-\n-`struct hashmap`::\n-\n-\tThe hash table structure. 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 (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-When `disallow_rehash` is set, automatic rehashes are prevented during inserts\n-and deletes.\n-\n-`struct hashmap_entry`::\n-\n-\tAn opaque structure representing an entry in the hash table, which must\n-\tbe used as first member of user data structures. Ideally it should be\n-\tfollowed by an int-sized member to prevent unused memory on 64-bit\n-\tsystems due to alignment.\n-+\n-The `hash` member is the entry's hash code and the `next` member points to the\n-next entry in case of collisions (i.e. if multiple entries map to the same\n-bucket).\n-\n-`struct hashmap_iter`::\n-\n-\tAn iterator structure, to be used with hashmap_iter_* functions.\n-\n-Types\n------\n-\n-`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::\n-\n-\tUser-supplied function to test two hashmap entries for equality. Shall\n-\treturn 0 if the entries are equal.\n-+\n-This function is always called with non-NULL `entry` / `entry_or_key`\n-parameters that have the same hash code. When looking up an entry, the `key`\n-and `keydata` parameters to hashmap_get and hashmap_remove are always passed\n-as second and third argument, respectively. Otherwise, `keydata` is NULL.\n-\n-Functions\n----------\n-\n-`unsigned int strhash(const char *buf)`::\n-`unsigned int strihash(const char *buf)`::\n-`unsigned int memhash(const void *buf, size_t len)`::\n-`unsigned int memihash(const void *buf, size_t len)`::\n-`unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)`::\n-\n-\tReady-to-use hash functions for strings, using the FNV-1 algorithm (see\n-\thttp://www.isthe.com/chongo/tech/comp/fnv).\n-+\n-`strhash` and `strihash` take 0-terminated strings, while `memhash` and\n-`memihash` operate on arbitrary-length memory.\n-+\n-`strihash` and `memihash` are case insensitive versions.\n-+\n-`memihash_cont` is a variant of `memihash` that allows a computation to be\n-continued with another chunk of data.\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.\n-+\n-`map` is the hashmap to initialize.\n-+\n-The `equals_function` can be specified to compare two entries for equality.\n-If NULL, entries are considered equal if their hash codes are equal.\n-+\n-If the total number of entries is known in advance, the `initial_size`\n-parameter may be used to preallocate a sufficiently large table and thus\n-prevent expensive resizing. If 0, the table is dynamically resized.\n-\n-`void hashmap_free(struct hashmap *map, int free_entries)`::\n-\n-\tFrees a hashmap structure and allocated memory.\n-+\n-`map` is the hashmap to free.\n-+\n-If `free_entries` is true, each hashmap_entry in the map is freed as well\n-(using stdlib's free()).\n-\n-`void hashmap_entry_init(void *entry, unsigned int hash)`::\n-\n-\tInitializes a hashmap_entry structure.\n-+\n-`entry` points to the entry to initialize.\n-+\n-`hash` is the hash code of the entry.\n-+\n-The hashmap_entry structure does not hold references to external resources,\n-and it is safe to just discard it once you are done with it (i.e. if\n-your structure was allocated with xmalloc(), you can just free(3) it,\n-and if it is on stack, you can just let it go out of scope).\n-\n-`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::\n-\n-\tReturns the hashmap entry for the specified key, or NULL if not found.\n-+\n-`map` is the hashmap structure.\n-+\n-`key` is a hashmap_entry structure (or user data structure that starts with\n-hashmap_entry) that has at least been initialized with the proper hash code\n-(via `hashmap_entry_init`).\n-+\n-If an entry with matching hash code is found, `key` and `keydata` are passed\n-to `hashmap_cmp_fn` to decide whether the entry matches the key.\n-\n-`void *hashmap_get_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\n-\tused to iterate over duplicate entries (see `hashmap_add`).\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the hashmap_entry to start the search from, obtained via a previous\n-call to `hashmap_get` or `hashmap_get_next`.\n-\n-`void hashmap_add(struct hashmap *map, void *entry)`::\n-\n-\tAdds a hashmap entry. This allows to add duplicate entries (i.e.\n-\tseparate values with the same key according to hashmap_cmp_fn).\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the entry to add.\n-\n-`void *hashmap_put(struct hashmap *map, void *entry)`::\n-\n-\tAdds or replaces a hashmap entry. If the hashmap contains duplicate\n-\tentries equal to the specified entry, only one of them will be replaced.\n-+\n-`map` is the hashmap structure.\n-+\n-`entry` is the entry to add or replace.\n-+\n-Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n-\n-`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::\n-\n-\tRemoves a hashmap entry matching the specified key. If the hashmap\n-\tcontains duplicate entries equal to the specified key, only one of\n-\tthem will be removed.\n-+\n-`map` is the hashmap structure.\n-+\n-`key` is a hashmap_entry structure (or user data structure that starts with\n-hashmap_entry) that has at least been initialized with the proper hash code\n-(via `hashmap_entry_init`).\n-+\n-If an entry with matching hash code is found, `key` and `keydata` are\n-passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n-+\n-Returns the removed entry, or NULL if not found.\n-\n-`void hashmap_disallow_rehash(struct hashmap *map, unsigned value)`::\n-\n-\tDisallow/allow automatic rehashing of the hashmap during inserts\n-\tand deletes.\n-+\n-This is useful if the caller knows that the hashmap will be accessed\n-by multiple threads.\n-+\n-The caller is still responsible for any necessary locking; this simply\n-prevents unexpected rehashing.  The caller is also responsible for properly\n-sizing the initial hashmap to ensure good performance.\n-+\n-A call to allow rehashing does not force a rehash; that might happen\n-with the next insert or delete.\n-\n-`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::\n-`void *hashmap_iter_next(struct hashmap_iter *iter)`::\n-`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::\n-\n-\tUsed to iterate over all entries of a hashmap. Note that it is\n-\tnot safe to add or remove entries to the hashmap while\n-\titerating.\n-+\n-`hashmap_iter_init` initializes a `hashmap_iter` structure.\n-+\n-`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no\n-more entries.\n-+\n-`hashmap_iter_first` is a combination of both (i.e. initializes the iterator\n-and returns the first entry, if any).\n-\n-`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-Here's a simple usage example that maps long keys to double values.\n-------------\n-struct hashmap map;\n-\n-struct long2double {\n-\tstruct hashmap_entry ent; /* must be the first member! */\n-\tlong key;\n-\tdouble value;\n-};\n-\n-static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)\n-{\n-\treturn !(e1->key == e2->key);\n-}\n-\n-void long2double_init(void)\n-{\n-\thashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);\n-}\n-\n-void long2double_free(void)\n-{\n-\thashmap_free(&map, 1);\n-}\n-\n-static struct long2double *find_entry(long key)\n-{\n-\tstruct long2double k;\n-\thashmap_entry_init(&k, memhash(&key, sizeof(long)));\n-\tk.key = key;\n-\treturn hashmap_get(&map, &k, NULL);\n-}\n-\n-double get_value(long key)\n-{\n-\tstruct long2double *e = find_entry(key);\n-\treturn e ? e->value : 0;\n-}\n-\n-void set_value(long key, double value)\n-{\n-\tstruct long2double *e = find_entry(key);\n-\tif (!e) {\n-\t\te = malloc(sizeof(struct long2double));\n-\t\thashmap_entry_init(e, memhash(&key, sizeof(long)));\n-\t\te->key = key;\n-\t\thashmap_add(&map, e);\n-\t}\n-\te->value = value;\n-}\n-------------\n-\n-Using variable-sized keys\n--------------------------\n-\n-The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary\n-`hashmap_entry` structure as key to find the correct entry. If the key data is\n-variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable\n-to create a full-fledged entry structure on the heap and copy all the key data\n-into the structure.\n-\n-In this case, the `keydata` parameter can be used to pass\n-variable-sized key data directly to the comparison function, and the `key`\n-parameter can be a stripped-down, fixed size entry structure allocated on the\n-stack.\n-\n-See test-hashmap.c for an example using arbitrary-length strings as keys.\ndiff --git a/hashmap.h b/hashmap.h\nindex aaf09e047e..7a8fa7fa3d 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -3,17 +3,123 @@\n \n /*\n  * Generic implementation of hash-based key-value mappings.\n- * See Documentation/technical/api-hashmap.txt.\n+ *\n+ * An example that maps long to a string:\n+ * For the sake of the example this allows to lookup exact values, too\n+ * (i.e. it is operated as a set, the value is part of the key)\n+ * -------------------------------------\n+ *\n+ * struct hashmap map;\n+ * struct long2string {\n+ *     struct hashmap_entry ent; // must be the first member!\n+ *     long key;\n+ *     char value[FLEX_ARRAY];   // be careful with allocating on stack!\n+ * };\n+ *\n+ * #define COMPARE_VALUE 1\n+ *\n+ * static int long2string_cmp(const struct long2string *e1,\n+ *                            const struct long2string *e2,\n+ *                            const void *keydata, const void *userdata)\n+ * {\n+ *     char *string = keydata;\n+ *     unsigned *flags = (unsigned*)userdata;\n+ *\n+ *     if (flags & COMPARE_VALUE)\n+ *         return !(e1->key == e2->key) || (keydata ?\n+ *                  strcmp(e1->value, keydata) : strcmp(e1->value, e2->value));\n+ *     else\n+ *         return !(e1->key == e2->key);\n+ * }\n+ *\n+ * int main(int argc, char **argv)\n+ * {\n+ *     long key;\n+ *     char *value, *action;\n+ *\n+ *     unsigned flags = ALLOW_DUPLICATE_KEYS;\n+ *\n+ *     hashmap_init(&map, (hashmap_cmp_fn) long2string_cmp, &flags, 0);\n+ *\n+ *     while (scanf(\"%s %l %s\", action, key, value)) {\n+ *\n+ *         if (!strcmp(\"add\", action)) {\n+ *             struct long2string *e;\n+ *             e = malloc(sizeof(struct long2string) + strlen(value));\n+ *             hashmap_entry_init(e, memhash(&key, sizeof(long)));\n+ *             e->key = key;\n+ *             memcpy(e->value, value, strlen(value));\n+ *             hashmap_add(&map, e);\n+ *         }\n+ *\n+ *         if (!strcmp(\"print_all_by_key\", action)) {\n+ *             flags &= ~COMPARE_VALUE;\n+ *\n+ *             struct long2string k;\n+ *             hashmap_entry_init(&k, memhash(&key, sizeof(long)));\n+ *             k.key = key;\n+ *\n+ *             struct long2string *e = hashmap_get(&map, &k, NULL);\n+ *             if (e) {\n+ *                 printf(\"first: %l %s\\n\", e->key, e->value);\n+ *                 while (e = hashmap_get_next(&map, e))\n+ *                     printf(\"found more: %l %s\\n\", e->key, e->value);\n+ *             }\n+ *         }\n+ *\n+ *         if (!strcmp(\"has_exact_match\", action)) {\n+ *             flags |= COMPARE_VALUE;\n+ *\n+ *             struct long2string *e;\n+ *             e = malloc(sizeof(struct long2string) + strlen(value));\n+ *             hashmap_entry_init(e, memhash(&key, sizeof(long)));\n+ *             e->key = key;\n+ *             memcpy(e->value, value, strlen(value));\n+ *\n+ *             printf(\"%s found\\n\", hashmap_get(&map, e, NULL) ? \"\" : \"not\");\n+ *         }\n+ *\n+ *         if (!strcmp(\"has_exact_match_no_heap_alloc\", action)) {\n+ *             flags |= COMPARE_VALUE;\n+ *\n+ *             struct long2string e;\n+ *             hashmap_entry_init(e, memhash(&key, sizeof(long)));\n+ *             e.key = key;\n+ *\n+ *             printf(\"%s found\\n\", hashmap_get(&map, e, value) ? \"\" : \"not\");\n+ *         }\n+ *\n+ *         if (!strcmp(\"end\", action)) {\n+ *             hashmap_free(&map, 1);\n+ *             break;\n+ *         }\n+ *     }\n+ * }\n  */\n \n-/* FNV-1 functions */\n-\n+/*\n+ * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see\n+ * http://www.isthe.com/chongo/tech/comp/fnv).\n+ * `strhash` and `strihash` take 0-terminated strings, while `memhash` and\n+ * `memihash` operate on arbitrary-length memory.\n+ * `strihash` and `memihash` are case insensitive versions.\n+ * `memihash_cont` is a variant of `memihash` that allows a computation to be\n+ * continued with another chunk of data.\n+ */\n extern unsigned int strhash(const char *buf);\n extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n extern unsigned int memihash(const void *buf, size_t len);\n extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);\n \n+/*\n+ * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n+ * for use in hash tables. Cryptographic hashes are supposed to have\n+ * uniform distribution, so in contrast to `memhash()`, this just copies\n+ * the first `sizeof(int)` bytes without shuffling any bits. Note that\n+ * the results will be different on big-endian and little-endian\n+ * platforms, so they should not be stored or transferred over the net.\n+ */\n static inline unsigned int sha1hash(const unsigned char *sha1)\n {\n \t/*\n@@ -25,90 +131,255 @@ static inline unsigned int sha1hash(const unsigned char *sha1)\n \treturn hash;\n }\n \n-/* data structures */\n-\n+/*\n+ * struct hashmap_entry is an opaque structure representing an entry in the\n+ * hash table, which must be used as first member of user data structures.\n+ * Ideally it should be followed by an int-sized member to prevent unused\n+ * memory on 64-bit systems due to alignment.\n+ */\n struct hashmap_entry {\n+\t/*\n+\t * next points to the next entry in case of collisions (i.e. if\n+\t * multiple entries map to the same bucket)\n+\t */\n \tstruct hashmap_entry *next;\n+\n+\t/* entry's hash code */\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.\n+ *\n+ * This function is always called with non-NULL `entry` and `entry_or_key`\n+ * parameters that have the same hash code.\n+ *\n+ * When looking up an entry, the `key` and `keydata` parameters to hashmap_get\n+ * and hashmap_remove are always passed as second `entry_or_key` and third\n+ * argument `keydata`, respectively. Otherwise, `keydata` is NULL.\n+ *\n+ * When it is too expensive to allocate a user entry (either because it is\n+ * large or varialbe sized, such that it is not on the stack), then the\n+ * relevant data to check for equality should be passed via `keydata`.\n+ * In this case `key` can be a stripped down version of the user key data\n+ * or even just a hashmap_entry having the correct hash.\n+ *\n+ * The `hashmap_cmp_fn_data` entry is the pointer given in the init function.\n+ */\n typedef int (*hashmap_cmp_fn)(const void *hashmap_cmp_fn_data,\n \t\t\t      const void *entry, const void *entry_or_key,\n \t\t\t      const void *keydata);\n \n+/*\n+ * struct hashmap is the hash table structure. Members can be used as follows,\n+ * but should not be modified directly.\n+ */\n struct hashmap {\n \tstruct hashmap_entry **table;\n+\n+\t/* Stores the comparison function specified in `hashmap_init()`. */\n \thashmap_cmp_fn cmpfn;\n \tconst void *cmpfn_data;\n-\tunsigned int size, tablesize, grow_at, shrink_at;\n-\tunsigned disallow_rehash : 1;\n-};\n \n-struct hashmap_iter {\n-\tstruct hashmap *map;\n-\tstruct hashmap_entry *next;\n-\tunsigned int tablepos;\n+\t/* total number of entries (0 means the hashmap is empty) */\n+\tunsigned int size;\n+\n+\t/*\n+\t * tablesize is the allocated size of the hash table. A non-0 value\n+\t * indicates that the hashmap is initialized. It may also be useful\n+\t * for statistical purposes (i.e. `size / tablesize` is the current\n+\t * load factor).\n+\t */\n+\tunsigned int tablesize;\n+\n+\tunsigned int grow_at;\n+\tunsigned int shrink_at;\n+\n+\t/* See `hashmap_disallow_rehash`. */\n+\tunsigned disallow_rehash : 1;\n };\n \n /* hashmap functions */\n \n+/*\n+ * Initializes a hashmap structure.\n+ *\n+ * `map` is the hashmap to initialize.\n+ *\n+ * The `equals_function` can be specified to compare two entries for equality.\n+ * If NULL, entries are considered equal if their hash codes are equal.\n+ *\n+ * The `equals_function_data` parameter can be used to provide additional data\n+ * (a callback cookie) that will be passed to `equals_function` each time it\n+ * is called. This allows a single `equals_function` to implement multiple\n+ * comparison functions.\n+ *\n+ * If the total number of entries is known in advance, the `initial_size`\n+ * parameter may be used to preallocate a sufficiently large table and thus\n+ * prevent expensive resizing. If 0, the table is dynamically resized.\n+ */\n extern void hashmap_init(struct hashmap *map,\n \t\t\t hashmap_cmp_fn equals_function,\n \t\t\t const void *equals_function_data,\n \t\t\t size_t initial_size);\n+\n+/*\n+ * Frees a hashmap structure and allocated memory.\n+ *\n+ * If `free_entries` is true, each hashmap_entry in the map is freed as well\n+ * using stdlibs free().\n+ */\n extern void hashmap_free(struct hashmap *map, int free_entries);\n \n /* hashmap_entry functions */\n \n+/*\n+ * Initializes a hashmap_entry structure.\n+ *\n+ * `entry` points to the entry to initialize.\n+ * `hash` is the hash code of the entry.\n+ *\n+ * The hashmap_entry structure does not hold references to external resources,\n+ * and it is safe to just discard it once you are done with it (i.e. if\n+ * your structure was allocated with xmalloc(), you can just free(3) it,\n+ * and if it is on stack, you can just let it go out of scope).\n+ */\n static inline void hashmap_entry_init(void *entry, unsigned int hash)\n {\n \tstruct hashmap_entry *e = entry;\n \te->hash = hash;\n \te->next = NULL;\n }\n+\n+/*\n+ * Returns the hashmap entry for the specified key, or NULL if not found.\n+ *\n+ * `map` is the hashmap structure.\n+ *\n+ * `key` is a user data structure that starts with hashmap_entry that has at\n+ * least been initialized with the proper hash code (via `hashmap_entry_init`).\n+ *\n+ * `keydata` is a data structure that holds just enough information to check\n+ * for equality to a given entry.\n+ *\n+ * If the key data is variable-sized (e.g. a FLEX_ARRAY string) or quite large,\n+ * it is undesirable to create a full-fledged entry structure on the heap and\n+ * copy all the key data into the structure.\n+ *\n+ * In this case, the `keydata` parameter can be used to pass\n+ * variable-sized key data directly to the comparison function, and the `key`\n+ * parameter can be a stripped-down, fixed size entry structure allocated on the\n+ * stack.\n+ *\n+ * 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 extern void *hashmap_get(const struct hashmap *map, const void *key,\n-\t\tconst void *keydata);\n-extern void *hashmap_get_next(const struct hashmap *map, const void *entry);\n-extern void hashmap_add(struct hashmap *map, void *entry);\n-extern void *hashmap_put(struct hashmap *map, void *entry);\n-extern void *hashmap_remove(struct hashmap *map, const void *key,\n-\t\tconst void *keydata);\n+\t\t\t const void *keydata);\n \n+/*\n+ * Returns the hashmap entry for the specified hash code and key data,\n+ * or NULL if not found.\n+ *\n+ * `map` is the hashmap structure.\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 of `hashmap_cmp_fn` points to a hashmap_entry\n+ * structure that should not be used in the comparison.\n+ */\n static inline void *hashmap_get_from_hash(const struct hashmap *map,\n-\t\tunsigned int hash, const void *keydata)\n+\t\t\t\t\t  unsigned int hash,\n+\t\t\t\t\t  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+/*\n+ * Returns the next equal hashmap entry, or NULL if not found. This can be\n+ * used to iterate over duplicate entries (see `hashmap_add`).\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the hashmap_entry to start the search from, obtained via a previous\n+ * call to `hashmap_get` or `hashmap_get_next`.\n+ */\n+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.\n+ * separate values with the same key according to hashmap_cmp_fn).\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the entry to add.\n+ */\n+extern void hashmap_add(struct hashmap *map, void *entry);\n+\n+/*\n+ * Adds or replaces a hashmap entry. If the hashmap contains duplicate\n+ * entries equal to the specified entry, only one of them will be replaced.\n+ *\n+ * `map` is the hashmap structure.\n+ * `entry` is the entry to add or replace.\n+ * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n+ */\n+extern void *hashmap_put(struct hashmap *map, void *entry);\n+\n+/*\n+ * Removes a hashmap entry matching the specified key. If the hashmap contains\n+ * duplicate entries equal to the specified key, only one of them will be\n+ * removed. Returns the removed entry, or NULL if not found.\n+ *\n+ * Argument explanation is the same as in `hashmap_get`.\n+ */\n+extern void *hashmap_remove(struct hashmap *map, const void *key,\n+\t\tconst void *keydata);\n+\n+/*\n+ * Returns the `bucket` an entry is stored in.\n+ * Useful for multithreaded read access.\n+ */\n int hashmap_bucket(const struct hashmap *map, unsigned int hash);\n \n /*\n  * Disallow/allow rehashing of the hashmap.\n- * This is useful if the caller knows that the hashmap\n- * needs multi-threaded access.  The caller is still\n- * required to guard/lock searches and inserts in a\n- * manner appropriate to their usage.  This simply\n- * prevents the table from being unexpectedly re-mapped.\n+ * This is useful if the caller knows that the hashmap needs multi-threaded\n+ * access.  The caller is still required to guard/lock searches and inserts\n+ * in a manner appropriate to their usage.  This simply prevents the table\n+ * from being unexpectedly re-mapped.\n  *\n- * If is up to the caller to ensure that the hashmap is\n- * initialized to a reasonable size to prevent poor\n- * performance.\n+ * It is up to the caller to ensure that the hashmap is initialized to a\n+ * reasonable size to prevent poor performance.\n  *\n- * When value=1, prevent future rehashes on adds and deleted.\n- * When value=0, allow future rehahses.  This DOES NOT force\n- * a rehash now.\n+ * A call to allow rehashing does not force a rehash; that might happen\n+ * with the next insert or delete.\n  */\n static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)\n {\n \tmap->disallow_rehash = value;\n }\n \n-/* hashmap_iter functions */\n+/*\n+ * Used to iterate over all entries of a hashmap. Note that it is\n+ * not safe to add or remove entries to the hashmap while\n+ * iterating.\n+ */\n+struct hashmap_iter {\n+\tstruct hashmap *map;\n+\tstruct hashmap_entry *next;\n+\tunsigned int tablepos;\n+};\n \n+/* Initializes a `hashmap_iter` structure. */\n extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n+\n+/* Returns the next hashmap_entry, or NULL if there are no more entries. */\n extern void *hashmap_iter_next(struct hashmap_iter *iter);\n+\n+/* Initializes the iterator and returns the first entry, if any. */\n static inline void *hashmap_iter_first(struct hashmap *map,\n \t\tstruct hashmap_iter *iter)\n {\n@@ -116,8 +387,21 @@ static inline void *hashmap_iter_first(struct hashmap *map,\n \treturn hashmap_iter_next(iter);\n }\n \n-/* string interning */\n+/* String interning */\n \n+/*\n+ * Returns the unique, interned version of the specified string or data,\n+ * similar to the `String.intern` API in Java and .NET, respectively.\n+ * Interned 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 extern const void *memintern(const void *data, size_t len);\n static inline const char *strintern(const char *string)\n {\n-- \n2.13.0.31.g9b732c453e\n\n"},{"id":"323604","messageId":"xmqqefu1qmpy.fsf@gitster.mtv.corp.google.com","threadId":"46284","inReplyTo":"20170630191407.5381-3-sbeller@google.com","subject":"Re: [PATCHv3 2/3] patch-ids.c: use hashmap correctly","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-30T19:50:17Z","receivedAt":"2017-06-30T19:50:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> As eluded to in the previous patch, the code in patch-ids.c is using\n> the hashmaps API wrong.\n>\n> Luckily we do not have a bug, as all hashmap functionality that we use\n> here (hashmap_get) passes through the keydata.  If hashmap_get_next were\n> to be used, a bug would occur as that passes NULL for the key_data.\n>\n> So instead use the hashmap API correctly and provide the caller required\n> data in the compare function via the first argument that always gets\n> passed and was setup via the hashmap_init function.\n>\n> Signed-off-by: Stefan Beller <sbeller@google.com>\n> ---\n>  patch-ids.c | 8 ++++----\n>  1 file changed, 4 insertions(+), 4 deletions(-)\n\nNicely explained.  Thanks for polishing the series.\n\n>\n> diff --git a/patch-ids.c b/patch-ids.c\n> index 815c115811..b4166b0f38 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -35,10 +35,10 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n>   * the side of safety.  The actual value being negative does not have\n>   * any significance; only that it is non-zero matters.\n>   */\n> -static int patch_id_cmp(const void *unused_cmp_data,\n> +static int patch_id_cmp(struct diff_options *opt,\n>  \t\t\tstruct patch_id *a,\n>  \t\t\tstruct patch_id *b,\n> -\t\t\tstruct diff_options *opt)\n> +\t\t\tconst void *unused_keydata)\n>  {\n>  \tif (is_null_oid(&a->patch_id) &&\n>  \t    commit_patch_id(a->commit, opt, &a->patch_id, 0))\n> @@ -59,7 +59,7 @@ int init_patch_ids(struct patch_ids *ids)\n>  \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n>  \tdiff_setup_done(&ids->diffopts);\n>  \thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp,\n> -\t\t     NULL, 256);\n> +\t\t     &ids->diffopts, 256);\n>  \treturn 0;\n>  }\n>  \n> @@ -95,7 +95,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n>  \tif (init_patch_id_entry(&patch, commit, ids))\n>  \t\treturn NULL;\n>  \n> -\treturn hashmap_get(&ids->patches, &patch, &ids->diffopts);\n> +\treturn hashmap_get(&ids->patches, &patch, NULL);\n>  }\n>  \n>  struct patch_id *add_commit_patch_id(struct commit *commit,\n"},{"id":"323832","messageId":"20170705090003.ervwwantjliim3az@sigill.intra.peff.net","threadId":"46284","inReplyTo":"20170630191407.5381-3-sbeller@google.com","subject":"Re: [PATCHv3 2/3] patch-ids.c: use hashmap correctly","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-05T09:00:03Z","receivedAt":"2017-07-05T09:00:10Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 30, 2017 at 12:14:06PM -0700, Stefan Beller wrote:\n\n> As eluded to in the previous patch, the code in patch-ids.c is using\n> the hashmaps API wrong.\n> \n> Luckily we do not have a bug, as all hashmap functionality that we use\n> here (hashmap_get) passes through the keydata.  If hashmap_get_next were\n> to be used, a bug would occur as that passes NULL for the key_data.\n> \n> So instead use the hashmap API correctly and provide the caller required\n> data in the compare function via the first argument that always gets\n> passed and was setup via the hashmap_init function.\n\nReviewing this a bit late, but it looks good to me. And I think the\nexplanation above nicely covers what is going on (and why it isn't a\nbug).\n\n-Peff\n\nPS I think you meant \"alluded\" in the first sentence, unless you really\n   were trying to escape the previous patch. :)\n"}]}