You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by zw...@apache.org on 2017/10/13 16:17:00 UTC
[trafficserver] branch 7.1.x updated: Fix the implementation of
Http2DependencyTree
This is an automated email from the ASF dual-hosted git repository.
zwoop pushed a commit to branch 7.1.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/7.1.x by this push:
new 856bb18 Fix the implementation of Http2DependencyTree
856bb18 is described below
commit 856bb18ed80afe5d3e8166331bf4fc4c8a022abb
Author: scw00 <sc...@apache.org>
AuthorDate: Fri Sep 1 10:17:43 2017 +0800
Fix the implementation of Http2DependencyTree
(cherry picked from commit f367a3032a8e0a172e77b5180ddee3257adb6f31)
Conflicts:
proxy/http2/Http2Stream.h
proxy/http2/test_Http2DependencyTree.cc
---
proxy/http2/Http2ConnectionState.cc | 14 +-
proxy/http2/Http2DependencyTree.h | 228 ++++++++++++++++--------------
proxy/http2/Http2Stream.h | 10 +-
proxy/http2/test_Http2DependencyTree.cc | 237 ++++++++++++++++++++++----------
4 files changed, 303 insertions(+), 186 deletions(-)
diff --git a/proxy/http2/Http2ConnectionState.cc b/proxy/http2/Http2ConnectionState.cc
index 0836db8..225a1c0 100644
--- a/proxy/http2/Http2ConnectionState.cc
+++ b/proxy/http2/Http2ConnectionState.cc
@@ -279,7 +279,7 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame)
}
if (new_stream && Http2::stream_priority_enabled) {
- DependencyTree::Node *node = cstate.dependency_tree->find(stream_id);
+ Http2DependencyTree::Node *node = cstate.dependency_tree->find(stream_id);
if (node != nullptr) {
stream->priority_node = node;
node->t = stream;
@@ -398,7 +398,7 @@ rcv_priority_frame(Http2ConnectionState &cstate, const Http2Frame &frame)
DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d, tree size: %d",
priority.stream_dependency, priority.weight, priority.exclusive_flag, cstate.dependency_tree->size());
- DependencyTree::Node *node = cstate.dependency_tree->find(stream_id);
+ Http2DependencyTree::Node *node = cstate.dependency_tree->find(stream_id);
if (node != nullptr) {
// [RFC 7540] 5.3.3 Reprioritization
@@ -1089,7 +1089,7 @@ Http2ConnectionState::delete_stream(Http2Stream *stream)
DebugHttp2Stream(ua_session, stream->get_id(), "Delete stream");
if (Http2::stream_priority_enabled) {
- DependencyTree::Node *node = stream->priority_node;
+ Http2DependencyTree::Node *node = stream->priority_node;
if (node != nullptr) {
if (node->active) {
dependency_tree->deactivate(node, 0);
@@ -1159,7 +1159,7 @@ Http2ConnectionState::schedule_stream(Http2Stream *stream)
{
DebugHttp2Stream(ua_session, stream->get_id(), "Scheduled");
- DependencyTree::Node *node = stream->priority_node;
+ Http2DependencyTree::Node *node = stream->priority_node;
ink_release_assert(node != nullptr);
SCOPED_MUTEX_LOCK(lock, this->mutex, this_ethread());
@@ -1176,14 +1176,14 @@ Http2ConnectionState::schedule_stream(Http2Stream *stream)
void
Http2ConnectionState::send_data_frames_depends_on_priority()
{
- DependencyTree::Node *node = dependency_tree->top();
+ Http2DependencyTree::Node *node = dependency_tree->top();
// No node to send or no connection level window left
if (node == nullptr || client_rwnd <= 0) {
return;
}
- Http2Stream *stream = node->t;
+ Http2Stream *stream = static_cast<Http2Stream *>(node->t);
ink_release_assert(stream != nullptr);
DebugHttp2Stream(ua_session, stream->get_id(), "top node, point=%d", node->point);
@@ -1491,7 +1491,7 @@ Http2ConnectionState::send_push_promise_frame(Http2Stream *stream, URL &url)
return;
}
if (Http2::stream_priority_enabled) {
- DependencyTree::Node *node = this->dependency_tree->find(id);
+ Http2DependencyTree::Node *node = this->dependency_tree->find(id);
if (node != nullptr) {
stream->priority_node = node;
} else {
diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h
index 70aed80..f0a5692 100644
--- a/proxy/http2/Http2DependencyTree.h
+++ b/proxy/http2/Http2DependencyTree.h
@@ -37,80 +37,79 @@
const static uint32_t K = 256;
const static uint32_t HTTP2_DEPENDENCY_TREE_MAX_DEPTH = 256;
-template <typename T> class Http2DependencyTree
+namespace Http2DependencyTree
+{
+class Node
{
public:
- class Node
+ Node(void *t = nullptr) : t(t)
{
- public:
- Node()
- : active(false),
- queued(false),
- id(HTTP2_PRIORITY_DEFAULT_STREAM_DEPENDENCY),
- weight(HTTP2_PRIORITY_DEFAULT_WEIGHT),
- point(0),
- parent(NULL),
- t(NULL)
- {
- entry = new PriorityQueueEntry<Node *>(this);
- queue = new PriorityQueue<Node *>();
- }
- Node(uint32_t i, uint32_t w, uint32_t p, Node *n, T t)
- : active(false), queued(false), id(i), weight(w), point(p), parent(n), t(t)
- {
- entry = new PriorityQueueEntry<Node *>(this);
- queue = new PriorityQueue<Node *>();
- }
+ entry = new PriorityQueueEntry<Node *>(this);
+ queue = new PriorityQueue<Node *>();
+ }
- ~Node()
- {
- delete entry;
- delete queue;
-
- // delete all child nodes
- if (!children.empty()) {
- Node *node = children.head;
- Node *next = NULL;
- while (node) {
- next = node->link.next;
- children.remove(node);
- delete node;
- node = next;
- }
+ Node(uint32_t i, uint32_t w, uint32_t p, Node *n, void *t = nullptr) : id(i), weight(w), point(p), t(t), parent(n)
+ {
+ entry = new PriorityQueueEntry<Node *>(this);
+ queue = new PriorityQueue<Node *>();
+ }
+
+ ~Node()
+ {
+ delete entry;
+ delete queue;
+
+ // delete all child nodes
+ if (!children.empty()) {
+ Node *node = children.head;
+ Node *next = nullptr;
+ while (node) {
+ next = node->link.next;
+ children.remove(node);
+ delete node;
+ node = next;
}
}
+ }
- LINK(Node, link);
+ LINK(Node, link);
- bool
- operator<(const Node &n) const
- {
- return point < n.point;
- }
- bool
- operator>(const Node &n) const
- {
- return point > n.point;
- }
+ bool
+ operator<(const Node &n) const
+ {
+ return point < n.point;
+ }
+ bool
+ operator>(const Node &n) const
+ {
+ return point > n.point;
+ }
- bool active;
- bool queued;
- uint32_t id;
- uint32_t weight;
- uint32_t point;
- Node *parent;
- DLL<Node> children;
- PriorityQueueEntry<Node *> *entry;
- PriorityQueue<Node *> *queue;
- T t;
- };
-
- Http2DependencyTree(uint32_t max_concurrent_streams)
- : _root(new Node()), _max_depth(MIN(max_concurrent_streams, HTTP2_DEPENDENCY_TREE_MAX_DEPTH)), _node_count(0)
+ bool
+ is_shadow() const
{
+ return t == nullptr;
}
- ~Http2DependencyTree() { delete _root; }
+
+ bool active = false;
+ bool queued = false;
+ uint32_t id = HTTP2_PRIORITY_DEFAULT_STREAM_DEPENDENCY;
+ uint32_t weight = HTTP2_PRIORITY_DEFAULT_WEIGHT;
+ uint32_t point = 0;
+ void *t = nullptr;
+ Node *parent = nullptr;
+ DLL<Node> children;
+ PriorityQueueEntry<Node *> *entry;
+ PriorityQueue<Node *> *queue;
+};
+
+template <typename T> class Tree
+{
+public:
+ Tree(uint32_t max_concurrent_streams) : _max_depth(MIN(max_concurrent_streams, HTTP2_DEPENDENCY_TREE_MAX_DEPTH)) {}
+ ~Tree() { delete _root; }
Node *find(uint32_t id);
+ Node *find_shadow(uint32_t id);
Node *add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t);
void remove(Node *node);
void reprioritize(uint32_t new_parent_id, uint32_t id, bool exclusive);
@@ -126,27 +125,27 @@ private:
Node *_top(Node *node);
void _change_parent(Node *new_parent, Node *node, bool exclusive);
- Node *_root;
+ Node *_root = new Node(this);
uint32_t _max_depth;
- uint32_t _node_count;
+ uint32_t _node_count = 0;
};
template <typename T>
-typename Http2DependencyTree<T>::Node *
-Http2DependencyTree<T>::_find(Node *node, uint32_t id, uint32_t depth)
+Node *
+Tree<T>::_find(Node *node, uint32_t id, uint32_t depth)
{
if (node->id == id) {
return node;
}
if (node->children.empty() || depth >= _max_depth) {
- return NULL;
+ return nullptr;
}
- Node *result = NULL;
+ Node *result = nullptr;
for (Node *n = node->children.head; n; n = n->link.next) {
result = _find(n, id, ++depth);
- if (result != NULL) {
+ if (result != nullptr) {
break;
}
}
@@ -155,23 +154,39 @@ Http2DependencyTree<T>::_find(Node *node, uint32_t id, uint32_t depth)
}
template <typename T>
-typename Http2DependencyTree<T>::Node *
-Http2DependencyTree<T>::find(uint32_t id)
+Node *
+Tree<T>::find_shadow(uint32_t id)
{
return _find(_root, id);
}
template <typename T>
-typename Http2DependencyTree<T>::Node *
-Http2DependencyTree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t)
+Node *
+Tree<T>::find(uint32_t id)
+{
+ Node *n = _find(_root, id);
+ return n == nullptr ? nullptr : (n->is_shadow() ? nullptr : n);
+}
+
+template <typename T>
+Node *
+Tree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t)
{
Node *parent = find(parent_id);
- if (parent == NULL) {
- parent = _root;
+ if (parent == nullptr) {
+ parent = add(0, parent_id, HTTP2_PRIORITY_DEFAULT_WEIGHT, false, nullptr);
+ }
+
+ Node *node = find_shadow(id);
+ if (node != nullptr && node->is_shadow()) {
+ node->t = t;
+ node->point = id;
+ node->weight = weight;
+ return node;
}
// Use stream id as initial point
- Node *node = new Node(id, weight, id, parent, t);
+ node = new Node(id, weight, id, parent, t);
if (exclusive) {
while (Node *child = parent->children.pop()) {
@@ -196,7 +211,7 @@ Http2DependencyTree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bo
template <typename T>
void
-Http2DependencyTree<T>::remove(Node *node)
+Tree<T>::remove(Node *node)
{
if (node == _root || node->active) {
return;
@@ -221,16 +236,21 @@ Http2DependencyTree<T>::remove(Node *node)
child->parent = parent;
}
+ // delete the shadow parent
+ if (parent->is_shadow() && parent->children.empty() && parent->queue->empty()) {
+ remove(parent);
+ }
+
--_node_count;
delete node;
}
template <typename T>
void
-Http2DependencyTree<T>::reprioritize(uint32_t id, uint32_t new_parent_id, bool exclusive)
+Tree<T>::reprioritize(uint32_t id, uint32_t new_parent_id, bool exclusive)
{
Node *node = find(id);
- if (node == NULL) {
+ if (node == nullptr) {
return;
}
@@ -239,9 +259,9 @@ Http2DependencyTree<T>::reprioritize(uint32_t id, uint32_t new_parent_id, bool e
template <typename T>
void
-Http2DependencyTree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool exclusive)
+Tree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool exclusive)
{
- if (node == NULL) {
+ if (node == nullptr) {
return;
}
@@ -254,34 +274,38 @@ Http2DependencyTree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool ex
ink_assert(node->parent);
Node *new_parent = find(new_parent_id);
- if (new_parent == NULL) {
+ if (new_parent == nullptr) {
return;
}
_change_parent(new_parent, old_parent, false);
_change_parent(node, new_parent, exclusive);
+
+ // delete the shadow node
+ if (node->is_shadow() && node->children.empty() && node->queue->empty()) {
+ remove(node);
+ }
}
// Change node's parent to new_parent
template <typename T>
void
-Http2DependencyTree<T>::_change_parent(Node *node, Node *new_parent, bool exclusive)
+Tree<T>::_change_parent(Node *node, Node *new_parent, bool exclusive)
{
- ink_release_assert(node->parent != NULL);
+ ink_release_assert(node->parent != nullptr);
node->parent->children.remove(node);
if (node->queued) {
node->parent->queue->erase(node->entry);
node->queued = false;
Node *current = node->parent;
- while (current->queue->empty() && !current->active && current->parent != NULL) {
+ while (current->queue->empty() && !current->active && current->parent != nullptr) {
current->parent->queue->erase(current->entry);
current->queued = false;
current = current->parent;
}
}
- node->parent = NULL;
-
+ node->parent = nullptr;
if (exclusive) {
while (Node *child = new_parent->children.pop()) {
if (child->queued) {
@@ -299,7 +323,7 @@ Http2DependencyTree<T>::_change_parent(Node *node, Node *new_parent, bool exclus
if (node->active || !node->queue->empty()) {
Node *current = node;
- while (current->parent != NULL && !current->queued) {
+ while (current->parent != nullptr && !current->queued) {
current->parent->queue->push(current->entry);
current->queued = true;
current = current->parent;
@@ -308,18 +332,18 @@ Http2DependencyTree<T>::_change_parent(Node *node, Node *new_parent, bool exclus
}
template <typename T>
-typename Http2DependencyTree<T>::Node *
-Http2DependencyTree<T>::_top(Node *node)
+Node *
+Tree<T>::_top(Node *node)
{
Node *child = node;
- while (child != NULL) {
+ while (child != nullptr) {
if (child->active) {
return child;
} else if (!child->queue->empty()) {
child = child->queue->top()->node;
} else {
- return NULL;
+ return nullptr;
}
}
@@ -327,19 +351,19 @@ Http2DependencyTree<T>::_top(Node *node)
}
template <typename T>
-typename Http2DependencyTree<T>::Node *
-Http2DependencyTree<T>::top()
+Node *
+Tree<T>::top()
{
return _top(_root);
}
template <typename T>
void
-Http2DependencyTree<T>::activate(Node *node)
+Tree<T>::activate(Node *node)
{
node->active = true;
- while (node->parent != NULL && !node->queued) {
+ while (node->parent != nullptr && !node->queued) {
node->parent->queue->push(node->entry);
node->queued = true;
node = node->parent;
@@ -348,11 +372,11 @@ Http2DependencyTree<T>::activate(Node *node)
template <typename T>
void
-Http2DependencyTree<T>::deactivate(Node *node, uint32_t sent)
+Tree<T>::deactivate(Node *node, uint32_t sent)
{
node->active = false;
- while (node->queue->empty() && node->parent != NULL) {
+ while (node->queue->empty() && node->parent != nullptr) {
node->parent->queue->erase(node->entry);
node->queued = false;
@@ -364,9 +388,9 @@ Http2DependencyTree<T>::deactivate(Node *node, uint32_t sent)
template <typename T>
void
-Http2DependencyTree<T>::update(Node *node, uint32_t sent)
+Tree<T>::update(Node *node, uint32_t sent)
{
- while (node->parent != NULL) {
+ while (node->parent != nullptr) {
node->point += sent * K / (node->weight + 1);
if (node->queued) {
@@ -382,9 +406,9 @@ Http2DependencyTree<T>::update(Node *node, uint32_t sent)
template <typename T>
uint32_t
-Http2DependencyTree<T>::size() const
+Tree<T>::size() const
{
return _node_count;
}
-
+} // namespce Http2DependencyTree
#endif // __HTTP2_DEP_TREE_H__
diff --git a/proxy/http2/Http2Stream.h b/proxy/http2/Http2Stream.h
index 9387976..ed28b54 100644
--- a/proxy/http2/Http2Stream.h
+++ b/proxy/http2/Http2Stream.h
@@ -33,7 +33,7 @@
class Http2Stream;
class Http2ConnectionState;
-typedef Http2DependencyTree<Http2Stream *> DependencyTree;
+typedef Http2DependencyTree::Tree<Http2Stream *> DependencyTree;
class Http2Stream : public ProxyClientTransaction
{
@@ -193,10 +193,10 @@ public:
bool is_first_transaction_flag;
HTTPHdr response_header;
- IOBufferReader *response_reader;
- IOBufferReader *request_reader;
- MIOBuffer request_buffer;
- DependencyTree::Node *priority_node;
+ IOBufferReader *response_reader = nullptr;
+ IOBufferReader *request_reader = nullptr;
+ MIOBuffer request_buffer = CLIENT_CONNECTION_FIRST_READ_BUFFER_SIZE_INDEX;
+ Http2DependencyTree::Node *priority_node = nullptr;
EThread *
get_thread()
diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc
index a2249c3..20ee49c 100644
--- a/proxy/http2/test_Http2DependencyTree.cc
+++ b/proxy/http2/test_Http2DependencyTree.cc
@@ -31,7 +31,8 @@
using namespace std;
-using Tree = Http2DependencyTree<string *>;
+using Tree = Http2DependencyTree::Tree<std::string *>;
+using Node = Http2DependencyTree::Node;
/**
* Exclusive Dependency Creation
@@ -53,9 +54,9 @@ REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSE
tree->add(0, 1, 0, false, &b);
tree->add(0, 3, 0, false, &c);
- Tree::Node *node_a = tree->find(0);
- Tree::Node *node_b = tree->find(1);
- Tree::Node *node_c = tree->find(3);
+ Node *node_a = tree->find(0);
+ Node *node_b = tree->find(1);
+ Node *node_c = tree->find(3);
box.check(node_b->parent == node_a, "parent of B should be A");
box.check(node_c->parent == node_a, "parent of C should be A");
@@ -63,7 +64,7 @@ REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSE
// Add node with exclusive flag
tree->add(0, 5, 0, true, &d);
- Tree::Node *node_d = tree->find(5);
+ Node *node_d = tree->find(5);
box.check(node_d->parent == node_a, "parent of D should be A");
box.check(node_b->parent == node_d, "parent of B should be D");
@@ -102,10 +103,10 @@ REGRESSION_TEST(Http2DependencyTree_2)(RegressionTest *t, int /* atype ATS_UNUSE
tree->reprioritize(1, 7, false);
- Tree::Node *node_x = tree->find(0);
- Tree::Node *node_a = tree->find(1);
- Tree::Node *node_d = tree->find(7);
- Tree::Node *node_f = tree->find(11);
+ Node *node_x = tree->find(0);
+ Node *node_a = tree->find(1);
+ Node *node_d = tree->find(7);
+ Node *node_f = tree->find(11);
box.check(node_a->parent == node_d, "parent of A should be D");
box.check(node_d->parent == node_x, "parent of D should be X");
@@ -144,10 +145,10 @@ REGRESSION_TEST(Http2DependencyTree_3)(RegressionTest *t, int /* atype ATS_UNUSE
tree->reprioritize(1, 7, true);
- Tree::Node *node_x = tree->find(0);
- Tree::Node *node_a = tree->find(1);
- Tree::Node *node_d = tree->find(7);
- Tree::Node *node_f = tree->find(11);
+ Node *node_x = tree->find(0);
+ Node *node_a = tree->find(1);
+ Node *node_d = tree->find(7);
+ Node *node_f = tree->find(11);
box.check(node_a->parent == node_d, "parent of A should be D");
box.check(node_d->parent == node_x, "parent of D should be X");
@@ -171,15 +172,15 @@ REGRESSION_TEST(Http2DependencyTree_4)(RegressionTest *t, int /* atype ATS_UNUSE
string a("A");
tree->add(0, 1, 0, false, &a);
- Tree::Node *node_a = tree->find(1);
+ Node *node_a = tree->find(1);
- box.check(tree->top() == nullptr, "top should be NULL");
+ box.check(tree->top() == nullptr, "top should be nullptr");
tree->activate(node_a);
box.check(tree->top() == node_a, "top should be A");
tree->deactivate(node_a, 0);
- box.check(tree->top() == nullptr, "top should be NULL");
+ box.check(tree->top() == nullptr, "top should be nullptr");
delete tree;
}
@@ -204,10 +205,10 @@ REGRESSION_TEST(Http2DependencyTree_5)(RegressionTest *t, int /* atype ATS_UNUSE
tree->add(0, 3, 15, false, &a);
tree->add(3, 5, 15, false, &b);
- Tree::Node *node_a = tree->find(3);
- Tree::Node *node_b = tree->find(5);
+ Node *node_a = tree->find(3);
+ Node *node_b = tree->find(5);
- box.check(tree->top() == nullptr, "top should be NULL");
+ box.check(tree->top() == nullptr, "top should be nullptr");
tree->activate(node_a);
tree->activate(node_b);
@@ -239,9 +240,9 @@ REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSE
// NOTE, weight is actual weight - 1
tree->add(0, 3, 20, false, &a); // node_a is unused
- Tree::Node *node_b = tree->add(3, 5, 10, false, &b);
- Tree::Node *node_c = tree->add(3, 7, 10, false, &c);
- Tree::Node *node_d = tree->add(0, 9, 20, false, &d);
+ Node *node_b = tree->add(3, 5, 10, false, &b);
+ Node *node_c = tree->add(3, 7, 10, false, &c);
+ Node *node_d = tree->add(0, 9, 20, false, &d);
// Activate B, C and D
tree->activate(node_b);
@@ -251,8 +252,8 @@ REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSE
ostringstream oss;
for (int i = 0; i < 90; ++i) {
- Tree::Node *node = tree->top();
- oss << node->t->c_str();
+ Node *node = tree->top();
+ oss << static_cast<string *>(node->t)->c_str();
tree->update(node, 100);
}
@@ -279,15 +280,15 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_50)(RegressionTest *t, int /* atype A
string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"), g("G"), h("H"), i("I");
- Tree::Node *node_a = tree->add(0, 3, 255, false, &a);
- Tree::Node *node_b = tree->add(0, 5, 255, false, &b);
- Tree::Node *node_c = tree->add(0, 7, 255, false, &c);
- Tree::Node *node_d = tree->add(0, 9, 182, false, &d);
- Tree::Node *node_e = tree->add(0, 11, 182, false, &e);
- Tree::Node *node_f = tree->add(0, 13, 182, false, &f);
- Tree::Node *node_g = tree->add(0, 15, 146, false, &g);
- Tree::Node *node_h = tree->add(0, 17, 146, false, &h);
- Tree::Node *node_i = tree->add(0, 19, 146, false, &i);
+ Node *node_a = tree->add(0, 3, 255, false, &a);
+ Node *node_b = tree->add(0, 5, 255, false, &b);
+ Node *node_c = tree->add(0, 7, 255, false, &c);
+ Node *node_d = tree->add(0, 9, 182, false, &d);
+ Node *node_e = tree->add(0, 11, 182, false, &e);
+ Node *node_f = tree->add(0, 13, 182, false, &f);
+ Node *node_g = tree->add(0, 15, 146, false, &g);
+ Node *node_h = tree->add(0, 17, 146, false, &h);
+ Node *node_i = tree->add(0, 19, 146, false, &i);
// Activate nodes from A to I
tree->activate(node_a);
@@ -303,8 +304,8 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_50)(RegressionTest *t, int /* atype A
ostringstream oss;
for (int i = 0; i < 108; ++i) {
- Tree::Node *node = tree->top();
- oss << node->t->c_str();
+ Node *node = tree->top();
+ oss << static_cast<string *>(node->t)->c_str();
tree->update(node, 16375);
}
@@ -340,15 +341,15 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_51)(RegressionTest *t, int /* atype A
string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"), g("G"), h("H"), i("I");
- Tree::Node *node_a = tree->add(0, 3, 255, false, &a);
- Tree::Node *node_b = tree->add(3, 5, 255, false, &b);
- Tree::Node *node_c = tree->add(5, 7, 255, false, &c);
- Tree::Node *node_d = tree->add(7, 9, 182, false, &d);
- Tree::Node *node_e = tree->add(9, 11, 182, false, &e);
- Tree::Node *node_f = tree->add(11, 13, 182, false, &f);
- Tree::Node *node_g = tree->add(13, 15, 146, false, &g);
- Tree::Node *node_h = tree->add(15, 17, 146, false, &h);
- Tree::Node *node_i = tree->add(17, 19, 146, false, &i);
+ Node *node_a = tree->add(0, 3, 255, false, &a);
+ Node *node_b = tree->add(3, 5, 255, false, &b);
+ Node *node_c = tree->add(5, 7, 255, false, &c);
+ Node *node_d = tree->add(7, 9, 182, false, &d);
+ Node *node_e = tree->add(9, 11, 182, false, &e);
+ Node *node_f = tree->add(11, 13, 182, false, &f);
+ Node *node_g = tree->add(13, 15, 146, false, &g);
+ Node *node_h = tree->add(15, 17, 146, false, &h);
+ Node *node_i = tree->add(17, 19, 146, false, &i);
// Activate nodes A, C, E, G, and I
tree->activate(node_a);
@@ -360,9 +361,9 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_51)(RegressionTest *t, int /* atype A
ostringstream oss;
for (int i = 0; i < 9; ++i) {
- Tree::Node *node = tree->top();
+ Node *node = tree->top();
if (node != nullptr) {
- oss << node->t->c_str();
+ oss << static_cast<string *>(node->t)->c_str();
tree->deactivate(node, 16384);
tree->remove(node);
@@ -376,9 +377,9 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_51)(RegressionTest *t, int /* atype A
tree->activate(node_h);
for (int i = 0; i < 9; ++i) {
- Tree::Node *node = tree->top();
+ Node *node = tree->top();
if (node != nullptr) {
- oss << node->t->c_str();
+ oss << static_cast<string *>(node->t)->c_str();
tree->deactivate(node, 16384);
tree->remove(node);
@@ -412,16 +413,16 @@ REGRESSION_TEST(Http2DependencyTree_remove_1)(RegressionTest *t, int /* atype AT
string a("A"), b("B"), c("C");
// NOTE, weight is actual weight - 1
- Tree::Node *node_a = tree->add(0, 3, 30, false, &a);
- Tree::Node *node_b = tree->add(3, 5, 20, false, &b);
- Tree::Node *node_c = tree->add(3, 7, 10, false, &c);
+ Node *node_a = tree->add(0, 3, 30, false, &a);
+ Node *node_b = tree->add(3, 5, 20, false, &b);
+ Node *node_c = tree->add(3, 7, 10, false, &c);
// Activate A, B, and C
tree->activate(node_a);
tree->activate(node_b);
tree->activate(node_c);
- Tree::Node *top_node = nullptr;
+ Node *top_node = nullptr;
// Deactivate A and try to remove
top_node = tree->top();
@@ -468,9 +469,9 @@ REGRESSION_TEST(Http2DependencyTree_remove_2)(RegressionTest *t, int /* atype AT
string a("A"), b("B"), c("C");
// NOTE, weight is actual weight - 1
- Tree::Node *node_a = tree->add(0, 3, 20, false, &a);
- Tree::Node *node_b = tree->add(3, 5, 10, false, &b);
- Tree::Node *node_c = tree->add(5, 7, 10, false, &c);
+ Node *node_a = tree->add(0, 3, 20, false, &a);
+ Node *node_b = tree->add(3, 5, 10, false, &b);
+ Node *node_c = tree->add(5, 7, 10, false, &c);
// Activate, deactivate, and remove C
tree->activate(node_c);
@@ -490,7 +491,7 @@ REGRESSION_TEST(Http2DependencyTree_remove_2)(RegressionTest *t, int /* atype AT
tree->deactivate(node_b, 16384);
tree->remove(node_b);
- box.check(tree->top() == nullptr, "Top node should be NULL");
+ box.check(tree->top() == nullptr, "Top node should be nullptr");
box.check(tree->find(3) == nullptr, "Tree should be empty");
box.check(tree->find(5) == nullptr, "Tree should be empty");
box.check(tree->find(7) == nullptr, "Tree should be empty");
@@ -515,7 +516,7 @@ REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* at
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C"), d("D");
- Tree::Node *B = tree->add(0, 1, 0, false, &b);
+ Node *B = tree->add(0, 1, 0, false, &b);
tree->add(0, 3, 0, false, &c);
tree->activate(B);
@@ -525,7 +526,7 @@ REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* at
tree->deactivate(B, 0);
tree->remove(B);
- box.check(tree->top() == NULL, "Tree top should be NULL");
+ box.check(tree->top() == nullptr, "Tree top should be nullptr");
delete tree;
}
@@ -547,9 +548,9 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize)(RegressionTest *t, int /* atyp
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
- Tree::Node *A = tree->add(0, 7, 70, false, &a);
- Tree::Node *B = tree->add(0, 3, 10, false, &b);
- Tree::Node *C = tree->add(3, 5, 30, false, &c);
+ Node *A = tree->add(0, 7, 70, false, &a);
+ Node *B = tree->add(0, 3, 10, false, &b);
+ Node *C = tree->add(3, 5, 30, false, &c);
tree->activate(A);
tree->activate(B);
@@ -593,10 +594,10 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_2)(RegressionTest *t, int /* at
tree->add(5, 9, 0, false, &e);
tree->add(7, 11, 0, false, &f);
- Tree::Node *node_x = tree->find(0);
- Tree::Node *node_a = tree->find(1);
- Tree::Node *node_b = tree->find(3);
- Tree::Node *node_d = tree->find(7);
+ Node *node_x = tree->find(0);
+ Node *node_a = tree->find(1);
+ Node *node_b = tree->find(3);
+ Node *node_d = tree->find(7);
tree->activate(node_b);
box.check(node_x->queue->in(node_a->entry), "A should be in x's queue");
@@ -638,11 +639,11 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(RegressionTest *t, int /* at
tree->add(5, 9, 0, false, &e);
tree->add(7, 11, 0, false, &f);
- Tree::Node *node_x = tree->find(0);
- Tree::Node *node_a = tree->find(1);
- Tree::Node *node_c = tree->find(5);
- Tree::Node *node_d = tree->find(7);
- Tree::Node *node_f = tree->find(11);
+ Node *node_x = tree->find(0);
+ Node *node_a = tree->find(1);
+ Node *node_c = tree->find(5);
+ Node *node_d = tree->find(7);
+ Node *node_f = tree->find(11);
tree->activate(node_f);
tree->reprioritize(1, 7, true);
@@ -656,6 +657,98 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(RegressionTest *t, int /* at
delete tree;
}
+/** test for https://github.com/apache/trafficserver/issues/2268
+*
+* root root root
+* / =====> / \ =======> / \
+* A A shadow A shadow
+* \ \
+* B B
+* \
+* C
+*
+* root root
+* / \ /
+* ======> A shadow =======> A
+* \
+* C
+*/
+REGRESSION_TEST(Http2DependencyTree_insert_with_empty_parent)(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");
+ tree->add(0, 3, 20, false, &a);
+ Node *b_n = tree->add(5, 7, 30, true, &b);
+
+ box.check(b_n->parent->id == 5, "Node B's parent should be 5");
+ box.check(tree->find(5) == nullptr, "The shadow nodes should not be found");
+ box.check(tree->find_shadow(5)->is_shadow() == true, "nodes 5 should be the shadow node");
+
+ Node *c_n = tree->add(7, 9, 30, false, &c);
+ tree->remove(b_n);
+
+ box.check(c_n->parent->id == 5, "Node C's parent should be 5");
+ box.check(tree->find(7) == nullptr, "Nodes b should be removed");
+ box.check(tree->find_shadow(5)->is_shadow() == true, "Nodes 5 should be existed after removing");
+
+ tree->remove(c_n);
+ box.check(tree->find_shadow(5) == nullptr, "Shadow nodes should be remove");
+
+ delete tree;
+}
+
+/** test for https://github.com/apache/trafficserver/issues/2268
+*
+* root root root root
+* / =====> / \ =======> / \ =======> / \
+* A A shadow A B A B
+* \ \
+* B shadow
+*/
+REGRESSION_TEST(Http2DependencyTree_shadow_reprioritize)(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");
+ tree->add(0, 3, 20, false, &a);
+ tree->add(5, 7, 30, true, &b);
+
+ Node *s_n = tree->find_shadow(5);
+ box.check(s_n != nullptr && s_n->is_shadow() == true, "Shadow nodes should not be nullptr");
+
+ tree->reprioritize(s_n, 7, false);
+ box.check(tree->find_shadow(5) == nullptr, "Shadow nodes should be nullptr after reprioritizing");
+
+ delete tree;
+}
+
+REGRESSION_TEST(Http2DependencyTree_shadow_change)(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");
+
+ tree->add(0, 3, 20, false, &a);
+ tree->add(5, 7, 30, true, &b);
+
+ tree->add(0, 5, 15, false, &c);
+
+ Node *c_n = tree->find(5);
+ box.check(c_n != nullptr && c_n->is_shadow() == false, "Node 5 should not be shadow node");
+ box.check(c_n->point == 5 && c_n->weight == 15, "The weight and point should be 15");
+
+ delete tree;
+}
+
REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
{
TestBox box(t, pstatus);
@@ -668,8 +761,8 @@ REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype A
tree->add(i, i + 1, 16, false, &a);
}
- Tree::Node *node = tree->find(101);
- box.check(node->parent->id == 0, "101st node should be child of root node");
+ Node *node = tree->find(101);
+ box.check(node->parent->parent->id == 0, "101st node should be child of root's child node");
delete tree;
}
--
To stop receiving notification emails like this one, please contact
['"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>'].