[esan] Add iterator to esan's generic hashtable

[bruening]

Summary

Adds simple iterator support to the esan hashtable.

[aizatsky]

lib/esan/esan_hashtable.h

70 ↗

(On Diff #65081)

Specify that iterator copies data, so it would be inefficient for non-primitive types.

343 ↗

(On Diff #65081)

I'm not sure that this iterator is correct when table is empty. Could you add a test please?

test/esan/Unit/hashtable.cpp

86 ↗

(On Diff #65081)

Please also add a small test to make sure it works with

for (auto Pair : DataTable) {
}

[bruening]

lib/esan/esan_hashtable.h

343 ↗

(On Diff #65081)

I believe it should work...and it works in my added test.

[bruening]

Address reviewer requests: more tests, comment on copying.

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

public:
   ~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.
+  // tables or with an iterator.
   void lock();
   void unlock();
 
 private:
-  void resize();
-
   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;
 };

 }
 
 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

compiler-rt/trunk/test/esan/Unit/hashtable.cpp

struct MyDataPayload {
   operator size_t() const { return (size_t)*Data; }
   MyData *Data;
 };
 
 int main()
 {
   __esan::HashTable<int, int> IntTable;
   assert(IntTable.size() == 0);
+
+  // Test iteration on an empty table.
+  int Count = 0;
+  for (auto Iter = IntTable.begin(); Iter != IntTable.end();
+       ++Iter, ++Count) {
+    // Empty.
+  }
+  assert(Count == 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);
+
+  // Test iterator.
+  IntTable.lock();
+  for (auto Iter = IntTable.begin(); Iter != IntTable.end();
+       ++Iter, ++Count) {
+    assert((*Iter).Key == 4);
+    assert((*Iter).Data == 42);
+  }
+  IntTable.unlock();
+  assert(Count == 1);
+  assert(Count == IntTable.size());
   assert(!IntTable.remove(5));
   assert(IntTable.remove(4));
 
+  // Test a more complex payload.
   __esan::HashTable<int, MyDataPayload> DataTable(4);
   MyDataPayload NewData(new MyData("mystring"));
   Added = DataTable.add(4, NewData);
   assert(Added);
   MyDataPayload FoundData;
   Found = DataTable.lookup(4, FoundData);
   assert(Found && strcmp(FoundData.Data->Buf, "mystring") == 0);
   assert(!DataTable.remove(5));
   assert(DataTable.remove(4));
   // Test resize.
   for (int i = 0; i < 4; ++i) {
     MyDataPayload MoreData(new MyData("delete-at-end"));
     Added = DataTable.add(i+1, MoreData);
     assert(Added);
     assert(!DataTable.add(i+1, MoreData));
   }
   for (int i = 0; i < 4; ++i) {
     Found = DataTable.lookup(i+1, FoundData);
     assert(Found && strcmp(FoundData.Data->Buf, "delete-at-end") == 0);
   }
+  DataTable.lock();
+  Count = 0;
+  for (auto Iter = DataTable.begin(); Iter != DataTable.end();
+       ++Iter, ++Count) {
+    int Key = (*Iter).Key;
+    FoundData = (*Iter).Data;
+    assert(Key >= 1 && Key <= 4);
+    assert(strcmp(FoundData.Data->Buf, "delete-at-end") == 0);
+  }
+  DataTable.unlock();
+  assert(Count == 4);
+  assert(Count == DataTable.size());
+
+  // Ensure the iterator supports a range-based for loop.
+  DataTable.lock();
+  Count = 0;
+  for (auto Pair : DataTable) {
+    assert(Pair.Key >= 1 && Pair.Key <= 4);
+    assert(strcmp(Pair.Data.Data->Buf, "delete-at-end") == 0);
+    ++Count;
+  }
+  DataTable.unlock();
+  assert(Count == 4);
+  assert(Count == DataTable.size());
 
   // Test payload freeing via smart pointer wrapper.
   __esan::HashTable<MyDataPayload, MyDataPayload, true> DataKeyTable;
   MyDataPayload DataA(new MyData("string AB"));
   DataKeyTable.lock();
   Added = DataKeyTable.add(DataA, DataA);
   assert(Added);
   Found = DataKeyTable.lookup(DataA, FoundData);