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: Use constructor inheritance Created Oct. 10, 2017, 6:30 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
(...skipping 57 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 entry_type* find_bucket(const key_type& key) const 125 entry_type* find_bucket(key_type_cref key) const
125 { 126 {
126 size_type h = entry_type::hash(key); 127 size_type h = entry_type::hash(key);
127 128
128 // This does quadratic probing, effectively the following formula is used: 129 // This does quadratic probing, effectively the following formula is used:
129 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount 130 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
130 for (size_type i = 0; ; ++i) 131 for (size_type i = 0; ; ++i)
131 { 132 {
132 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to 133 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
133 // h % mBucketCount but significantly faster. 134 // h % mBucketCount but significantly faster.
134 entry_type* entry = &mBuckets[h & (mBucketCount - 1)]; 135 entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after
191 mBuckets.reset(new entry_type[mBucketCount]); 192 mBuckets.reset(new entry_type[mBucketCount]);
192 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here 193 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
193 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer"); 194 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
194 } 195 }
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>
sergei 2017/10/11 10:03:22 I would remove Value template parameter because it
Wladimir Palant 2017/10/11 18:28:31 Done.
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;
sergei 2017/10/11 10:03:21 entry_type is already defined in the public base c
Wladimir Palant 2017/10/11 18:28:31 Yes. However, using it in this class will produce
sergei 2017/10/17 12:58:06 Acknowledged. Interesting whether there is a diffe
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::size_type size_type;
277 typedef typename super::entry_type entry_type;
278 typedef typename super::key_type key_type;
sergei 2017/10/11 10:03:22 Why is it required to define again size_type, entr
Wladimir Palant 2017/10/11 18:28:31 Done here. For Map class they are actually require
279
280 using super::super;
281 };
282
283 template<typename Entry, typename Value>
284 class Map : public Map_internal::HashContainer<Entry> 276 class Map : public Map_internal::HashContainer<Entry>
285 { 277 {
286 public: 278 public:
287 typedef Map_internal::HashContainer<Entry> super; 279 typedef Map_internal::HashContainer<Entry> super;
288 typedef typename super::size_type size_type; 280 typedef typename super::size_type size_type;
289 typedef typename super::entry_type entry_type; 281 typedef typename super::entry_type entry_type;
290 typedef typename super::key_type key_type; 282 typedef typename super::key_type_cref key_type_cref;
291 typedef Value value_type; 283 typedef typename entry_type::value_type value_type;
292 typedef typename super::const_reference const_reference; 284 typedef typename super::const_reference const_reference;
sergei 2017/10/11 10:03:22 const_reference is already defined in the publicly
Wladimir Palant 2017/10/11 18:28:31 It's used in this class, we'll get compile error u
293 typedef Map_internal::MapReference<entry_type, value_type> reference; 285 typedef Map_internal::MapReference<entry_type> reference;
294 friend struct Map_internal::MapReference<entry_type, value_type>; 286 friend struct Map_internal::MapReference<entry_type>;
295 287
296 using super::super; 288 using super::super;
297 289
298 Map(std::initializer_list<entry_type> list) 290 Map(std::initializer_list<entry_type> list)
299 : super(list.size()) 291 : super(list.size())
300 { 292 {
301 for (const auto& item : list) 293 for (const auto& item : list)
302 super::insert(item); 294 super::insert(item);
303 } 295 }
304 296
305 value_type& operator[](const key_type& key) 297 value_type& operator[](key_type_cref key)
306 { 298 {
307 entry_type* entry = super::find_bucket(key); 299 entry_type* entry = super::find_bucket(key);
308 if (entry->is_invalid()) 300 if (entry->is_invalid())
309 entry = super::assign(entry, key); 301 entry = super::assign(entry, key);
310 return entry->second; 302 return entry->second;
311 } 303 }
312 304
313 const_reference find(const key_type& key) const 305 const_reference find(key_type_cref key) const
sergei 2017/10/11 10:03:22 It seems this method is not needed because it's av
Wladimir Palant 2017/10/11 18:28:31 We declare a non-const variant of this method belo
sergei 2017/10/17 12:58:06 What about `using super::find;`, though it should
314 { 306 {
315 return super::find(key); 307 return super::find(key);
316 } 308 }
317 309
318 reference find(const key_type& key) 310 reference find(key_type_cref key)
319 { 311 {
320 return reference(this, key, super::find_bucket(key)); 312 return reference(this, key, super::find_bucket(key));
321 } 313 }
322 }; 314 };
LEFTRIGHT

Powered by Google App Engine
This is Rietveld