1 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 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/ADT/STLExtras.h" 21 #include "llvm/ADT/iterator.h" 22 #include "llvm/Support/Compiler.h" 23 #include "llvm/Support/type_traits.h" 24 #include <cstddef> 25 #include <functional> 26 #include <set> 27 #include <type_traits> 28 #include <utility> 29 30 namespace llvm { 31 32 /// SmallSetIterator - This class implements a const_iterator for SmallSet by 33 /// delegating to the underlying SmallVector or Set iterators. 34 template <typename T, unsigned N, typename C> 35 class SmallSetIterator 36 : public iterator_facade_base<SmallSetIterator<T, N, C>, 37 std::forward_iterator_tag, T> { 38 private: 39 using SetIterTy = typename std::set<T, C>::const_iterator; 40 using VecIterTy = typename SmallVector<T, N>::const_iterator; 41 using SelfTy = SmallSetIterator<T, N, C>; 42 43 /// Iterators to the parts of the SmallSet containing the data. They are set 44 /// depending on isSmall. 45 union { 46 SetIterTy SetIter; 47 VecIterTy VecIter; 48 }; 49 50 bool isSmall; 51 52 public: 53 SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {} 54 55 SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {} 56 57 // Spell out destructor, copy/move constructor and assignment operators for 58 // MSVC STL, where set<T>::const_iterator is not trivially copy constructible. 59 ~SmallSetIterator() { 60 if (isSmall) 61 VecIter.~VecIterTy(); 62 else 63 SetIter.~SetIterTy(); 64 } 65 66 SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) { 67 if (isSmall) 68 VecIter = Other.VecIter; 69 else 70 // Use placement new, to make sure SetIter is properly constructed, even 71 // if it is not trivially copy-able (e.g. in MSVC). 72 new (&SetIter) SetIterTy(Other.SetIter); 73 } 74 75 SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) { 76 if (isSmall) 77 VecIter = std::move(Other.VecIter); 78 else 79 // Use placement new, to make sure SetIter is properly constructed, even 80 // if it is not trivially copy-able (e.g. in MSVC). 81 new (&SetIter) SetIterTy(std::move(Other.SetIter)); 82 } 83 84 SmallSetIterator& operator=(const SmallSetIterator& Other) { 85 // Call destructor for SetIter, so it gets properly destroyed if it is 86 // not trivially destructible in case we are setting VecIter. 87 if (!isSmall) 88 SetIter.~SetIterTy(); 89 90 isSmall = Other.isSmall; 91 if (isSmall) 92 VecIter = Other.VecIter; 93 else 94 new (&SetIter) SetIterTy(Other.SetIter); 95 return *this; 96 } 97 98 SmallSetIterator& operator=(SmallSetIterator&& Other) { 99 // Call destructor for SetIter, so it gets properly destroyed if it is 100 // not trivially destructible in case we are setting VecIter. 101 if (!isSmall) 102 SetIter.~SetIterTy(); 103 104 isSmall = Other.isSmall; 105 if (isSmall) 106 VecIter = std::move(Other.VecIter); 107 else 108 new (&SetIter) SetIterTy(std::move(Other.SetIter)); 109 return *this; 110 } 111 112 bool operator==(const SmallSetIterator &RHS) const { 113 if (isSmall != RHS.isSmall) 114 return false; 115 if (isSmall) 116 return VecIter == RHS.VecIter; 117 return SetIter == RHS.SetIter; 118 } 119 120 SmallSetIterator &operator++() { // Preincrement 121 if (isSmall) 122 VecIter++; 123 else 124 SetIter++; 125 return *this; 126 } 127 128 const T &operator*() const { return isSmall ? *VecIter : *SetIter; } 129 }; 130 131 /// SmallSet - This maintains a set of unique values, optimizing for the case 132 /// when the set is small (less than N). In this case, the set can be 133 /// maintained with no mallocs. If the set gets large, we expand to using an 134 /// std::set to maintain reasonable lookup times. 135 template <typename T, unsigned N, typename C = std::less<T>> 136 class SmallSet { 137 /// Use a SmallVector to hold the elements here (even though it will never 138 /// reach its 'large' stage) to avoid calling the default ctors of elements 139 /// we will never use. 140 SmallVector<T, N> Vector; 141 std::set<T, C> Set; 142 143 using VIterator = typename SmallVector<T, N>::const_iterator; 144 using mutable_iterator = typename SmallVector<T, N>::iterator; 145 146 // In small mode SmallPtrSet uses linear search for the elements, so it is 147 // not a good idea to choose this value too high. You may consider using a 148 // DenseSet<> instead if you expect many elements in the set. 149 static_assert(N <= 32, "N should be small"); 150 151 public: 152 using size_type = size_t; 153 using const_iterator = SmallSetIterator<T, N, C>; 154 155 SmallSet() = default; 156 157 LLVM_NODISCARD bool empty() const { 158 return Vector.empty() && Set.empty(); 159 } 160 161 size_type size() const { 162 return isSmall() ? Vector.size() : Set.size(); 163 } 164 165 /// count - Return 1 if the element is in the set, 0 otherwise. 166 size_type count(const T &V) const { 167 if (isSmall()) { 168 // Since the collection is small, just do a linear search. 169 return vfind(V) == Vector.end() ? 0 : 1; 170 } else { 171 return Set.count(V); 172 } 173 } 174 175 /// insert - Insert an element into the set if it isn't already there. 176 /// Returns true if the element is inserted (it was not in the set before). 177 /// The first value of the returned pair is unused and provided for 178 /// partial compatibility with the standard library self-associative container 179 /// concept. 180 // FIXME: Add iterators that abstract over the small and large form, and then 181 // return those here. 182 std::pair<NoneType, bool> insert(const T &V) { 183 if (!isSmall()) 184 return std::make_pair(None, Set.insert(V).second); 185 186 VIterator I = vfind(V); 187 if (I != Vector.end()) // Don't reinsert if it already exists. 188 return std::make_pair(None, false); 189 if (Vector.size() < N) { 190 Vector.push_back(V); 191 return std::make_pair(None, true); 192 } 193 194 // Otherwise, grow from vector to set. 195 while (!Vector.empty()) { 196 Set.insert(Vector.back()); 197 Vector.pop_back(); 198 } 199 Set.insert(V); 200 return std::make_pair(None, true); 201 } 202 203 template <typename IterT> 204 void insert(IterT I, IterT E) { 205 for (; I != E; ++I) 206 insert(*I); 207 } 208 209 bool erase(const T &V) { 210 if (!isSmall()) 211 return Set.erase(V); 212 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 213 if (*I == V) { 214 Vector.erase(I); 215 return true; 216 } 217 return false; 218 } 219 220 void clear() { 221 Vector.clear(); 222 Set.clear(); 223 } 224 225 const_iterator begin() const { 226 if (isSmall()) 227 return {Vector.begin()}; 228 return {Set.begin()}; 229 } 230 231 const_iterator end() const { 232 if (isSmall()) 233 return {Vector.end()}; 234 return {Set.end()}; 235 } 236 237 /// Check if the SmallSet contains the given element. 238 bool contains(const T &V) const { 239 if (isSmall()) 240 return vfind(V) != Vector.end(); 241 return Set.find(V) != Set.end(); 242 } 243 244 private: 245 bool isSmall() const { return Set.empty(); } 246 247 VIterator vfind(const T &V) const { 248 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 249 if (*I == V) 250 return I; 251 return Vector.end(); 252 } 253 }; 254 255 /// If this set is of pointer values, transparently switch over to using 256 /// SmallPtrSet for performance. 257 template <typename PointeeType, unsigned N> 258 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 259 260 /// Equality comparison for SmallSet. 261 /// 262 /// Iterates over elements of LHS confirming that each element is also a member 263 /// of RHS, and that RHS contains no additional values. 264 /// Equivalent to N calls to RHS.count. 265 /// For small-set mode amortized complexity is O(N^2) 266 /// For large-set mode amortized complexity is linear, worst case is O(N^2) (if 267 /// every hash collides). 268 template <typename T, unsigned LN, unsigned RN, typename C> 269 bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { 270 if (LHS.size() != RHS.size()) 271 return false; 272 273 // All elements in LHS must also be in RHS 274 return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); }); 275 } 276 277 /// Inequality comparison for SmallSet. 278 /// 279 /// Equivalent to !(LHS == RHS). See operator== for performance notes. 280 template <typename T, unsigned LN, unsigned RN, typename C> 281 bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { 282 return !(LHS == RHS); 283 } 284 285 } // end namespace llvm 286 287 #endif // LLVM_ADT_SMALLSET_H 288