OLD | NEW |
(Empty) | |
| 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. |
| 9 // |
| 10 // To use, start by declaring the class which will be contained in the linked |
| 11 // list, as extending LinkNode (this gives it next/previous pointers). |
| 12 // |
| 13 // class MyNodeType : public LinkNode<MyNodeType> { |
| 14 // ... |
| 15 // }; |
| 16 // |
| 17 // Next, to keep track of the list's head/tail, use a LinkedList instance: |
| 18 // |
| 19 // LinkedList<MyNodeType> list; |
| 20 // |
| 21 // To add elements to the list, use any of LinkedList::Append, |
| 22 // LinkNode::InsertBefore, or LinkNode::InsertAfter: |
| 23 // |
| 24 // LinkNode<MyNodeType>* n1 = ...; |
| 25 // LinkNode<MyNodeType>* n2 = ...; |
| 26 // LinkNode<MyNodeType>* n3 = ...; |
| 27 // |
| 28 // list.Append(n1); |
| 29 // list.Append(n3); |
| 30 // n3->InsertBefore(n3); |
| 31 // |
| 32 // Lastly, to iterate through the linked list forwards: |
| 33 // |
| 34 // for (LinkNode<MyNodeType>* node = list.head(); |
| 35 // node != list.end(); |
| 36 // node = node->next()) { |
| 37 // MyNodeType* value = node->value(); |
| 38 // ... |
| 39 // } |
| 40 // |
| 41 // Or to iterate the linked list backwards: |
| 42 // |
| 43 // for (LinkNode<MyNodeType>* node = list.tail(); |
| 44 // node != list.end(); |
| 45 // node = node->previous()) { |
| 46 // MyNodeType* value = node->value(); |
| 47 // ... |
| 48 // } |
| 49 // |
| 50 |
| 51 namespace base { |
| 52 |
| 53 template <typename T> |
| 54 class LinkNode { |
| 55 public: |
| 56 LinkNode() : previous_(0), next_(0) {} |
| 57 LinkNode(LinkNode<T>* previous, LinkNode<T>* next) |
| 58 : previous_(previous), next_(next) {} |
| 59 |
| 60 // Insert |this| into the linked list, before |e|. |
| 61 void InsertBefore(LinkNode<T>* e) { |
| 62 this->next_ = e; |
| 63 this->previous_ = e->previous_; |
| 64 e->previous_->next_ = this; |
| 65 e->previous_ = this; |
| 66 } |
| 67 |
| 68 // Insert |this| into the linked list, after |e|. |
| 69 void InsertAfter(LinkNode<T>* e) { |
| 70 this->next_ = e->next_; |
| 71 this->previous_ = e; |
| 72 e->next_->previous_ = this; |
| 73 e->next_ = this; |
| 74 } |
| 75 |
| 76 // Remove |this| from the linked list. |
| 77 void RemoveFromList() { |
| 78 this->previous_->next_ = this->next_; |
| 79 this->next_->previous_ = this->previous_; |
| 80 } |
| 81 |
| 82 LinkNode<T>* previous() const { |
| 83 return previous_; |
| 84 } |
| 85 |
| 86 LinkNode<T>* next() const { |
| 87 return next_; |
| 88 } |
| 89 |
| 90 // Cast from the node-type to the value type. |
| 91 const T* value() const { |
| 92 return reinterpret_cast<const T*>(this); |
| 93 } |
| 94 |
| 95 T* value() { |
| 96 return reinterpret_cast<T*>(this); |
| 97 } |
| 98 |
| 99 private: |
| 100 LinkNode<T>* previous_; |
| 101 LinkNode<T>* next_; |
| 102 }; |
| 103 |
| 104 template <typename T> |
| 105 class LinkedList { |
| 106 public: |
| 107 // The "root" node is self-referential, and forms the basis of a circular |
| 108 // list (root_.next() will point back to the start of the list, |
| 109 // and root_->previous() wraps around to the end of the list). |
| 110 LinkedList() : root_(&root_, &root_) {} |
| 111 |
| 112 // Appends |e| to the end of the linked list. |
| 113 void Append(LinkNode<T>* e) { |
| 114 e->InsertBefore(&root_); |
| 115 } |
| 116 |
| 117 LinkNode<T>* head() const { |
| 118 return root_.next(); |
| 119 } |
| 120 |
| 121 LinkNode<T>* tail() const { |
| 122 return root_.previous(); |
| 123 } |
| 124 |
| 125 const LinkNode<T>* end() const { |
| 126 return &root_; |
| 127 } |
| 128 |
| 129 private: |
| 130 LinkNode<T> root_; |
| 131 }; |
| 132 |
| 133 } // namespace base |
| 134 |
| 135 #endif // BASE_LINKED_LIST_H_ |
OLD | NEW |