| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights |
| 3 * reserved. | 3 * reserved. |
| 4 * Copyright (C) 2008 David Levin <levin@chromium.org> | 4 * Copyright (C) 2008 David Levin <levin@chromium.org> |
| 5 * | 5 * |
| 6 * This library is free software; you can redistribute it and/or | 6 * This library is free software; you can redistribute it and/or |
| 7 * modify it under the terms of the GNU Library General Public | 7 * modify it under the terms of the GNU Library General Public |
| 8 * License as published by the Free Software Foundation; either | 8 * License as published by the Free Software Foundation; either |
| 9 * version 2 of the License, or (at your option) any later version. | 9 * version 2 of the License, or (at your option) any later version. |
| 10 * | 10 * |
| (...skipping 739 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 750 return contains<IdentityTranslatorType>(key); | 750 return contains<IdentityTranslatorType>(key); |
| 751 } | 751 } |
| 752 | 752 |
| 753 template <typename HashTranslator, typename T> | 753 template <typename HashTranslator, typename T> |
| 754 iterator find(const T&); | 754 iterator find(const T&); |
| 755 template <typename HashTranslator, typename T> | 755 template <typename HashTranslator, typename T> |
| 756 const_iterator find(const T&) const; | 756 const_iterator find(const T&) const; |
| 757 template <typename HashTranslator, typename T> | 757 template <typename HashTranslator, typename T> |
| 758 bool contains(const T&) const; | 758 bool contains(const T&) const; |
| 759 | 759 |
| 760 void remove(KeyPeekInType); | 760 void erase(KeyPeekInType); |
| 761 void remove(iterator); | 761 void erase(iterator); |
| 762 void remove(const_iterator); | 762 void erase(const_iterator); |
| 763 void clear(); | 763 void clear(); |
| 764 | 764 |
| 765 static bool isEmptyBucket(const ValueType& value) { | 765 static bool isEmptyBucket(const ValueType& value) { |
| 766 return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); | 766 return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); |
| 767 } | 767 } |
| 768 static bool isDeletedBucket(const ValueType& value) { | 768 static bool isDeletedBucket(const ValueType& value) { |
| 769 return KeyTraits::isDeletedValue(Extractor::extract(value)); | 769 return KeyTraits::isDeletedValue(Extractor::extract(value)); |
| 770 } | 770 } |
| 771 static bool isEmptyOrDeletedBucket(const ValueType& value) { | 771 static bool isEmptyOrDeletedBucket(const ValueType& value) { |
| 772 return HashTableHelper<ValueType, Extractor, | 772 return HashTableHelper<ValueType, Extractor, |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 816 typedef std::pair<LookupType, unsigned> FullLookupType; | 816 typedef std::pair<LookupType, unsigned> FullLookupType; |
| 817 | 817 |
| 818 LookupType lookupForWriting(const Key& key) { | 818 LookupType lookupForWriting(const Key& key) { |
| 819 return lookupForWriting<IdentityTranslatorType>(key); | 819 return lookupForWriting<IdentityTranslatorType>(key); |
| 820 } | 820 } |
| 821 template <typename HashTranslator, typename T> | 821 template <typename HashTranslator, typename T> |
| 822 FullLookupType fullLookupForWriting(const T&); | 822 FullLookupType fullLookupForWriting(const T&); |
| 823 template <typename HashTranslator, typename T> | 823 template <typename HashTranslator, typename T> |
| 824 LookupType lookupForWriting(const T&); | 824 LookupType lookupForWriting(const T&); |
| 825 | 825 |
| 826 void remove(ValueType*); | 826 void erase(ValueType*); |
| 827 | 827 |
| 828 bool shouldExpand() const { | 828 bool shouldExpand() const { |
| 829 return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; | 829 return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; |
| 830 } | 830 } |
| 831 bool mustRehashInPlace() const { | 831 bool mustRehashInPlace() const { |
| 832 return m_keyCount * m_minLoad < m_tableSize * 2; | 832 return m_keyCount * m_minLoad < m_tableSize * 2; |
| 833 } | 833 } |
| 834 bool shouldShrink() const { | 834 bool shouldShrink() const { |
| 835 // isAllocationAllowed check should be at the last because it's | 835 // isAllocationAllowed check should be at the last because it's |
| 836 // expensive. | 836 // expensive. |
| (...skipping 454 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1291 entry = expand(entry); | 1291 entry = expand(entry); |
| 1292 } else if (Traits::weakHandlingFlag == WeakHandlingInCollections && | 1292 } else if (Traits::weakHandlingFlag == WeakHandlingInCollections && |
| 1293 shouldShrink()) { | 1293 shouldShrink()) { |
| 1294 // When weak hash tables are processed by the garbage collector, | 1294 // When weak hash tables are processed by the garbage collector, |
| 1295 // elements with no other strong references to them will have their | 1295 // elements with no other strong references to them will have their |
| 1296 // table entries cleared. But no shrinking of the backing store is | 1296 // table entries cleared. But no shrinking of the backing store is |
| 1297 // allowed at that time, as allocations are prohibited during that | 1297 // allowed at that time, as allocations are prohibited during that |
| 1298 // GC phase. | 1298 // GC phase. |
| 1299 // | 1299 // |
| 1300 // With that weak processing taking care of removals, explicit | 1300 // With that weak processing taking care of removals, explicit |
| 1301 // remove()s of elements is rarely done. Which implies that the | 1301 // erase()s of elements is rarely done. Which implies that the |
| 1302 // weak hash table will never be checked if it can be shrunk. | 1302 // weak hash table will never be checked if it can be shrunk. |
| 1303 // | 1303 // |
| 1304 // To prevent weak hash tables with very low load factors from | 1304 // To prevent weak hash tables with very low load factors from |
| 1305 // developing, we perform it when adding elements instead. | 1305 // developing, we perform it when adding elements instead. |
| 1306 entry = rehash(m_tableSize / 2, entry); | 1306 entry = rehash(m_tableSize / 2, entry); |
| 1307 } | 1307 } |
| 1308 | 1308 |
| 1309 return AddResult(this, entry, true); | 1309 return AddResult(this, entry, true); |
| 1310 } | 1310 } |
| 1311 | 1311 |
| (...skipping 147 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1459 typename HashFunctions, | 1459 typename HashFunctions, |
| 1460 typename Traits, | 1460 typename Traits, |
| 1461 typename KeyTraits, | 1461 typename KeyTraits, |
| 1462 typename Allocator> | 1462 typename Allocator> |
| 1463 void HashTable<Key, | 1463 void HashTable<Key, |
| 1464 Value, | 1464 Value, |
| 1465 Extractor, | 1465 Extractor, |
| 1466 HashFunctions, | 1466 HashFunctions, |
| 1467 Traits, | 1467 Traits, |
| 1468 KeyTraits, | 1468 KeyTraits, |
| 1469 Allocator>::remove(ValueType* pos) { | 1469 Allocator>::erase(ValueType* pos) { |
| 1470 registerModification(); | 1470 registerModification(); |
| 1471 #if DUMP_HASHTABLE_STATS | 1471 #if DUMP_HASHTABLE_STATS |
| 1472 atomicIncrement(&HashTableStats::instance().numRemoves); | 1472 atomicIncrement(&HashTableStats::instance().numRemoves); |
| 1473 #endif | 1473 #endif |
| 1474 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1474 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1475 ++m_stats->numRemoves; | 1475 ++m_stats->numRemoves; |
| 1476 #endif | 1476 #endif |
| 1477 | 1477 |
| 1478 enterAccessForbiddenScope(); | 1478 enterAccessForbiddenScope(); |
| 1479 deleteBucket(*pos); | 1479 deleteBucket(*pos); |
| 1480 leaveAccessForbiddenScope(); | 1480 leaveAccessForbiddenScope(); |
| 1481 ++m_deletedCount; | 1481 ++m_deletedCount; |
| 1482 --m_keyCount; | 1482 --m_keyCount; |
| 1483 | 1483 |
| 1484 if (shouldShrink()) | 1484 if (shouldShrink()) |
| 1485 shrink(); | 1485 shrink(); |
| 1486 } | 1486 } |
| 1487 | 1487 |
| 1488 template <typename Key, | 1488 template <typename Key, |
| 1489 typename Value, | 1489 typename Value, |
| 1490 typename Extractor, | 1490 typename Extractor, |
| 1491 typename HashFunctions, | 1491 typename HashFunctions, |
| 1492 typename Traits, | 1492 typename Traits, |
| 1493 typename KeyTraits, | 1493 typename KeyTraits, |
| 1494 typename Allocator> | 1494 typename Allocator> |
| 1495 inline void | 1495 inline void |
| 1496 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1496 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1497 remove(iterator it) { | 1497 erase(iterator it) { |
| 1498 if (it == end()) | 1498 if (it == end()) |
| 1499 return; | 1499 return; |
| 1500 remove(const_cast<ValueType*>(it.m_iterator.m_position)); | 1500 erase(const_cast<ValueType*>(it.m_iterator.m_position)); |
| 1501 } | 1501 } |
| 1502 | 1502 |
| 1503 template <typename Key, | 1503 template <typename Key, |
| 1504 typename Value, | 1504 typename Value, |
| 1505 typename Extractor, | 1505 typename Extractor, |
| 1506 typename HashFunctions, | 1506 typename HashFunctions, |
| 1507 typename Traits, | 1507 typename Traits, |
| 1508 typename KeyTraits, | 1508 typename KeyTraits, |
| 1509 typename Allocator> | 1509 typename Allocator> |
| 1510 inline void | 1510 inline void |
| 1511 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1511 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1512 remove(const_iterator it) { | 1512 erase(const_iterator it) { |
| 1513 if (it == end()) | 1513 if (it == end()) |
| 1514 return; | 1514 return; |
| 1515 remove(const_cast<ValueType*>(it.m_position)); | 1515 erase(const_cast<ValueType*>(it.m_position)); |
| 1516 } | 1516 } |
| 1517 | 1517 |
| 1518 template <typename Key, | 1518 template <typename Key, |
| 1519 typename Value, | 1519 typename Value, |
| 1520 typename Extractor, | 1520 typename Extractor, |
| 1521 typename HashFunctions, | 1521 typename HashFunctions, |
| 1522 typename Traits, | 1522 typename Traits, |
| 1523 typename KeyTraits, | 1523 typename KeyTraits, |
| 1524 typename Allocator> | 1524 typename Allocator> |
| 1525 inline void | 1525 inline void |
| 1526 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1526 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1527 remove(KeyPeekInType key) { | 1527 erase(KeyPeekInType key) { |
| 1528 remove(find(key)); | 1528 erase(find(key)); |
| 1529 } | 1529 } |
| 1530 | 1530 |
| 1531 template <typename Key, | 1531 template <typename Key, |
| 1532 typename Value, | 1532 typename Value, |
| 1533 typename Extractor, | 1533 typename Extractor, |
| 1534 typename HashFunctions, | 1534 typename HashFunctions, |
| 1535 typename Traits, | 1535 typename Traits, |
| 1536 typename KeyTraits, | 1536 typename KeyTraits, |
| 1537 typename Allocator> | 1537 typename Allocator> |
| 1538 Value* | 1538 Value* |
| (...skipping 732 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2271 CollectionIterator end(toBeRemoved.end()); | 2271 CollectionIterator end(toBeRemoved.end()); |
| 2272 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 2272 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
| 2273 collection.erase(*it); | 2273 collection.erase(*it); |
| 2274 } | 2274 } |
| 2275 | 2275 |
| 2276 } // namespace WTF | 2276 } // namespace WTF |
| 2277 | 2277 |
| 2278 #include "wtf/HashIterators.h" | 2278 #include "wtf/HashIterators.h" |
| 2279 | 2279 |
| 2280 #endif // WTF_HashTable_h | 2280 #endif // WTF_HashTable_h |
| OLD | NEW |