diff options
author | The Android Open Source Project <initial-contribution@android.com> | 2008-12-17 18:05:15 -0800 |
---|---|---|
committer | The Android Open Source Project <initial-contribution@android.com> | 2008-12-17 18:05:15 -0800 |
commit | 1cbdecfa9fc428ac2d8aca0fa91c9580b3d57353 (patch) | |
tree | 4457a7306ea5acb43fe05bfe0973b1f7faf97ba2 /JavaScriptCore/wtf/HashTable.h | |
parent | 9364f22aed35e1a1e9d07c121510f80be3ab0502 (diff) | |
download | external_webkit-1cbdecfa9fc428ac2d8aca0fa91c9580b3d57353.zip external_webkit-1cbdecfa9fc428ac2d8aca0fa91c9580b3d57353.tar.gz external_webkit-1cbdecfa9fc428ac2d8aca0fa91c9580b3d57353.tar.bz2 |
Code drop from //branches/cupcake/...@124589
Diffstat (limited to 'JavaScriptCore/wtf/HashTable.h')
-rw-r--r-- | JavaScriptCore/wtf/HashTable.h | 260 |
1 files changed, 75 insertions, 185 deletions
diff --git a/JavaScriptCore/wtf/HashTable.h b/JavaScriptCore/wtf/HashTable.h index 3b87490..4c7790a 100644 --- a/JavaScriptCore/wtf/HashTable.h +++ b/JavaScriptCore/wtf/HashTable.h @@ -1,7 +1,5 @@ -// -*- mode: c++; c-basic-offset: 4 -*- /* - * This file is part of the KDE libraries - * Copyright (C) 2005, 2006 Apple Computer, Inc. + * Copyright (C) 2005, 2006, 2007, 2008 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 @@ -63,25 +61,26 @@ namespace WTF { template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> class HashTableConstIterator; -#if CHECK_HASHTABLE_ITERATORS template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*, HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*); template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*); -#else + +#if !CHECK_HASHTABLE_ITERATORS + template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*, HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { } template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { } + #endif typedef enum { HashItemKnownGood } HashItemKnownGoodTag; - template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> class HashTableConstIterator { private: @@ -325,10 +324,11 @@ namespace WTF { void clear(); static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); } - static bool isDeletedBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::deletedValue(); } + static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); } static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); } ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); } + template<typename T, typename HashTranslator> ValueType* lookup(const T&); #if CHECK_HASHTABLE_CONSISTENCY void checkTableConsistency() const; @@ -343,11 +343,12 @@ namespace WTF { typedef pair<ValueType*, bool> LookupType; typedef pair<LookupType, unsigned> FullLookupType; - template<typename T, typename HashTranslator> ValueType* lookup(const T&); LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); }; template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&); template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&); + template<typename T, typename HashTranslator> void checkKey(const T&); + void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*); void removeAndInvalidate(ValueType*); void remove(ValueType*); @@ -362,7 +363,7 @@ namespace WTF { void reinsert(ValueType&); static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); } - static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); } + static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); } FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash) { return FullLookupType(LookupType(position, found), hash); } @@ -423,24 +424,47 @@ namespace WTF { return key; } +#if ASSERT_DISABLED + template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> template<typename T, typename HashTranslator> - inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) + inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) { - ASSERT(m_table); -#if !ASSERT_DISABLED - if (HashFunctions::safeToCompareToEmptyOrDeleted) { - ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); - ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key)); - } + } + +#else + + template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> + template<typename T, typename HashTranslator> + void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key) + { + if (!HashFunctions::safeToCompareToEmptyOrDeleted) + return; + ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); + ValueType deletedValue = Traits::emptyValue(); + deletedValue.~ValueType(); + Traits::constructDeletedValue(deletedValue); + ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key)); + new (&deletedValue) ValueType(Traits::emptyValue()); + } + #endif + template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> + template<typename T, typename HashTranslator> + inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) + { + checkKey<T, HashTranslator>(key); + int k = 0; int sizeMask = m_tableSizeMask; ValueType* table = m_table; unsigned h = HashTranslator::hash(key); int i = h & sizeMask; + if (!table) + return 0; + #if DUMP_HASHTABLE_STATS ++HashTableStats::numAccesses; int probeCount = 0; @@ -478,12 +502,7 @@ namespace WTF { inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) { ASSERT(m_table); -#if !ASSERT_DISABLED - if (HashFunctions::safeToCompareToEmptyOrDeleted) { - ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); - ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key)); - } -#endif + checkKey<T, HashTranslator>(key); int k = 0; ValueType* table = m_table; @@ -535,12 +554,7 @@ namespace WTF { inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) { ASSERT(m_table); -#if !ASSERT_DISABLED - if (HashFunctions::safeToCompareToEmptyOrDeleted) { - ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); - ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key)); - } -#endif + checkKey<T, HashTranslator>(key); int k = 0; ValueType* table = m_table; @@ -591,12 +605,7 @@ namespace WTF { template<typename T, typename Extra, typename HashTranslator> inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra& extra) { -#if !ASSERT_DISABLED - if (HashFunctions::safeToCompareToEmptyOrDeleted) { - ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); - ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key)); - } -#endif + checkKey<T, HashTranslator>(key); invalidateIterators(); @@ -652,6 +661,7 @@ namespace WTF { } if (deletedEntry) { + initializeBucket(*deletedEntry); entry = deletedEntry; --m_deletedCount; } @@ -661,12 +671,14 @@ namespace WTF { ++m_keyCount; if (shouldExpand()) { - // FIXME: this makes an extra copy on expand. Probably not that bad since + // FIXME: This makes an extra copy on expand. Probably not that bad since // expand is rare, but would be better to have a version of expand that can - // follow a pivot entry and return the new position + // follow a pivot entry and return the new position. KeyType enteredKey = Extractor::extract(*entry); expand(); - return std::make_pair(find(enteredKey), true); + pair<iterator, bool> p = std::make_pair(find(enteredKey), true); + ASSERT(p.first != end()); + return p; } checkTableConsistency(); @@ -678,6 +690,8 @@ namespace WTF { template<typename T, typename Extra, typename HashTranslator> inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(const T& key, const Extra& extra) { + checkKey<T, HashTranslator>(key); + invalidateIterators(); if (!m_table) @@ -687,25 +701,29 @@ namespace WTF { FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key); - ValueType *entry = lookupResult.first.first; + ValueType* entry = lookupResult.first.first; bool found = lookupResult.first.second; unsigned h = lookupResult.second; if (found) return std::make_pair(makeKnownGoodIterator(entry), false); - if (isDeletedBucket(*entry)) + if (isDeletedBucket(*entry)) { + initializeBucket(*entry); --m_deletedCount; + } HashTranslator::translate(*entry, key, extra, h); ++m_keyCount; if (shouldExpand()) { - // FIXME: this makes an extra copy on expand. Probably not that bad since + // FIXME: This makes an extra copy on expand. Probably not that bad since // expand is rare, but would be better to have a version of expand that can - // follow a pivot entry and return the new position + // follow a pivot entry and return the new position. KeyType enteredKey = Extractor::extract(*entry); expand(); - return std::make_pair(find(enteredKey), true); + pair<iterator, bool> p = std::make_pair(find(enteredKey), true); + ASSERT(p.first != end()); + return p; } checkTableConsistency(); @@ -723,7 +741,7 @@ namespace WTF { ++HashTableStats::numReinserts; #endif - Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookupForWriting(Extractor::extract(entry)).first)); + Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first); } template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> @@ -747,7 +765,7 @@ namespace WTF { if (!m_table) return end(); - ValueType* entry = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key); + ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key); if (!entry) return end(); @@ -761,7 +779,7 @@ namespace WTF { if (!m_table) return false; - return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key); + return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key); } template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> @@ -821,12 +839,12 @@ namespace WTF { } template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> - Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) + Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) { // would use a template member function with explicit specializations here, but // gcc doesn't appear to support that if (Traits::emptyValueIsZero) - return static_cast<ValueType *>(fastZeroedMalloc(size * sizeof(ValueType))); + return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType))); ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType))); for (int i = 0; i < size; i++) initializeBucket(result[i]); @@ -834,11 +852,14 @@ namespace WTF { } template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> - void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size) + void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size) { - if (Traits::needsDestruction) - for (int i = 0; i < size; ++i) - table[i].~ValueType(); + if (Traits::needsDestruction) { + for (int i = 0; i < size; ++i) { + if (!isDeletedBucket(table[i])) + table[i].~ValueType(); + } + } fastFree(table); } @@ -862,7 +883,7 @@ namespace WTF { checkTableConsistencyExceptSize(); int oldTableSize = m_tableSize; - ValueType *oldTable = m_table; + ValueType* oldTable = m_table; #if DUMP_HASHTABLE_STATS if (oldTableSize != 0) @@ -919,7 +940,7 @@ namespace WTF { invalidateIterators(); other.invalidateIterators(); - ValueType *tmp_table = m_table; + ValueType* tmp_table = m_table; m_table = other.m_table; other.m_table = tmp_table; @@ -967,7 +988,7 @@ namespace WTF { int count = 0; int deletedCount = 0; for (int j = 0; j < m_tableSize; ++j) { - ValueType *entry = m_table + j; + ValueType* entry = m_table + j; if (isEmptyBucket(*entry)) continue; @@ -1115,137 +1136,6 @@ namespace WTF { return a.m_impl != b.m_impl; } - // reference count manager - - template<typename ValueTraits, typename ValueStorageTraits> struct NeedsRef { - static const bool value = ValueTraits::needsRef && !ValueStorageTraits::needsRef; - }; - template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits> - struct NeedsRef<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> { - typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits; - typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits; - static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value; - static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value; - static const bool value = firstNeedsRef || secondNeedsRef; - }; - - template<bool needsRef, typename ValueTraits, typename ValueStorageTraits> struct RefCounterBase; - - template<typename ValueTraits, typename ValueStorageTraits> - struct RefCounterBase<false, ValueTraits, ValueStorageTraits> { - typedef typename ValueStorageTraits::TraitType ValueStorageType; - static void ref(const ValueStorageType&) { } - static void deref(const ValueStorageType&) { } - }; - - template<typename ValueTraits, typename ValueStorageTraits> - struct RefCounterBase<true, ValueTraits, ValueStorageTraits> { - typedef typename ValueStorageTraits::TraitType ValueStorageType; - static void ref(const ValueStorageType& v) { ValueTraits::ref(v); } - static void deref(const ValueStorageType& v) { ValueTraits::deref(v); } - }; - - template<typename ValueTraits, typename ValueStorageTraits> struct RefCounter { - typedef typename ValueTraits::TraitType ValueType; - typedef typename ValueStorageTraits::TraitType ValueStorageType; - static const bool needsRef = NeedsRef<ValueTraits, ValueStorageTraits>::value; - typedef RefCounterBase<needsRef, ValueTraits, ValueStorageTraits> Base; - static void ref(const ValueStorageType& v) { Base::ref(v); } - static void deref(const ValueStorageType& v) { Base::deref(v); } - }; - - template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits> - struct RefCounter<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> { - typedef typename FirstTraits::TraitType FirstType; - typedef typename SecondTraits::TraitType SecondType; - typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits; - typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits; - typedef typename ValueStorageTraits::TraitType ValueStorageType; - static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value; - static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value; - typedef RefCounterBase<firstNeedsRef, FirstTraits, FirstStorageTraits> FirstBase; - typedef RefCounterBase<secondNeedsRef, SecondTraits, SecondStorageTraits> SecondBase; - static void ref(const ValueStorageType& v) { - FirstBase::ref(v.first); - SecondBase::ref(v.second); - } - static void deref(const ValueStorageType& v) { - FirstBase::deref(v.first); - SecondBase::deref(v.second); - } - }; - - template<bool needsRef, typename HashTableType, typename ValueTraits> struct HashTableRefCounterBase; - - template<typename HashTableType, typename ValueTraits> - struct HashTableRefCounterBase<false, HashTableType, ValueTraits> - { - static void refAll(HashTableType&) { } - static void derefAll(HashTableType&) { } - }; - - template<typename HashTableType, typename ValueTraits> - struct HashTableRefCounterBase<true, HashTableType, ValueTraits> - { - typedef typename HashTableType::iterator iterator; - typedef RefCounter<ValueTraits, typename HashTableType::ValueTraits> ValueRefCounter; - static void refAll(HashTableType&); - static void derefAll(HashTableType&); - }; - - template<typename HashTableType, typename ValueTraits> - void HashTableRefCounterBase<true, HashTableType, ValueTraits>::refAll(HashTableType& table) - { - iterator end = table.end(); - for (iterator it = table.begin(); it != end; ++it) - ValueRefCounter::ref(*it); - } - - template<typename HashTableType, typename ValueTraits> - void HashTableRefCounterBase<true, HashTableType, ValueTraits>::derefAll(HashTableType& table) - { - iterator end = table.end(); - for (iterator it = table.begin(); it != end; ++it) - ValueRefCounter::deref(*it); - } - - template<typename HashTableType, typename ValueTraits> struct HashTableRefCounter { - static const bool needsRef = NeedsRef<ValueTraits, typename HashTableType::ValueTraits>::value; - typedef HashTableRefCounterBase<needsRef, HashTableType, ValueTraits> Base; - static void refAll(HashTableType& table) { Base::refAll(table); } - static void derefAll(HashTableType& table) { Base::derefAll(table); } - }; - - // helper template for HashMap and HashSet. - template<bool needsRef, typename FromType, typename ToType, typename FromTraits> struct Assigner; - - template<typename FromType, typename ToType, typename FromTraits> struct Assigner<false, FromType, ToType, FromTraits> { - typedef union { - FromType m_from; - ToType m_to; - } UnionType; - - static void assign(const FromType& from, ToType& to) { reinterpret_cast<UnionType*>(&to)->m_from = from; } - }; - - template<typename FromType, typename ToType, typename FromTraits> struct Assigner<true, FromType, ToType, FromTraits> { - static void assign(const FromType& from, ToType& to) - { - ToType oldTo = to; - memcpy(&to, &from, sizeof(FromType)); - FromTraits::ref(to); - FromTraits::deref(oldTo); - } - }; - - template<typename FromType, typename FromTraits> struct Assigner<false, FromType, FromType, FromTraits> { - static void assign(const FromType& from, FromType& to) { to = from; } - }; - - template<typename FromType, typename FromTraits> struct Assigner<true, FromType, FromType, FromTraits> { - static void assign(const FromType& from, FromType& to) { to = from; } - }; - } // namespace WTF #include "HashIterators.h" |