Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(790)

Side by Side Diff: third_party/WebKit/Source/wtf/HashTable.h

Issue 2585673002: Replace ASSERT, ENABLE(ASSERT), and ASSERT_NOT_REACHED in wtf (Closed)
Patch Set: Fix an Asan issue with LinkedHashSetNodeBase::unlink Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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 276 matching lines...) Expand 10 before | Expand all | Expand 10 after
287 while (m_position != m_endPosition && 287 while (m_position != m_endPosition &&
288 HashTableType::isEmptyOrDeletedBucket(*m_position)) 288 HashTableType::isEmptyOrDeletedBucket(*m_position))
289 ++m_position; 289 ++m_position;
290 } 290 }
291 291
292 HashTableConstIterator(PointerType position, 292 HashTableConstIterator(PointerType position,
293 PointerType endPosition, 293 PointerType endPosition,
294 const HashTableType* container) 294 const HashTableType* container)
295 : m_position(position), 295 : m_position(position),
296 m_endPosition(endPosition) 296 m_endPosition(endPosition)
297 #if ENABLE(ASSERT) 297 #if DCHECK_IS_ON()
298 , 298 ,
299 m_container(container), 299 m_container(container),
300 m_containerModifications(container->modifications()) 300 m_containerModifications(container->modifications())
301 #endif 301 #endif
302 { 302 {
303 skipEmptyBuckets(); 303 skipEmptyBuckets();
304 } 304 }
305 305
306 HashTableConstIterator(PointerType position, 306 HashTableConstIterator(PointerType position,
307 PointerType endPosition, 307 PointerType endPosition,
308 const HashTableType* container, 308 const HashTableType* container,
309 HashItemKnownGoodTag) 309 HashItemKnownGoodTag)
310 : m_position(position), 310 : m_position(position),
311 m_endPosition(endPosition) 311 m_endPosition(endPosition)
312 #if ENABLE(ASSERT) 312 #if DCHECK_IS_ON()
313 , 313 ,
314 m_container(container), 314 m_container(container),
315 m_containerModifications(container->modifications()) 315 m_containerModifications(container->modifications())
316 #endif 316 #endif
317 { 317 {
318 ASSERT(m_containerModifications == m_container->modifications()); 318 #if DCHECK_IS_ON()
319 DCHECK_EQ(m_containerModifications, m_container->modifications());
320 #endif
319 } 321 }
320 322
321 void checkModifications() const { 323 void checkModifications() const {
324 #if DCHECK_IS_ON()
322 // HashTable and collections that build on it do not support 325 // HashTable and collections that build on it do not support
323 // modifications while there is an iterator in use. The exception is 326 // modifications while there is an iterator in use. The exception is
324 // ListHashSet, which has its own iterators that tolerate modification 327 // ListHashSet, which has its own iterators that tolerate modification
325 // of the underlying set. 328 // of the underlying set.
326 ASSERT(m_containerModifications == m_container->modifications()); 329 DCHECK_EQ(m_containerModifications, m_container->modifications());
327 ASSERT(!m_container->accessForbidden()); 330 DCHECK(!m_container->accessForbidden());
331 #endif
328 } 332 }
329 333
330 public: 334 public:
331 HashTableConstIterator() {} 335 HashTableConstIterator() {}
332 336
333 GetType get() const { 337 GetType get() const {
334 checkModifications(); 338 checkModifications();
335 return m_position; 339 return m_position;
336 } 340 }
337 typename Traits::IteratorConstReferenceType operator*() const { 341 typename Traits::IteratorConstReferenceType operator*() const {
338 return Traits::getToReferenceConstConversion(get()); 342 return Traits::getToReferenceConstConversion(get());
339 } 343 }
340 GetType operator->() const { return get(); } 344 GetType operator->() const { return get(); }
341 345
342 const_iterator& operator++() { 346 const_iterator& operator++() {
343 ASSERT(m_position != m_endPosition); 347 DCHECK_NE(m_position, m_endPosition);
344 checkModifications(); 348 checkModifications();
345 ++m_position; 349 ++m_position;
346 skipEmptyBuckets(); 350 skipEmptyBuckets();
347 return *this; 351 return *this;
348 } 352 }
349 353
350 // postfix ++ intentionally omitted 354 // postfix ++ intentionally omitted
351 355
352 // Comparison. 356 // Comparison.
353 bool operator==(const const_iterator& other) const { 357 bool operator==(const const_iterator& other) const {
(...skipping 13 matching lines...) Expand all
367 if (m_position == m_endPosition) 371 if (m_position == m_endPosition)
368 return stream << "iterator representing <end>"; 372 return stream << "iterator representing <end>";
369 // TODO(tkent): Change |m_position| to |*m_position| to show the 373 // TODO(tkent): Change |m_position| to |*m_position| to show the
370 // pointed object. It requires a lot of new stream printer functions. 374 // pointed object. It requires a lot of new stream printer functions.
371 return stream << "iterator pointing to " << m_position; 375 return stream << "iterator pointing to " << m_position;
372 } 376 }
373 377
374 private: 378 private:
375 PointerType m_position; 379 PointerType m_position;
376 PointerType m_endPosition; 380 PointerType m_endPosition;
377 #if ENABLE(ASSERT) 381 #if DCHECK_IS_ON()
378 const HashTableType* m_container; 382 const HashTableType* m_container;
379 int64_t m_containerModifications; 383 int64_t m_containerModifications;
380 #endif 384 #endif
381 }; 385 };
382 386
383 template <typename Key, 387 template <typename Key,
384 typename Value, 388 typename Value,
385 typename Extractor, 389 typename Extractor,
386 typename Hash, 390 typename Hash,
387 typename Traits, 391 typename Traits,
(...skipping 285 matching lines...) Expand 10 before | Expand all | Expand 10 after
673 typedef Key KeyType; 677 typedef Key KeyType;
674 typedef typename KeyTraits::PeekInType KeyPeekInType; 678 typedef typename KeyTraits::PeekInType KeyPeekInType;
675 typedef Value ValueType; 679 typedef Value ValueType;
676 typedef Extractor ExtractorType; 680 typedef Extractor ExtractorType;
677 typedef KeyTraits KeyTraitsType; 681 typedef KeyTraits KeyTraitsType;
678 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; 682 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
679 typedef HashTableAddResult<HashTable, ValueType> AddResult; 683 typedef HashTableAddResult<HashTable, ValueType> AddResult;
680 684
681 HashTable(); 685 HashTable();
682 void finalize() { 686 void finalize() {
683 ASSERT(!Allocator::isGarbageCollected); 687 DCHECK(!Allocator::isGarbageCollected);
684 if (LIKELY(!m_table)) 688 if (LIKELY(!m_table))
685 return; 689 return;
686 ASSERT(!m_accessForbidden); 690 enterAccessForbiddenScope();
687 #if ENABLE(ASSERT)
688 m_accessForbidden = true;
689 #endif
690 deleteAllBucketsAndDeallocate(m_table, m_tableSize); 691 deleteAllBucketsAndDeallocate(m_table, m_tableSize);
691 #if ENABLE(ASSERT) 692 leaveAccessForbiddenScope();
692 m_accessForbidden = false;
693 #endif
694 m_table = nullptr; 693 m_table = nullptr;
695 } 694 }
696 695
697 HashTable(const HashTable&); 696 HashTable(const HashTable&);
698 HashTable(HashTable&&); 697 HashTable(HashTable&&);
699 void swap(HashTable&); 698 void swap(HashTable&);
700 HashTable& operator=(const HashTable&); 699 HashTable& operator=(const HashTable&);
701 HashTable& operator=(HashTable&&); 700 HashTable& operator=(HashTable&&);
702 701
703 // When the hash table is empty, just return the same iterator for end as 702 // When the hash table is empty, just return the same iterator for end as
704 // for begin. This is more efficient because we don't have to skip all the 703 // for begin. This is more efficient because we don't have to skip all the
705 // empty and deleted buckets, and iterating an empty table is a common case 704 // empty and deleted buckets, and iterating an empty table is a common case
706 // that's worth optimizing. 705 // that's worth optimizing.
707 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); } 706 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
708 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } 707 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
709 const_iterator begin() const { 708 const_iterator begin() const {
710 return isEmpty() ? end() : makeConstIterator(m_table); 709 return isEmpty() ? end() : makeConstIterator(m_table);
711 } 710 }
712 const_iterator end() const { 711 const_iterator end() const {
713 return makeKnownGoodConstIterator(m_table + m_tableSize); 712 return makeKnownGoodConstIterator(m_table + m_tableSize);
714 } 713 }
715 714
716 unsigned size() const { 715 unsigned size() const {
717 ASSERT(!m_accessForbidden); 716 DCHECK(!accessForbidden());
718 return m_keyCount; 717 return m_keyCount;
719 } 718 }
720 unsigned capacity() const { 719 unsigned capacity() const {
721 ASSERT(!m_accessForbidden); 720 DCHECK(!accessForbidden());
722 return m_tableSize; 721 return m_tableSize;
723 } 722 }
724 bool isEmpty() const { 723 bool isEmpty() const {
725 ASSERT(!m_accessForbidden); 724 DCHECK(!accessForbidden());
726 return !m_keyCount; 725 return !m_keyCount;
727 } 726 }
728 727
729 void reserveCapacityForSize(unsigned size); 728 void reserveCapacityForSize(unsigned size);
730 729
731 template <typename IncomingValueType> 730 template <typename IncomingValueType>
732 AddResult add(IncomingValueType&& value) { 731 AddResult add(IncomingValueType&& value) {
733 return add<IdentityTranslatorType>(Extractor::extract(value), 732 return add<IdentityTranslatorType>(Extractor::extract(value),
734 std::forward<IncomingValueType>(value)); 733 std::forward<IncomingValueType>(value));
735 } 734 }
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after
777 return lookup<IdentityTranslatorType, KeyPeekInType>(key); 776 return lookup<IdentityTranslatorType, KeyPeekInType>(key);
778 } 777 }
779 template <typename HashTranslator, typename T> 778 template <typename HashTranslator, typename T>
780 ValueType* lookup(const T&); 779 ValueType* lookup(const T&);
781 template <typename HashTranslator, typename T> 780 template <typename HashTranslator, typename T>
782 const ValueType* lookup(const T&) const; 781 const ValueType* lookup(const T&) const;
783 782
784 template <typename VisitorDispatcher> 783 template <typename VisitorDispatcher>
785 void trace(VisitorDispatcher); 784 void trace(VisitorDispatcher);
786 785
787 #if ENABLE(ASSERT) 786 #if DCHECK_IS_ON()
787 void enterAccessForbiddenScope() {
788 DCHECK(!m_accessForbidden);
789 m_accessForbidden = true;
790 }
791 void leaveAccessForbiddenScope() { m_accessForbidden = false; }
788 bool accessForbidden() const { return m_accessForbidden; } 792 bool accessForbidden() const { return m_accessForbidden; }
789 int64_t modifications() const { return m_modifications; } 793 int64_t modifications() const { return m_modifications; }
790 void registerModification() { m_modifications++; } 794 void registerModification() { m_modifications++; }
791 // HashTable and collections that build on it do not support modifications 795 // HashTable and collections that build on it do not support modifications
792 // while there is an iterator in use. The exception is ListHashSet, which 796 // while there is an iterator in use. The exception is ListHashSet, which
793 // has its own iterators that tolerate modification of the underlying set. 797 // has its own iterators that tolerate modification of the underlying set.
794 void checkModifications(int64_t mods) const { 798 void checkModifications(int64_t mods) const {
795 ASSERT(mods == m_modifications); 799 DCHECK_EQ(mods, m_modifications);
796 } 800 }
797 #else 801 #else
802 void enterAccessForbiddenScope() {}
803 void leaveAccessForbiddenScope() {}
804 bool accessForbidden() const { return false; }
798 int64_t modifications() const { return 0; } 805 int64_t modifications() const { return 0; }
799 void registerModification() {} 806 void registerModification() {}
800 void checkModifications(int64_t mods) const {} 807 void checkModifications(int64_t mods) const {}
801 #endif 808 #endif
802 809
803 private: 810 private:
804 static ValueType* allocateTable(unsigned size); 811 static ValueType* allocateTable(unsigned size);
805 static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size); 812 static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size);
806 813
807 typedef std::pair<ValueType*, bool> LookupType; 814 typedef std::pair<ValueType*, bool> LookupType;
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after
863 } 870 }
864 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { 871 const_iterator makeKnownGoodConstIterator(ValueType* pos) const {
865 return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); 872 return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood);
866 } 873 }
867 874
868 static const unsigned m_maxLoad = 2; 875 static const unsigned m_maxLoad = 2;
869 static const unsigned m_minLoad = 6; 876 static const unsigned m_minLoad = 6;
870 877
871 unsigned tableSizeMask() const { 878 unsigned tableSizeMask() const {
872 size_t mask = m_tableSize - 1; 879 size_t mask = m_tableSize - 1;
873 ASSERT((mask & m_tableSize) == 0); 880 DCHECK_EQ((mask & m_tableSize), 0u);
874 return mask; 881 return mask;
875 } 882 }
876 883
877 void setEnqueued() { m_queueFlag = true; } 884 void setEnqueued() { m_queueFlag = true; }
878 void clearEnqueued() { m_queueFlag = false; } 885 void clearEnqueued() { m_queueFlag = false; }
879 bool enqueued() { return m_queueFlag; } 886 bool enqueued() { return m_queueFlag; }
880 887
881 ValueType* m_table; 888 ValueType* m_table;
882 unsigned m_tableSize; 889 unsigned m_tableSize;
883 unsigned m_keyCount; 890 unsigned m_keyCount;
884 #if ENABLE(ASSERT) 891 #if DCHECK_IS_ON()
885 unsigned m_deletedCount : 30; 892 unsigned m_deletedCount : 30;
886 unsigned m_queueFlag : 1; 893 unsigned m_queueFlag : 1;
887 unsigned m_accessForbidden : 1; 894 unsigned m_accessForbidden : 1;
888 unsigned m_modifications; 895 unsigned m_modifications;
889 #else 896 #else
890 unsigned m_deletedCount : 31; 897 unsigned m_deletedCount : 31;
891 unsigned m_queueFlag : 1; 898 unsigned m_queueFlag : 1;
892 #endif 899 #endif
893 900
894 #if DUMP_HASHTABLE_STATS_PER_TABLE 901 #if DUMP_HASHTABLE_STATS_PER_TABLE
(...skipping 29 matching lines...) Expand all
924 Extractor, 931 Extractor,
925 HashFunctions, 932 HashFunctions,
926 Traits, 933 Traits,
927 KeyTraits, 934 KeyTraits,
928 Allocator>::HashTable() 935 Allocator>::HashTable()
929 : m_table(nullptr), 936 : m_table(nullptr),
930 m_tableSize(0), 937 m_tableSize(0),
931 m_keyCount(0), 938 m_keyCount(0),
932 m_deletedCount(0), 939 m_deletedCount(0),
933 m_queueFlag(false) 940 m_queueFlag(false)
934 #if ENABLE(ASSERT) 941 #if DCHECK_IS_ON()
935 , 942 ,
936 m_accessForbidden(false), 943 m_accessForbidden(false),
937 m_modifications(0) 944 m_modifications(0)
938 #endif 945 #endif
939 #if DUMP_HASHTABLE_STATS_PER_TABLE 946 #if DUMP_HASHTABLE_STATS_PER_TABLE
940 , 947 ,
941 m_stats(nullptr) 948 m_stats(nullptr)
942 #endif 949 #endif
943 { 950 {
944 static_assert(Allocator::isGarbageCollected || 951 static_assert(Allocator::isGarbageCollected ||
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after
1008 typename Value, 1015 typename Value,
1009 typename Extractor, 1016 typename Extractor,
1010 typename HashFunctions, 1017 typename HashFunctions,
1011 typename Traits, 1018 typename Traits,
1012 typename KeyTraits, 1019 typename KeyTraits,
1013 typename Allocator> 1020 typename Allocator>
1014 template <typename HashTranslator, typename T> 1021 template <typename HashTranslator, typename T>
1015 inline const Value* 1022 inline const Value*
1016 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1023 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1017 lookup(const T& key) const { 1024 lookup(const T& key) const {
1018 ASSERT(!m_accessForbidden); 1025 DCHECK(!accessForbidden());
1019 ASSERT((HashTableKeyChecker< 1026 DCHECK((HashTableKeyChecker<
1020 HashTranslator, KeyTraits, 1027 HashTranslator, KeyTraits,
1021 HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key))); 1028 HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key)));
1022 const ValueType* table = m_table; 1029 const ValueType* table = m_table;
1023 if (!table) 1030 if (!table)
1024 return nullptr; 1031 return nullptr;
1025 1032
1026 size_t k = 0; 1033 size_t k = 0;
1027 size_t sizeMask = tableSizeMask(); 1034 size_t sizeMask = tableSizeMask();
1028 unsigned h = HashTranslator::hash(key); 1035 unsigned h = HashTranslator::hash(key);
1029 size_t i = h & sizeMask; 1036 size_t i = h & sizeMask;
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
1064 template <typename HashTranslator, typename T> 1071 template <typename HashTranslator, typename T>
1065 inline typename HashTable<Key, 1072 inline typename HashTable<Key,
1066 Value, 1073 Value,
1067 Extractor, 1074 Extractor,
1068 HashFunctions, 1075 HashFunctions,
1069 Traits, 1076 Traits,
1070 KeyTraits, 1077 KeyTraits,
1071 Allocator>::LookupType 1078 Allocator>::LookupType
1072 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1079 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1073 lookupForWriting(const T& key) { 1080 lookupForWriting(const T& key) {
1074 ASSERT(!m_accessForbidden); 1081 DCHECK(!accessForbidden());
1075 ASSERT(m_table); 1082 DCHECK(m_table);
1076 registerModification(); 1083 registerModification();
1077 1084
1078 ValueType* table = m_table; 1085 ValueType* table = m_table;
1079 size_t k = 0; 1086 size_t k = 0;
1080 size_t sizeMask = tableSizeMask(); 1087 size_t sizeMask = tableSizeMask();
1081 unsigned h = HashTranslator::hash(key); 1088 unsigned h = HashTranslator::hash(key);
1082 size_t i = h & sizeMask; 1089 size_t i = h & sizeMask;
1083 1090
1084 UPDATE_ACCESS_COUNTS(); 1091 UPDATE_ACCESS_COUNTS();
1085 1092
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
1120 template <typename HashTranslator, typename T> 1127 template <typename HashTranslator, typename T>
1121 inline typename HashTable<Key, 1128 inline typename HashTable<Key,
1122 Value, 1129 Value,
1123 Extractor, 1130 Extractor,
1124 HashFunctions, 1131 HashFunctions,
1125 Traits, 1132 Traits,
1126 KeyTraits, 1133 KeyTraits,
1127 Allocator>::FullLookupType 1134 Allocator>::FullLookupType
1128 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1135 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1129 fullLookupForWriting(const T& key) { 1136 fullLookupForWriting(const T& key) {
1130 ASSERT(!m_accessForbidden); 1137 DCHECK(!accessForbidden());
1131 ASSERT(m_table); 1138 DCHECK(m_table);
1132 registerModification(); 1139 registerModification();
1133 1140
1134 ValueType* table = m_table; 1141 ValueType* table = m_table;
1135 size_t k = 0; 1142 size_t k = 0;
1136 size_t sizeMask = tableSizeMask(); 1143 size_t sizeMask = tableSizeMask();
1137 unsigned h = HashTranslator::hash(key); 1144 unsigned h = HashTranslator::hash(key);
1138 size_t i = h & sizeMask; 1145 size_t i = h & sizeMask;
1139 1146
1140 UPDATE_ACCESS_COUNTS(); 1147 UPDATE_ACCESS_COUNTS();
1141 1148
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after
1215 template <typename HashTranslator, typename T, typename Extra> 1222 template <typename HashTranslator, typename T, typename Extra>
1216 typename HashTable<Key, 1223 typename HashTable<Key,
1217 Value, 1224 Value,
1218 Extractor, 1225 Extractor,
1219 HashFunctions, 1226 HashFunctions,
1220 Traits, 1227 Traits,
1221 KeyTraits, 1228 KeyTraits,
1222 Allocator>::AddResult 1229 Allocator>::AddResult
1223 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1230 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1224 add(T&& key, Extra&& extra) { 1231 add(T&& key, Extra&& extra) {
1225 ASSERT(!m_accessForbidden); 1232 DCHECK(!accessForbidden());
1226 ASSERT(Allocator::isAllocationAllowed()); 1233 DCHECK(Allocator::isAllocationAllowed());
1227 if (!m_table) 1234 if (!m_table)
1228 expand(); 1235 expand();
1229 1236
1230 ASSERT(m_table); 1237 DCHECK(m_table);
1231 1238
1232 ValueType* table = m_table; 1239 ValueType* table = m_table;
1233 size_t k = 0; 1240 size_t k = 0;
1234 size_t sizeMask = tableSizeMask(); 1241 size_t sizeMask = tableSizeMask();
1235 unsigned h = HashTranslator::hash(key); 1242 unsigned h = HashTranslator::hash(key);
1236 size_t i = h & sizeMask; 1243 size_t i = h & sizeMask;
1237 1244
1238 UPDATE_ACCESS_COUNTS(); 1245 UPDATE_ACCESS_COUNTS();
1239 1246
1240 ValueType* deletedEntry = nullptr; 1247 ValueType* deletedEntry = nullptr;
(...skipping 27 matching lines...) Expand all
1268 if (deletedEntry) { 1275 if (deletedEntry) {
1269 // Overwrite any data left over from last use, using placement new or 1276 // Overwrite any data left over from last use, using placement new or
1270 // memset. 1277 // memset.
1271 initializeBucket(*deletedEntry); 1278 initializeBucket(*deletedEntry);
1272 entry = deletedEntry; 1279 entry = deletedEntry;
1273 --m_deletedCount; 1280 --m_deletedCount;
1274 } 1281 }
1275 1282
1276 HashTranslator::translate(*entry, std::forward<T>(key), 1283 HashTranslator::translate(*entry, std::forward<T>(key),
1277 std::forward<Extra>(extra)); 1284 std::forward<Extra>(extra));
1278 ASSERT(!isEmptyOrDeletedBucket(*entry)); 1285 DCHECK(!isEmptyOrDeletedBucket(*entry));
1279 1286
1280 ++m_keyCount; 1287 ++m_keyCount;
1281 1288
1282 if (shouldExpand()) { 1289 if (shouldExpand()) {
1283 entry = expand(entry); 1290 entry = expand(entry);
1284 } else if (Traits::weakHandlingFlag == WeakHandlingInCollections && 1291 } else if (Traits::weakHandlingFlag == WeakHandlingInCollections &&
1285 shouldShrink()) { 1292 shouldShrink()) {
1286 // When weak hash tables are processed by the garbage collector, 1293 // When weak hash tables are processed by the garbage collector,
1287 // elements with no other strong references to them will have their 1294 // elements with no other strong references to them will have their
1288 // table entries cleared. But no shrinking of the backing store is 1295 // table entries cleared. But no shrinking of the backing store is
(...skipping 22 matching lines...) Expand all
1311 template <typename HashTranslator, typename T, typename Extra> 1318 template <typename HashTranslator, typename T, typename Extra>
1312 typename HashTable<Key, 1319 typename HashTable<Key,
1313 Value, 1320 Value,
1314 Extractor, 1321 Extractor,
1315 HashFunctions, 1322 HashFunctions,
1316 Traits, 1323 Traits,
1317 KeyTraits, 1324 KeyTraits,
1318 Allocator>::AddResult 1325 Allocator>::AddResult
1319 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1326 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1320 addPassingHashCode(T&& key, Extra&& extra) { 1327 addPassingHashCode(T&& key, Extra&& extra) {
1321 ASSERT(!m_accessForbidden); 1328 DCHECK(!accessForbidden());
1322 ASSERT(Allocator::isAllocationAllowed()); 1329 DCHECK(Allocator::isAllocationAllowed());
1323 if (!m_table) 1330 if (!m_table)
1324 expand(); 1331 expand();
1325 1332
1326 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); 1333 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
1327 1334
1328 ValueType* entry = lookupResult.first.first; 1335 ValueType* entry = lookupResult.first.first;
1329 bool found = lookupResult.first.second; 1336 bool found = lookupResult.first.second;
1330 unsigned h = lookupResult.second; 1337 unsigned h = lookupResult.second;
1331 1338
1332 if (found) 1339 if (found)
1333 return AddResult(this, entry, false); 1340 return AddResult(this, entry, false);
1334 1341
1335 registerModification(); 1342 registerModification();
1336 1343
1337 if (isDeletedBucket(*entry)) { 1344 if (isDeletedBucket(*entry)) {
1338 initializeBucket(*entry); 1345 initializeBucket(*entry);
1339 --m_deletedCount; 1346 --m_deletedCount;
1340 } 1347 }
1341 1348
1342 HashTranslator::translate(*entry, std::forward<T>(key), 1349 HashTranslator::translate(*entry, std::forward<T>(key),
1343 std::forward<Extra>(extra), h); 1350 std::forward<Extra>(extra), h);
1344 ASSERT(!isEmptyOrDeletedBucket(*entry)); 1351 DCHECK(!isEmptyOrDeletedBucket(*entry));
1345 1352
1346 ++m_keyCount; 1353 ++m_keyCount;
1347 if (shouldExpand()) 1354 if (shouldExpand())
1348 entry = expand(entry); 1355 entry = expand(entry);
1349 1356
1350 return AddResult(this, entry, true); 1357 return AddResult(this, entry, true);
1351 } 1358 }
1352 1359
1353 template <typename Key, 1360 template <typename Key,
1354 typename Value, 1361 typename Value,
1355 typename Extractor, 1362 typename Extractor,
1356 typename HashFunctions, 1363 typename HashFunctions,
1357 typename Traits, 1364 typename Traits,
1358 typename KeyTraits, 1365 typename KeyTraits,
1359 typename Allocator> 1366 typename Allocator>
1360 Value* 1367 Value*
1361 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1368 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1362 reinsert(ValueType&& entry) { 1369 reinsert(ValueType&& entry) {
1363 ASSERT(m_table); 1370 DCHECK(m_table);
1364 registerModification(); 1371 registerModification();
1365 ASSERT(!lookupForWriting(Extractor::extract(entry)).second); 1372 DCHECK(!lookupForWriting(Extractor::extract(entry)).second);
1366 ASSERT( 1373 DCHECK(
1367 !isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); 1374 !isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
1368 #if DUMP_HASHTABLE_STATS 1375 #if DUMP_HASHTABLE_STATS
1369 atomicIncrement(&HashTableStats::instance().numReinserts); 1376 atomicIncrement(&HashTableStats::instance().numReinserts);
1370 #endif 1377 #endif
1371 #if DUMP_HASHTABLE_STATS_PER_TABLE 1378 #if DUMP_HASHTABLE_STATS_PER_TABLE
1372 ++m_stats->numReinserts; 1379 ++m_stats->numReinserts;
1373 #endif 1380 #endif
1374 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first; 1381 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
1375 Mover<ValueType, Allocator, 1382 Mover<ValueType, Allocator,
1376 Traits::template NeedsToForbidGCOnMove<>::value>::move(std::move(entry), 1383 Traits::template NeedsToForbidGCOnMove<>::value>::move(std::move(entry),
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after
1460 KeyTraits, 1467 KeyTraits,
1461 Allocator>::remove(ValueType* pos) { 1468 Allocator>::remove(ValueType* pos) {
1462 registerModification(); 1469 registerModification();
1463 #if DUMP_HASHTABLE_STATS 1470 #if DUMP_HASHTABLE_STATS
1464 atomicIncrement(&HashTableStats::instance().numRemoves); 1471 atomicIncrement(&HashTableStats::instance().numRemoves);
1465 #endif 1472 #endif
1466 #if DUMP_HASHTABLE_STATS_PER_TABLE 1473 #if DUMP_HASHTABLE_STATS_PER_TABLE
1467 ++m_stats->numRemoves; 1474 ++m_stats->numRemoves;
1468 #endif 1475 #endif
1469 1476
1470 ASSERT(!m_accessForbidden); 1477 enterAccessForbiddenScope();
1471 #if ENABLE(ASSERT)
1472 m_accessForbidden = true;
1473 #endif
1474 deleteBucket(*pos); 1478 deleteBucket(*pos);
1475 #if ENABLE(ASSERT) 1479 leaveAccessForbiddenScope();
1476 m_accessForbidden = false;
1477 #endif
1478 ++m_deletedCount; 1480 ++m_deletedCount;
1479 --m_keyCount; 1481 --m_keyCount;
1480 1482
1481 if (shouldShrink()) 1483 if (shouldShrink())
1482 shrink(); 1484 shrink();
1483 } 1485 }
1484 1486
1485 template <typename Key, 1487 template <typename Key,
1486 typename Value, 1488 typename Value,
1487 typename Extractor, 1489 typename Extractor,
(...skipping 142 matching lines...) Expand 10 before | Expand all | Expand 10 after
1630 typename Value, 1632 typename Value,
1631 typename Extractor, 1633 typename Extractor,
1632 typename HashFunctions, 1634 typename HashFunctions,
1633 typename Traits, 1635 typename Traits,
1634 typename KeyTraits, 1636 typename KeyTraits,
1635 typename Allocator> 1637 typename Allocator>
1636 Value* 1638 Value*
1637 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1639 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1638 expandBuffer(unsigned newTableSize, Value* entry, bool& success) { 1640 expandBuffer(unsigned newTableSize, Value* entry, bool& success) {
1639 success = false; 1641 success = false;
1640 ASSERT(m_tableSize < newTableSize); 1642 DCHECK_LT(m_tableSize, newTableSize);
1641 if (!Allocator::expandHashTableBacking(m_table, 1643 if (!Allocator::expandHashTableBacking(m_table,
1642 newTableSize * sizeof(ValueType))) 1644 newTableSize * sizeof(ValueType)))
1643 return nullptr; 1645 return nullptr;
1644 1646
1645 success = true; 1647 success = true;
1646 1648
1647 Value* newEntry = nullptr; 1649 Value* newEntry = nullptr;
1648 unsigned oldTableSize = m_tableSize; 1650 unsigned oldTableSize = m_tableSize;
1649 ValueType* originalTable = m_table; 1651 ValueType* originalTable = m_table;
1650 1652
1651 ValueType* temporaryTable = allocateTable(oldTableSize); 1653 ValueType* temporaryTable = allocateTable(oldTableSize);
1652 for (unsigned i = 0; i < oldTableSize; i++) { 1654 for (unsigned i = 0; i < oldTableSize; i++) {
1653 if (&m_table[i] == entry) 1655 if (&m_table[i] == entry)
1654 newEntry = &temporaryTable[i]; 1656 newEntry = &temporaryTable[i];
1655 if (isEmptyOrDeletedBucket(m_table[i])) { 1657 if (isEmptyOrDeletedBucket(m_table[i])) {
1656 ASSERT(&m_table[i] != entry); 1658 DCHECK_NE(&m_table[i], entry);
1657 if (Traits::emptyValueIsZero) { 1659 if (Traits::emptyValueIsZero) {
1658 memset(&temporaryTable[i], 0, sizeof(ValueType)); 1660 memset(&temporaryTable[i], 0, sizeof(ValueType));
1659 } else { 1661 } else {
1660 initializeBucket(temporaryTable[i]); 1662 initializeBucket(temporaryTable[i]);
1661 } 1663 }
1662 } else { 1664 } else {
1663 Mover<ValueType, Allocator, 1665 Mover<ValueType, Allocator,
1664 Traits::template NeedsToForbidGCOnMove<>::value>:: 1666 Traits::template NeedsToForbidGCOnMove<>::value>::
1665 move(std::move(m_table[i]), temporaryTable[i]); 1667 move(std::move(m_table[i]), temporaryTable[i]);
1666 } 1668 }
1667 } 1669 }
1668 m_table = temporaryTable; 1670 m_table = temporaryTable;
1669 1671
1670 if (Traits::emptyValueIsZero) { 1672 if (Traits::emptyValueIsZero) {
1671 memset(originalTable, 0, newTableSize * sizeof(ValueType)); 1673 memset(originalTable, 0, newTableSize * sizeof(ValueType));
1672 } else { 1674 } else {
1673 for (unsigned i = 0; i < newTableSize; i++) 1675 for (unsigned i = 0; i < newTableSize; i++)
1674 initializeBucket(originalTable[i]); 1676 initializeBucket(originalTable[i]);
1675 } 1677 }
1676 newEntry = rehashTo(originalTable, newTableSize, newEntry); 1678 newEntry = rehashTo(originalTable, newTableSize, newEntry);
1677 1679
1678 ASSERT(!m_accessForbidden); 1680 enterAccessForbiddenScope();
1679 #if ENABLE(ASSERT)
1680 m_accessForbidden = true;
1681 #endif
1682 deleteAllBucketsAndDeallocate(temporaryTable, oldTableSize); 1681 deleteAllBucketsAndDeallocate(temporaryTable, oldTableSize);
1683 #if ENABLE(ASSERT) 1682 leaveAccessForbiddenScope();
1684 m_accessForbidden = false;
1685 #endif
1686 1683
1687 return newEntry; 1684 return newEntry;
1688 } 1685 }
1689 1686
1690 template <typename Key, 1687 template <typename Key,
1691 typename Value, 1688 typename Value,
1692 typename Extractor, 1689 typename Extractor,
1693 typename HashFunctions, 1690 typename HashFunctions,
1694 typename Traits, 1691 typename Traits,
1695 typename KeyTraits, 1692 typename KeyTraits,
(...skipping 13 matching lines...) Expand all
1709 if (oldTableSize != 0) 1706 if (oldTableSize != 0)
1710 ++m_stats->numRehashes; 1707 ++m_stats->numRehashes;
1711 #endif 1708 #endif
1712 1709
1713 m_table = newTable; 1710 m_table = newTable;
1714 m_tableSize = newTableSize; 1711 m_tableSize = newTableSize;
1715 1712
1716 Value* newEntry = nullptr; 1713 Value* newEntry = nullptr;
1717 for (unsigned i = 0; i != oldTableSize; ++i) { 1714 for (unsigned i = 0; i != oldTableSize; ++i) {
1718 if (isEmptyOrDeletedBucket(oldTable[i])) { 1715 if (isEmptyOrDeletedBucket(oldTable[i])) {
1719 ASSERT(&oldTable[i] != entry); 1716 DCHECK_NE(&oldTable[i], entry);
1720 continue; 1717 continue;
1721 } 1718 }
1722 Value* reinsertedEntry = reinsert(std::move(oldTable[i])); 1719 Value* reinsertedEntry = reinsert(std::move(oldTable[i]));
1723 if (&oldTable[i] == entry) { 1720 if (&oldTable[i] == entry) {
1724 ASSERT(!newEntry); 1721 DCHECK(!newEntry);
1725 newEntry = reinsertedEntry; 1722 newEntry = reinsertedEntry;
1726 } 1723 }
1727 } 1724 }
1728 1725
1729 m_deletedCount = 0; 1726 m_deletedCount = 0;
1730 1727
1731 #if DUMP_HASHTABLE_STATS_PER_TABLE 1728 #if DUMP_HASHTABLE_STATS_PER_TABLE
1732 if (!m_stats) 1729 if (!m_stats)
1733 m_stats = HashTableStatsPtr<Allocator>::create(); 1730 m_stats = HashTableStatsPtr<Allocator>::create();
1734 #endif 1731 #endif
(...skipping 30 matching lines...) Expand all
1765 if (Allocator::isGarbageCollected && newTableSize > oldTableSize) { 1762 if (Allocator::isGarbageCollected && newTableSize > oldTableSize) {
1766 bool success; 1763 bool success;
1767 Value* newEntry = expandBuffer(newTableSize, entry, success); 1764 Value* newEntry = expandBuffer(newTableSize, entry, success);
1768 if (success) 1765 if (success)
1769 return newEntry; 1766 return newEntry;
1770 } 1767 }
1771 1768
1772 ValueType* newTable = allocateTable(newTableSize); 1769 ValueType* newTable = allocateTable(newTableSize);
1773 Value* newEntry = rehashTo(newTable, newTableSize, entry); 1770 Value* newEntry = rehashTo(newTable, newTableSize, entry);
1774 1771
1775 ASSERT(!m_accessForbidden); 1772 enterAccessForbiddenScope();
1776 #if ENABLE(ASSERT)
1777 m_accessForbidden = true;
1778 #endif
1779 deleteAllBucketsAndDeallocate(oldTable, oldTableSize); 1773 deleteAllBucketsAndDeallocate(oldTable, oldTableSize);
1780 #if ENABLE(ASSERT) 1774 leaveAccessForbiddenScope();
1781 m_accessForbidden = false;
1782 #endif
1783 1775
1784 return newEntry; 1776 return newEntry;
1785 } 1777 }
1786 1778
1787 template <typename Key, 1779 template <typename Key,
1788 typename Value, 1780 typename Value,
1789 typename Extractor, 1781 typename Extractor,
1790 typename HashFunctions, 1782 typename HashFunctions,
1791 typename Traits, 1783 typename Traits,
1792 typename KeyTraits, 1784 typename KeyTraits,
1793 typename Allocator> 1785 typename Allocator>
1794 void HashTable<Key, 1786 void HashTable<Key,
1795 Value, 1787 Value,
1796 Extractor, 1788 Extractor,
1797 HashFunctions, 1789 HashFunctions,
1798 Traits, 1790 Traits,
1799 KeyTraits, 1791 KeyTraits,
1800 Allocator>::clear() { 1792 Allocator>::clear() {
1801 registerModification(); 1793 registerModification();
1802 if (!m_table) 1794 if (!m_table)
1803 return; 1795 return;
1804 1796
1805 ASSERT(!m_accessForbidden); 1797 enterAccessForbiddenScope();
1806 #if ENABLE(ASSERT)
1807 m_accessForbidden = true;
1808 #endif
1809 deleteAllBucketsAndDeallocate(m_table, m_tableSize); 1798 deleteAllBucketsAndDeallocate(m_table, m_tableSize);
1810 #if ENABLE(ASSERT) 1799 leaveAccessForbiddenScope();
1811 m_accessForbidden = false;
1812 #endif
1813 m_table = nullptr; 1800 m_table = nullptr;
1814 m_tableSize = 0; 1801 m_tableSize = 0;
1815 m_keyCount = 0; 1802 m_keyCount = 0;
1816 } 1803 }
1817 1804
1818 template <typename Key, 1805 template <typename Key,
1819 typename Value, 1806 typename Value,
1820 typename Extractor, 1807 typename Extractor,
1821 typename HashFunctions, 1808 typename HashFunctions,
1822 typename Traits, 1809 typename Traits,
1823 typename KeyTraits, 1810 typename KeyTraits,
1824 typename Allocator> 1811 typename Allocator>
1825 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1812 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1826 HashTable(const HashTable& other) 1813 HashTable(const HashTable& other)
1827 : m_table(nullptr), 1814 : m_table(nullptr),
1828 m_tableSize(0), 1815 m_tableSize(0),
1829 m_keyCount(0), 1816 m_keyCount(0),
1830 m_deletedCount(0), 1817 m_deletedCount(0),
1831 m_queueFlag(false) 1818 m_queueFlag(false)
1832 #if ENABLE(ASSERT) 1819 #if DCHECK_IS_ON()
1833 , 1820 ,
1834 m_accessForbidden(false), 1821 m_accessForbidden(false),
1835 m_modifications(0) 1822 m_modifications(0)
1836 #endif 1823 #endif
1837 #if DUMP_HASHTABLE_STATS_PER_TABLE 1824 #if DUMP_HASHTABLE_STATS_PER_TABLE
1838 , 1825 ,
1839 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats)) 1826 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats))
1840 #endif 1827 #endif
1841 { 1828 {
1842 // Copy the hash table the dumb way, by adding each element to the new 1829 // Copy the hash table the dumb way, by adding each element to the new
(...skipping 11 matching lines...) Expand all
1854 typename Traits, 1841 typename Traits,
1855 typename KeyTraits, 1842 typename KeyTraits,
1856 typename Allocator> 1843 typename Allocator>
1857 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: 1844 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
1858 HashTable(HashTable&& other) 1845 HashTable(HashTable&& other)
1859 : m_table(nullptr), 1846 : m_table(nullptr),
1860 m_tableSize(0), 1847 m_tableSize(0),
1861 m_keyCount(0), 1848 m_keyCount(0),
1862 m_deletedCount(0), 1849 m_deletedCount(0),
1863 m_queueFlag(false) 1850 m_queueFlag(false)
1864 #if ENABLE(ASSERT) 1851 #if DCHECK_IS_ON()
1865 , 1852 ,
1866 m_accessForbidden(false), 1853 m_accessForbidden(false),
1867 m_modifications(0) 1854 m_modifications(0)
1868 #endif 1855 #endif
1869 #if DUMP_HASHTABLE_STATS_PER_TABLE 1856 #if DUMP_HASHTABLE_STATS_PER_TABLE
1870 , 1857 ,
1871 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats)) 1858 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats))
1872 #endif 1859 #endif
1873 { 1860 {
1874 swap(other); 1861 swap(other);
1875 } 1862 }
1876 1863
1877 template <typename Key, 1864 template <typename Key,
1878 typename Value, 1865 typename Value,
1879 typename Extractor, 1866 typename Extractor,
1880 typename HashFunctions, 1867 typename HashFunctions,
1881 typename Traits, 1868 typename Traits,
1882 typename KeyTraits, 1869 typename KeyTraits,
1883 typename Allocator> 1870 typename Allocator>
1884 void HashTable<Key, 1871 void HashTable<Key,
1885 Value, 1872 Value,
1886 Extractor, 1873 Extractor,
1887 HashFunctions, 1874 HashFunctions,
1888 Traits, 1875 Traits,
1889 KeyTraits, 1876 KeyTraits,
1890 Allocator>::swap(HashTable& other) { 1877 Allocator>::swap(HashTable& other) {
1891 ASSERT(!m_accessForbidden); 1878 DCHECK(!accessForbidden());
1892 std::swap(m_table, other.m_table); 1879 std::swap(m_table, other.m_table);
1893 std::swap(m_tableSize, other.m_tableSize); 1880 std::swap(m_tableSize, other.m_tableSize);
1894 std::swap(m_keyCount, other.m_keyCount); 1881 std::swap(m_keyCount, other.m_keyCount);
1895 // std::swap does not work for bit fields. 1882 // std::swap does not work for bit fields.
1896 unsigned deleted = m_deletedCount; 1883 unsigned deleted = m_deletedCount;
1897 m_deletedCount = other.m_deletedCount; 1884 m_deletedCount = other.m_deletedCount;
1898 other.m_deletedCount = deleted; 1885 other.m_deletedCount = deleted;
1899 ASSERT(!m_queueFlag); 1886 DCHECK(!m_queueFlag);
1900 ASSERT(!other.m_queueFlag); 1887 DCHECK(!other.m_queueFlag);
1901 1888
1902 #if ENABLE(ASSERT) 1889 #if DCHECK_IS_ON()
1903 std::swap(m_modifications, other.m_modifications); 1890 std::swap(m_modifications, other.m_modifications);
1904 #endif 1891 #endif
1905 1892
1906 #if DUMP_HASHTABLE_STATS_PER_TABLE 1893 #if DUMP_HASHTABLE_STATS_PER_TABLE
1907 HashTableStatsPtr<Allocator>::swap(m_stats, other.m_stats); 1894 HashTableStatsPtr<Allocator>::swap(m_stats, other.m_stats);
1908 #endif 1895 #endif
1909 } 1896 }
1910 1897
1911 template <typename Key, 1898 template <typename Key,
1912 typename Value, 1899 typename Value,
(...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after
2024 // because that would cause allocation during GC. 2011 // because that would cause allocation during GC.
2025 } 2012 }
2026 } 2013 }
2027 } 2014 }
2028 } 2015 }
2029 2016
2030 // Called repeatedly for tables that have both weak and strong pointers. 2017 // Called repeatedly for tables that have both weak and strong pointers.
2031 static void ephemeronIteration(typename Allocator::Visitor* visitor, 2018 static void ephemeronIteration(typename Allocator::Visitor* visitor,
2032 void* closure) { 2019 void* closure) {
2033 HashTableType* table = reinterpret_cast<HashTableType*>(closure); 2020 HashTableType* table = reinterpret_cast<HashTableType*>(closure);
2034 ASSERT(table->m_table); 2021 DCHECK(table->m_table);
2035 // Check the hash table for elements that we now know will not be 2022 // Check the hash table for elements that we now know will not be
2036 // removed by weak processing. Those elements need to have their strong 2023 // removed by weak processing. Those elements need to have their strong
2037 // pointers traced. 2024 // pointers traced.
2038 for (ValueType* element = table->m_table + table->m_tableSize - 1; 2025 for (ValueType* element = table->m_table + table->m_tableSize - 1;
2039 element >= table->m_table; element--) { 2026 element >= table->m_table; element--) {
2040 if (!HashTableType::isEmptyOrDeletedBucket(*element)) 2027 if (!HashTableType::isEmptyOrDeletedBucket(*element))
2041 TraceInCollectionTrait<WeakHandlingInCollections, WeakPointersActWeak, 2028 TraceInCollectionTrait<WeakHandlingInCollections, WeakPointersActWeak,
2042 ValueType, Traits>::trace(visitor, *element); 2029 ValueType, Traits>::trace(visitor, *element);
2043 } 2030 }
2044 } 2031 }
2045 2032
2046 // Called when the ephemeron iteration is done and before running the per 2033 // Called when the ephemeron iteration is done and before running the per
2047 // thread weak processing. It is guaranteed to be called before any thread 2034 // thread weak processing. It is guaranteed to be called before any thread
2048 // is resumed. 2035 // is resumed.
2049 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, 2036 static void ephemeronIterationDone(typename Allocator::Visitor* visitor,
2050 void* closure) { 2037 void* closure) {
2051 HashTableType* table = reinterpret_cast<HashTableType*>(closure); 2038 HashTableType* table = reinterpret_cast<HashTableType*>(closure);
2052 ASSERT(Allocator::weakTableRegistered(visitor, table)); 2039 #if DCHECK_IS_ON()
2040 DCHECK(Allocator::weakTableRegistered(visitor, table));
2041 #endif
2053 table->clearEnqueued(); 2042 table->clearEnqueued();
2054 } 2043 }
2055 }; 2044 };
2056 2045
2057 template <typename Key, 2046 template <typename Key,
2058 typename Value, 2047 typename Value,
2059 typename Extractor, 2048 typename Extractor,
2060 typename HashFunctions, 2049 typename HashFunctions,
2061 typename Traits, 2050 typename Traits,
2062 typename KeyTraits, 2051 typename KeyTraits,
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after
2111 // by the visitor. 2100 // by the visitor.
2112 Allocator::registerBackingStoreReference(visitor, &m_table); 2101 Allocator::registerBackingStoreReference(visitor, &m_table);
2113 if (!IsTraceableInCollectionTrait<Traits>::value) 2102 if (!IsTraceableInCollectionTrait<Traits>::value)
2114 return; 2103 return;
2115 if (Traits::weakHandlingFlag == WeakHandlingInCollections) { 2104 if (Traits::weakHandlingFlag == WeakHandlingInCollections) {
2116 // If we have both strong and weak pointers in the collection then 2105 // If we have both strong and weak pointers in the collection then
2117 // we queue up the collection for fixed point iteration a la 2106 // we queue up the collection for fixed point iteration a la
2118 // Ephemerons: 2107 // Ephemerons:
2119 // http://dl.acm.org/citation.cfm?doid=263698.263733 - see also 2108 // http://dl.acm.org/citation.cfm?doid=263698.263733 - see also
2120 // http://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak 2109 // http://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak
2121 ASSERT(!enqueued() || Allocator::weakTableRegistered(visitor, this)); 2110 #if DCHECK_IS_ON()
2111 DCHECK(!enqueued() || Allocator::weakTableRegistered(visitor, this));
2112 #endif
2122 if (!enqueued()) { 2113 if (!enqueued()) {
2123 Allocator::registerWeakTable( 2114 Allocator::registerWeakTable(
2124 visitor, this, 2115 visitor, this,
2125 WeakProcessingHashTableHelper< 2116 WeakProcessingHashTableHelper<
2126 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, 2117 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions,
2127 Traits, KeyTraits, Allocator>::ephemeronIteration, 2118 Traits, KeyTraits, Allocator>::ephemeronIteration,
2128 WeakProcessingHashTableHelper< 2119 WeakProcessingHashTableHelper<
2129 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, 2120 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions,
2130 Traits, KeyTraits, Allocator>::ephemeronIterationDone); 2121 Traits, KeyTraits, Allocator>::ephemeronIterationDone);
2131 setEnqueued(); 2122 setEnqueued();
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after
2278 CollectionIterator end(toBeRemoved.end()); 2269 CollectionIterator end(toBeRemoved.end());
2279 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) 2270 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
2280 collection.remove(*it); 2271 collection.remove(*it);
2281 } 2272 }
2282 2273
2283 } // namespace WTF 2274 } // namespace WTF
2284 2275
2285 #include "wtf/HashIterators.h" 2276 #include "wtf/HashIterators.h"
2286 2277
2287 #endif // WTF_HashTable_h 2278 #endif // WTF_HashTable_h
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/wtf/HashMapTest.cpp ('k') | third_party/WebKit/Source/wtf/HexNumber.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698