| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. |
| 3 * Copyright (C) 2008 David Levin <levin@chromium.org> | 3 * Copyright (C) 2008 David Levin <levin@chromium.org> |
| 4 * | 4 * |
| 5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
| 6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
| 7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
| 8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
| 9 * | 9 * |
| 10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
| (...skipping 461 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 472 void clear(); | 472 void clear(); |
| 473 | 473 |
| 474 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsE
mptyValue<KeyTraits>(Extractor::extract(value)); } | 474 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsE
mptyValue<KeyTraits>(Extractor::extract(value)); } |
| 475 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::
isDeletedValue(Extractor::extract(value)); } | 475 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::
isDeletedValue(Extractor::extract(value)); } |
| 476 static bool isEmptyOrDeletedBucket(const ValueType& value) { return Hash
TableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); } | 476 static bool isEmptyOrDeletedBucket(const ValueType& value) { return Hash
TableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); } |
| 477 | 477 |
| 478 ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorT
ype, KeyPeekInType>(key); } | 478 ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorT
ype, KeyPeekInType>(key); } |
| 479 template<typename HashTranslator, typename T> ValueType* lookup(T); | 479 template<typename HashTranslator, typename T> ValueType* lookup(T); |
| 480 template<typename HashTranslator, typename T> const ValueType* lookup(T)
const; | 480 template<typename HashTranslator, typename T> const ValueType* lookup(T)
const; |
| 481 | 481 |
| 482 void trace(typename Allocator::Visitor*); | 482 template<typename VisitorDispatcher> void trace(VisitorDispatcher); |
| 483 | 483 |
| 484 #if ENABLE(ASSERT) | 484 #if ENABLE(ASSERT) |
| 485 int64_t modifications() const { return m_modifications; } | 485 int64_t modifications() const { return m_modifications; } |
| 486 void registerModification() { m_modifications++; } | 486 void registerModification() { m_modifications++; } |
| 487 // HashTable and collections that build on it do not support | 487 // HashTable and collections that build on it do not support |
| 488 // modifications while there is an iterator in use. The exception is | 488 // modifications while there is an iterator in use. The exception is |
| 489 // ListHashSet, which has its own iterators that tolerate modification | 489 // ListHashSet, which has its own iterators that tolerate modification |
| 490 // of the underlying set. | 490 // of the underlying set. |
| 491 void checkModifications(int64_t mods) const { ASSERT(mods == m_modificat
ions); } | 491 void checkModifications(int64_t mods) const { ASSERT(mods == m_modificat
ions); } |
| 492 #else | 492 #else |
| (...skipping 723 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1216 static void ephemeronIterationDone(typename Allocator::Visitor* visitor,
void* closure) | 1216 static void ephemeronIterationDone(typename Allocator::Visitor* visitor,
void* closure) |
| 1217 { | 1217 { |
| 1218 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits, Allocator> HashTableType; | 1218 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits, Allocator> HashTableType; |
| 1219 HashTableType* table = reinterpret_cast<HashTableType*>(closure); | 1219 HashTableType* table = reinterpret_cast<HashTableType*>(closure); |
| 1220 ASSERT(Allocator::weakTableRegistered(visitor, table)); | 1220 ASSERT(Allocator::weakTableRegistered(visitor, table)); |
| 1221 table->clearEnqueued(); | 1221 table->clearEnqueued(); |
| 1222 } | 1222 } |
| 1223 }; | 1223 }; |
| 1224 | 1224 |
| 1225 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 1225 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
| 1226 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo
cator>::trace(typename Allocator::Visitor* visitor) | 1226 template<typename VisitorDispatcher> |
| 1227 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo
cator>::trace(VisitorDispatcher visitor) |
| 1227 { | 1228 { |
| 1228 // If someone else already marked the backing and queued up the trace | 1229 // If someone else already marked the backing and queued up the trace |
| 1229 // and/or weak callback then we are done. This optimization does not | 1230 // and/or weak callback then we are done. This optimization does not |
| 1230 // happen for ListHashSet since its iterator does not point at the | 1231 // happen for ListHashSet since its iterator does not point at the |
| 1231 // backing. | 1232 // backing. |
| 1232 if (!m_table || visitor->isAlive(m_table)) | 1233 if (!m_table || visitor->isAlive(m_table)) |
| 1233 return; | 1234 return; |
| 1234 // Normally, we mark the backing store without performing trace. This | 1235 // Normally, we mark the backing store without performing trace. This |
| 1235 // means it is marked live, but the pointers inside it are not marked. | 1236 // means it is marked live, but the pointers inside it are not marked. |
| 1236 // Instead we will mark the pointers below. However, for backing | 1237 // Instead we will mark the pointers below. However, for backing |
| (...skipping 30 matching lines...) Expand all Loading... |
| 1267 // We don't need to trace the elements here, since registering | 1268 // We don't need to trace the elements here, since registering |
| 1268 // as a weak table above will cause them to be traced (perhaps | 1269 // as a weak table above will cause them to be traced (perhaps |
| 1269 // several times). It's better to wait until everything else is | 1270 // several times). It's better to wait until everything else is |
| 1270 // traced before tracing the elements for the first time; this | 1271 // traced before tracing the elements for the first time; this |
| 1271 // may reduce (by one) the number of iterations needed to get | 1272 // may reduce (by one) the number of iterations needed to get |
| 1272 // to a fixed point. | 1273 // to a fixed point. |
| 1273 return; | 1274 return; |
| 1274 } | 1275 } |
| 1275 for (ValueType* element = m_table + m_tableSize - 1; element >= m_ta
ble; element--) { | 1276 for (ValueType* element = m_table + m_tableSize - 1; element >= m_ta
ble; element--) { |
| 1276 if (!isEmptyOrDeletedBucket(*element)) | 1277 if (!isEmptyOrDeletedBucket(*element)) |
| 1277 Allocator::template trace<ValueType, Traits>(visitor, *eleme
nt); | 1278 Allocator::template trace<VisitorDispatcher, ValueType, Trai
ts>(visitor, *element); |
| 1278 } | 1279 } |
| 1279 } | 1280 } |
| 1280 } | 1281 } |
| 1281 | 1282 |
| 1282 // iterator adapters | 1283 // iterator adapters |
| 1283 | 1284 |
| 1284 template<typename HashTableType, typename Traits> struct HashTableConstItera
torAdapter { | 1285 template<typename HashTableType, typename Traits> struct HashTableConstItera
torAdapter { |
| 1285 HashTableConstIteratorAdapter() {} | 1286 HashTableConstIteratorAdapter() {} |
| 1286 HashTableConstIteratorAdapter(const typename HashTableType::const_iterat
or& impl) : m_impl(impl) {} | 1287 HashTableConstIteratorAdapter(const typename HashTableType::const_iterat
or& impl) : m_impl(impl) {} |
| 1287 typedef typename Traits::IteratorConstGetType GetType; | 1288 typedef typename Traits::IteratorConstGetType GetType; |
| (...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1378 CollectionIterator end(toBeRemoved.end()); | 1379 CollectionIterator end(toBeRemoved.end()); |
| 1379 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 1380 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
| 1380 collection.remove(*it); | 1381 collection.remove(*it); |
| 1381 } | 1382 } |
| 1382 | 1383 |
| 1383 } // namespace WTF | 1384 } // namespace WTF |
| 1384 | 1385 |
| 1385 #include "wtf/HashIterators.h" | 1386 #include "wtf/HashIterators.h" |
| 1386 | 1387 |
| 1387 #endif // WTF_HashTable_h | 1388 #endif // WTF_HashTable_h |
| OLD | NEW |