chromium/third_party/blink/renderer/platform/wtf/linked_hash_set.h

/*
 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights
 * reserved.
 * Copyright (C) 2011, Benjamin Poulain <[email protected]>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 */

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LINKED_HASH_SET_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LINKED_HASH_SET_H_

#include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h"
#include "third_party/blink/renderer/platform/wtf/hash_map.h"
#include "third_party/blink/renderer/platform/wtf/hash_set.h"
#include "third_party/blink/renderer/platform/wtf/sanitizers.h"
#include "third_party/blink/renderer/platform/wtf/type_traits.h"
#include "third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h"

namespace WTF {

// LinkedHashSet provides a Set interface like HashSet, but also has a
// predictable iteration order. It has O(1) insertion, removal, and test for
// containership. It 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.
//
// This container supports WeakMember<T>.
//
// LinkedHashSet 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).
//
// Note: empty/deleted values as defined in HashTraits are not allowed.
template <typename ValueArg,
          typename TraitsArg = HashTraits<ValueArg>,
          typename Allocator = PartitionAllocator>
class LinkedHashSet { … };

template <typename T, typename TraitsArg, typename Allocator>
inline void LinkedHashSet<T, TraitsArg, Allocator>::Swap(LinkedHashSet& other) { … }

template <typename T, typename TraitsArg, typename Allocator>
typename LinkedHashSet<T, TraitsArg, Allocator>::iterator
LinkedHashSet<T, TraitsArg, Allocator>::find(ValuePeekInType value) { … }

template <typename T, typename TraitsArg, typename Allocator>
typename LinkedHashSet<T, TraitsArg, Allocator>::const_iterator
LinkedHashSet<T, TraitsArg, Allocator>::find(ValuePeekInType value) const { … }

template <typename T, typename TraitsArg, typename Allocator>
bool LinkedHashSet<T, TraitsArg, Allocator>::Contains(
    ValuePeekInType value) const { … }

template <typename ValueType, typename TraitsArg, typename Allocator>
template <typename HashTranslator, typename T>
inline typename LinkedHashSet<ValueType, TraitsArg, Allocator>::iterator
LinkedHashSet<ValueType, TraitsArg, Allocator>::Find(const T& value) { … }

template <typename ValueType, typename TraitsArg, typename Allocator>
template <typename HashTranslator, typename T>
inline typename LinkedHashSet<ValueType, TraitsArg, Allocator>::const_iterator
LinkedHashSet<ValueType, TraitsArg, Allocator>::Find(const T& value) const { … }

template <typename ValueType, typename TraitsArg, typename Allocator>
template <typename HashTranslator, typename T>
bool LinkedHashSet<ValueType, TraitsArg, Allocator>::Contains(
    const T& value) const { … }

template <typename T, typename TraitsArg, typename Allocator>
template <typename IncomingValueType>
typename LinkedHashSet<T, TraitsArg, Allocator>::AddResult
LinkedHashSet<T, TraitsArg, Allocator>::insert(IncomingValueType&& value) { … }

template <typename T, typename TraitsArg, typename Allocator>
template <typename IncomingValueType>
typename LinkedHashSet<T, TraitsArg, Allocator>::AddResult
LinkedHashSet<T, TraitsArg, Allocator>::InsertBefore(
    ValuePeekInType before_value,
    IncomingValueType&& value) { … }

template <typename T, typename TraitsArg, typename Allocator>
template <typename IncomingValueType>
typename LinkedHashSet<T, TraitsArg, Allocator>::AddResult
LinkedHashSet<T, TraitsArg, Allocator>::InsertBefore(
    const_iterator it,
    IncomingValueType&& value) { … }

template <typename T, typename TraitsArg, typename Allocator>
template <typename IncomingValueType>
typename LinkedHashSet<T, TraitsArg, Allocator>::AddResult
LinkedHashSet<T, TraitsArg, Allocator>::AppendOrMoveToLast(
    IncomingValueType&& value) { … }

template <typename T, typename TraitsArg, typename Allocator>
template <typename IncomingValueType>
typename LinkedHashSet<T, TraitsArg, Allocator>::AddResult
LinkedHashSet<T, TraitsArg, Allocator>::PrependOrMoveToFirst(
    IncomingValueType&& value) { … }

template <typename T, typename TraitsArg, typename Allocator>
void LinkedHashSet<T, TraitsArg, Allocator>::MoveTo(
    const_iterator target,
    const_iterator new_position) { … }

template <typename T, typename TraitsArg, typename Allocator>
inline void LinkedHashSet<T, TraitsArg, Allocator>::erase(
    ValuePeekInType value) { … }

template <typename T, typename TraitsArg, typename Allocator>
inline void LinkedHashSet<T, TraitsArg, Allocator>::erase(const_iterator it) { … }

template <typename T, typename TraitsArg, typename Allocator>
inline void LinkedHashSet<T, TraitsArg, Allocator>::RemoveFirst() { … }

template <typename T, typename TraitsArg, typename Allocator>
inline void LinkedHashSet<T, TraitsArg, Allocator>::pop_back() { … }

template <typename T, typename TraitsArg, typename Allocator>
inline void LinkedHashSet<T, TraitsArg, Allocator>::clear() { … }

template <typename T, typename TraitsArg, typename Allocator>
template <typename IncomingValueType>
typename LinkedHashSet<T, TraitsArg, Allocator>::AddResult
LinkedHashSet<T, TraitsArg, Allocator>::InsertOrMoveBefore(
    const_iterator position,
    IncomingValueType&& value,
    MoveType type) { … }

}  // namespace WTF

LinkedHashSet;

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LINKED_HASH_SET_H_