On Jan 21, 2008, at 2:33 PM, Ted Kremenek wrote: > URL: http://llvm.org/viewvc/llvm-project?rev=46224&view=rev > Log: > 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.
I don't think this works Ted: collisions *will* cause the tree to be corrupt, and you can't guarantee that they won't happen. I don't think this is valid for all clients of the data structure. -Chris _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
