[trafficserver] 02/05: TS-4537 Add `erase` method to PriorityQueue (#708)

[so...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

sorber pushed a commit to branch 6.2.x
in repository https://git-dual.apache.org/repos/asf/trafficserver.git

commit 921d2cb24f74bdc937df7c03406c26a841fe6bfc
Author: Thomas Jackson <ja...@gmail.com>
AuthorDate: Tue Jun 14 23:05:04 2016 -0700

    TS-4537 Add `erase` method to PriorityQueue (#708)
    
    This closes #708
    (cherry picked from commit 78850a89e62c095438a1e7a1c4a25da69b446a4b)
    
    Conflicts:
    	lib/ts/test_PriorityQueue.cc
---
 lib/ts/PriorityQueue.h       | 20 +++++++++++++++++++-
 lib/ts/test_PriorityQueue.cc | 30 ++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 1 deletion(-)

diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h
index 109f7d4..6b9f821 100644
--- a/lib/ts/PriorityQueue.h
+++ b/lib/ts/PriorityQueue.h
@@ -28,7 +28,8 @@
 #include "ts/Vec.h"
 
 template <typename T> struct PriorityQueueEntry {
-  PriorityQueueEntry(T n) : index(0), node(n) {}
+  PriorityQueueEntry(T n) : index(0), node(n){};
+  PriorityQueueEntry() : index(0){};
   uint32_t index;
   T node;
 };
@@ -52,6 +53,7 @@ public:
   void push(PriorityQueueEntry<T> *);
   void update(PriorityQueueEntry<T> *);
   void update(PriorityQueueEntry<T> *, bool);
+  void erase(PriorityQueueEntry<T> *);
   const Vec<PriorityQueueEntry<T> *> &dump() const;
 
 private:
@@ -115,6 +117,22 @@ PriorityQueue<T, Comp>::pop()
 
 template <typename T, typename Comp>
 void
+PriorityQueue<T, Comp>::erase(PriorityQueueEntry<T> *entry)
+{
+  if (empty()) {
+    return;
+  }
+
+  _v[entry->index] = _v[_v.length() - 1];
+  _v.pop();
+  _bubble_down(entry->index);
+  if (!empty()) {
+    _bubble_up(entry->index);
+  }
+}
+
+template <typename T, typename Comp>
+void
 PriorityQueue<T, Comp>::update(PriorityQueueEntry<T> *entry)
 {
   ink_release_assert(entry != NULL);
diff --git a/lib/ts/test_PriorityQueue.cc b/lib/ts/test_PriorityQueue.cc
index 3ade64b..807e000 100644
--- a/lib/ts/test_PriorityQueue.cc
+++ b/lib/ts/test_PriorityQueue.cc
@@ -278,6 +278,36 @@ REGRESSION_TEST(PriorityQueue_5)(RegressionTest *t, int /* atype ATS_UNUSED */,
   box.check(pq->top() == NULL, "top should be NULL");
 }
 
+// Test erase method
+REGRESSION_TEST(PriorityQueue_6)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+{
+  TestBox box(t, pstatus);
+  box = REGRESSION_TEST_PASSED;
+
+  PQ *pq = new PQ();
+
+  N *a = new N(10, "A");
+  N *b = new N(20, "B");
+  N *c = new N(30, "C");
+
+  Entry *entry_a = new Entry(a);
+  Entry *entry_b = new Entry(b);
+  Entry *entry_c = new Entry(c);
+
+  pq->push(entry_a);
+  pq->push(entry_b);
+  pq->push(entry_c);
+
+  box.check(pq->top() == entry_a, "top should be entry_a");
+  pq->erase(entry_a);
+  box.check(pq->top() == entry_b, "top should be entry_b");
+  pq->erase(entry_c);
+  box.check(pq->top() == entry_b, "top should be entry_b");
+  pq->erase(entry_b);
+  box.check(pq->top() == NULL, "top should be NULL");
+  box.check(pq->empty(), "should be empty");
+}
+
 int
 main(int /* argc ATS_UNUSED */, const char ** /* argv ATS_UNUSED */)
 {

-- 
To stop receiving notification emails like this one, please contact
"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>.