Tag: entity-component-systems

A doubly linked list for entt components

I recently implemented a small CRTP template to group entities in entt. It turned out quite nicely, so let me share it here:

template <class T> class doubly_linked_component
{
public:
  using node_type = doubly_linked_component<T>;
  static void on_construct(entt::registry& entities,
    const entt::entity e)
  {
    auto& that = entities.get<T>(e);
    that.next_ = that.prev_ = e;
  }
  static void on_destroy(entt::registry& entities,
    const entt::entity e)
  {
    auto& that = entities.get<T>(e);
    // List has only this element?
    if (that.next_ == e)
    {
      return;
    }
    auto next = that.next_;
    auto prev = that.prev_;
    auto& next_node = static_cast<node_type&>(entities.get<T>(next));
    auto& prev_node = static_cast<node_type&>(entities.get<T>(prev));
    prev_node.next_ = next;
    next_node.prev_ = prev;
  }
  static void merge(entt::registry& entities,
    entt::entity lhs, entt::entity rhs)
  {
    auto& lhs_node = static_cast<node_type&>(entities.get_or_emplace<T>(lhs));
    auto& rhs_node = static_cast<node_type&>(entities.get_or_emplace<T>(rhs));
    // The end of left (which is left.prev_) needs to point to right
    auto lhs_end = lhs_node.prev_;
    auto rhs_end = rhs_node.prev_;
    auto& lhs_end_node = static_cast<node_type&>(entities.get<T>(lhs_end));
    auto& rhs_end_node = static_cast<node_type&>(entities.get<T>(rhs_end));
    lhs_end_node.next_ = rhs;
    rhs_node.prev_ = lhs_end;
    rhs_end_node.next_ = lhs;
    lhs_node.prev_ = rhs_end;
  }
  static std::generator<entt::entity> enumerate(entt::registry& entities,
    entt::entity e)
  {
    // By default, entities are their own lists
    if (!entities.any_of<T>(e))
    {
      co_yield e;
    }
    else
    {
      auto current = e;
      while (true)
      {
        co_yield current;
        current = entities.get<T>(current).next_;
        if (current == e)
          break;
      }
    }
  }
private:
  entt::entity prev_ = entt::null;
  entt::entity next_ = entt::null;
};

You can use it like this:

struct cool_group : doubly_linked_component<cool_group> {};

By default, each entity represents its own 1-sized group. To merge two groups:

cool_group::merge(entities, left, right);

To iterate over all entities, I am using the new std::generator and coroutines. You can use it like this:

for (auto entity : cool_group::enumerate(entities, head))
  do_something(entity);

entt will automatically call into on_construct and on_destroy.

People nowadays usually avoid linked lists because of all the pointer chasing required to actually use them. The pointer chasing is not the problem though, the non-locality is. If you make sure your nodes are all allocated in memory close to each other, there is hardly a penalty. entt will usually do this if nodes are also allocated close in time, which is often the case if you want to group things, so this works nicely in that regard, too. Feel free to use this code under CC0.