A surprisingly useful little class: TwoWayPointer
by Malte Skarupke
In graph like data structures (explicit or implicit) there is a problem of memory safety when you remove a node. You have to clean up all the connections pointing to you. If your graph structure is explicit this is easy, otherwise it can often be annoying to find all pointers pointing to you. A while ago I thought that you could solve that by introducing a two way pointer, which has to be the same size as a normal pointer, but which knows how to disconnect itself on the other side, so that you don’t have to write any clean up code.
The reason why it turned out surprisingly useful is that if both ends of the connection know about each other, I can make them keep the connection alive even if one of them is moved around. So if one of them lives in a std::vector and the vector reallocates, the TwoWayPointer can handle that case and just change the pointer on the other end to point to the new location. That can dramatically simplify code.
One example is that I’m now using it in my signal/slot class which I’ve also included in this blog post. It allowed me to simplify the signal/slot implementation a lot. Compare it to your favourite signal implementation if you want. There is usually a lot of code overhead associated with memory safety. That all went away in this implementation.
Here is the code for the two way pointer:
#pragma once
#include <memory>
#include <cstddef>
template<typename T, typename S>
struct TwoWayPointer
{
private:
TwoWayPointer<S, T> * ptr;
template<typename, typename>
friend struct TwoWayPointer;
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator==(std::nullptr_t, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(std::nullptr_t, const TwoWayPointer<T2, S2> &);
public:
T value;
TwoWayPointer()
: ptr(), value()
{
}
TwoWayPointer(T value)
: ptr(), value(std::move(value))
{
}
TwoWayPointer(TwoWayPointer<S, T> * ptr)
: ptr(ptr), value()
{
if (ptr)
ptr->ptr = this;
}
TwoWayPointer(TwoWayPointer<S, T> * ptr, T value)
: ptr(ptr), value(std::move(value))
{
if (ptr)
ptr->ptr = this;
}
TwoWayPointer(TwoWayPointer && other)
: TwoWayPointer(other.ptr, std::move(other.value))
{
other.ptr = nullptr;
}
TwoWayPointer & operator=(TwoWayPointer && other)
{
if (ptr)
{
if (other.ptr)
std::swap(ptr->ptr, other.ptr->ptr);
else
ptr->ptr = &other;
}
else if (other.ptr)
other.ptr->ptr = this;
std::swap(ptr, other.ptr);
value = std::move(other.value);
return *this;
}
TwoWayPointer & operator=(TwoWayPointer<S, T> * ptr)
{
return *this = TwoWayPointer(ptr);
}
~TwoWayPointer()
{
cut_connection();
}
void cut_connection()
{
if (ptr)
{
ptr->ptr = nullptr;
ptr = nullptr;
}
}
S * operator->() const
{
return std::addressof(ptr->value);
}
S & operator*() const
{
return ptr->value;
}
explicit operator bool() const
{
return ptr;
}
bool operator!() const
{
return !ptr;
}
};
template<typename S>
struct TwoWayPointer<void, S>
{
private:
TwoWayPointer<S, void> * ptr;
template<typename, typename>
friend struct TwoWayPointer;
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator==(std::nullptr_t, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(std::nullptr_t, const TwoWayPointer<T2, S2> &);
public:
TwoWayPointer()
: ptr()
{
}
TwoWayPointer(TwoWayPointer<S, void> * ptr)
: ptr(ptr)
{
if (ptr)
ptr->ptr = this;
}
TwoWayPointer(TwoWayPointer && other)
: TwoWayPointer(other.ptr)
{
other.ptr = nullptr;
}
TwoWayPointer & operator=(TwoWayPointer && other)
{
if (ptr)
{
if (other.ptr)
std::swap(ptr->ptr, other.ptr->ptr);
else
ptr->ptr = &other;
}
else if (other.ptr)
other.ptr->ptr = this;
std::swap(ptr, other.ptr);
return *this;
}
TwoWayPointer & operator=(TwoWayPointer<S, void> * ptr)
{
return *this = TwoWayPointer(ptr);
}
~TwoWayPointer()
{
cut_connection();
}
void cut_connection()
{
if (ptr)
{
ptr->ptr = nullptr;
ptr = nullptr;
}
}
S * operator->() const
{
return std::addressof(ptr->value);
}
S & operator*() const
{
return ptr->value;
}
explicit operator bool() const
{
return ptr;
}
bool operator!() const
{
return !ptr;
}
};
template<typename T>
struct TwoWayPointer<T, void>
{
private:
TwoWayPointer<void, T> * ptr;
template<typename, typename>
friend struct TwoWayPointer;
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator==(std::nullptr_t, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(std::nullptr_t, const TwoWayPointer<T2, S2> &);
public:
T value;
TwoWayPointer()
: ptr(), value()
{
}
TwoWayPointer(T value)
: ptr(), value(std::move(value))
{
}
TwoWayPointer(TwoWayPointer<void, T> * ptr)
: ptr(ptr), value()
{
if (ptr)
ptr->ptr = this;
}
TwoWayPointer(TwoWayPointer<void, T> * ptr, T value)
: ptr(ptr), value(std::move(value))
{
if (ptr)
ptr->ptr = this;
}
TwoWayPointer(TwoWayPointer && other)
: TwoWayPointer(other.ptr, std::move(other.value))
{
other.ptr = nullptr;
}
TwoWayPointer & operator=(TwoWayPointer && other)
{
if (ptr)
{
if (other.ptr)
std::swap(ptr->ptr, other.ptr->ptr);
else
ptr->ptr = &other;
}
else if (other.ptr)
other.ptr->ptr = this;
std::swap(ptr, other.ptr);
value = std::move(other.value);
return *this;
}
TwoWayPointer & operator=(TwoWayPointer<void, T> * ptr)
{
return *this = TwoWayPointer(ptr);
}
~TwoWayPointer()
{
cut_connection();
}
void cut_connection()
{
if (ptr)
{
ptr->ptr = nullptr;
ptr = nullptr;
}
}
explicit operator bool() const
{
return ptr;
}
bool operator!() const
{
return !ptr;
}
};
template<>
struct TwoWayPointer<void, void>
{
private:
TwoWayPointer<void, void> * ptr;
template<typename, typename>
friend struct TwoWayPointer;
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator==(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator!=(const TwoWayPointer<T2, S2> &, std::nullptr_t);
template<typename T2, typename S2>
friend bool operator==(std::nullptr_t, const TwoWayPointer<T2, S2> &);
template<typename T2, typename S2>
friend bool operator!=(std::nullptr_t, const TwoWayPointer<T2, S2> &);
public:
TwoWayPointer()
: ptr()
{
}
TwoWayPointer(TwoWayPointer<void, void> * ptr)
: ptr(ptr)
{
if (ptr)
ptr->ptr = this;
}
TwoWayPointer(TwoWayPointer && other)
: TwoWayPointer(other.ptr)
{
other.ptr = nullptr;
}
TwoWayPointer & operator=(TwoWayPointer && other)
{
if (ptr)
{
if (other.ptr)
std::swap(ptr->ptr, other.ptr->ptr);
else
ptr->ptr = &other;
}
else if (other.ptr)
other.ptr->ptr = this;
std::swap(ptr, other.ptr);
return *this;
}
TwoWayPointer & operator=(TwoWayPointer<void, void> * ptr)
{
return *this = TwoWayPointer(ptr);
}
~TwoWayPointer()
{
cut_connection();
}
void cut_connection()
{
if (ptr)
{
ptr->ptr = nullptr;
ptr = nullptr;
}
}
explicit operator bool() const
{
return ptr;
}
bool operator!() const
{
return !ptr;
}
};
template<typename T, typename S>
bool operator==(const TwoWayPointer<T, S> & lhs, const TwoWayPointer<T, S> & rhs)
{
return lhs.ptr == rhs.ptr;
}
template<typename T, typename S>
bool operator!=(const TwoWayPointer<T, S> & lhs, const TwoWayPointer<T, S> & rhs)
{
return !(lhs == rhs);
}
template<typename T, typename S>
bool operator==(const TwoWayPointer<T, S> & lhs, std::nullptr_t)
{
return !lhs;
}
template<typename T, typename S>
bool operator!=(const TwoWayPointer<T, S> & lhs, std::nullptr_t)
{
return !(lhs == nullptr);
}
template<typename T, typename S>
bool operator==(std::nullptr_t, const TwoWayPointer<T, S> & rhs)
{
return rhs == nullptr;
}
template<typename T, typename S>
bool operator!=(std::nullptr_t, const TwoWayPointer<T, S> & rhs)
{
return !(nullptr == rhs);
}
There is lots of copy+paste for the void pointer special cases. I blame C++ and its lack of static_if. But if you look past the code duplication, it’s not that complicated. And here is the code for the signal/slot implementation that uses it:
#pragma once
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
#include "two_way_pointer.hpp"
namespace sig
{
template<typename...>
class Signal;
template<typename... Args>
class Slot;
class Connection
{
public:
Connection() = default;
template<typename... Args>
explicit Connection(Slot<Args...> & slot)
: slot(&slot.connection)
{
}
Connection(Connection && other) = default;
Connection & operator=(Connection && other)
{
disconnect();
slot = std::move(other.slot);
return *this;
}
~Connection()
{
disconnect();
}
void disconnect()
{
if (slot)
slot.cut_connection();
}
protected:
TwoWayPointer<void, void> slot;
};
template<typename... Args>
class Slot
{
std::function<void (Args...)> func;
TwoWayPointer<void, void> connection;
friend class Connection;
public:
template<typename Func>
Slot(Func && func)
: func(std::forward<Func>(func))
{
}
void operator()(const Args &... args)
{
func(args...);
}
bool is_empty() const
{
return !connection;
}
void clear()
{
connection.cut_connection();
}
};
template<typename... Args>
class Signal
{
public:
Signal() = default;
Signal(Signal && other)
: to_add(std::move(other.to_add))
, slots(std::move(other.slots))
{
}
Signal & operator=(Signal && other)
{
slots = std::move(other.slots);
to_add = std::move(other.to_add);
return *this;
}
void emit(const Args &... args)
{
perform_delayed_adds();
auto end = slots.end();
slots.erase(std::remove_if(slots.begin(), end, [&](Slot<Args...> & slot) -> bool
{
if (slot.is_empty())
return true;
slot(args...);
return slot.is_empty();
}), end);
}
/**
* Connect the given function or functor to this signal. It will be called
* every time that someone emits this signal.
* This function returns a Connection that will disconnect the slot
* when it is destroyed. Therefore if you ignore the return value this
* function will have no effect because the Connection will disconnect
* immediately
*/
template<typename T>
Connection connect(T && slot)
{
Slot<Args...> new_slot(std::forward<T>(slot));
Connection to_return(new_slot);
if (slots.size() == slots.capacity())
{
to_add.erase(std::remove_if(to_add.begin(), to_add.end(), std::mem_fn(&Slot<Args...>::is_empty)), to_add.end());
to_add.emplace_back(std::move(new_slot));
}
else
slots.emplace_back(std::move(new_slot));
return to_return;
}
void perform_delayed_adds()
{
std::move(to_add.begin(), to_add.end(), std::back_inserter(slots));
to_add.clear();
}
void clear()
{
to_add.clear();
slots.clear();
}
size_t size() const
{
return slots.size();
}
size_t capacity() const
{
return slots.capacity();
}
void reserve(size_t count)
{
slots.reserve(count);
}
private:
std::vector<Slot<Args...>> slots;
// containers for storing objects that should be added on the next emit
// this is needed because slots have a tendency to add new things in
// their callbacks, and the slots vector could reallocate
std::vector<Slot<Args...>> to_add;
};
}
Isn’t that nice and simple? It’s only exactly the code that should be there and no more. Looks almost like a garbage collected language. The reason why this is so simple is that now I can just have a pointer into something that’s stored inside of a std::vector. If the vector reallocates or objects move around in there, everything works out fine because the TwoWayPointer keeps the connection alive. That takes away layers of indirections and the memory management concerns associated with that.
In this case I only use the void pointer version of the TwoWayPointer. That’s because the only possible action is to disconnect. The Connection only stores the pointer into the Slot. The Slot only has a std::function and a pointer to the Connection. I also have a version of this code where I store the std::function inside the TwoWayPointer. Then the Connection has a pointer to the std::function, and I can write such features as map(), filter(), take_n(), until() etc. on the connection class because the connection can just modify the data that’s stored inside of the signal. Unfortunately the naive implementation of that is inefficient, and the efficient implementation is a huge mess of templates that’s too complicated and that’s not finished so I don’t want to write a blog post about it yet. (I am missing one crucial ingredient: joining of two signals. Should be possible, but the first time I tried I was drowning in template complexity and had to work on something else for a while. Haven’t gotten back to that code yet)
But even just this is pretty good. It’s a basic signal/slot implementation, and if you need other features like blocking of signals or sorting of callbacks you can build them on top of this as separate classes.
The license for this code is this:
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.
In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
For more information, please refer to <http://unlicense.org/>
Probably Dance 
I think you may have hit something super useful because this pattern is no uncommon. I last used it in a non-allocating future/promise implementation there the future and promise had ptrs back to each other. Using an instance of this, all of that boilerplate would be eliminated. I just may use this. Though I think a better name is bi_ptr, bi_dir_ptr and duplex_ptr.