gdbsupport/intrusive_list.h

/* Intrusive double linked list for GDB, the GNU debugger.
   Copyright (C) 2021 Free Software Foundation, Inc.

   This file is part of GDB.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#ifndef GDBSUPPORT_INTRUSIVE_LIST_H
#define GDBSUPPORT_INTRUSIVE_LIST_H

#define INTRUSIVE_LIST_UNLINKED_VALUE ((T *) -1)

/* A list node.  The elements put in an intrusive_list either inherit
   from this, or have a field of this type.  */
template<typename T>
struct intrusive_list_node
{
  bool is_linked () const
  {
    return next != INTRUSIVE_LIST_UNLINKED_VALUE;
  }

  T *next = INTRUSIVE_LIST_UNLINKED_VALUE;
  T *prev = INTRUSIVE_LIST_UNLINKED_VALUE;
};

/* Follows a couple types used by intrusive_list as template parameter to find
   the intrusive_list_node for a given element.  One for lists where the
   elements inherit intrusive_list_node, and another for elements that keep the
   node as member field.  */

/* For element types that inherit from intrusive_list_node.  */

template<typename T>
struct intrusive_base_node
{
  static intrusive_list_node<T> *as_node (T *elem)
  { return elem; }
};

/* For element types that keep the node as member field.  */

template<typename T, intrusive_list_node<T> T::*MemberNode>
struct intrusive_member_node
{
  static intrusive_list_node<T> *as_node (T *elem)
  { return &(elem->*MemberNode); }
};

/* Common code for forward and reverse iterators.  */

template<typename T, typename AsNode, typename SelfType>
struct intrusive_list_base_iterator
{
  using self_type = SelfType;
  using iterator_category = std::bidirectional_iterator_tag;
  using value_type = T;
  using pointer = T *;
  using const_pointer = const T *;
  using reference = T &;
  using const_reference = const T &;
  using difference_type = ptrdiff_t;
  using size_type = size_t;
  using node_type = intrusive_list_node<T>;

  /* Create an iterator pointing to ELEM.  */
  explicit intrusive_list_base_iterator (T *elem)
    : m_elem (elem)
  {}

  /* Create a past-the-end iterator.  */
  intrusive_list_base_iterator ()
    : m_elem (nullptr)
  {}

  reference operator* () const
  { return *m_elem; }

  pointer operator-> () const
  { return m_elem; }

  bool operator== (const self_type &other) const
  { return m_elem == other.m_elem; }

  bool operator!= (const self_type &other) const
  { return m_elem != other.m_elem; }

protected:
  static node_type *as_node (T *elem)
  { return AsNode::as_node (elem); }

  /* A past-end-the iterator points to the list's head.  */
  pointer m_elem;
};

/* Forward iterator for an intrusive_list.  */

template<typename T, typename AsNode = intrusive_base_node<T>>
struct intrusive_list_iterator
  : public intrusive_list_base_iterator
	     <T, AsNode, intrusive_list_iterator<T, AsNode>>
{
  using base = intrusive_list_base_iterator
		 <T, AsNode, intrusive_list_iterator<T, AsNode>>;
  using self_type = typename base::self_type;
  using node_type = typename base::node_type;

  /* Inherit constructor and M_NODE visibility from base.  */
  using base::base;
  using base::m_elem;

  self_type &operator++ ()
  {
    node_type *node = this->as_node (m_elem);
    m_elem = node->next;
    return *this;
  }

  self_type operator++ (int)
  {
    self_type temp = *this;
    node_type *node = this->as_node (m_elem);
    m_elem = node->next;
    return temp;
  }

  self_type &operator-- ()
  {
    node_type *node = this->as_node (m_elem);
    m_elem = node->prev;
    return *this;
  }

  self_type operator-- (int)
  {
    self_type temp = *this;
    node_type *node = this->as_node (m_elem);
    m_elem = node->prev;
    return temp;
  }
};

/* Reverse iterator for an intrusive_list.  */

template<typename T, typename AsNode = intrusive_base_node<T>>
struct intrusive_list_reverse_iterator
  : public intrusive_list_base_iterator
	     <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>
{
  using base = intrusive_list_base_iterator
		 <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>;
  using self_type = typename base::self_type;

  /* Inherit constructor and M_NODE visibility from base.  */
  using base::base;
  using base::m_elem;
  using node_type = typename base::node_type;

  self_type &operator++ ()
  {
    node_type *node = this->as_node (m_elem);
    m_elem = node->prev;
    return *this;
  }

  self_type operator++ (int)
  {
    self_type temp = *this;
    node_type *node = this->as_node (m_elem);
    m_elem = node->prev;
    return temp;
  }

  self_type &operator-- ()
  {
    node_type *node = this->as_node (m_elem);
    m_elem = node->next;
    return *this;
  }

  self_type operator-- (int)
  {
    self_type temp = *this;
    node_type *node = this->as_node (m_elem);
    m_elem = node->next;
    return temp;
  }
};

