proxygen: proxygen::HTTP2PriorityQueue::Node Class Reference

Inheritance diagram for proxygen::HTTP2PriorityQueue::Node:

Classes
struct	IdHash

struct	IdNodeEqual

struct	PendingNode

Public Types
using	PendingList = std::deque< PendingNode >

Public Member Functions
	Node (HTTP2PriorityQueue &queue, Node inParent, HTTPCodec::StreamID id, uint8_t weight, HTTPTransaction txn)

	~Node () override

void	setPermanent ()

Node *	getParent () const

HTTPCodec::StreamID	getID () const

HTTPCodec::StreamID	parentID () const

HTTPTransaction *	getTransaction () const

void	clearTransaction ()

Node *	emplaceNode (std::unique_ptr< Node > node, bool exclusive)

void	removeFromTree ()

void	signalPendingEgress ()

void	clearPendingEgress ()

uint16_t	getWeight () const

void	updateWeight (uint8_t weight)

Node *	reparent (Node *newParent, bool exclusive)

bool	isDescendantOf (Node *node) const

bool	isEnqueued () const override

bool	inEgressTree () const

double	getRelativeWeight () const

double	getRelativeEnqueuedWeight () const

bool	iterate (const std::function< bool(HTTPCodec::StreamID, HTTPTransaction *, double)> &fn, const std::function< bool()> &stopFn, bool all)

bool	visitBFS (double relativeParentWeight, const std::function< bool(HTTP2PriorityQueue &queue, HTTPCodec::StreamID, HTTPTransaction *, double)> &fn, bool all, PendingList &pendingNodes, bool enqueuedChildren)

void	updateEnqueuedWeight (bool activeNodes)

void	dropPriorityNodes ()

void	convertVirtualNode (HTTPTransaction *txn)

uint64_t	calculateDepth (bool includeVirtual=true) const override

void	flattenSubtree ()

void	flattenSubtreeDFS (Node *subtreeRoot)

Public Member Functions inherited from folly::HHWheelTimer::Callback
	Callback ()=default

virtual	~Callback ()

virtual void	callbackCanceled () noexcept

void	cancelTimeout ()

bool	isScheduled () const

std::chrono::milliseconds	getTimeRemaining ()

Static Public Member Functions
static void	addChildToNewSubtreeRoot (std::unique_ptr< Node > child, Node *subtreeRoot)

Static Public Attributes
static const uint16_t	kDefaultWeight = 16

Private Member Functions
Node *	addChild (std::unique_ptr< Node > child)

void	addChildren (std::list< std::unique_ptr< Node >> &&children)

std::unique_ptr< Node >	detachChild (Node *node)

void	addEnqueuedChild (HTTP2PriorityQueue::Node *node)

void	removeEnqueuedChild (HTTP2PriorityQueue::Node *node)

void	timeoutExpired () noexceptoverride

void	refreshTimeout ()

Static Private Member Functions
static void	propagatePendingEgressSignal (Node *node)

static void	propagatePendingEgressClear (Node *node)

Private Attributes
HTTP2PriorityQueue &	queue_

Node *	parent_ {nullptr}

HTTPCodec::StreamID	id_ {0}

uint16_t	weight_ {kDefaultWeight}

HTTPTransaction *	txn_ {nullptr}

bool	isPermanent_ {false}

bool	enqueued_ {false}

uint64_t	totalEnqueuedWeightCheck_ {0}

uint64_t	totalEnqueuedWeight_ {0}

uint64_t	totalChildWeight_ {0}

std::list< std::unique_ptr< Node > >	children_

std::list< std::unique_ptr< Node > >::iterator	self_

folly::IntrusiveListHook	enqueuedHook_

folly::IntrusiveList< Node,&Node::enqueuedHook_ >	enqueuedChildren_

Friends
bool	operator== (const Node &lhs, const Node &rhs)

std::size_t	hash_value (const Node &node)

Additional Inherited Members
Protected Member Functions inherited from folly::HHWheelTimer::Callback
virtual std::chrono::steady_clock::time_point	getCurTime ()

Detailed Description

Definition at line 196 of file HTTP2PriorityQueue.h.

Member Typedef Documentation

using proxygen::HTTP2PriorityQueue::Node::PendingList = std::deque<PendingNode>

Definition at line 336 of file HTTP2PriorityQueue.h.

Constructor & Destructor Documentation

