gdbsupport/intrusive_list.h

   1 /* Intrusive double linked list for GDB, the GNU debugger.
   2    Copyright (C) 2021-2022 Free Software Foundation, Inc.
   3
   4    This file is part of GDB.
   5
   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.
  10
  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.
  15
  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/>.  */
  18
  19 #ifndef GDBSUPPORT_INTRUSIVE_LIST_H
  20 #define GDBSUPPORT_INTRUSIVE_LIST_H
  21
  22 #define INTRUSIVE_LIST_UNLINKED_VALUE ((T *) -1)
  23
  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
  28 {
  29 public:
  30   bool is_linked () const
  31   {
  32     return next != INTRUSIVE_LIST_UNLINKED_VALUE;
  33   }
  34
  35 private:
  36   T *next = INTRUSIVE_LIST_UNLINKED_VALUE;
  37   T *prev = INTRUSIVE_LIST_UNLINKED_VALUE;
  38
  39   template<typename T2, typename AsNode>
  40   friend struct intrusive_list_iterator;
  41
  42   template<typename T2, typename AsNode>
  43   friend struct intrusive_list_reverse_iterator;
  44
  45   template<typename T2, typename AsNode>
  46   friend struct intrusive_list;
  47 };
  48
  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.  */
  53
  54 /* For element types that inherit from intrusive_list_node.  */
  55
  56 template<typename T>
  57 struct intrusive_base_node
  58 {
  59   static intrusive_list_node<T> *as_node (T *elem)
  60   { return elem; }
  61 };
  62
  63 /* For element types that keep the node as member field.  */
  64
  65 template<typename T, intrusive_list_node<T> T::*MemberNode>
  66 struct intrusive_member_node
  67 {
  68   static intrusive_list_node<T> *as_node (T *elem)
  69   { return &(elem->*MemberNode); }
  70 };
  71
  72 /* Common code for forward and reverse iterators.  */
  73
  74 template<typename T, typename AsNode, typename SelfType>
  75 struct intrusive_list_base_iterator
  76 {
  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>;
  87
  88   /* Create an iterator pointing to ELEM.  */
  89   explicit intrusive_list_base_iterator (T *elem)
  90     : m_elem (elem)
  91   {}
  92
  93   /* Create a past-the-end iterator.  */
  94   intrusive_list_base_iterator ()
  95     : m_elem (nullptr)
  96   {}
  97
  98   reference operator* () const
  99   { return *m_elem; }
 100
 101   pointer operator-> () const
 102   { return m_elem; }
 103
 104   bool operator== (const self_type &other) const
 105   { return m_elem == other.m_elem; }
 106
 107   bool operator!= (const self_type &other) const
 108   { return m_elem != other.m_elem; }
 109
 110 protected:
 111   static node_type *as_node (T *elem)
 112   { return AsNode::as_node (elem); }
 113
 114   /* A past-end-the iterator points to the list's head.  */
 115   pointer m_elem;
 116 };
 117
 118 /* Forward iterator for an intrusive_list.  */
 119
 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>>
 124 {
 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;
 129
 130   /* Inherit constructor and M_NODE visibility from base.  */
 131   using base::base;
 132   using base::m_elem;
 133
 134   self_type &operator++ ()
 135   {
 136     node_type *node = this->as_node (m_elem);
 137     m_elem = node->next;
 138     return *this;
 139   }
 140
 141   self_type operator++ (int)
 142   {
 143     self_type temp = *this;
 144     node_type *node = this->as_node (m_elem);
 145     m_elem = node->next;
 146     return temp;
 147   }
 148
 149   self_type &operator-- ()
 150   {
 151     node_type *node = this->as_node (m_elem);
 152     m_elem = node->prev;
 153     return *this;
 154   }
 155
 156   self_type operator-- (int)
 157   {
 158     self_type temp = *this;
 159     node_type *node = this->as_node (m_elem);
 160     m_elem = node->prev;
 161     return temp;
 162   }
 163 };
 164
 165 /* Reverse iterator for an intrusive_list.  */
 166
 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>>
 171 {
 172   using base = intrusive_list_base_iterator
 173                  <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>;
 174   using self_type = typename base::self_type;
 175
 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;
 180
 181   self_type &operator++ ()
 182   {
 183     node_type *node = this->as_node (m_elem);
 184     m_elem = node->prev;
 185     return *this;
 186   }
 187
 188   self_type operator++ (int)
 189   {
 190     self_type temp = *this;
 191     node_type *node = this->as_node (m_elem);
 192     m_elem = node->prev;
 193     return temp;
 194   }
 195
 196   self_type &operator-- ()
 197   {
 198     node_type *node = this->as_node (m_elem);
 199     m_elem = node->next;
 200     return *this;
 201   }
 202
 203   self_type operator-- (int)
 204   {
 205     self_type temp = *this;
 206     node_type *node = this->as_node (m_elem);
 207     m_elem = node->next;
 208     return temp;
 209   }
 210 };
 211
 212 /* An intrusive double-linked list.
 213
 214    T is the type of the elements to link.  The type T must either:
 215
 216     - inherit from intrusive_list_node<T>
 217     - have an intrusive_list_node<T> member
 218
 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:
 223
 224      intrusive_member_node<T, &T::member>
 225
 226    where `member` is the name of the member.  */
 227
 228 template <typename T, typename AsNode = intrusive_base_node<T>>
 229 class intrusive_list
 230 {
 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>;
 245
 246   intrusive_list () = default;
 247
 248   ~intrusive_list ()
 249   {
 250     clear ();
 251   }
 252
 253   intrusive_list (intrusive_list &&other)
 254     : m_front (other.m_front),
 255       m_back (other.m_back)
 256   {
 257     other.m_front = nullptr;
 258     other.m_back = nullptr;
 259   }
 260
 261   intrusive_list &operator= (intrusive_list &&other)
 262   {
 263     m_front = other.m_front;
 264     m_back = other.m_back;
 265     other.m_front = nullptr;
 266     other.m_back = nullptr;
 267
 268     return *this;
 269   }
 270
 271   void swap (intrusive_list &other)
 272   {
 273     std::swap (m_front, other.m_front);
 274     std::swap (m_back, other.m_back);
 275   }
 276
 277   iterator iterator_to (reference value)
 278   {
 279     return iterator (&value);
 280   }
 281
 282   const_iterator iterator_to (const_reference value)
 283   {
 284     return const_iterator (&value);
 285   }
 286
 287   reference front ()
 288   {
 289     gdb_assert (!this->empty ());
 290     return *m_front;
 291   }
 292
 293   const_reference front () const
 294   {
 295     gdb_assert (!this->empty ());
 296     return *m_front;
 297   }
 298
 299   reference back ()
 300   {
 301     gdb_assert (!this->empty ());
 302     return *m_back;
 303   }
 304
 305   const_reference back () const
 306   {
 307     gdb_assert (!this->empty ());
 308     return *m_back;
 309   }
 310
 311   void push_front (reference elem)
 312   {
 313     intrusive_list_node<T> *elem_node = as_node (&elem);
 314
 315     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 316     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 317
 318     if (this->empty ())
 319       this->push_empty (elem);
 320     else
 321       this->push_front_non_empty (elem);
 322   }
 323
 324   void push_back (reference elem)
 325   {
 326     intrusive_list_node<T> *elem_node = as_node (&elem);
 327
 328     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 329     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 330
 331     if (this->empty ())
 332       this->push_empty (elem);
 333     else
 334       this->push_back_non_empty (elem);
 335   }
 336
 337   /* Inserts ELEM before POS.  */
 338   void insert (const_iterator pos, reference elem)
 339   {
 340     if (this->empty ())
 341       return this->push_empty (elem);
 342
 343     if (pos == this->begin ())
 344       return this->push_front_non_empty (elem);
 345
 346     if (pos == this->end ())
 347       return this->push_back_non_empty (elem);
 348
 349     intrusive_list_node<T> *elem_node = as_node (&elem);
 350     T *pos_elem = &*pos;
 351     intrusive_list_node<T> *pos_node = as_node (pos_elem);
 352     T *prev_elem = pos_node->prev;
 353     intrusive_list_node<T> *prev_node = as_node (prev_elem);
 354
 355     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 356     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 357
 358     elem_node->prev = prev_elem;
 359     prev_node->next = &elem;
 360     elem_node->next = pos_elem;
 361     pos_node->prev = &elem;
 362   }
 363
 364   /* Move elements from LIST at the end of the current list.  */
 365   void splice (intrusive_list &&other)
 366   {
 367     if (other.empty ())
 368       return;
 369
 370     if (this->empty ())
 371       {
 372         *this = std::move (other);
 373         return;
 374       }
 375
 376     /* [A ... B] + [C ... D] */
 377     T *b_elem = m_back;
 378     node_type *b_node = as_node (b_elem);
 379     T *c_elem = other.m_front;
 380     node_type *c_node = as_node (c_elem);
 381     T *d_elem = other.m_back;
 382
 383     b_node->next = c_elem;
 384     c_node->prev = b_elem;
 385     m_back = d_elem;
 386
 387     other.m_front = nullptr;
 388     other.m_back = nullptr;
 389   }
 390
 391   void pop_front ()
 392   {
 393     gdb_assert (!this->empty ());
 394     erase_element (*m_front);
 395   }
 396
 397   void pop_back ()
 398   {
 399     gdb_assert (!this->empty ());
 400     erase_element (*m_back);
 401   }
 402
 403 private:
 404   /* Push ELEM in the list, knowing the list is empty.  */
 405   void push_empty (T &elem)
 406   {
 407     gdb_assert (this->empty ());
 408
 409     intrusive_list_node<T> *elem_node = as_node (&elem);
 410
 411     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 412     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 413
 414     m_front = &elem;
 415     m_back = &elem;
 416     elem_node->prev = nullptr;
 417     elem_node->next = nullptr;
 418   }
 419
 420   /* Push ELEM at the front of the list, knowing the list is not empty.  */
 421   void push_front_non_empty (T &elem)
 422   {
 423     gdb_assert (!this->empty ());
 424
 425     intrusive_list_node<T> *elem_node = as_node (&elem);
 426     intrusive_list_node<T> *front_node = as_node (m_front);
 427
 428     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 429     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 430
 431     elem_node->next = m_front;
 432     front_node->prev = &elem;
 433     elem_node->prev = nullptr;
 434     m_front = &elem;
 435   }
 436
 437   /* Push ELEM at the back of the list, knowing the list is not empty.  */
 438   void push_back_non_empty (T &elem)
 439   {
 440     gdb_assert (!this->empty ());
 441
 442     intrusive_list_node<T> *elem_node = as_node (&elem);
 443     intrusive_list_node<T> *back_node = as_node (m_back);
 444
 445     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 446     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 447
 448     elem_node->prev = m_back;
 449     back_node->next = &elem;
 450     elem_node->next = nullptr;
 451     m_back = &elem;
 452   }
 453
 454   void erase_element (T &elem)
 455   {
 456     intrusive_list_node<T> *elem_node = as_node (&elem);
 457
 458     gdb_assert (elem_node->prev != INTRUSIVE_LIST_UNLINKED_VALUE);
 459     gdb_assert (elem_node->next != INTRUSIVE_LIST_UNLINKED_VALUE);
 460
 461     if (m_front == &elem)
 462       {
 463         gdb_assert (elem_node->prev == nullptr);
 464         m_front = elem_node->next;
 465       }
 466     else
 467       {
 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;
 471       }
 472
 473     if (m_back == &elem)
 474       {
 475         gdb_assert (elem_node->next == nullptr);
 476         m_back = elem_node->prev;
 477       }
 478     else
 479       {
 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;
 483       }
 484
 485     elem_node->next = INTRUSIVE_LIST_UNLINKED_VALUE;
 486     elem_node->prev = INTRUSIVE_LIST_UNLINKED_VALUE;
 487   }
 488
 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)
 493   {
 494     iterator ret = i;
 495     ++ret;
 496
 497     erase_element (*i);
 498
 499     return ret;
 500   }
 501
 502   /* Erase all the elements.  The elements are not destroyed.  */
 503   void clear ()
 504   {
 505     while (!this->empty ())
 506       pop_front ();
 507   }
 508
 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)
 513   {
 514     while (!this->empty ())
 515       {
 516         pointer p = &front ();
 517         pop_front ();
 518         disposer (p);
 519       }
 520   }
 521
 522   bool empty () const
 523   {
 524     return m_front == nullptr;
 525   }
 526
 527   iterator begin () noexcept
 528   {
 529     return iterator (m_front);
 530   }
 531
 532   const_iterator begin () const noexcept
 533   {
 534     return const_iterator (m_front);
 535   }
 536
 537   const_iterator cbegin () const noexcept
 538   {
 539     return const_iterator (m_front);
 540   }
 541
 542   iterator end () noexcept
 543   {
 544     return {};
 545   }
 546
 547   const_iterator end () const noexcept
 548   {
 549     return {};
 550   }
 551
 552   const_iterator cend () const noexcept
 553   {
 554     return {};
 555   }
 556
 557   reverse_iterator rbegin () noexcept
 558   {
 559     return reverse_iterator (m_back);
 560   }
 561
 562   const_reverse_iterator rbegin () const noexcept
 563   {
 564     return const_reverse_iterator (m_back);
 565   }
 566
 567   const_reverse_iterator crbegin () const noexcept
 568   {
 569     return const_reverse_iterator (m_back);
 570   }
 571
 572   reverse_iterator rend () noexcept
 573   {
 574     return {};
 575   }
 576
 577   const_reverse_iterator rend () const noexcept
 578   {
 579     return {};
 580   }
 581
 582   const_reverse_iterator crend () const noexcept
 583   {
 584     return {};
 585   }
 586
 587 private:
 588   static node_type *as_node (T *elem)
 589   {
 590     return AsNode::as_node (elem);
 591   }
 592
 593   T *m_front = nullptr;
 594   T *m_back = nullptr;
 595 };
 596
 597 #endif /* GDBSUPPORT_INTRUSIVE_LIST_H */