llunak updated this revision to Diff 431216.
llunak added a comment.
- add a function for selecting a pool in ConstString
- use uint32_t for hash in StringMap API
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D122974/new/
https://reviews.llvm.org/D122974
Files:
lldb/source/Utility/ConstString.cpp
llvm/include/llvm/ADT/StringMap.h
llvm/lib/Support/StringMap.cpp
Index: llvm/lib/Support/StringMap.cpp
===================================================================
--- llvm/lib/Support/StringMap.cpp
+++ llvm/lib/Support/StringMap.cpp
@@ -11,7 +11,6 @@
//===----------------------------------------------------------------------===//
#include "llvm/ADT/StringMap.h"
-#include "llvm/Support/DJB.h"
#include "llvm/Support/MathExtras.h"
using namespace llvm;
@@ -80,11 +79,14 @@
/// specified bucket will be non-null. Otherwise, it will be null. In either
/// case, the FullHashValue field of the bucket will be set to the hash value
/// of the string.
-unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
+unsigned StringMapImpl::LookupBucketFor(StringRef Name,
+ uint32_t FullHashValue) {
+#ifdef EXPENSIVE_CHECKS
+ assert(FullHashValue == hash(Name));
+#endif
// Hash table unallocated so far?
if (NumBuckets == 0)
init(16);
- unsigned FullHashValue = djbHash(Name, 0);
unsigned BucketNo = FullHashValue & (NumBuckets - 1);
unsigned *HashTable = getHashTable(TheTable, NumBuckets);
@@ -136,10 +138,12 @@
/// FindKey - Look up the bucket that contains the specified key. If it exists
/// in the map, return the bucket number of the key. Otherwise return -1.
/// This does not modify the map.
-int StringMapImpl::FindKey(StringRef Key) const {
+int StringMapImpl::FindKey(StringRef Key, uint32_t FullHashValue) const {
if (NumBuckets == 0)
return -1; // Really empty table?
- unsigned FullHashValue = djbHash(Key, 0);
+#ifdef EXPENSIVE_CHECKS
+ assert(FullHashValue == hash(Key));
+#endif
unsigned BucketNo = FullHashValue & (NumBuckets - 1);
unsigned *HashTable = getHashTable(TheTable, NumBuckets);
Index: llvm/include/llvm/ADT/StringMap.h
===================================================================
--- llvm/include/llvm/ADT/StringMap.h
+++ llvm/include/llvm/ADT/StringMap.h
@@ -17,6 +17,7 @@
#include "llvm/ADT/StringMapEntry.h"
#include "llvm/ADT/iterator.h"
#include "llvm/Support/AllocatorBase.h"
+#include "llvm/Support/DJB.h"
#include "llvm/Support/PointerLikeTypeTraits.h"
#include <initializer_list>
#include <iterator>
@@ -60,12 +61,20 @@
/// specified bucket will be non-null. Otherwise, it will be null. In either
/// case, the FullHashValue field of the bucket will be set to the hash value
/// of the string.
- unsigned LookupBucketFor(StringRef Key);
+ unsigned LookupBucketFor(StringRef Key) {
+ return LookupBucketFor(Key, hash(Key));
+ }
+
+ /// Overload that explicitly takes precomputed hash(Key).
+ unsigned LookupBucketFor(StringRef Key, uint32_t FullHashValue);
/// FindKey - Look up the bucket that contains the specified key. If it exists
/// in the map, return the bucket number of the key. Otherwise return -1.
/// This does not modify the map.
- int FindKey(StringRef Key) const;
+ int FindKey(StringRef Key) const { return FindKey(Key, hash(Key)); }
+
+ /// Overload that explicitly takes precomputed hash(Key).
+ int FindKey(StringRef Key, uint32_t FullHashValue) const;
/// RemoveKey - Remove the specified StringMapEntry from the table, but do not
/// delete it. This aborts if the value isn't in the table.
@@ -94,6 +103,8 @@
bool empty() const { return NumItems == 0; }
unsigned size() const { return NumItems; }
+ static uint32_t hash(StringRef Key) { return llvm::djbHash(Key, 0); }
+
void swap(StringMapImpl &Other) {
std::swap(TheTable, Other.TheTable);
std::swap(NumBuckets, Other.NumBuckets);
@@ -215,15 +226,19 @@
StringMapKeyIterator<ValueTy>(end()));
}
- iterator find(StringRef Key) {
- int Bucket = FindKey(Key);
+ iterator find(StringRef Key) { return find(Key, hash(Key)); }
+
+ iterator find(StringRef Key, uint32_t FullHashValue) {
+ int Bucket = FindKey(Key, FullHashValue);
if (Bucket == -1)
return end();
return iterator(TheTable + Bucket, true);
}
- const_iterator find(StringRef Key) const {
- int Bucket = FindKey(Key);
+ const_iterator find(StringRef Key) const { return find(Key, hash(Key)); }
+
+ const_iterator find(StringRef Key, uint32_t FullHashValue) const {
+ int Bucket = FindKey(Key, FullHashValue);
if (Bucket == -1)
return end();
return const_iterator(TheTable + Bucket, true);
@@ -294,7 +309,13 @@
/// if and only if the insertion takes place, and the iterator component of
/// the pair points to the element with key equivalent to the key of the pair.
std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
- return try_emplace(KV.first, std::move(KV.second));
+ return try_emplace_with_hash(KV.first, hash(KV.first),
+ std::move(KV.second));
+ }
+
+ std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV,
+ uint32_t FullHashValue) {
+ return try_emplace_with_hash(KV.first, FullHashValue, std::move(KV.second));
}
/// Inserts elements from range [first, last). If multiple elements in the
@@ -327,8 +348,15 @@
/// if and only if the insertion takes place, and the iterator component of
/// the pair points to the element with key equivalent to the key of the pair.
template <typename... ArgsTy>
- std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
- unsigned BucketNo = LookupBucketFor(Key);
+ std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&...Args) {
+ return try_emplace_with_hash(Key, hash(Key), std::forward<ArgsTy>(Args)...);
+ }
+
+ template <typename... ArgsTy>
+ std::pair<iterator, bool> try_emplace_with_hash(StringRef Key,
+ uint32_t FullHashValue,
+ ArgsTy &&...Args) {
+ unsigned BucketNo = LookupBucketFor(Key, FullHashValue);
StringMapEntryBase *&Bucket = TheTable[BucketNo];
if (Bucket && Bucket != getTombstoneVal())
return std::make_pair(iterator(TheTable + BucketNo, false),
Index: lldb/source/Utility/ConstString.cpp
===================================================================
--- lldb/source/Utility/ConstString.cpp
+++ lldb/source/Utility/ConstString.cpp
@@ -77,10 +77,10 @@
return 0;
}
- StringPoolValueType GetMangledCounterpart(const char *ccstr) const {
+ StringPoolValueType GetMangledCounterpart(const char *ccstr) {
if (ccstr != nullptr) {
- const uint8_t h = hash(llvm::StringRef(ccstr));
- llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
+ const PoolEntry &pool = selectPool(llvm::StringRef(ccstr));
+ llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
return GetStringMapEntryFromKeyData(ccstr).getValue();
}
return nullptr;
@@ -100,19 +100,20 @@
const char *GetConstCStringWithStringRef(const llvm::StringRef &string_ref) {
if (string_ref.data()) {
- const uint8_t h = hash(string_ref);
+ const uint32_t string_hash = StringPool::hash(string_ref);
+ PoolEntry &pool = selectPool(string_hash);
{
- llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
- auto it = m_string_pools[h].m_string_map.find(string_ref);
- if (it != m_string_pools[h].m_string_map.end())
+ llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
+ auto it = pool.m_string_map.find(string_ref, string_hash);
+ if (it != pool.m_string_map.end())
return it->getKeyData();
}
- llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+ llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);
StringPoolEntryType &entry =
- *m_string_pools[h]
- .m_string_map.insert(std::make_pair(string_ref, nullptr))
+ *pool.m_string_map
+ .insert(std::make_pair(string_ref, nullptr), string_hash)
.first;
return entry.getKeyData();
}
@@ -125,12 +126,14 @@
const char *demangled_ccstr = nullptr;
{
- const uint8_t h = hash(demangled);
- llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+ const uint32_t demangled_hash = StringPool::hash(demangled);
+ PoolEntry &pool = selectPool(demangled_hash);
+ llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);
// Make or update string pool entry with the mangled counterpart
- StringPool &map = m_string_pools[h].m_string_map;
- StringPoolEntryType &entry = *map.try_emplace(demangled).first;
+ StringPool &map = pool.m_string_map;
+ StringPoolEntryType &entry =
+ *map.try_emplace_with_hash(demangled, demangled_hash).first;
entry.second = mangled_ccstr;
@@ -141,8 +144,8 @@
{
// Now assign the demangled const string as the counterpart of the
// mangled const string...
- const uint8_t h = hash(llvm::StringRef(mangled_ccstr));
- llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+ PoolEntry &pool = selectPool(llvm::StringRef(mangled_ccstr));
+ llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);
GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);
}
@@ -171,11 +174,6 @@
}
protected:
- uint8_t hash(const llvm::StringRef &s) const {
- uint32_t h = llvm::djbHash(s);
- return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
- }
-
struct PoolEntry {
mutable llvm::sys::SmartRWMutex<false> m_mutex;
StringPool m_string_map;
@@ -183,6 +181,14 @@
};
std::array<PoolEntry, 256> m_string_pools;
+
+ PoolEntry &selectPool(const llvm::StringRef &s) {
+ return selectPool(StringPool::hash(s));
+ }
+
+ PoolEntry &selectPool(uint32_t h) {
+ return m_string_pools[((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff];
+ }
};
// Frameworks and dylibs aren't supposed to have global C++ initializers so we
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