/* An intrusive double-linked list.

   T is the type of the elements to link.  The type T must either:

    - inherit from intrusive_list_node<T>
    - have an intrusive_list_node<T> member

   AsNode is a type with an as_node static method used to get a node from an
   element.  If elements inherit from intrusive_list_node<T>, use the default
   intrusive_base_node<T>.  If elements have an intrusive_list_node<T> member,
   use:

     intrusive_member_node<T, &T::member>

   where `member` is the name of the member.  */

template <typename T, typename AsNode = intrusive_base_node<T>>
class intrusive_list
{
public:
  using value_type = T;
  using pointer = T *;
  using const_pointer = const T *;
  using reference = T &;
  using const_reference = const T &;
  using difference_type = ptrdiff_t;
  using size_type = size_t;
  using iterator = intrusive_list_iterator<T, AsNode>;
  using reverse_iterator = intrusive_list_reverse_iterator<T, AsNode>;
  using const_iterator = const intrusive_list_iterator<T, AsNode>;
  using const_reverse_iterator
    = const intrusive_list_reverse_iterator<T, AsNode>;
  using node_type = intrusive_list_node<T>;

  intrusive_list () = default;

  ~intrusive_list ()
  {
    clear ();
  }

  intrusive_list (intrusive_list &&other)
    : m_front (other.m_front),
      m_back (other.m_back)
  {
    other.m_front = nullptr;
    other.m_back = nullptr;
  }

  intrusive_list &operator= (intrusive_list &&other)
  {
    m_front = other.m_front;
    m_back = other.m_back;
    other.m_front = nullptr;
    other.m_back = nullptr;

    return *this;
  }

  void swap (intrusive_list &other)
  {
    std::swap (m_front, other.m_front);
    std::swap (m_back, other.m_back);
  }

  iterator iterator_to (reference value)
  {
    return iterator (&value);
  }

  const_iterator iterator_to (const_reference value)
  {
    return const_iterator (&value);
  }

  reference front ()
  {
    gdb_assert (!this->empty ());
    return *m_front;
  }

  const_reference front () const
  {
    gdb_assert (!this->empty ());
    return *m_front;
  }

  reference back ()
  {
    gdb_assert (!this->empty ());
    return *m_back;
  }

  const_reference back () const
  {
    gdb_assert (!this->empty ());
    return *m_back;
  }

  void push_front (reference elem)
  {
    intrusive_list_node<T> *elem_node = as_node (&elem);

    gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);

    if (this->empty ())
      this->push_empty (elem);
    else
      this->push_front_non_empty (elem);
  }

  void push_back (reference elem)
  {
    intrusive_list_node<T> *elem_node = as_node (&elem);

    gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);

    if (this->empty ())
      this->push_empty (elem);
    else
      this->push_back_non_empty (elem);
  }

  /* Inserts ELEM before POS.  */
  void insert (const_iterator pos, reference elem)
  {
    if (this->empty ())
      return this->push_empty (elem);

    if (pos == this->begin ())
      return this->push_front_non_empty (elem);

    if (pos == this->end ())
      return this->push_back_non_empty (elem);

    intrusive_list_node<T> *elem_node = as_node (&elem);
    T *pos_elem = &*pos;
    intrusive_list_node<T> *pos_node = as_node (pos_elem);
    T *prev_elem = pos_node->prev;
    intrusive_list_node<T> *prev_node = as_node (prev_elem);

    gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);

    elem_node->prev = prev_elem;
    prev_node->next = &elem;
    elem_node->next = pos_elem;
    pos_node->prev = &elem;
  }

  /* Move elements from LIST at the end of the current list.  */
  void splice (intrusive_list &&other)
  {
    if (other.empty ())
      return;

    if (this->empty ())
      {
	*this = std::move (other);
	return;
      }

    /* [A ... B] + [C ... D] */
    T *b_elem = m_back;
    node_type *b_node = as_node (b_elem);
    T *c_elem = other.m_front;
    node_type *c_node = as_node (c_elem);
    T *d_elem = other.m_back;

    b_node->next = c_elem;
    c_node->prev = b_elem;
    m_back = d_elem;

    other.m_front = nullptr;
    other.m_back = nullptr;
  }

  void pop_front ()
  {
    gdb_assert (!this->empty ());
    erase_element (*m_front);
  }

  void pop_back ()
  {
    gdb_assert (!this->empty ());
    erase_element (*m_back);
  }

