UniqueDeferredQueue improvements (#3847)

Add clear().

Add UniqueNonrepeatingDeferredQueue which also has the property
that it never repeats values in the output.

Also add unit tests.

2 files changed, 64 insertions, 0 deletions

diff --git a/src/support/unique_deferring_queue.h b/src/support/unique_deferring_queue.h
index ad8f3967d..ba59ffd8f 100644
--- a/src/support/unique_deferring_queue.h
+++ b/src/support/unique_deferring_queue.h
@@ -25,6 +25,7 @@
 
 #include <queue>
 #include <unordered_map>
+#include <unordered_set>
 
 namespace wasm {
 
@@ -57,6 +58,31 @@ template<typename T> struct UniqueDeferredQueue {
       // skip this one, keep going
     }
   }
+
+  void clear() {
+    std::queue<T> empty;
+    std::swap(data, empty);
+    count.clear();
+  }
+};
+
+// As UniqueDeferredQueue, but once an item has been processed through the queue
+// (that is, popped) it will be ignored from then on in later pushes.
+template<typename T>
+struct UniqueNonrepeatingDeferredQueue : UniqueDeferredQueue<T> {
+  std::unordered_set<T> processed;
+
+  void push(T item) {
+    if (!processed.count(item)) {
+      UniqueDeferredQueue<T>::push(item);
+    }
+  }
+
+  T pop() {
+    T ret = UniqueDeferredQueue<T>::pop();
+    processed.insert(ret);
+    return ret;
+  }
 };
 
 } // namespace wasm
diff --git a/test/example/cpp-unit.cpp b/test/example/cpp-unit.cpp
index 49893d1d2..3ab35d381 100644
--- a/test/example/cpp-unit.cpp
+++ b/test/example/cpp-unit.cpp
@@ -6,6 +6,7 @@
 #include <ir/cost.h>
 #include <ir/effects.h>
 #include <pass.h>
+#include <support/unique_deferring_queue.h>
 #include <wasm.h>
 
 using namespace wasm;
@@ -581,12 +582,49 @@ void test_field() {
                4);
 }
 
+void test_queue() {
+  {
+    UniqueDeferredQueue<int> queue;
+    queue.push(1);
+    queue.push(2);
+    queue.push(3);
+    queue.push(2);
+    // first in was 1
+    assert_equal(queue.pop(), 1);
+    // next in was 2, but it was added later, so we defer to then, and get the 3
+    assert_equal(queue.pop(), 3);
+    assert_equal(queue.pop(), 2);
+    assert_equal(queue.empty(), true);
+  }
+  {
+    UniqueDeferredQueue<int> queue;
+    queue.push(1);
+    queue.push(2);
+    assert_equal(queue.pop(), 1);
+    // clearing clears the queue
+    queue.clear();
+    assert_equal(queue.empty(), true);
+  }
+  {
+    UniqueNonrepeatingDeferredQueue<int> queue;
+    queue.push(1);
+    assert_equal(queue.pop(), 1);
+    queue.push(1);
+    // We never repeat values in this queue, so the last push of 1 is ignored.
+    assert_equal(queue.empty(), true);
+    // But new values work.
+    queue.push(2);
+    assert_equal(queue.pop(), 2);
+  }
+}
+
 int main() {
   test_bits();
   test_cost();
   test_effects();
   test_literals();
   test_field();
+  test_queue();
 
   if (failsCount > 0) {
     abort();