This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a commit to branch 1.8.x
in repository https://gitbox.apache.org/repos/asf/mesos.git
commit 956f631247e51a310b5180af5f032077f2059250
Author: Meng Zhu <m...@mesosphere.io>
AuthorDate: Tue Apr 23 18:44:33 2019 -0700
Added a random sorter helper to find active internal nodes.
Active internal nodes are defined as internal nodes that have
at least one active leaf node.
Review: https://reviews.apache.org/r/70542
---
src/master/allocator/sorter/random/sorter.cpp | 39 +++++++++++++++++++++++++++
src/master/allocator/sorter/random/sorter.hpp | 5 ++++
2 files changed, 44 insertions(+)
diff --git a/src/master/allocator/sorter/random/sorter.cpp
b/src/master/allocator/sorter/random/sorter.cpp
index 183a903..ad06b0b 100644
--- a/src/master/allocator/sorter/random/sorter.cpp
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -545,6 +545,45 @@ double RandomSorter::getWeight(const Node* node) const
}
+hashset<RandomSorter::Node*> RandomSorter::activeInternalNodes() const
+{
+ // Using post-order traversal to find all the internal nodes
+ // that have at least one active leaf descendant and store
+ // them in the input `result` hashset.
+ //
+ // Returns true if the subtree at the input `node` contains any
+ // active leaf node.
+ std::function<bool(Node*, hashset<Node*>&)> searchActiveInternal =
+ [&searchActiveInternal](Node* node, hashset<Node*>& result) {
+ switch (node->kind) {
+ case Node::ACTIVE_LEAF: return true;
+
+ case Node::INACTIVE_LEAF: return false;
+
+ case Node::INTERNAL: {
+ bool active = false;
+ foreach (Node* child, node->children) {
+ if (searchActiveInternal(child, result)) {
+ active = true;
+ }
+ }
+
+ if (active) {
+ result.insert(node);
+ }
+ return active;
+ }
+ }
+ UNREACHABLE();
+ };
+
+ hashset<Node*> result;
+ searchActiveInternal(root, result);
+
+ return result;
+}
+
+
RandomSorter::Node* RandomSorter::find(const string& clientPath) const
{
Option<Node*> client_ = clients.get(clientPath);
diff --git a/src/master/allocator/sorter/random/sorter.hpp
b/src/master/allocator/sorter/random/sorter.hpp
index 125ce84..0c2d645 100644
--- a/src/master/allocator/sorter/random/sorter.hpp
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -29,6 +29,7 @@
#include <stout/check.hpp>
#include <stout/hashmap.hpp>
+#include <stout/hashset.hpp>
#include <stout/option.hpp>
#include "common/resource_quantities.hpp"
@@ -123,6 +124,10 @@ private:
// returned.
double getWeight(const Node* node) const;
+ // Get active internal nodes -- internal nodes that have at least
+ // one active leaf descendant.
+ hashset<Node*> activeInternalNodes() const;
+
// Returns the client associated with the given path. Returns
// nullptr if the path is not found or if the path identifies an
// internal node in the tree (not a client).
