How about an intrusive list? Of references?

General JUCE discussion
1

Since we’re asking for data structures…it would be really cool to have an intrusive linked list template.

This is great for audio i/o callbacks since the routines to manipulate the list would not require calls to new or delete.

And if we can get an intrusive linked list of reference counted objects that would be super duper.

For reference, here is my own intrusive linked list implementation:

// Intrusive list

namespace detail {

struct List_default_tag
{
};

}

//------------------------------------------------------------------------------

// intrusive doubly linked list

template <class Elem,
          class Tag = detail::List_default_tag>
class List : NonCopyable
{
public:
  typedef int size_type;

  typedef Elem        value_type;
  typedef Elem&       reference;
  typedef Elem const& const_reference;
  typedef Elem*       pointer;
  typedef Elem const* const_pointer;

  class Node : NonCopyable
  {
  public:
    Node () { }

  private:
    friend class List;
    Node* m_next;
    Node* m_prev;
  };

private:
  template <class ElemType, class NodeType>
  class iterator_base
    : public boost::iterator_facade <
      iterator_base <ElemType, NodeType>,
      ElemType,
      boost::bidirectional_traversal_tag
    >
  {
  private:
    explicit iterator_base (NodeType* node) : m_node (node)
    {
    }

  public:
    iterator_base () : m_node (0)
    {
    }

    template <class OtherElemType, class OtherNodeType>
    iterator_base (iterator_base <OtherElemType, OtherNodeType> const& other)
      : m_node (other.m_node)
    {
    }

    template <class OtherElemType, class OtherNodeType>
    iterator_base& operator= (iterator_base <OtherElemType, OtherNodeType> const& other)
    {
      m_node = other.m_node;
      return *this;
    }

    template <class OtherElemType, class OtherNodeType>
    bool operator == (iterator_base <OtherElemType, OtherNodeType> const& other) const
    {
      return m_node == other.m_node;
    }

    template <class OtherElemType, class OtherNodeType>
    bool operator != (iterator_base <OtherElemType, OtherNodeType> const& other) const
    {
      return ! this->operator== (other);
    }

    /*
    operator ElemType* () const
    {
      return static_cast <ElemType*> (m_node);
    }
    */
    
  private:
    friend class List;
    friend class boost::iterator_core_access;

    NodeType* get_node ()
    {
      return m_node;
    }

    NodeType const* get_node () const
    {
      return m_node;
    }

    reference dereference () const
    {
      return *static_cast <ElemType*> (m_node);
    }

    bool equal (NodeType *const *node) const
    {
      return m_node == node;
    }

    void increment ()
    {
      vfassert (m_node->m_next);
      m_node = m_node->m_next;
    }

    void decrement ()
    {
      vfassert (m_node->m_prev && m_node->m_prev->m_prev != 0);
      m_node = m_node->m_prev;
    }

  private:
    NodeType* m_node;
  };

public:
  typedef iterator_base <Elem, Node> iterator;
  typedef iterator_base <Elem const, Node const> const_iterator;

public:
  List ()
    : m_size (0)
  {
    m_head.m_prev = 0; // identifies the head
    m_tail.m_next = 0; // identifies the tail
    clear ();
  }

  size_type size () const { return m_size; }

  reference front ()
  {
    if (empty ())
      Throw (Error().fail (__FILE__, __LINE__, Error::noMoreData));
    return element_from (m_head.m_next);
  }

  const_reference front () const
  {
    if (empty ())
      Throw (Error().fail (__FILE__, __LINE__, Error::noMoreData));
    return element_from (m_head.m_next);
  }

  reference back ()
  {
    if (empty ())
      Throw (Error().fail (__FILE__, __LINE__, Error::noMoreData));
    return element_from (m_tail.m_prev);
  }

  const_reference back () const
  {
    if (empty ())
      Throw (Error().fail (__FILE__, __LINE__, Error::noMoreData));
    return element_from (m_tail.m_prev);
  }

  iterator begin ()
  {
    return iterator (m_head.m_next);
  }

  const_iterator begin () const
  {
    return const_iterator (m_head.m_next);
  }

