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 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 |
OLD | NEW |