1
\$\begingroup\$

Below is my implementation of a thread safe scene graph; I'd love some feedback, especially regarding safety and efficiency.

The key pieces are deferring node deletion until a single threaded portion of the code and automatically pointing NodeLink<> members to nullptr when their target is deleted.

The game update loop goes something like this to defer deletion:

while (true) {
    Update(); // Can be multi-threaded
    Draw(); // Can be multi-threaded
    NodeManager::DoDeletes(); // Down to a single thread
}

I'm assuming that Node deletion, insertion, and re-linking will be somewhat infrequent (~10 actions per frame with rare spikes into the 100s).

Some node links are marked as critical, which means that if the link dies, then the pointed to node should be deleted. For example, a boat may have a critical link to its sail so that both disappear at the same time when the boat is deleted. The sail may have an a critical back to the boat as well, so that if the sail is deleted, then the boat goes too (as opposed to leaving a non-functional boat). If shared_ptr is an AND operation, then critical links would be an OR (first to drop the link deletes the object).

I've designed with patterns like this in mind:

NodeLink<Creature> target;
...
void Update() {
  if (!target.IsValid()) {
    return;
  }
  // Do a bunch of stuff with target
}

So that the user needs only check if the link is valid at the start of some update, and it's guaranteed to be valid for the rest of the update (barring the user re-assigning it).

Here's the code with a small test case:

#include <atomic>
#include <exception>
#include <list>
#include <mutex>
#include <set>
#include <type_traits>

// For testing only
#include <iostream>

class BaseNodeLink;
class Node;

class NodeManager {
private:
    // Mutex for enqueueing in delete queue
    static std::mutex deleteQueueMutex;

    // Set of IDs being delted this phase to prevent multiple deletion
    static std::set<uint64_t> deleteIds;

    // Queue of nodes to delete this phase
    static std::list<Node*> deleteList;

    static std::atomic<uint64_t> nextId;

public:

    // Generatess a unique node ID and returns it.
    static uint64_t GenerateId();

    // Clears all links to the given node.
    static void ClearLinks(Node* node);

    // Queues the given node for deletion.
    static void QueueDelete(Node* node);

    // Processes all queued deletes.
    static void DoDeletes();

    // Puts the given node in the given given. If marked critical, the node will be deleted
    // when the link is reset or deleted.
    static void Link(BaseNodeLink* p, Node* newNode, bool newNodeCritical);

    // Removes the node (if any) from the given link.
    static void Unlink(BaseNodeLink* p);
};

////////////////////////////////////////////////////////////////////////////////
// Node
class Node {
private:
    friend class NodeManager;
    BaseNodeLink* head;
    std::mutex linkMutex;
    bool queuedForDelete;
    uint64_t nodeId;

public:

    Node() {
        head = nullptr;
        queuedForDelete = false;
        nodeId = NodeManager::GenerateId();
        std::cout << "Created Node " << nodeId << std::endl;
    }

    virtual ~Node() {
        NodeManager::ClearLinks(this);
        std::cout << "Deleted Node " << nodeId << std::endl;
    }

    uint64_t GetNodeId() const {
        return nodeId;
    }
};

////////////////////////////////////////////////////////////////////////////////
// Node Link

class EmptyLinkException : public std::exception {
};

class BaseNodeLink {
private:
    friend class NodeManager;

    BaseNodeLink* next;
    BaseNodeLink* prev;

    bool critical;

protected:

    // Get/set link using Node values
    virtual Node* GetAsNode() const = 0;
    virtual void SetFromNode(Node* node) = 0;

public:

    BaseNodeLink() 
        : next(nullptr), prev(nullptr), critical(false)
    {}

    virtual ~BaseNodeLink() {}

    // Returns true if the link points to a valid Node
    bool IsValid() const {
        return GetAsNode() != nullptr;
    }

    // Returns true if the link is marked as critical (delete node upon link deletion or reset).
    bool IsCritical() const {
        return critical;
    }
};

template <typename T>
class NodeLink : public BaseNodeLink {
private:
    T* node = nullptr;

protected:

    Node* GetAsNode() const override {
        return (Node*)node;
    }

    void SetFromNode(Node* node) override {
        this->node = dynamic_cast<T*>(node);
    }

public:

    virtual ~NodeLink() {
        if (node && IsCritical()) {
            NodeManager::QueueDelete((Node*)node);
        }
    }

    T* Get() const {
        return node;
    }

