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