{"thread":{"id":"45948","subject":"[PATCH] hashmap: hashmap_get_next passes through keydata as well","startedAt":"2017-05-12T20:02:56Z","lastAt":"2017-05-16T16:13:25Z","messageCount":4,"participants":["Stefan Beller","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"319561","messageId":"20170512200244.25245-1-sbeller@google.com","threadId":"45948","inReplyTo":null,"subject":"[PATCH] hashmap: hashmap_get_next passes through keydata as well","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-05-12T20:02:44Z","receivedAt":"2017-05-12T20:02:56Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"The 'keydata' may be of value in the underlying compare function to decide\nif the given two entries are the same.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/technical/api-hashmap.txt | 6 ++++--\n diffcore-rename.c                       | 2 +-\n hashmap.c                               | 5 +++--\n hashmap.h                               | 3 ++-\n name-hash.c                             | 2 +-\n t/helper/test-hashmap.c                 | 2 +-\n 6 files changed, 12 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex ccc634bbd7..343f1660a9 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -140,11 +140,11 @@ to `hashmap_cmp_fn` to decide whether the entry matches the key.\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+`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+`void *hashmap_get_next(const struct hashmap *map, const void *entry, const void *keydata)`::\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@@ -153,6 +153,8 @@ should not be used in the comparison.\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+`keydata` is passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n \n `void hashmap_add(struct hashmap *map, void *entry)`::\n \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex f7444c86bd..0007fcba23 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -280,7 +280,7 @@ static int find_identical_files(struct hashmap *srcs,\n \t * Find the best source match for specified destination.\n \t */\n \tp = hashmap_get_from_hash(srcs, hash_filespec(target), NULL);\n-\tfor (; p; p = hashmap_get_next(srcs, p)) {\n+\tfor (; p; p = hashmap_get_next(srcs, p, NULL)) {\n \t\tint score;\n \t\tstruct diff_filespec *source = p->filespec;\n \ndiff --git a/hashmap.c b/hashmap.c\nindex 7d1044eb5d..f144d2fc04 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -182,11 +182,12 @@ void *hashmap_get(const struct hashmap *map, const void *key, const void *keydat\n \treturn *find_entry_ptr(map, key, keydata);\n }\n \n-void *hashmap_get_next(const struct hashmap *map, const void *entry)\n+void *hashmap_get_next(const struct hashmap *map, const void *entry,\n+\t\t       const void *keydata)\n {\n \tstruct hashmap_entry *e = ((struct hashmap_entry *) entry)->next;\n \tfor (; e; e = e->next)\n-\t\tif (entry_equals(map, entry, e, NULL))\n+\t\tif (entry_equals(map, entry, e, keydata))\n \t\t\treturn e;\n \treturn NULL;\n }\ndiff --git a/hashmap.h b/hashmap.h\nindex de6022a3a9..536c53a8ab 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -64,7 +64,8 @@ static inline void hashmap_entry_init(void *entry, unsigned int hash)\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_get_next(const struct hashmap *map, const void *entry,\n+\t\t\t      const void *keydata);\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,\ndiff --git a/name-hash.c b/name-hash.c\nindex 39309efb7f..55758ab232 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -703,7 +703,7 @@ struct cache_entry *index_file_exists(struct index_state *istate, const char *na\n \twhile (ce) {\n \t\tif (same_name(ce, name, namelen, icase))\n \t\t\treturn ce;\n-\t\tce = hashmap_get_next(&istate->name_hash, ce);\n+\t\tce = hashmap_get_next(&istate->name_hash, ce, NULL);\n \t}\n \treturn NULL;\n }\ndiff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c\nindex 7aa9440e27..fa33b32317 100644\n--- a/t/helper/test-hashmap.c\n+++ b/t/helper/test-hashmap.c\n@@ -206,7 +206,7 @@ int cmd_main(int argc, const char **argv)\n \t\t\t\tputs(\"NULL\");\n \t\t\twhile (entry) {\n \t\t\t\tputs(get_value(entry));\n-\t\t\t\tentry = hashmap_get_next(&map, entry);\n+\t\t\t\tentry = hashmap_get_next(&map, entry, NULL);\n \t\t\t}\n \n \t\t} else if (!strcmp(\"remove\", cmd) && l1) {\n-- \n2.13.0.18.g183880de0a\n\n"},{"id":"319602","messageId":"20170513085050.plmau5ffvzn6ibfp@sigill.intra.peff.net","threadId":"45948","inReplyTo":"20170512200244.25245-1-sbeller@google.com","subject":"Re: [PATCH] hashmap: hashmap_get_next passes through keydata as well","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-05-13T08:50:50Z","receivedAt":"2017-05-13T08:51:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 12, 2017 at 01:02:44PM -0700, Stefan Beller wrote:\n\n> The 'keydata' may be of value in the underlying compare function to decide\n> if the given two entries are the same.\n\nI had to scratch my head over this for a minute, because there isn't\nreally any motivating example of what you're trying to do.\n\nI think I figured it out, but I have a feeling it is violating the\nintent of the \"keydata\" parameter.  That parameter is typically used not\nas a pointer to arbitrary auxiliary data, but as a trick for finding a\nhash entry without having to allocate a struct for it.\n\nSo generally, I'd think two entries in the table should be able to be\ncompared on their own merits, even if no keydata is available. Without\nthat property, any internal operations in the hashmap can't actually do\nan entry comparison (e.g., a table resize that needs to rehash the\nentries).\n\nIt works out in the current code because the chaining is purely linear,\nand doesn't care about order. So we can rehash and just stick the\nelements into a new list. But if it were switched out for a different\ndata structure (e.g., a tree), then the hashmap code would need to be\nable to compare elements.\n\nI don't think we have any particular plans for such a change, but I\nwonder if we should avoid encouraging callers to rely on the current\nimplementation.\n\n-Peff\n"},{"id":"319617","messageId":"CAGZ79kZxN5-K19R+gd-pZ1Uc30_JRKugjMTJZ4er2dF71pStPg@mail.gmail.com","threadId":"45948","inReplyTo":"20170513085050.plmau5ffvzn6ibfp@sigill.intra.peff.net","subject":"Re: [PATCH] hashmap: hashmap_get_next passes through keydata as well","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-05-13T14:06:35Z","receivedAt":"2017-05-13T14:06:45Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sat, May 13, 2017 at 1:50 AM, Jeff King <peff@peff.net> wrote:\n> On Fri, May 12, 2017 at 01:02:44PM -0700, Stefan Beller wrote:\n>\n>> The 'keydata' may be of value in the underlying compare function to decide\n>> if the given two entries are the same.\n>\n> I had to scratch my head over this for a minute, because there isn't\n> really any motivating example of what you're trying to do.\n>\n> I think I figured it out, but I have a feeling it is violating the\n> intent of the \"keydata\" parameter.  That parameter is typically used not\n> as a pointer to arbitrary auxiliary data, but as a trick for finding a\n> hash entry without having to allocate a struct for it.\n\nYes, I was violating the intent exactly as you describe. I'll adapt my patches\naccordingly.\n\nI do not really buy into the trick though, because when the overhead of\nallocating a 'key' struct filling in the key parts only leaving out the value\nis so much more expensive than giving the key via this keydata argument,\nthen there are serious issues with your data structure IMHO.\nExample:\n\n  struct {\n    struct hashmap_entry ent;\n    int actual key;\n    char value[4096*1024]\n  } key_plus_value;\n\nNow when you want to look up a specific key, you don't want to allocate\nsuch a struct on the stack, as we'd be wasting 4M memory of the stack\ntrashing the caches. However the neat part about this struct is that the\nkey part is (a) totally separate from the values, and (b) comes before\nany value part, such that\n\n  struct {\n    struct hashmap_entry ent;\n    int actual key;\n  } key_only;\n\n  struct key_only = {{NULL, 0}, 42};\n  struct key_plus_value *match = hashmap_get(&map, &key, NULL);\n\nworks, I would think?\n\n>\n> So generally, I'd think two entries in the table should be able to be\n> compared on their own merits, even if no keydata is available. Without\n> that property, any internal operations in the hashmap can't actually do\n> an entry comparison (e.g., a table resize that needs to rehash the\n> entries).\n>\n> It works out in the current code because the chaining is purely linear,\n> and doesn't care about order. So we can rehash and just stick the\n> elements into a new list. But if it were switched out for a different\n> data structure (e.g., a tree), then the hashmap code would need to be\n> able to compare elements.\n\nNote that most compare functions do not return an order, but only\na boolean [no]match, so putting it into an ordered tree could only\nrely on the hash that we already know without aid from the compare function.\nOf course we could fix our compare functions before doing such a\nrefactoring, but I want to point out how involved that would be.\n\n>\n> I don't think we have any particular plans for such a change, but I\n> wonder if we should avoid encouraging callers to rely on the current\n> implementation.\n\nAfter a night of sleep it is easy to fix my code to behave as the API\nintended. Yesterday I could not see how to fix it.\n\nThanks,\nStefan\n\n>\n> -Peff\n"},{"id":"319924","messageId":"20170516161315.oraebpe2zuzuo3q3@sigill.intra.peff.net","threadId":"45948","inReplyTo":"CAGZ79kZxN5-K19R+gd-pZ1Uc30_JRKugjMTJZ4er2dF71pStPg@mail.gmail.com","subject":"Re: [PATCH] hashmap: hashmap_get_next passes through keydata as well","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-05-16T16:13:15Z","receivedAt":"2017-05-16T16:13:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, May 13, 2017 at 07:06:35AM -0700, Stefan Beller wrote:\n\n> > I think I figured it out, but I have a feeling it is violating the\n> > intent of the \"keydata\" parameter.  That parameter is typically used not\n> > as a pointer to arbitrary auxiliary data, but as a trick for finding a\n> > hash entry without having to allocate a struct for it.\n> \n> Yes, I was violating the intent exactly as you describe. I'll adapt my patches\n> accordingly.\n> \n> I do not really buy into the trick though, because when the overhead of\n> allocating a 'key' struct filling in the key parts only leaving out the value\n> is so much more expensive than giving the key via this keydata argument,\n> then there are serious issues with your data structure IMHO.\n> Example:\n> [...]\n\nSure, in your example it works to allocate a partial structure on the\nstack. But if you look at the users of the hashmap, quite a few are\nstructs with final flex-array members, which cannot easily do that\nwithout allocating a new struct on the heap.  You can work around it by\nconverting them to flex-ptrs (at the cost of an extra 8 bytes per\nstruct) and having the \"key only\" version be an oddball by pointing\noutside the struct. But I do think having the flexibility in hashmap is\nnice.\n\nI actually wish that it did not even require the hashmap entry to be at\nthe beginning of the struct; it makes it hard to put the same structure\ninto multiple hashes/lists. See for example the pack MRU, which is in\nboth a hash and a doubly-linked list. Fortunately the list code is\nflexible enough to allow its pointers anywhere in the struct.\n\nSo yeah, we could design all of our data structures to fit into the\nhashmap's world-view. But I think it's handy for it to be flexible.\n\n> > It works out in the current code because the chaining is purely linear,\n> > and doesn't care about order. So we can rehash and just stick the\n> > elements into a new list. But if it were switched out for a different\n> > data structure (e.g., a tree), then the hashmap code would need to be\n> > able to compare elements.\n> \n> Note that most compare functions do not return an order, but only\n> a boolean [no]match, so putting it into an ordered tree could only\n> rely on the hash that we already know without aid from the compare function.\n> Of course we could fix our compare functions before doing such a\n> refactoring, but I want to point out how involved that would be.\n\nGood point, I didn't think of that. Moving to any non-linear lookup\nwithin a single bucket would require totally changing the cmp_fn\ncontract, and that's not likely to happen (and anyway, if we're starting\nto care about intra-bucket lookup times, that's probably a sign we\nshould be growing the table more aggressively).\n\nSo my concern was just nonsense.\n\n> > I don't think we have any particular plans for such a change, but I\n> > wonder if we should avoid encouraging callers to rely on the current\n> > implementation.\n> \n> After a night of sleep it is easy to fix my code to behave as the API\n> intended. Yesterday I could not see how to fix it.\n\nYay, then. :)\n\n-Peff\n"}]}