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 |