Re: [PATCH] Document khash

[Jeff King <peff@peff.net>]

On Mon, Nov 25, 2013 at 04:04:48PM +0100, Thomas Rast wrote:

> > I think I'll also lend you a hand writing Documentation/technical/api-khash.txt
> > (expect it tomorrow) so that we also have documentation in the git
> > style, where gitters can be expected to find it on their own.
> 
> Here goes.

Thanks. Some comments below.

> > Furthermore, would it be a problem to name the second hash sha1_int
> > instead?  I have another use for such a hash, and I can't imagine I'm
> > the only one.  (That's not critical however, I can do the required
> > editing in that other series.)
> 
> Actually, let's not do that.  Since everything is 'static inline'
> anyway, there's no cost to simply instantiating more hashes as needed.

Yeah. If we cared about code duplication, we'd have to split it into
declaration and definition macros, and then collect the definitions in
one .c file (khash does support this, but we don't use it). I don't
think we are using enough repeated ones to make it matter, and most of
the functions benefit from inlining anyway.

> +------------
> +#import "khash.h"
> +KHASH_INIT(NAME, key_t, value_t, is_map, key_hash_fn, key_equal_fn)
> +------------

#import?

> +The arguments are as follows:
> [...]
> +`khint_t key_hash_fn(key_t)`::
> +	Hash function.

It is true that this is a khint_t, but I do not think knowing that helps
the caller. They need to design a hash function, so knowing the size and
type of the hint helps. Maybe:

  Return a hash value for a key. The khint_t is a 32-bit unsigned value.
  Git provides __kh_oid_hash, which converts a sha1 into a hash value.

> +`int key_equal_fn(key_t a, key_t b)`::
> +	Comparison function.  Return 1 if the two keys are the same, 0
> +	otherwise.

Here we provide __kh_oid_cmp, and we should mention it. Based on recent
discussions, this should probably be __kh_oid_equal, since it is not a
"cmp" function in the ordering sense.

> +`khint_t kh_get_NAME(const kh_NAME_t *hash, key_t key)`::
> +	Find the given key in the hash table.  The returned khint_t
> +	should be treated as an opaque iterator token that indexes
> +	into the hash.  Use `kh_value` to get the value from the
> +	token.  If the key does not exist, returns kh_end(hash).

I do not know of the khash author's intention, but in the bitmap code we
prefer khiter_t to represent an iterator. It is the same as a khint_t,
but I think that is an implementation detail (and the khash functions
should probably be returning a khiter_t).

> [...]

The rest of it looks correct to me.

-Peff