proxygen::HTTP2PriorityQueue::Node::Node	(	HTTP2PriorityQueue &	queue,
		HTTP2PriorityQueue::Node *	inParent,
		HTTPCodec::StreamID	id,
		uint8_t	weight,
		HTTPTransaction *	txn
	)

Definition at line 21 of file HTTP2PriorityQueue.cpp.

References id_, proxygen::HTTP2PriorityQueue::nodes_, and queue_.

     : queue_(queue),
       parent_(inParent),
       id_(id),
       weight_(weight + 1),
       txn_(txn) {
   DCHECK(queue_.nodes_.find(id_,
                             IdHash(), IdNodeEqual()) == queue_.nodes_.end());
   queue_.nodes_.insert(*this);
 }

proxygen::HTTP2PriorityQueue::Node::~Node ( )

override

Definition at line 35 of file HTTP2PriorityQueue.cpp.

References proxygen::HTTP2PriorityQueue::numVirtualNodes_, queue_, and txn_.

                               {
   if (!txn_) {
     queue_.numVirtualNodes_--;
   }
 }

Member Function Documentation

HTTP2PriorityQueue::Node * proxygen::HTTP2PriorityQueue::Node::addChild ( std::unique_ptr< Node > child )

private

Definition at line 91 of file HTTP2PriorityQueue.cpp.

References folly::HHWheelTimer::Callback::cancelTimeout(), children_, id_, folly::gen::move, self_, and totalChildWeight_.

Referenced by addChildren(), and emplaceNode().

                                             {
   CHECK_NE(id_, child->id_) << "Tried to create a loop in the tree";
   child->parent_ = this;
   totalChildWeight_ += child->weight_;
   Node* raw = child.get();
   raw->self_ = children_.insert(children_.end(), std::move(child));
   cancelTimeout();
   return raw;
 }

void proxygen::HTTP2PriorityQueue::Node::addChildren ( std::list< std::unique_ptr< Node >> && children )

private

Definition at line 67 of file HTTP2PriorityQueue.cpp.

References addChild(), addEnqueuedChild(), child, inEgressTree(), folly::gen::move, propagatePendingEgressSignal(), folly::f14::swap(), totalEnqueuedWeight_, and uint64_t.

Referenced by removeFromTree().

                                                                      {
   list<unique_ptr<Node>> emptyChilden;
   uint64_t totalEnqueuedWeight = 0;
   for (auto& child: children) {
     if (child->inEgressTree()) {
       totalEnqueuedWeight += child->weight_;
       child->parent_->removeEnqueuedChild(child.get());
       CHECK(!child->enqueuedHook_.is_linked());
       addEnqueuedChild(child.get());
     } else {
       CHECK(!child->enqueuedHook_.is_linked());
     }
     addChild(std::move(child));
   }
   std::swap(children, emptyChilden);
   if (totalEnqueuedWeight > 0) {
     if (!inEgressTree()) {
       propagatePendingEgressSignal(this);
     }
     totalEnqueuedWeight_ += totalEnqueuedWeight;
   }
 }

void proxygen::HTTP2PriorityQueue::Node::addChildToNewSubtreeRoot	(	std::unique_ptr< Node >	child,
		Node *	subtreeRoot
	)

static

Definition at line 417 of file HTTP2PriorityQueue.cpp.

References children_, kDefaultWeight, folly::gen::move, and self_.

Referenced by flattenSubtree(), and flattenSubtreeDFS().

                                                                       {
   child->children_.clear();
   child->parent_ = subtreeRoot;
   child->weight_ = kDefaultWeight;
   child->totalChildWeight_ = 0;
   child->totalEnqueuedWeight_ = 0;
 #ifndef NDEBUG
   child->totalEnqueuedWeightCheck_ = 0;
 #endif
   Node* raw = child.get();
   raw->self_ = subtreeRoot->children_.insert(subtreeRoot->children_.end(),
                                              std::move(child));
 }

void proxygen::HTTP2PriorityQueue::Node::addEnqueuedChild ( HTTP2PriorityQueue::Node * node )

private

Definition at line 160 of file HTTP2PriorityQueue.cpp.

References enqueuedChildren_, and enqueuedHook_.

Referenced by addChildren(), and propagatePendingEgressSignal().

                                                                      {
   CHECK(!node->enqueuedHook_.is_linked());
   enqueuedChildren_.push_back(*node);
 }

uint64_t proxygen::HTTP2PriorityQueue::Node::calculateDepth ( bool includeVirtual = true ) const

override

Definition at line 365 of file HTTP2PriorityQueue.cpp.

References getParent(), txn_, and uint64_t.

