Automatic date update in version.in
[binutils-gdb.git] / gdbsupport / intrusive_list.h
blob2262d9fb4270d184a77f01b17c6af2bdb64ec352
1 /* Intrusive double linked list for GDB, the GNU debugger.
2 Copyright (C) 2021-2024 Free Software Foundation, Inc.
4 This file is part of GDB.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 #ifndef GDBSUPPORT_INTRUSIVE_LIST_H
20 #define GDBSUPPORT_INTRUSIVE_LIST_H
22 #define INTRUSIVE_LIST_UNLINKED_VALUE ((T *) -1)
24 /* A list node. The elements put in an intrusive_list either inherit
25 from this, or have a field of this type. */
26 template<typename T>
27 class intrusive_list_node
29 public:
30 bool is_linked () const
32 return next != INTRUSIVE_LIST_UNLINKED_VALUE;
35 private:
36 T *next = INTRUSIVE_LIST_UNLINKED_VALUE;
37 T *prev = INTRUSIVE_LIST_UNLINKED_VALUE;
39 template<typename T2, typename AsNode>
40 friend struct intrusive_list_iterator;
42 template<typename T2, typename AsNode>
43 friend struct intrusive_list_reverse_iterator;
45 template<typename T2, typename AsNode>
46 friend struct intrusive_list;
49 /* Follows a couple types used by intrusive_list as template parameter to find
50 the intrusive_list_node for a given element. One for lists where the
51 elements inherit intrusive_list_node, and another for elements that keep the
52 node as member field. */
54 /* For element types that inherit from intrusive_list_node. */
56 template<typename T>
57 struct intrusive_base_node
59 static intrusive_list_node<T> *as_node (T *elem)
60 { return elem; }
63 /* For element types that keep the node as member field. */
65 template<typename T, intrusive_list_node<T> T::*MemberNode>
66 struct intrusive_member_node
68 static intrusive_list_node<T> *as_node (T *elem)
69 { return &(elem->*MemberNode); }
72 /* Common code for forward and reverse iterators. */
74 template<typename T, typename AsNode, typename SelfType>
75 struct intrusive_list_base_iterator
77 using self_type = SelfType;
78 using iterator_category = std::bidirectional_iterator_tag;
79 using value_type = T;
80 using pointer = T *;
81 using const_pointer = const T *;
82 using reference = T &;
83 using const_reference = const T &;
84 using difference_type = ptrdiff_t;
85 using size_type = size_t;
86 using node_type = intrusive_list_node<T>;
88 /* Create an iterator pointing to ELEM. */
89 explicit intrusive_list_base_iterator (pointer elem)
90 : m_elem (elem)
93 /* Create a past-the-end iterator. */
94 intrusive_list_base_iterator ()
95 : m_elem (nullptr)
98 reference operator* () const
99 { return *m_elem; }
101 pointer operator-> () const
102 { return m_elem; }
104 bool operator== (const self_type &other) const
105 { return m_elem == other.m_elem; }
107 bool operator!= (const self_type &other) const
108 { return m_elem != other.m_elem; }
110 protected:
111 static node_type *as_node (pointer elem)
112 { return AsNode::as_node (elem); }
114 /* A past-end-the iterator points to the list's head. */
115 pointer m_elem;
118 /* Forward iterator for an intrusive_list. */
120 template<typename T, typename AsNode = intrusive_base_node<T>>
121 struct intrusive_list_iterator
122 : public intrusive_list_base_iterator
123 <T, AsNode, intrusive_list_iterator<T, AsNode>>
125 using base = intrusive_list_base_iterator
126 <T, AsNode, intrusive_list_iterator<T, AsNode>>;
127 using self_type = typename base::self_type;
128 using node_type = typename base::node_type;
130 /* Inherit constructor and M_NODE visibility from base. */
131 using base::base;
132 using base::m_elem;
134 self_type &operator++ ()
136 node_type *node = this->as_node (m_elem);
137 m_elem = node->next;
138 return *this;
141 self_type operator++ (int)
143 self_type temp = *this;
144 node_type *node = this->as_node (m_elem);
145 m_elem = node->next;
146 return temp;
149 self_type &operator-- ()
151 node_type *node = this->as_node (m_elem);
152 m_elem = node->prev;
153 return *this;
156 self_type operator-- (int)
158 self_type temp = *this;
159 node_type *node = this->as_node (m_elem);
160 m_elem = node->prev;
161 return temp;
165 /* Reverse iterator for an intrusive_list. */
167 template<typename T, typename AsNode = intrusive_base_node<T>>
168 struct intrusive_list_reverse_iterator
169 : public intrusive_list_base_iterator
170 <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>
172 using base = intrusive_list_base_iterator
173 <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>;
174 using self_type = typename base::self_type;
176 /* Inherit constructor and M_NODE visibility from base. */
177 using base::base;
178 using base::m_elem;
179 using node_type = typename base::node_type;
181 self_type &operator++ ()
183 node_type *node = this->as_node (m_elem);
184 m_elem = node->prev;
185 return *this;
188 self_type operator++ (int)
190 self_type temp = *this;
191 node_type *node = this->as_node (m_elem);
192 m_elem = node->prev;
193 return temp;
196 self_type &operator-- ()
198 node_type *node = this->as_node (m_elem);
199 m_elem = node->next;
200 return *this;
203 self_type operator-- (int)
205 self_type temp = *this;
206 node_type *node = this->as_node (m_elem);
207 m_elem = node->next;
208 return temp;
212 /* An intrusive double-linked list.
214 T is the type of the elements to link. The type T must either:
216 - inherit from intrusive_list_node<T>
217 - have an intrusive_list_node<T> member
219 AsNode is a type with an as_node static method used to get a node from an
220 element. If elements inherit from intrusive_list_node<T>, use the default
221 intrusive_base_node<T>. If elements have an intrusive_list_node<T> member,
222 use:
224 intrusive_member_node<T, &T::member>
226 where `member` is the name of the member. */
228 template <typename T, typename AsNode = intrusive_base_node<T>>
229 class intrusive_list
231 public:
232 using value_type = T;
233 using pointer = T *;
234 using const_pointer = const T *;
235 using reference = T &;
236 using const_reference = const T &;
237 using difference_type = ptrdiff_t;
238 using size_type = size_t;
239 using iterator = intrusive_list_iterator<T, AsNode>;
240 using reverse_iterator = intrusive_list_reverse_iterator<T, AsNode>;
241 using const_iterator = const intrusive_list_iterator<T, AsNode>;
242 using const_reverse_iterator
243 = const intrusive_list_reverse_iterator<T, AsNode>;
244 using node_type = intrusive_list_node<T>;
246 intrusive_list () = default;
248 ~intrusive_list ()
250 clear ();
253 intrusive_list (intrusive_list &&other)
254 : m_front (other.m_front),
255 m_back (other.m_back)
257 other.m_front = nullptr;
258 other.m_back = nullptr;
261 intrusive_list &operator= (intrusive_list &&other)
263 m_front = other.m_front;
264 m_back = other.m_back;
265 other.m_front = nullptr;
266 other.m_back = nullptr;
268 return *this;
271 void swap (intrusive_list &other)
273 std::swap (m_front, other.m_front);
274 std::swap (m_back, other.m_back);
277 iterator iterator_to (reference value)
279 return iterator (&value);
282 const_iterator iterator_to (const_reference value)
284 return const_iterator (&value);
287 reference front ()
289 gdb_assert (!this->empty ());
290 return *m_front;
293 const_reference front () const
295 gdb_assert (!this->empty ());
296 return *m_front;
299 reference back ()
301 gdb_assert (!this->empty ());
302 return *m_back;
305 const_reference back () const
307 gdb_assert (!this->empty ());
308 return *m_back;
311 void push_front (reference elem)
313 intrusive_list_node<T> *elem_node = as_node (&elem);
315 gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
316 gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
318 if (this->empty ())
319 this->push_empty (elem);
320 else
321 this->push_front_non_empty (elem);
324 void push_back (reference elem)
326 intrusive_list_node<T> *elem_node = as_node (&elem);
328 gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
329 gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
331 if (this->empty ())
332 this->push_empty (elem);
333 else
334 this->push_back_non_empty (elem);
337 /* Inserts ELEM before POS. */
338 void insert (const_iterator pos, reference elem)
340 if (this->empty ())
341 return this->push_empty (elem);
343 if (pos == this->begin ())
344 return this->push_front_non_empty (elem);
346 if (pos == this->end ())
347 return this->push_back_non_empty (elem);
349 intrusive_list_node<T> *elem_node = as_node (&elem);
350 pointer pos_elem = &*pos;
351 intrusive_list_node<T> *pos_node = as_node (pos_elem);
352 pointer prev_elem = pos_node->prev;
353 intrusive_list_node<T> *prev_node = as_node (prev_elem);
355 gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
356 gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
358 elem_node->prev = prev_elem;
359 prev_node->next = &elem;
360 elem_node->next = pos_elem;
361 pos_node->prev = &elem;
364 /* Move elements from LIST at the end of the current list. */
365 void splice (intrusive_list &&other)
367 if (other.empty ())
368 return;
370 if (this->empty ())
372 *this = std::move (other);
373 return;
376 /* [A ... B] + [C ... D] */
377 pointer b_elem = m_back;
378 node_type *b_node = as_node (b_elem);
379 pointer c_elem = other.m_front;
380 node_type *c_node = as_node (c_elem);
381 pointer d_elem = other.m_back;
383 b_node->next = c_elem;
384 c_node->prev = b_elem;
385 m_back = d_elem;
387 other.m_front = nullptr;
388 other.m_back = nullptr;
391 void pop_front ()
393 gdb_assert (!this->empty ());
394 erase_element (*m_front);
397 void pop_back ()
399 gdb_assert (!this->empty ());
400 erase_element (*m_back);
403 private:
404 /* Push ELEM in the list, knowing the list is empty. */
405 void push_empty (reference elem)
407 gdb_assert (this->empty ());
409 intrusive_list_node<T> *elem_node = as_node (&elem);
411 gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
412 gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
414 m_front = &elem;
415 m_back = &elem;
416 elem_node->prev = nullptr;
417 elem_node->next = nullptr;
420 /* Push ELEM at the front of the list, knowing the list is not empty. */
421 void push_front_non_empty (reference elem)
423 gdb_assert (!this->empty ());
425 intrusive_list_node<T> *elem_node = as_node (&elem);
426 intrusive_list_node<T> *front_node = as_node (m_front);
428 gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
429 gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
431 elem_node->next = m_front;
432 front_node->prev = &elem;
433 elem_node->prev = nullptr;
434 m_front = &elem;
437 /* Push ELEM at the back of the list, knowing the list is not empty. */
438 void push_back_non_empty (reference elem)
440 gdb_assert (!this->empty ());
442 intrusive_list_node<T> *elem_node = as_node (&elem);
443 intrusive_list_node<T> *back_node = as_node (m_back);
445 gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
446 gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
448 elem_node->prev = m_back;
449 back_node->next = &elem;
450 elem_node->next = nullptr;
451 m_back = &elem;
454 void erase_element (reference elem)
456 intrusive_list_node<T> *elem_node = as_node (&elem);
458 gdb_assert (elem_node->prev != INTRUSIVE_LIST_UNLINKED_VALUE);
459 gdb_assert (elem_node->next != INTRUSIVE_LIST_UNLINKED_VALUE);
461 if (m_front == &elem)
463 gdb_assert (elem_node->prev == nullptr);
464 m_front = elem_node->next;
466 else
468 gdb_assert (elem_node->prev != nullptr);
469 intrusive_list_node<T> *prev_node = as_node (elem_node->prev);
470 prev_node->next = elem_node->next;
473 if (m_back == &elem)
475 gdb_assert (elem_node->next == nullptr);
476 m_back = elem_node->prev;
478 else
480 gdb_assert (elem_node->next != nullptr);
481 intrusive_list_node<T> *next_node = as_node (elem_node->next);
482 next_node->prev = elem_node->prev;
485 elem_node->next = INTRUSIVE_LIST_UNLINKED_VALUE;
486 elem_node->prev = INTRUSIVE_LIST_UNLINKED_VALUE;
489 public:
490 /* Remove the element pointed by I from the list. The element
491 pointed by I is not destroyed. */
492 iterator erase (const_iterator i)
494 iterator ret = i;
495 ++ret;
497 erase_element (*i);
499 return ret;
502 /* Erase all the elements. The elements are not destroyed. */
503 void clear ()
505 while (!this->empty ())
506 pop_front ();
509 /* Erase all the elements. Disposer::operator()(pointer) is called
510 for each of the removed elements. */
511 template<typename Disposer>
512 void clear_and_dispose (Disposer disposer)
514 while (!this->empty ())
516 pointer p = &front ();
517 pop_front ();
518 disposer (p);
522 bool empty () const
524 return m_front == nullptr;
527 iterator begin () noexcept
529 return iterator (m_front);
532 const_iterator begin () const noexcept
534 return const_iterator (m_front);
537 const_iterator cbegin () const noexcept
539 return const_iterator (m_front);
542 iterator end () noexcept
544 return {};
547 const_iterator end () const noexcept
549 return {};
552 const_iterator cend () const noexcept
554 return {};
557 reverse_iterator rbegin () noexcept
559 return reverse_iterator (m_back);
562 const_reverse_iterator rbegin () const noexcept
564 return const_reverse_iterator (m_back);
567 const_reverse_iterator crbegin () const noexcept
569 return const_reverse_iterator (m_back);
572 reverse_iterator rend () noexcept
574 return {};
577 const_reverse_iterator rend () const noexcept
579 return {};
582 const_reverse_iterator crend () const noexcept
584 return {};
587 private:
588 static node_type *as_node (pointer elem)
590 return AsNode::as_node (elem);
593 pointer m_front = nullptr;
594 pointer m_back = nullptr;
597 #endif /* GDBSUPPORT_INTRUSIVE_LIST_H */