You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by ma...@apache.org on 2016/04/08 10:32:46 UTC
trafficserver git commit: TS-4295: Add Priority Queue in lib/ts/
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 <ma...@apache.org>
Authored: Fri Apr 8 17:25:54 2016 +0900
Committer: Masaori Koshiba <ma...@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;
+}