-// -*- 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.
+ * Copyright (C) 2008 David Levin <levin@chromium.org>
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
#include "FastMalloc.h"
#include "HashTraits.h"
#include <wtf/Assertions.h>
+#include <wtf/Threading.h>
namespace WTF {
struct HashTableStats {
~HashTableStats();
+ // All of the variables are accessed in ~HashTableStats when the static struct is destroyed.
+
+ // The following variables are all atomically incremented when modified.
static int numAccesses;
- static int numCollisions;
- static int collisionGraph[4096];
- static int maxCollisions;
static int numRehashes;
static int numRemoves;
static int numReinserts;
+
+ // The following variables are only modified in the recordCollisionAtCount method within a mutex.
+ static int maxCollisions;
+ static int numCollisions;
+ static int collisionGraph[4096];
+
static void recordCollisionAtCount(int count);
};
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:
#if CHECK_HASHTABLE_ITERATORS
public:
+ // Any modifications of the m_next or m_previous of an iterator that is in a linked list of a HashTable::m_iterator,
+ // should be guarded with m_table->m_mutex.
mutable const HashTableType* m_table;
mutable const_iterator* m_next;
mutable const_iterator* m_previous;
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;
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*);
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); }
#if CHECK_HASHTABLE_ITERATORS
public:
+ // All access to m_iterators should be guarded with m_mutex.
mutable const_iterator* m_iterators;
+ mutable Mutex m_mutex;
#endif
};
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;
+ atomicIncrement(&HashTableStats::numAccesses);
int probeCount = 0;
#endif
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;
int i = h & sizeMask;
#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numAccesses;
+ atomicIncrement(&HashTableStats::numAccesses);
int probeCount = 0;
#endif
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;
int i = h & sizeMask;
#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numAccesses;
+ atomicIncrement(&HashTableStats::numAccesses);
int probeCount = 0;
#endif
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();
int i = h & sizeMask;
#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numAccesses;
+ atomicIncrement(&HashTableStats::numAccesses);
int probeCount = 0;
#endif
}
if (deletedEntry) {
+ initializeBucket(*deletedEntry);
entry = deletedEntry;
--m_deletedCount;
}
++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();
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)
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();
ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numReinserts;
+ atomicIncrement(&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>
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();
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>
void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
{
#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numRemoves;
+ atomicIncrement(&HashTableStats::numRemoves);
#endif
deleteBucket(*pos);
}
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]);
}
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);
}
checkTableConsistencyExceptSize();
int oldTableSize = m_tableSize;
- ValueType *oldTable = m_table;
+ ValueType* oldTable = m_table;
#if DUMP_HASHTABLE_STATS
if (oldTableSize != 0)
- ++HashTableStats::numRehashes;
+ atomicIncrement(&HashTableStats::numRehashes);
#endif
m_tableSize = newTableSize;
invalidateIterators();
other.invalidateIterators();
- ValueType *tmp_table = m_table;
+ ValueType* tmp_table = m_table;
m_table = other.m_table;
other.m_table = tmp_table;
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;
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
{
+ MutexLocker lock(m_mutex);
const_iterator* next;
for (const_iterator* p = m_iterators; p; p = next) {
next = p->m_next;
if (!table) {
it->m_next = 0;
} else {
+ MutexLocker lock(table->m_mutex);
ASSERT(table->m_iterators != it);
it->m_next = table->m_iterators;
table->m_iterators = it;
ASSERT(!it->m_next);
ASSERT(!it->m_previous);
} else {
+ MutexLocker lock(it->m_table->m_mutex);
if (it->m_next) {
ASSERT(it->m_next->m_previous == it);
it->m_next->m_previous = it->m_previous;
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"
projects / apple / javascriptcore.git / blobdiff