Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(269)

Side by Side Diff: Source/wtf/BloomFilter.h

Issue 20300002: Fix trailing whitespace in .cpp, .h, and .idl files (ex. Source/core) (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/wtf/BitVector.cpp ('k') | Source/wtf/CheckedArithmetic.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2011 Apple Inc. All rights reserved. 2 * Copyright (C) 2011 Apple Inc. All rights reserved.
3 * 3 *
4 * Redistribution and use in source and binary forms, with or without 4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions 5 * modification, are permitted provided that the following conditions
6 * are met: 6 * are met:
7 * 1. Redistributions of source code must retain the above copyright 7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer. 8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright 9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the 10 * notice, this list of conditions and the following disclaimer in the
(...skipping 14 matching lines...) Expand all
25 25
26 #ifndef BloomFilter_h 26 #ifndef BloomFilter_h
27 #define BloomFilter_h 27 #define BloomFilter_h
28 28
29 #include "wtf/Compiler.h" 29 #include "wtf/Compiler.h"
30 #include "wtf/text/AtomicString.h" 30 #include "wtf/text/AtomicString.h"
31 31
32 namespace WTF { 32 namespace WTF {
33 33
34 // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of me mory. 34 // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of me mory.
35 // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number o f unique 35 // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number o f unique
36 // keys and m is the table size (==2^keyBits). 36 // keys and m is the table size (==2^keyBits).
37 template <unsigned keyBits> 37 template <unsigned keyBits>
38 class BloomFilter { 38 class BloomFilter {
39 public: 39 public:
40 COMPILE_ASSERT(keyBits <= 16, bloom_filter_key_size); 40 COMPILE_ASSERT(keyBits <= 16, bloom_filter_key_size);
41 41
42 static const size_t tableSize = 1 << keyBits; 42 static const size_t tableSize = 1 << keyBits;
43 static const unsigned keyMask = (1 << keyBits) - 1; 43 static const unsigned keyMask = (1 << keyBits) - 1;
44 static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max(); } 44 static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max(); }
45 45
46 BloomFilter() { clear(); } 46 BloomFilter() { clear(); }
47 47
48 void add(unsigned hash); 48 void add(unsigned hash);
49 void remove(unsigned hash); 49 void remove(unsigned hash);
50 50
51 // The filter may give false positives (claim it may contain a key it doesn' t) 51 // The filter may give false positives (claim it may contain a key it doesn' t)
52 // but never false negatives (claim it doesn't contain a key it does). 52 // but never false negatives (claim it doesn't contain a key it does).
53 bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot( hash); } 53 bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot( hash); }
54 54
55 // The filter must be cleared before reuse even if all keys are removed. 55 // The filter must be cleared before reuse even if all keys are removed.
56 // Otherwise overflowed keys will stick around. 56 // Otherwise overflowed keys will stick around.
57 void clear(); 57 void clear();
58 58
59 void add(const AtomicString& string) { add(string.impl()->existingHash()); } 59 void add(const AtomicString& string) { add(string.impl()->existingHash()); }
60 void add(const String& string) { add(string.impl()->hash()); } 60 void add(const String& string) { add(string.impl()->hash()); }
61 void remove(const AtomicString& string) { remove(string.impl()->existingHash ()); } 61 void remove(const AtomicString& string) { remove(string.impl()->existingHash ()); }
62 void remove(const String& string) { remove(string.impl()->hash()); } 62 void remove(const String& string) { remove(string.impl()->hash()); }
63 63
64 bool mayContain(const AtomicString& string) const { return mayContain(string .impl()->existingHash()); } 64 bool mayContain(const AtomicString& string) const { return mayContain(string .impl()->existingHash()); }
65 bool mayContain(const String& string) const { return mayContain(string.impl( )->hash()); } 65 bool mayContain(const String& string) const { return mayContain(string.impl( )->hash()); }
66 66
67 #if !ASSERT_DISABLED 67 #if !ASSERT_DISABLED
68 // Slow. 68 // Slow.
69 bool likelyEmpty() const; 69 bool likelyEmpty() const;
70 bool isClear() const; 70 bool isClear() const;
71 #endif 71 #endif
72 72
73 private: 73 private:
74 uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; } 74 uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; }
75 uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask]; } 75 uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask]; }
76 const uint8_t& firstSlot(unsigned hash) const { return m_table[hash & keyMas k]; } 76 const uint8_t& firstSlot(unsigned hash) const { return m_table[hash & keyMas k]; }
77 const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16) & keyMask]; } 77 const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16) & keyMask]; }
78 78
79 uint8_t m_table[tableSize]; 79 uint8_t m_table[tableSize];
80 }; 80 };
81 81
82 template <unsigned keyBits> 82 template <unsigned keyBits>
83 inline void BloomFilter<keyBits>::add(unsigned hash) 83 inline void BloomFilter<keyBits>::add(unsigned hash)
84 { 84 {
85 uint8_t& first = firstSlot(hash); 85 uint8_t& first = firstSlot(hash);
86 uint8_t& second = secondSlot(hash); 86 uint8_t& second = secondSlot(hash);
87 if (LIKELY(first < maximumCount())) 87 if (LIKELY(first < maximumCount()))
88 ++first; 88 ++first;
89 if (LIKELY(second < maximumCount())) 89 if (LIKELY(second < maximumCount()))
90 ++second; 90 ++second;
91 } 91 }
92 92
93 template <unsigned keyBits> 93 template <unsigned keyBits>
94 inline void BloomFilter<keyBits>::remove(unsigned hash) 94 inline void BloomFilter<keyBits>::remove(unsigned hash)
95 { 95 {
96 uint8_t& first = firstSlot(hash); 96 uint8_t& first = firstSlot(hash);
97 uint8_t& second = secondSlot(hash); 97 uint8_t& second = secondSlot(hash);
98 ASSERT(first); 98 ASSERT(first);
99 ASSERT(second); 99 ASSERT(second);
100 // In case of an overflow, the slot sticks in the table until clear(). 100 // In case of an overflow, the slot sticks in the table until clear().
101 if (LIKELY(first < maximumCount())) 101 if (LIKELY(first < maximumCount()))
102 --first; 102 --first;
103 if (LIKELY(second < maximumCount())) 103 if (LIKELY(second < maximumCount()))
104 --second; 104 --second;
105 } 105 }
106 106
107 template <unsigned keyBits> 107 template <unsigned keyBits>
108 inline void BloomFilter<keyBits>::clear() 108 inline void BloomFilter<keyBits>::clear()
109 { 109 {
110 memset(m_table, 0, tableSize); 110 memset(m_table, 0, tableSize);
111 } 111 }
112 112
113 #if !ASSERT_DISABLED 113 #if !ASSERT_DISABLED
114 template <unsigned keyBits> 114 template <unsigned keyBits>
115 bool BloomFilter<keyBits>::likelyEmpty() const 115 bool BloomFilter<keyBits>::likelyEmpty() const
116 { 116 {
(...skipping 13 matching lines...) Expand all
130 } 130 }
131 return true; 131 return true;
132 } 132 }
133 #endif 133 #endif
134 134
135 } 135 }
136 136
137 using WTF::BloomFilter; 137 using WTF::BloomFilter;
138 138
139 #endif 139 #endif
OLDNEW
« no previous file with comments | « Source/wtf/BitVector.cpp ('k') | Source/wtf/CheckedArithmetic.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698