| 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 |