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

Side by Side Diff: compiled/Map.h

Issue 29572731: Issue 5141 - Generalize Map class to allow non-strings as keys (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore
Patch Set: Introduced key_type_cref Created Dec. 4, 2017, 1:43 p.m.
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View unified diff | Download patch
OLDNEW
1 /* 1 /*
2 * This file is part of Adblock Plus <https://adblockplus.org/>, 2 * This file is part of Adblock Plus <https://adblockplus.org/>,
3 * Copyright (C) 2006-present eyeo GmbH 3 * Copyright (C) 2006-present eyeo GmbH
4 * 4 *
5 * Adblock Plus is free software: you can redistribute it and/or modify 5 * Adblock Plus is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 3 as 6 * it under the terms of the GNU General Public License version 3 as
7 * published by the Free Software Foundation. 7 * published by the Free Software Foundation.
8 * 8 *
9 * Adblock Plus is distributed in the hope that it will be useful, 9 * Adblock Plus is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details. 12 * GNU General Public License for more details.
13 * 13 *
14 * You should have received a copy of the GNU General Public License 14 * You should have received a copy of the GNU General Public License
15 * along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>. 15 * along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>.
16 */ 16 */
17 17
18 #pragma once 18 #pragma once
19 19
20 #include <cstddef>
21 #include <cmath> 20 #include <cmath>
22 #include <initializer_list> 21 #include <initializer_list>
23 #include <memory> 22 #include <memory>
24 23
24 #include "debug.h"
25 #include "String.h" 25 #include "String.h"
26 #include "debug.h"
27 26
28 template<typename T> 27 template<typename Entry>
29 class StringMap; 28 class Map;
30 29
31 namespace StringMap_internal 30 namespace Map_internal
32 { 31 {
33 template<typename Entry> 32 template<typename Entry>
34 struct HashContainerIterator 33 struct HashContainerIterator
35 { 34 {
36 typedef Entry entry_type; 35 typedef Entry entry_type;
37 typedef HashContainerIterator<Entry> iterator; 36 typedef HashContainerIterator<Entry> iterator;
38 37
39 const entry_type* mPos; 38 const entry_type* mPos;
40 const entry_type* mEnd; 39 const entry_type* mEnd;
41 40
42 explicit HashContainerIterator(const entry_type* start, const entry_type* en d) 41 explicit HashContainerIterator(const entry_type* start, const entry_type* en d)
43 : mPos(start), mEnd(end) 42 : mPos(start), mEnd(end)
44 { 43 {
45 if (mPos != mEnd && mPos->first.is_invalid()) 44 if (mPos != mEnd && mPos->is_invalid())
46 ++(*this); 45 ++(*this);
47 } 46 }
48 47
49 const entry_type& operator*() const 48 const entry_type& operator*() const
50 { 49 {
51 return *mPos; 50 return *mPos;
52 } 51 }
53 52
54 const entry_type* operator->() const 53 const entry_type* operator->() const
55 { 54 {
56 return mPos; 55 return mPos;
57 } 56 }
58 57
59 iterator& operator++() 58 iterator& operator++()
60 { 59 {
61 do { 60 do {
62 ++mPos; 61 ++mPos;
63 } while(mPos != mEnd && mPos->first.is_invalid()); 62 } while(mPos != mEnd && mPos->is_invalid());
64 return *this; 63 return *this;
65 } 64 }
66 65
67 bool operator==(const iterator& it) const 66 bool operator==(const iterator& it) const
68 { 67 {
69 return mPos == it.mPos; 68 return mPos == it.mPos;
70 } 69 }
71 70
72 bool operator!=(const iterator& it) const 71 bool operator!=(const iterator& it) const
73 { 72 {
(...skipping 13 matching lines...) Expand all
87 { 86 {
88 } 87 }
89 88
90 const entry_type* operator->() const 89 const entry_type* operator->() const
91 { 90 {
92 return mEntry; 91 return mEntry;
93 } 92 }
94 93
95 operator bool() const 94 operator bool() const
96 { 95 {
97 return !mEntry->first.is_invalid(); 96 return !mEntry->is_invalid();
98 } 97 }
99 }; 98 };
100 99
101 template<typename Entry> 100 template<typename Entry>
102 class HashContainer 101 class HashContainer
103 { 102 {
104 public: 103 public:
105 typedef Entry entry_type; 104 typedef Entry entry_type;
106 typedef size_t size_type; 105 typedef typename Entry::key_type_cref key_type_cref;
106 typedef typename entry_type::size_type size_type;
107 typedef HashContainerIterator<Entry> const_iterator; 107 typedef HashContainerIterator<Entry> const_iterator;
108 typedef HashContainerReference<const Entry> const_reference; 108 typedef HashContainerReference<const Entry> const_reference;
109 109
110 private: 110 private:
111 explicit HashContainer(const HashContainer& other); 111 explicit HashContainer(const HashContainer& other);
112 void operator=(const HashContainer& other); 112 void operator=(const HashContainer& other);
113 113
114 protected: 114 protected:
115 static constexpr size_type MIN_BUCKETS = 1; 115 static constexpr size_type MIN_BUCKETS = 1;
116 static constexpr double LOAD_FACTOR = 0.8; 116 static constexpr double LOAD_FACTOR = 0.8;
117 std::unique_ptr<entry_type[]> mBuckets; 117 std::unique_ptr<entry_type[]> mBuckets;
118 size_type mBucketCount; 118 size_type mBucketCount;
119 size_type mEntryCount; 119 size_type mEntryCount;
120 120
121 #if defined(DEBUG) 121 #if defined(DEBUG)
122 size_type mInsertCounter; 122 size_type mInsertCounter;
123 #endif 123 #endif
124 124
125 explicit HashContainer(size_type expectedEntries = 0) 125 entry_type* find_bucket(key_type_cref key) const
126 : mEntryCount(0)
127 { 126 {
128 expectedEntries = ceil(expectedEntries / LOAD_FACTOR); 127 size_type h = entry_type::hash(key);
129 mBucketCount = MIN_BUCKETS;
130 while (mBucketCount < expectedEntries)
131 mBucketCount <<= 1;
132
133 mBuckets.reset(new entry_type[mBucketCount]);
134 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
135 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
136 }
137
138 static size_type hash(const String& str)
139 {
140 // FNV-1a hash function
141 size_type result = 2166136261;
142 for (String::size_type i = 0; i < str.length(); i++)
143 result = (result ^ str[i]) * 16777619;
144 return result;
145 }
146
147 entry_type* find_bucket(const String& key) const
148 {
149 size_type h = hash(key);
150 128
151 // This does quadratic probing, effectively the following formula is used: 129 // This does quadratic probing, effectively the following formula is used:
152 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount 130 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
153 for (size_type i = 0; ; ++i) 131 for (size_type i = 0; ; ++i)
154 { 132 {
155 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to 133 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
156 // h % mBucketCount but significantly faster. 134 // h % mBucketCount but significantly faster.
157 entry_type* entry = &mBuckets[h & (mBucketCount - 1)]; 135 entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
158 if (entry->first.is_invalid() || entry->first.equals(key)) 136 if (entry->is_invalid() || entry->equals(key))
159 return entry; 137 return entry;
160 h += i; 138 h += i;
161 } 139 }
162 } 140 }
163 141
164 void resize(size_type bucketCount) 142 void resize(size_type bucketCount)
165 { 143 {
166 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets)); 144 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets));
167 size_type oldCount = mBucketCount; 145 size_type oldCount = mBucketCount;
168 146
169 mEntryCount = 0; 147 mEntryCount = 0;
170 mBucketCount = bucketCount; 148 mBucketCount = bucketCount;
171 mBuckets.reset(new entry_type[mBucketCount]); 149 mBuckets.reset(new entry_type[mBucketCount]);
172 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here 150 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
173 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer"); 151 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
174 152
175 // Copy old entries into the new buffer 153 // Copy old entries into the new buffer
176 for (size_type i = 0; i < oldCount; i++) 154 for (size_type i = 0; i < oldCount; i++)
177 { 155 {
178 entry_type& entry = oldBuckets[i]; 156 entry_type& entry = oldBuckets[i];
179 if (!entry.first.is_invalid() && !entry.first.is_deleted()) 157 if (!entry.is_invalid() && !entry.is_deleted())
180 { 158 {
181 *find_bucket(entry.first) = entry; 159 *find_bucket(entry.first) = entry;
182 mEntryCount++; 160 mEntryCount++;
183 } 161 }
184 } 162 }
185 } 163 }
186 164
187 entry_type* assign(entry_type* existing, const entry_type& entry) 165 entry_type* assign(entry_type* existing, const entry_type& entry)
188 { 166 {
189 if (existing->first.is_invalid()) 167 if (existing->is_invalid())
190 { 168 {
191 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) 169 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
192 { 170 {
193 resize(mBucketCount << 1); 171 resize(mBucketCount << 1);
194 existing = find_bucket(entry.first); 172 existing = find_bucket(entry.first);
195 } 173 }
196 mEntryCount++; 174 mEntryCount++;
197 #if defined(DEBUG) 175 #if defined(DEBUG)
198 mInsertCounter++; 176 mInsertCounter++;
199 #endif 177 #endif
200 } 178 }
201 *existing = entry; 179 *existing = entry;
202 return existing; 180 return existing;
203 } 181 }
204 182
205 public: 183 public:
184 explicit HashContainer(size_type expectedEntries = 0)
185 : mEntryCount(0)
186 {
187 expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
188 mBucketCount = MIN_BUCKETS;
189 while (mBucketCount < expectedEntries)
190 mBucketCount <<= 1;
191
192 mBuckets.reset(new entry_type[mBucketCount]);
193 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
194 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
195 }
196
206 void insert(const entry_type& entry) 197 void insert(const entry_type& entry)
207 { 198 {
208 assign(find_bucket(entry.first), entry); 199 assign(find_bucket(entry.first), entry);
209 } 200 }
210 201
211 bool erase(const String& key) 202 bool erase(key_type_cref key)
212 { 203 {
213 entry_type* entry = find_bucket(key); 204 entry_type* entry = find_bucket(key);
214 if (entry->first.is_invalid()) 205 if (entry->is_invalid())
215 return false; 206 return false;
216 207
217 entry->first.erase(); 208 entry->erase();
218 return true; 209 return true;
219 } 210 }
220 211
221 const_reference find(const String& key) const 212 const_reference find(key_type_cref key) const
222 { 213 {
223 return const_reference(find_bucket(key)); 214 return const_reference(find_bucket(key));
224 } 215 }
225 216
226 const_iterator begin() const 217 const_iterator begin() const
227 { 218 {
228 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]); 219 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
229 } 220 }
230 221
231 const_iterator end() const 222 const_iterator end() const
232 { 223 {
233 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]); 224 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]);
234 } 225 }
235 226
236 size_type size() const 227 size_type size() const
237 { 228 {
238 return mEntryCount; 229 return mEntryCount;
239 } 230 }
240 }; 231 };
241 232
242 struct StringSetEntry 233 template<typename Entry>
234 struct MapReference : public HashContainerReference<Entry>
243 { 235 {
244 StringSetEntry() {} 236 typedef HashContainerReference<Entry> super;
245 StringSetEntry(const String& key)
246 : first(key)
247 {
248 }
249
250 DependentString first;
251 };
252
253 template<typename T>
254 struct StringMapEntry
255 {
256 StringMapEntry() {}
257 StringMapEntry(const String& key)
258 : first(key), second()
259 {
260 }
261 StringMapEntry(const String& key, T value)
262 : first(key), second(value)
263 {
264 }
265
266 DependentString first;
267 T second;
268 };
269
270 template<typename T>
271 struct StringMapEntryReference : public HashContainerReference<StringMapEntry< T>>
272 {
273 typedef HashContainerReference<StringMapEntry<T>> super;
274 typedef typename super::entry_type entry_type; 237 typedef typename super::entry_type entry_type;
275 typedef StringMap<T> map_type; 238 typedef typename entry_type::key_type_cref key_type_cref;
239 typedef typename entry_type::value_type value_type;
240 typedef Map<entry_type> map_type;
276 241
277 map_type* mMap; 242 map_type* mMap;
278 243
279 #if defined(DEBUG) 244 #if defined(DEBUG)
280 typename map_type::size_type mInsertCounter; 245 typename map_type::size_type mInsertCounter;
281 typename map_type::size_type mHash; 246 typename map_type::size_type mHash;
282 #endif 247 #endif
283 248
284 StringMapEntryReference(map_type* map, const String& key, entry_type* entry) 249 MapReference(map_type* map, key_type_cref key, entry_type* entry)
285 : super(entry), mMap(map) 250 : super(entry), mMap(map)
286 { 251 {
287 #if defined(DEBUG) 252 #if defined(DEBUG)
288 mInsertCounter = mMap->mInsertCounter; 253 mInsertCounter = mMap->mInsertCounter;
289 mHash = mMap->hash(key); 254 mHash = entry_type::hash(key);
290 #endif 255 #endif
291 } 256 }
292 257
293 void assign(const String& key, const T& value) 258 void assign(key_type_cref key, const value_type& value)
294 { 259 {
295 #if defined(DEBUG) 260 #if defined(DEBUG)
296 assert2(mInsertCounter == mMap->mInsertCounter, 261 assert2(mInsertCounter == mMap->mInsertCounter,
297 u"There should be no insert operations performed between map.find() an d assign()"_str); 262 u"There should be no insert operations performed between map.find() an d assign()"_str);
298 assert2(mHash == mMap->hash(key), 263 assert2(mHash == entry_type::hash(key),
299 u"The keys used in map.find() and assign() should be identical"_str); 264 u"The keys used in map.find() and assign() should be identical"_str);
300 #endif 265 #endif
301 266
302 mMap->assign(this->mEntry, entry_type(key, value)); 267 mMap->assign(this->mEntry, entry_type(key, value));
303 } 268 }
304 }; 269 };
305 } 270 }
306 271
307 class StringSet 272 template<typename Entry>
308 : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry> 273 using Set = Map_internal::HashContainer<Entry>;
309 {
310 };
311 274
312 template<typename T> 275 template<typename Entry>
313 class StringMap 276 class Map : public Map_internal::HashContainer<Entry>
314 : public StringMap_internal::HashContainer<StringMap_internal::StringMapEntry< T>>
315 { 277 {
316 public: 278 public:
317 typedef StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T >> super; 279 typedef Map_internal::HashContainer<Entry> super;
318 typedef typename super::size_type size_type; 280 typedef typename super::size_type size_type;
319 typedef typename super::entry_type entry_type; 281 typedef typename super::entry_type entry_type;
282 typedef typename super::key_type_cref key_type_cref;
283 typedef typename entry_type::value_type value_type;
320 typedef typename super::const_reference const_reference; 284 typedef typename super::const_reference const_reference;
321 typedef StringMap_internal::StringMapEntryReference<T> reference; 285 typedef Map_internal::MapReference<entry_type> reference;
322 friend struct StringMap_internal::StringMapEntryReference<T>; 286 friend struct Map_internal::MapReference<entry_type>;
323 287
324 explicit StringMap(size_type expectedEntries = 0) 288 using super::super;
325 : super(expectedEntries)
326 {
327 }
328 289
329 StringMap(std::initializer_list<entry_type> list) 290 Map(std::initializer_list<entry_type> list)
330 : super(list.size()) 291 : super(list.size())
331 { 292 {
332 for (const auto& item : list) 293 for (const auto& item : list)
333 super::insert(item); 294 super::insert(item);
334 } 295 }
335 296
336 ~StringMap() 297 value_type& operator[](key_type_cref key)
337 {
338 }
339
340 T& operator[](const String& key)
341 { 298 {
342 entry_type* entry = super::find_bucket(key); 299 entry_type* entry = super::find_bucket(key);
343 if (entry->first.is_invalid()) 300 if (entry->is_invalid())
344 entry = super::assign(entry, key); 301 entry = super::assign(entry, key);
345 return entry->second; 302 return entry->second;
346 } 303 }
347 304
348 const_reference find(const String& key) const 305 const_reference find(key_type_cref key) const
349 { 306 {
350 return super::find(key); 307 return super::find(key);
351 } 308 }
352 309
353 reference find(const String& key) 310 reference find(key_type_cref key)
354 { 311 {
355 return reference(this, key, super::find_bucket(key)); 312 return reference(this, key, super::find_bucket(key));
356 } 313 }
357 }; 314 };
OLDNEW

Powered by Google App Engine
This is Rietveld