Changeset 237419 in webkit
- Timestamp:
- Oct 25, 2018 10:41:35 AM (5 years ago)
- Location:
- trunk
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WTF/ChangeLog
r237402 r237419 1 2018-10-25 Geoffrey Garen <ggaren@apple.com> 2 3 HashMap should support selecting a random entry 4 https://bugs.webkit.org/show_bug.cgi?id=190814 5 6 Reviewed by Antti Koivisto. 7 8 In some cases, remove(begin()) is not quite good enough as a random 9 eviction strategy. (See https://bugs.webkit.org/show_bug.cgi?id=190792.) 10 So, let's support real random eviction. 11 12 (And by "real" I mean "pseudo".) 13 14 * wtf/HashCountedSet.h: 15 * wtf/HashMap.h: 16 * wtf/HashSet.h: 17 * wtf/ListHashSet.h: 18 (WTF::ListHashSet::random): 19 (WTF::ListHashSet::random const): 20 * wtf/LoggingHashMap.h: 21 * wtf/LoggingHashSet.h: Plumb through the random() iterator. 22 23 * wtf/HashTable.h: 24 (WTF::HashTable::random): 25 (WTF::HashTable::random const): Implement the random() iterator. 26 makeIterator() already supports starting from any bucket, so this is 27 pretty easy. 28 29 In the subtle case where we select end(), we choose to wrap around and 30 return begin(). We expect that clients don't really think of the end() 31 bucket as being in the domain of the random search. Also, we don't want 32 to annoy clients who know their tables are non-empty with needless 33 checks for end(). 34 35 * wtf/RandomNumber.cpp: 36 (WTF::weakRandomUint32): 37 * wtf/RandomNumber.h: Added a free function for weak random numbers so 38 that clients that want cheap random numbers aren't required to allocate 39 storage for a WeakRandom generator. 40 1 41 2018-10-24 Megan Gardner <megan_gardner@apple.com> 2 42 -
trunk/Source/WTF/wtf/HashCountedSet.h
r223617 r237419 70 70 const_iterator end() const; 71 71 72 iterator random() { return m_impl.random(); } 73 const_iterator random() const { return m_impl.random(); } 74 72 75 ValuesIteratorRange values(); 73 76 const ValuesConstIteratorRange values() const; -
trunk/Source/WTF/wtf/HashMap.h
r237099 r237419 99 99 const_iterator end() const; 100 100 101 iterator random() { return m_impl.random(); } 102 const_iterator random() const { return m_impl.random(); } 103 101 104 KeysIteratorRange keys() { return makeSizedIteratorRange(*this, begin().keys(), end().keys()); } 102 105 const KeysConstIteratorRange keys() const { return makeSizedIteratorRange(*this, begin().keys(), end().keys()); } -
trunk/Source/WTF/wtf/HashSet.h
r237099 r237419 69 69 iterator end() const; 70 70 71 iterator random() { return m_impl.random(); } 72 const_iterator random() const { return m_impl.random(); } 73 71 74 iterator find(const ValueType&) const; 72 75 bool contains(const ValueType&) const; -
trunk/Source/WTF/wtf/HashTable.h
r234879 r237419 33 33 #include <wtf/Lock.h> 34 34 #include <wtf/MathExtras.h> 35 #include <wtf/RandomNumber.h> 35 36 #include <wtf/StdLibExtras.h> 36 37 #include <wtf/ValueCheck.h> … … 379 380 const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); } 380 381 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); } 382 383 iterator random() 384 { 385 if (isEmpty()) 386 return end(); 387 auto it = makeIterator(m_table + (weakRandomUint32() & m_tableSizeMask)); 388 if (it == end()) 389 return begin(); 390 return it; 391 } 392 393 const_iterator random() const { return const_cast<HashTable*>(this)->random().const_iterator(); } 381 394 382 395 unsigned size() const { return m_keyCount; } -
trunk/Source/WTF/wtf/ListHashSet.h
r223617 r237419 88 88 const_iterator end() const { return makeConstIterator(nullptr); } 89 89 90 iterator random() { return makeIterator(m_impl.random()); } 91 const_iterator random() const { return makeIterator(m_impl.random()); } 92 90 93 reverse_iterator rbegin() { return reverse_iterator(end()); } 91 94 reverse_iterator rend() { return reverse_iterator(begin()); } -
trunk/Source/WTF/wtf/LoggingHashMap.h
r235841 r237419 101 101 const_iterator begin() const { return m_map.begin(); } 102 102 const_iterator end() const { return m_map.end(); } 103 104 iterator random() { return m_map.random(); } 105 const_iterator random() const { return m_map.random(); } 103 106 104 107 auto keys() { return m_map.keys(); } -
trunk/Source/WTF/wtf/LoggingHashSet.h
r213939 r237419 101 101 iterator end() const { return m_set.end(); } 102 102 103 iterator random() { return m_set.random(); } 104 const_iterator random() const { return m_set.random(); } 105 103 106 iterator find(const ValueType& value) const 104 107 { -
trunk/Source/WTF/wtf/RandomNumber.cpp
r237099 r237419 35 35 #include <wtf/CryptographicallyRandomNumber.h> 36 36 #include <wtf/RandomNumberSeed.h> 37 #include <wtf/WeakRandom.h> 37 38 38 39 namespace WTF { … … 44 45 } 45 46 47 unsigned weakRandomUint32() 48 { 49 // We don't care about thread safety. WeakRandom just uses POD types, 50 // and racy access just increases randomness. 51 static WeakRandom s_weakRandom; 52 return s_weakRandom.getUint32(); 46 53 } 54 55 } -
trunk/Source/WTF/wtf/RandomNumber.h
r237099 r237419 28 28 namespace WTF { 29 29 30 // Returns a pseudo-random number in the range [0, 1), attempts to be 31 // cryptographically secure if possible on the target platform 30 // Returns a cryptographically secure pseudo-random number in the range [0, 1). 32 31 WTF_EXPORT_PRIVATE double randomNumber(); 32 33 // Returns a cheap pseudo-random number in the range (0, UINT_MAX]. 34 WTF_EXPORT_PRIVATE unsigned weakRandomUint32(); 33 35 34 36 } 35 37 36 38 using WTF::randomNumber; 39 using WTF::weakRandomUint32; -
trunk/Tools/ChangeLog
r237407 r237419 1 2018-10-25 Geoffrey Garen <ggaren@apple.com> 2 3 HashMap should support selecting a random entry 4 https://bugs.webkit.org/show_bug.cgi?id=190814 5 6 Reviewed by Antti Koivisto. 7 8 Unit testing is fun and easy! 9 10 * TestWebKitAPI/Tests/WTF/HashMap.cpp: 11 (TestWebKitAPI::ZeroHash::hash): 12 (TestWebKitAPI::TEST): 13 1 14 2018-10-24 Tim Horton <timothy_horton@apple.com> 2 15 -
trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp
r234879 r237419 70 70 } 71 71 72 template<typename T> struct BigTableHashTraits : public HashTraits<T> { 73 static const int minimumTableSize = WTF::HashTableCapacityForSize<4096>::value; 74 }; 75 76 template<typename T> struct ZeroHash : public IntHash<T> { 77 static unsigned hash(const T&) { return 0; } 78 }; 79 72 80 TEST(WTF_HashMap, DoubleHashCollisions) 73 81 { … … 989 997 } 990 998 999 TEST(WTF_HashMap, Random_Empty) 1000 { 1001 HashMap<unsigned, unsigned> map; 1002 1003 auto result = map.random(); 1004 ASSERT_EQ(result, map.end()); 1005 } 1006 1007 TEST(WTF_HashMap, Random_WrapAround) 1008 { 1009 HashMap<unsigned, unsigned, ZeroHash<unsigned>, BigTableHashTraits<unsigned>> map; 1010 map.add(1, 1); 1011 1012 auto result = map.random(); 1013 ASSERT_EQ(result, map.begin()); 1014 } 1015 1016 TEST(WTF_HashMap, Random_IsRandom) 1017 { 1018 HashMap<unsigned, unsigned> map; 1019 map.add(1, 1); 1020 map.add(2, 2); 1021 1022 unsigned ones = 0; 1023 unsigned twos = 0; 1024 1025 for (unsigned i = 0; i < 100; ++i) { 1026 auto it = map.random(); 1027 if (it->value == 1) 1028 ++ones; 1029 else { 1030 ASSERT_EQ(it->value, 2u); 1031 ++twos; 1032 } 1033 } 1034 1035 ASSERT_EQ(ones + twos, 100u); 1036 ASSERT_LE(ones, 99u); 1037 ASSERT_LE(twos, 99u); 1038 } 1039 991 1040 } // namespace TestWebKitAPI
Note: See TracChangeset
for help on using the changeset viewer.