trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sc...@apache.org
Subject [trafficserver] branch master updated: Fix the implementation of Http2DependencyTree
Date Tue, 05 Sep 2017 08:53:47 GMT
This is an automated email from the ASF dual-hosted git repository.

scw00 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 f367a30  Fix the implementation of Http2DependencyTree
f367a30 is described below

commit f367a3032a8e0a172e77b5180ddee3257adb6f31
Author: scw00 <scw00@apache.org>
AuthorDate: Fri Sep 1 10:17:43 2017 +0800

    Fix the implementation of Http2DependencyTree
---
 proxy/http2/Http2ConnectionState.cc     |  14 +-
 proxy/http2/Http2DependencyTree.h       | 229 ++++++++++++++++--------------
 proxy/http2/Http2Stream.h               |  10 +-
 proxy/http2/test_Http2DependencyTree.cc | 237 ++++++++++++++++++++++----------
 4 files changed, 304 insertions(+), 186 deletions(-)

diff --git a/proxy/http2/Http2ConnectionState.cc b/proxy/http2/Http2ConnectionState.cc
index 1e64aa3..d4bb301 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
@@ -1114,7 +1114,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);
@@ -1187,7 +1187,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());
@@ -1204,14 +1204,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);
 
@@ -1519,7 +1519,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..d4b44ee 100644
--- a/proxy/http2/Http2DependencyTree.h
+++ b/proxy/http2/Http2DependencyTree.h
@@ -37,80 +37,80 @@
 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 +126,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 +155,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 +212,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 +237,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 +260,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 +275,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 +324,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 +333,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 +352,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 +373,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 +389,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 +407,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 d9828cc..8d299fb 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
 {
@@ -167,10 +167,10 @@ public:
   bool is_first_transaction_flag = false;
 
   HTTPHdr response_header;
-  IOBufferReader *response_reader     = nullptr;
-  IOBufferReader *request_reader      = nullptr;
-  MIOBuffer request_buffer            = CLIENT_CONNECTION_FIRST_READ_BUFFER_SIZE_INDEX;
-  DependencyTree::Node *priority_node = nullptr;
+  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 712f76c..20ee49c 100644
--- a/proxy/http2/test_Http2DependencyTree.cc
+++ b/proxy/http2/test_Http2DependencyTree.cc
@@ -31,7 +31,8 @@
 
 using namespace std;
 
-using Tree = Http2DependencyTree<std::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() == nullptr, "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" <commits@trafficserver.apache.org>'].

Mime
View raw message