Referenced by proxygen::HTTP2PriorityQueue::updatePriority().

                                                                 {
   uint64_t depth = 0;
   const Node* cur = this;
   while (cur->getParent() != nullptr) {
     if (cur->txn_ || includeVirtual) {
       depth += 1;
     }
     cur = cur->getParent();
   }
   return depth;
 }

void proxygen::HTTP2PriorityQueue::Node::clearPendingEgress ( )

Definition at line 195 of file HTTP2PriorityQueue.cpp.

References enqueued_, and propagatePendingEgressClear().

Referenced by proxygen::HTTP2PriorityQueue::removeTransaction().

                                            {
   CHECK(enqueued_);
   enqueued_ = false;
   propagatePendingEgressClear(this);
 }

void proxygen::HTTP2PriorityQueue::Node::clearTransaction ( )

inline

Definition at line 256 of file HTTP2PriorityQueue.h.

References proxygen::HTTP2PriorityQueueBase::clearPendingEgress(), and proxygen::HTTP2PriorityQueueBase::signalPendingEgress().

Referenced by proxygen::HTTP2PriorityQueue::removeTransaction().

                             {
       txn_ = nullptr;
     }

void proxygen::HTTP2PriorityQueue::Node::convertVirtualNode ( HTTPTransaction * txn )

Definition at line 355 of file HTTP2PriorityQueue.cpp.

References folly::HHWheelTimer::Callback::cancelTimeout(), isPermanent_, proxygen::HTTP2PriorityQueue::numVirtualNodes_, queue_, txn_, and uint64_t.

Referenced by proxygen::HTTP2PriorityQueue::addTransaction().

                                                                {
   CHECK(!txn_);
   CHECK(!isPermanent_);
   CHECK_GT(queue_.numVirtualNodes_, 0);
   queue_.numVirtualNodes_--;
   txn_ = txn;
   cancelTimeout();
 }

unique_ptr< HTTP2PriorityQueue::Node > proxygen::HTTP2PriorityQueue::Node::detachChild ( Node * node )

private

Definition at line 103 of file HTTP2PriorityQueue.cpp.

References children_, isEnqueued(), isPermanent_, folly::gen::move, parent_, queue_, proxygen::HTTP2PriorityQueue::scheduleNodeExpiration(), self_, totalChildWeight_, txn_, and weight_.

Referenced by removeFromTree(), and reparent().

                                               {
   CHECK(!node->isEnqueued());
   totalChildWeight_ -= node->weight_;
   auto it = node->self_;
   auto res = std::move(*node->self_);
   children_.erase(it);
   node->parent_ = nullptr;
   if (children_.empty() && !txn_ && !isPermanent_) {
     queue_.scheduleNodeExpiration(this);
   }
   return res;
 }

void proxygen::HTTP2PriorityQueue::Node::dropPriorityNodes ( )

Definition at line 344 of file HTTP2PriorityQueue.cpp.

References child, children_, isPermanent_, removeFromTree(), and txn_.

Referenced by proxygen::HTTP2PriorityQueue::detachThreadLocals().

                                           {
   for (auto it = children_.begin(); it != children_.end(); ) {
     auto& child = *it++;
     child->dropPriorityNodes();
   }
   if (!txn_ && !isPermanent_) {
     removeFromTree();
   }
 }

HTTP2PriorityQueue::Node * proxygen::HTTP2PriorityQueue::Node::emplaceNode	(	std::unique_ptr< Node >	node,
		bool	exclusive
	)

Definition at line 43 of file HTTP2PriorityQueue.cpp.

References addChild(), children_, id_, inEgressTree(), folly::gen::move, propagatePendingEgressClear(), folly::f14::swap(), totalChildWeight_, totalEnqueuedWeight_, and totalEnqueuedWeightCheck_.

Referenced by reparent().

                                                            {
   CHECK(!node->isEnqueued());
   list<unique_ptr<Node>> children;
   CHECK_NE(id_, node->id_) << "Tried to create a loop in the tree";
   if (exclusive) {
     // this->children become new node's children
     std::swap(children, children_);
     totalChildWeight_ = 0;
     bool wasInEgressTree = inEgressTree();
     totalEnqueuedWeight_ = 0;
 #ifndef NDEBUG
     totalEnqueuedWeightCheck_ = 0;
 #endif
     if (wasInEgressTree && !inEgressTree()) {
       propagatePendingEgressClear(this);
     }
   }
   auto res = addChild(std::move(node));
   res->addChildren(std::move(children));
   return res;
 }

