[WIP] Add InsertionOrderSet, with constant-time insertion and removal.

[efriedma]

Summary

This is useful in places which need a consistent iteration order like a SetVector, but also need constant-time removal. @efriedma quickly hacked this together as a proof of concept for D48372; there's a lot of room for improvement.

[george.burgess.iv]

Thinking out loud: I wonder how often people ask for insertion order but only actually care about having a consistent order.

If the primary use-case we care about is "I inserted X, Y, Z, A, and removed Z. I expect to iterate over X, Y, and A in some order that's consistent across reruns regardless of what these hashed to/etc, but I don't actually care that X comes before Y and A," then we can probably be clever to save some space:

void remove(ValueT value) {
  auto MapFind = Map.find(value);
  if (MapFind != Map.end()) {
    size_t Index = MapFind->second;
    Map.erase(MapFind);
    if (Index != size() - 1) {
      swap(Vec[Index], Vec.back());
      Map.find(Vec[Index])->second = I;
    }
    Vec.pop_back();
  }
}

...Which would also let us get rid of the Optional.

[efriedma]

I could have used DenseMapInfo::getTombstoneKey() here instead of Optional, I think. But making remove() swap might still be worthwhile; it would give random-access iteration, and more flexibility with the keys (with a different underlying hashtable, we could allow keys which don't have tombstones).

[labrinea]

include/llvm/ADT/InsertionOrderSet.h

63

Since the iterator does not allow random access of the underlying vector we might want something like this:

iterator at(size_t idx) {
  return MakeSetIterator(Vec.begin()+idx);
}

[labrinea]

Another thing to consider maybe is the complexity of iteration over the vector. Imagine the case where we insert N elements and we erase M with M being almost the size of N. The iteration will be O(N) and not O(N-M).

[efriedma]

Imagine the case where we insert N elements and we erase M with M being almost the size of N

This is essentially the issue I noted with the comment: "It doesn't clean out dead entries in the vector when the set is rehashed". I mean, I guess it's not exactly the same thing, but I think we end up rehashing in almost all the scenarios where this would matter, and we could add a shrink_to_fit method for other cases.

[labrinea]

I've accidentally edited the revision instead of just adding a new diff. Anyway, I've reset it to the original content and created https://reviews.llvm.org/D49030 with my changes for review.

[efriedma]

Closing in favor of https://reviews.llvm.org/D49030, which is probably closer to what we want in most cases.

include/llvm/ADT/InsertionOrderSet.h

+//===- InsertionOrderSet.h - Hash table--------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include <vector>
+
+namespace llvm {
+
+/// A hash table with constant-time insertion and removal, and iteration in
+/// insertion order. This is by contrast to a SetVector, which does not have
+/// constant-time removal (but has random-access iterators).
+///
+/// Issues with the current implementation:
+/// - It makes two copies of each item in the set.
+/// - It doesn't clean out dead entries in the vector when the set is rehashed.
+/// - InsertionOrderMap is missing.
+/// - The name could probably be improved.
+template <class ValueT>
+class InsertionOrderSet {
+  DenseMap<ValueT, size_t> Map;
+  typedef std::vector<Optional<ValueT>> VecType;
+  VecType Vec;
+
+  struct Filter {
+    bool operator()(const Optional<ValueT>& In) {
+      return In.hasValue();
+    }
+  };
+  typedef filter_iterator<typename VecType::iterator, Filter> FilteredIter;
+
+public:
+  typedef pointee_iterator<FilteredIter> iterator;
+
+private:
+  iterator MakeSetIterator(typename VecType::iterator I) {
+    return FilteredIter{I, Vec.end(), Filter{}};
+  }
+
+public:
+  std::pair<iterator, bool> insert(ValueT value) {
+    auto SetIns = Map.insert(std::make_pair(value, Vec.size()));
+    if (SetIns.second) {
+      Vec.push_back(value);
+      return { MakeSetIterator(Vec.end()-1), true };
+    }
+    return { MakeSetIterator(Vec.begin()+SetIns.first->second), false };
+  }
+
+  iterator begin() {
+    return MakeSetIterator(Vec.begin());
+  }
+  iterator end() {
+    return MakeSetIterator(Vec.end());
+  }
+
+  void clear() {
+    Vec.clear();
+    Map.clear();
+  }
+
+  size_t size() const {
+    return Vec.size();
+  }
+
+  void remove(ValueT value) {
+    auto MapFind = Map.find(value);
+    if (MapFind != Map.end()) {
+      size_t Index = MapFind->second;
+      Map.erase(MapFind);
+      Vec[Index] = None;
+    }
+  }
+};
+}