Skip to content

Instantly share code, notes, and snippets.

@dillonhicks

dillonhicks/slab-allocated-subtree.cpp

Created August 14, 2020 16:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dillonhicks/da7f8f220229f84b198a1a84259656b4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dillonhicks/da7f8f220229f84b198a1a84259656b4 to your computer and use it in GitHub Desktop.
Download ZIP
Perfect N-Ary Trees Using Slab Allocated Subtrees
Raw
slab-allocated-subtree.cpp
/*
// https://godbolt.org/z/avdEMh
$ g++ -O3 -std=c++17 templatenodes.cpp -o templatenodes
$ ./templatenodes
(0) -- 16 bytes {root}
(1) ---- 8 bytes
(2) ------ 4 bytes
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(2) ------ 4 bytes
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(1) ---- 8 bytes
(2) ------ 4 bytes
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(2) ------ 4 bytes
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
(3) -------- 2 bytes
(4) ---------- 1 bytes {leaf}
(4) ---------- 1 bytes {leaf}
*/
#include <atomic>
#include <iostream>
#include <memory>
#include <array>
#include <ostream>
#include <optional>
#include <numeric>
#include <unordered_set>
using level_t = uint32_t;
using dimension_t = uint8_t;
using node_id_t = uint64_t;
#if !defined(TREE_BLOCK_LEVELS)
#define TREE_BLOCK_LEVELS 4
#endif // !defined(TREE_BLOCK_LEVELS)
constexpr auto TreeBlockLevels() -> level_t {
return TREE_BLOCK_LEVELS;
}
#if !defined(TREE_DIMENSIONS)
#define TREE_DIMENSIONS 2
#endif //!defined (TREE_DIMENSIONS)
constexpr auto TreeDimensions() -> dimension_t {
return TREE_DIMENSIONS;
}
/**
* util template to allow for creation of multiple static counters with
* a nicer interface and fewer static initialization headaches.
*/
template <char...Args>
struct Counter {
using atomic_counter_t = std::atomic<node_id_t >;
static auto Next() -> node_id_t {
return C().fetch_add(1);
}
static auto Clear() -> void {
C().store(0);
}
private:
static auto C() -> atomic_counter_t& {
static atomic_counter_t k_counter = 0;
return k_counter;
}
};
// node and subtree/slab counters for
// keeping some debugging info
using NodeId = Counter<'a'>;
using SubTreeId = Counter<'b'>;
/**
* A recursive template that will expand to a perfect N-ary tree with
* the desired number of levels which is also contiguous in memory. The base case template
* specialization allows for dynamic initialization of additional subtrees as children
* of leaf nodes.
*
*
* @tparam NodeDataType The data associated with each node in
* the tree, should be printable and allow for default
* initialization.
*
* @tparam DIMENSIONS The branchiness of tree, 1 = binary tree, 2 = quad tree, 3 = oct tree, etc.
* @tparam MAX_LEVELS The number of full levels in a memory contiguous subtree
* @tparam LEVEL used for recursive template expansion
*/
template<class NodeDataType, dimension_t DIMENSIONS, level_t MAX_LEVELS, level_t LEVEL = MAX_LEVELS>
class Node {
public:
constexpr static auto MaxChildCount() -> size_t {
return 1ul << DIMENSIONS;
}
constexpr static auto ChildCount() -> size_t {
return MaxChildCount();
}
using ChildNode = Node<NodeDataType, DIMENSIONS, MAX_LEVELS, LEVEL - 1>;
using ChildNodes = std::array<ChildNode, ChildCount()>;
constexpr static auto Dimensions() -> dimension_t {
return DIMENSIONS;
}
constexpr static auto BlockLocalLevel() -> level_t {
return (MAX_LEVELS - LEVEL);
}
constexpr static auto Level() -> level_t {
return /* REMOTE_PARENT_LEVEL + */ BlockLocalLevel();
}
constexpr static auto IsRoot() -> bool {
return Level() == 0;
}
auto IsLeaf() const -> bool {
return ChildCount() == 0;
}
auto Child(size_t idx) -> ChildNode* {
if (idx < 0 || idx > ChildCount()) {
return nullptr;
}
return &(m_children[idx]);
}
auto Child(size_t idx) const -> const ChildNode* {
if (idx < 0 || idx > ChildCount()) {
return nullptr;
}
return &(m_children[idx]);
}
auto Children() -> ChildNodes& {
return m_children;
}
auto Children() const -> const ChildNodes& {
return m_children;
}
auto Data() const -> const NodeDataType& {
return m_data;
}
auto Data() -> NodeDataType& {
return m_data;
}
auto InitChildren() -> bool {
return true;
}
template <class InitFunction>
auto InitChild(size_t idx, InitFunction init) -> bool {
return true;
}
auto Id() const -> const node_id_t& {
return m_id;
}
friend auto operator<<(std::ostream& os, const Node& node) -> std::ostream& {
os << "[" << node.Id() << "] " <<
"(" << node.Level() << ", " << node.BlockLocalLevel() << ") " <<
std::string(2 * (node.Level() + 1), '-');
if constexpr (Node::IsRoot()) {
os << " {root} ";
} else {
os << " {node} ";
}
os << " " <<
sizeof(node) << " bytes" << ", data: " << node.m_data;
os << std::endl;
for (auto& child : node.m_children) {
os << child;
}
return os;
}
private:
node_id_t m_id = NodeId::Next();
ChildNodes m_children{};
NodeDataType m_data{};
};
// recursive base case of the Node template to halt the
// template expansion and act as a glue layer for initializing
// dynamic heap (or mmap file allocated) subtrees.
template<class NodeDataType, dimension_t DIMENSIONS, level_t MAX_LEVELS>
class Node<NodeDataType, DIMENSIONS, MAX_LEVELS, 0> {
public:
constexpr static auto MaxChildCount() -> size_t {
return 1ul << DIMENSIONS;
}
using ChildNode = Node<NodeDataType, DIMENSIONS, MAX_LEVELS>;
using ChildNodes = std::array<std::unique_ptr<ChildNode>, MaxChildCount()>;
constexpr static auto Dimensions() -> dimension_t {
return DIMENSIONS;
}
constexpr static auto BlockLocalLevel() -> level_t {
return MAX_LEVELS;
}
constexpr static auto Level() -> level_t {
return /* REMOTE_PARENT_LEVEL + */ BlockLocalLevel();
}
constexpr static auto IsRoot() -> bool {
return Level() == 0;
}
auto IsLeaf() const -> bool {
return ChildCount() == 0;
}
auto ChildCount() const -> size_t {
if (m_children == nullptr) {
return 0;
}
return std::accumulate(m_children->begin(), m_children->end(), 0ul, [](auto& count, const auto& elem){
return count + (elem.get() == nullptr ? 0 : 1);
});
}
auto Child(size_t idx) -> ChildNode* {
if (idx < 0 || idx > MaxChildCount()) {
return nullptr;
} else if (m_children == nullptr) {
return nullptr;
}
return (*m_children)[idx].get();
}
auto Child(size_t idx) const -> const ChildNode* {
if (idx < 0 || idx > MaxChildCount()) {
return nullptr;
} else if (m_children == nullptr) {
return nullptr;
}
return (*m_children)[idx].get();
}
auto Data() const -> const NodeDataType& {
return m_data;
}
auto Data() -> NodeDataType& {
return m_data;
}
auto InitChildren() -> bool {
if (m_children != nullptr) {
return false;
}
m_children = std::make_unique<ChildNodes>();
return true;
}
template <class InitFunction>
auto InitChild(size_t idx, InitFunction init) -> bool{
if (m_children == nullptr) {
return false;
} else if (idx < 0 || idx > MaxChildCount()) {
return false;
}
(*m_children)[idx] = std::make_unique<ChildNode>();
auto& child = *(*m_children)[idx];
init(child);
return true;
}
auto Id() const -> const node_id_t& {
return m_id;
}
friend auto operator<<(std::ostream& os, const Node& node) -> std::ostream& {
os << "[" << node.Id() << "] " <<
"(" << node.Level() << ", " << node.BlockLocalLevel() << ") " <<
std::string(2 * (node.Level() + 1), '-');
if (node.m_children == nullptr) {
os << " {leaf} ";
} else {
os << " {node} ";
}
os << " " <<
sizeof(node) << " bytes" << " data: " << node.m_data;
if (node.m_children == nullptr) {
return os << std::endl;
}
os << std::endl;
for (auto& child : *(node.m_children)) {
if (child.get() == nullptr) {
continue;
}
os << *child;
}
return os;
}
private:
node_id_t m_id = NodeId::Next();
std::unique_ptr<ChildNodes> m_children{};
NodeDataType m_data{};
};
//
// Test and Example Code
//
struct empty_t{
auto friend operator<<(std::ostream& os, const empty_t& empty) -> std::ostream& {
return os << "{}";
}
};
template <class NodeDataType=empty_t>
using DefaultSlabTree = Node<NodeDataType, TreeDimensions(), TreeBlockLevels()>;
template <class NodeDataType, dimension_t DIMS, level_t LEVELS>
using NarySlabTree = Node<NodeDataType, DIMS, LEVELS>;
template <class NodeT, class Visitor>
static auto Traverse(NodeT& node, Visitor visit) -> void {
visit(node);
const auto childCount = node.MaxChildCount();
for (auto idx = 0ul; idx < childCount; idx++) {
auto* child = node.Child(idx);
if (child == nullptr) {
continue;
}
Traverse(*child, visit);
}
}
static auto example000_ostream() -> void {
std::cout << __FUNCTION__ << std::endl;
NodeId::Clear();
auto rootPtr = std::make_unique<DefaultSlabTree<>>();
std::cout << *rootPtr << std::endl;
std::cout << std::endl;
}
static auto example001_traversal() -> void {
std::cout << __FUNCTION__ << std::endl;
NodeId::Clear();
auto rootPtr = std::make_unique<DefaultSlabTree<>>();
Traverse(*rootPtr, [](auto&& node) {
std::cout << "is leaf: " << (node.IsLeaf() ? "yes" : "no ") << std::endl;
});
std::cout << std::endl;
}
template <class TreeType>
static auto create_first_available_subtree(TreeType& root) {
bool createdSubTree = false;
Traverse(root, [&](auto&& node) {
if (!node.IsLeaf() || createdSubTree) {
return;
}
node.InitChildren();
auto subtreeId = std::string("stid: ") + std::to_string(SubTreeId::Next());
node.InitChild(0, [&](auto&& child){
std::cout << "init'd child id: " << child.Id() << " of node id: " << node.Id() << std::endl;
Traverse(child, [&](auto&& b2Node) {
b2Node.Data() = subtreeId;
});
createdSubTree = true;
});
});
}
static auto example002_init_dynamic_children() -> void {
std::cout << __FUNCTION__ << std::endl;
NodeId::Clear();
SubTreeId::Clear();
// make a tree with string payload
auto rootPtr = std::make_unique<DefaultSlabTree<std::string>>();
auto subtreeId0 = std::string("stid: ") + std::to_string(SubTreeId::Next());
Traverse(*rootPtr, [&](auto&& node) {
node.Data() = subtreeId0;
});
std::cout << "pass 1, no dynamic leafs" << std::endl;
std::cout << *rootPtr << std::endl;
create_first_available_subtree(*rootPtr);
std::cout << std::endl;
std::cout << "pass 2: one new subtree for 1 previous leaf" << std::endl;
std::cout << *rootPtr << std::endl;
create_first_available_subtree(*rootPtr);
std::cout << std::endl;
std::cout << "pass 3: two new subtree for two previous leafs" << std::endl;
std::cout << *rootPtr << std::endl;
create_first_available_subtree(*rootPtr);
std::cout << std::endl;
std::cout << "pass 4 ..." << std::endl;
std::cout << *rootPtr << std::endl;
create_first_available_subtree(*rootPtr);
std::cout << std::endl;
std::cout << "pass 5 ..." << std::endl;
std::cout << *rootPtr << std::endl;
std::cout << std::endl;
std::cout << "pass 6..." << std::endl;
std::cout << *rootPtr << std::endl;
std::cout << std::endl;
}
template <class TreeType>
static auto CountNodes(TreeType& root) -> size_t {
size_t counter = 0;
Traverse(root, [&](auto&&){
counter++;
});
return counter;
}
template <class TreeType>
static auto TreeSize(TreeType& root) -> size_t {
size_t counter = 0;
Traverse(root, [&](auto&& node){
if (node.IsRoot()) {
counter += sizeof(node);
}
});
return counter;
}
//template <class TreeType>
//static auto MaxLevelDepth(TreeType& root) -> level_t {
// level_t level = 0;
//
// Traverse(root, [&](auto&& node){
// level = std::max(level, node.Level());
// })
//
// return level
//}
template <class TreeType>
static auto GrowLevel(TreeType& root) -> void {
std::unordered_set<node_id_t> growIdSet {};
Traverse(root, [&](auto&& node) {
if (node.IsLeaf()) {
growIdSet.emplace(node.Id());
}
});
Traverse(root, [&](auto&& node) {
auto it = growIdSet.find(node.Id());
if (it == growIdSet.end()) {
return;
}
node.InitChildren();
for (auto idx = 0ul; idx < node.MaxChildCount(); idx++) {
node.InitChild(idx, [&](auto &&child) {});
}
});
}
static auto example003_grow_and_count_nodes() {
std::cout << __FUNCTION__ << std::endl;
{
using BinaryTree = NarySlabTree<empty_t, /* dims */ 1, /* levels per subtree */ 0>; // falls back to pointer based binary tree
NodeId::Clear();
SubTreeId::Clear();
auto rootPtr = std::make_unique<BinaryTree>();
std::cout << "grow binary tree - start - nodes: " << CountNodes(*rootPtr) << std::endl;
for (auto round = 0; round < 8; round++) {
GrowLevel(*rootPtr);
std::cout << "grow level - rnd " << round << " - nodes: " << CountNodes(*rootPtr) << std::endl;
}
std::cout << "grow binary tree - end - nodes: " << CountNodes(*rootPtr) << " size: " << TreeSize(*rootPtr) << " bytes" << std::endl;
}
std::cout<< std::endl;
{
using QuadTree = NarySlabTree<empty_t, /* dims */ 2, /* levels per subtree */ 0>; // falls back to pointer quad tree
NodeId::Clear();
SubTreeId::Clear();
auto rootPtr = std::make_unique<QuadTree>();
std::cout << "grow quad tree - start - nodes: " << CountNodes(*rootPtr) << std::endl;
for (auto round = 0; round < 7; round ++) {
GrowLevel(*rootPtr);
std::cout << "grow level - rnd " << round << " - nodes: " << CountNodes(*rootPtr) << std::endl;
}
std::cout << "grow quad tree- end - nodes: " << CountNodes(*rootPtr) << " size: " << TreeSize(*rootPtr) << " bytes" << std::endl;
}
std::cout<< std::endl;
{
using OctTree = NarySlabTree<empty_t, /* dims */ 3, /* levels per subtree */ 0>; // falls back to pointer oct tree
NodeId::Clear();
SubTreeId::Clear();
auto rootPtr = std::make_unique<OctTree>();
std::cout << "grow oct tree - start - nodes: " << CountNodes(*rootPtr) << std::endl;
for (auto round = 0; round < 6; round ++) {
GrowLevel(*rootPtr);
std::cout << "grow level - rnd " << round << " - nodes: " << CountNodes(*rootPtr) << std::endl;
}
std::cout << "grow oct tree- end - nodes: " << CountNodes(*rootPtr) << " size: " << TreeSize(*rootPtr) << " bytes" << std::endl;
}
std::cout<< std::endl;
{
using HexTree = NarySlabTree<empty_t, /* dims */ 4, /* levels per subtree */ 0>; // falls back to pointer hex tree
NodeId::Clear();
SubTreeId::Clear();
auto rootPtr = std::make_unique<HexTree>();
std::cout << "grow hex tree - start - nodes: " << CountNodes(*rootPtr) << std::endl;
for (auto round = 0; round < 5; round ++) {
GrowLevel(*rootPtr);
std::cout << "grow level - rnd " << round << " - nodes: " << CountNodes(*rootPtr) << std::endl;
}
std::cout << "grow hex tree- end - nodes: " << CountNodes(*rootPtr) << " size: " << TreeSize(*rootPtr) << " bytes" << std::endl;
}
std::cout<< std::endl;
{
using D5Tree = NarySlabTree<empty_t, /* dims */ 5, /* levels per subtree */ 0>; // falls back to pointer d5 tree
NodeId::Clear();
SubTreeId::Clear();
auto rootPtr = std::make_unique<D5Tree>();
std::cout << "grow d5 tree - start - nodes: " << CountNodes(*rootPtr) << std::endl;
for (auto round = 0; round < 4; round ++) {
GrowLevel(*rootPtr);
std::cout << "grow level - rnd " << round << " - nodes: " << CountNodes(*rootPtr) << std::endl;
}
std::cout << "grow d5 tree- end - nodes: " << CountNodes(*rootPtr) << " size: " << TreeSize(*rootPtr) << " bytes" << std::endl;
}
}
int main() {
example000_ostream();
example001_traversal();
example002_init_dynamic_children();
example003_grow_and_count_nodes();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment