{"thread":{"id":"49433","subject":"[PATCH] fetch: replace string-list used as a look-up table with a hashmap","startedAt":"2018-09-26T21:28:34Z","lastAt":"2018-10-31T14:50:15Z","messageCount":11,"participants":["Junio C Hamano","Stefan Beller","Jeff King","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"359008","messageId":"xmqqin2sj6df.fsf@gitster-ct.c.googlers.com","threadId":"49433","inReplyTo":null,"subject":"[PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-26T21:28:28Z","receivedAt":"2018-09-26T21:28:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In find_non_local_tags() helper function (used to implement the\n\"follow tags\"), we use string_list_has_string() on two string lists\nas a way to see if a refname has already been processed, etc.\n\nAll this code predates more modern in-core lookup API like hashmap;\nreplace them with two hashmaps and one string list---the hashmaps\nare used for look-ups and the string list is to keep the order of\nitems in the returned result stable (which is the only single thing\nhashmap does worse than lookups on string-list).\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * Just to remind ourselves that we talked about getting rid of\n   string-list used as look-up tables by replacing them with hashmap\n   but haven't seen much effort expended on it.  I think this is my\n   first semi-serious use of hashmap, and the code is expected to be\n   full of newbie mistakes, inefficiencies and ignorance of idioms;\n   pointing out any of which is much appreciated.\n\n builtin/fetch.c | 116 +++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 90 insertions(+), 26 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 0696abfc2a..5d1fd8dd49 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -246,16 +246,73 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)\n \treturn 0;\n }\n \n+struct refname_hash_entry {\n+\tstruct hashmap_entry ent; /* must be the first member */\n+\tstruct object_id oid;\n+\tchar refname[FLEX_ARRAY];\n+};\n+\n+static int refname_hash_entry_cmp(const void *hashmap_cmp_fn_data,\n+\t\t\t\t  const struct refname_hash_entry *e1,\n+\t\t\t\t  const struct refname_hash_entry *e2,\n+\t\t\t\t  const void *keydata)\n+{\n+\treturn strcmp(e1->refname, keydata ? keydata : e2->refname);\n+}\n+\n+static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n+\t\t\t\t\t\t   const char *refname,\n+\t\t\t\t\t\t   const struct object_id *oid)\n+{\n+\tstruct refname_hash_entry *ent;\n+\tsize_t len = strlen(refname);\n+\n+\tFLEX_ALLOC_MEM(ent, refname, refname, len);\n+\thashmap_entry_init(ent, memhash(refname, len));\n+\toidcpy(&ent->oid, oid);\n+\thashmap_add(map, ent);\n+\treturn ent;\n+}\n+\n+static int add_one_refname(const char *refname,\n+\t\t\t   const struct object_id *oid,\n+\t\t\t   int flag, void *cbdata)\n+{\n+\tstruct hashmap *refname_map = cbdata;\n+\n+\t(void) refname_hash_add(refname_map, refname, oid);\n+\treturn 0;\n+}\n+\n+static void refname_hash_init(struct hashmap *map)\n+{\n+\thashmap_init(map, (hashmap_cmp_fn)refname_hash_entry_cmp, NULL, 0);\n+}\n+\n+static int refname_hash_exists(struct hashmap *map, const char *refname)\n+{\n+\tstruct hashmap_entry key;\n+\tsize_t len = strlen(refname);\n+\thashmap_entry_init(&key, memhash(refname, len));\n+\n+\treturn !!hashmap_get(map, &key, refname);\n+}\n+\n static void find_non_local_tags(const struct ref *refs,\n \t\t\t\tstruct ref **head,\n \t\t\t\tstruct ref ***tail)\n {\n-\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n-\tstruct string_list remote_refs = STRING_LIST_INIT_NODUP;\n+\tstruct hashmap existing_refs;\n+\tstruct hashmap remote_refs;\n+\tstruct string_list remote_refs_list = STRING_LIST_INIT_NODUP;\n+\tstruct string_list_item *remote_ref_item;\n \tconst struct ref *ref;\n-\tstruct string_list_item *item = NULL;\n+\tstruct refname_hash_entry *item = NULL;\n \n-\tfor_each_ref(add_existing, &existing_refs);\n+\trefname_hash_init(&existing_refs);\n+\trefname_hash_init(&remote_refs);\n+\n+\tfor_each_ref(add_one_refname, &existing_refs);\n \tfor (ref = refs; ref; ref = ref->next) {\n \t\tif (!starts_with(ref->name, \"refs/tags/\"))\n \t\t\tcontinue;\n@@ -271,10 +328,10 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n \t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n-\t\t\t    !has_sha1_file_with_flags(item->util,\n+\t\t\t    !has_sha1_file_with_flags(item->oid.hash,\n \t\t\t\t\t\t      OBJECT_INFO_QUICK) &&\n-\t\t\t    !will_fetch(head, item->util))\n-\t\t\t\titem->util = NULL;\n+\t\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\t\toidclr(&item->oid);\n \t\t\titem = NULL;\n \t\t\tcontinue;\n \t\t}\n@@ -286,47 +343,54 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t * fetch.\n \t\t */\n \t\tif (item &&\n-\t\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n-\t\t    !will_fetch(head, item->util))\n-\t\t\titem->util = NULL;\n+\t\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n+\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\toidclr(&item->oid);\n \n \t\titem = NULL;\n \n \t\t/* skip duplicates and refs that we already have */\n-\t\tif (string_list_has_string(&remote_refs, ref->name) ||\n-\t\t    string_list_has_string(&existing_refs, ref->name))\n+\t\tif (refname_hash_exists(&remote_refs, ref->name) ||\n+\t\t    refname_hash_exists(&existing_refs, ref->name))\n \t\t\tcontinue;\n \n-\t\titem = string_list_insert(&remote_refs, ref->name);\n-\t\titem->util = (void *)&ref->old_oid;\n+\t\titem = refname_hash_add(&remote_refs, ref->name, &ref->old_oid);\n+\t\tstring_list_insert(&remote_refs_list, ref->name);\n \t}\n-\tstring_list_clear(&existing_refs, 1);\n+\thashmap_free(&existing_refs, 1);\n \n \t/*\n \t * We may have a final lightweight tag that needs to be\n \t * checked to see if it needs fetching.\n \t */\n \tif (item &&\n-\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n-\t    !will_fetch(head, item->util))\n-\t\titem->util = NULL;\n+\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n+\t    !will_fetch(head, item->oid.hash))\n+\t\toidclr(&item->oid);\n \n \t/*\n-\t * For all the tags in the remote_refs string list,\n+\t * For all the tags in the remote_refs_list,\n \t * add them to the list of refs to be fetched\n \t */\n-\tfor_each_string_list_item(item, &remote_refs) {\n+\tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n+\t\tconst char *refname = remote_ref_item->string;\n+\t\tstruct hashmap_entry key;\n+\n+\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n+\t\titem = hashmap_get(&remote_refs, &key, refname);\n+\t\tif (!item)\n+\t\t\tcontinue; /* can this happen??? */\n+\n \t\t/* Unless we have already decided to ignore this item... */\n-\t\tif (item->util)\n-\t\t{\n-\t\t\tstruct ref *rm = alloc_ref(item->string);\n-\t\t\trm->peer_ref = alloc_ref(item->string);\n-\t\t\toidcpy(&rm->old_oid, item->util);\n+\t\tif (!is_null_oid(&item->oid)) {\n+\t\t\tstruct ref *rm = alloc_ref(item->refname);\n+\t\t\trm->peer_ref = alloc_ref(item->refname);\n+\t\t\toidcpy(&rm->old_oid, &item->oid);\n \t\t\t**tail = rm;\n \t\t\t*tail = &rm->next;\n \t\t}\n \t}\n-\n+\thashmap_free(&remote_refs, 1);\n \tstring_list_clear(&remote_refs, 0);\n }\n \n-- \n2.19.0-271-gfe8321ec05\n\n"},{"id":"359019","messageId":"CAGZ79kamkLV7yHtCu_qSqNzj7bJm0=Uw1CKxss+zTKJWsYz3qw@mail.gmail.com","threadId":"49433","inReplyTo":"xmqqin2sj6df.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-09-26T22:59:08Z","receivedAt":"2018-09-26T22:59:22Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Sep 26, 2018 at 2:28 PM Junio C Hamano <gitster@pobox.com> wrote:\n\n>\n> +struct refname_hash_entry {\n> +       struct hashmap_entry ent; /* must be the first member */\n\n$ git grep \"struct hashmap_entry\" reveals that we have another\nconvention that we follow but not document, which is to stress\nthe importance of putting the hashmap_entry first. ;-)\n\n> +       struct object_id oid;\n> +       char refname[FLEX_ARRAY];\n> +};\n> +\n> +static int refname_hash_entry_cmp(const void *hashmap_cmp_fn_data,\n> +                                 const struct refname_hash_entry *e1,\n> +                                 const struct refname_hash_entry *e2,\n> +                                 const void *keydata)\n> +{\n> +       return strcmp(e1->refname, keydata ? keydata : e2->refname);\n> +}\n\nand later\n\n    hashmap_init(...  (hashmap_cmp_fn)refname_hash_entry_cmp, ...);\n\nI wonder if we'd want to stick to this style, as that seems to be the easiest\nto do, and drop the efforts started in 55c965f3a2 (Merge branch\n'sb/hashmap-cleanup', 2017-08-11), that avoids the cast in the init,\nbut puts the (implicit) casts in the _cmp function as we'd take\nvoid pointers as the function signature and recast to a local variable.\n\n> +\n> +static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n> +                                                  const char *refname,\n> +                                                  const struct object_id *oid)\n> +{\n> +       struct refname_hash_entry *ent;\n> +       size_t len = strlen(refname);\n> +\n> +       FLEX_ALLOC_MEM(ent, refname, refname, len);\n> +       hashmap_entry_init(ent, memhash(refname, len));\n\nmemhash is preferred over strhash as we already know the length.\nFor a second I wondered why we use it instead of strhash\n\n> +static int refname_hash_exists(struct hashmap *map, const char *refname)\n> +{\n> +       struct hashmap_entry key;\n> +       size_t len = strlen(refname);\n> +       hashmap_entry_init(&key, memhash(refname, len));\n\nHere we could use strhash, but as they could change to\ndiffering implementation, we keep using memhash.\n\n>         /*\n> -        * For all the tags in the remote_refs string list,\n> +        * For all the tags in the remote_refs_list,\n>          * add them to the list of refs to be fetched\n>          */\n> -       for_each_string_list_item(item, &remote_refs) {\n> +       for_each_string_list_item(remote_ref_item, &remote_refs_list) {\n> +               const char *refname = remote_ref_item->string;\n> +               struct hashmap_entry key;\n> +\n> +               hashmap_entry_init(&key, memhash(refname, strlen(refname)));\n> +               item = hashmap_get(&remote_refs, &key, refname);\n\n> +               if (!item)\n> +                       continue; /* can this happen??? */\n\nI thought this could happen when we have hash collisions,\nI convinced myself otherwise, as we pass the refname to hashmap_get\nas the 'keydata', so when there is a hash collision we keep comparing\nto the real value.\n\nAnd as whenever we have an insert to remote_refs_list, we also\nhave a refname_hash_add to the remote_refs hashmap,\nI think the return of NULL is not possible, and we could switch\nit to BUG(...);\n\n\n> All this code predates more modern in-core lookup API like hashmap;\n> replace them with two hashmaps and one string list---the hashmaps\n> are used for look-ups and the string list is to keep the order of\n> items in the returned result stable (which is the only single thing\n> hashmap does worse than lookups on string-list).\n>\n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n\nI wonder if we want to add an API to the hashmap that allows for ordered\niteration (as hashmap_iter_* relies on the hashing function for its output)\n\nI think it may be too early to do so, but there are 2 thoughts on how to do it:\n* Each element keeps (prev/next) pointers to the previously inserted\n  element and updates the next pointer when the next element is inserted.\n  When removing elements we'd have to update the next and prev pointer\n  of the adjacent elements.\n  Then iteration can be done in insertion-order.\n  Probably this would go into its own file ordered-hashmap.{c, h}\n* provide an order function to hashmap_iter_init, which then\n  orders according to that function before the first call of\n  hashmap_iter_next returns.\n\n>  * Just to remind ourselves that we talked about getting rid of\n>    string-list used as look-up tables by replacing them with hashmap\n>    but haven't seen much effort expended on it.  I think this is my\n>    first semi-serious use of hashmap, and the code is expected to be\n>    full of newbie mistakes, inefficiencies and ignorance of idioms;\n>    pointing out any of which is much appreciated.\n\nI could not find newbie mistakes, but gave my thoughts anyway.\n\nStefan\n"},{"id":"359029","messageId":"20180927053418.GB14178@sigill.intra.peff.net","threadId":"49433","inReplyTo":"xmqqin2sj6df.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-27T05:34:19Z","receivedAt":"2018-09-27T05:34:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 26, 2018 at 02:28:28PM -0700, Junio C Hamano wrote:\n\n> In find_non_local_tags() helper function (used to implement the\n> \"follow tags\"), we use string_list_has_string() on two string lists\n> as a way to see if a refname has already been processed, etc.\n> \n> All this code predates more modern in-core lookup API like hashmap;\n> replace them with two hashmaps and one string list---the hashmaps\n> are used for look-ups and the string list is to keep the order of\n> items in the returned result stable (which is the only single thing\n> hashmap does worse than lookups on string-list).\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n> \n>  * Just to remind ourselves that we talked about getting rid of\n>    string-list used as look-up tables by replacing them with hashmap\n>    but haven't seen much effort expended on it.  I think this is my\n>    first semi-serious use of hashmap, and the code is expected to be\n>    full of newbie mistakes, inefficiencies and ignorance of idioms;\n>    pointing out any of which is much appreciated.\n\nAs you probably noticed, there's a bit of boilerplate required to use a\nhashmap. I had figured we could replace most of these with a single\n\"strmap\" API to map a string to a void pointer (which is basically\nwhat string-list gives you).\n\nThat would save on the boilerplate. But your solution here replaces a\n\"void *\" pointer with an actual \"struct object_id\" member, which\nimproves type-safety. It also removes questions about memory lifetimes\n(at the minor cost of copying the oids). So this path is probably better\nif we don't mind a little extra code.\n\nI do note that your struct just has the same information as \"struct\nref\":\n\n> +struct refname_hash_entry {\n> +\tstruct hashmap_entry ent; /* must be the first member */\n> +\tstruct object_id oid;\n> +\tchar refname[FLEX_ARRAY];\n> +};\n\nSo yet another alternative here is to just define a single hashmap that\nstores void pointers. That also throws away some type safety, but is\nmaybe conceptually simpler. I dunno. It's actually a pain to do that\nwith \"struct hashmap\" because it requires the caller to handle\nallocation. An open-addressed hash table, as we use elsewhere (and in\nkhash.h) is a bit simpler, since it doesn't need to do any per-entry\nmalloc.\n\nTo be clear, I'm perfectly happy with the approach in your patch here.\nI'm just musing on what might might be the least painful thing for doing\nmore of them.\n\n-Peff\n"},{"id":"359031","messageId":"20180927055415.GC14178@sigill.intra.peff.net","threadId":"49433","inReplyTo":"CAGZ79kamkLV7yHtCu_qSqNzj7bJm0=Uw1CKxss+zTKJWsYz3qw@mail.gmail.com","subject":"Re: [PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-27T05:54:15Z","receivedAt":"2018-09-27T05:54:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 26, 2018 at 03:59:08PM -0700, Stefan Beller wrote:\n\n> > +struct refname_hash_entry {\n> > +       struct hashmap_entry ent; /* must be the first member */\n> \n> $ git grep \"struct hashmap_entry\" reveals that we have another\n> convention that we follow but not document, which is to stress\n> the importance of putting the hashmap_entry first. ;-)\n\nOne thing I've liked about the list.h implementation is that you can\nstore the list pointer anywhere in the struct, or even have the same\nstruct in multiple lists.\n\nThe only funny thing is that you have to \"dereference\" the iterator like\nthis:\n\n  struct list_head *pos;\n  struct actual_thing *item;\n  ...\n  item = list_entry(pos, struct actual_thing, list_member);\n\nwhich is a minor pain, but it's reasonably hard to get it wrong.\n\nI wonder if we could do the same here. The hashmap would only ever see\nthe \"struct hashmap_entry\", and then the caller would convert that back\nto the actual type. I think we could even get away with not converting\nexisting callers; if the hashmap _is_ at the front, then that\nlist_entry() really just devolves to a cast. So as long as the struct\ndefinition and the users of the struct agree, it would just work.\n\n> > +static int refname_hash_entry_cmp(const void *hashmap_cmp_fn_data,\n> > +                                 const struct refname_hash_entry *e1,\n> > +                                 const struct refname_hash_entry *e2,\n> > +                                 const void *keydata)\n> > +{\n> > +       return strcmp(e1->refname, keydata ? keydata : e2->refname);\n> > +}\n> \n> and later\n> \n>     hashmap_init(...  (hashmap_cmp_fn)refname_hash_entry_cmp, ...);\n> \n> I wonder if we'd want to stick to this style, as that seems to be the easiest\n> to do, and drop the efforts started in 55c965f3a2 (Merge branch\n> 'sb/hashmap-cleanup', 2017-08-11), that avoids the cast in the init,\n> but puts the (implicit) casts in the _cmp function as we'd take\n> void pointers as the function signature and recast to a local variable.\n\nI think that casting the function pointer technically breaks the C\nstandard, though probably not in a way that is a problem on any real\nsystems.\n\nThe other thing about the \"cast inside the cmp function\" approach from\nsb/hashmap-cleanup is that it is less likely to go stale. If we change\nthe definition of hashmap_cmp_fn, then any functions which are manually\ncast will suppress the compiler errors. When the function takes void\npointers, the same can happen if \"struct refname_hash_entry\" is swapped\nout for another struct, but IMHO that's a less likely error to make.\n\nI admit that's just a gut feeling, though. It would be nice if we could\navoid casting altogether, but I think that puts us into macro territory\n(which I'm not altogether opposed to, but it has its own drawbacks).\n\n-Peff\n"},{"id":"359304","messageId":"xmqqva6o88b7.fsf@gitster-ct.c.googlers.com","threadId":"49433","inReplyTo":"20180927055415.GC14178@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-29T18:31:08Z","receivedAt":"2018-09-29T18:31:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Sep 26, 2018 at 03:59:08PM -0700, Stefan Beller wrote:\n>\n>> > +struct refname_hash_entry {\n>> > +       struct hashmap_entry ent; /* must be the first member */\n>> \n>> $ git grep \"struct hashmap_entry\" reveals that we have another\n>> convention that we follow but not document, which is to stress\n>> the importance of putting the hashmap_entry first. ;-)\n>\n> One thing I've liked about the list.h implementation is that you can\n> store the list pointer anywhere in the struct, or even have the same\n> struct in multiple lists.\n>\n> The only funny thing is that you have to \"dereference\" the iterator like\n> this:\n>\n>   struct list_head *pos;\n>   struct actual_thing *item;\n>   ...\n>   item = list_entry(pos, struct actual_thing, list_member);\n>\n> which is a minor pain, but it's reasonably hard to get it wrong.\n>\n> I wonder if we could do the same here. The hashmap would only ever see\n> the \"struct hashmap_entry\", and then the caller would convert that back\n> to the actual type.\n\nHmph, how would hashmap_cmp_fn look like with that scheme?  It would\nget one entry, another entry (or just the skeleton of it) and\noptionally a separate keydata (if the second one is skeleton), and\nthe first two points at the embedded hashmap struct, not the\nsurrounding one.  The callback function is now responsible for\ncalling a hashmap_entry() macro that adjusts for the negative offset\nlike list_entry() does?\n\n> I think we could even get away with not converting\n> existing callers; if the hashmap _is_ at the front, then that\n> list_entry() really just devolves to a cast.\n\nYes.\n\n> So as long as the struct\n> definition and the users of the struct agree, it would just work.\n\nYes, too.\n\nWas it ever a consideration, when allowing struct list-head anywhere\nin the enclosing struct, that it would allow an element to be on\nmore than one list?  Would it benefit us to be able to place an\nelement in multiple hashmaps because we do not have to have the\nembedded hashmap_entry always at the beginning if we did this\nchange?\n"},{"id":"359323","messageId":"xmqq5zyn91ku.fsf@gitster-ct.c.googlers.com","threadId":"49433","inReplyTo":"20180927053418.GB14178@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-30T02:11:13Z","receivedAt":"2018-09-30T02:11:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> So yet another alternative here is to just define a single hashmap that\n> stores void pointers. That also throws away some type safety, but is\n> maybe conceptually simpler. I dunno.\n\nI was tempted to try that route, which would essentially give us \"if\nyou are abusing string-list as a look-up table, and if either you do\nnot need to iterate over all the elements, or you do not care about\nthe order in which such an interation is made, then use this\ninstead\" API that can more easily substitute string-list without\nboilerplate.\n\nBut I am not sure if that is worth it.  Perhaps we may end up doing\nso when we find the second thing to move from string-list to hashmap,\nbut not with this patch (and yes, there is another string-list user\nin the same source file, which I think can reuse what I added with\nthis patch).\n\nIn any case, I expect to be offline more than half of the next week,\nso before I forget, here is an updated patch.  Two changes since the\nversion posted earlier are:\n\n - remote_refs_list (not remote_refs which is a hashmap) is passed\n   to string_list_clear() at the end.  This is a fix for an outright\n   bug Ramsay noticed.\n\n - The callback function now takes (const void *) and casts its\n   parameters to correct type before they are used, instead of\n   casting the pointer to a function whose signature is wrong in the\n   call to hashmap_init().  This was noticed by Stefan and I agree\n   that doing it this way makes more sense.\n\n-- >8 --\nSubject: [PATCH v2] fetch: replace string-list used as a look-up table with a hashmap\n\nIn find_non_local_tags() helper function (used to implement the\n\"follow tags\"), we use string_list_has_string() on two string lists\nas a way to see if a refname has already been processed, etc.\n\nAll this code predates more modern in-core lookup API like hashmap;\nreplace them with two hashmaps and one string list---the hashmaps\nare used for look-ups and the string list is to keep the order of\nitems in the returned result stable (which is the only single thing\nhashmap does worse than lookups on string-list).\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/fetch.c | 121 +++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 94 insertions(+), 27 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 0696abfc2a..489531ec93 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -246,16 +246,76 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)\n \treturn 0;\n }\n \n+struct refname_hash_entry {\n+\tstruct hashmap_entry ent; /* must be the first member */\n+\tstruct object_id oid;\n+\tchar refname[FLEX_ARRAY];\n+};\n+\n+static int refname_hash_entry_cmp(const void *hashmap_cmp_fn_data,\n+\t\t\t\t  const void *e1_,\n+\t\t\t\t  const void *e2_,\n+\t\t\t\t  const void *keydata)\n+{\n+\tconst struct refname_hash_entry *e1 = e1_;\n+\tconst struct refname_hash_entry *e2 = e2_;\n+\n+\treturn strcmp(e1->refname, keydata ? keydata : e2->refname);\n+}\n+\n+static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n+\t\t\t\t\t\t   const char *refname,\n+\t\t\t\t\t\t   const struct object_id *oid)\n+{\n+\tstruct refname_hash_entry *ent;\n+\tsize_t len = strlen(refname);\n+\n+\tFLEX_ALLOC_MEM(ent, refname, refname, len);\n+\thashmap_entry_init(ent, memhash(refname, len));\n+\toidcpy(&ent->oid, oid);\n+\thashmap_add(map, ent);\n+\treturn ent;\n+}\n+\n+static int add_one_refname(const char *refname,\n+\t\t\t   const struct object_id *oid,\n+\t\t\t   int flag, void *cbdata)\n+{\n+\tstruct hashmap *refname_map = cbdata;\n+\n+\t(void) refname_hash_add(refname_map, refname, oid);\n+\treturn 0;\n+}\n+\n+static void refname_hash_init(struct hashmap *map)\n+{\n+\thashmap_init(map, refname_hash_entry_cmp, NULL, 0);\n+}\n+\n+static int refname_hash_exists(struct hashmap *map, const char *refname)\n+{\n+\tstruct hashmap_entry key;\n+\tsize_t len = strlen(refname);\n+\thashmap_entry_init(&key, memhash(refname, len));\n+\n+\treturn !!hashmap_get(map, &key, refname);\n+}\n+\n static void find_non_local_tags(const struct ref *refs,\n \t\t\t\tstruct ref **head,\n \t\t\t\tstruct ref ***tail)\n {\n-\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n-\tstruct string_list remote_refs = STRING_LIST_INIT_NODUP;\n+\tstruct hashmap existing_refs;\n+\tstruct hashmap remote_refs;\n+\tstruct string_list remote_refs_list = STRING_LIST_INIT_NODUP;\n+\tstruct string_list_item *remote_ref_item;\n \tconst struct ref *ref;\n-\tstruct string_list_item *item = NULL;\n+\tstruct refname_hash_entry *item = NULL;\n \n-\tfor_each_ref(add_existing, &existing_refs);\n+\trefname_hash_init(&existing_refs);\n+\trefname_hash_init(&remote_refs);\n+\n+\tfor_each_ref(add_one_refname, &existing_refs);\n \tfor (ref = refs; ref; ref = ref->next) {\n \t\tif (!starts_with(ref->name, \"refs/tags/\"))\n \t\t\tcontinue;\n@@ -271,10 +331,10 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n \t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n-\t\t\t    !has_sha1_file_with_flags(item->util,\n+\t\t\t    !has_sha1_file_with_flags(item->oid.hash,\n \t\t\t\t\t\t      OBJECT_INFO_QUICK) &&\n-\t\t\t    !will_fetch(head, item->util))\n-\t\t\t\titem->util = NULL;\n+\t\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\t\toidclr(&item->oid);\n \t\t\titem = NULL;\n \t\t\tcontinue;\n \t\t}\n@@ -286,48 +346,55 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t * fetch.\n \t\t */\n \t\tif (item &&\n-\t\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n-\t\t    !will_fetch(head, item->util))\n-\t\t\titem->util = NULL;\n+\t\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n+\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\toidclr(&item->oid);\n \n \t\titem = NULL;\n \n \t\t/* skip duplicates and refs that we already have */\n-\t\tif (string_list_has_string(&remote_refs, ref->name) ||\n-\t\t    string_list_has_string(&existing_refs, ref->name))\n+\t\tif (refname_hash_exists(&remote_refs, ref->name) ||\n+\t\t    refname_hash_exists(&existing_refs, ref->name))\n \t\t\tcontinue;\n \n-\t\titem = string_list_insert(&remote_refs, ref->name);\n-\t\titem->util = (void *)&ref->old_oid;\n+\t\titem = refname_hash_add(&remote_refs, ref->name, &ref->old_oid);\n+\t\tstring_list_insert(&remote_refs_list, ref->name);\n \t}\n-\tstring_list_clear(&existing_refs, 1);\n+\thashmap_free(&existing_refs, 1);\n \n \t/*\n \t * We may have a final lightweight tag that needs to be\n \t * checked to see if it needs fetching.\n \t */\n \tif (item &&\n-\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n-\t    !will_fetch(head, item->util))\n-\t\titem->util = NULL;\n+\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n+\t    !will_fetch(head, item->oid.hash))\n+\t\toidclr(&item->oid);\n \n \t/*\n-\t * For all the tags in the remote_refs string list,\n+\t * For all the tags in the remote_refs_list,\n \t * add them to the list of refs to be fetched\n \t */\n-\tfor_each_string_list_item(item, &remote_refs) {\n+\tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n+\t\tconst char *refname = remote_ref_item->string;\n+\t\tstruct hashmap_entry key;\n+\n+\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n+\t\titem = hashmap_get(&remote_refs, &key, refname);\n+\t\tif (!item)\n+\t\t\tcontinue; /* can this happen??? */\n+\n \t\t/* Unless we have already decided to ignore this item... */\n-\t\tif (item->util)\n-\t\t{\n-\t\t\tstruct ref *rm = alloc_ref(item->string);\n-\t\t\trm->peer_ref = alloc_ref(item->string);\n-\t\t\toidcpy(&rm->old_oid, item->util);\n+\t\tif (!is_null_oid(&item->oid)) {\n+\t\t\tstruct ref *rm = alloc_ref(item->refname);\n+\t\t\trm->peer_ref = alloc_ref(item->refname);\n+\t\t\toidcpy(&rm->old_oid, &item->oid);\n \t\t\t**tail = rm;\n \t\t\t*tail = &rm->next;\n \t\t}\n \t}\n-\n-\tstring_list_clear(&remote_refs, 0);\n+\thashmap_free(&remote_refs, 1);\n+\tstring_list_clear(&remote_refs_list, 0);\n }\n \n static struct ref *get_ref_map(struct remote *remote,\n-- \n2.19.0-271-gfe8321ec05\n\n\n"},{"id":"359329","messageId":"20180930045713.GB32120@sigill.intra.peff.net","threadId":"49433","inReplyTo":"xmqqva6o88b7.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-30T04:57:13Z","receivedAt":"2018-09-30T04:57:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Sep 29, 2018 at 11:31:08AM -0700, Junio C Hamano wrote:\n\n> > The only funny thing is that you have to \"dereference\" the iterator like\n> > this:\n> >\n> >   struct list_head *pos;\n> >   struct actual_thing *item;\n> >   ...\n> >   item = list_entry(pos, struct actual_thing, list_member);\n> >\n> > which is a minor pain, but it's reasonably hard to get it wrong.\n> >\n> > I wonder if we could do the same here. The hashmap would only ever see\n> > the \"struct hashmap_entry\", and then the caller would convert that back\n> > to the actual type.\n> \n> Hmph, how would hashmap_cmp_fn look like with that scheme?  It would\n> get one entry, another entry (or just the skeleton of it) and\n> optionally a separate keydata (if the second one is skeleton), and\n> the first two points at the embedded hashmap struct, not the\n> surrounding one.  The callback function is now responsible for\n> calling a hashmap_entry() macro that adjusts for the negative offset\n> like list_entry() does?\n\nExactly. The comparison functions currently look something like this:\n\n  int foo_hash_cmp(const void *data,\n\t\t   const void *e1, const void *e2,\n\t\t   const void *keydata)\n  {\n\tconst struct foo *f1 = (const struct foo *)e1;\n\tconst struct foo *f2 = (const struct foo *)e2;\n\treturn strcmp(foo->field, keydata ? keydata : foo->field);\n  }\n\n(this is using the correct function signature; you can drop the casts if\nyou violate that, but IMHO this style is more maintainable in the long\nrun). With the hashmap_entry at an arbitrary position, the body is:\n\n  const struct foo *f1 = hash_entry(e1, struct foo, hash_field);\n  const struct foo *f2 = hash_entry(e2, struct foo, hash_field);\n  return strcmp(foo->field, keydata ? keydata : foo->field);\n\nwhere hash_field is the member of \"struct foo\" that holds the \"struct\nhashmap_entry\". So that's not so different, but there is an interesting\nimplication here. The comparison callback has to know which\nhashmap_entry name to use! So if you have a struct that can be in two\nhashes, like:\n\n  struct foo {\n    char *name;\n    struct hashmap_entry h1;\n    struct hashmap_entry h2;\n  };\n\nthen you cannot use a single foo_hash_cmp() function. You have to use a\ndifferent one for each field. Which seems kind of nasty and error-prone.\n\nSo I dunno. Maybe this is not a good direction. I have to admit that I'm\nnot wild about our hashmap implementation in general:\n\n  - the way it handles allocations is often awkward, or causes you to\n    write confusing boilerplate\n\n  - it's not type-safe\n\n  - it seems slower than open-addressed alternatives (e.g., over in [1]\n    we determined that oidset can be made almost twice as fast using\n    khash)\n\n  - the chained implementation in hashmap.c is probably better for cases\n    where there's a lot of deletions, because removing from the hashmap\n    truly removes everything (whereas with open-addressed schemes, we\n    either didn't implement deletion at all, or it sets a marker which\n    allows the item to be dropped next time the hash is resized)\n\n[1] https://public-inbox.org/git/20180814015842.GA27055@sigill.intra.peff.net/\n\n> Was it ever a consideration, when allowing struct list-head anywhere\n> in the enclosing struct, that it would allow an element to be on\n> more than one list?\n\nI don't know the history of that list code in that kernel, but I always\nassumed that was one of the goals. We don't use it yet, but there are\nplaces where we could (e.g., packed_git is part of the regular packed\nlist, as well as the mru; the former is implemented as a singly-linked\nlist, but that's mostly historical).\n\nIt also allows us to have an item in a list and a hashmap (since if they\nboth needed to be at the start of the struct, that wouldn't work). We do\nuse that ability for delta_base_cache_entry.\n\n> Would it benefit us to be able to place an\n> element in multiple hashmaps because we do not have to have the\n> embedded hashmap_entry always at the beginning if we did this\n> change?\n\nI'm not sure. I think it would allow us to more aggressively stick the\nhashmap_entry inside existing structs. For instance, in the patch from\nthis thread, could we actually shove the hashmap_entry structs into\n\"struct ref\", and save having to allocate the extra refname_hash struct?\n\nI guess that pollutes \"struct ref\", though. Unless we generically say\n\"it can be a part of up to 3 hashes\" and provide struct hashmap_entry\nh1, struct hashmap_entry h2, etc. And then your new code does:\n\n  struct hashmap existing_refs;\n  struct hashmap remote_refs;\n\n  /*\n   * These need to be different compare functions to access the\n   * h1 and h2 fields in \"struct ref\"!\n   */\n  hashmap_init(&existing_refs, ref_hash_cmp_h1);\n  hashmap_init(&remote_refs, ref_hash_cmp_h2);\n\n  ...\n\n  hashmap_add(&existing_refs, &some_ref->h1);\n\nBut that seems pretty error-prone (not just confusing h1 and h2 here,\nbut how do we know that some other part of the code isn't using \"h1\" for\nits own hash already?)\n\nSo again, maybe this is just a bad direction.\n\nAt least with an open-addressed scheme, the hash table itself contains\neverything, and you can just store pointers to the existing refs.\n\n-Peff\n"},{"id":"360898","messageId":"xmqqy3au1tr1.fsf_-_@gitster-ct.c.googlers.com","threadId":"49433","inReplyTo":"xmqq5zyn91ku.fsf@gitster-ct.c.googlers.com","subject":"[PATCH v3] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-19T03:48:50Z","receivedAt":"2018-10-19T03:49:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In find_non_local_tags() helper function (used to implement the\n\"follow tags\"), we use string_list_has_string() on two string lists\nas a way to see if a refname has already been processed, etc.\n\nAll this code predates more modern in-core lookup API like hashmap;\nreplace them with two hashmaps and one string list---the hashmaps\nare used for look-ups and the string list is to keep the order of\nitems in the returned result stable (which is the only single thing\nhashmap does worse than lookups on string-list).\n\nSimilarly, get_ref_map() uses another string-list as a look-up table\nfor existing refs.  Replace it with a hashmap.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * This converts another string-list user in the same file.  For now\n   I am done with this topic; I'm willing to fix bugs in this patch,\n   but do not intend to spend time killing more string-lists used as\n   look-up tables.\n\n builtin/fetch.c | 152 +++++++++++++++++++++++++++++++++---------------\n 1 file changed, 106 insertions(+), 46 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 0696abfc2a..0f8e333022 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -223,18 +223,6 @@ static void add_merge_config(struct ref **head,\n \t}\n }\n \n-static int add_existing(const char *refname, const struct object_id *oid,\n-\t\t\tint flag, void *cbdata)\n-{\n-\tstruct string_list *list = (struct string_list *)cbdata;\n-\tstruct string_list_item *item = string_list_insert(list, refname);\n-\tstruct object_id *old_oid = xmalloc(sizeof(*old_oid));\n-\n-\toidcpy(old_oid, oid);\n-\titem->util = old_oid;\n-\treturn 0;\n-}\n-\n static int will_fetch(struct ref **head, const unsigned char *sha1)\n {\n \tstruct ref *rm = *head;\n@@ -246,16 +234,76 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)\n \treturn 0;\n }\n \n+struct refname_hash_entry {\n+\tstruct hashmap_entry ent; /* must be the first member */\n+\tstruct object_id oid;\n+\tchar refname[FLEX_ARRAY];\n+};\n+\n+static int refname_hash_entry_cmp(const void *hashmap_cmp_fn_data,\n+\t\t\t\t  const void *e1_,\n+\t\t\t\t  const void *e2_,\n+\t\t\t\t  const void *keydata)\n+{\n+\tconst struct refname_hash_entry *e1 = e1_;\n+\tconst struct refname_hash_entry *e2 = e2_;\n+\n+\treturn strcmp(e1->refname, keydata ? keydata : e2->refname);\n+}\n+\n+static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n+\t\t\t\t\t\t   const char *refname,\n+\t\t\t\t\t\t   const struct object_id *oid)\n+{\n+\tstruct refname_hash_entry *ent;\n+\tsize_t len = strlen(refname);\n+\n+\tFLEX_ALLOC_MEM(ent, refname, refname, len);\n+\thashmap_entry_init(ent, memhash(refname, len));\n+\toidcpy(&ent->oid, oid);\n+\thashmap_add(map, ent);\n+\treturn ent;\n+}\n+\n+static int add_one_refname(const char *refname,\n+\t\t\t   const struct object_id *oid,\n+\t\t\t   int flag, void *cbdata)\n+{\n+\tstruct hashmap *refname_map = cbdata;\n+\n+\t(void) refname_hash_add(refname_map, refname, oid);\n+\treturn 0;\n+}\n+\n+static void refname_hash_init(struct hashmap *map)\n+{\n+\thashmap_init(map, refname_hash_entry_cmp, NULL, 0);\n+}\n+\n+static int refname_hash_exists(struct hashmap *map, const char *refname)\n+{\n+\tstruct hashmap_entry key;\n+\tsize_t len = strlen(refname);\n+\thashmap_entry_init(&key, memhash(refname, len));\n+\n+\treturn !!hashmap_get(map, &key, refname);\n+}\n+\n static void find_non_local_tags(const struct ref *refs,\n \t\t\t\tstruct ref **head,\n \t\t\t\tstruct ref ***tail)\n {\n-\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n-\tstruct string_list remote_refs = STRING_LIST_INIT_NODUP;\n+\tstruct hashmap existing_refs;\n+\tstruct hashmap remote_refs;\n+\tstruct string_list remote_refs_list = STRING_LIST_INIT_NODUP;\n+\tstruct string_list_item *remote_ref_item;\n \tconst struct ref *ref;\n-\tstruct string_list_item *item = NULL;\n+\tstruct refname_hash_entry *item = NULL;\n \n-\tfor_each_ref(add_existing, &existing_refs);\n+\trefname_hash_init(&existing_refs);\n+\trefname_hash_init(&remote_refs);\n+\n+\tfor_each_ref(add_one_refname, &existing_refs);\n \tfor (ref = refs; ref; ref = ref->next) {\n \t\tif (!starts_with(ref->name, \"refs/tags/\"))\n \t\t\tcontinue;\n@@ -271,10 +319,10 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n \t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n-\t\t\t    !has_sha1_file_with_flags(item->util,\n+\t\t\t    !has_sha1_file_with_flags(item->oid.hash,\n \t\t\t\t\t\t      OBJECT_INFO_QUICK) &&\n-\t\t\t    !will_fetch(head, item->util))\n-\t\t\t\titem->util = NULL;\n+\t\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\t\toidclr(&item->oid);\n \t\t\titem = NULL;\n \t\t\tcontinue;\n \t\t}\n@@ -286,48 +334,55 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t * fetch.\n \t\t */\n \t\tif (item &&\n-\t\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n-\t\t    !will_fetch(head, item->util))\n-\t\t\titem->util = NULL;\n+\t\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n+\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\toidclr(&item->oid);\n \n \t\titem = NULL;\n \n \t\t/* skip duplicates and refs that we already have */\n-\t\tif (string_list_has_string(&remote_refs, ref->name) ||\n-\t\t    string_list_has_string(&existing_refs, ref->name))\n+\t\tif (refname_hash_exists(&remote_refs, ref->name) ||\n+\t\t    refname_hash_exists(&existing_refs, ref->name))\n \t\t\tcontinue;\n \n-\t\titem = string_list_insert(&remote_refs, ref->name);\n-\t\titem->util = (void *)&ref->old_oid;\n+\t\titem = refname_hash_add(&remote_refs, ref->name, &ref->old_oid);\n+\t\tstring_list_insert(&remote_refs_list, ref->name);\n \t}\n-\tstring_list_clear(&existing_refs, 1);\n+\thashmap_free(&existing_refs, 1);\n \n \t/*\n \t * We may have a final lightweight tag that needs to be\n \t * checked to see if it needs fetching.\n \t */\n \tif (item &&\n-\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n-\t    !will_fetch(head, item->util))\n-\t\titem->util = NULL;\n+\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n+\t    !will_fetch(head, item->oid.hash))\n+\t\toidclr(&item->oid);\n \n \t/*\n-\t * For all the tags in the remote_refs string list,\n+\t * For all the tags in the remote_refs_list,\n \t * add them to the list of refs to be fetched\n \t */\n-\tfor_each_string_list_item(item, &remote_refs) {\n+\tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n+\t\tconst char *refname = remote_ref_item->string;\n+\t\tstruct hashmap_entry key;\n+\n+\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n+\t\titem = hashmap_get(&remote_refs, &key, refname);\n+\t\tif (!item)\n+\t\t\tcontinue; /* can this happen??? */\n+\n \t\t/* Unless we have already decided to ignore this item... */\n-\t\tif (item->util)\n-\t\t{\n-\t\t\tstruct ref *rm = alloc_ref(item->string);\n-\t\t\trm->peer_ref = alloc_ref(item->string);\n-\t\t\toidcpy(&rm->old_oid, item->util);\n+\t\tif (!is_null_oid(&item->oid)) {\n+\t\t\tstruct ref *rm = alloc_ref(item->refname);\n+\t\t\trm->peer_ref = alloc_ref(item->refname);\n+\t\t\toidcpy(&rm->old_oid, &item->oid);\n \t\t\t**tail = rm;\n \t\t\t*tail = &rm->next;\n \t\t}\n \t}\n-\n-\tstring_list_clear(&remote_refs, 0);\n+\thashmap_free(&remote_refs, 1);\n+\tstring_list_clear(&remote_refs_list, 0);\n }\n \n static struct ref *get_ref_map(struct remote *remote,\n@@ -343,7 +398,7 @@ static struct ref *get_ref_map(struct remote *remote,\n \t/* opportunistically-updated references: */\n \tstruct ref *orefs = NULL, **oref_tail = &orefs;\n \n-\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n+\tstruct hashmap existing_refs;\n \n \tif (rs->nr) {\n \t\tstruct refspec *fetch_refspec;\n@@ -437,19 +492,24 @@ static struct ref *get_ref_map(struct remote *remote,\n \n \tref_map = ref_remove_duplicates(ref_map);\n \n-\tfor_each_ref(add_existing, &existing_refs);\n+\trefname_hash_init(&existing_refs);\n+\tfor_each_ref(add_one_refname, &existing_refs);\n+\n \tfor (rm = ref_map; rm; rm = rm->next) {\n \t\tif (rm->peer_ref) {\n-\t\t\tstruct string_list_item *peer_item =\n-\t\t\t\tstring_list_lookup(&existing_refs,\n-\t\t\t\t\t\t   rm->peer_ref->name);\n+\t\t\tstruct hashmap_entry key;\n+\t\t\tconst char *refname = rm->peer_ref->name;\n+\t\t\tstruct refname_hash_entry *peer_item;\n+\n+\t\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n+\t\t\tpeer_item = hashmap_get(&existing_refs, &key, refname);\n \t\t\tif (peer_item) {\n-\t\t\t\tstruct object_id *old_oid = peer_item->util;\n+\t\t\t\tstruct object_id *old_oid = &peer_item->oid;\n \t\t\t\toidcpy(&rm->peer_ref->old_oid, old_oid);\n \t\t\t}\n \t\t}\n \t}\n-\tstring_list_clear(&existing_refs, 1);\n+\thashmap_free(&existing_refs, 1);\n \n \treturn ref_map;\n }\n-- \n2.19.1-450-ga4b8ab5363\n\n"},{"id":"361150","messageId":"nycvar.QRO.7.76.6.1810221140510.4546@tvgsbejvaqbjf.bet","threadId":"49433","inReplyTo":"xmqqy3au1tr1.fsf_-_@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-10-22T09:57:46Z","receivedAt":"2018-10-22T09:58:00Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Fri, 19 Oct 2018, Junio C Hamano wrote:\n\n> In find_non_local_tags() helper function (used to implement the\n> \"follow tags\"), we use string_list_has_string() on two string lists\n> as a way to see if a refname has already been processed, etc.\n> \n> All this code predates more modern in-core lookup API like hashmap;\n> replace them with two hashmaps and one string list---the hashmaps\n> are used for look-ups and the string list is to keep the order of\n> items in the returned result stable (which is the only single thing\n> hashmap does worse than lookups on string-list).\n\nThis sounds as if you would need a linked hash map, i.e. a hash map whose\niterator remembers the order in which items were inserted.\n\nI am fine, however, with your patch as a first step in that direction, and\nonly implementing a linked hash map when we realize that we need it\nsomewhere else, too.\n\nJust one thing^W^Wa couple of things:\n\n> Similarly, get_ref_map() uses another string-list as a look-up table\n> for existing refs.  Replace it with a hashmap.\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n> \n>  * This converts another string-list user in the same file.  For now\n>    I am done with this topic; I'm willing to fix bugs in this patch,\n>    but do not intend to spend time killing more string-lists used as\n>    look-up tables.\n> \n>  builtin/fetch.c | 152 +++++++++++++++++++++++++++++++++---------------\n>  1 file changed, 106 insertions(+), 46 deletions(-)\n> \n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 0696abfc2a..0f8e333022 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -223,18 +223,6 @@ static void add_merge_config(struct ref **head,\n>  \t}\n>  }\n>  \n> -static int add_existing(const char *refname, const struct object_id *oid,\n> -\t\t\tint flag, void *cbdata)\n> -{\n> -\tstruct string_list *list = (struct string_list *)cbdata;\n> -\tstruct string_list_item *item = string_list_insert(list, refname);\n> -\tstruct object_id *old_oid = xmalloc(sizeof(*old_oid));\n> -\n> -\toidcpy(old_oid, oid);\n> -\titem->util = old_oid;\n> -\treturn 0;\n> -}\n> -\n>  static int will_fetch(struct ref **head, const unsigned char *sha1)\n>  {\n>  \tstruct ref *rm = *head;\n> @@ -246,16 +234,76 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)\n>  \treturn 0;\n>  }\n>  \n> +struct refname_hash_entry {\n> +\tstruct hashmap_entry ent; /* must be the first member */\n> +\tstruct object_id oid;\n> +\tchar refname[FLEX_ARRAY];\n> +};\n> +\n> +static int refname_hash_entry_cmp(const void *hashmap_cmp_fn_data,\n> +\t\t\t\t  const void *e1_,\n> +\t\t\t\t  const void *e2_,\n> +\t\t\t\t  const void *keydata)\n> +{\n> +\tconst struct refname_hash_entry *e1 = e1_;\n> +\tconst struct refname_hash_entry *e2 = e2_;\n> +\n> +\treturn strcmp(e1->refname, keydata ? keydata : e2->refname);\n> +}\n> +\n> +static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n> +\t\t\t\t\t\t   const char *refname,\n> +\t\t\t\t\t\t   const struct object_id *oid)\n> +{\n> +\tstruct refname_hash_entry *ent;\n> +\tsize_t len = strlen(refname);\n> +\n> +\tFLEX_ALLOC_MEM(ent, refname, refname, len);\n> +\thashmap_entry_init(ent, memhash(refname, len));\n> +\toidcpy(&ent->oid, oid);\n> +\thashmap_add(map, ent);\n> +\treturn ent;\n> +}\n> +\n> +static int add_one_refname(const char *refname,\n> +\t\t\t   const struct object_id *oid,\n> +\t\t\t   int flag, void *cbdata)\n> +{\n> +\tstruct hashmap *refname_map = cbdata;\n> +\n> +\t(void) refname_hash_add(refname_map, refname, oid);\n> +\treturn 0;\n> +}\n> +\n> +static void refname_hash_init(struct hashmap *map)\n> +{\n> +\thashmap_init(map, refname_hash_entry_cmp, NULL, 0);\n> +}\n> +\n> +static int refname_hash_exists(struct hashmap *map, const char *refname)\n> +{\n> +\tstruct hashmap_entry key;\n> +\tsize_t len = strlen(refname);\n> +\thashmap_entry_init(&key, memhash(refname, len));\n> +\n> +\treturn !!hashmap_get(map, &key, refname);\n\nIt would probably make more sense to `hashmap_get_from_hash()` and\n`strhash()` here (and `strhash()` should probably be used everywhere\ninstead of `memhash(str, strlen(str))`).\n\n> +}\n> +\n>  static void find_non_local_tags(const struct ref *refs,\n>  \t\t\t\tstruct ref **head,\n>  \t\t\t\tstruct ref ***tail)\n>  {\n> -\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n> -\tstruct string_list remote_refs = STRING_LIST_INIT_NODUP;\n> +\tstruct hashmap existing_refs;\n> +\tstruct hashmap remote_refs;\n> +\tstruct string_list remote_refs_list = STRING_LIST_INIT_NODUP;\n> +\tstruct string_list_item *remote_ref_item;\n>  \tconst struct ref *ref;\n> -\tstruct string_list_item *item = NULL;\n> +\tstruct refname_hash_entry *item = NULL;\n>  \n> -\tfor_each_ref(add_existing, &existing_refs);\n> +\trefname_hash_init(&existing_refs);\n> +\trefname_hash_init(&remote_refs);\n> +\n> +\tfor_each_ref(add_one_refname, &existing_refs);\n>  \tfor (ref = refs; ref; ref = ref->next) {\n>  \t\tif (!starts_with(ref->name, \"refs/tags/\"))\n>  \t\t\tcontinue;\n> @@ -271,10 +319,10 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n>  \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n>  \t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n> -\t\t\t    !has_sha1_file_with_flags(item->util,\n> +\t\t\t    !has_sha1_file_with_flags(item->oid.hash,\n\nI am not sure that we need to test for null OIDs here, given that...\n\n>  \t\t\t\t\t\t      OBJECT_INFO_QUICK) &&\n> -\t\t\t    !will_fetch(head, item->util))\n> -\t\t\t\titem->util = NULL;\n> +\t\t\t    !will_fetch(head, item->oid.hash))\n> +\t\t\t\toidclr(&item->oid);\n\nwe no longer can set `util` to `NULL`, but have to use a null OID to\nindicate that condition now.\n\nOf course, `has_sha1_file_with_flags()` is supposed to return `false` for\nnull OIDs, I guess.\n\n>  \t\t\titem = NULL;\n>  \t\t\tcontinue;\n>  \t\t}\n> @@ -286,48 +334,55 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t\t * fetch.\n>  \t\t */\n>  \t\tif (item &&\n> -\t\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n> -\t\t    !will_fetch(head, item->util))\n> -\t\t\titem->util = NULL;\n> +\t\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n> +\t\t    !will_fetch(head, item->oid.hash))\n> +\t\t\toidclr(&item->oid);\n>  \n>  \t\titem = NULL;\n>  \n>  \t\t/* skip duplicates and refs that we already have */\n> -\t\tif (string_list_has_string(&remote_refs, ref->name) ||\n> -\t\t    string_list_has_string(&existing_refs, ref->name))\n> +\t\tif (refname_hash_exists(&remote_refs, ref->name) ||\n> +\t\t    refname_hash_exists(&existing_refs, ref->name))\n>  \t\t\tcontinue;\n>  \n> -\t\titem = string_list_insert(&remote_refs, ref->name);\n> -\t\titem->util = (void *)&ref->old_oid;\n> +\t\titem = refname_hash_add(&remote_refs, ref->name, &ref->old_oid);\n> +\t\tstring_list_insert(&remote_refs_list, ref->name);\n>  \t}\n> -\tstring_list_clear(&existing_refs, 1);\n> +\thashmap_free(&existing_refs, 1);\n>  \n>  \t/*\n>  \t * We may have a final lightweight tag that needs to be\n>  \t * checked to see if it needs fetching.\n>  \t */\n>  \tif (item &&\n> -\t    !has_sha1_file_with_flags(item->util, OBJECT_INFO_QUICK) &&\n> -\t    !will_fetch(head, item->util))\n> -\t\titem->util = NULL;\n> +\t    !has_sha1_file_with_flags(item->oid.hash, OBJECT_INFO_QUICK) &&\n> +\t    !will_fetch(head, item->oid.hash))\n> +\t\toidclr(&item->oid);\n>  \n>  \t/*\n> -\t * For all the tags in the remote_refs string list,\n> +\t * For all the tags in the remote_refs_list,\n>  \t * add them to the list of refs to be fetched\n>  \t */\n> -\tfor_each_string_list_item(item, &remote_refs) {\n> +\tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n> +\t\tconst char *refname = remote_ref_item->string;\n> +\t\tstruct hashmap_entry key;\n> +\n> +\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n> +\t\titem = hashmap_get(&remote_refs, &key, refname);\n> +\t\tif (!item)\n> +\t\t\tcontinue; /* can this happen??? */\n\nThis would indicate a BUG, no?\n\nThank you for working on this,\nDscho\n\n> +\n>  \t\t/* Unless we have already decided to ignore this item... */\n> -\t\tif (item->util)\n> -\t\t{\n> -\t\t\tstruct ref *rm = alloc_ref(item->string);\n> -\t\t\trm->peer_ref = alloc_ref(item->string);\n> -\t\t\toidcpy(&rm->old_oid, item->util);\n> +\t\tif (!is_null_oid(&item->oid)) {\n> +\t\t\tstruct ref *rm = alloc_ref(item->refname);\n> +\t\t\trm->peer_ref = alloc_ref(item->refname);\n> +\t\t\toidcpy(&rm->old_oid, &item->oid);\n>  \t\t\t**tail = rm;\n>  \t\t\t*tail = &rm->next;\n>  \t\t}\n>  \t}\n> -\n> -\tstring_list_clear(&remote_refs, 0);\n> +\thashmap_free(&remote_refs, 1);\n> +\tstring_list_clear(&remote_refs_list, 0);\n>  }\n>  \n>  static struct ref *get_ref_map(struct remote *remote,\n> @@ -343,7 +398,7 @@ static struct ref *get_ref_map(struct remote *remote,\n>  \t/* opportunistically-updated references: */\n>  \tstruct ref *orefs = NULL, **oref_tail = &orefs;\n>  \n> -\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n> +\tstruct hashmap existing_refs;\n>  \n>  \tif (rs->nr) {\n>  \t\tstruct refspec *fetch_refspec;\n> @@ -437,19 +492,24 @@ static struct ref *get_ref_map(struct remote *remote,\n>  \n>  \tref_map = ref_remove_duplicates(ref_map);\n>  \n> -\tfor_each_ref(add_existing, &existing_refs);\n> +\trefname_hash_init(&existing_refs);\n> +\tfor_each_ref(add_one_refname, &existing_refs);\n> +\n>  \tfor (rm = ref_map; rm; rm = rm->next) {\n>  \t\tif (rm->peer_ref) {\n> -\t\t\tstruct string_list_item *peer_item =\n> -\t\t\t\tstring_list_lookup(&existing_refs,\n> -\t\t\t\t\t\t   rm->peer_ref->name);\n> +\t\t\tstruct hashmap_entry key;\n> +\t\t\tconst char *refname = rm->peer_ref->name;\n> +\t\t\tstruct refname_hash_entry *peer_item;\n> +\n> +\t\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n> +\t\t\tpeer_item = hashmap_get(&existing_refs, &key, refname);\n>  \t\t\tif (peer_item) {\n> -\t\t\t\tstruct object_id *old_oid = peer_item->util;\n> +\t\t\t\tstruct object_id *old_oid = &peer_item->oid;\n>  \t\t\t\toidcpy(&rm->peer_ref->old_oid, old_oid);\n>  \t\t\t}\n>  \t\t}\n>  \t}\n> -\tstring_list_clear(&existing_refs, 1);\n> +\thashmap_free(&existing_refs, 1);\n>  \n>  \treturn ref_map;\n>  }\n> -- \n> 2.19.1-450-ga4b8ab5363\n> \n> \n"},{"id":"361747","messageId":"xmqqk1m3c2dz.fsf_-_@gitster-ct.c.googlers.com","threadId":"49433","inReplyTo":"nycvar.QRO.7.76.6.1810221140510.4546@tvgsbejvaqbjf.bet","subject":"Re*: [PATCH v3] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-27T06:47:04Z","receivedAt":"2018-10-27T06:54:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Just one thing^W^Wa couple of things:\n>\n> It would probably make more sense to `hashmap_get_from_hash()` and\n> `strhash()` here (and `strhash()` should probably be used everywhere\n> instead of `memhash(str, strlen(str))`).\n\nhashmap_get_from_hash() certainly is much better suited for simpler\nusage pattern like these callsites, and the ones in sequencer.c.  It\nis a shame that a more complex variant takes the shorter-and-sweeter\nname hashmap_get().\n\nI wish we named the latter hashmap_get_fullblown_feature_rich() and\ncalled the _from_hash() thing a simple hashmap_get() from day one,\nbut it is way too late.\n\nI looked briefly the users of the _get() variant, and some of their\nuses are legitimately not-simple and cannot be reduced to use the\nsimpler _get_from_hash variant, it seems.  But others like those in\nbuiltin/difftool.c should be straight-forward to convert to use the\nsimpler get_from_hash variant.  It could be a low-hanging fruit left\nfor later clean-up, perhaps.\n\n>> @@ -271,10 +319,10 @@ static void find_non_local_tags(const struct ref *refs,\n>>  \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n>>  \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n>>  \t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n>> -\t\t\t    !has_sha1_file_with_flags(item->util,\n>> +\t\t\t    !has_sha1_file_with_flags(item->oid.hash,\n>\n> I am not sure that we need to test for null OIDs here, given that...\n> ...\n> Of course, `has_sha1_file_with_flags()` is supposed to return `false` for\n> null OIDs, I guess.\n\nYup.  An alternative is to make item->oid a pointer to oid, not an\noid object itself, so that we can express \"no OID for this ref\" in a\nmore explicit way, but is_null_oid() is already used as \"no OID\" in\nmany other codepaths, so...\n\n>> +\tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n>> +\t\tconst char *refname = remote_ref_item->string;\n>> +\t\tstruct hashmap_entry key;\n>> +\n>> +\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n>> +\t\titem = hashmap_get(&remote_refs, &key, refname);\n>> +\t\tif (!item)\n>> +\t\t\tcontinue; /* can this happen??? */\n>\n> This would indicate a BUG, no?\n\nPossibly.  Alternatively, we can just use item without checking and\nlet the runtime segfault.\n\nHere is an incremental on top that can be squashed in to turn v3\ninto v4.\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 0f8e333022..aee1d9bf21 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -259,7 +259,7 @@ static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n \tsize_t len = strlen(refname);\n \n \tFLEX_ALLOC_MEM(ent, refname, refname, len);\n-\thashmap_entry_init(ent, memhash(refname, len));\n+\thashmap_entry_init(ent, strhash(refname));\n \toidcpy(&ent->oid, oid);\n \thashmap_add(map, ent);\n \treturn ent;\n@@ -282,11 +282,7 @@ static void refname_hash_init(struct hashmap *map)\n \n static int refname_hash_exists(struct hashmap *map, const char *refname)\n {\n-\tstruct hashmap_entry key;\n-\tsize_t len = strlen(refname);\n-\thashmap_entry_init(&key, memhash(refname, len));\n-\n-\treturn !!hashmap_get(map, &key, refname);\n+\treturn !!hashmap_get_from_hash(map, strhash(refname), refname);\n }\n \n static void find_non_local_tags(const struct ref *refs,\n@@ -365,12 +361,10 @@ static void find_non_local_tags(const struct ref *refs,\n \t */\n \tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n \t\tconst char *refname = remote_ref_item->string;\n-\t\tstruct hashmap_entry key;\n \n-\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n-\t\titem = hashmap_get(&remote_refs, &key, refname);\n+\t\titem = hashmap_get_from_hash(&remote_refs, strhash(refname), refname);\n \t\tif (!item)\n-\t\t\tcontinue; /* can this happen??? */\n+\t\t\tBUG(\"unseen remote ref?\");\n \n \t\t/* Unless we have already decided to ignore this item... */\n \t\tif (!is_null_oid(&item->oid)) {\n@@ -497,12 +491,12 @@ static struct ref *get_ref_map(struct remote *remote,\n \n \tfor (rm = ref_map; rm; rm = rm->next) {\n \t\tif (rm->peer_ref) {\n-\t\t\tstruct hashmap_entry key;\n \t\t\tconst char *refname = rm->peer_ref->name;\n \t\t\tstruct refname_hash_entry *peer_item;\n \n-\t\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n-\t\t\tpeer_item = hashmap_get(&existing_refs, &key, refname);\n+\t\t\tpeer_item = hashmap_get_from_hash(&existing_refs,\n+\t\t\t\t\t\t\t  strhash(refname),\n+\t\t\t\t\t\t\t  refname);\n \t\t\tif (peer_item) {\n \t\t\t\tstruct object_id *old_oid = &peer_item->oid;\n \t\t\t\toidcpy(&rm->peer_ref->old_oid, old_oid);\n"},{"id":"362110","messageId":"nycvar.QRO.7.76.6.1810311542560.4546@tvgsbejvaqbjf.bet","threadId":"49433","inReplyTo":"xmqqk1m3c2dz.fsf_-_@gitster-ct.c.googlers.com","subject":"Re: Re*: [PATCH v3] fetch: replace string-list used as a look-up table with a hashmap","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-10-31T14:50:00Z","receivedAt":"2018-10-31T14:50:15Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Sat, 27 Oct 2018, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > Just one thing^W^Wa couple of things:\n> >\n> > It would probably make more sense to `hashmap_get_from_hash()` and\n> > `strhash()` here (and `strhash()` should probably be used everywhere\n> > instead of `memhash(str, strlen(str))`).\n> \n> hashmap_get_from_hash() certainly is much better suited for simpler\n> usage pattern like these callsites, and the ones in sequencer.c.  It\n> is a shame that a more complex variant takes the shorter-and-sweeter\n> name hashmap_get().\n\nI agree, at least in part.\n\nFrom what I understand, hashmap_get_from_hash() needs a little assistance\nfrom the comparison function with which the hashmap is configured, see\ne.g. this function in the sequencer:\n\n\tstatic int labels_cmp(const void *fndata, const struct labels_entry *a,\n\t\t\t      const struct labels_entry *b, const void *key)\n\t{\n\t\treturn key ? strcmp(a->label, key) : strcmp(a->label, b->label);\n\t}\n\nSee how that first tests whether `key` is non-`NULL`, and then takes a\nshortcut, not even looking at `b`? This is important, because `b` does not\nrefer to a complete `labels_entry` when we call `hashmap_get_from_hash()`.\nIt only refers to a `hashmap_entry`. Looking at `b->label` would access\nsome random memory, and do most certainly the wrong thing.\n\n> I wish we named the latter hashmap_get_fullblown_feature_rich() and\n> called the _from_hash() thing a simple hashmap_get() from day one,\n> but it is way too late.\n> \n> I looked briefly the users of the _get() variant, and some of their\n> uses are legitimately not-simple and cannot be reduced to use the\n> simpler _get_from_hash variant, it seems.  But others like those in\n> builtin/difftool.c should be straight-forward to convert to use the\n> simpler get_from_hash variant.  It could be a low-hanging fruit left\n> for later clean-up, perhaps.\n\nRight. #leftoverbits\n\n> >> @@ -271,10 +319,10 @@ static void find_non_local_tags(const struct ref *refs,\n> >>  \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n> >>  \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n> >>  \t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n> >> -\t\t\t    !has_sha1_file_with_flags(item->util,\n> >> +\t\t\t    !has_sha1_file_with_flags(item->oid.hash,\n> >\n> > I am not sure that we need to test for null OIDs here, given that...\n> > ...\n> > Of course, `has_sha1_file_with_flags()` is supposed to return `false` for\n> > null OIDs, I guess.\n> \n> Yup.  An alternative is to make item->oid a pointer to oid, not an\n> oid object itself, so that we can express \"no OID for this ref\" in a\n> more explicit way, but is_null_oid() is already used as \"no OID\" in\n> many other codepaths, so...\n\nRight, and it would complicate the code. So I am fine with your version of\nit.\n\n> >> +\tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n> >> +\t\tconst char *refname = remote_ref_item->string;\n> >> +\t\tstruct hashmap_entry key;\n> >> +\n> >> +\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n> >> +\t\titem = hashmap_get(&remote_refs, &key, refname);\n> >> +\t\tif (!item)\n> >> +\t\t\tcontinue; /* can this happen??? */\n> >\n> > This would indicate a BUG, no?\n> \n> Possibly.  Alternatively, we can just use item without checking and\n> let the runtime segfault.\n\nHahaha! Yep. We could also cause a crash. I do prefer the BUG() call.\n\n> Here is an incremental on top that can be squashed in to turn v3\n> into v4.\n\nNice.\n\nThanks!\nDscho\n\n> \n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 0f8e333022..aee1d9bf21 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -259,7 +259,7 @@ static struct refname_hash_entry *refname_hash_add(struct hashmap *map,\n>  \tsize_t len = strlen(refname);\n>  \n>  \tFLEX_ALLOC_MEM(ent, refname, refname, len);\n> -\thashmap_entry_init(ent, memhash(refname, len));\n> +\thashmap_entry_init(ent, strhash(refname));\n>  \toidcpy(&ent->oid, oid);\n>  \thashmap_add(map, ent);\n>  \treturn ent;\n> @@ -282,11 +282,7 @@ static void refname_hash_init(struct hashmap *map)\n>  \n>  static int refname_hash_exists(struct hashmap *map, const char *refname)\n>  {\n> -\tstruct hashmap_entry key;\n> -\tsize_t len = strlen(refname);\n> -\thashmap_entry_init(&key, memhash(refname, len));\n> -\n> -\treturn !!hashmap_get(map, &key, refname);\n> +\treturn !!hashmap_get_from_hash(map, strhash(refname), refname);\n>  }\n>  \n>  static void find_non_local_tags(const struct ref *refs,\n> @@ -365,12 +361,10 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t */\n>  \tfor_each_string_list_item(remote_ref_item, &remote_refs_list) {\n>  \t\tconst char *refname = remote_ref_item->string;\n> -\t\tstruct hashmap_entry key;\n>  \n> -\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n> -\t\titem = hashmap_get(&remote_refs, &key, refname);\n> +\t\titem = hashmap_get_from_hash(&remote_refs, strhash(refname), refname);\n>  \t\tif (!item)\n> -\t\t\tcontinue; /* can this happen??? */\n> +\t\t\tBUG(\"unseen remote ref?\");\n>  \n>  \t\t/* Unless we have already decided to ignore this item... */\n>  \t\tif (!is_null_oid(&item->oid)) {\n> @@ -497,12 +491,12 @@ static struct ref *get_ref_map(struct remote *remote,\n>  \n>  \tfor (rm = ref_map; rm; rm = rm->next) {\n>  \t\tif (rm->peer_ref) {\n> -\t\t\tstruct hashmap_entry key;\n>  \t\t\tconst char *refname = rm->peer_ref->name;\n>  \t\t\tstruct refname_hash_entry *peer_item;\n>  \n> -\t\t\thashmap_entry_init(&key, memhash(refname, strlen(refname)));\n> -\t\t\tpeer_item = hashmap_get(&existing_refs, &key, refname);\n> +\t\t\tpeer_item = hashmap_get_from_hash(&existing_refs,\n> +\t\t\t\t\t\t\t  strhash(refname),\n> +\t\t\t\t\t\t\t  refname);\n>  \t\t\tif (peer_item) {\n>  \t\t\t\tstruct object_id *old_oid = &peer_item->oid;\n>  \t\t\t\toidcpy(&rm->peer_ref->old_oid, old_oid);\n> \n"}]}