Thoughts on creating a tracking pointer class, part 16: Second attempt to use a list

Thoughts on Creating a Tracking Pointer Class, Part 16: Second Attempt to Use a List
In the previous parts of this article, we discussed the basic design of a tracking pointer class and the implementation details. In this part, we explore two alternative approaches to creating a tracking pointer, one using a list, and the other using a smart pointer with an optional reference. We’ll discuss the advantages and disadvantages of each approach and consider the memory management implications.

1. Using a List:
A list-based approach to tracking pointers is straightforward and straightforward. Here’s the implementation of a tracking pointer with a list:
“`cpp
template
class TrackingPointer
{
private:
friend class trackable_object;

std::list m_trackers;

TrackingPointer() = default;
TrackingPointer(T* node) : m_trackers(node) {}

void update_trackers(T* p) override
{
for (auto& node : m_trackers) {
node = p;
}
}

public:
T* get() const override
{
return m_trackers.back();
}

~TrackingPointer() override
{
m_trackers.pop_back();
update_trackers(nullptr);
}
};

Commenter LB pointed out that you can use the splice method to move nodes between lists. So let’s try that.

The idea is that each tracking_ptr holds an iterator to a list node that is part of a list controlled by the tracked object. When the tracked object expires its tracking pointers (either due to being moved into or at destruction), the nodes are moved (via splice) to a holding pen which I will call orphans. And when the tracked object is moved from, its tracking pointer nodes are spliced into the tracking pointer list of the destination.

template<typename T>
using tracker_list = std::list<T*>;

template<typename T>
using tracker_node_ptr = typename tracker_list<T>::iterator;

We make up some convenient aliases: A tracker list is a list of pointers to trackable objects. And a tracker node pointer is an iterator into that list. It is the tracker node pointer fow which which our tracking_ptr servers as a wrapper.

template<typename T> struct trackable_object;

We forward-declare the trackable object base class so that we can talk about it in the tracking_ptr definition.

template<typename T> tracker_list<T> orphans;

And here is our list of orphans. This is where nodes go when they no longer point to anything.

template<typename T>
tracking_node_ptr<T> create_node(tracking_list<T>& list, T* value)
{
    return list.emplace(list.end(), value));
}

And since we will be doing this a lot, here’s a helper function to create a new node in a tracking list and return an iterator to it, ready to be wrapped in a tracking pointer.

template<typename T>
struct tracking_ptr
{
private:
    friend struct trackable_object<T>;

    tracker_node_ptr<T> m_node;

    explicit tracking_ptr(tracker_node_ptr<T> const& node) noexcept :
        m_node(node)
    {
    }

As noted earlier, the tracking pointer itself wraps an iterator into the tracking list. When the tracking pointer is created, the trackable_object will use the private constructor to tell it which node it is tracking. The pointer inside that node points back to whatever object the tracking pointer is tracking; if the tracking pointer has expired, then the node is on the orphan list.

    tracker_list& containing_list() noexcept
    {
        if (*m_node) {
            return (*m_node)->trackable_object<T>::m_trackers;
        } else {
            return orphans<T>;
        }
    }

We can infer the list that contains our list node by seeing if our node has expired. If the pointer inside the list node is non-null, then that pointer points to the object whose list we belong to. If the pointer inside the list node is null, then the tracking pointer has expired, and the node is an orphan and lives in the orphan list.

public:
    tracking_ptr(tracking_ptr const& other) :
        m_node(create_node(orphans<T>, nullptr))
    {
    }

Default-constructing a tracking pointer creates an already-orphaned pointer. Make a node for it on the orphans list.

    tracking_ptr(tracking_ptr const& other) :
        m_node(create_node(other.containing_list(), *other.m_node))
    {
    }

Copy-constructing a tracking pointer creates a new node in the same list as the source.

    tracking_ptr(tracking_ptr&& other) noexcept :
        m_node(std::exchange(other.m_node,
                    create_node(orphans<T>, nullptr)))
    {
    }

Move-constructing a tracking pointer adopts the node from the source and then orphans the source.

    T* get() const noexcept
    {
        return *m_node;
    }

When you ask for the pointed-to object, we get it from the list node. This will return nullptr for orphans.

    ~tracking_ptr()
    {
        containing_list.erase(m_node);
    }

Destructing the tracking pointer removes it from whatever list its node belongs to.

    ⟦ assignment operators elided for expository purposes ⟧
};

I’m not going to bother with the assignment operators since they aren’t really the focus of the discussion.

template<typename T>
struct trackable_object
{
private:
    friend struct tracking_ptr<T>;

    tracker_list<T> m_trackers;

    T* outer() noexcept
    {
        return static_cast<T*>(this);
    }

The trackable object has a list of all the tracking pointers that are tracking it. The helper function outer gives us a pointer to the outer object.

    void update_trackers(T* p) noexcept
    {
        for (auto& node : m_trackers) {
            node = p;
        }
    }

When the object wants to change what all its tracking pointers refer to, it can use update_trackers. This doesn’t move the nodes anywhere; you have to do that as a separate step.

public:
    trackable_object() = default;

Constructing the trackable object merely constructs an empty list.

    ~trackable_object()
    {
        update_trackers(nullptr); 
        orphans<T>.splice(orphans<T>.begin(), m_trackers);
    }

When the trackable object destructs, all the active tracking pointers now point to nothing, and all of the nodes are moved to the orphans list.

    trackable_object(const trackable_object&) :
        trackable_object()
    {
    }

Copy-constructing a trackable object creates a separate tracking list and doesn’t affect the tracking list of the copied-from object.

    trackable_object(trackable_object&& other) noexcept :
        m_trackers(std::move(other.m_trackers))
    {
        update_trackers(outer());
    }

Move-constructing a trackable object transfers the tracking pointers to the new object, and we update those tracking pointers to point to the newly-constructed object.

    trackable_object& operator=(const trackable_object&)
    {
        return *this;
    }

Copy-assigning a trackable object does nothing to the tracking pointers.

    trackable_object& operator=(trackable_object&& other) noexcept
    {
        update_trackers(nullptr);
        orphans<T>.splice(orphans<T>.begin(), m_trackers);

        m_trackers.splice(m_trackers.begin(), other.m_trackers);
        update_trackers(outer());

        return *this;
    }

Move-assigning a trackable object expires its existing tracking pointers (sets the pointers to null and then moves them to the orphans list), and then steals all the tracking pointers from the source object (and setting the pointers to point to the assigned-to object).

    tracking_ptr<T> track()
    {
        auto new_node = m_trackers.emplace(m_trackers.end(), outer());
        return tracking_ptr<T>(new_node);
    }

To create a tracking pointer, we create a new node in our tracking list and tell the tracking pointer to wrap an iterator to it.

Okay, that’s a quick implementation of the basic design. What do we see?

One annoying thing is that creating an empty tracking pointer performs an allocation. You sort of hope that empty tracking pointers are noexcept constructible and are basically free, but that’s sadly not the case.

Move construction is also potentially-throwing since we have to leave an orphan node in the source object.

We can avoid this problem by using a sentinel iterator to indicate an empty tracking pointer. An obvious choice for this is orphans<T>.end() since it is already there and doesn’t become invalidated.

Unfortunately, this doesn’t work because you are not allowed to compare iterators from different containers. The comparison if (m_node == orphans<T>.end()) is illegal if m_node is not an orphan, but the way we set things up, the way to check if a node is an orphan is to dereference it to look at the pointer inside, but we can’t do that either because the end() iterator is not dereferencable.

One solution is to preallocate a single node on the orphans list and use that for all orphans. Now instead of creating a node on the orphan list, we just grab the orphans<T>.begin() node. This preallocated node has a null pointer inside, so we can look at the wrapped pointer to detect that we have an orphan, and only then do we compare it against orphans<T>.begin() to see if we have the special orphan (in which case we never erase it).

Another solution is for the tracking pointer to use a std::optional to hold the iterator. An empty iterator would mean that the node is already orphaned.

Both of these solutions still have the problem that there is an orphan list at all. In fact, the way we set things up, we have multiple orphan lists, one for each type T. We can consolidate this down to a single orphan list by using type erasure and making the tracking list a std::list<void*>, and then applying a lot of casting when we pull pointers out of the nodes.

Another problem with orphan lists is multithreaded access. We already said that tracking pointers and the objects they track must all belong to the same thread due to the possibility of observing an object in mid-move. But a shared orphan list means that all tracking pointers and tracked objects must belong to the same thread because they can collide on the orphan list. You can fix this by adding a mutex to the orphan list, but this could end up being a multithreaded choke point.

We could avoid unsafe multithreaded access to the orphan lists by making the orphan lists immutable: The only node on the orphan lists is the special sentinel. The entries on the tracking list would now have to be a std::pair<T*, tracking_ptr<T>*: The T* is used by the tracking pointer to find the trackable object, and the tracking_ptr<T>* is used by the trackable object so it can hunt down all the active tracking pointers and erase their m_node and set the m_node to the special sentinel orphan.

But wait, creating the orphan list could throw an exception due to low memory, so that’s another thing to worry about. We can get rid of the orphan lists entirely by bringing back the std::optional<tracking_node_ptr<T>> as the m_node. You would combine this with the std::pair so that when the tracked object wants to expire its tracking nodes, it can reset all of the m_nodes.

So yes, you could do this with std::list, but we had to work around multiple weaknesses. The prohibition on comparing iterators from different containers forced us to come up with somewhat clunky workarounds, and the inability to extract list nodes without attaching them to another list forces us to create a “holding pen” for all the orphaned nodes.

The post Thoughts on creating a tracking pointer class, part 16: Second attempt to use a list appeared first on The Old New Thing.