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 647 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
658 } | 658 } |
659 UPDATE_PROBE_COUNTS(); | 659 UPDATE_PROBE_COUNTS(); |
660 if (!k) | 660 if (!k) |
661 k = 1 | doubleHash(h); | 661 k = 1 | doubleHash(h); |
662 i = (i + k) & sizeMask; | 662 i = (i + k) & sizeMask; |
663 } | 663 } |
664 } | 664 } |
665 | 665 |
666 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 666 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
667 template<typename HashTranslator, typename T> | 667 template<typename HashTranslator, typename T> |
668 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Tr
aits, KeyTraits, Allocator>::lookupForWriting(const T& key) | 668 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator>::lookupForWriting(const T& key) -> LookupType |
669 { | 669 { |
670 ASSERT(m_table); | 670 ASSERT(m_table); |
671 registerModification(); | 671 registerModification(); |
672 | 672 |
673 ValueType* table = m_table; | 673 ValueType* table = m_table; |
674 size_t k = 0; | 674 size_t k = 0; |
675 size_t sizeMask = tableSizeMask(); | 675 size_t sizeMask = tableSizeMask(); |
676 unsigned h = HashTranslator::hash(key); | 676 unsigned h = HashTranslator::hash(key); |
677 size_t i = h & sizeMask; | 677 size_t i = h & sizeMask; |
678 | 678 |
(...skipping 21 matching lines...) Expand all Loading... |
700 } | 700 } |
701 UPDATE_PROBE_COUNTS(); | 701 UPDATE_PROBE_COUNTS(); |
702 if (!k) | 702 if (!k) |
703 k = 1 | doubleHash(h); | 703 k = 1 | doubleHash(h); |
704 i = (i + k) & sizeMask; | 704 i = (i + k) & sizeMask; |
705 } | 705 } |
706 } | 706 } |
707 | 707 |
708 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 708 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
709 template<typename HashTranslator, typename T> | 709 template<typename HashTranslator, typename T> |
710 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions
, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key) | 710 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator>::fullLookupForWriting(const T& key) -> FullLookupType |
711 { | 711 { |
712 ASSERT(m_table); | 712 ASSERT(m_table); |
713 registerModification(); | 713 registerModification(); |
714 | 714 |
715 ValueType* table = m_table; | 715 ValueType* table = m_table; |
716 size_t k = 0; | 716 size_t k = 0; |
717 size_t sizeMask = tableSizeMask(); | 717 size_t sizeMask = tableSizeMask(); |
718 unsigned h = HashTranslator::hash(key); | 718 unsigned h = HashTranslator::hash(key); |
719 size_t i = h & sizeMask; | 719 size_t i = h & sizeMask; |
720 | 720 |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
774 // contained garbage (eg. from a previous use of the same slot). | 774 // contained garbage (eg. from a previous use of the same slot). |
775 // Therefore we forbid a GC while both the key and the value are | 775 // Therefore we forbid a GC while both the key and the value are |
776 // initialized. | 776 // initialized. |
777 Allocator::enterGCForbiddenScope(); | 777 Allocator::enterGCForbiddenScope(); |
778 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initializ
e<Traits>(bucket); | 778 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initializ
e<Traits>(bucket); |
779 Allocator::leaveGCForbiddenScope(); | 779 Allocator::leaveGCForbiddenScope(); |
780 } | 780 } |
781 | 781 |
782 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 782 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
783 template<typename HashTranslator, typename T, typename Extra> | 783 template<typename HashTranslator, typename T, typename Extra> |
784 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, Ke
yTraits, Allocator>::add(const T& key, const Extra& extra) | 784 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo
cator>::add(const T& key, const Extra& extra) -> AddResult |
785 { | 785 { |
786 ASSERT(Allocator::isAllocationAllowed()); | 786 ASSERT(Allocator::isAllocationAllowed()); |
787 if (!m_table) | 787 if (!m_table) |
788 expand(); | 788 expand(); |
789 | 789 |
790 ASSERT(m_table); | 790 ASSERT(m_table); |
791 | 791 |
792 ValueType* table = m_table; | 792 ValueType* table = m_table; |
793 size_t k = 0; | 793 size_t k = 0; |
794 size_t sizeMask = tableSizeMask(); | 794 size_t sizeMask = tableSizeMask(); |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
839 ++m_keyCount; | 839 ++m_keyCount; |
840 | 840 |
841 if (shouldExpand()) | 841 if (shouldExpand()) |
842 entry = expand(entry); | 842 entry = expand(entry); |
843 | 843 |
844 return AddResult(this, entry, true); | 844 return AddResult(this, entry, true); |
845 } | 845 } |
846 | 846 |
847 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 847 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
848 template<typename HashTranslator, typename T, typename Extra> | 848 template<typename HashTranslator, typename T, typename Extra> |
849 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, Ke
yTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra) | 849 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo
cator>::addPassingHashCode(const T& key, const Extra& extra) -> AddResult |
850 { | 850 { |
851 ASSERT(Allocator::isAllocationAllowed()); | 851 ASSERT(Allocator::isAllocationAllowed()); |
852 if (!m_table) | 852 if (!m_table) |
853 expand(); | 853 expand(); |
854 | 854 |
855 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); | 855 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); |
856 | 856 |
857 ValueType* entry = lookupResult.first.first; | 857 ValueType* entry = lookupResult.first.first; |
858 bool found = lookupResult.first.second; | 858 bool found = lookupResult.first.second; |
859 unsigned h = lookupResult.second; | 859 unsigned h = lookupResult.second; |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
903 { | 903 { |
904 ValueType* entry = lookup<HashTranslator>(key); | 904 ValueType* entry = lookup<HashTranslator>(key); |
905 if (!entry) | 905 if (!entry) |
906 return end(); | 906 return end(); |
907 | 907 |
908 return makeKnownGoodIterator(entry); | 908 return makeKnownGoodIterator(entry); |
909 } | 909 } |
910 | 910 |
911 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 911 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
912 template <typename HashTranslator, typename T> | 912 template <typename HashTranslator, typename T> |
913 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits, Allocator>::const_iterator HashTable<Key, Value, Extractor, HashFunctions
, Traits, KeyTraits, Allocator>::find(const T& key) const | 913 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator>::find(const T& key) const -> const_iterator |
914 { | 914 { |
915 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(
key); | 915 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(
key); |
916 if (!entry) | 916 if (!entry) |
917 return end(); | 917 return end(); |
918 | 918 |
919 return makeKnownGoodConstIterator(entry); | 919 return makeKnownGoodConstIterator(entry); |
920 } | 920 } |
921 | 921 |
922 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 922 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
923 template <typename HashTranslator, typename T> | 923 template <typename HashTranslator, typename T> |
(...skipping 271 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1195 #if ENABLE(ASSERT) | 1195 #if ENABLE(ASSERT) |
1196 std::swap(m_modifications, other.m_modifications); | 1196 std::swap(m_modifications, other.m_modifications); |
1197 #endif | 1197 #endif |
1198 | 1198 |
1199 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1199 #if DUMP_HASHTABLE_STATS_PER_TABLE |
1200 m_stats.swap(other.m_stats); | 1200 m_stats.swap(other.m_stats); |
1201 #endif | 1201 #endif |
1202 } | 1202 } |
1203 | 1203 |
1204 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 1204 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
1205 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator
>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>
::operator=(const HashTable& other) | 1205 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo
cator>::operator=(const HashTable& other) -> HashTable& |
1206 { | 1206 { |
1207 HashTable tmp(other); | 1207 HashTable tmp(other); |
1208 swap(tmp); | 1208 swap(tmp); |
1209 return *this; | 1209 return *this; |
1210 } | 1210 } |
1211 | 1211 |
1212 template<WeakHandlingFlag weakHandlingFlag, typename Key, typename Value, ty
pename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, t
ypename Allocator> | 1212 template<WeakHandlingFlag weakHandlingFlag, typename Key, typename Value, ty
pename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, t
ypename Allocator> |
1213 struct WeakProcessingHashTableHelper; | 1213 struct WeakProcessingHashTableHelper; |
1214 | 1214 |
1215 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 1215 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
(...skipping 228 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1444 CollectionIterator end(toBeRemoved.end()); | 1444 CollectionIterator end(toBeRemoved.end()); |
1445 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 1445 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
1446 collection.remove(*it); | 1446 collection.remove(*it); |
1447 } | 1447 } |
1448 | 1448 |
1449 } // namespace WTF | 1449 } // namespace WTF |
1450 | 1450 |
1451 #include "wtf/HashIterators.h" | 1451 #include "wtf/HashIterators.h" |
1452 | 1452 |
1453 #endif // WTF_HashTable_h | 1453 #endif // WTF_HashTable_h |
OLD | NEW |