patchhashmap: hashmap_get_next passes through keydata as well

The 'keydata' may be of value in the underlying compare function to decide if the given two entries are the same.

Signed-off-by: Stefan Beller <sbeller@google.com>
---
 Documentation/technical/api-hashmap.txt | 6 ++++--
 diffcore-rename.c                       | 2 +-
 hashmap.c                               | 5 +++--
 hashmap.h                               | 3 ++-
 name-hash.c                             | 2 +-
 t/helper/test-hashmap.c                 | 2 +-
 6 files changed, 12 insertions(+), 8 deletions(-)

On Fri, May 12, 2017 at 01:02:44PM -0700, Stefan Beller wrote:

I had to scratch my head over this for a minute, because there isn't really any motivating example of what you're trying to do.

I think I figured it out, but I have a feeling it is violating the intent of the "keydata" parameter. That parameter is typically used not as a pointer to arbitrary auxiliary data, but as a trick for finding a hash entry without having to allocate a struct for it.

So generally, I'd think two entries in the table should be able to be compared on their own merits, even if no keydata is available. Without that property, any internal operations in the hashmap can't actually do an entry comparison (e.g., a table resize that needs to rehash the entries).

It works out in the current code because the chaining is purely linear, and doesn't care about order. So we can rehash and just stick the elements into a new list. But if it were switched out for a different data structure (e.g., a tree), then the hashmap code would need to be able to compare elements.

I don't think we have any particular plans for such a change, but I wonder if we should avoid encouraging callers to rely on the current implementation.

-Peff

On Sat, May 13, 2017 at 1:50 AM, Jeff King <peff@peff.net> wrote:

Yes, I was violating the intent exactly as you describe. I'll adapt my patches accordingly.

I do not really buy into the trick though, because when the overhead of allocating a 'key' struct filling in the key parts only leaving out the value is so much more expensive than giving the key via this keydata argument, then there are serious issues with your data structure IMHO. Example:

  struct {
    struct hashmap_entry ent;
    int actual key;
    char value[4096*1024]
  } key_plus_value;

Now when you want to look up a specific key, you don't want to allocate such a struct on the stack, as we'd be wasting 4M memory of the stack trashing the caches. However the neat part about this struct is that the key part is (a) totally separate from the values, and (b) comes before any value part, such that

  struct {
    struct hashmap_entry ent;
    int actual key;
  } key_only;

  struct key_only = {{NULL, 0}, 42};
  struct key_plus_value *match = hashmap_get(&map, &key, NULL);

works, I would think?

Note that most compare functions do not return an order, but only a boolean [no]match, so putting it into an ordered tree could only rely on the hash that we already know without aid from the compare function. Of course we could fix our compare functions before doing such a refactoring, but I want to point out how involved that would be.

After a night of sleep it is easy to fix my code to behave as the API intended. Yesterday I could not see how to fix it.

Thanks, Stefan

On Sat, May 13, 2017 at 07:06:35AM -0700, Stefan Beller wrote:

Sure, in your example it works to allocate a partial structure on the stack. But if you look at the users of the hashmap, quite a few are structs with final flex-array members, which cannot easily do that without allocating a new struct on the heap. You can work around it by converting them to flex-ptrs (at the cost of an extra 8 bytes per struct) and having the "key only" version be an oddball by pointing outside the struct. But I do think having the flexibility in hashmap is nice.

I actually wish that it did not even require the hashmap entry to be at the beginning of the struct; it makes it hard to put the same structure into multiple hashes/lists. See for example the pack MRU, which is in both a hash and a doubly-linked list. Fortunately the list code is flexible enough to allow its pointers anywhere in the struct.

So yeah, we could design all of our data structures to fit into the hashmap's world-view. But I think it's handy for it to be flexible.

Good point, I didn't think of that. Moving to any non-linear lookup within a single bucket would require totally changing the cmp_fn contract, and that's not likely to happen (and anyway, if we're starting to care about intra-bucket lookup times, that's probably a sign we should be growing the table more aggressively).

So my concern was just nonsense.

Yay, then. :)

-Peff