Repository: trafficserver Updated Branches: refs/heads/master ea1691ba5 -> 5952dd78f
TS-4295: Add Priority Queue in lib/ts/ This closes #537. Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/5952dd78 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/5952dd78 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/5952dd78 Branch: refs/heads/master Commit: 5952dd78fc607be8567d4e86ce184ea91bcce867 Parents: ea1691b Author: Masaori Koshiba <masa...@apache.org> Authored: Fri Apr 8 17:25:54 2016 +0900 Committer: Masaori Koshiba <masa...@apache.org> Committed: Fri Apr 8 17:30:58 2016 +0900 ---------------------------------------------------------------------- .gitignore | 1 + lib/ts/Makefile.am | 7 +- lib/ts/PriorityQueue.h | 214 ++++++++++++++++++++++++++++ lib/ts/Regression.cc | 2 +- lib/ts/Regression.h | 2 +- lib/ts/TestBox.h | 1 + lib/ts/test_PriorityQueue.cc | 285 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 509 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/.gitignore ---------------------------------------------------------------------- diff --git a/.gitignore b/.gitignore index 493d95c..bf65b4e 100644 --- a/.gitignore +++ b/.gitignore @@ -77,6 +77,7 @@ lib/ts/test_Map lib/ts/test_Vec lib/ts/test_geometry lib/ts/test_Regex +lib/ts/test_PriorityQueue lib/ts/test_X509HostnameValidator lib/perl/lib/Apache/TS.pm http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/lib/ts/Makefile.am ---------------------------------------------------------------------- diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am index 8824fb9..71ae96e 100644 --- a/lib/ts/Makefile.am +++ b/lib/ts/Makefile.am @@ -21,7 +21,7 @@ library_includedir=$(includedir)/ts library_include_HEADERS = apidefs.h noinst_PROGRAMS = mkdfa CompileParseRules -check_PROGRAMS = test_arena test_atomic test_freelist test_geometry test_List test_Map test_Regex test_Vec test_X509HostnameValidator +check_PROGRAMS = test_arena test_atomic test_freelist test_geometry test_List test_Map test_Regex test_PriorityQueue test_Vec test_X509HostnameValidator TESTS = $(check_PROGRAMS) AM_CPPFLAGS = -I$(top_srcdir)/lib @@ -84,6 +84,7 @@ libtsutil_la_SOURCES = \ MatcherUtils.h \ ParseRules.cc \ ParseRules.h \ + PriorityQueue.h \ Ptr.h \ RawHashTable.cc \ RawHashTable.h \ @@ -216,6 +217,10 @@ test_Regex_SOURCES = test_Regex.cc test_Regex_LDADD = libtsutil.la @LIBTCL@ @LIBPCRE@ test_Regex_LDFLAGS = @EXTRA_CXX_LDFLAGS@ @LIBTOOL_LINK_FLAGS@ +test_PriorityQueue_SOURCES = test_PriorityQueue.cc +test_PriorityQueue_LDADD = libtsutil.la @LIBTCL@ @LIBPCRE@ +test_PriorityQueue_LDFLAGS = @EXTRA_CXX_LDFLAGS@ @LIBTOOL_LINK_FLAGS@ + test_Vec_SOURCES = test_Vec.cc test_Vec_LDADD = libtsutil.la @LIBTCL@ @LIBPCRE@ test_Vec_LDFLAGS = @EXTRA_CXX_LDFLAGS@ @LIBTOOL_LINK_FLAGS@ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/lib/ts/PriorityQueue.h ---------------------------------------------------------------------- diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h new file mode 100644 index 0000000..f7185af --- /dev/null +++ b/lib/ts/PriorityQueue.h @@ -0,0 +1,214 @@ +/** @file + + Priority Queue Implementation using Binary Heap. + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#ifndef __PRIORITY_QUEUE_H__ +#define __PRIORITY_QUEUE_H__ + +#include "ts/ink_assert.h" +#include "ts/Vec.h" + +template <typename T> struct PriorityQueueEntry { + PriorityQueueEntry(T n) : index(0), node(n) {} + + uint32_t index; + T node; +}; + +template <typename T> struct PriorityQueueLess { + bool operator()(const T &a, const T &b) { return *a < *b; } +}; + +template <typename T, class Comp = PriorityQueueLess<T> > class PriorityQueue +{ +public: + PriorityQueue() {} + ~PriorityQueue() {} + + const bool empty(); + PriorityQueueEntry<T> *top(); + void pop(); + void push(PriorityQueueEntry<T> *); + void update(PriorityQueueEntry<T> *); + void update(PriorityQueueEntry<T> *, bool); + const Vec<PriorityQueueEntry<T> *> &dump() const; + +private: + Vec<PriorityQueueEntry<T> *> _v; + + void _swap(uint32_t, uint32_t); + void _bubble_up(uint32_t); + void _bubble_down(uint32_t); +}; + +template <typename T, typename Comp> +const Vec<PriorityQueueEntry<T> *> & +PriorityQueue<T, Comp>::dump() const +{ + return _v; +} + +template <typename T, typename Comp> +const bool +PriorityQueue<T, Comp>::empty() +{ + return _v.length() == 0; +} + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::push(PriorityQueueEntry<T> *entry) +{ + ink_release_assert(entry != NULL); + + int len = _v.length(); + _v.push_back(entry); + entry->index = len; + + _bubble_up(len); +} + +template <typename T, typename Comp> +PriorityQueueEntry<T> * +PriorityQueue<T, Comp>::top() +{ + if (empty()) { + return NULL; + } else { + return _v[0]; + } +} + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::pop() +{ + if (empty()) { + return; + } + + _v[0] = _v[_v.length() - 1]; + _v.pop(); + _bubble_down(0); +} + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::update(PriorityQueueEntry<T> *entry) +{ + ink_release_assert(entry != NULL); + + if (empty()) { + return; + } + + // One of them will works whether weight is increased or decreased + _bubble_down(entry->index); + _bubble_up(entry->index); +} + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::update(PriorityQueueEntry<T> *entry, bool increased) +{ + ink_release_assert(entry != NULL); + + if (empty()) { + return; + } + + if (increased) { + _bubble_down(entry->index); + } else { + _bubble_up(entry->index); + } +} + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::_swap(uint32_t i, uint32_t j) +{ + PriorityQueueEntry<T> *tmp = _v[i]; + _v[i] = _v[j]; + _v[j] = tmp; + + _v[i]->index = i; + _v[j]->index = j; +} + + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::_bubble_up(uint32_t index) +{ + if (empty()) { + ink_release_assert(false); + } + + Comp comp; + + uint32_t parent; + while (index != 0) { + parent = (index - 1) / 2; + if (comp(_v[index]->node, _v[parent]->node)) { + _swap(parent, index); + index = parent; + continue; + } + + break; + } +} + +template <typename T, typename Comp> +void +PriorityQueue<T, Comp>::_bubble_down(uint32_t index) +{ + if (empty()) { + // Do nothing + return; + } + + uint32_t left, right, smaller; + + Comp comp; + + while (true) { + if ((left = index * 2 + 1) >= _v.length()) { + break; + } else if ((right = index * 2 + 2) >= _v.length()) { + smaller = left; + } else { + smaller = comp(_v[left]->node, _v[right]->node) ? left : right; + } + + if (comp(_v[smaller]->node, _v[index]->node)) { + _swap(smaller, index); + index = smaller; + continue; + } + + break; + } +} + +#endif // __PRIORITY_QUEUE_H__ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/lib/ts/Regression.cc ---------------------------------------------------------------------- diff --git a/lib/ts/Regression.cc b/lib/ts/Regression.cc index 503917d..878197c 100644 --- a/lib/ts/Regression.cc +++ b/lib/ts/Regression.cc @@ -86,7 +86,7 @@ start_test(RegressionTest *t) } int -RegressionTest::run(char *atest) +RegressionTest::run(const char *atest) { if (atest) dfa.compile(atest); http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/lib/ts/Regression.h ---------------------------------------------------------------------- diff --git a/lib/ts/Regression.h b/lib/ts/Regression.h index f86c7ee..289c787 100644 --- a/lib/ts/Regression.h +++ b/lib/ts/Regression.h @@ -79,7 +79,7 @@ struct RegressionTest { static int ran_tests; static DFA dfa; static RegressionTest *current; - static int run(char *name = NULL); + static int run(const char *name = NULL); static int run_some(); static int check_status(); }; http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/lib/ts/TestBox.h ---------------------------------------------------------------------- diff --git a/lib/ts/TestBox.h b/lib/ts/TestBox.h index 4020fc3..d8140e2 100644 --- a/lib/ts/TestBox.h +++ b/lib/ts/TestBox.h @@ -25,6 +25,7 @@ */ #include <stdarg.h> +#include "ts/ink_apidefs.h" #include "ts/Regression.h" namespace http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5952dd78/lib/ts/test_PriorityQueue.cc ---------------------------------------------------------------------- diff --git a/lib/ts/test_PriorityQueue.cc b/lib/ts/test_PriorityQueue.cc new file mode 100644 index 0000000..a6e1740 --- /dev/null +++ b/lib/ts/test_PriorityQueue.cc @@ -0,0 +1,285 @@ +/** @file + + Unit tests for PriorityQueue + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +*/ + +#include <iostream> +#include <string.h> + +#include <ts/TestBox.h> + +#include "PriorityQueue.h" + +using namespace std; + +class N +{ +public: + N(uint32_t w, string c) : weight(w), content(c) {} + + bool operator<(const N &n) const { return weight < n.weight; } + + uint32_t weight; + string content; +}; + +typedef PriorityQueueEntry<N *> Entry; +typedef PriorityQueue<N *> PQ; + +// For debug +void +dump(PQ *pq) +{ + Vec<Entry *> v = pq->dump(); + + for (uint32_t i = 0; i < v.length(); i++) { + cout << v[i]->index << "," << v[i]->node->weight << "," << v[i]->node->content << endl; + } + cout << "--------" << endl; +} + +// Push, top, and pop a entry +REGRESSION_TEST(PriorityQueue_1)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + PQ *pq = new PQ(); + N *a = new N(6, "A"); + Entry *entry_a = new Entry(a); + + pq->push(entry_a); + box.check(pq->top() == entry_a, "top should be entry_a"); + + pq->pop(); + box.check(pq->top() == NULL, "top should be NULL"); +} + +// Increase weight +REGRESSION_TEST(PriorityQueue_2)(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"); + + a->weight = 40; + pq->update(entry_a); + + box.check(pq->top() == entry_b, "top should be entry_b"); + + b->weight = 50; + pq->update(entry_b, true); + + box.check(pq->top() == entry_c, "top should be entry_c"); +} + +// Decrease weight +REGRESSION_TEST(PriorityQueue_3)(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"); + + b->weight = 5; + pq->update(entry_b); + + box.check(pq->top() == entry_b, "top should be entry_b"); + + c->weight = 3; + pq->update(entry_c, false); + + box.check(pq->top() == entry_c, "top should be entry_c"); +} + +// Push, top, and pop 9 entries +REGRESSION_TEST(PriorityQueue_4)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + PQ *pq = new PQ(); + + N *a = new N(6, "A"); + N *b = new N(1, "B"); + N *c = new N(9, "C"); + N *d = new N(8, "D"); + N *e = new N(4, "E"); + N *f = new N(3, "F"); + N *g = new N(2, "G"); + N *h = new N(7, "H"); + N *i = new N(5, "I"); + + Entry *entry_a = new Entry(a); + Entry *entry_b = new Entry(b); + Entry *entry_c = new Entry(c); + Entry *entry_d = new Entry(d); + Entry *entry_e = new Entry(e); + Entry *entry_f = new Entry(f); + Entry *entry_g = new Entry(g); + Entry *entry_h = new Entry(h); + Entry *entry_i = new Entry(i); + + pq->push(entry_a); + pq->push(entry_b); + pq->push(entry_c); + pq->push(entry_d); + pq->push(entry_e); + pq->push(entry_f); + pq->push(entry_g); + pq->push(entry_h); + pq->push(entry_i); + + box.check(pq->top() == entry_b, "top should be entry_b"); // 1 + pq->pop(); + box.check(pq->top() == entry_g, "top should be entry_g"); // 2 + pq->pop(); + box.check(pq->top() == entry_f, "top should be entry_f"); // 3 + pq->pop(); + box.check(pq->top() == entry_e, "top should be entry_e"); // 4 + pq->pop(); + box.check(pq->top() == entry_i, "top should be entry_i"); // 5 + pq->pop(); + box.check(pq->top() == entry_a, "top should be entry_a"); // 6 + pq->pop(); + box.check(pq->top() == entry_h, "top should be entry_h"); // 7 + pq->pop(); + box.check(pq->top() == entry_d, "top should be entry_d"); // 8 + pq->pop(); + box.check(pq->top() == entry_c, "top should be entry_c"); // 9 + pq->pop(); + + box.check(pq->top() == NULL, "top should be NULL"); +} + +// // Push, top, pop, and update 9 entries +REGRESSION_TEST(PriorityQueue_5)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + PQ *pq = new PQ(); + + N *a = new N(6, "A"); + N *b = new N(1, "B"); + N *c = new N(9, "C"); + N *d = new N(8, "D"); + N *e = new N(4, "E"); + N *f = new N(3, "F"); + N *g = new N(2, "G"); + N *h = new N(7, "H"); + N *i = new N(5, "I"); + + Entry *entry_a = new Entry(a); + Entry *entry_b = new Entry(b); + Entry *entry_c = new Entry(c); + Entry *entry_d = new Entry(d); + Entry *entry_e = new Entry(e); + Entry *entry_f = new Entry(f); + Entry *entry_g = new Entry(g); + Entry *entry_h = new Entry(h); + Entry *entry_i = new Entry(i); + + pq->push(entry_a); + pq->push(entry_b); + pq->push(entry_c); + pq->push(entry_d); + pq->push(entry_e); + pq->push(entry_f); + pq->push(entry_g); + pq->push(entry_h); + pq->push(entry_i); + + // Pop head and push it back again + box.check(pq->top() == entry_b, "top should be entry_b"); // 1 + pq->pop(); + b->weight += 100; + pq->push(entry_b); + // Update weight + a->weight += 100; + pq->update(entry_a); + c->weight += 100; + pq->update(entry_d); + e->weight += 100; + pq->update(entry_e); + g->weight += 100; + pq->update(entry_g); + + // Check + box.check(pq->top() == entry_f, "top should be entry_f"); // 3 + pq->pop(); + box.check(pq->top() == entry_i, "top should be entry_i"); // 5 + pq->pop(); + box.check(pq->top() == entry_h, "top should be entry_h"); // 7 + pq->pop(); + box.check(pq->top() == entry_d, "top should be entry_d"); // 8 + pq->pop(); + box.check(pq->top() == entry_b, "top should be entry_b"); // 101 + pq->pop(); + box.check(pq->top() == entry_g, "top should be entry_g"); // 102 + pq->pop(); + box.check(pq->top() == entry_e, "top should be entry_e"); // 104 + pq->pop(); + box.check(pq->top() == entry_a, "top should be entry_a"); // 106 + pq->pop(); + box.check(pq->top() == entry_c, "top should be entry_c"); // 109 + pq->pop(); + + box.check(pq->top() == NULL, "top should be NULL"); +} + +int +main(int /* argc ATS_UNUSED */, const char ** /* argv ATS_UNUSED */) +{ + const char *name = "PriorityQueue"; + RegressionTest::run(name); + + return RegressionTest::final_status == REGRESSION_TEST_PASSED ? 0 : 1; +}