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 467 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
478 #endif | 478 #endif |
479 | 479 |
480 #if CHECK_HASHTABLE_ITERATORS | 480 #if CHECK_HASHTABLE_ITERATORS |
481 void invalidateIterators(); | 481 void invalidateIterators(); |
482 #else | 482 #else |
483 static void invalidateIterators() { } | 483 static void invalidateIterators() { } |
484 #endif | 484 #endif |
485 | 485 |
486 static const int m_maxLoad = 2; | 486 static const int m_maxLoad = 2; |
487 static const int m_minLoad = 6; | 487 static const int m_minLoad = 6; |
| 488 static const int perturbShift = 5; |
488 | 489 |
489 ValueType* m_table; | 490 ValueType* m_table; |
490 int m_tableSize; | 491 int m_tableSize; |
491 int m_tableSizeMask; | 492 int m_tableSizeMask; |
492 int m_keyCount; | 493 int m_keyCount; |
493 int m_deletedCount; | 494 int m_deletedCount; |
494 | 495 |
495 #if CHECK_HASHTABLE_ITERATORS | 496 #if CHECK_HASHTABLE_ITERATORS |
496 public: | 497 public: |
497 // All access to m_iterators should be guarded with m_mutex. | 498 // All access to m_iterators should be guarded with m_mutex. |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
554 #if CHECK_HASHTABLE_ITERATORS | 555 #if CHECK_HASHTABLE_ITERATORS |
555 , m_iterators(0) | 556 , m_iterators(0) |
556 , m_mutex(adoptPtr(new Mutex)) | 557 , m_mutex(adoptPtr(new Mutex)) |
557 #endif | 558 #endif |
558 #if DUMP_HASHTABLE_STATS_PER_TABLE | 559 #if DUMP_HASHTABLE_STATS_PER_TABLE |
559 , m_stats(adoptPtr(new Stats)) | 560 , m_stats(adoptPtr(new Stats)) |
560 #endif | 561 #endif |
561 { | 562 { |
562 } | 563 } |
563 | 564 |
564 inline unsigned doubleHash(unsigned key) | |
565 { | |
566 key = ~key + (key >> 23); | |
567 key ^= (key << 12); | |
568 key ^= (key >> 7); | |
569 key ^= (key << 2); | |
570 key ^= (key >> 20); | |
571 return key; | |
572 } | |
573 | |
574 #if ASSERT_DISABLED | 565 #if ASSERT_DISABLED |
575 | 566 |
576 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 567 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
577 template<typename HashTranslator, typename T> | 568 template<typename HashTranslator, typename T> |
578 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s>::checkKey(const T&) | 569 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s>::checkKey(const T&) |
579 { | 570 { |
580 } | 571 } |
581 | 572 |
582 #else | 573 #else |
583 | 574 |
(...skipping 12 matching lines...) Expand all Loading... |
596 } | 587 } |
597 | 588 |
598 #endif | 589 #endif |
599 | 590 |
600 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 591 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
601 template<typename HashTranslator, typename T> | 592 template<typename HashTranslator, typename T> |
602 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTra
its>::lookup(const T& key) | 593 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTra
its>::lookup(const T& key) |
603 { | 594 { |
604 checkKey<HashTranslator>(key); | 595 checkKey<HashTranslator>(key); |
605 | 596 |
606 int k = 0; | |
607 int sizeMask = m_tableSizeMask; | 597 int sizeMask = m_tableSizeMask; |
608 ValueType* table = m_table; | 598 ValueType* table = m_table; |
609 unsigned h = HashTranslator::hash(key); | 599 unsigned h = HashTranslator::hash(key); |
610 int i = h & sizeMask; | 600 unsigned i = h; |
| 601 unsigned perturb = h; |
611 | 602 |
612 if (!table) | 603 if (!table) |
613 return 0; | 604 return 0; |
614 | 605 |
615 #if DUMP_HASHTABLE_STATS | 606 #if DUMP_HASHTABLE_STATS |
616 atomicIncrement(&HashTableStats::numAccesses); | 607 atomicIncrement(&HashTableStats::numAccesses); |
617 int probeCount = 0; | 608 int probeCount = 0; |
618 #endif | 609 #endif |
619 | 610 |
620 #if DUMP_HASHTABLE_STATS_PER_TABLE | 611 #if DUMP_HASHTABLE_STATS_PER_TABLE |
621 ++m_stats->numAccesses; | 612 ++m_stats->numAccesses; |
622 int perTableProbeCount = 0; | 613 int perTableProbeCount = 0; |
623 #endif | 614 #endif |
624 | 615 |
625 while (1) { | 616 while (1) { |
626 ValueType* entry = table + i; | 617 ValueType* entry = table + (i & sizeMask); |
627 | 618 |
628 // we count on the compiler to optimize out this branch | 619 // we count on the compiler to optimize out this branch |
629 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 620 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
630 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 621 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
631 return entry; | 622 return entry; |
632 | 623 |
633 if (isEmptyBucket(*entry)) | 624 if (isEmptyBucket(*entry)) |
634 return 0; | 625 return 0; |
635 } else { | 626 } else { |
636 if (isEmptyBucket(*entry)) | 627 if (isEmptyBucket(*entry)) |
637 return 0; | 628 return 0; |
638 | 629 |
639 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor:
:extract(*entry), key)) | 630 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor:
:extract(*entry), key)) |
640 return entry; | 631 return entry; |
641 } | 632 } |
642 #if DUMP_HASHTABLE_STATS | 633 #if DUMP_HASHTABLE_STATS |
643 ++probeCount; | 634 ++probeCount; |
644 HashTableStats::recordCollisionAtCount(probeCount); | 635 HashTableStats::recordCollisionAtCount(probeCount); |
645 #endif | 636 #endif |
646 | 637 |
647 #if DUMP_HASHTABLE_STATS_PER_TABLE | 638 #if DUMP_HASHTABLE_STATS_PER_TABLE |
648 ++perTableProbeCount; | 639 ++perTableProbeCount; |
649 m_stats->recordCollisionAtCount(perTableProbeCount); | 640 m_stats->recordCollisionAtCount(perTableProbeCount); |
650 #endif | 641 #endif |
651 | 642 |
652 if (k == 0) | 643 perturb >>= perturbShift; |
653 k = 1 | doubleHash(h); | 644 i = i*5 + perturb + 1; |
654 i = (i + k) & sizeMask; | |
655 } | 645 } |
656 } | 646 } |
657 | 647 |
658 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 648 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
659 template<typename HashTranslator, typename T> | 649 template<typename HashTranslator, typename T> |
660 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTr
aits>::lookupForWriting(const T& key) | 650 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTr
aits>::lookupForWriting(const T& key) |
661 { | 651 { |
662 ASSERT(m_table); | 652 ASSERT(m_table); |
663 checkKey<HashTranslator>(key); | 653 checkKey<HashTranslator>(key); |
664 | 654 |
665 int k = 0; | |
666 ValueType* table = m_table; | 655 ValueType* table = m_table; |
667 int sizeMask = m_tableSizeMask; | 656 int sizeMask = m_tableSizeMask; |
668 unsigned h = HashTranslator::hash(key); | 657 unsigned h = HashTranslator::hash(key); |
669 int i = h & sizeMask; | 658 unsigned i = h; |
| 659 unsigned perturb = h; |
670 | 660 |
671 #if DUMP_HASHTABLE_STATS | 661 #if DUMP_HASHTABLE_STATS |
672 atomicIncrement(&HashTableStats::numAccesses); | 662 atomicIncrement(&HashTableStats::numAccesses); |
673 int probeCount = 0; | 663 int probeCount = 0; |
674 #endif | 664 #endif |
675 | 665 |
676 #if DUMP_HASHTABLE_STATS_PER_TABLE | 666 #if DUMP_HASHTABLE_STATS_PER_TABLE |
677 ++m_stats->numAccesses; | 667 ++m_stats->numAccesses; |
678 int perTableProbeCount = 0; | 668 int perTableProbeCount = 0; |
679 #endif | 669 #endif |
680 | 670 |
681 ValueType* deletedEntry = 0; | 671 ValueType* deletedEntry = 0; |
682 | 672 |
683 while (1) { | 673 while (1) { |
684 ValueType* entry = table + i; | 674 ValueType* entry = table + (i & sizeMask); |
685 | 675 |
686 // we count on the compiler to optimize out this branch | 676 // we count on the compiler to optimize out this branch |
687 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 677 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
688 if (isEmptyBucket(*entry)) | 678 if (isEmptyBucket(*entry)) |
689 return LookupType(deletedEntry ? deletedEntry : entry, false
); | 679 return LookupType(deletedEntry ? deletedEntry : entry, false
); |
690 | 680 |
691 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 681 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
692 return LookupType(entry, true); | 682 return LookupType(entry, true); |
693 | 683 |
694 if (isDeletedBucket(*entry)) | 684 if (isDeletedBucket(*entry)) |
(...skipping 10 matching lines...) Expand all Loading... |
705 #if DUMP_HASHTABLE_STATS | 695 #if DUMP_HASHTABLE_STATS |
706 ++probeCount; | 696 ++probeCount; |
707 HashTableStats::recordCollisionAtCount(probeCount); | 697 HashTableStats::recordCollisionAtCount(probeCount); |
708 #endif | 698 #endif |
709 | 699 |
710 #if DUMP_HASHTABLE_STATS_PER_TABLE | 700 #if DUMP_HASHTABLE_STATS_PER_TABLE |
711 ++perTableProbeCount; | 701 ++perTableProbeCount; |
712 m_stats->recordCollisionAtCount(perTableProbeCount); | 702 m_stats->recordCollisionAtCount(perTableProbeCount); |
713 #endif | 703 #endif |
714 | 704 |
715 if (k == 0) | 705 perturb >>= perturbShift; |
716 k = 1 | doubleHash(h); | 706 i = i*5 + perturb + 1; |
717 i = (i + k) & sizeMask; | |
718 } | 707 } |
719 } | 708 } |
720 | 709 |
721 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> | 710 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits> |
722 template<typename HashTranslator, typename T> | 711 template<typename HashTranslator, typename T> |
723 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, K
eyTraits>::fullLookupForWriting(const T& key) | 712 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyT
raits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, K
eyTraits>::fullLookupForWriting(const T& key) |
724 { | 713 { |
725 ASSERT(m_table); | 714 ASSERT(m_table); |
726 checkKey<HashTranslator>(key); | 715 checkKey<HashTranslator>(key); |
727 | 716 |
728 int k = 0; | |
729 ValueType* table = m_table; | 717 ValueType* table = m_table; |
730 int sizeMask = m_tableSizeMask; | 718 int sizeMask = m_tableSizeMask; |
731 unsigned h = HashTranslator::hash(key); | 719 unsigned h = HashTranslator::hash(key); |
732 int i = h & sizeMask; | 720 unsigned i = h; |
| 721 unsigned perturb = h; |
733 | 722 |
734 #if DUMP_HASHTABLE_STATS | 723 #if DUMP_HASHTABLE_STATS |
735 atomicIncrement(&HashTableStats::numAccesses); | 724 atomicIncrement(&HashTableStats::numAccesses); |
736 int probeCount = 0; | 725 int probeCount = 0; |
737 #endif | 726 #endif |
738 | 727 |
739 #if DUMP_HASHTABLE_STATS_PER_TABLE | 728 #if DUMP_HASHTABLE_STATS_PER_TABLE |
740 ++m_stats->numAccesses; | 729 ++m_stats->numAccesses; |
741 int perTableProbeCount = 0; | 730 int perTableProbeCount = 0; |
742 #endif | 731 #endif |
743 | 732 |
744 ValueType* deletedEntry = 0; | 733 ValueType* deletedEntry = 0; |
745 | 734 |
746 while (1) { | 735 while (1) { |
747 ValueType* entry = table + i; | 736 ValueType* entry = table + (i & sizeMask); |
748 | 737 |
749 // we count on the compiler to optimize out this branch | 738 // we count on the compiler to optimize out this branch |
750 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 739 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
751 if (isEmptyBucket(*entry)) | 740 if (isEmptyBucket(*entry)) |
752 return makeLookupResult(deletedEntry ? deletedEntry : entry,
false, h); | 741 return makeLookupResult(deletedEntry ? deletedEntry : entry,
false, h); |
753 | 742 |
754 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 743 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
755 return makeLookupResult(entry, true, h); | 744 return makeLookupResult(entry, true, h); |
756 | 745 |
757 if (isDeletedBucket(*entry)) | 746 if (isDeletedBucket(*entry)) |
(...skipping 10 matching lines...) Expand all Loading... |
768 #if DUMP_HASHTABLE_STATS | 757 #if DUMP_HASHTABLE_STATS |
769 ++probeCount; | 758 ++probeCount; |
770 HashTableStats::recordCollisionAtCount(probeCount); | 759 HashTableStats::recordCollisionAtCount(probeCount); |
771 #endif | 760 #endif |
772 | 761 |
773 #if DUMP_HASHTABLE_STATS_PER_TABLE | 762 #if DUMP_HASHTABLE_STATS_PER_TABLE |
774 ++perTableProbeCount; | 763 ++perTableProbeCount; |
775 m_stats->recordCollisionAtCount(perTableProbeCount); | 764 m_stats->recordCollisionAtCount(perTableProbeCount); |
776 #endif | 765 #endif |
777 | 766 |
778 if (k == 0) | 767 perturb >>= perturbShift; |
779 k = 1 | doubleHash(h); | 768 i = i*5 + perturb + 1; |
780 i = (i + k) & sizeMask; | |
781 } | 769 } |
782 } | 770 } |
783 | 771 |
784 template<bool emptyValueIsZero> struct HashTableBucketInitializer; | 772 template<bool emptyValueIsZero> struct HashTableBucketInitializer; |
785 | 773 |
786 template<> struct HashTableBucketInitializer<false> { | 774 template<> struct HashTableBucketInitializer<false> { |
787 template<typename Traits, typename Value> static void initialize(Value&
bucket) | 775 template<typename Traits, typename Value> static void initialize(Value&
bucket) |
788 { | 776 { |
789 new (NotNull, &bucket) Value(Traits::emptyValue()); | 777 new (NotNull, &bucket) Value(Traits::emptyValue()); |
790 } | 778 } |
(...skipping 23 matching lines...) Expand all Loading... |
814 | 802 |
815 invalidateIterators(); | 803 invalidateIterators(); |
816 | 804 |
817 if (!m_table) | 805 if (!m_table) |
818 expand(); | 806 expand(); |
819 | 807 |
820 internalCheckTableConsistency(); | 808 internalCheckTableConsistency(); |
821 | 809 |
822 ASSERT(m_table); | 810 ASSERT(m_table); |
823 | 811 |
824 int k = 0; | |
825 ValueType* table = m_table; | 812 ValueType* table = m_table; |
826 int sizeMask = m_tableSizeMask; | 813 int sizeMask = m_tableSizeMask; |
827 unsigned h = HashTranslator::hash(key); | 814 unsigned h = HashTranslator::hash(key); |
828 int i = h & sizeMask; | 815 unsigned i = h; |
| 816 unsigned perturb = h; |
829 | 817 |
830 #if DUMP_HASHTABLE_STATS | 818 #if DUMP_HASHTABLE_STATS |
831 atomicIncrement(&HashTableStats::numAccesses); | 819 atomicIncrement(&HashTableStats::numAccesses); |
832 int probeCount = 0; | 820 int probeCount = 0; |
833 #endif | 821 #endif |
834 | 822 |
835 #if DUMP_HASHTABLE_STATS_PER_TABLE | 823 #if DUMP_HASHTABLE_STATS_PER_TABLE |
836 ++m_stats->numAccesses; | 824 ++m_stats->numAccesses; |
837 int perTableProbeCount = 0; | 825 int perTableProbeCount = 0; |
838 #endif | 826 #endif |
839 | 827 |
840 ValueType* deletedEntry = 0; | 828 ValueType* deletedEntry = 0; |
841 ValueType* entry; | 829 ValueType* entry; |
842 while (1) { | 830 while (1) { |
843 entry = table + i; | 831 entry = table + (i & sizeMask); |
844 | 832 |
845 // we count on the compiler to optimize out this branch | 833 // we count on the compiler to optimize out this branch |
846 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 834 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
847 if (isEmptyBucket(*entry)) | 835 if (isEmptyBucket(*entry)) |
848 break; | 836 break; |
849 | 837 |
850 if (HashTranslator::equal(Extractor::extract(*entry), key)) | 838 if (HashTranslator::equal(Extractor::extract(*entry), key)) |
851 return AddResult(makeKnownGoodIterator(entry), false); | 839 return AddResult(makeKnownGoodIterator(entry), false); |
852 | 840 |
853 if (isDeletedBucket(*entry)) | 841 if (isDeletedBucket(*entry)) |
(...skipping 10 matching lines...) Expand all Loading... |
864 #if DUMP_HASHTABLE_STATS | 852 #if DUMP_HASHTABLE_STATS |
865 ++probeCount; | 853 ++probeCount; |
866 HashTableStats::recordCollisionAtCount(probeCount); | 854 HashTableStats::recordCollisionAtCount(probeCount); |
867 #endif | 855 #endif |
868 | 856 |
869 #if DUMP_HASHTABLE_STATS_PER_TABLE | 857 #if DUMP_HASHTABLE_STATS_PER_TABLE |
870 ++perTableProbeCount; | 858 ++perTableProbeCount; |
871 m_stats->recordCollisionAtCount(perTableProbeCount); | 859 m_stats->recordCollisionAtCount(perTableProbeCount); |
872 #endif | 860 #endif |
873 | 861 |
874 if (k == 0) | 862 perturb >>= perturbShift; |
875 k = 1 | doubleHash(h); | 863 i = i*5 + perturb + 1; |
876 i = (i + k) & sizeMask; | |
877 } | 864 } |
878 | 865 |
879 if (deletedEntry) { | 866 if (deletedEntry) { |
880 initializeBucket(*deletedEntry); | 867 initializeBucket(*deletedEntry); |
881 entry = deletedEntry; | 868 entry = deletedEntry; |
882 --m_deletedCount; | 869 --m_deletedCount; |
883 } | 870 } |
884 | 871 |
885 HashTranslator::translate(*entry, key, extra); | 872 HashTranslator::translate(*entry, key, extra); |
886 | 873 |
(...skipping 524 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1411 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) | 1398 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) |
1412 { | 1399 { |
1413 return a.m_impl != b.m_impl; | 1400 return a.m_impl != b.m_impl; |
1414 } | 1401 } |
1415 | 1402 |
1416 } // namespace WTF | 1403 } // namespace WTF |
1417 | 1404 |
1418 #include <wtf/HashIterators.h> | 1405 #include <wtf/HashIterators.h> |
1419 | 1406 |
1420 #endif // WTF_HashTable_h | 1407 #endif // WTF_HashTable_h |
OLD | NEW |