Re: RFC: modules for generic unordered sets and mappings

[Jim Meyering]

Bruno Haible wrote:
> Hi all,
>
> Apropos hash tables.
>
> For some years now, we have generic lists in gnulib. "Generic" means that the
> programmer can switch the implementation easily, because he's programming
> against an abstract API that has a number of different implementations.
>
> Here is my draft for applying the same approach to unordered sets. The normal
> implementation would be a hash table, but there are important variations:
>   - Is the key a pointer, or a memory block of arbitrary size?
>   - Is the value stored, or implicit?
>   - Does inserting a (key,value) pair make a copy of the key?
>   - Does the table allow removals?
>
> Feedback is highly appreciated! Do you see some interesting use case that I
> have overlooked?
>
>
> There shall be three abstract types:
>   * Unordered set
>   * Mapping from an unordered set to a 'void *' value
>   * Unordered multiset
>
>
> Unordered Set
> =============
>
> There are two flavours, depending on the key type: either a pointer
> (no copying involved upon insertion), or a memory block of varying size
> (copied during insertion).

For du, at least, it would be useful to allow a key type of uintmax_t.