| 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 |