diff options
Diffstat (limited to 'gdbsupport/intrusive_list.h')
| -rw-r--r-- | gdbsupport/intrusive_list.h | 559 |
1 files changed, 559 insertions, 0 deletions
diff --git a/gdbsupport/intrusive_list.h b/gdbsupport/intrusive_list.h new file mode 100644 index 0000000..8d49ce4 --- /dev/null +++ b/gdbsupport/intrusive_list.h @@ -0,0 +1,559 @@ +/* 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; + } + + 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 */ |