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