third_party/blink/renderer/platform/wtf/hash_set.h - chromium/src - Git at Google

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
  *
  * 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_HASH_SET_H_
 #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_SET_H_

 #include <initializer_list>
 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
 #include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h"
 #include "third_party/blink/renderer/platform/wtf/hash_table.h"
 #include "third_party/blink/renderer/platform/wtf/wtf_size_t.h"

 namespace WTF {

 struct IdentityExtractor;

 // Note: empty or deleted values are not allowed, using them may lead to
 // undefined behavior. For pointer keys this means that null pointers are not
 // allowed; for integer keys 0 or -1 can't be used as a key. This restriction
 // can be lifted if you supply custom key traits.
 template <typename ValueArg,
           typename HashArg = typename DefaultHash<ValueArg>::Hash,
           typename TraitsArg = HashTraits<ValueArg>,
           typename Allocator = PartitionAllocator>
 class HashSet {
   USE_ALLOCATOR(HashSet, Allocator);

  private:
   typedef HashArg HashFunctions;
   typedef TraitsArg ValueTraits;
   typedef typename ValueTraits::PeekInType ValuePeekInType;

  public:
   typedef typename ValueTraits::TraitType ValueType;
   using value_type = ValueType;

  private:
   typedef HashTable<ValueType,
                     ValueType,
                     IdentityExtractor,
                     HashFunctions,
                     ValueTraits,
                     ValueTraits,
                     Allocator>
       HashTableType;

  public:
   typedef HashTableConstIteratorAdapter<HashTableType, ValueTraits> iterator;
   typedef HashTableConstIteratorAdapter<HashTableType, ValueTraits>
       const_iterator;
   typedef typename HashTableType::AddResult AddResult;

   HashSet() {
     static_assert(Allocator::kIsGarbageCollected ||
                       !IsPointerToGarbageCollectedType<ValueArg>::value,
                   "Cannot put raw pointers to garbage-collected classes into "
                   "an off-heap HashSet. Use HeapHashSet<Member<T>> instead.");
   }
   HashSet(const HashSet&) = default;
   HashSet& operator=(const HashSet&) = default;
   HashSet(HashSet&&) = default;
   HashSet& operator=(HashSet&&) = default;

   HashSet(std::initializer_list<ValueType> elements);
   HashSet& operator=(std::initializer_list<ValueType> elements);

   void swap(HashSet& ref) { impl_.swap(ref.impl_); }

   unsigned size() const;
   unsigned Capacity() const;
   bool IsEmpty() const;

   void ReserveCapacityForSize(unsigned size) {
     impl_.ReserveCapacityForSize(size);
   }

   iterator begin() const;
   iterator end() const;

   // Returns an iterator to the found element, or end() if not found.
   iterator find(ValuePeekInType) const;
   bool Contains(ValuePeekInType) const;

   // An alternate version of find() that finds the object by hashing and
   // comparing with some other type, to avoid the cost of type
   // conversion. HashTranslator must have the following function members:
   //   static unsigned hash(const T&);
   //   static bool equal(const ValueType&, const T&);
   template <typename HashTranslator, typename T>
   iterator Find(const T&) const;
   template <typename HashTranslator, typename T>
   bool Contains(const T&) const;

   // The return value is a pair of an iterator to the new value's location,
   // and a bool that is true if an new entry was added.
   template <typename IncomingValueType>
   AddResult insert(IncomingValueType&&);

   // An alternate version of add() that finds the object by hashing and
   // comparing with some other type, to avoid the cost of type conversion if
   // the object is already in the table. HashTranslator must have the
   // following function members:
   //   static unsigned hash(const T&);
   //   static bool equal(const ValueType&, const T&);
   //   static translate(ValueType&, T&&, unsigned hashCode);
   template <typename HashTranslator, typename T>
   AddResult AddWithTranslator(T&&);

   // Does nothing if the value is not found.
   void erase(ValuePeekInType);
   void erase(iterator);
   void clear();
   template <typename Collection>
   void RemoveAll(const Collection& to_be_removed) {
     WTF::RemoveAll(*this, to_be_removed);
   }

   ValueType Take(iterator);
   ValueType Take(ValuePeekInType);
   ValueType TakeAny();

   template <typename VisitorDispatcher, typename A = Allocator>
   std::enable_if_t<A::kIsGarbageCollected> Trace(
       VisitorDispatcher visitor) const {
     impl_.Trace(visitor);
   }

  protected:
   ValueType** GetBufferSlot() { return impl_.GetBufferSlot(); }

  private:
   HashTableType impl_;
 };

 struct IdentityExtractor {
   STATIC_ONLY(IdentityExtractor);
   template <typename T>
   static const T& Extract(const T& t) {
     return t;
   }
   // Assumes out points to a buffer of size at least sizeof(T).
   template <typename T>
   static void ExtractSafe(const T& t, void* out) {
     AtomicReadMemcpy<sizeof(T)>(out, &t);
   }
 };

 template <typename Translator>
 struct HashSetTranslatorAdapter {
   STATIC_ONLY(HashSetTranslatorAdapter);
   template <typename T>
   static unsigned GetHash(const T& key) {
     return Translator::GetHash(key);
   }
   template <typename T, typename U>
   static bool Equal(const T& a, const U& b) {
     return Translator::Equal(a, b);
   }
   template <typename T, typename U, typename V>
   static void Translate(T& location, U&& key, const V&, unsigned hash_code) {
     Translator::Translate(location, std::forward<U>(key), hash_code);
   }
 };

 template <typename Value,
           typename HashFunctions,
           typename Traits,
           typename Allocator>
 HashSet<Value, HashFunctions, Traits, Allocator>::HashSet(
     std::initializer_list<ValueType> elements) {
   if (elements.size())
     impl_.ReserveCapacityForSize(SafeCast<wtf_size_t>(elements.size()));
   for (const ValueType& element : elements)
     insert(element);
 }

 template <typename Value,
           typename HashFunctions,
           typename Traits,
           typename Allocator>
 auto HashSet<Value, HashFunctions, Traits, Allocator>::operator=(
     std::initializer_list<ValueType> elements) -> HashSet& {
   *this = HashSet(std::move(elements));
   return *this;
 }

 template <typename T, typename U, typename V, typename W>
 inline unsigned HashSet<T, U, V, W>::size() const {
   return impl_.size();
 }

 template <typename T, typename U, typename V, typename W>
 inline unsigned HashSet<T, U, V, W>::Capacity() const {
   return impl_.Capacity();
 }

 template <typename T, typename U, typename V, typename W>
 inline bool HashSet<T, U, V, W>::IsEmpty() const {
   return impl_.IsEmpty();
 }

 template <typename T, typename U, typename V, typename W>
 inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::begin()
     const {
   return impl_.begin();
 }

 template <typename T, typename U, typename V, typename W>
 inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::end() const {
   return impl_.end();
 }

 template <typename T, typename U, typename V, typename W>
 inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::find(
     ValuePeekInType value) const {
   return impl_.find(value);
 }

 template <typename Value,
           typename HashFunctions,
           typename Traits,
           typename Allocator>
 inline bool HashSet<Value, HashFunctions, Traits, Allocator>::Contains(
     ValuePeekInType value) const {
   return impl_.Contains(value);
 }

 template <typename Value,
           typename HashFunctions,
           typename Traits,
           typename Allocator>
 template <typename HashTranslator, typename T>
 typename HashSet<Value, HashFunctions, Traits, Allocator>::
     iterator inline HashSet<Value, HashFunctions, Traits, Allocator>::Find(
         const T& value) const {
   return impl_.template Find<HashSetTranslatorAdapter<HashTranslator>>(value);
 }

 template <typename Value,
           typename HashFunctions,
           typename Traits,
           typename Allocator>
 template <typename HashTranslator, typename T>
 inline bool HashSet<Value, HashFunctions, Traits, Allocator>::Contains(
     const T& value) const {
   return impl_.template Contains<HashSetTranslatorAdapter<HashTranslator>>(
       value);
 }

 template <typename T, typename U, typename V, typename W>
 template <typename IncomingValueType>
 inline typename HashSet<T, U, V, W>::AddResult HashSet<T, U, V, W>::insert(
     IncomingValueType&& value) {
   return impl_.insert(std::forward<IncomingValueType>(value));
 }

 template <typename Value,
           typename HashFunctions,
           typename Traits,
           typename Allocator>
 template <typename HashTranslator, typename T>
 inline typename HashSet<Value, HashFunctions, Traits, Allocator>::AddResult
 HashSet<Value, HashFunctions, Traits, Allocator>::AddWithTranslator(T&& value) {
   // Forward only the first argument, because the second argument isn't actually
   // used in HashSetTranslatorAdapter.
   return impl_
       .template InsertPassingHashCode<HashSetTranslatorAdapter<HashTranslator>>(
           std::forward<T>(value), value);
 }

 template <typename T, typename U, typename V, typename W>
 inline void HashSet<T, U, V, W>::erase(iterator it) {
   impl_.erase(it.impl_);
 }

 template <typename T, typename U, typename V, typename W>
 inline void HashSet<T, U, V, W>::erase(ValuePeekInType value) {
   erase(find(value));
 }

 template <typename T, typename U, typename V, typename W>
 inline void HashSet<T, U, V, W>::clear() {
   impl_.clear();
 }

 template <typename T, typename U, typename V, typename W>
 inline auto HashSet<T, U, V, W>::Take(iterator it) -> ValueType {
   if (it == end())
     return ValueTraits::EmptyValue();

   ValueType result = std::move(const_cast<ValueType&>(*it));
   erase(it);

   return result;
 }

 template <typename T, typename U, typename V, typename W>
 inline auto HashSet<T, U, V, W>::Take(ValuePeekInType value) -> ValueType {
   return Take(find(value));
 }

 template <typename T, typename U, typename V, typename W>
 inline auto HashSet<T, U, V, W>::TakeAny() -> ValueType {
   return Take(begin());
 }

 template <typename C, typename W>
 inline void CopyToVector(const C& collection, W& vector) {
   typedef typename C::const_iterator iterator;

   {
     // Disallow GC across resize allocation, see crbug.com/568173
     typename W::GCForbiddenScope scope;
     vector.resize(collection.size());
   }

   iterator it = collection.begin();
   iterator end = collection.end();
   for (unsigned i = 0; it != end; ++it, ++i)
     vector[i] = *it;
 }

 }  // namespace WTF

 using WTF::HashSet;

 #endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_SET_H_
	/*
	* Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
	*
	* 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_HASH_SET_H_
	#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_SET_H_

	#include <initializer_list>
	#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
	#include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h"
	#include "third_party/blink/renderer/platform/wtf/hash_table.h"
	#include "third_party/blink/renderer/platform/wtf/wtf_size_t.h"

	namespace WTF {

	struct IdentityExtractor;

	// Note: empty or deleted values are not allowed, using them may lead to
	// undefined behavior. For pointer keys this means that null pointers are not
	// allowed; for integer keys 0 or -1 can't be used as a key. This restriction
	// can be lifted if you supply custom key traits.
	template <typename ValueArg,
	typename HashArg = typename DefaultHash<ValueArg>::Hash,
	typename TraitsArg = HashTraits<ValueArg>,
	typename Allocator = PartitionAllocator>
	class HashSet {
	USE_ALLOCATOR(HashSet, Allocator);

	private:
	typedef HashArg HashFunctions;
	typedef TraitsArg ValueTraits;
	typedef typename ValueTraits::PeekInType ValuePeekInType;

	public:
	typedef typename ValueTraits::TraitType ValueType;
	using value_type = ValueType;

	private:
	typedef HashTable<ValueType,
	ValueType,
	IdentityExtractor,
	HashFunctions,
	ValueTraits,
	ValueTraits,
	Allocator>
	HashTableType;

	public:
	typedef HashTableConstIteratorAdapter<HashTableType, ValueTraits> iterator;
	typedef HashTableConstIteratorAdapter<HashTableType, ValueTraits>
	const_iterator;
	typedef typename HashTableType::AddResult AddResult;

	HashSet() {
	static_assert(Allocator::kIsGarbageCollected \|\|
	!IsPointerToGarbageCollectedType<ValueArg>::value,
	"Cannot put raw pointers to garbage-collected classes into "
	"an off-heap HashSet. Use HeapHashSet<Member<T>> instead.");
	}
	HashSet(const HashSet&) = default;
	HashSet& operator=(const HashSet&) = default;
	HashSet(HashSet&&) = default;
	HashSet& operator=(HashSet&&) = default;

	HashSet(std::initializer_list<ValueType> elements);
	HashSet& operator=(std::initializer_list<ValueType> elements);

	void swap(HashSet& ref) { impl_.swap(ref.impl_); }

	unsigned size() const;
	unsigned Capacity() const;
	bool IsEmpty() const;

	void ReserveCapacityForSize(unsigned size) {
	impl_.ReserveCapacityForSize(size);
	}

	iterator begin() const;
	iterator end() const;

	// Returns an iterator to the found element, or end() if not found.
	iterator find(ValuePeekInType) const;
	bool Contains(ValuePeekInType) const;

	// An alternate version of find() that finds the object by hashing and
	// comparing with some other type, to avoid the cost of type
	// conversion. HashTranslator must have the following function members:
	// static unsigned hash(const T&);
	// static bool equal(const ValueType&, const T&);
	template <typename HashTranslator, typename T>
	iterator Find(const T&) const;
	template <typename HashTranslator, typename T>
	bool Contains(const T&) const;

	// The return value is a pair of an iterator to the new value's location,
	// and a bool that is true if an new entry was added.
	template <typename IncomingValueType>
	AddResult insert(IncomingValueType&&);

	// An alternate version of add() that finds the object by hashing and
	// comparing with some other type, to avoid the cost of type conversion if
	// the object is already in the table. HashTranslator must have the
	// following function members:
	// static unsigned hash(const T&);
	// static bool equal(const ValueType&, const T&);
	// static translate(ValueType&, T&&, unsigned hashCode);
	template <typename HashTranslator, typename T>
	AddResult AddWithTranslator(T&&);

	// Does nothing if the value is not found.
	void erase(ValuePeekInType);
	void erase(iterator);
	void clear();
	template <typename Collection>
	void RemoveAll(const Collection& to_be_removed) {
	WTF::RemoveAll(*this, to_be_removed);
	}

	ValueType Take(iterator);
	ValueType Take(ValuePeekInType);
	ValueType TakeAny();

	template <typename VisitorDispatcher, typename A = Allocator>
	std::enable_if_t<A::kIsGarbageCollected> Trace(
	VisitorDispatcher visitor) const {
	impl_.Trace(visitor);
	}

	protected:
	ValueType** GetBufferSlot() { return impl_.GetBufferSlot(); }

	private:
	HashTableType impl_;
	};

	struct IdentityExtractor {
	STATIC_ONLY(IdentityExtractor);
	template <typename T>
	static const T& Extract(const T& t) {
	return t;
	}
	// Assumes out points to a buffer of size at least sizeof(T).
	template <typename T>
	static void ExtractSafe(const T& t, void* out) {
	AtomicReadMemcpy<sizeof(T)>(out, &t);
	}
	};

	template <typename Translator>
	struct HashSetTranslatorAdapter {
	STATIC_ONLY(HashSetTranslatorAdapter);
	template <typename T>
	static unsigned GetHash(const T& key) {
	return Translator::GetHash(key);
	}
	template <typename T, typename U>
	static bool Equal(const T& a, const U& b) {
	return Translator::Equal(a, b);
	}
	template <typename T, typename U, typename V>
	static void Translate(T& location, U&& key, const V&, unsigned hash_code) {
	Translator::Translate(location, std::forward<U>(key), hash_code);
	}
	};

	template <typename Value,
	typename HashFunctions,
	typename Traits,
	typename Allocator>
	HashSet<Value, HashFunctions, Traits, Allocator>::HashSet(
	std::initializer_list<ValueType> elements) {
	if (elements.size())
	impl_.ReserveCapacityForSize(SafeCast<wtf_size_t>(elements.size()));
	for (const ValueType& element : elements)
	insert(element);
	}

	template <typename Value,
	typename HashFunctions,
	typename Traits,
	typename Allocator>
	auto HashSet<Value, HashFunctions, Traits, Allocator>::operator=(
	std::initializer_list<ValueType> elements) -> HashSet& {
	*this = HashSet(std::move(elements));
	return *this;
	}

	template <typename T, typename U, typename V, typename W>
	inline unsigned HashSet<T, U, V, W>::size() const {
	return impl_.size();
	}

	template <typename T, typename U, typename V, typename W>
	inline unsigned HashSet<T, U, V, W>::Capacity() const {
	return impl_.Capacity();
	}

	template <typename T, typename U, typename V, typename W>
	inline bool HashSet<T, U, V, W>::IsEmpty() const {
	return impl_.IsEmpty();
	}

	template <typename T, typename U, typename V, typename W>
	inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::begin()
	const {
	return impl_.begin();
	}

	template <typename T, typename U, typename V, typename W>
	inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::end() const {
	return impl_.end();
	}

	template <typename T, typename U, typename V, typename W>
	inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::find(
	ValuePeekInType value) const {
	return impl_.find(value);
	}

	template <typename Value,
	typename HashFunctions,
	typename Traits,
	typename Allocator>
	inline bool HashSet<Value, HashFunctions, Traits, Allocator>::Contains(
	ValuePeekInType value) const {
	return impl_.Contains(value);
	}

	template <typename Value,
	typename HashFunctions,
	typename Traits,
	typename Allocator>
	template <typename HashTranslator, typename T>
	typename HashSet<Value, HashFunctions, Traits, Allocator>::
	iterator inline HashSet<Value, HashFunctions, Traits, Allocator>::Find(
	const T& value) const {
	return impl_.template Find<HashSetTranslatorAdapter<HashTranslator>>(value);
	}

	template <typename Value,
	typename HashFunctions,
	typename Traits,
	typename Allocator>
	template <typename HashTranslator, typename T>
	inline bool HashSet<Value, HashFunctions, Traits, Allocator>::Contains(
	const T& value) const {
	return impl_.template Contains<HashSetTranslatorAdapter<HashTranslator>>(
	value);
	}

	template <typename T, typename U, typename V, typename W>
	template <typename IncomingValueType>
	inline typename HashSet<T, U, V, W>::AddResult HashSet<T, U, V, W>::insert(
	IncomingValueType&& value) {
	return impl_.insert(std::forward<IncomingValueType>(value));
	}

	template <typename Value,
	typename HashFunctions,
	typename Traits,
	typename Allocator>
	template <typename HashTranslator, typename T>
	inline typename HashSet<Value, HashFunctions, Traits, Allocator>::AddResult
	HashSet<Value, HashFunctions, Traits, Allocator>::AddWithTranslator(T&& value) {
	// Forward only the first argument, because the second argument isn't actually
	// used in HashSetTranslatorAdapter.
	return impl_
	.template InsertPassingHashCode<HashSetTranslatorAdapter<HashTranslator>>(
	std::forward<T>(value), value);
	}

	template <typename T, typename U, typename V, typename W>
	inline void HashSet<T, U, V, W>::erase(iterator it) {
	impl_.erase(it.impl_);
	}

	template <typename T, typename U, typename V, typename W>
	inline void HashSet<T, U, V, W>::erase(ValuePeekInType value) {
	erase(find(value));
	}

	template <typename T, typename U, typename V, typename W>
	inline void HashSet<T, U, V, W>::clear() {
	impl_.clear();
	}

	template <typename T, typename U, typename V, typename W>
	inline auto HashSet<T, U, V, W>::Take(iterator it) -> ValueType {
	if (it == end())
	return ValueTraits::EmptyValue();

	ValueType result = std::move(const_cast<ValueType&>(*it));
	erase(it);

	return result;
	}

	template <typename T, typename U, typename V, typename W>
	inline auto HashSet<T, U, V, W>::Take(ValuePeekInType value) -> ValueType {
	return Take(find(value));
	}

	template <typename T, typename U, typename V, typename W>
	inline auto HashSet<T, U, V, W>::TakeAny() -> ValueType {
	return Take(begin());
	}

	template <typename C, typename W>
	inline void CopyToVector(const C& collection, W& vector) {
	typedef typename C::const_iterator iterator;

	{
	// Disallow GC across resize allocation, see crbug.com/568173
	typename W::GCForbiddenScope scope;
	vector.resize(collection.size());
	}

	iterator it = collection.begin();
	iterator end = collection.end();
	for (unsigned i = 0; it != end; ++it, ++i)
	vector[i] = *it;
	}

	} // namespace WTF

	using WTF::HashSet;

	#endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_SET_H_