Re: RFC: modules for generic unordered sets and mappings

[Bruno Haible]

Hi José,

> I think that I may be mixing two different things:
> set membership and searching in the contents of the set.  I will try
> to clarify myself:
> 
> - A membership function would get an element and would return a
>   boolean indicating whether the element is contained in the set. A
>   set cannot contain duplicates.
> 
>   Having two explicit types of elements (pointers and blobs), the set
>   abstraction can provide super-fast equality functions by using a
>   hash table, or whatever.  But that implicit function would not be
>   very useful for pointers, so we could let the user to specify an
>   'equal_fn' callback at set creation time.
> 
> - A 'search' function would use some search criteria to select a
>   subset of the elements in the set.
> 
>   The 'gl_set_search' function could then return the first element
>   matching that criteria.
> 
>   More than one element could be matched by a single search criteria,
>   and we could define many different searching criteria on the same
>   set.  For example, given a set of streams we may want to search for
>   EOFs.
>  
>   The 'equals_fn' function described above and used for membership
>   testing would not fit for searching purposes, since it would
>   evaluate to 'true' only for one element contained in the set.

Your second-kind search function is not a built-in function of the
data type. (We are talking about an in-memory hash table, not an
in-memory data base.) I'm only considering the first kind: a search
according to the equality function that was specified at table
construction time. This is the only criterion for which the data structure
is optimized.

And yes, the user-defined equality is only provided for the pointer-type
keys. The blob-type keys are compared with memcmp.

> ... rely on the usage of iterators to implement searches.

Yes, sure.

Bruno