    void Reset(T* newNode, bool newNodeCritical) {
        if (node == newNode) {
            return;
        }

        if (IsValid() && IsCritical()) {
            NodeManager::QueueDelete(GetAsNode());
        }

        NodeManager::Unlink(this);
        NodeManager::Link(this, newNode, newNodeCritical);
    }

    // Releases the link to the node, ignoring the state of the critical flag.
    T* Release() {
        T* oldNode = node;
        NodeManager::Unlink(this);
        return oldNode;
    }

    T* operator ->() const {
        if (!node) {
            throw EmptyLinkException();
        }
        return node;
    }

    T* operator *() const {
        if (!node) {
            throw EmptyLinkException();
        }
        return node;
    }
};

////////////////////////////////////////////////////////////////////////////////
// Node Manager implementation

std::mutex NodeManager::deleteQueueMutex;
std::set<uint64_t> NodeManager::deleteIds;
std::list<Node*> NodeManager::deleteList;
std::atomic<uint64_t> NodeManager::nextId = 0;

uint64_t NodeManager::GenerateId() {
    return nextId++;
}

void NodeManager::ClearLinks(Node* node) {
    BaseNodeLink* p = node->head;
    while (p) {
        BaseNodeLink* lastP = p;
        p = p->next;

        lastP->SetFromNode(nullptr);
        lastP->prev = nullptr;
        lastP->next = nullptr;
        lastP->critical = false;
    }
    node->head = nullptr;
}

void NodeManager::QueueDelete(Node * node) {
    std::lock_guard<std::mutex> nodeLock(deleteQueueMutex);

    if (deleteIds.count(node->GetNodeId()) > 0) {
        return;
    }

    deleteIds.insert(node->GetNodeId());
    deleteList.push_back(node);
}

void NodeManager::DoDeletes() {
    while (deleteList.size() > 0) {
        delete deleteList.front();
        deleteList.pop_front();
    }
}

void NodeManager::Link(BaseNodeLink * p, Node * newNode, bool newNodeCritical) {
    if (newNode) {
        std::lock_guard<std::mutex> nodeLock(newNode->linkMutex);

        p->SetFromNode(newNode);
        p->prev = nullptr;
        p->next = newNode->head;
        p->critical = newNodeCritical;

        if (p->next) {
            p->next->prev = p;
        }
    }
}

void NodeManager::Unlink(BaseNodeLink * p) {
    if (p->IsValid()) {
        std::lock_guard<std::mutex> nodeLock(p->GetAsNode()->linkMutex);

        if (p->prev) {
            // Link is not head
            p->prev->next = p->next;
        } else {
            // Link is head
            p->GetAsNode()->head = p->next;
        }

        if (p->next) {
            p->next->prev = p->prev;
        }

        p->SetFromNode(nullptr);
        p->prev = nullptr;
        p->next = nullptr;
    }
}

////////////////////////////////////////////////////////////////////////////////
// Test case

class MeshNode : public Node {
public:
    MeshNode() {
        std::cout << "Mesh node " << GetNodeId() << " created" << std::endl;
    }

    ~MeshNode() {
        std::cout << "Mesh node " << GetNodeId() << " deleted" << std::endl;
    }

    void Foobar() {
        std::cout << "Foobar()" << std::endl;
    }
};


class DrawNode : public Node {
public:

    NodeLink<Node> link1;
    NodeLink<Node> link2;
    NodeLink<MeshNode> meshLink;

    DrawNode() {}

    ~DrawNode() {
        std::cout << "Draw node " << GetNodeId() << " deleted" << std::endl;
    }

    virtual void Draw() {
        // Draw code goes here
    }
};

int main() {
    std::cout << "Phase 1" << std::endl;
    Node* node0 = new Node();
    Node* node1 = new Node();
    Node* node2 = new Node();
    DrawNode* node3 = new DrawNode();
    DrawNode* node4 = new DrawNode();
    MeshNode* node5 = new MeshNode();
    NodeManager::DoDeletes();

    // Link node 3 to node 5, and mark it critical
    node3->meshLink.Reset(node5, true);
    node3->meshLink->Foobar();
    NodeManager::DoDeletes();

    // Link node 3 to node 0, but don't mark it critical
    node3->link1.Reset(node0, false);
    NodeManager::DoDeletes();

    // Link node 3 to node 1, and mark it critical
    node3->link2.Reset(node2, true);
    NodeManager::DoDeletes();

    // Link node 4 to node 3, and mark it critical
    node4->link2.Reset(node3, true);
    NodeManager::DoDeletes();

    std::cout << "\nPhase 2" << std::endl;
    NodeManager::QueueDelete(node4);
    NodeManager::DoDeletes();

    std::cout << "\nDone" << std::endl;

    system("PAUSE");
    return 0;
}

