compiler-rt/lib/esan/esan_hashtable.h

//===-- 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