Re: [PATCH v4 0/3]

[Jeff King <peff@peff.net>]

On Mon, Dec 24, 2018 at 12:47:53AM -0800, nbelakovski@gmail.com wrote:

> From: Nickolai Belakovski <nbelakovski@gmail.com>
> 
> > I don't think that works. The default function is always_equal(), which
> > will treat two entries equal if they have the same hash value. I.e., any
> > collisions would be considered a match.
> 
> You're absolutely right. I've added a compare function, but I left out the
> functionality for it to work with an entry passed in as a key. Doing so would
> mean the user would have to allocate a worktree struct, which just seems silly
> when the ref is all that's needed (and also defeats the purpose of avoiding
> extra allocations).

Unfortunately, that doesn't quite work. :)

Your compare function has to handle _both_ cases: two keys, or one key
and a keydata.

The former may be called when the hashmap has to compare two entries
internally (e.g., when it has to re-bucket all of the entries after a
resize). Your tests likely wouldn't run into this case in practice,
since you'd only have a handful of worktrees. But if you added, say,
thousands of worktrees and we had to grow the hash midway through the
process, it would segfault.  So you do need to handle the case when your
keydata is NULL.

In theory it would also be used for comparisons if we used a more clever
data structure to hold entries within a bucket. But since we just use a
linked list and linear search for now, we don't.

> And while most of the hashmap API seems OK, yea, this is definitely awful. It
> feels like it should just be able to take a key and return either an entry or
> NULL, and do away with entry_or_key and equals_function_data.

In your case, yeah, equals_function_data is not used at all (but there
are a few call-sites which need it to avoid relying on global data).

But the entry_or_key (coupled with keydata) is the magic that lets the
same function be used for both lookups as well as internal entry
comparisons.

I think having two separate comparison functions would make this a lot
more clear, though likely at the cost of having more boilerplate.

-Peff