22 DgiNode

Conceptual tree for all the fields of a model which can be referenced with a path

Consider the following example:

$model Point
{
    int x;
    int y;
};

$model Line
{
    Point p1;
    Point p2;
};

$struct X isa ceda::IObject :
    model
    {
        Line line;
        float width;
    }
{
};

An object instance of type X has the following tree structure for the fields in its model:

The nodes of this tree correspond to the possible paths. For example an empty path identifies the root node of the tree.

In cases where maps and dynamic arrays are used, the tree corresponding to all possible paths may be so large as to be practically infinite, and could not possibly be manifested in its entirety in memory.

For example, a map keyed by a string has a practically infinite set of possible key values.

Physically manifested tree of DGIndepNodeForModelField objects

The DGS indep nodes (of type DGIndepNodeForModelField which is a subclass of DGIndepNode) are organised into a physically manifested tree which mirrors the conceptual tree structure corresponding to paths that identify fields in the model of a given IObject.

It is crucial that we allow for representing only a subset of the tree corresponding to all possible paths. Fortunately a DGIndepNodeForModelField object is typically only needed at a relatively small number of the nodes. So we represent a physical tree which is just large enough to contain all the DGIndepNodeForModelField objects that are required at that time.

All the leaf nodes of the tree are of type DGIndepNodeForModelField. Internal nodes of the tree can optionally have an associated DGIndepNodeForModelField.

New DGIndepNodeForModelField objects are inserted into the tree as a result of read barriers, and remove themselves when they are evicted by the DGS.

The internal nodes are deleted when there are no descendent DGIndepNodeForModelField objects.

DgiNode

DgiNode is the base class for a node of the tree. It has a virtual destructor because the nodes are heap allocated and deleted polymorphically [actually looking at the implementation of DeleteNode() this is not true].

enum ENodeType
{
    NT_DGS_NODE,
    NT_VEC_NODE,
    NT_MAP_NODE
};

struct DgiNode
{
    DgiNode(ENodeType type) : type_(type) {}
    virtual ~DgiNode() {}

    ENodeType type_;
};

There are only 3 possible concrete types. ENodeType identifies these types:

Class hierarchy

InternalDgiNode

This is the base class for all the possible internal node types.

The member dgsNode_ allows the internal node to optionally have an associated indep DGS node. Therefore dgsNode_ can be null.

struct InternalDgiNode : public DgiNode
{
    InternalDgiNode(ENodeType type) : DgiNode(type), dgsNode_(nullptr) {}

    virtual bool AllChildrenAreNull() const = 0;

    // May be null.
    DGIndepNodeForModelField* dgsNode_;
};

StructDgiNode and ArrayDgiNode

StructDgiNode and ArrayDgiNode have an identical implementation, therefore class VecDgiNode represents this common code.

struct VecDgiNode : public InternalDgiNode
{
    VecDgiNode() : InternalDgiNode(NT_VEC_NODE) {}

    bool AllChildrenAreNull() const
    {
        for (DgiNode* e : elements_)
        {
            if (e) return false;
        }
        return true;
    }

    // Indexed by field index in the struct / index in the array
    // May have null elements meaning there are no DGS indep nodes under the element
    xvector<DgiNode*> elements_;
};

typedef VecDgiNode StructDgiNode;
typedef VecDgiNode ArrayDgiNode;

MapDgiNode

struct MapDgiNode : public InternalDgiNode
{
    MapDgiNode() : InternalDgiNode(NT_MAP_NODE) {}

    virtual bool AllChildrenAreNull() const
    {
        return map_.empty();
    }

    // Keyed by the serialised octets of the key of the correponding field
    // The mapped value is never null.
    typedef std::map< xvector<octet_t>, DgiNode*> MAP;
    MAP map_;
};

DGIndepNodeForModelField

class DGIndepNodeForModelField : public DgiNode, public DGIndepNode
{
public:
    DGIndepNodeForModelField(ptr<const IObject> obj, const Path& path) : DgiNode(NT_DGS_NODE),obj_(obj), path_(path) {}

    virtual ssize_t ByteSize() const;
    virtual void VisitContainingObject(IObjectVisitor& v) const {}
    virtual xstring Name() const;
    virtual void OnEvict() const;

    ptr<const IObject> obj_;
    Path path_;
};

ssize_t DGIndepNodeForModelField::ByteSize() const
{
    const int AVERAGE_PATH_SIZE = 8;
    return HeapAllocationOverhead +
           sizeof(DGIndepNodeForModelField) +
           HeapAllocationOverhead + AVERAGE_PATH_SIZE;
}

xstring DGIndepNodeForModelField::Name() const
{
    return cxMakeString(ObjectFieldDescriptor(obj_,path_));
}

void DGIndepNodeForModelField::OnEvict() const
{
    GetThreadDGSystem().DeleteIndepField(obj_,path_);
}

Deletion of a DgiNode

void DeleteNode(DgiNode* node)
{
    cxAssert(node);
    if (node->type_ == NT_DGS_NODE)
    {
        DGIndepNodeForModelField* n = reinterpret_cast<DGIndepNodeForModelField*>(node);
        cxVerify( n->TryEvict(false) );
        delete n;
    }
    else if (node->type_ == NT_VEC_NODE)
    {
        VecDgiNode* n = reinterpret_cast<VecDgiNode*>(node);
        if (n->dgsNode_)
        {
            cxVerify( n->dgsNode_->TryEvict(false) );
            delete n->dgsNode_;
        }
        for (DgiNode* c : n->elements_)
        {
            if (c) DeleteNode(c);
        }
        delete n;
    }
    else
    {
        cxAssert(node->type_ == NT_MAP_NODE);
        MapDgiNode* n = reinterpret_cast<MapDgiNode*>(node);
        if (n->dgsNode_)
        {
            cxVerify( n->dgsNode_->TryEvict(false) );
            delete n->dgsNode_;
        }
        for (const MapDgiNode::MAP::value_type& i : n->map_)
        {
            if (i.second) DeleteNode(i.second);
        }
        delete n;
    }
}