[mesos] 01/03: Added a random sorter helper to find active internal nodes.

[mz...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

mzhu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mesos.git

commit 5e52c686c29819113f42c6bde7d90324673b42dc
Author: Meng Zhu <mz...@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).