contrib/compiler-rt/lib/esan/esan_hashtable.h

   1 //===-- esan_hashtable.h ----------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file is a part of EfficiencySanitizer, a family of performance tuners.
  11 //
  12 // Generic resizing hashtable.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "sanitizer_common/sanitizer_allocator_internal.h"
  16 #include "sanitizer_common/sanitizer_internal_defs.h"
  17 #include "sanitizer_common/sanitizer_mutex.h"
  18 #include <stddef.h>
  19
  20 namespace __esan {
  21
  22 //===----------------------------------------------------------------------===//
  23 // Default hash and comparison functions
  24 //===----------------------------------------------------------------------===//
  25
  26 template <typename T> struct DefaultHash {
  27   size_t operator()(const T &Key) const {
  28     return (size_t)Key;
  29   }
  30 };
  31
  32 template <typename T> struct DefaultEqual {
  33   bool operator()(const T &Key1, const T &Key2) const {
  34     return Key1 == Key2;
  35   }
  36 };
  37
  38 //===----------------------------------------------------------------------===//
  39 // HashTable declaration
  40 //===----------------------------------------------------------------------===//
  41
  42 // A simple resizing and mutex-locked hashtable.
  43 //
  44 // If the default hash functor is used, KeyTy must have an operator size_t().
  45 // If the default comparison functor is used, KeyTy must have an operator ==.
  46 //
  47 // By default all operations are internally-synchronized with a mutex, with no
  48 // synchronization for payloads once hashtable functions return.  If
  49 // ExternalLock is set to true, the caller should call the lock() and unlock()
  50 // routines around all hashtable operations and subsequent manipulation of
  51 // payloads.
  52 template <typename KeyTy, typename DataTy, bool ExternalLock = false,
  53           typename HashFuncTy = DefaultHash<KeyTy>,
  54           typename EqualFuncTy = DefaultEqual<KeyTy> >
  55 class HashTable {
  56 public:
  57   // InitialCapacity must be a power of 2.
  58   // ResizeFactor must be between 1 and 99 and indicates the
  59   // maximum percentage full that the table should ever be.
  60   HashTable(u32 InitialCapacity = 2048, u32 ResizeFactor = 70);
  61   ~HashTable();
  62   bool lookup(const KeyTy &Key, DataTy &Payload); // Const except for Mutex.
  63   bool add(const KeyTy &Key, const DataTy &Payload);
  64   bool remove(const KeyTy &Key);
  65   u32 size(); // Const except for Mutex.
  66   // If the table is internally-synchronized, this lock must not be held
  67   // while a hashtable function is called as it will deadlock: the lock
  68   // is not recursive.  This is meant for use with externally-synchronized
  69   // tables or with an iterator.
  70   void lock();
  71   void unlock();
  72
  73 private:
  74   struct HashEntry {
  75     KeyTy Key;
  76     DataTy Payload;
  77     HashEntry *Next;
  78   };
  79
  80 public:
  81   struct HashPair {
  82     HashPair(KeyTy Key, DataTy Data) : Key(Key), Data(Data) {}
  83     KeyTy Key;
  84     DataTy Data;
  85   };
  86
  87   // This iterator does not perform any synchronization.
  88   // It expects the caller to lock the table across the whole iteration.
  89   // Calling HashTable functions while using the iterator is not supported.
  90   // The iterator returns copies of the keys and data.
  91   class iterator {
  92   public:
  93     iterator(
  94         HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table);
  95     iterator(const iterator &Src) = default;
  96     iterator &operator=(const iterator &Src) = default;
  97     HashPair operator*();
  98     iterator &operator++();
  99     iterator &operator++(int);
 100     bool operator==(const iterator &Cmp) const;
 101     bool operator!=(const iterator &Cmp) const;
 102
 103   private:
 104     iterator(
 105         HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table,
 106         int Idx);
 107     friend HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>;
 108     HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table;
 109     int Idx;
 110     HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::HashEntry
 111         *Entry;
 112   };
 113
 114   // No erase or insert iterator supported
 115   iterator begin();
 116   iterator end();
 117
 118 private:
 119   void resize();
 120
 121   HashEntry **Table;
 122   u32 Capacity;
 123   u32 Entries;
 124   const u32 ResizeFactor;
 125   BlockingMutex Mutex;
 126   const HashFuncTy HashFunc;
 127   const EqualFuncTy EqualFunc;
 128 };
 129
 130 //===----------------------------------------------------------------------===//
 131 // Hashtable implementation
 132 //===----------------------------------------------------------------------===//
 133
 134 template <typename KeyTy, typename DataTy, bool ExternalLock,
 135           typename HashFuncTy, typename EqualFuncTy>
 136 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::HashTable(
 137     u32 InitialCapacity, u32 ResizeFactor)
 138     : Capacity(InitialCapacity), Entries(0), ResizeFactor(ResizeFactor),
 139       HashFunc(HashFuncTy()), EqualFunc(EqualFuncTy()) {
 140   CHECK(IsPowerOfTwo(Capacity));
 141   CHECK(ResizeFactor >= 1 && ResizeFactor <= 99);
 142   Table = (HashEntry **)InternalAlloc(Capacity * sizeof(HashEntry *));
 143   internal_memset(Table, 0, Capacity * sizeof(HashEntry *));
 144 }
 145
 146 template <typename KeyTy, typename DataTy, bool ExternalLock,
 147           typename HashFuncTy, typename EqualFuncTy>
 148 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::~HashTable() {
 149   for (u32 i = 0; i < Capacity; ++i) {
 150     HashEntry *Entry = Table[i];
 151     while (Entry != nullptr) {
 152       HashEntry *Next = Entry->Next;
 153       Entry->Payload.~DataTy();
 154       InternalFree(Entry);
 155       Entry = Next;
 156     }
 157   }
 158   InternalFree(Table);
 159 }
 160
 161 template <typename KeyTy, typename DataTy, bool ExternalLock,
 162           typename HashFuncTy, typename EqualFuncTy>
 163 u32 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::size() {
 164   u32 Res;
 165   if (!ExternalLock)
 166     Mutex.Lock();
 167   Res = Entries;
 168   if (!ExternalLock)
 169     Mutex.Unlock();
 170   return Res;
 171 }
 172
 173 template <typename KeyTy, typename DataTy, bool ExternalLock,
 174           typename HashFuncTy, typename EqualFuncTy>
 175 bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::lookup(
 176     const KeyTy &Key, DataTy &Payload) {
 177   if (!ExternalLock)
 178     Mutex.Lock();
 179   bool Found = false;
 180   size_t Hash = HashFunc(Key) % Capacity;
 181   HashEntry *Entry = Table[Hash];
 182   for (; Entry != nullptr; Entry = Entry->Next) {
 183     if (EqualFunc(Entry->Key, Key)) {
 184       Payload = Entry->Payload;
 185       Found = true;
 186       break;
 187     }
 188   }
 189   if (!ExternalLock)
 190     Mutex.Unlock();
 191   return Found;
 192 }
 193
 194 template <typename KeyTy, typename DataTy, bool ExternalLock,
 195           typename HashFuncTy, typename EqualFuncTy>
 196 void HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::resize() {
 197   if (!ExternalLock)
 198     Mutex.CheckLocked();
 199   size_t OldCapacity = Capacity;
 200   HashEntry **OldTable = Table;
 201   Capacity *= 2;
 202   Table = (HashEntry **)InternalAlloc(Capacity * sizeof(HashEntry *));
 203   internal_memset(Table, 0, Capacity * sizeof(HashEntry *));
 204   // Re-hash
 205   for (u32 i = 0; i < OldCapacity; ++i) {
 206     HashEntry *OldEntry = OldTable[i];
 207     while (OldEntry != nullptr) {
 208       HashEntry *Next = OldEntry->Next;
 209       size_t Hash = HashFunc(OldEntry->Key) % Capacity;
 210       OldEntry->Next = Table[Hash];
 211       Table[Hash] = OldEntry;
 212       OldEntry = Next;
 213     }
 214   }
 215 }
 216
 217 template <typename KeyTy, typename DataTy, bool ExternalLock,
 218           typename HashFuncTy, typename EqualFuncTy>
 219 bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::add(
 220     const KeyTy &Key, const DataTy &Payload) {
 221   if (!ExternalLock)
 222     Mutex.Lock();
 223   bool Exists = false;
 224   size_t Hash = HashFunc(Key) % Capacity;
 225   HashEntry *Entry = Table[Hash];
 226   for (; Entry != nullptr; Entry = Entry->Next) {
 227     if (EqualFunc(Entry->Key, Key)) {
 228       Exists = true;
 229       break;
 230     }
 231   }
 232   if (!Exists) {
 233     Entries++;
 234     if (Entries * 100 >= Capacity * ResizeFactor) {
 235       resize();
 236       Hash = HashFunc(Key) % Capacity;
 237     }
 238     HashEntry *Add = (HashEntry *)InternalAlloc(sizeof(*Add));
 239     Add->Key = Key;
 240     Add->Payload = Payload;
 241     Add->Next = Table[Hash];
 242     Table[Hash] = Add;
 243   }
 244   if (!ExternalLock)
 245     Mutex.Unlock();
 246   return !Exists;
 247 }
 248
 249 template <typename KeyTy, typename DataTy, bool ExternalLock,
 250           typename HashFuncTy, typename EqualFuncTy>
 251 bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::remove(
 252     const KeyTy &Key) {
 253   if (!ExternalLock)
 254     Mutex.Lock();
 255   bool Found = false;
 256   size_t Hash = HashFunc(Key) % Capacity;
 257   HashEntry *Entry = Table[Hash];
 258   HashEntry *Prev = nullptr;
 259   for (; Entry != nullptr; Prev = Entry, Entry = Entry->Next) {
 260     if (EqualFunc(Entry->Key, Key)) {
 261       Found = true;
 262       Entries--;
 263       if (Prev == nullptr)
 264         Table[Hash] = Entry->Next;
 265       else
 266         Prev->Next = Entry->Next;
 267       Entry->Payload.~DataTy();
 268       InternalFree(Entry);
 269       break;
 270     }
 271   }
 272   if (!ExternalLock)
 273     Mutex.Unlock();
 274   return Found;
 275 }
 276
 277 template <typename KeyTy, typename DataTy, bool ExternalLock,
 278           typename HashFuncTy, typename EqualFuncTy>
 279 void HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::lock() {
 280   Mutex.Lock();
 281 }
 282
 283 template <typename KeyTy, typename DataTy, bool ExternalLock,
 284           typename HashFuncTy, typename EqualFuncTy>
 285 void HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::unlock() {
 286   Mutex.Unlock();
 287 }
 288
 289 //===----------------------------------------------------------------------===//
 290 // Iterator implementation
 291 //===----------------------------------------------------------------------===//
 292
 293 template <typename KeyTy, typename DataTy, bool ExternalLock,
 294           typename HashFuncTy, typename EqualFuncTy>
 295 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 296     iterator(
 297         HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table)
 298     : Table(Table), Idx(-1), Entry(nullptr) {
 299   operator++();
 300 }
 301
 302 template <typename KeyTy, typename DataTy, bool ExternalLock,
 303           typename HashFuncTy, typename EqualFuncTy>
 304 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 305     iterator(
 306         HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy> *Table,
 307         int Idx)
 308     : Table(Table), Idx(Idx), Entry(nullptr) {
 309   CHECK(Idx >= (int)Table->Capacity); // Only used to create end().
 310 }
 311
 312 template <typename KeyTy, typename DataTy, bool ExternalLock,
 313           typename HashFuncTy, typename EqualFuncTy>
 314 typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
 315                    EqualFuncTy>::HashPair
 316     HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 317     operator*() {
 318   CHECK(Idx >= 0 && Idx < (int)Table->Capacity);
 319   CHECK(Entry != nullptr);
 320   return HashPair(Entry->Key, Entry->Payload);
 321 }
 322
 323 template <typename KeyTy, typename DataTy, bool ExternalLock,
 324           typename HashFuncTy, typename EqualFuncTy>
 325 typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
 326                    EqualFuncTy>::iterator &
 327     HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 328     operator++() {
 329   if (Entry != nullptr)
 330     Entry = Entry->Next;
 331   while (Entry == nullptr) {
 332     ++Idx;
 333     if (Idx >= (int)Table->Capacity)
 334       break; // At end().
 335     Entry = Table->Table[Idx];
 336   }
 337   return *this;
 338 }
 339
 340 template <typename KeyTy, typename DataTy, bool ExternalLock,
 341           typename HashFuncTy, typename EqualFuncTy>
 342 typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
 343                    EqualFuncTy>::iterator &
 344     HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 345     operator++(int) {
 346   iterator Temp(*this);
 347   operator++();
 348   return Temp;
 349 }
 350
 351 template <typename KeyTy, typename DataTy, bool ExternalLock,
 352           typename HashFuncTy, typename EqualFuncTy>
 353 bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 354 operator==(const iterator &Cmp) const {
 355   return Cmp.Table == Table && Cmp.Idx == Idx && Cmp.Entry == Entry;
 356 }
 357
 358 template <typename KeyTy, typename DataTy, bool ExternalLock,
 359           typename HashFuncTy, typename EqualFuncTy>
 360 bool HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::iterator::
 361 operator!=(const iterator &Cmp) const {
 362   return Cmp.Table != Table || Cmp.Idx != Idx || Cmp.Entry != Entry;
 363 }
 364
 365 template <typename KeyTy, typename DataTy, bool ExternalLock,
 366           typename HashFuncTy, typename EqualFuncTy>
 367 typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
 368                    EqualFuncTy>::iterator
 369 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::begin() {
 370   return iterator(this);
 371 }
 372
 373 template <typename KeyTy, typename DataTy, bool ExternalLock,
 374           typename HashFuncTy, typename EqualFuncTy>
 375 typename HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy,
 376                    EqualFuncTy>::iterator
 377 HashTable<KeyTy, DataTy, ExternalLock, HashFuncTy, EqualFuncTy>::end() {
 378   return iterator(this, Capacity);
 379 }
 380
 381 } // namespace __esan