// 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_CONTAINERS_LINKED_LIST_H_ #define BASE_CONTAINERS_LINKED_LIST_H_ #include "base/base_export.h" #include "base/memory/raw_ptr_exclusion.h" // 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 { // ... // }; // // Next, to keep track of the list's head/tail, use a LinkedList instance: // // LinkedList list; // // To add elements to the list, use any of LinkedList::Append, // LinkNode::InsertBefore, or LinkNode::InsertAfter: // // LinkNode* n1 = ...; // LinkNode* n2 = ...; // LinkNode* n3 = ...; // // list.Append(n1); // list.Append(n3); // n2->InsertBefore(n3); // // Lastly, to iterate through the linked list forwards: // // for (LinkNode* node = list.head(); // node != list.end(); // node = node->next()) { // MyNodeType* value = node->value(); // ... // } // // Or to iterate the linked list backwards: // // for (LinkNode* node = list.tail(); // node != list.end(); // node = node->previous()) { // MyNodeType* value = node->value(); // ... // } // // Questions and Answers: // // Q. Should I use std::list or base::LinkedList? // // A. The main reason to use base::LinkedList over std::list is // performance. If you don't care about the performance differences // then use an STL container, as it makes for better code readability. // // Comparing the performance of base::LinkedList to std::list: // // * Erasing an element of type T* from base::LinkedList is // an O(1) operation. Whereas for std::list it is O(n). // That is because with std::list you must obtain an // iterator to the T* element before you can call erase(iterator). // // * Insertion operations with base::LinkedList never require // heap allocations. // // Q. How does base::LinkedList implementation differ from std::list? // // A. Doubly-linked lists are made up of nodes that contain "next" and // "previous" pointers that reference other nodes in the list. // // With base::LinkedList, the type being inserted already reserves // space for the "next" and "previous" pointers (base::LinkNode*). // Whereas with std::list the type can be anything, so the implementation // needs to glue on the "next" and "previous" pointers using // some internal node type. namespace base { namespace internal { // Base class for LinkNode type class BASE_EXPORT LinkNodeBase { public: void RemoveFromList(); protected: LinkNodeBase(); LinkNodeBase(LinkNodeBase* previous, LinkNodeBase* next); LinkNodeBase(LinkNodeBase&& rhs); LinkNodeBase(const LinkNodeBase&) = delete; ~LinkNodeBase() = default; LinkNodeBase& operator=(const LinkNodeBase&) = delete; // Calling these with |e| as a different LinkNode type as |this| is // unsafe. These are protected and only called from LinkNode to // ensure safety. void InsertBeforeBase(LinkNodeBase* e); void InsertAfterBase(LinkNodeBase* e); LinkNodeBase* previous_base() const { return previous_; } LinkNodeBase* next_base() const { return next_; } private: // `previous_` and `next_` are not a raw_ptr<...> for performance reasons: // on-stack pointer + a large number of non-PA pointees through WeakLinkNode + // based on analysis of sampling profiler data and tab_search:top100:2020. RAW_PTR_EXCLUSION LinkNodeBase* previous_ = nullptr; RAW_PTR_EXCLUSION LinkNodeBase* next_ = nullptr; }; } // namespace internal template class LinkNode : public internal::LinkNodeBase { public: LinkNode() = default; LinkNode(LinkNode* previous, LinkNode* next) : internal::LinkNodeBase(previous, next) {} LinkNode(LinkNode&&) = default; LinkNode(const LinkNode&) = delete; LinkNode& operator=(const LinkNode&) = delete; // Insert |this| into the linked list, before |e|. |this| must not // already be in a list. void InsertBefore(LinkNode* e) { InsertBeforeBase(e); } // Insert |this| into the linked list, after |e|. |this| must not // already be in a list. void InsertAfter(LinkNode* e) { InsertAfterBase(e); } LinkNode* previous() const { return static_cast*>(previous_base()); } LinkNode* next() const { return static_cast*>(next_base()); } // Cast from the node-type to the value type. const T* value() const { return static_cast(this); } T* value() { return static_cast(this); } }; template 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_) {} LinkedList(const LinkedList&) = delete; LinkedList& operator=(const LinkedList&) = delete; // Appends |e| to the end of the linked list. void Append(LinkNode* e) { e->InsertBefore(&root_); } LinkNode* head() const { return root_.next(); } LinkNode* tail() const { return root_.previous(); } const LinkNode* end() const { return &root_; } bool empty() const { return head() == end(); } private: LinkNode root_; }; } // namespace base #endif // BASE_CONTAINERS_LINKED_LIST_H_