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 22namespace 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. 31template <typename T, unsigned N, typename C = std::less<T> > 32class 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 // In small mode SmallPtrSet uses linear search for the elements, so it is 42 // not a good idea to choose this value too high. You may consider using a 43 // DenseSet<> instead if you expect many elements in the set. 44 static_assert(N <= 32, "N should be small"); 45 46public: 47 typedef size_t size_type; 48 SmallSet() {} 49 50 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 51 return Vector.empty() && Set.empty(); 52 } 53 54 size_type size() const { 55 return isSmall() ? Vector.size() : Set.size(); 56 } 57 58 /// count - Return 1 if the element is in the set, 0 otherwise. 59 size_type count(const T &V) const { 60 if (isSmall()) { 61 // Since the collection is small, just do a linear search. 62 return vfind(V) == Vector.end() ? 0 : 1; 63 } else { 64 return Set.count(V); 65 } 66 } 67 68 /// insert - Insert an element into the set if it isn't already there. 69 /// Returns true if the element is inserted (it was not in the set before). 70 /// The first value of the returned pair is unused and provided for 71 /// partial compatibility with the standard library self-associative container 72 /// concept. 73 // FIXME: Add iterators that abstract over the small and large form, and then 74 // return those here. 75 std::pair<NoneType, bool> insert(const T &V) { 76 if (!isSmall()) 77 return std::make_pair(None, Set.insert(V).second); 78 79 VIterator I = vfind(V); 80 if (I != Vector.end()) // Don't reinsert if it already exists. 81 return std::make_pair(None, false); 82 if (Vector.size() < N) { 83 Vector.push_back(V); 84 return std::make_pair(None, true); 85 } 86 87 // Otherwise, grow from vector to set. 88 while (!Vector.empty()) { 89 Set.insert(Vector.back()); 90 Vector.pop_back(); 91 } 92 Set.insert(V); 93 return std::make_pair(None, true); 94 } 95 96 template <typename IterT> 97 void insert(IterT I, IterT E) { 98 for (; I != E; ++I) 99 insert(*I); 100 } 101 102 bool erase(const T &V) { 103 if (!isSmall()) 104 return Set.erase(V); 105 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 106 if (*I == V) { 107 Vector.erase(I); 108 return true; 109 } 110 return false; 111 } 112 113 void clear() { 114 Vector.clear(); 115 Set.clear(); 116 } 117 118private: 119 bool isSmall() const { return Set.empty(); } 120 121 VIterator vfind(const T &V) const { 122 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 123 if (*I == V) 124 return I; 125 return Vector.end(); 126 } 127}; 128 129/// If this set is of pointer values, transparently switch over to using 130/// SmallPtrSet for performance. 131template <typename PointeeType, unsigned N> 132class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 133 134} // end namespace llvm 135 136#endif 137