[trafficserver] branch master updated: Remove the wrong entry from priority queue and insert the new node into queue

[zw...@apache.org]

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

zwoop pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git


The following commit(s) were added to refs/heads/master by this push:
     new a50aaf1  Remove the wrong entry from priority queue and insert the new node into queue
a50aaf1 is described below

commit a50aaf1a4f0a76faeb3050dec3a5e75ff90b9f94
Author: scw00 <sc...@apache.org>
AuthorDate: Thu Aug 10 20:43:51 2017 +0800

    Remove the wrong entry from priority queue and insert the new node into queue
---
 lib/ts/PriorityQueue.h                  |  6 ++++++
 lib/ts/test_PriorityQueue.cc            | 30 ++++++++++++++++++++++++++++++
 proxy/http2/Http2DependencyTree.h       |  8 ++++++++
 proxy/http2/test_Http2DependencyTree.cc | 32 ++++++++++++++++++++++++++++++++
 4 files changed, 76 insertions(+)

diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h
index c233670..8e27cb3 100644
--- a/lib/ts/PriorityQueue.h
+++ b/lib/ts/PriorityQueue.h
@@ -125,6 +125,12 @@ PriorityQueue<T, Comp>::erase(PriorityQueueEntry<T> *entry)
     return;
   }
 
+  // If the entry doesn't belong to this queue just return.
+  if (entry != _v[entry->index]) {
+    ink_assert(!_v.in(entry));
+    return;
+  }
+
   ink_release_assert(entry->index < _v.length());
   const uint32_t original_index = entry->index;
   if (original_index != (_v.length() - 1)) {
diff --git a/lib/ts/test_PriorityQueue.cc b/lib/ts/test_PriorityQueue.cc
index aa13e9f..6206c3c 100644
--- a/lib/ts/test_PriorityQueue.cc
+++ b/lib/ts/test_PriorityQueue.cc
@@ -524,3 +524,33 @@ REGRESSION_TEST(PriorityQueue_pop_and_erase)(RegressionTest *t, int /* atype ATS
   delete entry_y;
   delete entry_z;
 }
+
+REGRESSION_TEST(PriorityQueue_pop_and_erase_2)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+{
+  TestBox box(t, pstatus);
+  box = REGRESSION_TEST_PASSED;
+
+  PQ *pq1 = new PQ();
+
+  N *x = new N(20, "X");
+  N *y = new N(30, "Y");
+
+  Entry *X = new Entry(x);
+  Entry *Y = new Entry(y);
+
+  box.check(X->index == 0 && Y->index == 0, "X and Y index should be 0");
+
+  pq1->push(X);
+
+  pq1->erase(Y);
+
+  box.check(pq1->top() == X, "X should be in queue");
+
+  delete x;
+  delete y;
+
+  delete X;
+  delete Y;
+
+  delete pq1;
+}
diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h
index 526b9fc..8ad7fb0 100644
--- a/proxy/http2/Http2DependencyTree.h
+++ b/proxy/http2/Http2DependencyTree.h
@@ -175,12 +175,20 @@ Http2DependencyTree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bo
 
   if (exclusive) {
     while (Node *child = parent->children.pop()) {
+      if (child->queued) {
+        parent->queue->erase(child->entry);
+        node->queue->push(child->entry);
+      }
       node->children.push(child);
       child->parent = node;
     }
   }
 
   parent->children.push(node);
+  if (!node->queue->empty()) {
+    parent->queue->push(node->entry);
+    node->queued = true;
+  }
 
   ++_node_count;
   return node;
diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc
index 5056cbd..a147685 100644
--- a/proxy/http2/test_Http2DependencyTree.cc
+++ b/proxy/http2/test_Http2DependencyTree.cc
@@ -498,6 +498,38 @@ REGRESSION_TEST(Http2DependencyTree_remove_2)(RegressionTest *t, int /* atype AT
   delete tree;
 }
 
+/**
+ * Exclusive Dependency Creation
+ *
+ *       A            A
+ *      / \    =>     |
+ *     B   C          D
+ *                   / \
+ *                  B   C
+ */
+REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+{
+  TestBox box(t, pstatus);
+  box = REGRESSION_TEST_PASSED;
+
+  Tree *tree = new Tree(100);
+  string a("A"), b("B"), c("C"), d("D");
+
+  Tree::Node *B = tree->add(0, 1, 0, false, &b);
+  tree->add(0, 3, 0, false, &c);
+
+  tree->activate(B);
+  // Add node with exclusive flag
+  tree->add(0, 5, 0, true, &d);
+
+  tree->deactivate(B, 0);
+  tree->remove(B);
+
+  box.check(tree->top() == NULL, "Tree top should be NULL");
+
+  delete tree;
+}
+
 REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
 {
   TestBox box(t, pstatus);

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