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
81namespace base {
82
83template <typename T>
84class 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
141template <typename T>
142class 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