void proxygen::HTTP2PriorityQueue::Node::flattenSubtree ( )

Definition at line 378 of file HTTP2PriorityQueue.cpp.

References addChildToNewSubtreeRoot(), child, children_, for_each(), folly::gen::move, folly::f14::swap(), totalChildWeight_, totalEnqueuedWeight_, and totalEnqueuedWeightCheck_.

Referenced by proxygen::HTTP2PriorityQueue::rebuildTree().

                                        {
   std::list<std::unique_ptr<Node>> oldChildren_;
   // Move the old children to a temporary list
   std::swap(oldChildren_, children_);
   // Reparent the children
   for (auto& child : oldChildren_) {
     child->flattenSubtreeDFS(this);
     addChildToNewSubtreeRoot(std::move(child), this);
   }
   // Update the weights
   totalEnqueuedWeight_ = 0;
 #ifndef NDEBUG
   totalEnqueuedWeightCheck_ = 0;
 #endif
   totalChildWeight_ = 0;
   std::for_each(
     children_.begin(),
     children_.end(),
     [this](const std::unique_ptr<Node>& child) {
       totalChildWeight_ += child->weight_;
       if (child->enqueued_) {
         totalEnqueuedWeight_ += child->weight_;
 #ifndef NDEBUG
         totalEnqueuedWeightCheck_ += child->weight_;
 #endif
       }
     }
   );
 }

void proxygen::HTTP2PriorityQueue::Node::flattenSubtreeDFS ( Node * subtreeRoot )

Definition at line 409 of file HTTP2PriorityQueue.cpp.

References addChildToNewSubtreeRoot(), child, children_, and folly::gen::move.

                                                            {
   for (auto& child : children_) {
     child->flattenSubtreeDFS(subtreeRoot);
     addChildToNewSubtreeRoot(std::move(child), subtreeRoot);
   }
 }

HTTPCodec::StreamID proxygen::HTTP2PriorityQueue::Node::getID ( ) const

inline

Definition at line 241 of file HTTP2PriorityQueue.h.

Referenced by proxygen::HTTP2PriorityQueue::addTransaction(), proxygen::HTTP2PriorityQueue::removeTransaction(), proxygen::HTTP2PriorityQueue::scheduleNodeExpiration(), and proxygen::HTTP2PriorityQueue::updatePriority().

                                     {
       return id_;
     }

Node* proxygen::HTTP2PriorityQueue::Node::getParent ( ) const

inline

Definition at line 237 of file HTTP2PriorityQueue.h.

Referenced by calculateDepth(), and proxygen::HTTP2PriorityQueue::updatePriority().

                             {
       return parent_;
     }

double proxygen::HTTP2PriorityQueue::Node::getRelativeEnqueuedWeight ( ) const

inline

Definition at line 301 of file HTTP2PriorityQueue.h.

Referenced by visitBFS().

                                              {
       if (!parent_) {
         return 1.0;
       }
 
       if (parent_->totalEnqueuedWeight_ == 0) {
         return 0.0;
       }
 
       return static_cast<double>(weight_) / parent_->totalEnqueuedWeight_;
     }

double proxygen::HTTP2PriorityQueue::Node::getRelativeWeight ( ) const

inline

Definition at line 293 of file HTTP2PriorityQueue.h.

Referenced by iterate().

                                      {
       if (!parent_) {
         return 1.0;
       }
 
       return static_cast<double>(weight_) / parent_->totalChildWeight_;
     }

HTTPTransaction* proxygen::HTTP2PriorityQueue::Node::getTransaction ( ) const

inline

Definition at line 252 of file HTTP2PriorityQueue.h.

                                             {
       return txn_;
     }

uint16_t proxygen::HTTP2PriorityQueue::Node::getWeight ( ) const

inline

Definition at line 270 of file HTTP2PriorityQueue.h.

References uint8_t.

                                {
       return weight_;
     }

bool proxygen::HTTP2PriorityQueue::Node::inEgressTree ( ) const

inline

Definition at line 289 of file HTTP2PriorityQueue.h.

References proxygen::HTTP2PriorityQueueBase::BaseNode::isEnqueued().

Referenced by addChildren(), emplaceNode(), propagatePendingEgressClear(), propagatePendingEgressSignal(), removeFromTree(), reparent(), and updateWeight().

                               {
       return isEnqueued() || totalEnqueuedWeight_ > 0;
     }

bool proxygen::HTTP2PriorityQueue::Node::isDescendantOf ( HTTP2PriorityQueue::Node * node ) const

