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 1258 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1269 struct WeakProcessingHashTableHelper<NoWeakHandlingInCollections, Key, Value, Ex
tractor, HashFunctions, Traits, KeyTraits, Allocator> { | 1269 struct WeakProcessingHashTableHelper<NoWeakHandlingInCollections, Key, Value, Ex
tractor, HashFunctions, Traits, KeyTraits, Allocator> { |
1270 STATIC_ONLY(WeakProcessingHashTableHelper); | 1270 STATIC_ONLY(WeakProcessingHashTableHelper); |
1271 static void process(typename Allocator::Visitor* visitor, void* closure) {} | 1271 static void process(typename Allocator::Visitor* visitor, void* closure) {} |
1272 static void ephemeronIteration(typename Allocator::Visitor* visitor, void* c
losure) {} | 1272 static void ephemeronIteration(typename Allocator::Visitor* visitor, void* c
losure) {} |
1273 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, voi
d* closure) {} | 1273 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, voi
d* closure) {} |
1274 }; | 1274 }; |
1275 | 1275 |
1276 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 1276 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
1277 struct WeakProcessingHashTableHelper<WeakHandlingInCollections, Key, Value, Extr
actor, HashFunctions, Traits, KeyTraits, Allocator> { | 1277 struct WeakProcessingHashTableHelper<WeakHandlingInCollections, Key, Value, Extr
actor, HashFunctions, Traits, KeyTraits, Allocator> { |
1278 STATIC_ONLY(WeakProcessingHashTableHelper); | 1278 STATIC_ONLY(WeakProcessingHashTableHelper); |
| 1279 |
| 1280 using HashTableType = HashTable<Key, Value, Extractor, HashFunctions, Traits
, KeyTraits, Allocator>; |
| 1281 using ValueType = typename HashTableType::ValueType; |
| 1282 |
1279 // Used for purely weak and for weak-and-strong tables (ephemerons). | 1283 // Used for purely weak and for weak-and-strong tables (ephemerons). |
1280 static void process(typename Allocator::Visitor* visitor, void* closure) | 1284 static void process(typename Allocator::Visitor* visitor, void* closure) |
1281 { | 1285 { |
1282 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; | |
1283 HashTableType* table = reinterpret_cast<HashTableType*>(closure); | 1286 HashTableType* table = reinterpret_cast<HashTableType*>(closure); |
1284 if (!table->m_table) | 1287 if (!table->m_table) |
1285 return; | 1288 return; |
1286 // Now perform weak processing (this is a no-op if the backing was | 1289 // Now perform weak processing (this is a no-op if the backing was |
1287 // accessible through an iterator and was already marked strongly). | 1290 // accessible through an iterator and was already marked strongly). |
1288 typedef typename HashTableType::ValueType ValueType; | |
1289 for (ValueType* element = table->m_table + table->m_tableSize - 1; eleme
nt >= table->m_table; element--) { | 1291 for (ValueType* element = table->m_table + table->m_tableSize - 1; eleme
nt >= table->m_table; element--) { |
1290 if (!HashTableType::isEmptyOrDeletedBucket(*element)) { | 1292 if (!HashTableType::isEmptyOrDeletedBucket(*element)) { |
1291 // At this stage calling trace can make no difference | 1293 // At this stage calling trace can make no difference |
1292 // (everything is already traced), but we use the return value | 1294 // (everything is already traced), but we use the return value |
1293 // to remove things from the collection. | 1295 // to remove things from the collection. |
1294 | 1296 |
1295 // FIXME: This should be rewritten so that this can check if the | 1297 // FIXME: This should be rewritten so that this can check if the |
1296 // element is dead without calling trace, which is semantically | 1298 // element is dead without calling trace, which is semantically |
1297 // not correct to be called in weak processing stage. | 1299 // not correct to be called in weak processing stage. |
1298 if (TraceInCollectionTrait<WeakHandlingInCollections, WeakPointe
rsActWeak, ValueType, Traits>::trace(visitor, *element)) { | 1300 if (TraceInCollectionTrait<WeakHandlingInCollections, WeakPointe
rsActWeak, ValueType, Traits>::trace(visitor, *element)) { |
1299 table->registerModification(); | 1301 table->registerModification(); |
1300 HashTableType::deleteBucket(*element); // Also calls the des
tructor. | 1302 HashTableType::deleteBucket(*element); // Also calls the des
tructor. |
1301 table->m_deletedCount++; | 1303 table->m_deletedCount++; |
1302 table->m_keyCount--; | 1304 table->m_keyCount--; |
1303 // We don't rehash the backing until the next add or delete, | 1305 // We don't rehash the backing until the next add or delete, |
1304 // because that would cause allocation during GC. | 1306 // because that would cause allocation during GC. |
1305 } | 1307 } |
1306 } | 1308 } |
1307 } | 1309 } |
1308 } | 1310 } |
1309 | 1311 |
1310 // Called repeatedly for tables that have both weak and strong pointers. | 1312 // Called repeatedly for tables that have both weak and strong pointers. |
1311 static void ephemeronIteration(typename Allocator::Visitor* visitor, void* c
losure) | 1313 static void ephemeronIteration(typename Allocator::Visitor* visitor, void* c
losure) |
1312 { | 1314 { |
1313 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; | |
1314 HashTableType* table = reinterpret_cast<HashTableType*>(closure); | 1315 HashTableType* table = reinterpret_cast<HashTableType*>(closure); |
1315 ASSERT(table->m_table); | 1316 ASSERT(table->m_table); |
1316 // Check the hash table for elements that we now know will not be | 1317 // Check the hash table for elements that we now know will not be |
1317 // removed by weak processing. Those elements need to have their strong | 1318 // removed by weak processing. Those elements need to have their strong |
1318 // pointers traced. | 1319 // pointers traced. |
1319 typedef typename HashTableType::ValueType ValueType; | |
1320 for (ValueType* element = table->m_table + table->m_tableSize - 1; eleme
nt >= table->m_table; element--) { | 1320 for (ValueType* element = table->m_table + table->m_tableSize - 1; eleme
nt >= table->m_table; element--) { |
1321 if (!HashTableType::isEmptyOrDeletedBucket(*element)) | 1321 if (!HashTableType::isEmptyOrDeletedBucket(*element)) |
1322 TraceInCollectionTrait<WeakHandlingInCollections, WeakPointersAc
tWeak, ValueType, Traits>::trace(visitor, *element); | 1322 TraceInCollectionTrait<WeakHandlingInCollections, WeakPointersAc
tWeak, ValueType, Traits>::trace(visitor, *element); |
1323 } | 1323 } |
1324 } | 1324 } |
1325 | 1325 |
1326 // Called when the ephemeron iteration is done and before running the per | 1326 // Called when the ephemeron iteration is done and before running the per |
1327 // thread weak processing. It is guaranteed to be called before any thread | 1327 // thread weak processing. It is guaranteed to be called before any thread |
1328 // is resumed. | 1328 // is resumed. |
1329 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, voi
d* closure) | 1329 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, voi
d* closure) |
1330 { | 1330 { |
1331 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; | |
1332 HashTableType* table = reinterpret_cast<HashTableType*>(closure); | 1331 HashTableType* table = reinterpret_cast<HashTableType*>(closure); |
1333 ASSERT(Allocator::weakTableRegistered(visitor, table)); | 1332 ASSERT(Allocator::weakTableRegistered(visitor, table)); |
1334 table->clearEnqueued(); | 1333 table->clearEnqueued(); |
1335 } | 1334 } |
1336 }; | 1335 }; |
1337 | 1336 |
1338 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 1337 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
1339 template <typename VisitorDispatcher> | 1338 template <typename VisitorDispatcher> |
1340 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocato
r>::trace(VisitorDispatcher visitor) | 1339 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocato
r>::trace(VisitorDispatcher visitor) |
1341 { | 1340 { |
(...skipping 17 matching lines...) Expand all Loading... |
1359 // needed. | 1358 // needed. |
1360 if (Traits::weakHandlingFlag == NoWeakHandlingInCollections) { | 1359 if (Traits::weakHandlingFlag == NoWeakHandlingInCollections) { |
1361 Allocator::markNoTracing(visitor, m_table); | 1360 Allocator::markNoTracing(visitor, m_table); |
1362 } else { | 1361 } else { |
1363 Allocator::registerDelayedMarkNoTracing(visitor, m_table); | 1362 Allocator::registerDelayedMarkNoTracing(visitor, m_table); |
1364 // Since we're delaying marking this HashTable, it is possible that the | 1363 // Since we're delaying marking this HashTable, it is possible that the |
1365 // registerWeakMembers is called multiple times (in rare | 1364 // registerWeakMembers is called multiple times (in rare |
1366 // cases). However, it shouldn't cause any issue. | 1365 // cases). However, it shouldn't cause any issue. |
1367 Allocator::registerWeakMembers(visitor, this, m_table, WeakProcessingHas
hTableHelper<Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator>::process); | 1366 Allocator::registerWeakMembers(visitor, this, m_table, WeakProcessingHas
hTableHelper<Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator>::process); |
1368 } | 1367 } |
1369 if (NeedsTracingTrait<Traits>::value) { | 1368 if (!NeedsTracingTrait<Traits>::value) |
1370 if (Traits::weakHandlingFlag == WeakHandlingInCollections) { | 1369 return; |
1371 // If we have both strong and weak pointers in the collection then | 1370 if (Traits::weakHandlingFlag == WeakHandlingInCollections) { |
1372 // we queue up the collection for fixed point iteration a la | 1371 // If we have both strong and weak pointers in the collection then |
1373 // Ephemerons: | 1372 // we queue up the collection for fixed point iteration a la |
1374 // http://dl.acm.org/citation.cfm?doid=263698.263733 - see also | 1373 // Ephemerons: |
1375 // http://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak | 1374 // http://dl.acm.org/citation.cfm?doid=263698.263733 - see also |
1376 ASSERT(!enqueued() || Allocator::weakTableRegistered(visitor, this))
; | 1375 // http://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak |
1377 if (!enqueued()) { | 1376 ASSERT(!enqueued() || Allocator::weakTableRegistered(visitor, this)); |
1378 Allocator::registerWeakTable(visitor, this, | 1377 if (!enqueued()) { |
1379 WeakProcessingHashTableHelper<Traits::weakHandlingFlag, Key,
Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::ephemeronIterat
ion, | 1378 Allocator::registerWeakTable(visitor, this, |
1380 WeakProcessingHashTableHelper<Traits::weakHandlingFlag, Key,
Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::ephemeronIterat
ionDone); | 1379 WeakProcessingHashTableHelper<Traits::weakHandlingFlag, Key, Val
ue, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::ephemeronIteration, |
1381 setEnqueued(); | 1380 WeakProcessingHashTableHelper<Traits::weakHandlingFlag, Key, Val
ue, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::ephemeronIterationD
one); |
1382 } | 1381 setEnqueued(); |
1383 // We don't need to trace the elements here, since registering as a | |
1384 // weak table above will cause them to be traced (perhaps several | |
1385 // times). It's better to wait until everything else is traced | |
1386 // before tracing the elements for the first time; this may reduce | |
1387 // (by one) the number of iterations needed to get to a fixed point. | |
1388 return; | |
1389 } | 1382 } |
1390 for (ValueType* element = m_table + m_tableSize - 1; element >= m_table;
element--) { | 1383 // We don't need to trace the elements here, since registering as a |
1391 if (!isEmptyOrDeletedBucket(*element)) | 1384 // weak table above will cause them to be traced (perhaps several |
1392 Allocator::template trace<VisitorDispatcher, ValueType, Traits>(
visitor, *element); | 1385 // times). It's better to wait until everything else is traced |
1393 } | 1386 // before tracing the elements for the first time; this may reduce |
| 1387 // (by one) the number of iterations needed to get to a fixed point. |
| 1388 return; |
| 1389 } |
| 1390 for (ValueType* element = m_table + m_tableSize - 1; element >= m_table; ele
ment--) { |
| 1391 if (!isEmptyOrDeletedBucket(*element)) |
| 1392 Allocator::template trace<VisitorDispatcher, ValueType, Traits>(visi
tor, *element); |
1394 } | 1393 } |
1395 } | 1394 } |
1396 | 1395 |
1397 // iterator adapters | 1396 // iterator adapters |
1398 | 1397 |
1399 template <typename HashTableType, typename Traits> struct HashTableConstIterator
Adapter { | 1398 template <typename HashTableType, typename Traits> struct HashTableConstIterator
Adapter { |
1400 STACK_ALLOCATED(); | 1399 STACK_ALLOCATED(); |
1401 HashTableConstIteratorAdapter() {} | 1400 HashTableConstIteratorAdapter() {} |
1402 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator&
impl) : m_impl(impl) {} | 1401 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator&
impl) : m_impl(impl) {} |
1403 typedef typename Traits::IteratorConstGetType GetType; | 1402 typedef typename Traits::IteratorConstGetType GetType; |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1495 CollectionIterator end(toBeRemoved.end()); | 1494 CollectionIterator end(toBeRemoved.end()); |
1496 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 1495 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
1497 collection.remove(*it); | 1496 collection.remove(*it); |
1498 } | 1497 } |
1499 | 1498 |
1500 } // namespace WTF | 1499 } // namespace WTF |
1501 | 1500 |
1502 #include "wtf/HashIterators.h" | 1501 #include "wtf/HashIterators.h" |
1503 | 1502 |
1504 #endif // WTF_HashTable_h | 1503 #endif // WTF_HashTable_h |
OLD | NEW |