/* * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights * reserved. * Copyright (C) 2008 David Levin <[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. * */ #ifdef UNSAFE_BUFFERS_BUILD // TODO(crbug.com/351564777): Remove this and convert code to safer constructs. #pragma allow_unsafe_buffers #endif #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_TABLE_H_ #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_TABLE_H_ #include <memory> #include "base/check_op.h" #include "base/dcheck_is_on.h" #include "base/numerics/checked_math.h" #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/assertions.h" #include "third_party/blink/renderer/platform/wtf/atomic_operations.h" #include "third_party/blink/renderer/platform/wtf/construct_traits.h" #include "third_party/blink/renderer/platform/wtf/hash_traits.h" #include "third_party/blink/renderer/platform/wtf/type_traits.h" #if !defined(DUMP_HASHTABLE_STATS) #define DUMP_HASHTABLE_STATS … #endif #if !defined(DUMP_HASHTABLE_STATS_PER_TABLE) #define DUMP_HASHTABLE_STATS_PER_TABLE … #endif #if DUMP_HASHTABLE_STATS #include "third_party/blink/renderer/platform/wtf/threading.h" #endif #if DUMP_HASHTABLE_STATS_PER_TABLE #include <type_traits> #include "third_party/blink/renderer/platform/wtf/DataLog.h" #endif #if DUMP_HASHTABLE_STATS #if DUMP_HASHTABLE_STATS_PER_TABLE #define UPDATE_PROBE_COUNTS … #define UPDATE_ACCESS_COUNTS … #else #define UPDATE_PROBE_COUNTS … #define UPDATE_ACCESS_COUNTS … #endif #else #if DUMP_HASHTABLE_STATS_PER_TABLE #define UPDATE_PROBE_COUNTS … #define UPDATE_ACCESS_COUNTS … #else #define UPDATE_PROBE_COUNTS() … #define UPDATE_ACCESS_COUNTS() … #endif #endif namespace WTF { #if DUMP_HASHTABLE_STATS || DUMP_HASHTABLE_STATS_PER_TABLE struct WTF_EXPORT HashTableStats { HashTableStats() : numAccesses(0), numRehashes(0), numRemoves(0), numReinserts(0), maxCollisions(0), numCollisions(0), collisionGraph() {} // The following variables are all atomically incremented when modified. std::atomic_int numAccesses; std::atomic_int numRehashes; std::atomic_int numRemoves; std::atomic_int numReinserts; // The following variables are only modified in the recordCollisionAtCount // method within a mutex. int maxCollisions; int numCollisions; int collisionGraph[4096]; void copy(const HashTableStats* other); void recordCollisionAtCount(int count); void DumpStats(); static HashTableStats& instance(); template <typename VisitorDispatcher> void trace(VisitorDispatcher) const {} private: void RecordCollisionAtCountWithoutLock(int count); void DumpStatsWithoutLock(); }; #if DUMP_HASHTABLE_STATS_PER_TABLE template <typename Allocator, bool isGCType = Allocator::kIsGarbageCollected> class HashTableStatsPtr; template <typename Allocator> class HashTableStatsPtr<Allocator, false> final { STATIC_ONLY(HashTableStatsPtr); public: static std::unique_ptr<HashTableStats> Create() { return std::make_unique<HashTableStats>(); } static std::unique_ptr<HashTableStats> copy( const std::unique_ptr<HashTableStats>& other) { if (!other) return nullptr; return std::make_unique<HashTableStats>(*other); } static void swap(std::unique_ptr<HashTableStats>& stats, std::unique_ptr<HashTableStats>& other) { stats.swap(other); } }; template <typename Allocator> class HashTableStatsPtr<Allocator, true> final { STATIC_ONLY(HashTableStatsPtr); public: static HashTableStats* Create() { // TODO(cavalcantii): fix this. return new HashTableStats; } static HashTableStats* copy(const HashTableStats* other) { if (!other) return nullptr; HashTableStats* obj = Create(); obj->copy(other); return obj; } static void swap(HashTableStats*& stats, HashTableStats*& other) { std::swap(stats, other); } }; #endif #endif template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> class HashTable; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> class HashTableIterator; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> class HashTableConstIterator; template <WeakHandlingFlag x, typename T, typename U, typename V, typename W, typename X, typename Y> struct WeakProcessingHashTableHelper; HashItemKnownGoodTag; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> class HashTableConstIterator final { … }; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> std::ostream& operator<<(std::ostream& stream, const HashTableConstIterator<Key, Value, Extractor, Traits, KeyTraits, Allocator>& iterator) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> class HashTableIterator final { … }; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> std::ostream& operator<<(std::ostream& stream, const HashTableIterator<Key, Value, Extractor, Traits, KeyTraits, Allocator>& iterator) { … } swap; template <typename T, typename Allocator, typename Traits, bool enterGCForbiddenScope> struct Mover { … }; Mover<T, Allocator, Traits, true>; template <typename KeyTraits> class IdentityHashTranslator { … }; template <typename HashTableType, typename ValueType> struct HashTableAddResult final { … }; template <typename HashTranslator, typename KeyTraits, bool safeToCompareToEmptyOrDeleted> struct HashTableKeyChecker { … }; HashTableKeyChecker<HashTranslator, KeyTraits, true>; // Note: empty or deleted key values are not allowed, using them may lead to // undefined behavior. For pointer keys this means that null pointers are not // allowed unless you supply custom key traits. template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> class HashTable final { … }; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> inline HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::HashTable() : … { … } inline unsigned CalculateCapacity(unsigned size) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::ReserveCapacityForSize(unsigned new_size) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T> inline Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Lookup( const T& key) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T> inline const Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Lookup( const T& key) const { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T> inline typename HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: LookupResult HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: LookupForWriting(const T& key) { … } template <typename Traits, typename Allocator, typename Value, bool = Traits::kEmptyValueIsZero> struct HashTableBucketInitializer { … }; // Specialization when the hash traits for a type have kEmptyValueIsZero = true // which indicate that all zero bytes represent an empty object. HashTableBucketInitializer<Traits, Allocator, Value, true>; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> inline void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: ReinitializeBucket(ValueType& bucket) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T, typename Extra> typename HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: AddResult HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::insert( T&& key, Extra&& extra) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T, typename Extra> typename HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: AddResult HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: InsertPassingHashCode(T&& key, Extra&& extra) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Reinsert( ValueType&& entry) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T> inline typename HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: iterator HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Find( const T& key) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T> inline typename HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: const_iterator HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Find( const T& key) const { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> template <typename HashTranslator, typename T> bool HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Contains( const T& key) const { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::erase( const ValueType* pos) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> inline void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::erase( iterator it) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> inline void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::erase( const_iterator it) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> inline void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::erase( KeyPeekInType key) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::AllocateTable( unsigned size) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>:: DeleteAllBucketsAndDeallocate(ValueType* table, unsigned size) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Expand( Value* entry) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::ExpandBuffer( unsigned new_table_size, Value* entry, bool& success) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::RehashTo( ValueType* new_table, unsigned new_table_size, Value* entry) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> Value* HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Rehash( unsigned new_table_size, Value* entry) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::clear() { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::HashTable( const HashTable& other) : … { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::HashTable( HashTable&& other) : … { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::swap( HashTable& other) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>& HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::operator=( const HashTable& other) { … } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>& HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::operator=( HashTable&& other) { … } template <WeakHandlingFlag weakHandlingFlag, typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> struct WeakProcessingHashTableHelper { … }; WeakProcessingHashTableHelper<kWeakHandling, Key, Value, Extractor, Traits, KeyTraits, Allocator>; template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::Trace( auto visitor) const requires Allocator::kIsGarbageCollected { static_assert(WTF::IsWeak<ValueType>::value || IsTraceable<ValueType>::value, "Value should not be traced"); TraceTable(visitor, AsAtomicPtr(&table_)->load(std::memory_order_relaxed)); } template <typename Key, typename Value, typename Extractor, typename Traits, typename KeyTraits, typename Allocator> void HashTable<Key, Value, Extractor, Traits, KeyTraits, Allocator>::TraceTable( auto visitor, const ValueType* table) const requires Allocator::kIsGarbageCollected { if (!WTF::IsWeak<ValueType>::value) { // Strong HashTable. Allocator::template TraceHashTableBackingStrongly<ValueType, HashTable>( visitor, table, &table_); } else { // Weak HashTable. The HashTable may be held alive strongly from somewhere // else, e.g., an iterator. // Trace the table weakly. For marking this will result in delaying the // processing until the end of the atomic pause. It is safe to trace // weakly multiple times. Allocator::template TraceHashTableBackingWeakly<ValueType, HashTable>( visitor, table, &table_, WeakProcessingHashTableHelper<kWeakHandlingTrait<ValueType>, Key, Value, Extractor, Traits, KeyTraits, Allocator>::Process, this); } } // iterator adapters template <typename HashTableType, typename Traits, typename Enable = void> struct HashTableConstIteratorAdapter { … }; HashTableConstIteratorAdapter<HashTableType, Traits, typename std::enable_if_t<IsTraceable<typename Traits::TraitType>::value>>; template <typename HashTable, typename Traits, typename Enable> std::ostream& operator<<( std::ostream& stream, const HashTableConstIteratorAdapter<HashTable, Traits, Enable>& iterator) { … } template <typename HashTableType, typename Traits, typename Enable = void> struct HashTableIteratorAdapter { … }; HashTableIteratorAdapter<HashTableType, Traits, typename std::enable_if_t<IsTraceable<typename Traits::TraitType>::value>>; template <typename HashTable, typename Traits, typename Enable> std::ostream& operator<<( std::ostream& stream, const HashTableIteratorAdapter<HashTable, Traits, Enable>& iterator) { … } template <typename T, typename U> inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) { … } template <typename T, typename U> inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) { … } template <typename T, typename U> inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) { … } template <typename T, typename U> inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) { … } // All 4 combinations of ==, != and Const,non const. template <typename T, typename U> inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) { … } template <typename T, typename U> inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) { … } template <typename T, typename U> inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) { … } template <typename T, typename U> inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) { … } template <typename Collection1, typename Collection2> inline void RemoveAll(Collection1& collection, const Collection2& to_be_removed) { … } } // namespace WTF #endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_TABLE_H_
Codebase Browser
chromium