chromium/third_party/dawn/src/dawn/common/LinkedList.h

// 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.

// This file is a copy of Chromium's /src/base/containers/linked_list.h with the following
// modifications:
//   - Added iterators for ranged based iterations
//   - Added in list check before removing node to prevent segfault, now returns true iff removed
//   - Added MoveInto functionality for moving list elements to another list

#ifndef SRC_DAWN_COMMON_LINKEDLIST_H_
#define SRC_DAWN_COMMON_LINKEDLIST_H_

#include "dawn/common/Assert.h"
#include "partition_alloc/pointers/raw_ptr_exclusion.h"

namespace dawn {

// 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);
//   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();
//     ...
//   }
//
//   for (LinkNode<MyNodeType*> node : list) {
//     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:
//
// 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<T> to std::list<T*>:
//
//    * Erasing an element of type T* from base::LinkedList<T> is
//      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).
//
//    * Insertion operations with base::LinkedList<T> 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<T>, the type being inserted already reserves
//    space for the "next" and "previous" pointers (base::LinkNode<T>*).
//    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.

// Forward declarations of the types in order for recursive referencing and friending.
template <typename T>
class LinkNode;
template <typename T>
class LinkedList;

template <typename T>
class LinkNode { … };

template <typename T>
class LinkedList { … };

template <typename T>
class LinkedListIterator { … };

template <typename T>
LinkedListIterator<T> begin(LinkedList<T>& l) { … }

// Free end function does't use LinkedList<T>::end because of it's const nature. Instead we wrap
// around from tail.
template <typename T>
LinkedListIterator<T> end(LinkedList<T>& l) { … }

}  // namespace dawn

#endif  // SRC_DAWN_COMMON_LINKEDLIST_H_