Replaced (FoldingSet) profiling of ImutAVLTree with a hashing based scheme. The
authorTed Kremenek <kremenek@apple.com>
Mon, 21 Jan 2008 22:33:30 +0000 (22:33 +0000)
committerTed Kremenek <kremenek@apple.com>
Mon, 21 Jan 2008 22:33:30 +0000 (22:33 +0000)
commit6518f5fcbfc24e53ae453da0b080adf5448327be
tree9e2a51b7d2b6b91342d8eff3ab56fcbb06af0103
parent82137bd061440070839f2b94c8b7c16da4f41a6d
Replaced (FoldingSet) profiling of ImutAVLTree with a hashing based scheme. The
problem was that we previously hashed based on the pointers of the left and
right children, but this is bogus: we can easily have different trees that
represent the same set. Now we use a hashing based scheme that compares the
*contents* of the trees, but not without having to do a full scan of a tree. The
only caveat is that with hashing is that we may have collisions, which result in
two different trees being falsely labeled as equivalent. If this becomes a
problem, we can add extra data to the profile to hopefully resolve most
collisions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46224 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/ADT/ImmutableSet.h