1 files changed, 30 insertions, 254 deletions

diff --git a/deps/nghttp3/lib/nghttp3_tnode.c b/deps/nghttp3/lib/nghttp3_tnode.c
index b6f6b787436..94dca7dbf76 100644
--- a/deps/nghttp3/lib/nghttp3_tnode.c
+++ b/deps/nghttp3/lib/nghttp3_tnode.c
@@ -29,6 +29,7 @@
 #include "nghttp3_macro.h"
 #include "nghttp3_stream.h"
 #include "nghttp3_conn.h"
+#include "nghttp3_conv.h"
 
 nghttp3_node_id *nghttp3_node_id_init(nghttp3_node_id *nid,
                                       nghttp3_node_id_type type, int64_t id) {
@@ -41,294 +42,69 @@ int nghttp3_node_id_eq(const nghttp3_node_id *a, const nghttp3_node_id *b) {
   return a->type == b->type && a->id == b->id;
 }
 
-static int cycle_less(const nghttp3_pq_entry *lhsx,
-                      const nghttp3_pq_entry *rhsx) {
-  const nghttp3_tnode *lhs = nghttp3_struct_of(lhsx, nghttp3_tnode, pe);
-  const nghttp3_tnode *rhs = nghttp3_struct_of(rhsx, nghttp3_tnode, pe);
-
-  if (lhs->cycle == rhs->cycle) {
-    return lhs->seq < rhs->seq;
-  }
-
-  return rhs->cycle - lhs->cycle <= NGHTTP3_TNODE_MAX_CYCLE_GAP;
-}
-
 void nghttp3_tnode_init(nghttp3_tnode *tnode, const nghttp3_node_id *nid,
-                        uint64_t seq, uint32_t weight, nghttp3_tnode *parent,
-                        const nghttp3_mem *mem) {
-  nghttp3_pq_init(&tnode->pq, cycle_less, mem);
+                        uint64_t seq, uint8_t pri) {
+  assert(nghttp3_pri_uint8_urgency(pri) < NGHTTP3_URGENCY_LEVELS);
 
   tnode->pe.index = NGHTTP3_PQ_BAD_INDEX;
   tnode->nid = *nid;
   tnode->seq = seq;
   tnode->cycle = 0;
-  tnode->pending_penalty = 0;
-  tnode->weight = weight;
-  tnode->parent = parent;
-  tnode->first_child = NULL;
-  tnode->num_children = 0;
-  tnode->active = 0;
-
-  if (parent) {
-    tnode->next_sibling = parent->first_child;
-    parent->first_child = tnode;
-    ++parent->num_children;
-  } else {
-    tnode->next_sibling = NULL;
-  }
+  tnode->pri = pri;
 }
 
-void nghttp3_tnode_free(nghttp3_tnode *tnode) { nghttp3_pq_free(&tnode->pq); }
-
-int nghttp3_tnode_is_active(nghttp3_tnode *tnode) {
-  nghttp3_push_promise *pp;
+void nghttp3_tnode_free(nghttp3_tnode *tnode) { (void)tnode; }
 
-  switch (tnode->nid.type) {
-  case NGHTTP3_NODE_ID_TYPE_STREAM:
-    return nghttp3_stream_is_active(
-        nghttp3_struct_of(tnode, nghttp3_stream, node));
-  case NGHTTP3_NODE_ID_TYPE_PUSH:
-    pp = nghttp3_struct_of(tnode, nghttp3_push_promise, node);
-    return pp->stream && nghttp3_stream_is_active(pp->stream);
-  case NGHTTP3_NODE_ID_TYPE_UT:
-    /* For unit test */
-    return tnode->active;
-  default:
-    return 0;
-  }
-}
-
-static void tnode_unschedule(nghttp3_tnode *tnode) {
-  nghttp3_tnode *parent;
-
-  for (parent = tnode->parent; parent; tnode = parent, parent = tnode->parent) {
-    assert(tnode->pe.index != NGHTTP3_PQ_BAD_INDEX);
-
-    nghttp3_pq_remove(&parent->pq, &tnode->pe);
-    tnode->pe.index = NGHTTP3_PQ_BAD_INDEX;
-
-    if (nghttp3_tnode_is_active(parent) || !nghttp3_pq_empty(&parent->pq)) {
-      return;
-    }
-  }
-}
-
-void nghttp3_tnode_unschedule(nghttp3_tnode *tnode) {
-  if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX ||
-      !nghttp3_pq_empty(&tnode->pq)) {
-    return;
-  }
+static void tnode_unschedule(nghttp3_tnode *tnode, nghttp3_pq *pq) {
+  assert(tnode->pe.index != NGHTTP3_PQ_BAD_INDEX);
 
-  tnode_unschedule(tnode);
+  nghttp3_pq_remove(pq, &tnode->pe);
+  tnode->pe.index = NGHTTP3_PQ_BAD_INDEX;
 }
 
-void nghttp3_tnode_unschedule_detach(nghttp3_tnode *tnode) {
+void nghttp3_tnode_unschedule(nghttp3_tnode *tnode, nghttp3_pq *pq) {
   if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX) {
     return;
   }
 
-  tnode_unschedule(tnode);
-}
-
-static int tnode_schedule(nghttp3_tnode *tnode, nghttp3_tnode *parent,
-                          uint64_t base_cycle, size_t nwrite) {
-  uint64_t penalty =
-      (uint64_t)nwrite * NGHTTP3_MAX_WEIGHT + tnode->pending_penalty;
-
-  tnode->cycle = base_cycle + penalty / tnode->weight;
-  tnode->pending_penalty = (uint32_t)(penalty % tnode->weight);
-
-  return nghttp3_pq_push(&parent->pq, &tnode->pe);
+  tnode_unschedule(tnode, pq);
 }
 
-static uint64_t tnode_get_first_cycle(nghttp3_tnode *tnode) {
+static uint64_t pq_get_first_cycle(nghttp3_pq *pq) {
   nghttp3_tnode *top;
 
-  if (nghttp3_pq_empty(&tnode->pq)) {
+  if (nghttp3_pq_empty(pq)) {
     return 0;
   }
 
-  top = nghttp3_struct_of(nghttp3_pq_top(&tnode->pq), nghttp3_tnode, pe);
+  top = nghttp3_struct_of(nghttp3_pq_top(pq), nghttp3_tnode, pe);
   return top->cycle;
 }
 
-int nghttp3_tnode_schedule(nghttp3_tnode *tnode, size_t nwrite) {
-  nghttp3_tnode *parent;
-  uint64_t cycle;
-  int rv;
+int nghttp3_tnode_schedule(nghttp3_tnode *tnode, nghttp3_pq *pq,
+                           size_t nwrite) {
+  uint64_t penalty = nwrite / NGHTTP3_STREAM_MIN_WRITELEN;
 
-  for (parent = tnode->parent; parent; tnode = parent, parent = tnode->parent) {
-    if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX) {
-      cycle = tnode_get_first_cycle(parent);
-    } else if (nwrite != 0) {
-      cycle = tnode->cycle;
-      nghttp3_pq_remove(&parent->pq, &tnode->pe);
-      tnode->pe.index = NGHTTP3_PQ_BAD_INDEX;
-    } else {
+  if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX) {
+    tnode->cycle = pq_get_first_cycle(pq) +
+                   ((nwrite == 0 || !nghttp3_pri_uint8_inc(tnode->pri))
+                        ? 0
+                        : nghttp3_max(1, penalty));
+  } else if (nwrite > 0) {
+    if (!nghttp3_pri_uint8_inc(tnode->pri) || nghttp3_pq_size(pq) == 1) {
       return 0;
     }
 
-    rv = tnode_schedule(tnode, parent, cycle, nwrite);
-    if (rv != 0) {
-      return rv;
-    }
+    nghttp3_pq_remove(pq, &tnode->pe);
+    tnode->pe.index = NGHTTP3_PQ_BAD_INDEX;
+    tnode->cycle += nghttp3_max(1, penalty);
+  } else {
+    return 0;
   }
 
-  return 0;
+  return nghttp3_pq_push(pq, &tnode->pe);
 }
 
 int nghttp3_tnode_is_scheduled(nghttp3_tnode *tnode) {
   return tnode->pe.index != NGHTTP3_PQ_BAD_INDEX;
 }
-
-nghttp3_tnode *nghttp3_tnode_get_next(nghttp3_tnode *tnode) {
-  if (nghttp3_pq_empty(&tnode->pq)) {
-    return NULL;
-  }
-
-  tnode = nghttp3_struct_of(nghttp3_pq_top(&tnode->pq), nghttp3_tnode, pe);
-
-  for (;;) {
-    if (nghttp3_tnode_is_active(tnode)) {
-      return tnode;
-    }
-    assert(!nghttp3_pq_empty(&tnode->pq));
-    tnode = nghttp3_struct_of(nghttp3_pq_top(&tnode->pq), nghttp3_tnode, pe);
-    assert(tnode);
-  }
-}
-
-void nghttp3_tnode_insert(nghttp3_tnode *tnode, nghttp3_tnode *parent) {
-  assert(tnode->parent == NULL);
-  assert(tnode->next_sibling == NULL);
-  assert(tnode->pe.index == NGHTTP3_PQ_BAD_INDEX);
-
-  tnode->next_sibling = parent->first_child;
-  parent->first_child = tnode;
-  tnode->parent = parent;
-  ++parent->num_children;
-}
-
-int nghttp3_tnode_insert_exclusive(nghttp3_tnode *tnode,
-                                   nghttp3_tnode *parent) {
-  nghttp3_tnode **p, *node;
-  int rv;
-
-  for (node = parent->first_child; node; node = node->next_sibling) {
-    node->parent = tnode;
-
-    if (node->pe.index == NGHTTP3_PQ_BAD_INDEX) {
-      continue;
-    }
-
-    nghttp3_pq_remove(&parent->pq, &node->pe);
-    node->pe.index = NGHTTP3_PQ_BAD_INDEX;
-  }
-
-  for (p = &tnode->first_child; *p; p = &(*p)->next_sibling)
-    ;
-
-  *p = parent->first_child;
-  parent->first_child = NULL;
-  tnode->num_children += parent->num_children;
-  parent->num_children = 0;
-
-  nghttp3_tnode_insert(tnode, parent);
-
-  for (node = *p; node; node = node->next_sibling) {
-    if (nghttp3_tnode_is_active(node) ||
-        nghttp3_tnode_has_active_descendant(node)) {
-      rv = nghttp3_tnode_schedule(node, 0);
-      if (rv != 0) {
-        return rv;
-      }
-    }
-  }
-
-  return 0;
-}
-
-void nghttp3_tnode_remove(nghttp3_tnode *tnode) {
-  nghttp3_tnode *parent = tnode->parent, **p;
-
-  assert(parent);
-
-  if (tnode->pe.index != NGHTTP3_PQ_BAD_INDEX) {
-    nghttp3_tnode_unschedule_detach(tnode);
-  }
-
-  for (p = &parent->first_child; *p != tnode; p = &(*p)->next_sibling)
-    ;
-
-  *p = tnode->next_sibling;
-  --parent->num_children;
-  tnode->parent = tnode->next_sibling = NULL;
-}
-
-int nghttp3_tnode_squash(nghttp3_tnode *tnode) {
-  nghttp3_tnode *parent = tnode->parent, *node, **p, *first, *end;
-  int rv;
-
-  assert(parent);
-
-  for (p = &parent->first_child; *p != tnode; p = &(*p)->next_sibling)
-    ;
-
-  *p = tnode->first_child;
-
-  for (; *p; p = &(*p)->next_sibling) {
-    node = *p;
-    node->parent = parent;
-    node->weight =
-        (uint32_t)(node->weight * tnode->weight / tnode->num_children);
-    if (node->weight == 0) {
-      node->weight = 1;
-    }
-
-    if (node->pe.index == NGHTTP3_PQ_BAD_INDEX) {
-      continue;
-    }
-
-    nghttp3_pq_remove(&tnode->pq, &node->pe);
-    node->pe.index = NGHTTP3_PQ_BAD_INDEX;
-  }
-
-  *p = tnode->next_sibling;
-
-  first = tnode->first_child;
-  end = tnode->next_sibling;
-
-  if (tnode->pe.index != NGHTTP3_PQ_BAD_INDEX) {
-    nghttp3_tnode_unschedule(tnode);
-    assert(tnode->pe.index == NGHTTP3_PQ_BAD_INDEX);
-  }
-
-  parent->num_children += tnode->num_children;
-  tnode->num_children = 0;
-  tnode->parent = tnode->next_sibling = tnode->first_child = NULL;
-
-  for (node = first; node && node != end; node = node->next_sibling) {
-    if (nghttp3_tnode_is_active(node) ||
-        nghttp3_tnode_has_active_descendant(node)) {
-      rv = nghttp3_tnode_schedule(node, 0);
-      if (rv != 0) {
-        return rv;
-      }
-    }
-  }
-
-  return 0;
-}
-
-nghttp3_tnode *nghttp3_tnode_find_ascendant(nghttp3_tnode *tnode,
-                                            const nghttp3_node_id *nid) {
-  for (tnode = tnode->parent; tnode && !nghttp3_node_id_eq(nid, &tnode->nid);
-       tnode = tnode->parent)
-    ;
-
-  return tnode;
-}
-
-int nghttp3_tnode_has_active_descendant(nghttp3_tnode *tnode) {
-  return !nghttp3_pq_empty(&tnode->pq);
-}