linked_list.h 5.33 KB
Newer Older
gejun's avatar
gejun committed
1 2 3 4
// Copyright (c) 2009 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#ifndef BUTIL_CONTAINERS_LINKED_LIST_H_
#define BUTIL_CONTAINERS_LINKED_LIST_H_
gejun's avatar
gejun committed
7

8
#include "butil/macros.h"
gejun's avatar
gejun committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

// Simple LinkedList type. (See the Q&A section to understand how this
// differs from std::list).
//
// To use, start by declaring the class which will be contained in the linked
// list, as extending LinkNode (this gives it next/previous pointers).
//
//   class MyNodeType : public LinkNode<MyNodeType> {
//     ...
//   };
//
// Next, to keep track of the list's head/tail, use a LinkedList instance:
//
//   LinkedList<MyNodeType> list;
//
// To add elements to the list, use any of LinkedList::Append,
// LinkNode::InsertBefore, or LinkNode::InsertAfter:
//
//   LinkNode<MyNodeType>* n1 = ...;
//   LinkNode<MyNodeType>* n2 = ...;
//   LinkNode<MyNodeType>* n3 = ...;
//
//   list.Append(n1);
//   list.Append(n3);
33
//   n2->InsertBefore(n3);
gejun's avatar
gejun committed
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
//
// Lastly, to iterate through the linked list forwards:
//
//   for (LinkNode<MyNodeType>* node = list.head();
//        node != list.end();
//        node = node->next()) {
//     MyNodeType* value = node->value();
//     ...
//   }
//
// Or to iterate the linked list backwards:
//
//   for (LinkNode<MyNodeType>* node = list.tail();
//        node != list.end();
//        node = node->previous()) {
//     MyNodeType* value = node->value();
//     ...
//   }
//
// Questions and Answers:
//
55
// Q. Should I use std::list or butil::LinkedList?
gejun's avatar
gejun committed
56
//
57
// A. The main reason to use butil::LinkedList over std::list is
gejun's avatar
gejun committed
58 59 60
//    performance. If you don't care about the performance differences
//    then use an STL container, as it makes for better code readability.
//
61
//    Comparing the performance of butil::LinkedList<T> to std::list<T*>:
gejun's avatar
gejun committed
62
//
63
//    * Erasing an element of type T* from butil::LinkedList<T> is
gejun's avatar
gejun committed
64 65 66 67
//      an O(1) operation. Whereas for std::list<T*> it is O(n).
//      That is because with std::list<T*> you must obtain an
//      iterator to the T* element before you can call erase(iterator).
//
68
//    * Insertion operations with butil::LinkedList<T> never require
gejun's avatar
gejun committed
69 70
//      heap allocations.
//
71
// Q. How does butil::LinkedList implementation differ from std::list?
gejun's avatar
gejun committed
72 73 74 75
//
// A. Doubly-linked lists are made up of nodes that contain "next" and
//    "previous" pointers that reference other nodes in the list.
//
76 77
//    With butil::LinkedList<T>, the type being inserted already reserves
//    space for the "next" and "previous" pointers (butil::LinkNode<T>*).
gejun's avatar
gejun committed
78 79 80 81
//    Whereas with std::list<T> the type can be anything, so the implementation
//    needs to glue on the "next" and "previous" pointers using
//    some internal node type.

82
namespace butil {
gejun's avatar
gejun committed
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193

template <typename T>
class LinkNode {
 public:
  // LinkNode are self-referential as default.
  LinkNode() : previous_(this), next_(this) {}
    
  LinkNode(LinkNode<T>* previous, LinkNode<T>* next)
      : previous_(previous), next_(next) {}

  // Insert |this| into the linked list, before |e|.
  void InsertBefore(LinkNode<T>* e) {
    this->next_ = e;
    this->previous_ = e->previous_;
    e->previous_->next_ = this;
    e->previous_ = this;
  }

  // Insert |this| as a circular linked list into the linked list, before |e|.
  void InsertBeforeAsList(LinkNode<T>* e) {
    LinkNode<T>* prev = this->previous_;
    prev->next_ = e;
    this->previous_ = e->previous_;
    e->previous_->next_ = this;
    e->previous_ = prev;
  }
    
  // Insert |this| into the linked list, after |e|.
  void InsertAfter(LinkNode<T>* e) {
    this->next_ = e->next_;
    this->previous_ = e;
    e->next_->previous_ = this;
    e->next_ = this;
  }

  // Insert |this| as a circular list into the linked list, after |e|.
  void InsertAfterAsList(LinkNode<T>* e) {
    LinkNode<T>* prev = this->previous_;
    prev->next_ = e->next_;
    this->previous_ = e;
    e->next_->previous_ = prev;
    e->next_ = this;
  }

  // Remove |this| from the linked list.
  void RemoveFromList() {
    this->previous_->next_ = this->next_;
    this->next_->previous_ = this->previous_;
    // next() and previous() return non-NULL if and only this node is not in any
    // list.
    this->next_ = this;
    this->previous_ = this;
  }

  LinkNode<T>* previous() const {
    return previous_;
  }

  LinkNode<T>* next() const {
    return next_;
  }

  // Cast from the node-type to the value type.
  const T* value() const {
    return static_cast<const T*>(this);
  }

  T* value() {
    return static_cast<T*>(this);
  }

 private:
  LinkNode<T>* previous_;
  LinkNode<T>* next_;

  DISALLOW_COPY_AND_ASSIGN(LinkNode);
};

template <typename T>
class LinkedList {
 public:
  // The "root" node is self-referential, and forms the basis of a circular
  // list (root_.next() will point back to the start of the list,
  // and root_->previous() wraps around to the end of the list).
  LinkedList() {}

  // Appends |e| to the end of the linked list.
  void Append(LinkNode<T>* e) {
    e->InsertBefore(&root_);
  }

  LinkNode<T>* head() const {
    return root_.next();
  }

  LinkNode<T>* tail() const {
    return root_.previous();
  }

  const LinkNode<T>* end() const {
    return &root_;
  }

  bool empty() const { return head() == end(); }

 private:
  LinkNode<T> root_;

  DISALLOW_COPY_AND_ASSIGN(LinkedList);
};

194
}  // namespace butil
gejun's avatar
gejun committed
195

196
#endif  // BUTIL_CONTAINERS_LINKED_LIST_H_