We are considering 2 changes to the graph resource. They are not directly related, but since both would impact downstream users of graph resources, we are considering doing them at the same time or in quick succession:
- Change the arc container classes to store weak pointers instead of using
- Change the graph resource to hold shared pointers to its components in a
boost::multimapinstead of a
The issue here is that without careful arc management, removing a component may leave arcs with dangling references to freed memory. Any operations which remove components from a resource may do so without removing arcs which point to the removed components and there is no efficient way to validate changes: although most arcs have an inverse relationship with a “partner” arc, this is not required and in this case it is not possible to efficiently remove arcs (because any component C with an arc class that can have the expunged component E as its destination must be visited to ensure it does not reference E – that could be many nodes for many arc types).
The overhead for weak pointers is
- a small control structure and the use of atomic counter increments/decrements to update it.
- the cost of updating code to call
lock()and check validity before dereferencing.
This seems negligible compared to potentially expensive debugging.
- Arcs alternative 0: keep
- Arcs alternative 1: switch to
Now that we have some experience with the graph resource, we have observed a need for fetching graph nodes by their type in addition to by their UUID. As the number of nodes in a resource becomes large (as expected in some existing and upcoming projects), iterating over all the nodes becomes expensive.
Instead of the resource holding
std::set<std::shared_pointer<Component>>, we propose additional indexing of nodes by their (sub)class.
Besides the multi-index container, we also considered a (semi-)manually-maintained lookup for node type. This approach could keep the
std::set and simply add a map from Component type-indices to sets of components of that type.
The resource could observe operations to keep this auxiliary map up-to-date, so this approach would not necessarily require any changes to existing subclasses of
- This approach relies on operations properly reporting all changes, not just “top-level” changes.
- There would be no facility for additional indexes should the need arise.
The simplest use of the multi-index container is to just replace the graph-resource’s current
std::set with a
boost::multi_index container. The container would be indexed on UUID and each node’s type-index (a hash of the type name).
Because node types do not change, developers would generally not need to make large changes to be compatible with the difference in the container type. However, this would require existing code using the graph resource’s node set directly to be updated to a new iteration style.
If we are careful with the design, subclasses could be provided the ability to add indices relevant to their use cases. This would work by making the node storage a template parameter (and perhaps moving it out of the
graph::ResourceBase class into
graph::Resource) in addition to the TypeTraits parameter.
This approach could allow existing subclasses of
graph::Resource to specify a
std::set for the nodes and perhaps avoid any incompatible API changes. However, this would take some work to implement since the base graph resource would now need to handle different containers in the methods it provides.
- Nodes alternative 0: no change.
- Nodes alternative 1: add a map from type-info to nodes of that type (keeping the
- Nodes alternative 2a: swich the
std::setof nodes to
- Nodes alternative 2b: swich the
std::setof nodes to a template parameter (that subclasses could provide).