vector_backed_linked_list.h | Explore in Territory

// Copyright 2020 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_VECTOR_BACKED_LINKED_LIST_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_VECTOR_BACKED_LINKED_LIST_H_

#include <stddef.h>

#include <iterator>

#include "base/check_op.h"
#include "base/dcheck_is_on.h"
#include "base/gtest_prod_util.h"
#include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h"
#include "third_party/blink/renderer/platform/wtf/hash_traits.h"
#include "third_party/blink/renderer/platform/wtf/sanitizers.h"
#include "third_party/blink/renderer/platform/wtf/vector.h"

namespace WTF {

// VectorBackedLinkedList iterators are not invalidated by mutation of the
// collection, unless they point to removed items. This means, for example, that
// you can safely modify the container while iterating over it generally, as
// long as you don't remove the current item. Moving items does not invalidate
// iterator, so that it may cause unexpected behavior (i.e. loop unexpectedly
// ends when moving the current item to last).

template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListIterator;
template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListConstIterator;
template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListReverseIterator;
template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListConstReverseIterator;

template <typename ValueType, typename Allocator>
class VectorBackedLinkedListNode { … };

VectorTraits<VectorBackedLinkedListNode<ValueType, Allocator>>;

ConstructTraits<VectorBackedLinkedListNode<ValueType, Allocator>, Traits, Allocator>;

// VectorBackedLinkedList maintains a linked list through its contents such that
// iterating it yields values in the order in which they were inserted.
// The linked list is implementing in a vector (with links being indexes instead
// of pointers), to simplify the move of backing during GC compaction.
template <typename ValueType, typename Allocator = PartitionAllocator>
class VectorBackedLinkedList { … };

template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListIterator { … };

template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListConstIterator { … };

template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListReverseIterator { … };

template <typename VectorBackedLinkedListType>
class VectorBackedLinkedListConstReverseIterator
    : public VectorBackedLinkedListConstIterator<VectorBackedLinkedListType> { … };

template <typename T, typename Allocator>
VectorBackedLinkedList<T, Allocator>::VectorBackedLinkedList() { … }

template <typename T, typename Allocator>
inline void VectorBackedLinkedList<T, Allocator>::swap(
    VectorBackedLinkedList& other) { … }

template <typename T, typename Allocator>
T& VectorBackedLinkedList<T, Allocator>::front() { … }

template <typename T, typename Allocator>
const T& VectorBackedLinkedList<T, Allocator>::front() const { … }

template <typename T, typename Allocator>
T& VectorBackedLinkedList<T, Allocator>::back() { … }

template <typename T, typename Allocator>
const T& VectorBackedLinkedList<T, Allocator>::back() const { … }

template <typename T, typename Allocator>
template <typename IncomingValueType>
typename VectorBackedLinkedList<T, Allocator>::iterator
VectorBackedLinkedList<T, Allocator>::insert(const_iterator position,
                                             IncomingValueType&& value) { … }

template <typename T, typename Allocator>
typename VectorBackedLinkedList<T, Allocator>::iterator
VectorBackedLinkedList<T, Allocator>::MoveTo(const_iterator target,
                                             const_iterator new_position) { … }

template <typename T, typename Allocator>
typename VectorBackedLinkedList<T, Allocator>::iterator
VectorBackedLinkedList<T, Allocator>::erase(const_iterator position) { … }

template <typename T, typename Allocator>
void VectorBackedLinkedList<T, Allocator>::Unlink(const Node& node) { … }

}  // namespace WTF

VectorBackedLinkedList;

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_VECTOR_BACKED_LINKED_LIST_H_
chromium/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h
