[ADT] Simplify StringMapIterBase (NFC) #156392
Merged
+11
−15
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
In open-adressing hash tables, begin() needs to advance to the first valid element. We don't need to do the same for any other operations like end(), find(), and try_emplace(). The problem is that the constructor of StringMapIterBase says: bool NoAdvance = false This increases the burden on the callers because most places need to pass true for NoAdvance, defeating the benefit of the default parameter. This patch fixes the problem by changing the name and default to: bool Advance = false and adjusting callers. Again, begin() is the only caller that specifies this parameter. This patch fixes a "latent bug" where try_emplace() was requesting advancing even on a successful insertion. I say "latent" because the request is a no-op on success.
|
@llvm/pr-subscribers-llvm-adt Author: Kazu Hirata (kazutakahirata) ChangesIn open-adressing hash tables, begin() needs to advance to the first The problem is that the constructor of StringMapIterBase says: bool NoAdvance = false This increases the burden on the callers because most places need to This patch fixes the problem by changing the name and default to: bool Advance = false and adjusting callers. Again, begin() is the only caller that This patch fixes a "latent bug" where try_emplace() was requesting Full diff: https://github.com/llvm/llvm-project/pull/156392.diff 1 Files Affected:
diff --git a/llvm/include/llvm/ADT/StringMap.h b/llvm/include/llvm/ADT/StringMap.h
index ac66444968f8e..2c146fbf08df1 100644
--- a/llvm/include/llvm/ADT/StringMap.h
+++ b/llvm/include/llvm/ADT/StringMap.h
@@ -220,14 +220,12 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
using const_iterator = StringMapIterBase<ValueTy, true>;
using iterator = StringMapIterBase<ValueTy, false>;
- iterator begin() { return iterator(TheTable, NumBuckets == 0); }
- iterator end() { return iterator(TheTable + NumBuckets, true); }
+ iterator begin() { return iterator(TheTable, NumBuckets != 0); }
+ iterator end() { return iterator(TheTable + NumBuckets); }
const_iterator begin() const {
- return const_iterator(TheTable, NumBuckets == 0);
- }
- const_iterator end() const {
- return const_iterator(TheTable + NumBuckets, true);
+ return const_iterator(TheTable, NumBuckets != 0);
}
+ const_iterator end() const { return const_iterator(TheTable + NumBuckets); }
iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
return make_range(StringMapKeyIterator<ValueTy>(begin()),
@@ -240,7 +238,7 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
int Bucket = FindKey(Key, FullHashValue);
if (Bucket == -1)
return end();
- return iterator(TheTable + Bucket, true);
+ return iterator(TheTable + Bucket);
}
const_iterator find(StringRef Key) const { return find(Key, hash(Key)); }
@@ -249,7 +247,7 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
int Bucket = FindKey(Key, FullHashValue);
if (Bucket == -1)
return end();
- return const_iterator(TheTable + Bucket, true);
+ return const_iterator(TheTable + Bucket);
}
/// lookup - Return the entry for the specified key, or a default
@@ -380,8 +378,7 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
unsigned BucketNo = LookupBucketFor(Key, FullHashValue);
StringMapEntryBase *&Bucket = TheTable[BucketNo];
if (Bucket && Bucket != getTombstoneVal())
- return {iterator(TheTable + BucketNo, false),
- false}; // Already exists in map.
+ return {iterator(TheTable + BucketNo), false}; // Already exists in map.
if (Bucket == getTombstoneVal())
--NumTombstones;
@@ -391,7 +388,7 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
assert(NumItems + NumTombstones <= NumBuckets);
BucketNo = RehashTable(BucketNo);
- return {iterator(TheTable + BucketNo, false), true};
+ return {iterator(TheTable + BucketNo), true};
}
// clear - Empties out the StringMap
@@ -444,10 +441,9 @@ template <typename ValueTy, bool IsConst> class StringMapIterBase {
StringMapIterBase() = default;
- explicit StringMapIterBase(StringMapEntryBase **Bucket,
- bool NoAdvance = false)
+ explicit StringMapIterBase(StringMapEntryBase **Bucket, bool Advance = false)
: Ptr(Bucket) {
- if (!NoAdvance)
+ if (Advance)
AdvancePastEmptyBuckets();
}
@@ -469,7 +465,7 @@ template <typename ValueTy, bool IsConst> class StringMapIterBase {
template <bool ToConst,
typename = typename std::enable_if<!IsConst && ToConst>::type>
operator StringMapIterBase<ValueTy, ToConst>() const {
- return StringMapIterBase<ValueTy, ToConst>(Ptr, true);
+ return StringMapIterBase<ValueTy, ToConst>(Ptr);
}
friend bool operator==(const StringMapIterBase &LHS,
|
kuhar
approved these changes
Sep 2, 2025
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
In open-adressing hash tables, begin() needs to advance to the first
valid element. We don't need to do the same for any other operations
like end(), find(), and try_emplace().
The problem is that the constructor of StringMapIterBase says:
bool NoAdvance = false
This increases the burden on the callers because most places need to
pass true for NoAdvance, defeating the benefit of the default
parameter.
This patch fixes the problem by changing the name and default to:
bool Advance = false
and adjusting callers. Again, begin() is the only caller that
specifies this parameter.
This patch fixes a "latent bug" where try_emplace() was requesting
advancing even on a successful insertion. I say "latent" because the
request is a no-op on success.