Re: dwarf_output overview

[Mark Wielaard <mjw at redhat dot com>]

Hi Roland,

Rereading the following reminded me that I don't fully understand the
current hash function selections:

On Tue, 2010-07-20 at 05:22 -0700, Roland McGrath wrote:
> For all the simple attribute values the method is simple.  For each flavor
> of attr_value, the collector holds a set of values seen before.  The
> subr::value_set container type is used for this.  It's based on the STL
> unordered_set, which is a hash table where we supply the key type and the
> hash and comparison functions on that type.  In these sets, our key types
> are dwarf_output::value::value_*, which are the flavor-specific subtypes
> that an attr_value actually points to.  So, each of those types has to
> provide an integer hash function (a "hasher" inner class) and a comparison
> function (operator==).
> 
> The copier does a set insertion of the input value object, which installs a
> new dwarf_output::value::value_foobar object if none matched, or doesn't if
> one did, and then produces an attr_value that points to that.  Note that
> since this is the only way any dwarf_output::attr_value objects can ever
> get created, within one dwarf_output object (really, one collector), simple
> pointer equality is exactly correct as a semantic equality check for the
> non-reference attribute values.  A corollary is that just this pointer
> value itself can be used as the hash value for the attr_value object (a
> perfect hash function).
> [...]
> Like for the other sets, a pointer
> to a particular debug_info_entry in the collector serves as a perfect
> integer hash, since by definition pointer equality of the debug_info_entry
> object exactly maps to semantic equivalence.

Is using the pointer value has hash value really useful?
It is perfect in the sense that these elements are supposed to be
unique, so if you insert an existing item, you get back the already
created item. But since you are using the pointer to the unique item as
hash, you cannot use it to lookup since the new (non-unique) item you
are trying to insert has to be constructed also, and doesn't have the
same pointer value (yet). So you will have to compare all items already
in the collector set before you can decide to return the unique item. Or
am I missing something?

I would have had expected that for anything that is created by combining
elements would have a hash function based on the hash of the items
combined.

Thanks,

Mark