Index: lib/esan/esan_hashtable.h
===================================================================
--- /dev/null
+++ lib/esan/esan_hashtable.h
@@ -0,0 +1,243 @@
+//===-- 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 {
+
+// A simple resizing and mutex-locked hashtable.
+// KeyTy must have an operator== and an operator size_t() (for hashing).
+// Pointer types will be automatically de-referenced prior to either operator==
+// or a size_t hash cast.
+// 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> class HashTable {
+ public:
+  typedef size_t (*HashFuncTy)(KeyTy Key);
+  typedef void (*FreeDataTy)(DataTy Data);
+  // 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, 
+            bool ExternalLock = false, FreeDataTy FreeFunc = nullptr,
+            HashFuncTy HashFunc = hashDefault);
+  ~HashTable();
+  bool lookup(KeyTy Key, DataTy &Payload);
+  bool add(KeyTy Key, DataTy Payload);
+  bool remove(KeyTy Key);
+  u32 size();
+  // 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.
+  void lock();
+  void unlock();
+
+ private:
+  void resize();
+  static size_t hashDefault(KeyTy Key);
+
+  struct HashEntry {
+    KeyTy Key;
+    DataTy Payload;
+    HashEntry *Next;
+  };
+
+  HashEntry **Table;
+  u32 Capacity;
+  u32 Entries;
+  u32 ResizeFactor;
+  BlockingMutex Mutex;
+  bool ExternalLock;
+  HashFuncTy HashFunc;
+  FreeDataTy FreeFunc;
+};
+
+//===----------------------------------------------------------------------===//
+// Handle both pointers and values
+//===----------------------------------------------------------------------===//
+
+template<typename T> T& deRef(T Var) {
+  // The type is not a pointer, so just use it.
+  return Var;
+}
+
+template<typename T> T& deRef(T *Var) {
+  // De-reference a pointer type so that its operator== and operator size_t()
+  // will be used.
+  return *Var;
+}
+
+//===----------------------------------------------------------------------===//
+// Hashtable implementation
+//===----------------------------------------------------------------------===//
+
+template <typename KeyTy, typename DataTy>
+HashTable<KeyTy, DataTy>::HashTable(u32 InitialCapacity, u32 ResizeFactor, 
+                                    bool ExternalLock, FreeDataTy FreeFunc,
+                                    HashFuncTy HashFunc) :
+    Capacity(InitialCapacity), Entries(0), ResizeFactor(ResizeFactor),
+    ExternalLock(ExternalLock), HashFunc(HashFunc), FreeFunc(FreeFunc) {
+  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>
+HashTable<KeyTy, DataTy>::~HashTable() {
+  for (u32 i = 0; i < Capacity; ++i) {
+    HashEntry *Entry = Table[i];
+    while (Entry != nullptr) {
+      HashEntry *Next = Entry->Next;
+      if (FreeFunc)
+        FreeFunc(Entry->Payload);
+      InternalFree(Entry);
+      Entry = Next;
+    }
+  }
+  InternalFree(Table);
+}
+
+template <typename KeyTy, typename DataTy>
+size_t HashTable<KeyTy, DataTy>::hashDefault(KeyTy Key) {
+  return (size_t)deRef(Key);
+}
+
+template <typename KeyTy, typename DataTy>
+u32 HashTable<KeyTy, DataTy>::size() {
+  u32 Res;
+  if (!ExternalLock)
+    Mutex.Lock();
+  Res = Entries;
+  if (!ExternalLock)
+    Mutex.Unlock();
+  return Res;
+}
+
+template <typename KeyTy, typename DataTy>
+bool HashTable<KeyTy, DataTy>::lookup(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 (deRef(Entry->Key) == deRef(Key)) {
+      Payload = Entry->Payload;
+      Found = true;
+      break;
+    }
+  }
+  if (!ExternalLock)
+    Mutex.Unlock();
+  return Found;
+}
+
+template <typename KeyTy, typename DataTy>
+void HashTable<KeyTy, DataTy>::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 HashTable<KeyTy, DataTy>::add(KeyTy Key, 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 (deRef(Entry->Key) == deRef(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 HashTable<KeyTy, DataTy>::remove(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 (deRef(Entry->Key) == deRef(Key)) {
+      Found = true;
+      Entries--;
+      if (Prev == nullptr)
+        Table[Hash] = Entry->Next;
+      else
+        Prev->Next = Entry->Next;
+      if (FreeFunc)
+        FreeFunc(Entry->Payload);
+      InternalFree(Entry);
+      break;
+    }
+  }
+  if (!ExternalLock)
+    Mutex.Unlock();
+  return Found;
+}
+
+template <typename KeyTy, typename DataTy>
+void HashTable<KeyTy, DataTy>::lock() {
+  Mutex.Lock();
+}
+
+template <typename KeyTy, typename DataTy>
+void HashTable<KeyTy, DataTy>::unlock() {
+  Mutex.Unlock();
+}
+
+} // namespace __esan
Index: test/esan/Unit/hashtable.cpp
===================================================================
--- /dev/null
+++ test/esan/Unit/hashtable.cpp
@@ -0,0 +1,72 @@
+// RUN: %clangxx_unit -O0 %s -o %t 2>&1
+// RUN: %env_esan_opts="record_snapshots=0" %run %t 2>&1 | FileCheck %s
+
+#include "esan/esan_hashtable.h"
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+class MyData {
+ public:
+  MyData(const char *Str) { Buf = strdup(Str); }
+  ~MyData() { free(Buf); }
+  bool operator==(MyData &Cmp) { return strcmp(Buf, Cmp.Buf) == 0; }
+  operator size_t() const {
+    size_t Res = 0;
+    for (int i = 0; i < strlen(Buf); ++i)
+      Res ^= Buf[i];
+    return Res;
+  }
+  char *Buf;
+};
+
+void freeData(MyData *Data) {
+  fprintf(stderr, "Deleting %s.\n", Data->Buf);
+  delete Data;
+}
+
+int main()
+{
+  __esan::HashTable<int, int> IntTable;
+  assert(IntTable.size() == 0);
+  bool Added = IntTable.add(4, 42);
+  assert(Added);
+  assert(!IntTable.add(4, 42));
+  assert(IntTable.size() == 1);
+  int Value;
+  bool Found = IntTable.lookup(4, Value);
+  assert(Found && Value == 42);
+  assert(!IntTable.remove(5));
+  assert(IntTable.remove(4));
+
+  __esan::HashTable<int, MyData*> DataTable(4, 50, false, freeData);
+  MyData *NewData = new MyData("mystring");
+  Added = DataTable.add(4, NewData);
+  assert(Added);
+  MyData *FoundData;
+  Found = DataTable.lookup(4, FoundData);
+  assert(Found && strcmp(FoundData->Buf, "mystring") == 0);
+  assert(!DataTable.remove(5));
+  assert(DataTable.remove(4));
+  // Test resize.
+  for (int i = 0; i < 4; ++i) {
+    NewData = new MyData("delete-at-end");
+    Added = DataTable.add(i+1, NewData);
+    assert(Added);
+    assert(!DataTable.add(i+1, NewData));
+  }
+  for (int i = 0; i < 4; ++i) {
+    Found = DataTable.lookup(i+1, FoundData);
+    assert(Found && strcmp(FoundData->Buf, "delete-at-end") == 0);
+  }
+
+  fprintf(stderr, "All checks passed.\n");
+  return 0;
+}
+// CHECK:      Deleting mystring.
+// CHECK-NEXT: All checks passed.
+// CHECK-NEXT: Deleting delete-at-end.
+// CHECK-NEXT: Deleting delete-at-end.
+// CHECK-NEXT: Deleting delete-at-end.
+// CHECK-NEXT: Deleting delete-at-end.