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 187 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
198 template<typename T> struct Mover<T, true> { static void move(T& from, T& to
) { hashTableSwap(from, to); } }; | 198 template<typename T> struct Mover<T, true> { static void move(T& from, T& to
) { hashTableSwap(from, to); } }; |
199 template<typename T> struct Mover<T, false> { static void move(T& from, T& t
o) { to = from; } }; | 199 template<typename T> struct Mover<T, false> { static void move(T& from, T& t
o) { to = from; } }; |
200 | 200 |
201 template<typename HashFunctions> class IdentityHashTranslator { | 201 template<typename HashFunctions> class IdentityHashTranslator { |
202 public: | 202 public: |
203 template<typename T> static unsigned hash(const T& key) { return HashFun
ctions::hash(key); } | 203 template<typename T> static unsigned hash(const T& key) { return HashFun
ctions::hash(key); } |
204 template<typename T, typename U> static bool equal(const T& a, const U&
b) { return HashFunctions::equal(a, b); } | 204 template<typename T, typename U> static bool equal(const T& a, const U&
b) { return HashFunctions::equal(a, b); } |
205 template<typename T, typename U, typename V> static void translate(T& lo
cation, const U&, const V& value) { location = value; } | 205 template<typename T, typename U, typename V> static void translate(T& lo
cation, const U&, const V& value) { location = value; } |
206 }; | 206 }; |
207 | 207 |
208 template<typename IteratorType> struct HashTableAddResult { | 208 template<typename ValueType> struct HashTableAddResult { |
209 HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter),
isNewEntry(isNewEntry) { } | 209 HashTableAddResult(ValueType* storedValue, bool isNewEntry) : storedValu
e(storedValue), isNewEntry(isNewEntry) { } |
210 IteratorType iterator; | 210 ValueType* storedValue; |
211 bool isNewEntry; | 211 bool isNewEntry; |
212 }; | 212 }; |
213 | 213 |
214 template<typename Value, typename Extractor, typename KeyTraits> | 214 template<typename Value, typename Extractor, typename KeyTraits> |
215 struct HashTableHelper { | 215 struct HashTableHelper { |
216 static bool isEmptyBucket(const Value& value) { return isHashTraitsEmpty
Value<KeyTraits>(Extractor::extract(value)); } | 216 static bool isEmptyBucket(const Value& value) { return isHashTraitsEmpty
Value<KeyTraits>(Extractor::extract(value)); } |
217 static bool isDeletedBucket(const Value& value) { return KeyTraits::isDe
letedValue(Extractor::extract(value)); } | 217 static bool isDeletedBucket(const Value& value) { return KeyTraits::isDe
letedValue(Extractor::extract(value)); } |
218 static bool isEmptyOrDeletedBucket(const Value& value) { return isEmptyB
ucket(value) || isDeletedBucket(value); } | 218 static bool isEmptyOrDeletedBucket(const Value& value) { return isEmptyB
ucket(value) || isDeletedBucket(value); } |
219 }; | 219 }; |
220 | 220 |
221 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 221 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
222 class HashTable { | 222 class HashTable { |
223 public: | 223 public: |
224 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits,
KeyTraits, Allocator> iterator; | 224 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits,
KeyTraits, Allocator> iterator; |
225 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator> const_iterator; | 225 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator> const_iterator; |
226 typedef Traits ValueTraits; | 226 typedef Traits ValueTraits; |
227 typedef Key KeyType; | 227 typedef Key KeyType; |
228 typedef typename KeyTraits::PeekInType KeyPeekInType; | 228 typedef typename KeyTraits::PeekInType KeyPeekInType; |
229 typedef typename KeyTraits::PassInType KeyPassInType; | 229 typedef typename KeyTraits::PassInType KeyPassInType; |
230 typedef Value ValueType; | 230 typedef Value ValueType; |
231 typedef typename Traits::PeekInType ValuePeekInType; | 231 typedef typename Traits::PeekInType ValuePeekInType; |
232 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; | 232 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; |
233 typedef HashTableAddResult<iterator> AddResult; | 233 typedef HashTableAddResult<ValueType> AddResult; |
234 | 234 |
235 #if DUMP_HASHTABLE_STATS_PER_TABLE | 235 #if DUMP_HASHTABLE_STATS_PER_TABLE |
236 struct Stats { | 236 struct Stats { |
237 Stats() | 237 Stats() |
238 : numAccesses(0) | 238 : numAccesses(0) |
239 , numRehashes(0) | 239 , numRehashes(0) |
240 , numRemoves(0) | 240 , numRemoves(0) |
241 , numReinserts(0) | 241 , numReinserts(0) |
242 , maxCollisions(0) | 242 , maxCollisions(0) |
243 , numCollisions(0) | 243 , numCollisions(0) |
(...skipping 436 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
680 ValueType* entry; | 680 ValueType* entry; |
681 while (1) { | 681 while (1) { |
682 entry = table + i; | 682 entry = table + i; |
683 | 683 |
684 // we count on the compiler to optimize out this branch | 684 // we count on the compiler to optimize out this branch |
685 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 685 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
686 if (isEmptyBucket(*entry)) | 686 if (isEmptyBucket(*entry)) |
687 break; | 687 break; |
688 | 688 |
689 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 689 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
690 return AddResult(makeKnownGoodIterator(entry), false); | 690 return AddResult(entry, false); |
691 | 691 |
692 if (isDeletedBucket(*entry)) | 692 if (isDeletedBucket(*entry)) |
693 deletedEntry = entry; | 693 deletedEntry = entry; |
694 } else { | 694 } else { |
695 if (isEmptyBucket(*entry)) | 695 if (isEmptyBucket(*entry)) |
696 break; | 696 break; |
697 | 697 |
698 if (isDeletedBucket(*entry)) | 698 if (isDeletedBucket(*entry)) |
699 deletedEntry = entry; | 699 deletedEntry = entry; |
700 else if (HashTranslator::equal(Extractor::extract(*entry), key)) | 700 else if (HashTranslator::equal(Extractor::extract(*entry), key)) |
701 return AddResult(makeKnownGoodIterator(entry), false); | 701 return AddResult(entry, false); |
702 } | 702 } |
703 #if DUMP_HASHTABLE_STATS | 703 #if DUMP_HASHTABLE_STATS |
704 ++probeCount; | 704 ++probeCount; |
705 HashTableStats::recordCollisionAtCount(probeCount); | 705 HashTableStats::recordCollisionAtCount(probeCount); |
706 #endif | 706 #endif |
707 | 707 |
708 #if DUMP_HASHTABLE_STATS_PER_TABLE | 708 #if DUMP_HASHTABLE_STATS_PER_TABLE |
709 ++perTableProbeCount; | 709 ++perTableProbeCount; |
710 m_stats->recordCollisionAtCount(perTableProbeCount); | 710 m_stats->recordCollisionAtCount(perTableProbeCount); |
711 #endif | 711 #endif |
(...skipping 12 matching lines...) Expand all Loading... |
724 HashTranslator::translate(*entry, key, extra); | 724 HashTranslator::translate(*entry, key, extra); |
725 | 725 |
726 ++m_keyCount; | 726 ++m_keyCount; |
727 | 727 |
728 if (shouldExpand()) { | 728 if (shouldExpand()) { |
729 // FIXME: This makes an extra copy on expand. Probably not that bad
since | 729 // FIXME: This makes an extra copy on expand. Probably not that bad
since |
730 // expand is rare, but would be better to have a version of expand t
hat can | 730 // expand is rare, but would be better to have a version of expand t
hat can |
731 // follow a pivot entry and return the new position. | 731 // follow a pivot entry and return the new position. |
732 typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extr
actor::extract(*entry); | 732 typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extr
actor::extract(*entry); |
733 expand(); | 733 expand(); |
734 AddResult result(find(enteredKey), true); | 734 iterator findResult = find(enteredKey); |
735 ASSERT(result.iterator != end()); | 735 ASSERT(findResult != end()); |
| 736 ValueType* resultValue = findResult.get(); |
| 737 AddResult result(resultValue, true); |
736 return result; | 738 return result; |
737 } | 739 } |
738 | 740 |
739 return AddResult(makeKnownGoodIterator(entry), true); | 741 return AddResult(entry, true); |
740 } | 742 } |
741 | 743 |
742 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 744 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
743 template<typename HashTranslator, typename T, typename Extra> | 745 template<typename HashTranslator, typename T, typename Extra> |
744 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, Ke
yTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra) | 746 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits,
Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, Ke
yTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra) |
745 { | 747 { |
746 if (!m_table) | 748 if (!m_table) |
747 expand(); | 749 expand(); |
748 | 750 |
749 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); | 751 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); |
750 | 752 |
751 ValueType* entry = lookupResult.first.first; | 753 ValueType* entry = lookupResult.first.first; |
752 bool found = lookupResult.first.second; | 754 bool found = lookupResult.first.second; |
753 unsigned h = lookupResult.second; | 755 unsigned h = lookupResult.second; |
754 | 756 |
755 if (found) | 757 if (found) |
756 return AddResult(makeKnownGoodIterator(entry), false); | 758 return AddResult(entry, false); |
757 | 759 |
758 if (isDeletedBucket(*entry)) { | 760 if (isDeletedBucket(*entry)) { |
759 initializeBucket(*entry); | 761 initializeBucket(*entry); |
760 --m_deletedCount; | 762 --m_deletedCount; |
761 } | 763 } |
762 | 764 |
763 HashTranslator::translate(*entry, key, extra, h); | 765 HashTranslator::translate(*entry, key, extra, h); |
764 ++m_keyCount; | 766 ++m_keyCount; |
765 if (shouldExpand()) { | 767 if (shouldExpand()) { |
766 // FIXME: This makes an extra copy on expand. Probably not that bad
since | 768 // FIXME: This makes an extra copy on expand. Probably not that bad
since |
767 // expand is rare, but would be better to have a version of expand t
hat can | 769 // expand is rare, but would be better to have a version of expand t
hat can |
768 // follow a pivot entry and return the new position. | 770 // follow a pivot entry and return the new position. |
769 typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extr
actor::extract(*entry); | 771 typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extr
actor::extract(*entry); |
770 expand(); | 772 expand(); |
771 AddResult result(find(enteredKey), true); | 773 iterator findResult = find(enteredKey); |
772 ASSERT(result.iterator != end()); | 774 ASSERT(findResult != end()); |
| 775 ValueType* resultValue = findResult.get(); |
| 776 AddResult result(resultValue, true); |
773 return result; | 777 return result; |
774 } | 778 } |
775 | 779 |
776 return AddResult(makeKnownGoodIterator(entry), true); | 780 return AddResult(entry, true); |
777 } | 781 } |
778 | 782 |
779 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 783 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
780 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator>::reinsert(ValueType& entry) | 784 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator>::reinsert(ValueType& entry) |
781 { | 785 { |
782 ASSERT(m_table); | 786 ASSERT(m_table); |
783 ASSERT(!lookupForWriting(Extractor::extract(entry)).second); | 787 ASSERT(!lookupForWriting(Extractor::extract(entry)).second); |
784 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).fi
rst))); | 788 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).fi
rst))); |
785 #if DUMP_HASHTABLE_STATS | 789 #if DUMP_HASHTABLE_STATS |
786 atomicIncrement(&HashTableStats::numReinserts); | 790 atomicIncrement(&HashTableStats::numReinserts); |
(...skipping 373 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1160 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) | 1164 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) |
1161 { | 1165 { |
1162 return a.m_impl != b.m_impl; | 1166 return a.m_impl != b.m_impl; |
1163 } | 1167 } |
1164 | 1168 |
1165 } // namespace WTF | 1169 } // namespace WTF |
1166 | 1170 |
1167 #include "wtf/HashIterators.h" | 1171 #include "wtf/HashIterators.h" |
1168 | 1172 |
1169 #endif // WTF_HashTable_h | 1173 #endif // WTF_HashTable_h |
OLD | NEW |