19
19
#include " llvm/Support/AlignOf.h"
20
20
#include " llvm/Support/Compiler.h"
21
21
#include " llvm/Support/MathExtras.h"
22
+ #include " llvm/Support/ReverseIteration.h"
22
23
#include " llvm/Support/type_traits.h"
23
24
#include < algorithm>
24
25
#include < cassert>
@@ -67,18 +68,26 @@ class DenseMapBase : public DebugEpochBase {
67
68
DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true >;
68
69
69
70
inline iterator begin () {
70
- // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
71
- return empty () ? end () : iterator (getBuckets (), getBucketsEnd (), *this );
71
+ // When the map is empty, avoid the overhead of advancing/retreating past
72
+ // empty buckets.
73
+ if (empty ())
74
+ return end ();
75
+ if (shouldReverseIterate<KeyT>())
76
+ return makeIterator (getBucketsEnd () - 1 , getBuckets (), *this );
77
+ return makeIterator (getBuckets (), getBucketsEnd (), *this );
72
78
}
73
79
inline iterator end () {
74
- return iterator (getBucketsEnd (), getBucketsEnd (), *this , true );
80
+ return makeIterator (getBucketsEnd (), getBucketsEnd (), *this , true );
75
81
}
76
82
inline const_iterator begin () const {
77
- return empty () ? end ()
78
- : const_iterator (getBuckets (), getBucketsEnd (), *this );
83
+ if (empty ())
84
+ return end ();
85
+ if (shouldReverseIterate<KeyT>())
86
+ return makeConstIterator (getBucketsEnd () - 1 , getBuckets (), *this );
87
+ return makeConstIterator (getBuckets (), getBucketsEnd (), *this );
79
88
}
80
89
inline const_iterator end () const {
81
- return const_iterator (getBucketsEnd (), getBucketsEnd (), *this , true );
90
+ return makeConstIterator (getBucketsEnd (), getBucketsEnd (), *this , true );
82
91
}
83
92
84
93
LLVM_NODISCARD bool empty () const {
@@ -137,13 +146,13 @@ class DenseMapBase : public DebugEpochBase {
137
146
iterator find (const_arg_type_t <KeyT> Val) {
138
147
BucketT *TheBucket;
139
148
if (LookupBucketFor (Val, TheBucket))
140
- return iterator (TheBucket, getBucketsEnd (), *this , true );
149
+ return makeIterator (TheBucket, getBucketsEnd (), *this , true );
141
150
return end ();
142
151
}
143
152
const_iterator find (const_arg_type_t <KeyT> Val) const {
144
153
const BucketT *TheBucket;
145
154
if (LookupBucketFor (Val, TheBucket))
146
- return const_iterator (TheBucket, getBucketsEnd (), *this , true );
155
+ return makeConstIterator (TheBucket, getBucketsEnd (), *this , true );
147
156
return end ();
148
157
}
149
158
@@ -156,14 +165,14 @@ class DenseMapBase : public DebugEpochBase {
156
165
iterator find_as (const LookupKeyT &Val) {
157
166
BucketT *TheBucket;
158
167
if (LookupBucketFor (Val, TheBucket))
159
- return iterator (TheBucket, getBucketsEnd (), *this , true );
168
+ return makeIterator (TheBucket, getBucketsEnd (), *this , true );
160
169
return end ();
161
170
}
162
171
template <class LookupKeyT >
163
172
const_iterator find_as (const LookupKeyT &Val) const {
164
173
const BucketT *TheBucket;
165
174
if (LookupBucketFor (Val, TheBucket))
166
- return const_iterator (TheBucket, getBucketsEnd (), *this , true );
175
+ return makeConstIterator (TheBucket, getBucketsEnd (), *this , true );
167
176
return end ();
168
177
}
169
178
@@ -197,14 +206,16 @@ class DenseMapBase : public DebugEpochBase {
197
206
std::pair<iterator, bool > try_emplace (KeyT &&Key, Ts &&... Args) {
198
207
BucketT *TheBucket;
199
208
if (LookupBucketFor (Key, TheBucket))
200
- return std::make_pair (iterator (TheBucket, getBucketsEnd (), *this , true ),
201
- false ); // Already in map.
209
+ return std::make_pair (
210
+ makeIterator (TheBucket, getBucketsEnd (), *this , true ),
211
+ false ); // Already in map.
202
212
203
213
// Otherwise, insert the new element.
204
214
TheBucket =
205
215
InsertIntoBucket (TheBucket, std::move (Key), std::forward<Ts>(Args)...);
206
- return std::make_pair (iterator (TheBucket, getBucketsEnd (), *this , true ),
207
- true );
216
+ return std::make_pair (
217
+ makeIterator (TheBucket, getBucketsEnd (), *this , true ),
218
+ true );
208
219
}
209
220
210
221
// Inserts key,value pair into the map if the key isn't already in the map.
@@ -214,13 +225,15 @@ class DenseMapBase : public DebugEpochBase {
214
225
std::pair<iterator, bool > try_emplace (const KeyT &Key, Ts &&... Args) {
215
226
BucketT *TheBucket;
216
227
if (LookupBucketFor (Key, TheBucket))
217
- return std::make_pair (iterator (TheBucket, getBucketsEnd (), *this , true ),
218
- false ); // Already in map.
228
+ return std::make_pair (
229
+ makeIterator (TheBucket, getBucketsEnd (), *this , true ),
230
+ false ); // Already in map.
219
231
220
232
// Otherwise, insert the new element.
221
233
TheBucket = InsertIntoBucket (TheBucket, Key, std::forward<Ts>(Args)...);
222
- return std::make_pair (iterator (TheBucket, getBucketsEnd (), *this , true ),
223
- true );
234
+ return std::make_pair (
235
+ makeIterator (TheBucket, getBucketsEnd (), *this , true ),
236
+ true );
224
237
}
225
238
226
239
// / Alternate version of insert() which allows a different, and possibly
@@ -233,14 +246,16 @@ class DenseMapBase : public DebugEpochBase {
233
246
const LookupKeyT &Val) {
234
247
BucketT *TheBucket;
235
248
if (LookupBucketFor (Val, TheBucket))
236
- return std::make_pair (iterator (TheBucket, getBucketsEnd (), *this , true ),
237
- false ); // Already in map.
249
+ return std::make_pair (
250
+ makeIterator (TheBucket, getBucketsEnd (), *this , true ),
251
+ false ); // Already in map.
238
252
239
253
// Otherwise, insert the new element.
240
254
TheBucket = InsertIntoBucketWithLookup (TheBucket, std::move (KV.first ),
241
255
std::move (KV.second ), Val);
242
- return std::make_pair (iterator (TheBucket, getBucketsEnd (), *this , true ),
243
- true );
256
+ return std::make_pair (
257
+ makeIterator (TheBucket, getBucketsEnd (), *this , true ),
258
+ true );
244
259
}
245
260
246
261
// / insert - Range insertion of pairs.
@@ -411,6 +426,26 @@ class DenseMapBase : public DebugEpochBase {
411
426
}
412
427
413
428
private:
429
+ iterator makeIterator (BucketT *P, BucketT *E,
430
+ DebugEpochBase &Epoch,
431
+ bool NoAdvance=false ) {
432
+ if (shouldReverseIterate<KeyT>()) {
433
+ BucketT *B = P == getBucketsEnd () ? getBuckets () : P + 1 ;
434
+ return iterator (B, E, Epoch, NoAdvance);
435
+ }
436
+ return iterator (P, E, Epoch, NoAdvance);
437
+ }
438
+
439
+ const_iterator makeConstIterator (const BucketT *P, const BucketT *E,
440
+ const DebugEpochBase &Epoch,
441
+ const bool NoAdvance=false ) const {
442
+ if (shouldReverseIterate<KeyT>()) {
443
+ const BucketT *B = P == getBucketsEnd () ? getBuckets () : P + 1 ;
444
+ return const_iterator (B, E, Epoch, NoAdvance);
445
+ }
446
+ return const_iterator (P, E, Epoch, NoAdvance);
447
+ }
448
+
414
449
unsigned getNumEntries () const {
415
450
return static_cast <const DerivedT *>(this )->getNumEntries ();
416
451
}
@@ -1095,7 +1130,13 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
1095
1130
bool NoAdvance = false )
1096
1131
: DebugEpochBase::HandleBase(&Epoch), Ptr (Pos), End(E) {
1097
1132
assert (isHandleInSync () && " invalid construction!" );
1098
- if (!NoAdvance) AdvancePastEmptyBuckets ();
1133
+
1134
+ if (NoAdvance) return ;
1135
+ if (shouldReverseIterate<KeyT>()) {
1136
+ RetreatPastEmptyBuckets ();
1137
+ return ;
1138
+ }
1139
+ AdvancePastEmptyBuckets ();
1099
1140
}
1100
1141
1101
1142
// Converting ctor from non-const iterators to const iterators. SFINAE'd out
@@ -1109,10 +1150,14 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
1109
1150
1110
1151
reference operator *() const {
1111
1152
assert (isHandleInSync () && " invalid iterator access!" );
1153
+ if (shouldReverseIterate<KeyT>())
1154
+ return Ptr [-1 ];
1112
1155
return *Ptr ;
1113
1156
}
1114
1157
pointer operator ->() const {
1115
1158
assert (isHandleInSync () && " invalid iterator access!" );
1159
+ if (shouldReverseIterate<KeyT>())
1160
+ return &(Ptr [-1 ]);
1116
1161
return Ptr ;
1117
1162
}
1118
1163
@@ -1133,6 +1178,11 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
1133
1178
1134
1179
inline DenseMapIterator& operator ++() { // Preincrement
1135
1180
assert (isHandleInSync () && " invalid iterator access!" );
1181
+ if (shouldReverseIterate<KeyT>()) {
1182
+ --Ptr ;
1183
+ RetreatPastEmptyBuckets ();
1184
+ return *this ;
1185
+ }
1136
1186
++Ptr ;
1137
1187
AdvancePastEmptyBuckets ();
1138
1188
return *this ;
@@ -1144,13 +1194,24 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
1144
1194
1145
1195
private:
1146
1196
void AdvancePastEmptyBuckets () {
1197
+ assert (Ptr <= End);
1147
1198
const KeyT Empty = KeyInfoT::getEmptyKey ();
1148
1199
const KeyT Tombstone = KeyInfoT::getTombstoneKey ();
1149
1200
1150
1201
while (Ptr != End && (KeyInfoT::isEqual (Ptr ->getFirst (), Empty) ||
1151
1202
KeyInfoT::isEqual (Ptr ->getFirst (), Tombstone)))
1152
1203
++Ptr ;
1153
1204
}
1205
+
1206
+ void RetreatPastEmptyBuckets () {
1207
+ assert (Ptr >= End);
1208
+ const KeyT Empty = KeyInfoT::getEmptyKey ();
1209
+ const KeyT Tombstone = KeyInfoT::getTombstoneKey ();
1210
+
1211
+ while (Ptr != End && (KeyInfoT::isEqual (Ptr [-1 ].getFirst (), Empty) ||
1212
+ KeyInfoT::isEqual (Ptr [-1 ].getFirst (), Tombstone)))
1213
+ --Ptr ;
1214
+ }
1154
1215
};
1155
1216
1156
1217
template <typename KeyT, typename ValueT, typename KeyInfoT>
0 commit comments