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

Delta Between Two Patch Sets: compiled/Map.h

Issue 29572731: Issue 5141 - Generalize Map class to allow non-strings as keys (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore
Left Patch Set: Created Oct. 10, 2017, 2:25 p.m.
Right Patch Set: Addressed remaining nits Created Dec. 4, 2017, 6:28 p.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/IntMap.h ('k') | compiled/StringMap.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 /* 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 <cmath> 20 #include <cmath>
21 #include <initializer_list> 21 #include <initializer_list>
22 #include <memory> 22 #include <memory>
23 23
24 #include "debug.h" 24 #include "debug.h"
25 25 #include "String.h"
26 template<typename Entry, typename Value> 26
27 template<typename Entry>
27 class Map; 28 class Map;
28 29
29 namespace Map_internal 30 namespace Map_internal
30 { 31 {
31 template<typename Entry> 32 template<typename Entry>
32 struct HashContainerIterator 33 struct HashContainerIterator
33 { 34 {
34 typedef Entry entry_type; 35 typedef Entry entry_type;
35 typedef HashContainerIterator<Entry> iterator; 36 typedef HashContainerIterator<Entry> iterator;
36 37
37 const entry_type* mPos; 38 const entry_type* mPos;
38 const entry_type* mEnd; 39 const entry_type* mEnd;
39 40
40 explicit HashContainerIterator(const entry_type* start, const entry_type* en d) 41 explicit HashContainerIterator(const entry_type* start, const entry_type* en d)
41 : mPos(start), mEnd(end) 42 : mPos(start), mEnd(end)
42 { 43 {
43 if (mPos != mEnd && mPos->is_invalid()) 44 if (mPos != mEnd && mPos->is_invalid())
Wladimir Palant 2017/10/10 14:33:58 I chose to implement operations working on keys wi
44 ++(*this); 45 ++(*this);
45 } 46 }
46 47
47 const entry_type& operator*() const 48 const entry_type& operator*() const
48 { 49 {
49 return *mPos; 50 return *mPos;
50 } 51 }
51 52
52 const entry_type* operator->() const 53 const entry_type* operator->() const
53 { 54 {
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after
94 { 95 {
95 return !mEntry->is_invalid(); 96 return !mEntry->is_invalid();
96 } 97 }
97 }; 98 };
98 99
99 template<typename Entry> 100 template<typename Entry>
100 class HashContainer 101 class HashContainer
101 { 102 {
102 public: 103 public:
103 typedef Entry entry_type; 104 typedef Entry entry_type;
104 typedef typename Entry::key_type key_type; 105 typedef typename Entry::key_type_cref key_type_cref;
105 typedef typename entry_type::size_type size_type; 106 typedef typename entry_type::size_type size_type;
106 typedef HashContainerIterator<Entry> const_iterator; 107 typedef HashContainerIterator<Entry> const_iterator;
107 typedef HashContainerReference<const Entry> const_reference; 108 typedef HashContainerReference<const Entry> const_reference;
108 109
109 private: 110 private:
110 explicit HashContainer(const HashContainer& other); 111 explicit HashContainer(const HashContainer& other);
111 void operator=(const HashContainer& other); 112 void operator=(const HashContainer& other);
112 113
113 protected: 114 protected:
114 static constexpr size_type MIN_BUCKETS = 1; 115 static constexpr size_type MIN_BUCKETS = 1;
115 static constexpr double LOAD_FACTOR = 0.8; 116 static constexpr double LOAD_FACTOR = 0.8;
116 std::unique_ptr<entry_type[]> mBuckets; 117 std::unique_ptr<entry_type[]> mBuckets;
117 size_type mBucketCount; 118 size_type mBucketCount;
118 size_type mEntryCount; 119 size_type mEntryCount;
119 120
120 #if defined(DEBUG) 121 #if defined(DEBUG)
121 size_type mInsertCounter; 122 size_type mInsertCounter;
122 #endif 123 #endif
123 124
124 explicit HashContainer(size_type expectedEntries = 0) 125 entry_type* find_bucket(key_type_cref key) const
125 : mEntryCount(0)
126 {
127 expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
128 mBucketCount = MIN_BUCKETS;
129 while (mBucketCount < expectedEntries)
130 mBucketCount <<= 1;
131
132 mBuckets.reset(new entry_type[mBucketCount]);
133 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
134 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
135 }
136
137 entry_type* find_bucket(const key_type& key) const
138 { 126 {
139 size_type h = entry_type::hash(key); 127 size_type h = entry_type::hash(key);
140 128
141 // This does quadratic probing, effectively the following formula is used: 129 // This does quadratic probing, effectively the following formula is used:
142 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount 130 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
143 for (size_type i = 0; ; ++i) 131 for (size_type i = 0; ; ++i)
144 { 132 {
145 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to 133 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
146 // h % mBucketCount but significantly faster. 134 // h % mBucketCount but significantly faster.
147 entry_type* entry = &mBuckets[h & (mBucketCount - 1)]; 135 entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
186 mEntryCount++; 174 mEntryCount++;
187 #if defined(DEBUG) 175 #if defined(DEBUG)
188 mInsertCounter++; 176 mInsertCounter++;
189 #endif 177 #endif
190 } 178 }
191 *existing = entry; 179 *existing = entry;
192 return existing; 180 return existing;
193 } 181 }
194 182
195 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
196 void insert(const entry_type& entry) 197 void insert(const entry_type& entry)
197 { 198 {
198 assign(find_bucket(entry.first), entry); 199 assign(find_bucket(entry.first), entry);
199 } 200 }
200 201
201 bool erase(const key_type& key) 202 bool erase(key_type_cref key)
202 { 203 {
203 entry_type* entry = find_bucket(key); 204 entry_type* entry = find_bucket(key);
204 if (entry->is_invalid()) 205 if (entry->is_invalid())
205 return false; 206 return false;
206 207
207 entry->erase(); 208 entry->erase();
208 return true; 209 return true;
209 } 210 }
210 211
211 const_reference find(const key_type& key) const 212 const_reference find(key_type_cref key) const
212 { 213 {
213 return const_reference(find_bucket(key)); 214 return const_reference(find_bucket(key));
214 } 215 }
215 216
216 const_iterator begin() const 217 const_iterator begin() const
217 { 218 {
218 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]); 219 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
219 } 220 }
220 221
221 const_iterator end() const 222 const_iterator end() const
222 { 223 {
223 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]); 224 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]);
224 } 225 }
225 226
226 size_type size() const 227 size_type size() const
227 { 228 {
228 return mEntryCount; 229 return mEntryCount;
229 } 230 }
230 }; 231 };
231 232
232 template<typename Entry, typename Value> 233 template<typename Entry>
233 struct MapReference : public HashContainerReference<Entry> 234 struct MapReference : public HashContainerReference<Entry>
Wladimir Palant 2017/10/10 14:33:58 Logically, this class should be defined further ab
234 { 235 {
235 typedef HashContainerReference<Entry> super; 236 typedef HashContainerReference<Entry> super;
236 typedef typename super::entry_type entry_type; 237 typedef typename super::entry_type entry_type;
237 typedef typename entry_type::key_type key_type; 238 typedef typename entry_type::key_type_cref key_type_cref;
238 typedef Value value_type; 239 typedef typename entry_type::value_type value_type;
239 typedef Map<Entry, Value> map_type; 240 typedef Map<entry_type> map_type;
240 241
241 map_type* mMap; 242 map_type* mMap;
242 243
243 #if defined(DEBUG) 244 #if defined(DEBUG)
244 typename map_type::size_type mInsertCounter; 245 typename map_type::size_type mInsertCounter;
245 typename map_type::size_type mHash; 246 typename map_type::size_type mHash;
246 #endif 247 #endif
247 248
248 MapReference(map_type* map, const key_type& key, entry_type* entry) 249 MapReference(map_type* map, key_type_cref key, entry_type* entry)
249 : super(entry), mMap(map) 250 : super(entry), mMap(map)
250 { 251 {
251 #if defined(DEBUG) 252 #if defined(DEBUG)
252 mInsertCounter = mMap->mInsertCounter; 253 mInsertCounter = mMap->mInsertCounter;
253 mHash = entry_type::hash(key); 254 mHash = entry_type::hash(key);
254 #endif 255 #endif
255 } 256 }
256 257
257 void assign(const key_type& key, const value_type& value) 258 void assign(key_type_cref key, const value_type& value)
258 { 259 {
259 #if defined(DEBUG) 260 #if defined(DEBUG)
260 assert2(mInsertCounter == mMap->mInsertCounter, 261 assert2(mInsertCounter == mMap->mInsertCounter,
261 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);
262 assert2(mHash == entry_type::hash(key), 263 assert2(mHash == entry_type::hash(key),
263 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);
264 #endif 265 #endif
265 266
266 mMap->assign(this->mEntry, entry_type(key, value)); 267 mMap->assign(this->mEntry, entry_type(key, value));
267 } 268 }
268 }; 269 };
269 } 270 }
270 271
271 template<typename Entry> 272 template<typename Entry>
272 class Set : public Map_internal::HashContainer<Entry> 273 using Set = Map_internal::HashContainer<Entry>;
273 { 274
274 public: 275 template<typename Entry>
275 typedef Map_internal::HashContainer<Entry> super;
276 typedef typename super::entry_type entry_type;
277 typedef typename super::key_type key_type;
278 };
279
280 template<typename Entry, typename Value>
281 class Map : public Map_internal::HashContainer<Entry> 276 class Map : public Map_internal::HashContainer<Entry>
282 { 277 {
283 public: 278 public:
284 typedef Map_internal::HashContainer<Entry> super; 279 typedef Map_internal::HashContainer<Entry> super;
285 typedef typename super::size_type size_type; 280 typedef typename super::size_type size_type;
286 typedef typename super::entry_type entry_type; 281 typedef typename super::entry_type entry_type;
287 typedef typename super::key_type key_type; 282 typedef typename super::key_type_cref key_type_cref;
288 typedef Value value_type; 283 typedef typename entry_type::value_type value_type;
289 typedef typename super::const_reference const_reference; 284 typedef typename super::const_reference const_reference;
290 typedef Map_internal::MapReference<entry_type, value_type> reference; 285 typedef Map_internal::MapReference<entry_type> reference;
291 friend struct Map_internal::MapReference<entry_type, value_type>; 286 friend struct Map_internal::MapReference<entry_type>;
292 287
293 explicit Map(size_type expectedEntries = 0) 288 using super::super;
294 : super(expectedEntries) 289
295 { 290 Map(std::initializer_list<entry_type> list)
291 : super(list.size())
292 {
293 for (const auto& item : list)
294 super::insert(item);
296 } 295 }
297 296
298 value_type& operator[](const key_type& key) 297 value_type& operator[](key_type_cref key)
299 { 298 {
300 entry_type* entry = super::find_bucket(key); 299 entry_type* entry = super::find_bucket(key);
301 if (entry->is_invalid()) 300 if (entry->is_invalid())
302 entry = super::assign(entry, key); 301 entry = super::assign(entry, key);
303 return entry->second; 302 return entry->second;
304 } 303 }
305 304
306 const_reference find(const key_type& key) const 305 const_reference find(key_type_cref key) const
307 { 306 {
308 return super::find(key); 307 return super::find(key);
309 } 308 }
310 309
311 reference find(const key_type& key) 310 reference find(key_type_cref key)
312 { 311 {
313 return reference(this, key, super::find_bucket(key)); 312 return reference(this, key, super::find_bucket(key));
314 } 313 }
315 }; 314 };
LEFTRIGHT

Powered by Google App Engine
This is Rietveld