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

Delta Between Two Patch Sets: compiled/StringMap.h

Issue 29613616: Issue 6064 - Put C++ code into a configurable namespace (Closed) Base URL: https://github.com/adblockplus/adblockpluscore.git
Left Patch Set: Created Nov. 21, 2017, 1:53 p.m.
Right Patch Set: rebase Created Feb. 6, 2018, 9:54 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
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 <cstddef> 20 #include <cstddef>
21 #include <cmath>
22 #include <initializer_list>
23 #include <memory>
24 21
25 #include "base.h" 22 #include "base.h"
23 #include "Map.h"
26 #include "String.h" 24 #include "String.h"
27 #include "debug.h"
28 25
29 ABP_NS_BEGIN 26 ABP_NS_BEGIN
27 namespace StringMap_internal
sergei 2018/02/06 10:03:17 here is actually an unrelated change, we are norma
28 {
29 inline size_t stringHash(const String& key)
30 {
31 // FNV-1a hash function
32 size_t result = 2166136261;
33 for (size_t i = 0; i < key.length(); i++)
34 result = (result ^ key[i]) * 16777619;
35 return result;
36 }
37 }
30 38
31 template<typename T> 39 struct StringHash
32 class StringMap; 40 {
41 size_t operator()(const String& key) const
42 {
43 return StringMap_internal::stringHash(key);
44 }
45 };
33 46
34 namespace StringMap_internal 47 namespace StringMap_internal
35 { 48 {
36 template<typename Entry> 49 template<typename Key,
37 struct HashContainerIterator 50 class = typename std::enable_if<std::is_base_of<String, Key>::value>::type>
51 struct StringSetEntry
38 { 52 {
39 typedef Entry entry_type; 53 typedef Key key_type;
40 typedef HashContainerIterator<Entry> iterator; 54 typedef const String& key_type_cref;
55 typedef size_t size_type;
41 56
42 const entry_type* mPos; 57 key_type first;
43 const entry_type* mEnd;
44 58
45 explicit HashContainerIterator(const entry_type* start, const entry_type* en d) 59 StringSetEntry(key_type_cref key = key_type())
46 : mPos(start), mEnd(end)
47 { 60 {
48 if (mPos != mEnd && mPos->first.is_invalid()) 61 if (!key.is_invalid())
49 ++(*this); 62 first.reset(key);
50 } 63 }
51 64
52 const entry_type& operator*() const 65 bool equals(key_type_cref other) const
53 { 66 {
54 return *mPos; 67 return first.equals(other);
55 } 68 }
56 69
57 const entry_type* operator->() const 70 bool is_invalid() const
58 { 71 {
59 return mPos; 72 return first.is_invalid();
60 } 73 }
61 74
62 iterator& operator++() 75 bool is_deleted() const
63 { 76 {
64 do { 77 return first.is_deleted();
65 ++mPos;
66 } while(mPos != mEnd && mPos->first.is_invalid());
67 return *this;
68 } 78 }
69 79
70 bool operator==(const iterator& it) const 80 void erase()
71 { 81 {
72 return mPos == it.mPos; 82 first.erase();
73 } 83 }
74 84
75 bool operator!=(const iterator& it) const 85 static size_type hash(key_type_cref key)
76 { 86 {
77 return mPos != it.mPos; 87 return stringHash(key);
78 } 88 }
79 }; 89 };
80 90
81 template<typename Entry> 91 template<typename Key, typename Value>
82 struct HashContainerReference 92 struct StringMapEntry : StringSetEntry<Key>
83 { 93 {
84 typedef Entry entry_type; 94 typedef StringSetEntry<Key> super;
95 typedef Value value_type;
85 96
86 entry_type* mEntry; 97 value_type second;
87 98
88 explicit HashContainerReference(entry_type* entry) 99 StringMapEntry(typename super::key_type_cref key = Key(),
89 : mEntry(entry) 100 value_type value = value_type())
101 : super(key), second(std::move(value))
90 { 102 {
91 } 103 }
92 104
93 const entry_type* operator->() const 105 void erase()
94 { 106 {
95 return mEntry; 107 super::erase();
96 } 108 second = value_type();
97
98 operator bool() const
99 {
100 return !mEntry->first.is_invalid();
101 }
102 };
103
104 template<typename Entry>
105 class HashContainer
106 {
107 public:
108 typedef Entry entry_type;
109 typedef size_t size_type;
110 typedef HashContainerIterator<Entry> const_iterator;
111 typedef HashContainerReference<const Entry> const_reference;
112
113 private:
114 explicit HashContainer(const HashContainer& other);
115 void operator=(const HashContainer& other);
116
117 protected:
118 static constexpr size_type MIN_BUCKETS = 1;
119 static constexpr double LOAD_FACTOR = 0.8;
120 std::unique_ptr<entry_type[]> mBuckets;
121 size_type mBucketCount;
122 size_type mEntryCount;
123
124 #if defined(DEBUG)
125 size_type mInsertCounter;
126 #endif
127
128 explicit HashContainer(size_type expectedEntries = 0)
129 : mEntryCount(0)
130 {
131 expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
132 mBucketCount = MIN_BUCKETS;
133 while (mBucketCount < expectedEntries)
134 mBucketCount <<= 1;
135
136 mBuckets.reset(new entry_type[mBucketCount]);
137 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
138 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
139 }
140
141 static size_type hash(const String& str)
142 {
143 // FNV-1a hash function
144 size_type result = 2166136261;
145 for (String::size_type i = 0; i < str.length(); i++)
146 result = (result ^ str[i]) * 16777619;
147 return result;
148 }
149
150 entry_type* find_bucket(const String& key) const
151 {
152 size_type h = hash(key);
153
154 // This does quadratic probing, effectively the following formula is used:
155 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
156 for (size_type i = 0; ; ++i)
157 {
158 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
159 // h % mBucketCount but significantly faster.
160 entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
161 if (entry->first.is_invalid() || entry->first.equals(key))
162 return entry;
163 h += i;
164 }
165 }
166
167 void resize(size_type bucketCount)
168 {
169 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets));
170 size_type oldCount = mBucketCount;
171
172 mEntryCount = 0;
173 mBucketCount = bucketCount;
174 mBuckets.reset(new entry_type[mBucketCount]);
175 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
176 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
177
178 // Copy old entries into the new buffer
179 for (size_type i = 0; i < oldCount; i++)
180 {
181 entry_type& entry = oldBuckets[i];
182 if (!entry.first.is_invalid() && !entry.first.is_deleted())
183 {
184 *find_bucket(entry.first) = entry;
185 mEntryCount++;
186 }
187 }
188 }
189
190 entry_type* assign(entry_type* existing, const entry_type& entry)
191 {
192 if (existing->first.is_invalid())
193 {
194 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
195 {
196 resize(mBucketCount << 1);
197 existing = find_bucket(entry.first);
198 }
199 mEntryCount++;
200 #if defined(DEBUG)
201 mInsertCounter++;
202 #endif
203 }
204 *existing = entry;
205 return existing;
206 }
207
208 public:
209 void insert(const entry_type& entry)
210 {
211 assign(find_bucket(entry.first), entry);
212 }
213
214 bool erase(const String& key)
215 {
216 entry_type* entry = find_bucket(key);
217 if (entry->first.is_invalid())
218 return false;
219
220 entry->first.erase();
221 return true;
222 }
223
224 const_reference find(const String& key) const
225 {
226 return const_reference(find_bucket(key));
227 }
228
229 const_iterator begin() const
230 {
231 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
232 }
233
234 const_iterator end() const
235 {
236 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]);
237 }
238
239 size_type size() const
240 {
241 return mEntryCount;
242 }
243 };
244
245 struct StringSetEntry
246 {
247 StringSetEntry() {}
248 StringSetEntry(const String& key)
249 : first(key)
250 {
251 }
252
253 DependentString first;
254 };
255
256 template<typename T>
257 struct StringMapEntry
258 {
259 StringMapEntry() {}
260 StringMapEntry(const String& key)
261 : first(key), second()
262 {
263 }
264 StringMapEntry(const String& key, T value)
265 : first(key), second(value)
266 {
267 }
268
269 DependentString first;
270 T second;
271 };
272
273 template<typename T>
274 struct StringMapEntryReference : public HashContainerReference<StringMapEntry< T>>
275 {
276 typedef HashContainerReference<StringMapEntry<T>> super;
277 typedef typename super::entry_type entry_type;
278 typedef StringMap<T> map_type;
279
280 map_type* mMap;
281
282 #if defined(DEBUG)
283 typename map_type::size_type mInsertCounter;
284 typename map_type::size_type mHash;
285 #endif
286
287 StringMapEntryReference(map_type* map, const String& key, entry_type* entry)
288 : super(entry), mMap(map)
289 {
290 #if defined(DEBUG)
291 mInsertCounter = mMap->mInsertCounter;
292 mHash = mMap->hash(key);
293 #endif
294 }
295
296 void assign(const String& key, const T& value)
297 {
298 #if defined(DEBUG)
299 assert2(mInsertCounter == mMap->mInsertCounter,
300 u"There should be no insert operations performed between map.find() an d assign()"_str);
301 assert2(mHash == mMap->hash(key),
302 u"The keys used in map.find() and assign() should be identical"_str);
303 #endif
304
305 mMap->assign(this->mEntry, entry_type(key, value));
306 } 109 }
307 }; 110 };
308 } 111 }
309 112
310 class StringSet 113 using StringSet = Set<StringMap_internal::StringSetEntry<DependentString>>;
311 : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry>
312 {
313 };
314 114
315 template<typename T> 115 template<typename Value>
316 class StringMap 116 using StringMap = Map<StringMap_internal::StringMapEntry<DependentString, Value> >;
317 : public StringMap_internal::HashContainer<StringMap_internal::StringMapEntry< T>> 117 template<typename Value>
318 { 118 using OwnedStringMap = Map<StringMap_internal::StringMapEntry<OwnedString, Value >>;
319 public: 119 ABP_NS_END
320 typedef StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T >> super;
321 typedef typename super::size_type size_type;
322 typedef typename super::entry_type entry_type;
323 typedef typename super::const_reference const_reference;
324 typedef StringMap_internal::StringMapEntryReference<T> reference;
325 friend struct StringMap_internal::StringMapEntryReference<T>;
326
327 explicit StringMap(size_type expectedEntries = 0)
328 : super(expectedEntries)
329 {
330 }
331
332 StringMap(std::initializer_list<entry_type> list)
333 : super(list.size())
334 {
335 for (const auto& item : list)
336 super::insert(item);
337 }
338
339 ~StringMap()
340 {
341 }
342
343 T& operator[](const String& key)
344 {
345 entry_type* entry = super::find_bucket(key);
346 if (entry->first.is_invalid())
347 entry = super::assign(entry, key);
348 return entry->second;
349 }
350
351 const_reference find(const String& key) const
352 {
353 return super::find(key);
354 }
355
356 reference find(const String& key)
357 {
358 return reference(this, key, super::find_bucket(key));
359 }
360 };
361
362 ABP_NS_END
LEFTRIGHT

Powered by Google App Engine
This is Rietveld