Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code

Delta Between Two Patch Sets: compiled/StringMap.h

Issue 29333474: Issue 4125 - [emscripten] Convert filter classes to C++ (Closed)
Left Patch Set: Rebased, addressed comments, changed StringMap::find() return value Created Feb. 18, 2016, 4:02 p.m.
Right Patch Set: Addressed comments from Patch Set 28 Created March 21, 2017, 10:04 a.m.
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « compiled/String.h ('k') | compiled/StringScanner.h » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
1 #pragma once 1 #pragma once
2 2
3 #include <cstddef> 3 #include <cstddef>
4 #include <cmath> 4 #include <cmath>
5 #include <initializer_list> 5 #include <initializer_list>
6 #include <memory> 6 #include <memory>
7 7
8 #include "String.h" 8 #include "String.h"
9 #include "debug.h" 9 #include "debug.h"
10 10
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
56 { 56 {
57 return mPos != it.mPos; 57 return mPos != it.mPos;
58 } 58 }
59 }; 59 };
60 60
61 template<typename Entry> 61 template<typename Entry>
62 struct HashContainerReference 62 struct HashContainerReference
63 { 63 {
64 typedef Entry entry_type; 64 typedef Entry entry_type;
65 65
66 const entry_type* mEntry; 66 entry_type* mEntry;
67 67
68 explicit HashContainerReference(const entry_type* entry) 68 explicit HashContainerReference(entry_type* entry)
69 : mEntry(entry) 69 : mEntry(entry)
70 { 70 {
71 } 71 }
72 72
73 const entry_type* operator->() const 73 const entry_type* operator->() const
74 { 74 {
75 return mEntry; 75 return mEntry;
76 } 76 }
77 77
78 operator bool() const 78 operator bool() const
79 { 79 {
80 return !mEntry->first.is_invalid(); 80 return !mEntry->first.is_invalid();
81 } 81 }
82 }; 82 };
83 83
84 template<typename Entry> 84 template<typename Entry>
85 class HashContainer 85 class HashContainer
86 { 86 {
87 public: 87 public:
88 typedef Entry entry_type; 88 typedef Entry entry_type;
89 typedef size_t size_type; 89 typedef size_t size_type;
90 typedef HashContainerIterator<Entry> const_iterator; 90 typedef HashContainerIterator<Entry> const_iterator;
91 typedef HashContainerReference<Entry> const_reference; 91 typedef HashContainerReference<const Entry> const_reference;
92 92
93 private: 93 private:
94 HashContainer(const HashContainer& other); 94 explicit HashContainer(const HashContainer& other);
95 void operator=(const HashContainer& other); 95 void operator=(const HashContainer& other);
96 96
97 protected: 97 protected:
98 static constexpr size_type MIN_BUCKETS = 1; 98 static constexpr size_type MIN_BUCKETS = 1;
99 static constexpr double LOAD_FACTOR = 0.8; 99 static constexpr double LOAD_FACTOR = 0.8;
100 std::unique_ptr<entry_type[]> mBuckets; 100 std::unique_ptr<entry_type[]> mBuckets;
101 size_type mBucketCount; 101 size_type mBucketCount;
102 size_type mEntryCount; 102 size_type mEntryCount;
103 103
104 #if defined(DEBUG)
105 size_type mInsertCounter;
106 #endif
107
104 explicit HashContainer(size_type expectedEntries = 0) 108 explicit HashContainer(size_type expectedEntries = 0)
105 : mEntryCount(0) 109 : mEntryCount(0)
106 { 110 {
107 expectedEntries = ceil(expectedEntries / LOAD_FACTOR); 111 expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
108 mBucketCount = MIN_BUCKETS; 112 mBucketCount = MIN_BUCKETS;
109 while (mBucketCount < expectedEntries) 113 while (mBucketCount < expectedEntries)
110 mBucketCount <<= 1; 114 mBucketCount <<= 1;
111 115
112 mBuckets.reset(new entry_type[mBucketCount]); 116 mBuckets.reset(new entry_type[mBucketCount]);
113 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here 117 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
(...skipping 12 matching lines...) Expand all
126 entry_type* find_bucket(const String& key) const 130 entry_type* find_bucket(const String& key) const
127 { 131 {
128 size_type h = hash(key); 132 size_type h = hash(key);
129 133
130 // This does quadratic probing, effectively the following formula is used: 134 // This does quadratic probing, effectively the following formula is used:
131 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount 135 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
132 for (size_type i = 0; ; ++i) 136 for (size_type i = 0; ; ++i)
133 { 137 {
134 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to 138 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
135 // h % mBucketCount but significantly faster. 139 // h % mBucketCount but significantly faster.
136 entry_type* entry = &mBuckets[h & mBucketCount - 1]; 140 entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
137 if (entry->first.is_invalid() || entry->first.equals(key)) 141 if (entry->first.is_invalid() || entry->first.equals(key))
138 return entry; 142 return entry;
139 h += i; 143 h += i;
140 } 144 }
141 } 145 }
142 146
143 void resize(size_type bucketCount) 147 void resize(size_type bucketCount)
144 { 148 {
145 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets)); 149 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets));
146 size_type oldCount = mBucketCount; 150 size_type oldCount = mBucketCount;
147 151
148 mEntryCount = 0; 152 mEntryCount = 0;
149 mBucketCount = bucketCount; 153 mBucketCount = bucketCount;
150 mBuckets.reset(new entry_type[mBucketCount]); 154 mBuckets.reset(new entry_type[mBucketCount]);
151 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here 155 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
152 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer"); 156 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
153 157
154 // Copy old entries into the new buffer 158 // Copy old entries into the new buffer
155 for (size_type i = 0; i < oldCount; i++) 159 for (size_type i = 0; i < oldCount; i++)
156 { 160 {
157 entry_type& entry = oldBuckets[i]; 161 entry_type& entry = oldBuckets[i];
158 if (!entry.first.is_invalid()) 162 if (!entry.first.is_invalid() && !entry.first.is_deleted())
159 { 163 {
160 *find_bucket(entry.first) = entry; 164 *find_bucket(entry.first) = entry;
161 mEntryCount++; 165 mEntryCount++;
162 } 166 }
163 } 167 }
164 } 168 }
165 169
166 entry_type* assign(entry_type* existing, const entry_type& entry) 170 entry_type* assign(entry_type* existing, const entry_type& entry)
167 { 171 {
168 if (existing->first.is_invalid()) 172 if (existing->first.is_invalid())
169 { 173 {
170 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) 174 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
171 { 175 {
172 resize(mBucketCount << 1); 176 resize(mBucketCount << 1);
173 existing = find_bucket(entry.first); 177 existing = find_bucket(entry.first);
174 } 178 }
175 mEntryCount++; 179 mEntryCount++;
180 #if defined(DEBUG)
181 mInsertCounter++;
182 #endif
176 } 183 }
177 *existing = entry; 184 *existing = entry;
178 return existing; 185 return existing;
179 } 186 }
180 187
181 public: 188 public:
182 void insert(const entry_type& entry) 189 void insert(const entry_type& entry)
183 { 190 {
184 assign(find_bucket(entry.first), entry); 191 assign(find_bucket(entry.first), entry);
185 } 192 }
186 193
194 bool erase(const String& key)
195 {
196 entry_type* entry = find_bucket(key);
197 if (entry->first.is_invalid())
198 return false;
199
200 entry->first.erase();
201 return true;
202 }
203
187 const_reference find(const String& key) const 204 const_reference find(const String& key) const
188 { 205 {
189 return const_reference(find_bucket(key)); 206 return const_reference(find_bucket(key));
190 } 207 }
191 208
192 const_iterator begin() const 209 const_iterator begin() const
193 { 210 {
194 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]); 211 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
195 } 212 }
196 213
(...skipping 12 matching lines...) Expand all
209 } 226 }
210 227
211 DependentString first; 228 DependentString first;
212 }; 229 };
213 230
214 template<typename T> 231 template<typename T>
215 struct StringMapEntry 232 struct StringMapEntry
216 { 233 {
217 StringMapEntry() {} 234 StringMapEntry() {}
218 StringMapEntry(const String& key) 235 StringMapEntry(const String& key)
219 : first(key) 236 : first(key), second()
220 { 237 {
221 } 238 }
222 StringMapEntry(const String& key, T value) 239 StringMapEntry(const String& key, T value)
223 : first(key), second(value) 240 : first(key), second(value)
224 { 241 {
225 } 242 }
226 243
227 DependentString first; 244 DependentString first;
228 T second; 245 T second;
229 }; 246 };
230 247
231 template<typename T> 248 template<typename T>
232 struct StringMapEntryReference : public HashContainerReference<StringMapEntry< T>> 249 struct StringMapEntryReference : public HashContainerReference<StringMapEntry< T>>
233 { 250 {
234 typedef HashContainerReference<StringMapEntry<T>> super; 251 typedef HashContainerReference<StringMapEntry<T>> super;
235 typedef typename super::entry_type entry_type; 252 typedef typename super::entry_type entry_type;
236 typedef StringMap<T> map_type; 253 typedef StringMap<T> map_type;
237 254
238 map_type* mMap; 255 map_type* mMap;
239 256
240 StringMapEntryReference(map_type* map, const entry_type* entry) 257 #if defined(DEBUG)
258 typename map_type::size_type mInsertCounter;
259 typename map_type::size_type mHash;
260 #endif
261
262 StringMapEntryReference(map_type* map, const String& key, entry_type* entry)
241 : super(entry), mMap(map) 263 : super(entry), mMap(map)
242 { 264 {
265 #if defined(DEBUG)
266 mInsertCounter = mMap->mInsertCounter;
267 mHash = mMap->hash(key);
268 #endif
243 } 269 }
244 270
245 void assign(const String& key, const T& value) 271 void assign(const String& key, const T& value)
sergei 2016/02/22 12:46:03 I have noticed a couple of asserts here in the rep
Wladimir Palant 2016/02/23 12:37:36 As explained under https://codereview.adblockplus.
246 { 272 {
247 mMap->assign(const_cast<entry_type*>(super::mEntry), entry_type(key, value )); 273 #if defined(DEBUG)
sergei 2016/02/22 12:46:02 `super::mEntry` is also accessible by `this->mEntr
sergei 2016/02/22 12:46:05 It's not necessary to use `const_cast` here. We ca
Wladimir Palant 2016/02/23 12:37:34 Done.
Wladimir Palant 2016/02/23 12:37:37 Done.
274 assert(mInsertCounter == mMap->mInsertCounter,
275 u"There should be no insert operations performed between map.find() an d assign()"_str);
276 assert(mHash == mMap->hash(key),
277 u"The keys used in map.find() and assign() should be identical"_str);
278 #endif
279
280 mMap->assign(this->mEntry, entry_type(key, value));
248 } 281 }
249 }; 282 };
250 } 283 }
251 284
252 class StringSet 285 class StringSet
253 : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry> 286 : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry>
254 { 287 {
255 }; 288 };
256 289
257 template<typename T> 290 template<typename T>
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
290 return entry->second; 323 return entry->second;
291 } 324 }
292 325
293 const_reference find(const String& key) const 326 const_reference find(const String& key) const
294 { 327 {
295 return super::find(key); 328 return super::find(key);
296 } 329 }
297 330
298 reference find(const String& key) 331 reference find(const String& key)
299 { 332 {
300 return reference(this, super::find_bucket(key)); 333 return reference(this, key, super::find_bucket(key));
301 } 334 }
302 }; 335 };
LEFTRIGHT

Powered by Google App Engine
This is Rietveld