From e509e7a17819f808dabb815474eb8c04540de7b3 Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Thu, 17 Jan 2008 17:36:49 +0000
Subject: [PATCH] Implemented "FIXME" in ImutAVLTree: isEqual() now also
 compares the *data* value and not just the key value when comparing trees. To
 do this we added data_type and data_type_ref to the ImutContainerInfo trait
 classes. For values stored in the tree that do not have separate key and data
 components, data_type is simply a typedef of bool, and isDataEqual() always
 evaluates to true. This allows us to support both ImmutableSet and
 ImmutableMap using the same underlying logic.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46130 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/ImmutableMap.h | 11 +++++++++--
 include/llvm/ADT/ImmutableSet.h | 18 ++++++++++++++++--
 2 files changed, 25 insertions(+), 4 deletions(-)

diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h
index 9646929c3ca..273a2977387 100644
--- a/include/llvm/ADT/ImmutableMap.h
+++ b/include/llvm/ADT/ImmutableMap.h
@@ -34,14 +34,21 @@ struct ImutKeyValueInfo {
     return V.first;
   }
   
-  static inline bool isEqual(key_type_ref L, key_type_ref R) {
-    return ImutContainerInfo<T>::isEqual(L,R);
+  static inline data_type_ref DataOfValue(value_type_ref V) {
+    return V.second;
   }
   
+  static inline bool isEqual(key_type_ref L, key_type_ref R) {
+    return ImutContainerInfo<T>::isEqual(L,R);
+  }  
   static inline bool isLess(key_type_ref L, key_type_ref R) {
     return ImutContainerInfo<T>::isLess(L,R);
   }
   
+  static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
+    return ImutContainerInfo<S>::isEqual(L,R);
+  }
+  
   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
     ImutContainerInfo<T>::Profile(ID, V.first);
     ImutContainerInfo<S>::Profile(ID, V.second);
diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index b31316b853a..7999bb59672 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -120,12 +120,16 @@ public:
         continue;
       }
       
-      // FIXME: need to compare data values, not key values, but our
-      // traits don't support this yet.
+      // Compare the keys.
       if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(LItr->getValue()),
                              ImutInfo::KeyOfValue(RItr->getValue())))
         return false;
       
+      // Also compare the data values.
+      if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(LItr->getValue()),
+                                 ImutInfo::DataOfValue(RItr->getValue())))
+        return false;
+      
       ++LItr;
       ++RItr;
     }
@@ -773,8 +777,11 @@ struct ImutContainerInfo : public ImutProfileInfo<T> {
   typedef typename ImutProfileInfo<T>::value_type_ref  value_type_ref;
   typedef value_type      key_type;
   typedef value_type_ref  key_type_ref;
+  typedef bool            data_type;
+  typedef bool            data_type_ref;
   
   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
   
   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 
     return std::equal_to<key_type>()(LHS,RHS);
@@ -783,6 +790,8 @@ struct ImutContainerInfo : public ImutProfileInfo<T> {
   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
     return std::less<key_type>()(LHS,RHS);
   }
+  
+  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
 };
 
 /// ImutContainerInfo - Specialization for pointer values to treat pointers
@@ -794,8 +803,11 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
   typedef typename ImutProfileInfo<T*>::value_type_ref  value_type_ref;
   typedef value_type      key_type;
   typedef value_type_ref  key_type_ref;
+  typedef bool            data_type;
+  typedef bool            data_type_ref;
   
   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
   
   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
     return LHS == RHS;
@@ -804,6 +816,8 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
     return LHS < RHS;
   }
+  
+  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
 };
 
 //===----------------------------------------------------------------------===//    
-- 
2.11.0