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 5 #ifndef BASE_CONTAINERS_LINKED_LIST_H_ 6 #define BASE_CONTAINERS_LINKED_LIST_H_ 7 8 #include "base/macros.h" 9 10 // Simple LinkedList type. (See the Q&A section to understand how this 11 // differs from std::list). 12 // 13 // To use, start by declaring the class which will be contained in the linked 14 // list, as extending LinkNode (this gives it next/previous pointers). 15 // 16 // class MyNodeType : public LinkNode<MyNodeType> { 17 // ... 18 // }; 19 // 20 // Next, to keep track of the list's head/tail, use a LinkedList instance: 21 // 22 // LinkedList<MyNodeType> list; 23 // 24 // To add elements to the list, use any of LinkedList::Append, 25 // LinkNode::InsertBefore, or LinkNode::InsertAfter: 26 // 27 // LinkNode<MyNodeType>* n1 = ...; 28 // LinkNode<MyNodeType>* n2 = ...; 29 // LinkNode<MyNodeType>* n3 = ...; 30 // 31 // list.Append(n1); 32 // list.Append(n3); 33 // n3->InsertBefore(n3); 34 // 35 // Lastly, to iterate through the linked list forwards: 36 // 37 // for (LinkNode<MyNodeType>* node = list.head(); 38 // node != list.end(); 39 // node = node->next()) { 40 // MyNodeType* value = node->value(); 41 // ... 42 // } 43 // 44 // Or to iterate the linked list backwards: 45 // 46 // for (LinkNode<MyNodeType>* node = list.tail(); 47 // node != list.end(); 48 // node = node->previous()) { 49 // MyNodeType* value = node->value(); 50 // ... 51 // } 52 // 53 // Questions and Answers: 54 // 55 // Q. Should I use std::list or base::LinkedList? 56 // 57 // A. The main reason to use base::LinkedList over std::list is 58 // performance. If you don't care about the performance differences 59 // then use an STL container, as it makes for better code readability. 60 // 61 // Comparing the performance of base::LinkedList<T> to std::list<T*>: 62 // 63 // * Erasing an element of type T* from base::LinkedList<T> is 64 // an O(1) operation. Whereas for std::list<T*> it is O(n). 65 // That is because with std::list<T*> you must obtain an 66 // iterator to the T* element before you can call erase(iterator). 67 // 68 // * Insertion operations with base::LinkedList<T> never require 69 // heap allocations. 70 // 71 // Q. How does base::LinkedList implementation differ from std::list? 72 // 73 // A. Doubly-linked lists are made up of nodes that contain "next" and 74 // "previous" pointers that reference other nodes in the list. 75 // 76 // With base::LinkedList<T>, the type being inserted already reserves 77 // space for the "next" and "previous" pointers (base::LinkNode<T>*). 78 // Whereas with std::list<T> the type can be anything, so the implementation 79 // needs to glue on the "next" and "previous" pointers using 80 // some internal node type. 81 82 namespace base { 83 84 template <typename T> 85 class LinkNode { 86 public: LinkNode()87 LinkNode() : previous_(nullptr), next_(nullptr) {} LinkNode(LinkNode<T> * previous,LinkNode<T> * next)88 LinkNode(LinkNode<T>* previous, LinkNode<T>* next) 89 : previous_(previous), next_(next) {} 90 LinkNode(LinkNode<T> && rhs)91 LinkNode(LinkNode<T>&& rhs) { 92 next_ = rhs.next_; 93 rhs.next_ = nullptr; 94 previous_ = rhs.previous_; 95 rhs.previous_ = nullptr; 96 97 // If the node belongs to a list, next_ and previous_ are both non-null. 98 // Otherwise, they are both null. 99 if (next_) { 100 next_->previous_ = this; 101 previous_->next_ = this; 102 } 103 } 104 105 // Insert |this| into the linked list, before |e|. InsertBefore(LinkNode<T> * e)106 void InsertBefore(LinkNode<T>* e) { 107 this->next_ = e; 108 this->previous_ = e->previous_; 109 e->previous_->next_ = this; 110 e->previous_ = this; 111 } 112 113 // Insert |this| into the linked list, after |e|. InsertAfter(LinkNode<T> * e)114 void InsertAfter(LinkNode<T>* e) { 115 this->next_ = e->next_; 116 this->previous_ = e; 117 e->next_->previous_ = this; 118 e->next_ = this; 119 } 120 121 // Remove |this| from the linked list. RemoveFromList()122 void RemoveFromList() { 123 this->previous_->next_ = this->next_; 124 this->next_->previous_ = this->previous_; 125 // next() and previous() return non-null if and only this node is not in any 126 // list. 127 this->next_ = nullptr; 128 this->previous_ = nullptr; 129 } 130 previous()131 LinkNode<T>* previous() const { 132 return previous_; 133 } 134 next()135 LinkNode<T>* next() const { 136 return next_; 137 } 138 139 // Cast from the node-type to the value type. value()140 const T* value() const { 141 return static_cast<const T*>(this); 142 } 143 value()144 T* value() { 145 return static_cast<T*>(this); 146 } 147 148 private: 149 LinkNode<T>* previous_; 150 LinkNode<T>* next_; 151 152 DISALLOW_COPY_AND_ASSIGN(LinkNode); 153 }; 154 155 template <typename T> 156 class LinkedList { 157 public: 158 // The "root" node is self-referential, and forms the basis of a circular 159 // list (root_.next() will point back to the start of the list, 160 // and root_->previous() wraps around to the end of the list). LinkedList()161 LinkedList() : root_(&root_, &root_) {} 162 163 // Appends |e| to the end of the linked list. Append(LinkNode<T> * e)164 void Append(LinkNode<T>* e) { 165 e->InsertBefore(&root_); 166 } 167 head()168 LinkNode<T>* head() const { 169 return root_.next(); 170 } 171 tail()172 LinkNode<T>* tail() const { 173 return root_.previous(); 174 } 175 end()176 const LinkNode<T>* end() const { 177 return &root_; 178 } 179 empty()180 bool empty() const { return head() == end(); } 181 182 private: 183 LinkNode<T> root_; 184 185 DISALLOW_COPY_AND_ASSIGN(LinkedList); 186 }; 187 188 } // namespace base 189 190 #endif // BASE_CONTAINERS_LINKED_LIST_H_ 191