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

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

Issue 394353002: Replace tests of ASSERT_ENABLED with ENABLE(ASSERT). (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 6 years, 5 months 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 | Annotate | Revision Log
OLDNEW
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 106 matching lines...) Expand 10 before | Expand all | Expand 10 after
117 117
118 void skipEmptyBuckets() 118 void skipEmptyBuckets()
119 { 119 {
120 while (m_position != m_endPosition && HashTableType::isEmptyOrDelete dBucket(*m_position)) 120 while (m_position != m_endPosition && HashTableType::isEmptyOrDelete dBucket(*m_position))
121 ++m_position; 121 ++m_position;
122 } 122 }
123 123
124 HashTableConstIterator(PointerType position, PointerType endPosition, co nst HashTableType* container) 124 HashTableConstIterator(PointerType position, PointerType endPosition, co nst HashTableType* container)
125 : m_position(position) 125 : m_position(position)
126 , m_endPosition(endPosition) 126 , m_endPosition(endPosition)
127 #if ASSERT_ENABLED 127 #if ENABLE(ASSERT)
128 , m_container(container) 128 , m_container(container)
129 , m_containerModifications(container->modifications()) 129 , m_containerModifications(container->modifications())
130 #endif 130 #endif
131 { 131 {
132 skipEmptyBuckets(); 132 skipEmptyBuckets();
133 } 133 }
134 134
135 HashTableConstIterator(PointerType position, PointerType endPosition, co nst HashTableType* container, HashItemKnownGoodTag) 135 HashTableConstIterator(PointerType position, PointerType endPosition, co nst HashTableType* container, HashItemKnownGoodTag)
136 : m_position(position) 136 : m_position(position)
137 , m_endPosition(endPosition) 137 , m_endPosition(endPosition)
138 #if ASSERT_ENABLED 138 #if ENABLE(ASSERT)
139 , m_container(container) 139 , m_container(container)
140 , m_containerModifications(container->modifications()) 140 , m_containerModifications(container->modifications())
141 #endif 141 #endif
142 { 142 {
143 ASSERT(m_containerModifications == m_container->modifications()); 143 ASSERT(m_containerModifications == m_container->modifications());
144 } 144 }
145 145
146 void checkModifications() const 146 void checkModifications() const
147 { 147 {
148 // HashTable and collections that build on it do not support 148 // HashTable and collections that build on it do not support
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after
190 return *this == static_cast<const_iterator>(other); 190 return *this == static_cast<const_iterator>(other);
191 } 191 }
192 bool operator!=(const iterator& other) const 192 bool operator!=(const iterator& other) const
193 { 193 {
194 return *this != static_cast<const_iterator>(other); 194 return *this != static_cast<const_iterator>(other);
195 } 195 }
196 196
197 private: 197 private:
198 PointerType m_position; 198 PointerType m_position;
199 PointerType m_endPosition; 199 PointerType m_endPosition;
200 #if ASSERT_ENABLED 200 #if ENABLE(ASSERT)
201 const HashTableType* m_container; 201 const HashTableType* m_container;
202 int64_t m_containerModifications; 202 int64_t m_containerModifications;
203 #endif 203 #endif
204 }; 204 };
205 205
206 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator> 206 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator>
207 class HashTableIterator { 207 class HashTableIterator {
208 private: 208 private:
209 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait s, Allocator> HashTableType; 209 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait s, Allocator> HashTableType;
210 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator; 210 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after
265 public: 265 public:
266 template<typename T> static unsigned hash(const T& key) { return HashFun ctions::hash(key); } 266 template<typename T> static unsigned hash(const T& key) { return HashFun ctions::hash(key); }
267 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } 267 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
268 template<typename T, typename U, typename V> static void translate(T& lo cation, const U&, const V& value) { location = value; } 268 template<typename T, typename U, typename V> static void translate(T& lo cation, const U&, const V& value) { location = value; }
269 }; 269 };
270 270
271 template<typename HashTableType, typename ValueType> struct HashTableAddResu lt { 271 template<typename HashTableType, typename ValueType> struct HashTableAddResu lt {
272 HashTableAddResult(const HashTableType* container, ValueType* storedValu e, bool isNewEntry) 272 HashTableAddResult(const HashTableType* container, ValueType* storedValu e, bool isNewEntry)
273 : storedValue(storedValue) 273 : storedValue(storedValue)
274 , isNewEntry(isNewEntry) 274 , isNewEntry(isNewEntry)
275 #if SECURITY_ASSERT_ENABLED 275 #if ENABLE(SECURITY_ASSERT)
276 , m_container(container) 276 , m_container(container)
277 , m_containerModifications(container->modifications()) 277 , m_containerModifications(container->modifications())
278 #endif 278 #endif
279 { 279 {
280 ASSERT_UNUSED(container, container); 280 ASSERT_UNUSED(container, container);
281 } 281 }
282 282
283 ~HashTableAddResult() 283 ~HashTableAddResult()
284 { 284 {
285 // If rehash happened before accessing storedValue, it's 285 // If rehash happened before accessing storedValue, it's
286 // use-after-free. Any modification may cause a rehash, so we check 286 // use-after-free. Any modification may cause a rehash, so we check
287 // for modifications here. 287 // for modifications here.
288 // Rehash after accessing storedValue is harmless but will assert if 288 // Rehash after accessing storedValue is harmless but will assert if
289 // the AddResult destructor takes place after a modification. You 289 // the AddResult destructor takes place after a modification. You
290 // may need to limit the scope of the AddResult. 290 // may need to limit the scope of the AddResult.
291 ASSERT_WITH_SECURITY_IMPLICATION(m_containerModifications == m_conta iner->modifications()); 291 ASSERT_WITH_SECURITY_IMPLICATION(m_containerModifications == m_conta iner->modifications());
292 } 292 }
293 293
294 ValueType* storedValue; 294 ValueType* storedValue;
295 bool isNewEntry; 295 bool isNewEntry;
296 296
297 #if SECURITY_ASSERT_ENABLED 297 #if ENABLE(SECURITY_ASSERT)
298 private: 298 private:
299 const HashTableType* m_container; 299 const HashTableType* m_container;
300 const int64_t m_containerModifications; 300 const int64_t m_containerModifications;
301 #endif 301 #endif
302 }; 302 };
303 303
304 template<typename Value, typename Extractor, typename KeyTraits> 304 template<typename Value, typename Extractor, typename KeyTraits>
305 struct HashTableHelper { 305 struct HashTableHelper {
306 static bool isEmptyBucket(const Value& value) { return isHashTraitsEmpty Value<KeyTraits>(Extractor::extract(value)); } 306 static bool isEmptyBucket(const Value& value) { return isHashTraitsEmpty Value<KeyTraits>(Extractor::extract(value)); }
307 static bool isDeletedBucket(const Value& value) { return KeyTraits::isDe letedValue(Extractor::extract(value)); } 307 static bool isDeletedBucket(const Value& value) { return KeyTraits::isDe letedValue(Extractor::extract(value)); }
(...skipping 147 matching lines...) Expand 10 before | Expand all | Expand 10 after
455 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsE mptyValue<KeyTraits>(Extractor::extract(value)); } 455 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsE mptyValue<KeyTraits>(Extractor::extract(value)); }
456 static bool isDeletedBucket(const ValueType& value) { return KeyTraits:: isDeletedValue(Extractor::extract(value)); } 456 static bool isDeletedBucket(const ValueType& value) { return KeyTraits:: isDeletedValue(Extractor::extract(value)); }
457 static bool isEmptyOrDeletedBucket(const ValueType& value) { return Hash TableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); } 457 static bool isEmptyOrDeletedBucket(const ValueType& value) { return Hash TableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
458 458
459 ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorT ype, KeyPeekInType>(key); } 459 ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorT ype, KeyPeekInType>(key); }
460 template<typename HashTranslator, typename T> ValueType* lookup(T); 460 template<typename HashTranslator, typename T> ValueType* lookup(T);
461 template<typename HashTranslator, typename T> const ValueType* lookup(T) const; 461 template<typename HashTranslator, typename T> const ValueType* lookup(T) const;
462 462
463 void trace(typename Allocator::Visitor*); 463 void trace(typename Allocator::Visitor*);
464 464
465 #if ASSERT_ENABLED 465 #if ENABLE(ASSERT)
466 int64_t modifications() const { return m_modifications; } 466 int64_t modifications() const { return m_modifications; }
467 void registerModification() { m_modifications++; } 467 void registerModification() { m_modifications++; }
468 // HashTable and collections that build on it do not support 468 // HashTable and collections that build on it do not support
469 // modifications while there is an iterator in use. The exception is 469 // modifications while there is an iterator in use. The exception is
470 // ListHashSet, which has its own iterators that tolerate modification 470 // ListHashSet, which has its own iterators that tolerate modification
471 // of the underlying set. 471 // of the underlying set.
472 void checkModifications(int64_t mods) const { ASSERT(mods == m_modificat ions); } 472 void checkModifications(int64_t mods) const { ASSERT(mods == m_modificat ions); }
473 #else 473 #else
474 int64_t modifications() const { return 0; } 474 int64_t modifications() const { return 0; }
475 void registerModification() { } 475 void registerModification() { }
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
521 521
522 void setEnqueued() { m_queueFlag = true; } 522 void setEnqueued() { m_queueFlag = true; }
523 void clearEnqueued() { m_queueFlag = false; } 523 void clearEnqueued() { m_queueFlag = false; }
524 bool enqueued() { return m_queueFlag; } 524 bool enqueued() { return m_queueFlag; }
525 525
526 ValueType* m_table; 526 ValueType* m_table;
527 unsigned m_tableSize; 527 unsigned m_tableSize;
528 unsigned m_keyCount; 528 unsigned m_keyCount;
529 unsigned m_deletedCount:31; 529 unsigned m_deletedCount:31;
530 bool m_queueFlag:1; 530 bool m_queueFlag:1;
531 #if ASSERT_ENABLED 531 #if ENABLE(ASSERT)
532 unsigned m_modifications; 532 unsigned m_modifications;
533 #endif 533 #endif
534 534
535 #if DUMP_HASHTABLE_STATS_PER_TABLE 535 #if DUMP_HASHTABLE_STATS_PER_TABLE
536 public: 536 public:
537 mutable OwnPtr<Stats> m_stats; 537 mutable OwnPtr<Stats> m_stats;
538 #endif 538 #endif
539 539
540 template<WeakHandlingFlag x, typename T, typename U, typename V, typenam e W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHe lper; 540 template<WeakHandlingFlag x, typename T, typename U, typename V, typenam e W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHe lper;
541 template<typename T, typename U, typename V, typename W> friend class Li nkedHashSet; 541 template<typename T, typename U, typename V, typename W> friend class Li nkedHashSet;
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after
579 COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize); 579 COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
580 }; 580 };
581 581
582 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator> 582 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator>
583 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Al locator>::HashTable() 583 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Al locator>::HashTable()
584 : m_table(0) 584 : m_table(0)
585 , m_tableSize(0) 585 , m_tableSize(0)
586 , m_keyCount(0) 586 , m_keyCount(0)
587 , m_deletedCount(0) 587 , m_deletedCount(0)
588 , m_queueFlag(false) 588 , m_queueFlag(false)
589 #if ASSERT_ENABLED 589 #if ENABLE(ASSERT)
590 , m_modifications(0) 590 , m_modifications(0)
591 #endif 591 #endif
592 #if DUMP_HASHTABLE_STATS_PER_TABLE 592 #if DUMP_HASHTABLE_STATS_PER_TABLE
593 , m_stats(adoptPtr(new Stats)) 593 , m_stats(adoptPtr(new Stats))
594 #endif 594 #endif
595 { 595 {
596 } 596 }
597 597
598 inline unsigned doubleHash(unsigned key) 598 inline unsigned doubleHash(unsigned key)
599 { 599 {
(...skipping 458 matching lines...) Expand 10 before | Expand all | Expand 10 after
1058 m_keyCount = 0; 1058 m_keyCount = 0;
1059 } 1059 }
1060 1060
1061 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator> 1061 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator>
1062 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator >::HashTable(const HashTable& other) 1062 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator >::HashTable(const HashTable& other)
1063 : m_table(0) 1063 : m_table(0)
1064 , m_tableSize(0) 1064 , m_tableSize(0)
1065 , m_keyCount(0) 1065 , m_keyCount(0)
1066 , m_deletedCount(0) 1066 , m_deletedCount(0)
1067 , m_queueFlag(false) 1067 , m_queueFlag(false)
1068 #if ASSERT_ENABLED 1068 #if ENABLE(ASSERT)
1069 , m_modifications(0) 1069 , m_modifications(0)
1070 #endif 1070 #endif
1071 #if DUMP_HASHTABLE_STATS_PER_TABLE 1071 #if DUMP_HASHTABLE_STATS_PER_TABLE
1072 , m_stats(adoptPtr(new Stats(*other.m_stats))) 1072 , m_stats(adoptPtr(new Stats(*other.m_stats)))
1073 #endif 1073 #endif
1074 { 1074 {
1075 // Copy the hash table the dumb way, by adding each element to the new t able. 1075 // Copy the hash table the dumb way, by adding each element to the new t able.
1076 // It might be more efficient to copy the table slots, but it's not clea r that efficiency is needed. 1076 // It might be more efficient to copy the table slots, but it's not clea r that efficiency is needed.
1077 const_iterator end = other.end(); 1077 const_iterator end = other.end();
1078 for (const_iterator it = other.begin(); it != end; ++it) 1078 for (const_iterator it = other.begin(); it != end; ++it)
1079 add(*it); 1079 add(*it);
1080 } 1080 }
1081 1081
1082 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator> 1082 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator>
1083 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo cator>::swap(HashTable& other) 1083 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allo cator>::swap(HashTable& other)
1084 { 1084 {
1085 std::swap(m_table, other.m_table); 1085 std::swap(m_table, other.m_table);
1086 std::swap(m_tableSize, other.m_tableSize); 1086 std::swap(m_tableSize, other.m_tableSize);
1087 std::swap(m_keyCount, other.m_keyCount); 1087 std::swap(m_keyCount, other.m_keyCount);
1088 // std::swap does not work for bit fields. 1088 // std::swap does not work for bit fields.
1089 unsigned deleted = m_deletedCount; 1089 unsigned deleted = m_deletedCount;
1090 m_deletedCount = other.m_deletedCount; 1090 m_deletedCount = other.m_deletedCount;
1091 other.m_deletedCount = deleted; 1091 other.m_deletedCount = deleted;
1092 ASSERT(!m_queueFlag); 1092 ASSERT(!m_queueFlag);
1093 ASSERT(!other.m_queueFlag); 1093 ASSERT(!other.m_queueFlag);
1094 1094
1095 #if ASSERT_ENABLED 1095 #if ENABLE(ASSERT)
1096 std::swap(m_modifications, other.m_modifications); 1096 std::swap(m_modifications, other.m_modifications);
1097 #endif 1097 #endif
1098 1098
1099 #if DUMP_HASHTABLE_STATS_PER_TABLE 1099 #if DUMP_HASHTABLE_STATS_PER_TABLE
1100 m_stats.swap(other.m_stats); 1100 m_stats.swap(other.m_stats);
1101 #endif 1101 #endif
1102 } 1102 }
1103 1103
1104 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator> 1104 template<typename Key, typename Value, typename Extractor, typename HashFunc tions, typename Traits, typename KeyTraits, typename Allocator>
1105 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator >& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> ::operator=(const HashTable& other) 1105 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator >& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> ::operator=(const HashTable& other)
(...skipping 228 matching lines...) Expand 10 before | Expand all | Expand 10 after
1334 CollectionIterator end(toBeRemoved.end()); 1334 CollectionIterator end(toBeRemoved.end());
1335 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) 1335 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
1336 collection.remove(*it); 1336 collection.remove(*it);
1337 } 1337 }
1338 1338
1339 } // namespace WTF 1339 } // namespace WTF
1340 1340
1341 #include "wtf/HashIterators.h" 1341 #include "wtf/HashIterators.h"
1342 1342
1343 #endif // WTF_HashTable_h 1343 #endif // WTF_HashTable_h
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698