linked_list.h revision 116680a4aac90f2aa7413d9095a592090648e557
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2009 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef BASE_CONTAINERS_LINKED_LIST_H_ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BASE_CONTAINERS_LINKED_LIST_H_ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "base/macros.h" 9116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Simple LinkedList type. (See the Q&A section to understand how this 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// differs from std::list). 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// To use, start by declaring the class which will be contained in the linked 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// list, as extending LinkNode (this gives it next/previous pointers). 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// class MyNodeType : public LinkNode<MyNodeType> { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ... 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// }; 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Next, to keep track of the list's head/tail, use a LinkedList instance: 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LinkedList<MyNodeType> list; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// To add elements to the list, use any of LinkedList::Append, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LinkNode::InsertBefore, or LinkNode::InsertAfter: 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LinkNode<MyNodeType>* n1 = ...; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LinkNode<MyNodeType>* n2 = ...; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LinkNode<MyNodeType>* n3 = ...; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// list.Append(n1); 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// list.Append(n3); 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// n3->InsertBefore(n3); 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Lastly, to iterate through the linked list forwards: 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for (LinkNode<MyNodeType>* node = list.head(); 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// node != list.end(); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// node = node->next()) { 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MyNodeType* value = node->value(); 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ... 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// } 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Or to iterate the linked list backwards: 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for (LinkNode<MyNodeType>* node = list.tail(); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// node != list.end(); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// node = node->previous()) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MyNodeType* value = node->value(); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ... 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// } 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Questions and Answers: 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Q. Should I use std::list or base::LinkedList? 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A. The main reason to use base::LinkedList over std::list is 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// performance. If you don't care about the performance differences 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// then use an STL container, as it makes for better code readability. 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Comparing the performance of base::LinkedList<T> to std::list<T*>: 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Erasing an element of type T* from base::LinkedList<T> is 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// an O(1) operation. Whereas for std::list<T*> it is O(n). 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// That is because with std::list<T*> you must obtain an 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// iterator to the T* element before you can call erase(iterator). 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Insertion operations with base::LinkedList<T> never require 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// heap allocations. 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Q. How does base::LinkedList implementation differ from std::list? 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A. Doubly-linked lists are made up of nodes that contain "next" and 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "previous" pointers that reference other nodes in the list. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// With base::LinkedList<T>, the type being inserted already reserves 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// space for the "next" and "previous" pointers (base::LinkNode<T>*). 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Whereas with std::list<T> the type can be anything, so the implementation 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// needs to glue on the "next" and "previous" pointers using 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// some internal node type. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename T> 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LinkNode { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 87116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkNode() : previous_(NULL), next_(NULL) {} 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode(LinkNode<T>* previous, LinkNode<T>* next) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : previous_(previous), next_(next) {} 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert |this| into the linked list, before |e|. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void InsertBefore(LinkNode<T>* e) { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->next_ = e; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->previous_ = e->previous_; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->previous_->next_ = this; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->previous_ = this; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert |this| into the linked list, after |e|. 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void InsertAfter(LinkNode<T>* e) { 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->next_ = e->next_; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->previous_ = e; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->next_->previous_ = this; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->next_ = this; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove |this| from the linked list. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void RemoveFromList() { 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->previous_->next_ = this->next_; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->next_->previous_ = this->previous_; 111116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // next() and previous() return non-NULL if and only this node is not in any 112116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // list. 113116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch this->next_ = NULL; 114116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch this->previous_ = NULL; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T>* previous() const { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return previous_; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T>* next() const { 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return next_; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Cast from the node-type to the value type. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const T* value() const { 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<const T*>(this); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) T* value() { 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<T*>(this); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T>* previous_; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T>* next_; 137116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 138116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LinkNode); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename T> 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LinkedList { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The "root" node is self-referential, and forms the basis of a circular 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // list (root_.next() will point back to the start of the list, 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and root_->previous() wraps around to the end of the list). 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkedList() : root_(&root_, &root_) {} 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Appends |e| to the end of the linked list. 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Append(LinkNode<T>* e) { 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->InsertBefore(&root_); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T>* head() const { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return root_.next(); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T>* tail() const { 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return root_.previous(); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const LinkNode<T>* end() const { 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &root_; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 166116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool empty() const { return head() == end(); } 167116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkNode<T> root_; 170116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 171116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LinkedList); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace base 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // BASE_CONTAINERS_LINKED_LIST_H_ 177