123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586 |
- /* Intrusive double linked list for GDB, the GNU debugger.
- Copyright (C) 2021-2022 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 */
|