Definition at line 145 of file HTTP2PriorityQueue.cpp.

References id_, and parent_.

Referenced by proxygen::HTTP2PriorityQueue::updatePriority().

                                                                          {
   Node* cur = parent_;
   while (cur) {
     if (cur->id_ == node->id_) {
       return true;
     }
     cur = cur->parent_;
   }
   return false;
 }

bool proxygen::HTTP2PriorityQueue::Node::isEnqueued ( ) const

inlineoverride

Definition at line 283 of file HTTP2PriorityQueue.h.

Referenced by detachChild(), iterate(), removeFromTree(), proxygen::HTTP2PriorityQueue::removeTransaction(), updateEnqueuedWeight(), and visitBFS().

                                      {
       return (txn_ != nullptr && enqueued_);
     }

bool proxygen::HTTP2PriorityQueue::Node::iterate	(	const std::function< bool(HTTPCodec::StreamID, HTTPTransaction *, double)> &	fn,
		const std::function< bool()> &	stopFn,
		bool	all
	)

Definition at line 261 of file HTTP2PriorityQueue.cpp.

References child, children_, getRelativeWeight(), id_, isEnqueued(), parent_, stop(), totalEnqueuedWeight_, totalEnqueuedWeightCheck_, and txn_.

                                                {
   bool stop = false;
   if (stopFn()) {
     return true;
   }
 #ifndef NDEBUG
   CHECK_EQ(totalEnqueuedWeight_, totalEnqueuedWeightCheck_);
 #endif
   if (parent_ /* exclude root */  && (all || isEnqueued())) {
     stop = fn(id_, txn_, getRelativeWeight());
   }
   for (auto& child: children_) {
     if (stop || stopFn()) {
       return true;
     }
     stop = child->iterate(fn, stopFn, all);
   }
   return stop;
 }

HTTPCodec::StreamID proxygen::HTTP2PriorityQueue::Node::parentID ( ) const

inline

Definition at line 245 of file HTTP2PriorityQueue.h.

Referenced by proxygen::HTTP2PriorityQueue::updatePriority().

                                        {
       if (parent_) {
         return parent_->id_;
       }
       return 0;
     }

void proxygen::HTTP2PriorityQueue::Node::propagatePendingEgressClear ( HTTP2PriorityQueue::Node * node )

staticprivate

Definition at line 202 of file HTTP2PriorityQueue.cpp.

References inEgressTree(), parent, parent_, removeEnqueuedChild(), stop(), totalEnqueuedWeight_, and weight_.

Referenced by clearPendingEgress(), emplaceNode(), removeFromTree(), and reparent().

                                 {
   Node* parent = node->parent_;
   bool stop = node->inEgressTree();
   // Continue subtracting node->weight_ from parent_->totalEnqueuedWeight_
   // as long as node state changes from egress-in-subtree to
   // no-egress-in-subtree
   while (parent && !stop) {
     CHECK_GE(parent->totalEnqueuedWeight_, node->weight_);
     parent->totalEnqueuedWeight_ -= node->weight_;
     parent->removeEnqueuedChild(node);
     stop = parent->inEgressTree();
     node = parent;
     parent = parent->parent_;
   }
 }

void proxygen::HTTP2PriorityQueue::Node::propagatePendingEgressSignal ( HTTP2PriorityQueue::Node * node )

staticprivate

Definition at line 178 of file HTTP2PriorityQueue.cpp.

References addEnqueuedChild(), inEgressTree(), parent, parent_, stop(), totalEnqueuedWeight_, and weight_.

Referenced by addChildren(), reparent(), and signalPendingEgress().

                                 {
   Node* parent = node->parent_;
   bool stop = node->totalEnqueuedWeight_ > 0;
   // Continue adding node->weight_ to parent_->totalEnqueuedWeight_ as
   // long as node state changed from no-egress-in-subtree to
   // egress-in-subtree
   while (parent && !stop) {
     stop = parent->inEgressTree();
     parent->totalEnqueuedWeight_ += node->weight_;
     parent->addEnqueuedChild(node);
     node = parent;
     parent = parent->parent_;
   }
 }

void proxygen::HTTP2PriorityQueue::Node::refreshTimeout ( )

inlineprivate

Definition at line 380 of file HTTP2PriorityQueue.h.

Referenced by updateWeight().

                           {
       if (!txn_ && !isPermanent_ && isScheduled()) {
         queue_.scheduleNodeExpiration(this);
       }
     }

