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 <[email protected]> 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 "[email protected]" <[email protected]>.