private:
  /* Push ELEM in the list, knowing the list is empty.  */
  void push_empty (T &elem)
  {
    gdb_assert (this->empty ());

    intrusive_list_node<T> *elem_node = as_node (&elem);

    gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);

    m_front = &elem;
    m_back = &elem;
    elem_node->prev = nullptr;
    elem_node->next = nullptr;
  }

  /* Push ELEM at the front of the list, knowing the list is not empty.  */
  void push_front_non_empty (T &elem)
  {
    gdb_assert (!this->empty ());

    intrusive_list_node<T> *elem_node = as_node (&elem);
    intrusive_list_node<T> *front_node = as_node (m_front);

    gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);

    elem_node->next = m_front;
    front_node->prev = &elem;
    elem_node->prev = nullptr;
    m_front = &elem;
  }

  /* Push ELEM at the back of the list, knowing the list is not empty.  */
  void push_back_non_empty (T &elem)
  {
    gdb_assert (!this->empty ());

    intrusive_list_node<T> *elem_node = as_node (&elem);
    intrusive_list_node<T> *back_node = as_node (m_back);

    gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);

    elem_node->prev = m_back;
    back_node->next = &elem;
    elem_node->next = nullptr;
    m_back = &elem;
  }

  void erase_element (T &elem)
  {
    intrusive_list_node<T> *elem_node = as_node (&elem);

    gdb_assert (elem_node->prev != INTRUSIVE_LIST_UNLINKED_VALUE);
    gdb_assert (elem_node->next != INTRUSIVE_LIST_UNLINKED_VALUE);

    if (m_front == &elem)
      {
	gdb_assert (elem_node->prev == nullptr);
	m_front = elem_node->next;
      }
    else
      {
	gdb_assert (elem_node->prev != nullptr);
	intrusive_list_node<T> *prev_node = as_node (elem_node->prev);
	prev_node->next = elem_node->next;
      }

    if (m_back == &elem)
      {
	gdb_assert (elem_node->next == nullptr);
	m_back = elem_node->prev;
      }
    else
      {
	gdb_assert (elem_node->next != nullptr);
	intrusive_list_node<T> *next_node = as_node (elem_node->next);
	next_node->prev = elem_node->prev;
      }

    elem_node->next = INTRUSIVE_LIST_UNLINKED_VALUE;
    elem_node->prev = INTRUSIVE_LIST_UNLINKED_VALUE;
  }

public:
  /* Remove the element pointed by I from the list.  The element
     pointed by I is not destroyed.  */
  iterator erase (const_iterator i)
  {
    iterator ret = i;
    ++ret;

    erase_element (*i);

    return ret;
  }

  /* Erase all the elements.  The elements are not destroyed.  */
  void clear ()
  {
    while (!this->empty ())
      pop_front ();
  }

  /* Erase all the elements.  Disposer::operator()(pointer) is called
     for each of the removed elements.  */
  template<typename Disposer>
  void clear_and_dispose (Disposer disposer)
  {
    while (!this->empty ())
      {
	pointer p = &front ();
	pop_front ();
	disposer (p);
      }
  }

  bool empty () const
  {
    return m_front == nullptr;
  }

  iterator begin () noexcept
  {
    return iterator (m_front);
  }

  const_iterator begin () const noexcept
  {
    return const_iterator (m_front);
  }

  const_iterator cbegin () const noexcept
  {
    return const_iterator (m_front);
  }

  iterator end () noexcept
  {
    return {};
  }

  const_iterator end () const noexcept
  {
    return {};
  }

  const_iterator cend () const noexcept
  {
    return {};
  }

  reverse_iterator rbegin () noexcept
  {
    return reverse_iterator (m_back);
  }

  const_reverse_iterator rbegin () const noexcept
  {
    return const_reverse_iterator (m_back);
  }

  const_reverse_iterator crbegin () const noexcept
  {
    return const_reverse_iterator (m_back);
  }

  reverse_iterator rend () noexcept
  {
    return {};
  }

  const_reverse_iterator rend () const noexcept
  {
    return {};
  }

  const_reverse_iterator crend () const noexcept
  {
    return {};
  }

private:
  static node_type *as_node (T *elem)
  {
    return AsNode::as_node (elem);
  }

  T *m_front = nullptr;
  T *m_back = nullptr;
};

#endif /* GDBSUPPORT_INTRUSIVE_LIST_H */