void proxygen::HTTP2PriorityQueue::Node::removeEnqueuedChild ( HTTP2PriorityQueue::Node * node )

private

Definition at line 166 of file HTTP2PriorityQueue.cpp.

References enqueuedChildren_, and enqueuedHook_.

Referenced by propagatePendingEgressClear().

                                                                         {
   CHECK(node->enqueuedHook_.is_linked());
   enqueuedChildren_.erase(enqueuedChildren_.iterator_to(*node));
 }

void proxygen::HTTP2PriorityQueue::Node::removeFromTree ( )

Definition at line 233 of file HTTP2PriorityQueue.cpp.

References addChildren(), child, children_, detachChild(), inEgressTree(), isEnqueued(), max, folly::gen::move, parent_, propagatePendingEgressClear(), totalChildWeight_, totalEnqueuedWeight_, uint64_t, uint8_t, and weight_.

Referenced by dropPriorityNodes(), and proxygen::HTTP2PriorityQueue::removeTransaction().

                                        {
   if (!children_.empty()) {
     // update child weights so they sum to (approximately) this node's weight.
     double r = double(weight_) / totalChildWeight_;
     for (auto& child: children_) {
       uint64_t newWeight = std::max(uint64_t(child->weight_ * r), uint64_t(1));
       CHECK_LE(newWeight, 256);
       child->updateWeight(uint8_t(newWeight) - 1);
     }
   }
 
   CHECK(!isEnqueued());
   if (inEgressTree()) {
     // Gah this is tricky.
     // The children of this node are moving to this node's parent.  We need the
     // tree in a consistent state before calling addChildren, so mark the
     // current node's totalEnqueuedWeight_ as 0 and propagate the clear upwards.
     // addChildren will handle re-signalling egress.
     totalEnqueuedWeight_ = 0;
     propagatePendingEgressClear(this);
   }
 
   // move my children to my parent
   parent_->addChildren(std::move(children_));
   (void)parent_->detachChild(this);
 }

HTTP2PriorityQueue::Node * proxygen::HTTP2PriorityQueue::Node::reparent	(	HTTP2PriorityQueue::Node *	newParent,
		bool	exclusive
	)

Definition at line 117 of file HTTP2PriorityQueue.cpp.

References detachChild(), emplaceNode(), enqueued_, inEgressTree(), folly::gen::move, parent_, propagatePendingEgressClear(), propagatePendingEgressSignal(), totalEnqueuedWeight_, and uint64_t.

Referenced by proxygen::HTTP2PriorityQueue::updatePriority().

                                                    {
   // Save enqueued_ and totalEnqueuedWeight_, clear them and restore
   // after reparenting
   bool wasInEgressTree = inEgressTree();
   bool enqueued = enqueued_;
   uint64_t totalEnqueuedWeight = totalEnqueuedWeight_;
   totalEnqueuedWeight_ = 0;
   enqueued_ = false;
   if (wasInEgressTree) {
     propagatePendingEgressClear(this);
   }
 
   auto self = parent_->detachChild(this);
   (void)newParent->emplaceNode(std::move(self), exclusive);
 
   // Restore state
   enqueued_ = enqueued;
   if (wasInEgressTree) {
     propagatePendingEgressSignal(this);
   }
   totalEnqueuedWeight_ += totalEnqueuedWeight;
 
   return this;
 }

void proxygen::HTTP2PriorityQueue::Node::setPermanent ( )

inline

Definition at line 233 of file HTTP2PriorityQueue.h.

                         {
       isPermanent_ = true;
     }

void proxygen::HTTP2PriorityQueue::Node::signalPendingEgress ( )

Definition at line 172 of file HTTP2PriorityQueue.cpp.

References enqueued_, and propagatePendingEgressSignal().

                                             {
   enqueued_ = true;
   propagatePendingEgressSignal(this);
 }

void proxygen::HTTP2PriorityQueue::Node::timeoutExpired ( )

inlineoverrideprivatevirtualnoexcept

timeoutExpired() is invoked when the timeout has expired.

Implements folly::HHWheelTimer::Callback.

Definition at line 373 of file HTTP2PriorityQueue.h.

                                             {
       VLOG(5) << "Node=" << id_ << " expired";
       CHECK(txn_ == nullptr);
       queue_.pendingWeightChange_ = true;
       removeFromTree();
     }

void proxygen::HTTP2PriorityQueue::Node::updateEnqueuedWeight ( bool activeNodes )

Definition at line 325 of file HTTP2PriorityQueue.cpp.