The output of the test case is:

Phase 1
Created Node 0
Created Node 1
Created Node 2
Created Node 3
Created Node 4
Created Node 5
Mesh node 5 created
Foobar()

Phase 2
Draw node 4 deleted
Deleted Node 4
Draw node 3 deleted
Deleted Node 3
Mesh node 5 deleted
Deleted Node 5
Deleted Node 2

Done

And a multithreaded test case using OpenMP:

#include <omp.h>
#include <cassert>

class QuadNode : public Node {
public:

    NodeLink<QuadNode> links[4] = {};
    uint64_t value = 0;

    QuadNode() {
    }

    virtual ~QuadNode() {
    }

    uint64_t Sum() {
        uint64_t sum = value;

        for (int i = 0; i < 4; ++i) {
            if (links[i].IsValid()) {
                sum += links[i]->Sum();
            }
        }

        return sum;
    }
};

void FillQuadNodes(QuadNode* node, int depth) {
    node->value = depth;
    if (depth <= 1) {
        return;
    }

    for (int i = 0; i < 4; ++i) {
        node->links[i].Reset(new QuadNode(), true);
        FillQuadNodes(node->links[i].Get(), depth - 1);
    }
}

void DeleteSomeQuadNodes(QuadNode* node, int depth) {
    if (depth <= 0) {
        return;
    }

    for (int i = 0; i < 4; ++i) {
        if (!node->links[i].IsValid()) {
            continue;
        }

        if (depth == 2) {
            if (i % 2) {
                node->links[i].Reset(nullptr, false);
            }
        } else {
            DeleteSomeQuadNodes(node->links[i].Get(), depth - 1);
        }
    }
}

void DepthFirstDelete(QuadNode* node) {
    for (int i = 0; i < 4; ++i) {
        if (!node->links[i].IsValid()) {
            continue;
        }

        DepthFirstDelete(node->links[i].Get());
        node->links[i].Reset(nullptr, false);
    }
}

void Update() {
    QuadNode* root = new QuadNode();

    // Create nodes
#pragma omp parallel num_threads(4)
    {
        int i = omp_get_thread_num();
        int numThreads = omp_get_num_threads();
        assert(numThreads == 4);

        QuadNode* node = new QuadNode();
        root->links[i].Reset(node, true);

        FillQuadNodes(node, 7);
    }

    std::cout << root->Sum() << std::endl;
    assert(root->Sum() == 29116);

    NodeManager::DoDeletes();
    assert(root->Sum() == 29116);

    // Delete some nodes
#pragma omp parallel num_threads(4)
    {
        int i = omp_get_thread_num();
        int numThreads = omp_get_num_threads();
        assert(numThreads == 4);

        QuadNode* node = root->links[i].Get();
        DeleteSomeQuadNodes(node, 6);
    }

    std::cout << root->Sum() << std::endl;
    assert(root->Sum() == 16828);
    NodeManager::DoDeletes();
    std::cout << root->Sum() << std::endl;
    assert(root->Sum() == 16828);

    // Delete everything except the top two levels
#pragma omp parallel num_threads(16)
    {
        int i = omp_get_thread_num();
        int numThreads = omp_get_num_threads();
        assert(numThreads == 16);

        QuadNode* node = root->links[i / 4]->links[i % 4].Get();
        DepthFirstDelete(node);
    }

    std::cout << root->Sum() << std::endl;
    assert(root->Sum() == 124);
    NodeManager::DoDeletes();
    std::cout << root->Sum() << std::endl;
    assert(root->Sum() == 124);
}

int main() {
    Update();

    system("PAUSE");
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Have you tried and confirmed that this works in a multi-threaded context? Your example is entirely single-threaded \$\endgroup\$ – Frank Sep 6 '17 at 7:07
  • \$\begingroup\$ @Frank good point. Added to the question and it's working. \$\endgroup\$ – Caleb Sep 6 '17 at 9:30
  • \$\begingroup\$ What is your intention of separating Node and NodeLink ? \$\endgroup\$ – Harald Scheirich Sep 6 '17 at 16:16
  • \$\begingroup\$ @HaraldScheirich a couple reasons. First, non-nodes may refer to nodes in the scene graph, so it gives them the same safety. Second, so it can be templatized and wrap different type of nodes. \$\endgroup\$ – Caleb Sep 6 '17 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.