From 36c0fd220ef02b1ffd7a3ae0d98e0fdec6b55a5b Mon Sep 17 00:00:00 2001
From: Samuel Just <sam.just@inktank.com>
Date: Fri, 9 Nov 2012 18:37:44 -0800
Subject: [PATCH] PrioritizedQueue: allow caller to get items removed by
 removed_by_filter

Signed-off-by: Samuel Just <sam.just@inktank.com>
---
 src/common/PrioritizedQueue.h | 26 ++++++++++++++++++--------
 1 file changed, 18 insertions(+), 8 deletions(-)

diff --git a/src/common/PrioritizedQueue.h b/src/common/PrioritizedQueue.h
index 72ec3e913e247..7a7348267c045 100644
--- a/src/common/PrioritizedQueue.h
+++ b/src/common/PrioritizedQueue.h
@@ -47,14 +47,24 @@ class PrioritizedQueue {
   int64_t total_priority;
 
   template <class F>
-  static unsigned filter_list_pairs(list<pair<unsigned, T> > *l, F f) {
+  static unsigned filter_list_pairs(
+    list<pair<unsigned, T> > *l, F f,
+    list<T> *out) {
     unsigned ret = 0;
+    for (typename list<pair<unsigned, T> >::reverse_iterator i = l->rbegin();
+	 i != l->rend();
+	 ++i) {
+      if (out) {
+	if (f(i->second)) {
+	  out->push_front(i->second);
+	}
+      }
+    }
     for (typename list<pair<unsigned, T> >::iterator i = l->begin();
 	 i != l->end();
-	 ) {
+      ) {
       if (f(i->second)) {
 	l->erase(i++);
-	ret++;
       } else {
 	++i;
       }
@@ -119,11 +129,11 @@ class PrioritizedQueue {
       return q.empty();
     }
     template <class F>
-    void remove_by_filter(F f) {
+    void remove_by_filter(F f, list<T> *out) {
       for (typename map<K, list<pair<unsigned, T> > >::iterator i = q.begin();
 	   i != q.end();
 	   ) {
-	size -= filter_list_pairs(&(i->second), f);
+	size -= filter_list_pairs(&(i->second), f, out);
 	if (i->second.empty()) {
 	  if (cur == i)
 	    ++cur;
@@ -205,13 +215,13 @@ public:
   }
 
   template <class F>
-  void remove_by_filter(F f) {
+  void remove_by_filter(F f, list<T> *removed = 0) {
     for (typename map<unsigned, SubQueue>::iterator i = queue.begin();
 	 i != queue.end();
 	 ) {
       unsigned priority = i->first;
       
-      i->second.remove_by_filter(f);
+      i->second.remove_by_filter(f, removed);
       if (i->second.empty()) {
 	++i;
 	remove_queue(priority);
@@ -222,7 +232,7 @@ public:
     for (typename map<unsigned, SubQueue>::iterator i = high_queue.begin();
 	 i != high_queue.end();
 	 ) {
-      i->second.remove_by_filter(f);
+      i->second.remove_by_filter(f, removed);
       if (i->second.empty()) {
 	high_queue.erase(i++);
       } else {
-- 
2.39.5