Re: [PATCH] Add hash_contains function

[Jim Meyering]

Colin Watson wrote:
> I looked at converting man-db to use Gnulib's hash implementation rather
> than its own.  One obstacle seems to be that there is one place where
> man-db cares about the difference between a key not being in the hash at
> all, and a key being in the hash but with a NULL value (in Perl syntax,
> the difference between 'not exists $hash{$key}' and 'not defined
> $hash{$key}').  I haven't spent much time looking at the relevant code
> and so it may well be that it can be rewritten to avoid relying on this
> distinction, but in general it does seem like a useful distinction to
> draw; most high-level languages' built-in hash implementations allow you
> to ask whether a key exists without testing the truth of its value.

Hi Colin,

It's good to hear that man-db might use gnulib's hash function.

If the hash module were really unable to distinguish those cases, we
would have found it too limiting (and fixed it) long ago ;-)

The API for hash_insert requires that you pass it a non-NULL-pointer
(usually to a key/value pair).  If you want to map a particular
"key" to NULL, that's fine: you'd call hash_insert with the address
of a {SOME_KEY,NULL} buffer (you define the lay-out).  To look up that
key, you'd call hash_lookup with the pointer to a struct containing
{SOME_KEY,no-need-to-define}, and it will find the matching entry in
the table, returning a pointer, P, to the {SOME_KEY,NULL} buffer that
is in the table.  You would then examine P->value to see whether
SOME_KEY's value is NULL.

Note that if you want to use the hash table as a simple set, there is
no need to have a separate key,value struct, since the value would be
irrelevant.  In that case, you can save storage and indirection costs
by passing the key string directly to hash_insert (always assuming the
hash_compare and hash_hash functions are aware).

The bottom line is that hash_lookup cannot return NULL for a good
reason.  One cannot call hash_insert with a NULL pointer, so hash_lookup
could never return NULL for a matching entry in the hash table.

Perhaps this can be attributed to the lack of documentation and/or
examples?  For reference, there are many uses in gnulib itself
and in the tar and coreutils packages.

Jim