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 349 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
360 for (int i = 1; i <= maxCollisions; i++) { | 360 for (int i = 1; i <= maxCollisions; i++) { |
361 dataLogF(" %d lookups with exactly %d collisions (%.2f%% ,
%.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph
[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesse
s); | 361 dataLogF(" %d lookups with exactly %d collisions (%.2f%% ,
%.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph
[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesse
s); |
362 } | 362 } |
363 dataLogF("%d rehashes\n", numRehashes); | 363 dataLogF("%d rehashes\n", numRehashes); |
364 dataLogF("%d reinserts\n", numReinserts); | 364 dataLogF("%d reinserts\n", numReinserts); |
365 } | 365 } |
366 }; | 366 }; |
367 #endif | 367 #endif |
368 | 368 |
369 HashTable(); | 369 HashTable(); |
370 ~HashTable() | 370 ~HashTable() |
371 { | 371 { |
372 invalidateIterators(); | 372 invalidateIterators(); |
373 if (m_table) | 373 if (m_table) |
374 deallocateTable(m_table, m_tableSize); | 374 deallocateTable(m_table, m_tableSize); |
375 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION | 375 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION |
376 m_table = (ValueType*)(uintptr_t)0xbbadbeef; | 376 m_table = (ValueType*)(uintptr_t)0xbbadbeef; |
377 #endif | 377 #endif |
378 } | 378 } |
379 | 379 |
380 HashTable(const HashTable&); | 380 HashTable(const HashTable&); |
381 void swap(HashTable&); | 381 void swap(HashTable&); |
382 HashTable& operator=(const HashTable&); | 382 HashTable& operator=(const HashTable&); |
(...skipping 235 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
618 int probeCount = 0; | 618 int probeCount = 0; |
619 #endif | 619 #endif |
620 | 620 |
621 #if DUMP_HASHTABLE_STATS_PER_TABLE | 621 #if DUMP_HASHTABLE_STATS_PER_TABLE |
622 ++m_stats->numAccesses; | 622 ++m_stats->numAccesses; |
623 int perTableProbeCount = 0; | 623 int perTableProbeCount = 0; |
624 #endif | 624 #endif |
625 | 625 |
626 while (1) { | 626 while (1) { |
627 ValueType* entry = table + i; | 627 ValueType* entry = table + i; |
628 | 628 |
629 // we count on the compiler to optimize out this branch | 629 // we count on the compiler to optimize out this branch |
630 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 630 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
631 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 631 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
632 return entry; | 632 return entry; |
633 | 633 |
634 if (isEmptyBucket(*entry)) | 634 if (isEmptyBucket(*entry)) |
635 return 0; | 635 return 0; |
636 } else { | 636 } else { |
637 if (isEmptyBucket(*entry)) | 637 if (isEmptyBucket(*entry)) |
638 return 0; | 638 return 0; |
639 | 639 |
640 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor:
:extract(*entry), key)) | 640 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor:
:extract(*entry), key)) |
641 return entry; | 641 return entry; |
642 } | 642 } |
643 #if DUMP_HASHTABLE_STATS | 643 #if DUMP_HASHTABLE_STATS |
644 ++probeCount; | 644 ++probeCount; |
645 HashTableStats::recordCollisionAtCount(probeCount); | 645 HashTableStats::recordCollisionAtCount(probeCount); |
646 #endif | 646 #endif |
647 | 647 |
648 #if DUMP_HASHTABLE_STATS_PER_TABLE | 648 #if DUMP_HASHTABLE_STATS_PER_TABLE |
649 ++perTableProbeCount; | 649 ++perTableProbeCount; |
(...skipping 26 matching lines...) Expand all Loading... |
676 | 676 |
677 #if DUMP_HASHTABLE_STATS_PER_TABLE | 677 #if DUMP_HASHTABLE_STATS_PER_TABLE |
678 ++m_stats->numAccesses; | 678 ++m_stats->numAccesses; |
679 int perTableProbeCount = 0; | 679 int perTableProbeCount = 0; |
680 #endif | 680 #endif |
681 | 681 |
682 ValueType* deletedEntry = 0; | 682 ValueType* deletedEntry = 0; |
683 | 683 |
684 while (1) { | 684 while (1) { |
685 ValueType* entry = table + i; | 685 ValueType* entry = table + i; |
686 | 686 |
687 // we count on the compiler to optimize out this branch | 687 // we count on the compiler to optimize out this branch |
688 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 688 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
689 if (isEmptyBucket(*entry)) | 689 if (isEmptyBucket(*entry)) |
690 return LookupType(deletedEntry ? deletedEntry : entry, false
); | 690 return LookupType(deletedEntry ? deletedEntry : entry, false
); |
691 | 691 |
692 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 692 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
693 return LookupType(entry, true); | 693 return LookupType(entry, true); |
694 | 694 |
695 if (isDeletedBucket(*entry)) | 695 if (isDeletedBucket(*entry)) |
696 deletedEntry = entry; | 696 deletedEntry = entry; |
697 } else { | 697 } else { |
698 if (isEmptyBucket(*entry)) | 698 if (isEmptyBucket(*entry)) |
699 return LookupType(deletedEntry ? deletedEntry : entry, false
); | 699 return LookupType(deletedEntry ? deletedEntry : entry, false
); |
700 | 700 |
701 if (isDeletedBucket(*entry)) | 701 if (isDeletedBucket(*entry)) |
702 deletedEntry = entry; | 702 deletedEntry = entry; |
703 else if (HashTranslator::equal(Extractor::extract(*entry), key)) | 703 else if (HashTranslator::equal(Extractor::extract(*entry), key)) |
704 return LookupType(entry, true); | 704 return LookupType(entry, true); |
705 } | 705 } |
706 #if DUMP_HASHTABLE_STATS | 706 #if DUMP_HASHTABLE_STATS |
707 ++probeCount; | 707 ++probeCount; |
708 HashTableStats::recordCollisionAtCount(probeCount); | 708 HashTableStats::recordCollisionAtCount(probeCount); |
709 #endif | 709 #endif |
710 | 710 |
(...skipping 28 matching lines...) Expand all Loading... |
739 | 739 |
740 #if DUMP_HASHTABLE_STATS_PER_TABLE | 740 #if DUMP_HASHTABLE_STATS_PER_TABLE |
741 ++m_stats->numAccesses; | 741 ++m_stats->numAccesses; |
742 int perTableProbeCount = 0; | 742 int perTableProbeCount = 0; |
743 #endif | 743 #endif |
744 | 744 |
745 ValueType* deletedEntry = 0; | 745 ValueType* deletedEntry = 0; |
746 | 746 |
747 while (1) { | 747 while (1) { |
748 ValueType* entry = table + i; | 748 ValueType* entry = table + i; |
749 | 749 |
750 // we count on the compiler to optimize out this branch | 750 // we count on the compiler to optimize out this branch |
751 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 751 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
752 if (isEmptyBucket(*entry)) | 752 if (isEmptyBucket(*entry)) |
753 return makeLookupResult(deletedEntry ? deletedEntry : entry,
false, h); | 753 return makeLookupResult(deletedEntry ? deletedEntry : entry,
false, h); |
754 | 754 |
755 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 755 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
756 return makeLookupResult(entry, true, h); | 756 return makeLookupResult(entry, true, h); |
757 | 757 |
758 if (isDeletedBucket(*entry)) | 758 if (isDeletedBucket(*entry)) |
759 deletedEntry = entry; | 759 deletedEntry = entry; |
760 } else { | 760 } else { |
761 if (isEmptyBucket(*entry)) | 761 if (isEmptyBucket(*entry)) |
762 return makeLookupResult(deletedEntry ? deletedEntry : entry,
false, h); | 762 return makeLookupResult(deletedEntry ? deletedEntry : entry,
false, h); |
763 | 763 |
764 if (isDeletedBucket(*entry)) | 764 if (isDeletedBucket(*entry)) |
765 deletedEntry = entry; | 765 deletedEntry = entry; |
766 else if (HashTranslator::equal(Extractor::extract(*entry), key)) | 766 else if (HashTranslator::equal(Extractor::extract(*entry), key)) |
767 return makeLookupResult(entry, true, h); | 767 return makeLookupResult(entry, true, h); |
768 } | 768 } |
769 #if DUMP_HASHTABLE_STATS | 769 #if DUMP_HASHTABLE_STATS |
770 ++probeCount; | 770 ++probeCount; |
771 HashTableStats::recordCollisionAtCount(probeCount); | 771 HashTableStats::recordCollisionAtCount(probeCount); |
772 #endif | 772 #endif |
773 | 773 |
(...skipping 19 matching lines...) Expand all Loading... |
793 | 793 |
794 template<> struct HashTableBucketInitializer<true> { | 794 template<> struct HashTableBucketInitializer<true> { |
795 template<typename Traits, typename Value> static void initialize(Value&
bucket) | 795 template<typename Traits, typename Value> static void initialize(Value&
bucket) |
796 { | 796 { |
797 // This initializes the bucket without copying the empty value. | 797 // This initializes the bucket without copying the empty value. |
798 // That makes it possible to use this with types that don't support
copying. | 798 // That makes it possible to use this with types that don't support
copying. |
799 // The memset to 0 looks like a slow operation but is optimized by t
he compilers. | 799 // The memset to 0 looks like a slow operation but is optimized by t
he compilers. |
800 memset(&bucket, 0, sizeof(bucket)); | 800 memset(&bucket, 0, sizeof(bucket)); |
801 } | 801 } |
802 }; | 802 }; |
803 | 803 |
804 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 804 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
805 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s>::initializeBucket(ValueType& bucket) | 805 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s>::initializeBucket(ValueType& bucket) |
806 { | 806 { |
807 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initializ
e<Traits>(bucket); | 807 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initializ
e<Traits>(bucket); |
808 } | 808 } |
809 | 809 |
810 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 810 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
811 template<typename HashTranslator, typename T, typename Extra> | 811 template<typename HashTranslator, typename T, typename Extra> |
812 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::a
dd(const T& key, const Extra& extra) | 812 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::a
dd(const T& key, const Extra& extra) |
813 { | 813 { |
(...skipping 21 matching lines...) Expand all Loading... |
835 | 835 |
836 #if DUMP_HASHTABLE_STATS_PER_TABLE | 836 #if DUMP_HASHTABLE_STATS_PER_TABLE |
837 ++m_stats->numAccesses; | 837 ++m_stats->numAccesses; |
838 int perTableProbeCount = 0; | 838 int perTableProbeCount = 0; |
839 #endif | 839 #endif |
840 | 840 |
841 ValueType* deletedEntry = 0; | 841 ValueType* deletedEntry = 0; |
842 ValueType* entry; | 842 ValueType* entry; |
843 while (1) { | 843 while (1) { |
844 entry = table + i; | 844 entry = table + i; |
845 | 845 |
846 // we count on the compiler to optimize out this branch | 846 // we count on the compiler to optimize out this branch |
847 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 847 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
848 if (isEmptyBucket(*entry)) | 848 if (isEmptyBucket(*entry)) |
849 break; | 849 break; |
850 | 850 |
851 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 851 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
852 return AddResult(makeKnownGoodIterator(entry), false); | 852 return AddResult(makeKnownGoodIterator(entry), false); |
853 | 853 |
854 if (isDeletedBucket(*entry)) | 854 if (isDeletedBucket(*entry)) |
855 deletedEntry = entry; | 855 deletedEntry = entry; |
856 } else { | 856 } else { |
857 if (isEmptyBucket(*entry)) | 857 if (isEmptyBucket(*entry)) |
858 break; | 858 break; |
859 | 859 |
860 if (isDeletedBucket(*entry)) | 860 if (isDeletedBucket(*entry)) |
861 deletedEntry = entry; | 861 deletedEntry = entry; |
862 else if (HashTranslator::equal(Extractor::extract(*entry), key)) | 862 else if (HashTranslator::equal(Extractor::extract(*entry), key)) |
863 return AddResult(makeKnownGoodIterator(entry), false); | 863 return AddResult(makeKnownGoodIterator(entry), false); |
864 } | 864 } |
865 #if DUMP_HASHTABLE_STATS | 865 #if DUMP_HASHTABLE_STATS |
866 ++probeCount; | 866 ++probeCount; |
867 HashTableStats::recordCollisionAtCount(probeCount); | 867 HashTableStats::recordCollisionAtCount(probeCount); |
868 #endif | 868 #endif |
869 | 869 |
870 #if DUMP_HASHTABLE_STATS_PER_TABLE | 870 #if DUMP_HASHTABLE_STATS_PER_TABLE |
871 ++perTableProbeCount; | 871 ++perTableProbeCount; |
872 m_stats->recordCollisionAtCount(perTableProbeCount); | 872 m_stats->recordCollisionAtCount(perTableProbeCount); |
873 #endif | 873 #endif |
874 | 874 |
875 if (!k) | 875 if (!k) |
876 k = 1 | doubleHash(h); | 876 k = 1 | doubleHash(h); |
877 i = (i + k) & sizeMask; | 877 i = (i + k) & sizeMask; |
878 } | 878 } |
879 | 879 |
880 if (deletedEntry) { | 880 if (deletedEntry) { |
881 initializeBucket(*deletedEntry); | 881 initializeBucket(*deletedEntry); |
882 entry = deletedEntry; | 882 entry = deletedEntry; |
883 --m_deletedCount; | 883 --m_deletedCount; |
884 } | 884 } |
885 | 885 |
886 HashTranslator::translate(*entry, key, extra); | 886 HashTranslator::translate(*entry, key, extra); |
887 | 887 |
888 ++m_keyCount; | 888 ++m_keyCount; |
889 | 889 |
890 if (shouldExpand()) { | 890 if (shouldExpand()) { |
891 // FIXME: This makes an extra copy on expand. Probably not that bad
since | 891 // FIXME: This makes an extra copy on expand. Probably not that bad
since |
892 // expand is rare, but would be better to have a version of expand t
hat can | 892 // expand is rare, but would be better to have a version of expand t
hat can |
893 // follow a pivot entry and return the new position. | 893 // follow a pivot entry and return the new position. |
894 KeyType enteredKey = Extractor::extract(*entry); | 894 KeyType enteredKey = Extractor::extract(*entry); |
895 expand(); | 895 expand(); |
896 AddResult result(find(enteredKey), true); | 896 AddResult result(find(enteredKey), true); |
897 ASSERT(result.iterator != end()); | 897 ASSERT(result.iterator != end()); |
898 return result; | 898 return result; |
899 } | 899 } |
900 | 900 |
901 internalCheckTableConsistency(); | 901 internalCheckTableConsistency(); |
902 | 902 |
903 return AddResult(makeKnownGoodIterator(entry), true); | 903 return AddResult(makeKnownGoodIterator(entry), true); |
904 } | 904 } |
905 | 905 |
906 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 906 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
907 template<typename HashTranslator, typename T, typename Extra> | 907 template<typename HashTranslator, typename T, typename Extra> |
908 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::a
ddPassingHashCode(const T& key, const Extra& extra) | 908 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::a
ddPassingHashCode(const T& key, const Extra& extra) |
909 { | 909 { |
910 checkKey<HashTranslator>(key); | 910 checkKey<HashTranslator>(key); |
911 | 911 |
912 invalidateIterators(); | 912 invalidateIterators(); |
913 | 913 |
914 if (!m_table) | 914 if (!m_table) |
915 expand(); | 915 expand(); |
916 | 916 |
917 internalCheckTableConsistency(); | 917 internalCheckTableConsistency(); |
918 | 918 |
919 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); | 919 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); |
920 | 920 |
921 ValueType* entry = lookupResult.first.first; | 921 ValueType* entry = lookupResult.first.first; |
922 bool found = lookupResult.first.second; | 922 bool found = lookupResult.first.second; |
923 unsigned h = lookupResult.second; | 923 unsigned h = lookupResult.second; |
924 | 924 |
925 if (found) | 925 if (found) |
926 return AddResult(makeKnownGoodIterator(entry), false); | 926 return AddResult(makeKnownGoodIterator(entry), false); |
927 | 927 |
928 if (isDeletedBucket(*entry)) { | 928 if (isDeletedBucket(*entry)) { |
929 initializeBucket(*entry); | 929 initializeBucket(*entry); |
930 --m_deletedCount; | 930 --m_deletedCount; |
931 } | 931 } |
932 | 932 |
933 HashTranslator::translate(*entry, key, extra, h); | 933 HashTranslator::translate(*entry, key, extra, h); |
934 ++m_keyCount; | 934 ++m_keyCount; |
935 if (shouldExpand()) { | 935 if (shouldExpand()) { |
936 // FIXME: This makes an extra copy on expand. Probably not that bad
since | 936 // FIXME: This makes an extra copy on expand. Probably not that bad
since |
937 // expand is rare, but would be better to have a version of expand t
hat can | 937 // expand is rare, but would be better to have a version of expand t
hat can |
938 // follow a pivot entry and return the new position. | 938 // follow a pivot entry and return the new position. |
939 KeyType enteredKey = Extractor::extract(*entry); | 939 KeyType enteredKey = Extractor::extract(*entry); |
940 expand(); | 940 expand(); |
941 AddResult result(find(enteredKey), true); | 941 AddResult result(find(enteredKey), true); |
942 ASSERT(result.iterator != end()); | 942 ASSERT(result.iterator != end()); |
(...skipping 15 matching lines...) Expand all Loading... |
958 atomicIncrement(&HashTableStats::numReinserts); | 958 atomicIncrement(&HashTableStats::numReinserts); |
959 #endif | 959 #endif |
960 #if DUMP_HASHTABLE_STATS_PER_TABLE | 960 #if DUMP_HASHTABLE_STATS_PER_TABLE |
961 ++m_stats->numReinserts; | 961 ++m_stats->numReinserts; |
962 #endif | 962 #endif |
963 | 963 |
964 Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWritin
g(Extractor::extract(entry)).first); | 964 Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWritin
g(Extractor::extract(entry)).first); |
965 } | 965 } |
966 | 966 |
967 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 967 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
968 template <typename HashTranslator, typename T> | 968 template <typename HashTranslator, typename T> |
969 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fi
nd(const T& key) | 969 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fi
nd(const T& key) |
970 { | 970 { |
971 if (!m_table) | 971 if (!m_table) |
972 return end(); | 972 return end(); |
973 | 973 |
974 ValueType* entry = lookup<HashTranslator>(key); | 974 ValueType* entry = lookup<HashTranslator>(key); |
975 if (!entry) | 975 if (!entry) |
976 return end(); | 976 return end(); |
977 | 977 |
978 return makeKnownGoodIterator(entry); | 978 return makeKnownGoodIterator(entry); |
979 } | 979 } |
980 | 980 |
981 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 981 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
982 template <typename HashTranslator, typename T> | 982 template <typename HashTranslator, typename T> |
983 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s>::find(const T& key) const | 983 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>:
:const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s>::find(const T& key) const |
984 { | 984 { |
985 if (!m_table) | 985 if (!m_table) |
986 return end(); | 986 return end(); |
987 | 987 |
988 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(
key); | 988 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(
key); |
989 if (!entry) | 989 if (!entry) |
990 return end(); | 990 return end(); |
991 | 991 |
992 return makeKnownGoodConstIterator(entry); | 992 return makeKnownGoodConstIterator(entry); |
993 } | 993 } |
994 | 994 |
995 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 995 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
996 template <typename HashTranslator, typename T> | 996 template <typename HashTranslator, typename T> |
997 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::con
tains(const T& key) const | 997 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::con
tains(const T& key) const |
998 { | 998 { |
999 if (!m_table) | 999 if (!m_table) |
1000 return false; | 1000 return false; |
1001 | 1001 |
1002 return const_cast<HashTable*>(this)->lookup<HashTranslator>(key); | 1002 return const_cast<HashTable*>(this)->lookup<HashTranslator>(key); |
1003 } | 1003 } |
1004 | 1004 |
1005 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 1005 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
1006 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rem
oveAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos) | 1006 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rem
oveAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos) |
(...skipping 405 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1412 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) | 1412 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) |
1413 { | 1413 { |
1414 return a.m_impl != b.m_impl; | 1414 return a.m_impl != b.m_impl; |
1415 } | 1415 } |
1416 | 1416 |
1417 } // namespace WTF | 1417 } // namespace WTF |
1418 | 1418 |
1419 #include "wtf/HashIterators.h" | 1419 #include "wtf/HashIterators.h" |
1420 | 1420 |
1421 #endif // WTF_HashTable_h | 1421 #endif // WTF_HashTable_h |
OLD | NEW |