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