[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

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

344

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

test/esan/Unit/hashtable.cpp

109

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

for (auto Pair : DataTable) {
}

[bruening]

lib/esan/esan_hashtable.h

344

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

[bruening]

Address reviewer requests: more tests, comment on copying.

lib/esan/esan_hashtable.h

public:
   ~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.
+  // tables or with an iterator.
   void lock();
   void unlock();
 
  private:
-  void resize();
-  static size_t hashDefault(KeyTy Key);
-
   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>* 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>* Table, int Idx);
+    friend HashTable<KeyTy, DataTy>;
+    HashTable<KeyTy, DataTy>* Table;
+    int Idx;
+    HashTable<KeyTy, DataTy>::HashEntry *Entry;
+  };
+
+  // No erase or insert iterator supported
+  iterator begin();
+  iterator end();
+
+ private:
+  void resize();
+  static size_t hashDefault(KeyTy Key);
+
   HashEntry **Table;
   u32 Capacity;
   u32 Entries;
   u32 ResizeFactor;
   BlockingMutex Mutex;
   bool ExternalLock;
   HashFuncTy HashFunc;
   FreeDataTy FreeFunc;
void HashTable<KeyTy, DataTy>::lock() {
   Mutex.Lock();
 }
 
 template <typename KeyTy, typename DataTy>
 void HashTable<KeyTy, DataTy>::unlock() {
   Mutex.Unlock();
 }
 
+//===----------------------------------------------------------------------===//
+// Iterator implementation
+//===----------------------------------------------------------------------===//
+
+template <typename KeyTy, typename DataTy>
+HashTable<KeyTy, DataTy>::iterator::iterator(HashTable<KeyTy, DataTy>* Table) :
+    Table(Table), Idx(-1), Entry(nullptr) {
+  operator++();
+}
+
+template <typename KeyTy, typename DataTy>
+HashTable<KeyTy, DataTy>::iterator::iterator(HashTable<KeyTy, DataTy>* Table,
+                                             int Idx) :
+    Table(Table), Idx(Idx), Entry(nullptr)
+{
+  CHECK(Idx >= (int)Table->Capacity); // Only used to create end().
+}
+
+template <typename KeyTy, typename DataTy>
+typename HashTable<KeyTy, DataTy>::HashPair
+HashTable<KeyTy, DataTy>::iterator::operator*() {
+  CHECK(Idx >= 0 && Idx < (int)Table->Capacity);
+  CHECK(Entry != nullptr);
+  return HashPair(Entry->Key, Entry->Payload);
+}
+
+template <typename KeyTy, typename DataTy>
+typename HashTable<KeyTy, DataTy>::iterator&
+HashTable<KeyTy, DataTy>::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>
+typename HashTable<KeyTy, DataTy>::iterator&
+HashTable<KeyTy, DataTy>::iterator::operator++(int) {
+  iterator Temp(*this);
+  operator++();
+  return Temp;
+}
+
+template <typename KeyTy, typename DataTy>
+bool HashTable<KeyTy, DataTy>::iterator::operator==(const iterator& Cmp) const {
+  return Cmp.Table == Table && Cmp.Idx == Idx && Cmp.Entry == Entry;
+}
+
+template <typename KeyTy, typename DataTy>
+bool HashTable<KeyTy, DataTy>::iterator::operator!=(const iterator& Cmp) const {
+  return Cmp.Table != Table || Cmp.Idx != Idx || Cmp.Entry != Entry;
+}
+
+template <typename KeyTy, typename DataTy>
+typename HashTable<KeyTy, DataTy>::iterator
+HashTable<KeyTy, DataTy>::begin() {
+  return iterator(this);
+}
+
+template <typename KeyTy, typename DataTy>
+typename HashTable<KeyTy, DataTy>::iterator
+HashTable<KeyTy, DataTy>::end() {
+  return iterator(this, Capacity);
+}
+
+
 } // namespace __esan

test/esan/Unit/hashtable.cpp

void freeData(MyData *Data) {
   fprintf(stderr, "Deleting %s.\n", Data->Buf);
   delete 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, 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);
   }
+  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->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->Buf, "delete-at-end") == 0);
+    ++Count;
+  }
+  DataTable.unlock();
+  assert(Count == 4);
+  assert(Count == DataTable.size());
 
   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.