References child, children_, enqueuedHook_, isEnqueued(), parent_, totalChildWeight_, totalEnqueuedWeightCheck_, and weight_.

Referenced by proxygen::HTTP2PriorityQueue::iterateBFS(), proxygen::HTTP2PriorityQueue::nextEgress(), and proxygen::HTTP2PriorityQueue::updateEnqueuedWeight().

                                                              {
   totalEnqueuedWeightCheck_ = totalChildWeight_;
   for (auto& child: children_) {
     child->updateEnqueuedWeight(activeNodes);
   }
   if (activeNodes) {
     if (totalEnqueuedWeightCheck_ == 0 && !isEnqueued()) {
       // Must only be called with activeCount_ > 0, root cannot be dequeued
       CHECK_NOTNULL(parent_)->totalEnqueuedWeightCheck_ -= weight_;
     } else {
       CHECK(parent_ == nullptr || enqueuedHook_.is_linked());
     }
   } else {
     totalEnqueuedWeightCheck_ = 0;
   }
 }

void proxygen::HTTP2PriorityQueue::Node::updateWeight ( uint8_t weight )

Definition at line 221 of file HTTP2PriorityQueue.cpp.

References inEgressTree(), int16_t, parent_, refreshTimeout(), totalChildWeight_, totalEnqueuedWeight_, and weight_.

Referenced by proxygen::HTTP2PriorityQueue::updatePriority().

                                                    {
   int16_t delta = weight - weight_ + 1;
   weight_ = weight + 1;
   parent_->totalChildWeight_ += delta;
   if (inEgressTree()) {
     parent_->totalEnqueuedWeight_ += delta;
   }
   refreshTimeout();
 }

bool proxygen::HTTP2PriorityQueue::Node::visitBFS	(	double	relativeParentWeight,
		const std::function< bool(HTTP2PriorityQueue &queue, HTTPCodec::StreamID, HTTPTransaction *, double)> &	fn,
		bool	all,
		PendingList &	pendingNodes,
		bool	enqueuedChildren
	)

Definition at line 285 of file HTTP2PriorityQueue.cpp.

References child, children_, enqueuedChildren_, getRelativeEnqueuedWeight(), id_, folly::pushmi::invoke, isEnqueued(), parent_, queue_, totalEnqueuedWeight_, totalEnqueuedWeightCheck_, and txn_.

Referenced by proxygen::HTTP2PriorityQueue::iterateBFS(), and proxygen::HTTP2PriorityQueue::nextEgress().

                                                     {
   bool invoke = (parent_ != nullptr && (all || isEnqueued()));
   auto relativeEnqueuedWeight = getRelativeEnqueuedWeight();
 
 #ifndef NDEBUG
   CHECK_EQ(totalEnqueuedWeight_, totalEnqueuedWeightCheck_);
 #endif
   // Add children when all==true, or for any not invoked node with
   // pending children
   if (all || (!invoke && totalEnqueuedWeight_ > 0)) {
     double newRelWeight = relativeParentWeight * relativeEnqueuedWeight;
     if (enqueuedChildren) {
       for (auto child = enqueuedChildren_.begin();
            child != enqueuedChildren_.end();
            child++) {
         pendingNodes.emplace_back(child->id_, &(*child), newRelWeight);
       }
     } else {
       for (auto& child: children_) {
         pendingNodes.emplace_back(child->id_, child.get(), newRelWeight);
       }
     }
   }
 
   // Invoke fn last in case it deletes this node
   if (invoke && fn(queue_, id_, txn_,
                    relativeParentWeight * relativeEnqueuedWeight)) {
     return true;
   }
 
   return false;
 }

Friends And Related Function Documentation

std::size_t hash_value ( const Node & node )

friend

Definition at line 229 of file HTTP2PriorityQueue.h.

                                                   {
       return IdHash()(node.id_);
     }

bool operator==	(	const Node &	lhs,
		const Node &	rhs
	)

friend

Definition at line 226 of file HTTP2PriorityQueue.h.

                                                              {
       return lhs.id_ == rhs.id_;
     }

Member Data Documentation

std::list<std::unique_ptr<Node> > proxygen::HTTP2PriorityQueue::Node::children_

private

Definition at line 398 of file HTTP2PriorityQueue.h.

Referenced by addChild(), addChildToNewSubtreeRoot(), detachChild(), dropPriorityNodes(), emplaceNode(), flattenSubtree(), flattenSubtreeDFS(), iterate(), removeFromTree(), updateEnqueuedWeight(), and visitBFS().

