1 files changed, 72 insertions, 0 deletions
diff --git a/libs/mpi/src/computation_tree.cpp b/libs/mpi/src/computation_tree.cpp
new file mode 100644
index 000000000..60de534d1
--- /dev/null
+++ b/libs/mpi/src/computation_tree.cpp
@@ -0,0 +1,72 @@
+// Copyright (C) 2005 Douglas Gregor.
+
+// Use, modification and distribution is subject to the Boost Software
+// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// Compute parents, children, levels, etc. to effect a parallel
+// computation tree.
+
+#include <boost/mpi/detail/computation_tree.hpp>
+
+namespace boost { namespace mpi { namespace detail {
+
+int computation_tree::default_branching_factor = 3;
+
+computation_tree
+::computation_tree(int rank, int size, int root, int branching_factor)
+  : rank(rank), size(size), root(root),
+    branching_factor_(branching_factor > 1? branching_factor
+                      /* default */: default_branching_factor),
+    level_(0)
+{
+  // The position in the tree, once we've adjusted for non-zero
+  // roots.
+  int n = (rank + size - root) % size;
+  int sum = 0;
+  int term = 1;
+
+  /* The level is the smallest value of k such that
+
+  f^0 + f^1 + ... + f^k > n
+
+  for branching factor f and index n in the tree. */
+  while (sum <= n) {
+    ++level_;
+    term *= branching_factor_;
+    sum += term;
+  }
+}
+
+int computation_tree::level_index(int n) const
+{
+  int sum = 0;
+  int term = 1;
+  while (n--) {
+    sum += term;
+    term *= branching_factor_;
+  }
+  return sum;
+}
+
+int computation_tree::parent() const
+{
+  if (rank == root) return rank;
+  int n = rank + size - 1 - root;
+  return ((n % size / branching_factor_) + root) % size ;
+}
+
+int computation_tree::child_begin() const
+{
+  // Zero-based index of this node
+  int n = (rank + size - root) % size;
+
+  // Compute the index of the child (in a zero-based tree)
+  int child_index = level_index(level_ + 1)
+    + branching_factor_ * (n - level_index(level_));
+
+  if (child_index >= size) return root;
+  else return (child_index + root) % size;
+}
+
+} } } // end namespace boost::mpi::detail