summaryrefslogtreecommitdiff
path: root/lib/esan/esan_hashtable.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/esan/esan_hashtable.h')
-rw-r--r--lib/esan/esan_hashtable.h381
1 files changed, 381 insertions, 0 deletions
diff --git a/lib/esan/esan_hashtable.h b/lib/esan/esan_hashtable.h
new file mode 100644
index 0000000000000..7bd8297404003
--- /dev/null
+++ b/lib/esan/esan_hashtable.h
@@ -0,0 +1,381 @@
+//===-- esan_hashtable.h ----------------------------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of EfficiencySanitizer, a family of performance tuners.
+//
+// Generic resizing hashtable.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common/sanitizer_allocator_internal.h"
+#include "sanitizer_common/sanitizer_internal_defs.h"
+#include "sanitizer_common/sanitizer_mutex.h"
+#include <stddef.h>
+
+namespace __esan {
+
+//===----------------------------------------------------------------------===//
+// Default hash and comparison functions
+//===----------------------------------------------------------------------===//
+
+template <typename T> struct DefaultHash {
+ size_t operator()(const T &Key) const {
+ return (size_t)Key;
+ }
+};
+
+template <typename T> struct DefaultEqual {
+ bool operator()(const T &Key1, const T &Key2) const {
+ return Key1 == Key2;
+ }
+};
+
+//===----------------------------------------------------------------------===//
+// HashTable declaration
+//===----------------------------------------------------------------------===//
+
+// A simple resizing and mutex-locked hashtable.
+//
+// If the default hash functor is used, KeyTy must have an operator size_t().
+// If the default comparison functor is used, KeyTy must have an operator ==.
+//
+// By default all operations are internally-synchronized with a mutex, with no
+// synchronization for payloads once hashtable functions return. If
+// ExternalLock is set to true, the caller should call the lock() and unlock()
+// routines around all hashtable operations and subsequent manipulation of
+// payloads.
+template <typename KeyTy, typename DataTy, bool ExternalLock = false,
+ typename HashFuncTy = DefaultHash<KeyTy>,
+ typename EqualFuncTy = DefaultEqual<KeyTy> >
+class HashTable {
+public:
+ // InitialCapacity must be a power of 2.
+ // ResizeFactor must be between 1 and 99 and indicates the
+ // maximum percentage full that the table should ever be.
+ HashTable(u32 InitialCapacity = 2048, u32 ResizeFactor = 70);
+ ~HashTable();
+ bool lookup(const KeyTy &Key, DataTy &Payload); // Const except for Mutex.
+ bool add(const KeyTy &Key, const DataTy &Payload);
+ bool remove(const KeyTy &Key);
+ u32 size(); // Const except for Mutex.
+ // If the table is internally-synchronized, this lock must not be held
+ // while a hashtable function is called as it will deadlock: the lock
+ // is not recursive. This is meant for use with externally-synchronized
+ // tables or with an iterator.
+ void lock();
+ void unlock();
+
+private:
+ struct HashEntry {
+ KeyTy Key;
+ DataTy Payload;
+ HashEntry *Next;
+ };
+
+public:
+ struct HashPair {
+ HashPair(KeyTy Key, DataTy Data) : Key(Key), Data(Data) {}
+ KeyTy Key;
+ DataTy Data;
+ };
+
+ // This iterator does not perform any synchronization.
+ // It expects the caller to lock the table across the whole iteration.
+ // Calling HashTable functions while using the iterator is not supported.
+ // The iterator returns copies of the keys and data.
+ class iterator {
+ public:
+ iterator(
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table);
+ iterator(const iterator &Src) = default;
+ iterator &operator=(const iterator &Src) = default;
+ HashPair operator*();
+ iterator &operator++();
+ iterator &operator++(int);
+ bool operator==(const iterator &Cmp) const;
+ bool operator!=(const iterator &Cmp) const;
+
+ private:
+ iterator(
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table,
+ int Idx);
+ friend HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>;
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table;
+ int Idx;
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::HashEntry
+ *Entry;
+ };
+
+ // No erase or insert iterator supported
+ iterator begin();
+ iterator end();
+
+private:
+ void resize();
+
+ HashEntry **Table;
+ u32 Capacity;
+ u32 Entries;
+ const u32 ResizeFactor;
+ BlockingMutex Mutex;
+ const HashFuncTy HashFunc;
+ const EqualFuncTy EqualFunc;
+};
+
+//===----------------------------------------------------------------------===//
+// Hashtable implementation
+//===----------------------------------------------------------------------===//
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::HashTable(
+ u32 InitialCapacity, u32 ResizeFactor)
+ : Capacity(InitialCapacity), Entries(0), ResizeFactor(ResizeFactor),
+ HashFunc(HashFuncTy()), EqualFunc(EqualFuncTy()) {
+ CHECK(IsPowerOfTwo(Capacity));
+ CHECK(ResizeFactor >= 1 && ResizeFactor <= 99);
+ Table = (HashEntry **)InternalAlloc(Capacity * sizeof(HashEntry *));
+ internal_memset(Table, 0, Capacity * sizeof(HashEntry *));
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::~HashTable() {
+ for (u32 i = 0; i < Capacity; ++i) {
+ HashEntry *Entry = Table[i];
+ while (Entry != nullptr) {
+ HashEntry *Next = Entry->Next;
+ Entry->Payload.~DataTy();
+ InternalFree(Entry);
+ Entry = Next;
+ }
+ }
+ InternalFree(Table);
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+u32 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::size() {
+ u32 Res;
+ if (!ExternalLock)
+ Mutex.Lock();
+ Res = Entries;
+ if (!ExternalLock)
+ Mutex.Unlock();
+ return Res;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::lookup(
+ const KeyTy &Key, DataTy &Payload) {
+ if (!ExternalLock)
+ Mutex.Lock();
+ bool Found = false;
+ size_t Hash = HashFunc(Key) % Capacity;
+ HashEntry *Entry = Table[Hash];
+ for (; Entry != nullptr; Entry = Entry->Next) {
+ if (EqualFunc(Entry->Key, Key)) {
+ Payload = Entry->Payload;
+ Found = true;
+ break;
+ }
+ }
+ if (!ExternalLock)
+ Mutex.Unlock();
+ return Found;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+void HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::resize() {
+ if (!ExternalLock)
+ Mutex.CheckLocked();
+ size_t OldCapacity = Capacity;
+ HashEntry **OldTable = Table;
+ Capacity *= 2;
+ Table = (HashEntry **)InternalAlloc(Capacity * sizeof(HashEntry *));
+ internal_memset(Table, 0, Capacity * sizeof(HashEntry *));
+ // Re-hash
+ for (u32 i = 0; i < OldCapacity; ++i) {
+ HashEntry *OldEntry = OldTable[i];
+ while (OldEntry != nullptr) {
+ HashEntry *Next = OldEntry->Next;
+ size_t Hash = HashFunc(OldEntry->Key) % Capacity;
+ OldEntry->Next = Table[Hash];
+ Table[Hash] = OldEntry;
+ OldEntry = Next;
+ }
+ }
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::add(
+ const KeyTy &Key, const DataTy &Payload) {
+ if (!ExternalLock)
+ Mutex.Lock();
+ bool Exists = false;
+ size_t Hash = HashFunc(Key) % Capacity;
+ HashEntry *Entry = Table[Hash];
+ for (; Entry != nullptr; Entry = Entry->Next) {
+ if (EqualFunc(Entry->Key, Key)) {
+ Exists = true;
+ break;
+ }
+ }
+ if (!Exists) {
+ Entries++;
+ if (Entries * 100 >= Capacity * ResizeFactor) {
+ resize();
+ Hash = HashFunc(Key) % Capacity;
+ }
+ HashEntry *Add = (HashEntry *)InternalAlloc(sizeof(*Add));
+ Add->Key = Key;
+ Add->Payload = Payload;
+ Add->Next = Table[Hash];
+ Table[Hash] = Add;
+ }
+ if (!ExternalLock)
+ Mutex.Unlock();
+ return !Exists;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::remove(
+ const KeyTy &Key) {
+ if (!ExternalLock)
+ Mutex.Lock();
+ bool Found = false;
+ size_t Hash = HashFunc(Key) % Capacity;
+ HashEntry *Entry = Table[Hash];
+ HashEntry *Prev = nullptr;
+ for (; Entry != nullptr; Prev = Entry, Entry = Entry->Next) {
+ if (EqualFunc(Entry->Key, Key)) {
+ Found = true;
+ Entries--;
+ if (Prev == nullptr)
+ Table[Hash] = Entry->Next;
+ else
+ Prev->Next = Entry->Next;
+ Entry->Payload.~DataTy();
+ InternalFree(Entry);
+ break;
+ }
+ }
+ if (!ExternalLock)
+ Mutex.Unlock();
+ return Found;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+void HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::lock() {
+ Mutex.Lock();
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+void HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::unlock() {
+ Mutex.Unlock();
+}
+
+//===----------------------------------------------------------------------===//
+// Iterator implementation
+//===----------------------------------------------------------------------===//
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+ iterator(
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table)
+ : Table(Table), Idx(-1), Entry(nullptr) {
+ operator++();
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+ iterator(
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table,
+ int Idx)
+ : Table(Table), Idx(Idx), Entry(nullptr) {
+ CHECK(Idx >= (int)Table->Capacity); // Only used to create end().
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
+ EqualFuncTy>::HashPair
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+ operator*() {
+ CHECK(Idx >= 0 && Idx < (int)Table->Capacity);
+ CHECK(Entry != nullptr);
+ return HashPair(Entry->Key, Entry->Payload);
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
+ EqualFuncTy>::iterator &
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+ operator++() {
+ if (Entry != nullptr)
+ Entry = Entry->Next;
+ while (Entry == nullptr) {
+ ++Idx;
+ if (Idx >= (int)Table->Capacity)
+ break; // At end().
+ Entry = Table->Table[Idx];
+ }
+ return *this;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
+ EqualFuncTy>::iterator &
+ HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+ operator++(int) {
+ iterator Temp(*this);
+ operator++();
+ return Temp;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+operator==(const iterator &Cmp) const {
+ return Cmp.Table == Table && Cmp.Idx == Idx && Cmp.Entry == Entry;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
+operator!=(const iterator &Cmp) const {
+ return Cmp.Table != Table || Cmp.Idx != Idx || Cmp.Entry != Entry;
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
+ EqualFuncTy>::iterator
+HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::begin() {
+ return iterator(this);
+}
+
+template <typename KeyTy, typename DataTy, bool ExternalLock,
+ typename HashFuncTy, typename EqualFuncTy>
+typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
+ EqualFuncTy>::iterator
+HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::end() {
+ return iterator(this, Capacity);
+}
+
+} // namespace __esan
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-02 00:51:29 +0000