  const_iterator cbegin () const
  {
    return const_iterator (m_head.m_next);
  }

  iterator end ()
  {
    return iterator (&m_tail);
  }

  const_iterator end () const
  {
    return const_iterator (&m_tail);
  }

  const_iterator cend () const
  {
    return const_iterator (&m_tail);
  }

  bool empty () const
  {
    return m_head.m_next == &m_tail;
  }

  void clear ()
  {
    m_head.m_next = &m_tail;
    m_tail.m_prev = &m_head;
    m_size = 0;
  }

  iterator insert (iterator pos, Elem& elem)
  {
    Node* node = node_from (elem);
    node->m_next = pos.get_node ();
    node->m_prev = node->m_next->m_prev;
    node->m_next->m_prev = node;
    node->m_prev->m_next = node;
    ++m_size;
    return iterator (node);
  }

  void insert (iterator pos, List& other)
  {
    if (!other.empty ())
    {
      Node* before = pos.get_node ();
      other.m_head.m_next->m_prev = before->m_prev;
      before->m_prev->m_next = other.m_head.m_next;
      other.m_tail.m_prev->m_next = before;
      before->m_prev = other.m_tail.m_prev;
      m_size += other.m_size;
      other.clear ();
    }
  }

  iterator erase (iterator pos)
  {
    Node* node = pos.get_node ();
    ++pos;
    node->m_next->m_prev = node->m_prev;
    node->m_prev->m_next = node->m_next;
    --m_size;
    return pos;
  }

  void push_front (Elem& elem)
  {
    insert (begin(), elem);
  }

  void pop_front ()
  {
    if (empty ())
      Throw (Error().fail (__FILE__, __LINE__, Error::noMoreData));
    erase (begin ());
  }

  void push_back (Elem& elem)
  {
    insert (end(), elem);
  }

  void pop_back ()
  {
    if (empty ())
      Throw (Error().fail (__FILE__, __LINE__, Error::noMoreData));
    erase (--end ());
  }

  void swap (List& other)
  {
    List temp;
    temp.append (other);
    other.append (*this);
    append (temp);
  }

  void prepend (List& list)
  {
    insert (begin (), list);
  }

  void append (List& list)
  {
    insert (end(), list);
  }

  iterator iterator_to (Elem& elem) const
  {
    return iterator (static_cast <Node*> (&elem));
  }

  const_iterator const_iterator_to (Elem const& elem) const
  {
    return const_iterator (static_cast <Node const*> (&elem));
  }

private:
  inline reference element_from (Node* node)
  {
    return *(static_cast <pointer> (node));
  }

  inline const_reference element_from (Node const* node) const
  {
    return *(static_cast <const_pointer> (node));
  }

  inline Node* node_from (Elem& elem)
  {
    return static_cast <Node*> (&elem);
  }

  inline Node const* node_from (Elem const& elem) const
  {
    return static_cast <Node const*> (&elem);
  }

private:
  size_type m_size;
  Node m_head;
  Node m_tail;
};
2

There’s already a LinkedList class - is that similar?

3

Hmm…I think you mean LinkedListPointer and no that is not the same. For performance a doubly linked list is preferred. And LinkedListPointer’s requirement that the object contain a field called “nextListItem” is clunky at best. It also fails for the case where you want an object to exist in more than one list at the same time. Although to its credit, juce::LinkedListPointer is intrusive (the objects come with storage for the linked list pointer).

Compare with the use of my class:

class Object; // forward declaration required

struct ObjectList_tag; // for live and free lists
struct ObjectListProcess_tag; // for the processing list

// Object can be in the deleted list or active list
// Objects in the active list can optionally be on the list of objects that require processing
class Object : public List <Object, ObjectList_tag>, public List <Object, ObjectListProcess_tag>
{
public:
};

The only thing missing is to be able to have intrusive linked lists of references - that would ROCK, for audio i/o callbacks and using thread queues / functors in general.

4

Point taken, but my brain is too full to think about this right now…

5

I only brought it up because someone else was asking for new data types. This can sit on the back burner.

Recent studies show that manipulating std::list in the audio I/O callback is bad for your health…don’t ask me how I know this.