Re: RFC: modules for generic unordered sets and mappings

[Jim Meyering]

Jose E. Marchesi wrote:

>        gl_set_search               O(n)     O(1)
>
>        Here the search method returns a void *, with value (void*)-1
>        denoting "not found". Hmm, or should the search method better
>        take a 'bool *' argument???
>
> If 'gl_set_search' is merely testing the membership of an element in a
> set, would not suffice to make it to return a boolean value, like in:
>
>  bool gl_set_search (void *key);

I think the goal of this function is to return the single (first?)
KEY-matching entry from the set, or some special value if there's no
match.  However, that interface is subtly limiting, as Bruno appears to
have realized.  I would prefer one like this:

  bool gl_set_search (..., void const *key, void **match);

so as not to limit the range of valid "void*" result values.
Then we could even insert and query for a "NULL" key
or a key with that special value, (void*)-1.

I learned this the hard way, with hash_insert, since using NULL to
indicate "not found" precludes inserting "NULL" in hash.c.  I added the
more general hash_insert0 method just a few days ago, but that removes
only the restriction that the inserted KEY be a pointer.  There are
still some fundamental parts of hash.c that treat a NULL key as special.