Re: RFC: modules for generic unordered sets and mappings

[Bruno Haible]

Jim Meyering wrote:
> I think the goal of this function is to return the single (first?)
> KEY-matching entry from the set ...
> ...
> Think of set of composite values (a struct), of which
> one serves as a key.  You may want to query whether a
> dummy { key, x, y, z } is in the set, solely to find
> some real element with a matching key.

Yes, exactly. By the fact that the user can specify the equality function
and the hash function, two keys may be equal that are not == as pointers.
This can be used to store payload on the key's side. For example, in gettext,
we have
  typedef struct { msgid; msgstr; } *message_t;
The equality function compares only the msgid field of the message, but the
programmer is of course also interested in the msgstr part.

A similar use case is for uniquifying tables. These are conceptually a mapping
from a key to a canonical instance of the key, so that the value compares
equal to the key. If you implement this as a set rather than as a mapping,
you save memory.

> But then, is the set merely a special case of a map?

Yes it is. The programmer could also store the payload in a separate value.
But if the data structures of the program already store the payload with
the key, it can be viewed as a set.

> 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.

I have a slight preference for

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

because the user's value type most often is a 'foo_t *', not 'void *',
and in the first case if he declares a variable of type 'foo_t *',
he has to cast the pointer, breaking strict-aliasing rules. In the
second case the assignment from 'void *' to 'foo_t *' does not break
strict-aliasing rules.

Jose E. Marchesi wrote:
> The returned entry would be something like 'gl_list_node_t', right?

Good point. For the mapping data structure, I'll bear this in mind.
So that after looking up a value you can store a new value without
performing the search a second time.

But for the set abstraction, you don't need a type like 'gl_list_node_t'.

> I am not sure what would be the benefit of returning
> something like 'gl_set_node_t' instead of the boolean directly.  In
> case we want to change the membership status for some key then we
> simply check and remove/insert.

For removals, you don't need a 'gl_set_node_t': just call the 'remove'
operation. For insertions, Jim has already suggested a "find or add"
a.k.a. "insert is not already contained" operation. When you have this
one, you don't need 'gl_set_node_t'.

Bruno