gdbsupport/intrusive_list.h

   1 /* Intrusive double linked list for GDB, the GNU debugger.
   2    Copyright (C) 2021-2024 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 noexcept
  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) noexcept
  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) noexcept
  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 (pointer elem) noexcept
  90     : m_elem (elem)
  91   {}
  92
  93   /* Create a past-the-end iterator.  */
  94   intrusive_list_base_iterator () noexcept
  95     : m_elem (nullptr)
  96   {}
  97
  98   reference operator* () const noexcept
  99   { return *m_elem; }
 100
 101   pointer operator-> () const noexcept
 102   { return m_elem; }
 103
 104   bool operator== (const self_type &other) const noexcept
 105   { return m_elem == other.m_elem; }
 106
 107   bool operator!= (const self_type &other) const noexcept
 108   { return m_elem != other.m_elem; }
 109
 110 protected:
 111   static node_type *as_node (pointer elem) noexcept
 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++ () noexcept
 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) noexcept
 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-- () noexcept
 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) noexcept
 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++ () noexcept
 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) noexcept
 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-- () noexcept
 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) noexcept
 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 () noexcept = default;
 247
 248   ~intrusive_list ()
 249   {
 250     clear ();
 251   }
 252
 253   intrusive_list (intrusive_list &&other) noexcept
 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) noexcept
 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) noexcept
 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) noexcept
 278   {
 279     return iterator (&value);
 280   }
 281
 282   const_iterator iterator_to (const_reference value) noexcept
 283   {
 284     return const_iterator (&value);
 285   }
 286
 287   reference front () noexcept
 288   {
 289     gdb_assert (!this->empty ());
 290     return *m_front;
 291   }
 292
 293   const_reference front () const noexcept
 294   {
 295     gdb_assert (!this->empty ());
 296     return *m_front;
 297   }
 298
 299   reference back () noexcept
 300   {
 301     gdb_assert (!this->empty ());
 302     return *m_back;
 303   }
 304
 305   const_reference back () const noexcept
 306   {
 307     gdb_assert (!this->empty ());
 308     return *m_back;
 309   }
 310
 311   void push_front (reference elem) noexcept
 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) noexcept
 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
 339      Returns an iterator to the inserted element.  */
 340   iterator insert (const_iterator pos, reference elem) noexcept
 341   {
 342     if (this->empty ())
 343       return this->push_empty (elem);
 344
 345     if (pos == this->begin ())
 346       return this->push_front_non_empty (elem);
 347
 348     if (pos == this->end ())
 349       return this->push_back_non_empty (elem);
 350
 351     intrusive_list_node<T> *elem_node = as_node (&elem);
 352     pointer pos_elem = &*pos;
 353     intrusive_list_node<T> *pos_node = as_node (pos_elem);
 354     pointer prev_elem = pos_node->prev;
 355     intrusive_list_node<T> *prev_node = as_node (prev_elem);
 356
 357     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 358     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 359
 360     elem_node->prev = prev_elem;
 361     prev_node->next = &elem;
 362     elem_node->next = pos_elem;
 363     pos_node->prev = &elem;
 364
 365     return this->iterator_to (elem);
 366   }
 367
 368   /* Move elements from LIST at the end of the current list.  */
 369   void splice (intrusive_list &&other) noexcept
 370   {
 371     if (other.empty ())
 372       return;
 373
 374     if (this->empty ())
 375       {
 376         *this = std::move (other);
 377         return;
 378       }
 379
 380     /* [A ... B] + [C ... D] */
 381     pointer b_elem = m_back;
 382     node_type *b_node = as_node (b_elem);
 383     pointer c_elem = other.m_front;
 384     node_type *c_node = as_node (c_elem);
 385     pointer d_elem = other.m_back;
 386
 387     b_node->next = c_elem;
 388     c_node->prev = b_elem;
 389     m_back = d_elem;
 390
 391     other.m_front = nullptr;
 392     other.m_back = nullptr;
 393   }
 394
 395   void pop_front () noexcept
 396   {
 397     gdb_assert (!this->empty ());
 398     unlink_element (*m_front);
 399   }
 400
 401   void pop_back () noexcept
 402   {
 403     gdb_assert (!this->empty ());
 404     unlink_element (*m_back);
 405   }
 406
 407 private:
 408   /* Push ELEM in the list, knowing the list is empty.  */
 409   iterator push_empty (reference elem) noexcept
 410   {
 411     gdb_assert (this->empty ());
 412
 413     intrusive_list_node<T> *elem_node = as_node (&elem);
 414
 415     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 416     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 417
 418     m_front = &elem;
 419     m_back = &elem;
 420     elem_node->prev = nullptr;
 421     elem_node->next = nullptr;
 422
 423     return this->iterator_to (elem);
 424   }
 425
 426   /* Push ELEM at the front of the list, knowing the list is not empty.  */
 427   iterator push_front_non_empty (reference elem) noexcept
 428   {
 429     gdb_assert (!this->empty ());
 430
 431     intrusive_list_node<T> *elem_node = as_node (&elem);
 432     intrusive_list_node<T> *front_node = as_node (m_front);
 433
 434     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 435     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 436
 437     elem_node->next = m_front;
 438     front_node->prev = &elem;
 439     elem_node->prev = nullptr;
 440     m_front = &elem;
 441
 442     return this->iterator_to (elem);
 443   }
 444
 445   /* Push ELEM at the back of the list, knowing the list is not empty.  */
 446   iterator push_back_non_empty (reference elem) noexcept
 447   {
 448     gdb_assert (!this->empty ());
 449
 450     intrusive_list_node<T> *elem_node = as_node (&elem);
 451     intrusive_list_node<T> *back_node = as_node (m_back);
 452
 453     gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE);
 454     gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE);
 455
 456     elem_node->prev = m_back;
 457     back_node->next = &elem;
 458     elem_node->next = nullptr;
 459     m_back = &elem;
 460
 461     return this->iterator_to (elem);
 462   }
 463
 464 protected:
 465   void unlink_element (reference elem) noexcept
 466   {
 467     intrusive_list_node<T> *elem_node = as_node (&elem);
 468
 469     gdb_assert (elem_node->prev != INTRUSIVE_LIST_UNLINKED_VALUE);
 470     gdb_assert (elem_node->next != INTRUSIVE_LIST_UNLINKED_VALUE);
 471
 472     if (m_front == &elem)
 473       {
 474         gdb_assert (elem_node->prev == nullptr);
 475         m_front = elem_node->next;
 476       }
 477     else
 478       {
 479         gdb_assert (elem_node->prev != nullptr);
 480         intrusive_list_node<T> *prev_node = as_node (elem_node->prev);
 481         prev_node->next = elem_node->next;
 482       }
 483
 484     if (m_back == &elem)
 485       {
 486         gdb_assert (elem_node->next == nullptr);
 487         m_back = elem_node->prev;
 488       }
 489     else
 490       {
 491         gdb_assert (elem_node->next != nullptr);
 492         intrusive_list_node<T> *next_node = as_node (elem_node->next);
 493         next_node->prev = elem_node->prev;
 494       }
 495
 496     elem_node->next = INTRUSIVE_LIST_UNLINKED_VALUE;
 497     elem_node->prev = INTRUSIVE_LIST_UNLINKED_VALUE;
 498   }
 499
 500 public:
 501   /* Remove the element pointed by I from the list.  The element
 502      pointed by I is not destroyed.  */
 503   iterator erase (const_iterator i) noexcept
 504   {
 505     iterator ret = i;
 506     ++ret;
 507
 508     unlink_element (*i);
 509
 510     return ret;
 511   }
 512
 513   /* Erase all the elements.  The elements are not destroyed.  */
 514   void clear () noexcept
 515   {
 516     while (!this->empty ())
 517       pop_front ();
 518   }
 519
 520   /* Erase all the elements.  Disposer::operator()(pointer) is called
 521      for each of the removed elements.  */
 522   template<typename Disposer>
 523   void clear_and_dispose (Disposer disposer) noexcept
 524   {
 525     while (!this->empty ())
 526       {
 527         pointer p = &front ();
 528         pop_front ();
 529         disposer (p);
 530       }
 531   }
 532
 533   bool empty () const noexcept
 534   {
 535     return m_front == nullptr;
 536   }
 537
 538   iterator begin () noexcept
 539   {
 540     return iterator (m_front);
 541   }
 542
 543   const_iterator begin () const noexcept
 544   {
 545     return const_iterator (m_front);
 546   }
 547
 548   const_iterator cbegin () const noexcept
 549   {
 550     return const_iterator (m_front);
 551   }
 552
 553   iterator end () noexcept
 554   {
 555     return {};
 556   }
 557
 558   const_iterator end () const noexcept
 559   {
 560     return {};
 561   }
 562
 563   const_iterator cend () const noexcept
 564   {
 565     return {};
 566   }
 567
 568   reverse_iterator rbegin () noexcept
 569   {
 570     return reverse_iterator (m_back);
 571   }
 572
 573   const_reverse_iterator rbegin () const noexcept
 574   {
 575     return const_reverse_iterator (m_back);
 576   }
 577
 578   const_reverse_iterator crbegin () const noexcept
 579   {
 580     return const_reverse_iterator (m_back);
 581   }
 582
 583   reverse_iterator rend () noexcept
 584   {
 585     return {};
 586   }
 587
 588   const_reverse_iterator rend () const noexcept
 589   {
 590     return {};
 591   }
 592
 593   const_reverse_iterator crend () const noexcept
 594   {
 595     return {};
 596   }
 597
 598 private:
 599   static node_type *as_node (pointer elem) noexcept
 600   {
 601     return AsNode::as_node (elem);
 602   }
 603
 604   pointer m_front = nullptr;
 605   pointer m_back = nullptr;
 606 };
 607
 608 #endif /* GDBSUPPORT_INTRUSIVE_LIST_H */