bool proxygen::HTTP2PriorityQueue::Node::enqueued_ {false}

private

Definition at line 392 of file HTTP2PriorityQueue.h.

Referenced by clearPendingEgress(), reparent(), and signalPendingEgress().

folly::IntrusiveList<Node, &Node::enqueuedHook_> proxygen::HTTP2PriorityQueue::Node::enqueuedChildren_

private

Definition at line 404 of file HTTP2PriorityQueue.h.

Referenced by addEnqueuedChild(), removeEnqueuedChild(), and visitBFS().

folly::IntrusiveListHook proxygen::HTTP2PriorityQueue::Node::enqueuedHook_

private

Definition at line 403 of file HTTP2PriorityQueue.h.

Referenced by addEnqueuedChild(), removeEnqueuedChild(), and updateEnqueuedWeight().

HTTPCodec::StreamID proxygen::HTTP2PriorityQueue::Node::id_ {0}

private

Definition at line 388 of file HTTP2PriorityQueue.h.

Referenced by addChild(), emplaceNode(), isDescendantOf(), iterate(), Node(), proxygen::HTTP2PriorityQueue::Node::IdNodeEqual::operator()(), and visitBFS().

bool proxygen::HTTP2PriorityQueue::Node::isPermanent_ {false}

private

Definition at line 391 of file HTTP2PriorityQueue.h.

Referenced by convertVirtualNode(), detachChild(), and dropPriorityNodes().

const uint16_t proxygen::HTTP2PriorityQueue::Node::kDefaultWeight = 16

static

Definition at line 201 of file HTTP2PriorityQueue.h.

Referenced by addChildToNewSubtreeRoot().

Node* proxygen::HTTP2PriorityQueue::Node::parent_ {nullptr}

private

Definition at line 387 of file HTTP2PriorityQueue.h.

Referenced by detachChild(), isDescendantOf(), iterate(), propagatePendingEgressClear(), propagatePendingEgressSignal(), removeFromTree(), reparent(), updateEnqueuedWeight(), updateWeight(), and visitBFS().

HTTP2PriorityQueue& proxygen::HTTP2PriorityQueue::Node::queue_

private

Definition at line 386 of file HTTP2PriorityQueue.h.

Referenced by convertVirtualNode(), detachChild(), Node(), visitBFS(), and ~Node().

std::list<std::unique_ptr<Node> >::iterator proxygen::HTTP2PriorityQueue::Node::self_

private

Definition at line 399 of file HTTP2PriorityQueue.h.

Referenced by addChild(), addChildToNewSubtreeRoot(), and detachChild().

uint64_t proxygen::HTTP2PriorityQueue::Node::totalChildWeight_ {0}

private

Definition at line 397 of file HTTP2PriorityQueue.h.

Referenced by addChild(), detachChild(), emplaceNode(), flattenSubtree(), removeFromTree(), updateEnqueuedWeight(), and updateWeight().

uint64_t proxygen::HTTP2PriorityQueue::Node::totalEnqueuedWeight_ {0}

private

Definition at line 396 of file HTTP2PriorityQueue.h.

Referenced by addChildren(), emplaceNode(), flattenSubtree(), iterate(), propagatePendingEgressClear(), propagatePendingEgressSignal(), removeFromTree(), reparent(), updateWeight(), and visitBFS().

uint64_t proxygen::HTTP2PriorityQueue::Node::totalEnqueuedWeightCheck_ {0}

private

Definition at line 394 of file HTTP2PriorityQueue.h.

Referenced by emplaceNode(), flattenSubtree(), iterate(), updateEnqueuedWeight(), and visitBFS().

HTTPTransaction* proxygen::HTTP2PriorityQueue::Node::txn_ {nullptr}

private

Definition at line 390 of file HTTP2PriorityQueue.h.

Referenced by calculateDepth(), convertVirtualNode(), detachChild(), dropPriorityNodes(), iterate(), visitBFS(), and ~Node().

uint16_t proxygen::HTTP2PriorityQueue::Node::weight_ {kDefaultWeight}

private

Definition at line 389 of file HTTP2PriorityQueue.h.

Referenced by detachChild(), propagatePendingEgressClear(), propagatePendingEgressSignal(), removeFromTree(), updateEnqueuedWeight(), and updateWeight().

The documentation for this class was generated from the following files:

proxygen/lib/http/session/HTTP2PriorityQueue.h
proxygen/lib/http/session/HTTP2PriorityQueue.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation