base/containers/linked_list.h

   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:
  87   LinkNode() : previous_(NULL), next_(NULL) {}
  88   LinkNode(LinkNode<T>* previous, LinkNode<T>* next)
  89       : previous_(previous), next_(next) {}
  90
  91   // Insert |this| into the linked list, before |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|.
 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.
 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
 117   LinkNode<T>* previous() const {
 118     return previous_;
 119   }
 120
 121   LinkNode<T>* next() const {
 122     return next_;
 123   }
 124
 125   // Cast from the node-type to the value type.
 126   const T* value() const {
 127     return static_cast<const T*>(this);
 128   }
 129
 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).
 147   LinkedList() : root_(&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   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_