/home/arjun/llvm-project/llvm/include/llvm/ADT/DenseSet.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- 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 | | // This file defines the DenseSet and SmallDenseSet classes. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_ADT_DENSESET_H |
14 | | #define LLVM_ADT_DENSESET_H |
15 | | |
16 | | #include "llvm/ADT/DenseMap.h" |
17 | | #include "llvm/ADT/DenseMapInfo.h" |
18 | | #include "llvm/Support/MathExtras.h" |
19 | | #include "llvm/Support/type_traits.h" |
20 | | #include <algorithm> |
21 | | #include <cstddef> |
22 | | #include <initializer_list> |
23 | | #include <iterator> |
24 | | #include <utility> |
25 | | |
26 | | namespace llvm { |
27 | | |
28 | | namespace detail { |
29 | | |
30 | | struct DenseSetEmpty {}; |
31 | | |
32 | | // Use the empty base class trick so we can create a DenseMap where the buckets |
33 | | // contain only a single item. |
34 | | template <typename KeyT> class DenseSetPair : public DenseSetEmpty { |
35 | | KeyT key; |
36 | | |
37 | | public: |
38 | 0 | KeyT &getFirst() { return key; } Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairINS_9StringRefEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairINS_8ArrayRefIlEEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIjE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir4TypeEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir9AttributeEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIPKN4mlir16DialectInterfaceEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir8LocationEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir9AffineMapEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir10IntegerSetEE8getFirstEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir6detail18StorageUniquerImpl13HashedStorageEE8getFirstEv |
39 | 0 | const KeyT &getFirst() const { return key; } Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairINS_9StringRefEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairINS_8ArrayRefIlEEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIPKN4mlir16DialectInterfaceEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIjE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIN4mlir4TypeEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIN4mlir9AttributeEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIN4mlir8LocationEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIN4mlir9AffineMapEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIN4mlir10IntegerSetEE8getFirstEv Unexecuted instantiation: _ZNK4llvm6detail12DenseSetPairIN4mlir6detail18StorageUniquerImpl13HashedStorageEE8getFirstEv |
40 | 0 | DenseSetEmpty &getSecond() { return *this; } Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairINS_9StringRefEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairINS_8ArrayRefIlEEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIjE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir4TypeEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir9AttributeEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIPKN4mlir16DialectInterfaceEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir8LocationEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir10IntegerSetEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir9AffineMapEE9getSecondEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetPairIN4mlir6detail18StorageUniquerImpl13HashedStorageEE9getSecondEv |
41 | | const DenseSetEmpty &getSecond() const { return *this; } |
42 | | }; |
43 | | |
44 | | /// Base class for DenseSet and DenseSmallSet. |
45 | | /// |
46 | | /// MapTy should be either |
47 | | /// |
48 | | /// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, |
49 | | /// detail::DenseSetPair<ValueT>> |
50 | | /// |
51 | | /// or the equivalent SmallDenseMap type. ValueInfoT must implement the |
52 | | /// DenseMapInfo "concept". |
53 | | template <typename ValueT, typename MapTy, typename ValueInfoT> |
54 | | class DenseSetImpl { |
55 | | static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), |
56 | | "DenseMap buckets unexpectedly large!"); |
57 | | MapTy TheMap; |
58 | | |
59 | | template <typename T> |
60 | | using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; |
61 | | |
62 | | public: |
63 | | using key_type = ValueT; |
64 | | using value_type = ValueT; |
65 | | using size_type = unsigned; |
66 | | |
67 | 0 | explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {} Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplINS_8ArrayRefIlEENS_13SmallDenseMapIS3_NS0_13DenseSetEmptyELj8ENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_EC2Ej Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIjNS_8DenseMapIjNS0_13DenseSetEmptyENS_12DenseMapInfoIjEENS0_12DenseSetPairIjEEEES5_EC2Ej Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir9AttributeENS_8DenseMapIS3_NS0_13DenseSetEmptyENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_EC2Ej Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir4TypeENS_8DenseMapIS3_NS0_13DenseSetEmptyENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_EC2Ej Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIPKN4mlir16DialectInterfaceENS_8DenseMapIS5_NS0_13DenseSetEmptyENS2_6detail30DialectInterfaceCollectionBase16InterfaceKeyInfoENS0_12DenseSetPairIS5_EEEESA_EC2Ej Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir8LocationENS_13SmallDenseMapIS3_NS0_13DenseSetEmptyELj4ENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_EC2Ej Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_EC2Ej Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_EC2Ej Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_EC2Ej |
68 | | |
69 | | template <typename InputIt> |
70 | | DenseSetImpl(const InputIt &I, const InputIt &E) |
71 | | : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) { |
72 | | insert(I, E); |
73 | | } |
74 | | |
75 | | DenseSetImpl(std::initializer_list<ValueT> Elems) |
76 | | : DenseSetImpl(PowerOf2Ceil(Elems.size())) { |
77 | | insert(Elems.begin(), Elems.end()); |
78 | | } |
79 | | |
80 | | bool empty() const { return TheMap.empty(); } |
81 | | size_type size() const { return TheMap.size(); } |
82 | | size_t getMemorySize() const { return TheMap.getMemorySize(); } |
83 | | |
84 | | /// Grow the DenseSet so that it has at least Size buckets. Will not shrink |
85 | | /// the Size of the set. |
86 | | void resize(size_t Size) { TheMap.resize(Size); } |
87 | | |
88 | | /// Grow the DenseSet so that it can contain at least \p NumEntries items |
89 | | /// before resizing again. |
90 | | void reserve(size_t Size) { TheMap.reserve(Size); } |
91 | | |
92 | | void clear() { |
93 | | TheMap.clear(); |
94 | | } |
95 | | |
96 | | /// Return 1 if the specified key is in the set, 0 otherwise. |
97 | 0 | size_type count(const_arg_type_t<ValueT> V) const { |
98 | 0 | return TheMap.count(V); |
99 | 0 | } |
100 | | |
101 | | bool erase(const ValueT &V) { |
102 | | return TheMap.erase(V); |
103 | | } |
104 | | |
105 | | void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); } |
106 | | |
107 | | // Iterators. |
108 | | |
109 | | class ConstIterator; |
110 | | |
111 | | class Iterator { |
112 | | typename MapTy::iterator I; |
113 | | friend class DenseSetImpl; |
114 | | friend class ConstIterator; |
115 | | |
116 | | public: |
117 | | using difference_type = typename MapTy::iterator::difference_type; |
118 | | using value_type = ValueT; |
119 | | using pointer = value_type *; |
120 | | using reference = value_type &; |
121 | | using iterator_category = std::forward_iterator_tag; |
122 | | |
123 | | Iterator() = default; |
124 | 0 | Iterator(const typename MapTy::iterator &i) : I(i) {} Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplINS_9StringRefENS_8DenseMapIS2_NS0_13DenseSetEmptyENS_12DenseMapInfoIS2_EENS0_12DenseSetPairIS2_EEEES6_E8IteratorC2ERKNS_16DenseMapIteratorIS2_S4_S6_S8_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplINS_8ArrayRefIlEENS_13SmallDenseMapIS3_NS0_13DenseSetEmptyELj8ENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E8IteratorC2ERKNS_16DenseMapIteratorIS3_S5_S7_S9_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIjNS_8DenseMapIjNS0_13DenseSetEmptyENS_12DenseMapInfoIjEENS0_12DenseSetPairIjEEEES5_E8IteratorC2ERKNS_16DenseMapIteratorIjS3_S5_S7_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir4TypeENS_8DenseMapIS3_NS0_13DenseSetEmptyENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E8IteratorC2ERKNS_16DenseMapIteratorIS3_S5_S7_S9_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir9AttributeENS_8DenseMapIS3_NS0_13DenseSetEmptyENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E8IteratorC2ERKNS_16DenseMapIteratorIS3_S5_S7_S9_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIPKN4mlir16DialectInterfaceENS_8DenseMapIS5_NS0_13DenseSetEmptyENS2_6detail30DialectInterfaceCollectionBase16InterfaceKeyInfoENS0_12DenseSetPairIS5_EEEESA_E8IteratorC2ERKNS_16DenseMapIteratorIS5_S7_SA_SC_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir8LocationENS_13SmallDenseMapIS3_NS0_13DenseSetEmptyELj4ENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E8IteratorC2ERKNS_16DenseMapIteratorIS3_S5_S7_S9_Lb0EEE Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E8IteratorC2ERKNS_16DenseMapIteratorIS3_S5_S7_S9_Lb0EEE Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E8IteratorC2ERKNS_16DenseMapIteratorIS3_S5_S7_S9_Lb0EEE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E8IteratorC2ERKNS_16DenseMapIteratorIS5_S7_S8_SA_Lb0EEE |
125 | | |
126 | 0 | ValueT &operator*() { return I->getFirst(); } Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplINS_9StringRefENS_8DenseMapIS2_NS0_13DenseSetEmptyENS_12DenseMapInfoIS2_EENS0_12DenseSetPairIS2_EEEES6_E8IteratordeEv Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E8IteratordeEv Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E8IteratordeEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E8IteratordeEv |
127 | | const ValueT &operator*() const { return I->getFirst(); } |
128 | 0 | ValueT *operator->() { return &I->getFirst(); } |
129 | | const ValueT *operator->() const { return &I->getFirst(); } |
130 | | |
131 | | Iterator& operator++() { ++I; return *this; } |
132 | | Iterator operator++(int) { auto T = *this; ++I; return T; } |
133 | 0 | bool operator==(const ConstIterator& X) const { return I == X.I; } |
134 | 0 | bool operator!=(const ConstIterator& X) const { return I != X.I; } Unexecuted instantiation: MLIRContext.cpp:_ZNK4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E8IteratorneERKNSB_13ConstIteratorE Unexecuted instantiation: MLIRContext.cpp:_ZNK4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E8IteratorneERKNSB_13ConstIteratorE Unexecuted instantiation: _ZNK4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E8IteratorneERKNSC_13ConstIteratorE |
135 | | }; |
136 | | |
137 | | class ConstIterator { |
138 | | typename MapTy::const_iterator I; |
139 | | friend class DenseSetImpl; |
140 | | friend class Iterator; |
141 | | |
142 | | public: |
143 | | using difference_type = typename MapTy::const_iterator::difference_type; |
144 | | using value_type = ValueT; |
145 | | using pointer = const value_type *; |
146 | | using reference = const value_type &; |
147 | | using iterator_category = std::forward_iterator_tag; |
148 | | |
149 | | ConstIterator() = default; |
150 | 0 | ConstIterator(const Iterator &B) : I(B.I) {} Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E13ConstIteratorC2ERKNSB_8IteratorE Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E13ConstIteratorC2ERKNSB_8IteratorE Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E13ConstIteratorC2ERKNSC_8IteratorE |
151 | 0 | ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} |
152 | | |
153 | 0 | const ValueT &operator*() const { return I->getFirst(); } |
154 | | const ValueT *operator->() const { return &I->getFirst(); } |
155 | | |
156 | | ConstIterator& operator++() { ++I; return *this; } |
157 | | ConstIterator operator++(int) { auto T = *this; ++I; return T; } |
158 | 0 | bool operator==(const ConstIterator& X) const { return I == X.I; } |
159 | | bool operator!=(const ConstIterator& X) const { return I != X.I; } |
160 | | }; |
161 | | |
162 | | using iterator = Iterator; |
163 | | using const_iterator = ConstIterator; |
164 | | |
165 | | iterator begin() { return Iterator(TheMap.begin()); } |
166 | 0 | iterator end() { return Iterator(TheMap.end()); } Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E3endEv Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E3endEv Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E3endEv |
167 | | |
168 | | const_iterator begin() const { return ConstIterator(TheMap.begin()); } |
169 | 0 | const_iterator end() const { return ConstIterator(TheMap.end()); } |
170 | | |
171 | | iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); } |
172 | | const_iterator find(const_arg_type_t<ValueT> V) const { |
173 | | return ConstIterator(TheMap.find(V)); |
174 | | } |
175 | | |
176 | | /// Alternative version of find() which allows a different, and possibly less |
177 | | /// expensive, key type. |
178 | | /// The DenseMapInfo is responsible for supplying methods |
179 | | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type |
180 | | /// used. |
181 | | template <class LookupKeyT> |
182 | 0 | iterator find_as(const LookupKeyT &Val) { |
183 | 0 | return Iterator(TheMap.find_as(Val)); |
184 | 0 | } Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E7find_asISt5tupleIJjjNS_8ArrayRefINS2_10AffineExprEEEEEEENSB_8IteratorERKT_ Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E7find_asISt5tupleIJjjNS_8ArrayRefINS2_10AffineExprEEENSE_IbEEEEEENSB_8IteratorERKT_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E7find_asINS4_9LookupKeyEEENSC_8IteratorERKT_ |
185 | | template <class LookupKeyT> |
186 | 0 | const_iterator find_as(const LookupKeyT &Val) const { |
187 | 0 | return ConstIterator(TheMap.find_as(Val)); |
188 | 0 | } |
189 | | |
190 | 0 | void erase(Iterator I) { return TheMap.erase(I.I); } |
191 | | void erase(ConstIterator CI) { return TheMap.erase(CI.I); } |
192 | | |
193 | 0 | std::pair<iterator, bool> insert(const ValueT &V) { |
194 | 0 | detail::DenseSetEmpty Empty; |
195 | 0 | return TheMap.try_emplace(V, Empty); |
196 | 0 | } Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplINS_9StringRefENS_8DenseMapIS2_NS0_13DenseSetEmptyENS_12DenseMapInfoIS2_EENS0_12DenseSetPairIS2_EEEES6_E6insertERKS2_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplINS_8ArrayRefIlEENS_13SmallDenseMapIS3_NS0_13DenseSetEmptyELj8ENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E6insertERKS3_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIjNS_8DenseMapIjNS0_13DenseSetEmptyENS_12DenseMapInfoIjEENS0_12DenseSetPairIjEEEES5_E6insertERKj Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir4TypeENS_8DenseMapIS3_NS0_13DenseSetEmptyENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E6insertERKS3_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir9AttributeENS_8DenseMapIS3_NS0_13DenseSetEmptyENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E6insertERKS3_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIPKN4mlir16DialectInterfaceENS_8DenseMapIS5_NS0_13DenseSetEmptyENS2_6detail30DialectInterfaceCollectionBase16InterfaceKeyInfoENS0_12DenseSetPairIS5_EEEESA_E6insertERKS5_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir8LocationENS_13SmallDenseMapIS3_NS0_13DenseSetEmptyELj4ENS_12DenseMapInfoIS3_EENS0_12DenseSetPairIS3_EEEES7_E6insertERKS3_ |
197 | | |
198 | | std::pair<iterator, bool> insert(ValueT &&V) { |
199 | | detail::DenseSetEmpty Empty; |
200 | | return TheMap.try_emplace(std::move(V), Empty); |
201 | | } |
202 | | |
203 | | /// Alternative version of insert that uses a different (and possibly less |
204 | | /// expensive) key type. |
205 | | template <typename LookupKeyT> |
206 | | std::pair<iterator, bool> insert_as(const ValueT &V, |
207 | | const LookupKeyT &LookupKey) { |
208 | | return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey); |
209 | | } |
210 | | template <typename LookupKeyT> |
211 | 0 | std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) { |
212 | 0 | return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey); |
213 | 0 | } Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir9AffineMapENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_116AffineMapKeyInfoENS0_12DenseSetPairIS3_EEEES7_E9insert_asISt5tupleIJjjNS_8ArrayRefINS2_10AffineExprEEEEEEESt4pairINSB_8IteratorEbEOS3_RKT_ Unexecuted instantiation: MLIRContext.cpp:_ZN4llvm6detail12DenseSetImplIN4mlir10IntegerSetENS_8DenseMapIS3_NS0_13DenseSetEmptyEN12_GLOBAL__N_117IntegerSetKeyInfoENS0_12DenseSetPairIS3_EEEES7_E9insert_asISt5tupleIJjjNS_8ArrayRefINS2_10AffineExprEEENSE_IbEEEEEESt4pairINSB_8IteratorEbEOS3_RKT_ Unexecuted instantiation: _ZN4llvm6detail12DenseSetImplIN4mlir6detail18StorageUniquerImpl13HashedStorageENS_8DenseMapIS5_NS0_13DenseSetEmptyENS4_14StorageKeyInfoENS0_12DenseSetPairIS5_EEEES8_E9insert_asINS4_9LookupKeyEEESt4pairINSC_8IteratorEbEOS5_RKT_ |
214 | | |
215 | | // Range insertion of values. |
216 | | template<typename InputIt> |
217 | | void insert(InputIt I, InputIt E) { |
218 | | for (; I != E; ++I) |
219 | | insert(*I); |
220 | | } |
221 | | }; |
222 | | |
223 | | /// Equality comparison for DenseSet. |
224 | | /// |
225 | | /// Iterates over elements of LHS confirming that each element is also a member |
226 | | /// of RHS, and that RHS contains no additional values. |
227 | | /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst |
228 | | /// case is O(N^2) (if every hash collides). |
229 | | template <typename ValueT, typename MapTy, typename ValueInfoT> |
230 | | bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS, |
231 | | const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) { |
232 | | if (LHS.size() != RHS.size()) |
233 | | return false; |
234 | | |
235 | | for (auto &E : LHS) |
236 | | if (!RHS.count(E)) |
237 | | return false; |
238 | | |
239 | | return true; |
240 | | } |
241 | | |
242 | | /// Inequality comparison for DenseSet. |
243 | | /// |
244 | | /// Equivalent to !(LHS == RHS). See operator== for performance notes. |
245 | | template <typename ValueT, typename MapTy, typename ValueInfoT> |
246 | | bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS, |
247 | | const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) { |
248 | | return !(LHS == RHS); |
249 | | } |
250 | | |
251 | | } // end namespace detail |
252 | | |
253 | | /// Implements a dense probed hash-table based set. |
254 | | template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>> |
255 | | class DenseSet : public detail::DenseSetImpl< |
256 | | ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, |
257 | | detail::DenseSetPair<ValueT>>, |
258 | | ValueInfoT> { |
259 | | using BaseT = |
260 | | detail::DenseSetImpl<ValueT, |
261 | | DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, |
262 | | detail::DenseSetPair<ValueT>>, |
263 | | ValueInfoT>; |
264 | | |
265 | | public: |
266 | | using BaseT::BaseT; |
267 | | }; |
268 | | |
269 | | /// Implements a dense probed hash-table based set with some number of buckets |
270 | | /// stored inline. |
271 | | template <typename ValueT, unsigned InlineBuckets = 4, |
272 | | typename ValueInfoT = DenseMapInfo<ValueT>> |
273 | | class SmallDenseSet |
274 | | : public detail::DenseSetImpl< |
275 | | ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, |
276 | | ValueInfoT, detail::DenseSetPair<ValueT>>, |
277 | | ValueInfoT> { |
278 | | using BaseT = detail::DenseSetImpl< |
279 | | ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, |
280 | | ValueInfoT, detail::DenseSetPair<ValueT>>, |
281 | | ValueInfoT>; |
282 | | |
283 | | public: |
284 | | using BaseT::BaseT; |
285 | | }; |
286 | | |
287 | | } // end namespace llvm |
288 | | |
289 | | #endif // LLVM_ADT_DENSESET_H |