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/None.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include <set> 21 22 namespace llvm { 23 24 /// SmallSet - This maintains a set of unique values, optimizing for the case 25 /// when the set is small (less than N). In this case, the set can be 26 /// maintained with no mallocs. If the set gets large, we expand to using an 27 /// std::set to maintain reasonable lookup times. 28 /// 29 /// Note that this set does not provide a way to iterate over members in the 30 /// set. 31 template <typename T, unsigned N, typename C = std::less<T> > 32 class SmallSet { 33 /// Use a SmallVector to hold the elements here (even though it will never 34 /// reach its 'large' stage) to avoid calling the default ctors of elements 35 /// we will never use. 36 SmallVector<T, N> Vector; 37 std::set<T, C> Set; 38 typedef typename SmallVector<T, N>::const_iterator VIterator; 39 typedef typename SmallVector<T, N>::iterator mutable_iterator; 40 41 public: 42 typedef size_t size_type; SmallSet()43 SmallSet() {} 44 empty()45 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 46 return Vector.empty() && Set.empty(); 47 } 48 size()49 size_type size() const { 50 return isSmall() ? Vector.size() : Set.size(); 51 } 52 53 /// count - Return 1 if the element is in the set, 0 otherwise. count(const T & V)54 size_type count(const T &V) const { 55 if (isSmall()) { 56 // Since the collection is small, just do a linear search. 57 return vfind(V) == Vector.end() ? 0 : 1; 58 } else { 59 return Set.count(V); 60 } 61 } 62 63 /// insert - Insert an element into the set if it isn't already there. 64 /// Returns true if the element is inserted (it was not in the set before). 65 /// The first value of the returned pair is unused and provided for 66 /// partial compatibility with the standard library self-associative container 67 /// concept. 68 // FIXME: Add iterators that abstract over the small and large form, and then 69 // return those here. insert(const T & V)70 std::pair<NoneType, bool> insert(const T &V) { 71 if (!isSmall()) 72 return std::make_pair(None, Set.insert(V).second); 73 74 VIterator I = vfind(V); 75 if (I != Vector.end()) // Don't reinsert if it already exists. 76 return std::make_pair(None, false); 77 if (Vector.size() < N) { 78 Vector.push_back(V); 79 return std::make_pair(None, true); 80 } 81 82 // Otherwise, grow from vector to set. 83 while (!Vector.empty()) { 84 Set.insert(Vector.back()); 85 Vector.pop_back(); 86 } 87 Set.insert(V); 88 return std::make_pair(None, true); 89 } 90 91 template <typename IterT> insert(IterT I,IterT E)92 void insert(IterT I, IterT E) { 93 for (; I != E; ++I) 94 insert(*I); 95 } 96 erase(const T & V)97 bool erase(const T &V) { 98 if (!isSmall()) 99 return Set.erase(V); 100 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 101 if (*I == V) { 102 Vector.erase(I); 103 return true; 104 } 105 return false; 106 } 107 clear()108 void clear() { 109 Vector.clear(); 110 Set.clear(); 111 } 112 113 private: isSmall()114 bool isSmall() const { return Set.empty(); } 115 vfind(const T & V)116 VIterator vfind(const T &V) const { 117 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 118 if (*I == V) 119 return I; 120 return Vector.end(); 121 } 122 }; 123 124 /// If this set is of pointer values, transparently switch over to using 125 /// SmallPtrSet for performance. 126 template <typename PointeeType, unsigned N> 127 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 128 129 } // end namespace llvm 130 131 #endif 132