1 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the SmallSet class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SMALLSET_H 15 #define LLVM_ADT_SMALLSET_H 16 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include <set> 20 21 namespace llvm { 22 23 /// SmallSet - This maintains a set of unique values, optimizing for the case 24 /// when the set is small (less than N). In this case, the set can be 25 /// maintained with no mallocs. If the set gets large, we expand to using an 26 /// std::set to maintain reasonable lookup times. 27 /// 28 /// Note that this set does not provide a way to iterate over members in the 29 /// set. 30 template <typename T, unsigned N, typename C = std::less<T> > 31 class SmallSet { 32 /// Use a SmallVector to hold the elements here (even though it will never 33 /// reach its 'large' stage) to avoid calling the default ctors of elements 34 /// we will never use. 35 SmallVector<T, N> Vector; 36 std::set<T, C> Set; 37 typedef typename SmallVector<T, N>::const_iterator VIterator; 38 typedef typename SmallVector<T, N>::iterator mutable_iterator; 39 public: 40 SmallSet() {} 41 42 bool empty() const { return Vector.empty() && Set.empty(); } 43 unsigned size() const { 44 return isSmall() ? Vector.size() : Set.size(); 45 } 46 47 /// count - Return true if the element is in the set. 48 bool count(const T &V) const { 49 if (isSmall()) { 50 // Since the collection is small, just do a linear search. 51 return vfind(V) != Vector.end(); 52 } else { 53 return Set.count(V); 54 } 55 } 56 57 /// insert - Insert an element into the set if it isn't already there. 58 /// Returns true if the element is inserted (it was not in the set before). 59 bool insert(const T &V) { 60 if (!isSmall()) 61 return Set.insert(V).second; 62 63 VIterator I = vfind(V); 64 if (I != Vector.end()) // Don't reinsert if it already exists. 65 return false; 66 if (Vector.size() < N) { 67 Vector.push_back(V); 68 return true; 69 } 70 71 // Otherwise, grow from vector to set. 72 while (!Vector.empty()) { 73 Set.insert(Vector.back()); 74 Vector.pop_back(); 75 } 76 Set.insert(V); 77 return true; 78 } 79 80 template <typename IterT> 81 void insert(IterT I, IterT E) { 82 for (; I != E; ++I) 83 insert(*I); 84 } 85 86 bool erase(const T &V) { 87 if (!isSmall()) 88 return Set.erase(V); 89 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 90 if (*I == V) { 91 Vector.erase(I); 92 return true; 93 } 94 return false; 95 } 96 97 void clear() { 98 Vector.clear(); 99 Set.clear(); 100 } 101 private: 102 bool isSmall() const { return Set.empty(); } 103 104 VIterator vfind(const T &V) const { 105 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 106 if (*I == V) 107 return I; 108 return Vector.end(); 109 } 110 }; 111 112 /// If this set is of pointer values, transparently switch over to using 113 /// SmallPtrSet for performance. 114 template <typename PointeeType, unsigned N> 115 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 116 117 } // end namespace llvm 118 119 #endif 120