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