Index: base/linked_list.h |
=================================================================== |
--- base/linked_list.h (revision 0) |
+++ base/linked_list.h (revision 0) |
@@ -0,0 +1,135 @@ |
+// 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. |
+ |
+#ifndef BASE_LINKED_LIST_H_ |
+#define BASE_LINKED_LIST_H_ |
+ |
+// Simple LinkedList type. |
+// |
+// 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); |
+// n3->InsertBefore(n3); |
+// |
+// 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(); |
+// ... |
+// } |
+// |
+ |
+namespace base { |
+ |
+template <typename T> |
+class LinkNode { |
+ public: |
+ LinkNode() : previous_(0), next_(0) {} |
+ 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| 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; |
+ } |
+ |
+ // Remove |this| from the linked list. |
+ void RemoveFromList() { |
+ this->previous_->next_ = this->next_; |
+ this->next_->previous_ = this->previous_; |
+ } |
+ |
+ 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 reinterpret_cast<const T*>(this); |
+ } |
+ |
+ T* value() { |
+ return reinterpret_cast<T*>(this); |
+ } |
+ |
+ private: |
+ LinkNode<T>* previous_; |
+ LinkNode<T>* next_; |
+}; |
+ |
+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() : root_(&root_, &root_) {} |
+ |
+ // 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_; |
+ } |
+ |
+ private: |
+ LinkNode<T> root_; |
+}; |
+ |
+} // namespace base |
+ |
+#endif // BASE_LINKED_LIST_H_ |
Property changes on: base\linked_list.h |
___________________________________________________________________ |
Added: svn:eol-style |
+ LF |