• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_(NULL), next_(NULL) {}
LinkNode(LinkNode<T> * previous,LinkNode<T> * next)88   LinkNode(LinkNode<T>* previous, LinkNode<T>* next)
89       : previous_(previous), next_(next) {}
90 
91   // Insert |this| into the linked list, before |e|.
InsertBefore(LinkNode<T> * e)92   void InsertBefore(LinkNode<T>* e) {
93     this->next_ = e;
94     this->previous_ = e->previous_;
95     e->previous_->next_ = this;
96     e->previous_ = this;
97   }
98 
99   // Insert |this| into the linked list, after |e|.
InsertAfter(LinkNode<T> * e)100   void InsertAfter(LinkNode<T>* e) {
101     this->next_ = e->next_;
102     this->previous_ = e;
103     e->next_->previous_ = this;
104     e->next_ = this;
105   }
106 
107   // Remove |this| from the linked list.
RemoveFromList()108   void RemoveFromList() {
109     this->previous_->next_ = this->next_;
110     this->next_->previous_ = this->previous_;
111     // next() and previous() return non-NULL if and only this node is not in any
112     // list.
113     this->next_ = NULL;
114     this->previous_ = NULL;
115   }
116 
previous()117   LinkNode<T>* previous() const {
118     return previous_;
119   }
120 
next()121   LinkNode<T>* next() const {
122     return next_;
123   }
124 
125   // Cast from the node-type to the value type.
value()126   const T* value() const {
127     return static_cast<const T*>(this);
128   }
129 
value()130   T* value() {
131     return static_cast<T*>(this);
132   }
133 
134  private:
135   LinkNode<T>* previous_;
136   LinkNode<T>* next_;
137 
138   DISALLOW_COPY_AND_ASSIGN(LinkNode);
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).
LinkedList()147   LinkedList() : root_(&root_, &root_) {}
148 
149   // Appends |e| to the end of the linked list.
Append(LinkNode<T> * e)150   void Append(LinkNode<T>* e) {
151     e->InsertBefore(&root_);
152   }
153 
head()154   LinkNode<T>* head() const {
155     return root_.next();
156   }
157 
tail()158   LinkNode<T>* tail() const {
159     return root_.previous();
160   }
161 
end()162   const LinkNode<T>* end() const {
163     return &root_;
164   }
165 
empty()166   bool empty() const { return head() == end(); }
167 
168  private:
169   LinkNode<T> root_;
170 
171   DISALLOW_COPY_AND_ASSIGN(LinkedList);
172 };
173 
174 }  // namespace base
175 
176 #endif  // BASE_CONTAINERS_LINKED_LIST_H_
177