linked_list.h 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191
  1. // Copyright (c) 2009 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_CONTAINERS_LINKED_LIST_H_
  5. #define BASE_CONTAINERS_LINKED_LIST_H_
  6. #include "base/base_export.h"
  7. #include "base/memory/raw_ptr_exclusion.h"
  8. // Simple LinkedList type. (See the Q&A section to understand how this
  9. // differs from std::list).
  10. //
  11. // To use, start by declaring the class which will be contained in the linked
  12. // list, as extending LinkNode (this gives it next/previous pointers).
  13. //
  14. // class MyNodeType : public LinkNode<MyNodeType> {
  15. // ...
  16. // };
  17. //
  18. // Next, to keep track of the list's head/tail, use a LinkedList instance:
  19. //
  20. // LinkedList<MyNodeType> list;
  21. //
  22. // To add elements to the list, use any of LinkedList::Append,
  23. // LinkNode::InsertBefore, or LinkNode::InsertAfter:
  24. //
  25. // LinkNode<MyNodeType>* n1 = ...;
  26. // LinkNode<MyNodeType>* n2 = ...;
  27. // LinkNode<MyNodeType>* n3 = ...;
  28. //
  29. // list.Append(n1);
  30. // list.Append(n3);
  31. // n2->InsertBefore(n3);
  32. //
  33. // Lastly, to iterate through the linked list forwards:
  34. //
  35. // for (LinkNode<MyNodeType>* node = list.head();
  36. // node != list.end();
  37. // node = node->next()) {
  38. // MyNodeType* value = node->value();
  39. // ...
  40. // }
  41. //
  42. // Or to iterate the linked list backwards:
  43. //
  44. // for (LinkNode<MyNodeType>* node = list.tail();
  45. // node != list.end();
  46. // node = node->previous()) {
  47. // MyNodeType* value = node->value();
  48. // ...
  49. // }
  50. //
  51. // Questions and Answers:
  52. //
  53. // Q. Should I use std::list or base::LinkedList?
  54. //
  55. // A. The main reason to use base::LinkedList over std::list is
  56. // performance. If you don't care about the performance differences
  57. // then use an STL container, as it makes for better code readability.
  58. //
  59. // Comparing the performance of base::LinkedList<T> to std::list<T*>:
  60. //
  61. // * Erasing an element of type T* from base::LinkedList<T> is
  62. // an O(1) operation. Whereas for std::list<T*> it is O(n).
  63. // That is because with std::list<T*> you must obtain an
  64. // iterator to the T* element before you can call erase(iterator).
  65. //
  66. // * Insertion operations with base::LinkedList<T> never require
  67. // heap allocations.
  68. //
  69. // Q. How does base::LinkedList implementation differ from std::list?
  70. //
  71. // A. Doubly-linked lists are made up of nodes that contain "next" and
  72. // "previous" pointers that reference other nodes in the list.
  73. //
  74. // With base::LinkedList<T>, the type being inserted already reserves
  75. // space for the "next" and "previous" pointers (base::LinkNode<T>*).
  76. // Whereas with std::list<T> the type can be anything, so the implementation
  77. // needs to glue on the "next" and "previous" pointers using
  78. // some internal node type.
  79. namespace base {
  80. namespace internal {
  81. // Base class for LinkNode<T> type
  82. class BASE_EXPORT LinkNodeBase {
  83. public:
  84. void RemoveFromList();
  85. protected:
  86. LinkNodeBase();
  87. LinkNodeBase(LinkNodeBase* previous, LinkNodeBase* next);
  88. LinkNodeBase(LinkNodeBase&& rhs);
  89. LinkNodeBase(const LinkNodeBase&) = delete;
  90. ~LinkNodeBase() = default;
  91. LinkNodeBase& operator=(const LinkNodeBase&) = delete;
  92. // Calling these with |e| as a different LinkNode type as |this| is
  93. // unsafe. These are protected and only called from LinkNode<T> to
  94. // ensure safety.
  95. void InsertBeforeBase(LinkNodeBase* e);
  96. void InsertAfterBase(LinkNodeBase* e);
  97. LinkNodeBase* previous_base() const { return previous_; }
  98. LinkNodeBase* next_base() const { return next_; }
  99. private:
  100. // `previous_` and `next_` are not a raw_ptr<...> for performance reasons:
  101. // on-stack pointer + a large number of non-PA pointees through WeakLinkNode +
  102. // based on analysis of sampling profiler data and tab_search:top100:2020.
  103. RAW_PTR_EXCLUSION LinkNodeBase* previous_ = nullptr;
  104. RAW_PTR_EXCLUSION LinkNodeBase* next_ = nullptr;
  105. };
  106. } // namespace internal
  107. template <typename T>
  108. class LinkNode : public internal::LinkNodeBase {
  109. public:
  110. LinkNode() = default;
  111. LinkNode(LinkNode<T>* previous, LinkNode<T>* next)
  112. : internal::LinkNodeBase(previous, next) {}
  113. LinkNode(LinkNode<T>&&) = default;
  114. LinkNode(const LinkNode&) = delete;
  115. LinkNode& operator=(const LinkNode&) = delete;
  116. // Insert |this| into the linked list, before |e|. |this| must not
  117. // already be in a list.
  118. void InsertBefore(LinkNode<T>* e) { InsertBeforeBase(e); }
  119. // Insert |this| into the linked list, after |e|. |this| must not
  120. // already be in a list.
  121. void InsertAfter(LinkNode<T>* e) { InsertAfterBase(e); }
  122. LinkNode<T>* previous() const {
  123. return static_cast<LinkNode<T>*>(previous_base());
  124. }
  125. LinkNode<T>* next() const { return static_cast<LinkNode<T>*>(next_base()); }
  126. // Cast from the node-type to the value type.
  127. const T* value() const {
  128. return static_cast<const T*>(this);
  129. }
  130. T* value() {
  131. return static_cast<T*>(this);
  132. }
  133. };
  134. template <typename T>
  135. class LinkedList {
  136. public:
  137. // The "root" node is self-referential, and forms the basis of a circular
  138. // list (root_.next() will point back to the start of the list,
  139. // and root_->previous() wraps around to the end of the list).
  140. LinkedList() : root_(&root_, &root_) {}
  141. LinkedList(const LinkedList&) = delete;
  142. LinkedList& operator=(const LinkedList&) = delete;
  143. // Appends |e| to the end of the linked list.
  144. void Append(LinkNode<T>* e) {
  145. e->InsertBefore(&root_);
  146. }
  147. LinkNode<T>* head() const {
  148. return root_.next();
  149. }
  150. LinkNode<T>* tail() const {
  151. return root_.previous();
  152. }
  153. const LinkNode<T>* end() const {
  154. return &root_;
  155. }
  156. bool empty() const { return head() == end(); }
  157. private:
  158. LinkNode<T> root_;
  159. };
  160. } // namespace base
  161. #endif // BASE_CONTAINERS_LINKED_LIST_H_