From a4c7866f5e133c58ebbf09715a705d514209dac1 Mon Sep 17 00:00:00 2001
From: Alon Zakai <azakai@google.com>
Date: Thu, 29 Apr 2021 11:39:28 -0700
Subject: UniqueDeferredQueue improvements (#3847)

Add clear().

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

Also add unit tests.
---
 src/support/unique_deferring_queue.h | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

(limited to 'src')

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
-- 
cgit v1.2.3