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