On Tue, 2010-07-20 at 05:22 -0700, Roland McGrath wrote:
If there are no reference attributes to consider, then it proceeds
bottom up in the same straightforward way. That is, the entire map of
attributes (considered as a sequence of <int name, attr_value> pairs in a
canonical name-keyed order) can be hashed together to get a hash value for
the attributes container. Then a leaf node can combine the tag into the
that hash value to get a hash value for the whole DIE. Then, a sequence of
sibling leaf nodes' hash values are combined to form a hash value for the
whole children container. Then that hash value is combined with the tag
and the attribute map hash value to form a hash value for the whole DIE.
Then on up.
Wouldn't you also like to pass parts of the parent DIEs down? Since we
consider context of a DIE relevant for deciding whether they are really
similar. You could add a "context hash" to each DIE based on the simple
(non-reference) attributes of the parent they are embedded in. That way
two DIEs in different context would normally not get the same hash, so
you don't need to compare them plus checking their contexts are the
If that's all there were to do, it would be easy.
Of course, there are circular references.
So say we have:
<structure_type id="t1" name="list">
<member name="next" type="#p1"/>
<pointer_type id="p1" type="#t1"/>
Now, the structure_type's own attribute map is simple, so that hashes up
nicely. But, the member's attribute map includes a circular reference.
So, what we do is still hash up the whole attribute map, but use zero as
the hash value for the reference value. Now <member/> as a whole has a
hash value that contributes to the children vector hash value, and that
contributes to the structure_type's overall hash value.
Since you detect the cycle, could you use the smallest cycle size
instead of zero? Meaning, after X steps following this ref (in some
specific order), you find yourself again. That assumes that DIEs you
want to detect equal have the same circular reference structure.