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

Side by Side Diff: compiled/StringMap.h

Issue 29333474: Issue 4125 - [emscripten] Convert filter classes to C++ (Closed)
Patch Set: Addressed Sergei`s comments again Created Feb. 23, 2016, 9:29 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
« no previous file with comments | « compiled/String.h ('k') | compiled/StringScanner.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 #pragma once
2
3 #include <cstddef>
4 #include <cmath>
5 #include <initializer_list>
6 #include <memory>
7
8 #include "String.h"
9 #include "debug.h"
10
11 template<typename T>
12 class StringMap;
13
14 namespace StringMap_internal
15 {
16 template<typename Entry>
17 struct HashContainerIterator
18 {
19 typedef Entry entry_type;
20 typedef HashContainerIterator<Entry> iterator;
21
22 const entry_type* mPos;
23 const entry_type* mEnd;
24
25 explicit HashContainerIterator(const entry_type* start, const entry_type* en d)
26 : mPos(start), mEnd(end)
27 {
28 if (mPos != mEnd && mPos->first.is_invalid())
29 ++(*this);
30 }
31
32 const entry_type& operator*() const
33 {
34 return *mPos;
35 }
36
37 const entry_type* operator->() const
38 {
39 return mPos;
40 }
41
42 iterator& operator++()
43 {
44 do {
45 ++mPos;
46 } while(mPos != mEnd && mPos->first.is_invalid());
47 return *this;
48 }
49
50 bool operator==(const iterator& it) const
51 {
52 return mPos == it.mPos;
53 }
54
55 bool operator!=(const iterator& it) const
56 {
57 return mPos != it.mPos;
58 }
59 };
60
61 template<typename Entry>
62 struct HashContainerReference
63 {
64 typedef Entry entry_type;
65
66 entry_type* mEntry;
67
68 explicit HashContainerReference(entry_type* entry)
69 : mEntry(entry)
70 {
71 }
72
73 const entry_type* operator->() const
74 {
75 return mEntry;
76 }
77
78 operator bool() const
79 {
80 return !mEntry->first.is_invalid();
81 }
82 };
83
84 template<typename Entry>
85 class HashContainer
86 {
87 public:
88 typedef Entry entry_type;
89 typedef size_t size_type;
90 typedef HashContainerIterator<Entry> const_iterator;
91 typedef HashContainerReference<const Entry> const_reference;
92
93 private:
94 HashContainer(const HashContainer& other);
95 void operator=(const HashContainer& other);
96
97 protected:
98 static constexpr size_type MIN_BUCKETS = 1;
99 static constexpr double LOAD_FACTOR = 0.8;
100 std::unique_ptr<entry_type[]> mBuckets;
101 size_type mBucketCount;
102 size_type mEntryCount;
103
104 #if defined(DEBUG)
105 size_type mInsertCounter;
106 #endif
107
108 explicit HashContainer(size_type expectedEntries = 0)
109 : mEntryCount(0)
110 {
111 expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
112 mBucketCount = MIN_BUCKETS;
113 while (mBucketCount < expectedEntries)
114 mBucketCount <<= 1;
115
116 mBuckets.reset(new entry_type[mBucketCount]);
117 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
118 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
119 }
120
121 static size_type hash(const String& str)
122 {
123 // FNV-1a hash function
124 size_type result = 2166136261;
125 for (String::size_type i = 0; i < str.length(); i++)
126 result = (result ^ str[i]) * 16777619;
127 return result;
128 }
129
130 entry_type* find_bucket(const String& key) const
131 {
132 size_type h = hash(key);
133
134 // This does quadratic probing, effectively the following formula is used:
135 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
136 for (size_type i = 0; ; ++i)
137 {
138 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
139 // h % mBucketCount but significantly faster.
140 entry_type* entry = &mBuckets[h & mBucketCount - 1];
141 if (entry->first.is_invalid() || entry->first.equals(key))
142 return entry;
143 h += i;
144 }
145 }
146
147 void resize(size_type bucketCount)
148 {
149 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets));
150 size_type oldCount = mBucketCount;
151
152 mEntryCount = 0;
153 mBucketCount = bucketCount;
154 mBuckets.reset(new entry_type[mBucketCount]);
155 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
156 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
157
158 // Copy old entries into the new buffer
159 for (size_type i = 0; i < oldCount; i++)
160 {
161 entry_type& entry = oldBuckets[i];
162 if (!entry.first.is_invalid())
163 {
164 *find_bucket(entry.first) = entry;
165 mEntryCount++;
166 }
167 }
168 }
169
170 entry_type* assign(entry_type* existing, const entry_type& entry)
171 {
172 if (existing->first.is_invalid())
173 {
174 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
175 {
176 resize(mBucketCount << 1);
177 existing = find_bucket(entry.first);
178 }
179 mEntryCount++;
180 #if defined(DEBUG)
181 mInsertCounter++;
182 #endif
183 }
184 *existing = entry;
185 return existing;
186 }
187
188 public:
189 void insert(const entry_type& entry)
190 {
191 assign(find_bucket(entry.first), entry);
192 }
193
194 const_reference find(const String& key) const
195 {
196 return const_reference(find_bucket(key));
197 }
198
199 const_iterator begin() const
200 {
201 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
202 }
203
204 const_iterator end() const
205 {
206 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]);
207 }
208 };
209
210 struct StringSetEntry
211 {
212 StringSetEntry() {}
213 StringSetEntry(const String& key)
214 : first(key)
215 {
216 }
217
218 DependentString first;
219 };
220
221 template<typename T>
222 struct StringMapEntry
223 {
224 StringMapEntry() {}
225 StringMapEntry(const String& key)
226 : first(key)
227 {
228 }
229 StringMapEntry(const String& key, T value)
230 : first(key), second(value)
231 {
232 }
233
234 DependentString first;
235 T second;
236 };
237
238 template<typename T>
239 struct StringMapEntryReference : public HashContainerReference<StringMapEntry< T>>
240 {
241 typedef HashContainerReference<StringMapEntry<T>> super;
242 typedef typename super::entry_type entry_type;
243 typedef StringMap<T> map_type;
244
245 map_type* mMap;
246
247 #if defined(DEBUG)
248 typename map_type::size_type mInsertCounter;
249 typename map_type::size_type mHash;
250 #endif
251
252 StringMapEntryReference(map_type* map, const String& key, entry_type* entry)
253 : super(entry), mMap(map)
254 {
255 #if defined(DEBUG)
256 mInsertCounter = mMap->mInsertCounter;
257 mHash = mMap->hash(key);
258 #endif
259 }
260
261 void assign(const String& key, const T& value)
262 {
263 #if defined(DEBUG)
264 assert(mInsertCounter == mMap->mInsertCounter,
265 u"There should be no insert operations performed between map.find() an d assign()"_str);
266 assert(mHash == mMap->hash(key),
267 u"The keys used in map.find() and assign() should be identical"_str);
268 #endif
269
270 mMap->assign(this->mEntry, entry_type(key, value));
271 }
272 };
273 }
274
275 class StringSet
276 : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry>
277 {
278 };
279
280 template<typename T>
281 class StringMap
282 : public StringMap_internal::HashContainer<StringMap_internal::StringMapEntry< T>>
283 {
284 public:
285 typedef StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T >> super;
286 typedef typename super::size_type size_type;
287 typedef typename super::entry_type entry_type;
288 typedef typename super::const_reference const_reference;
289 typedef StringMap_internal::StringMapEntryReference<T> reference;
290 friend class StringMap_internal::StringMapEntryReference<T>;
291
292 explicit StringMap(size_type expectedEntries = 0)
293 : super(expectedEntries)
294 {
295 }
296
297 StringMap(std::initializer_list<entry_type> list)
298 : super(list.size())
299 {
300 for (auto it = list.begin(); it != list.end(); ++it)
301 super::insert(*it);
302 }
303
304 ~StringMap()
305 {
306 }
307
308 T& operator[](const String& key)
309 {
310 entry_type* entry = super::find_bucket(key);
311 if (entry->first.is_invalid())
312 entry = super::assign(entry, key);
313 return entry->second;
314 }
315
316 const_reference find(const String& key) const
317 {
318 return super::find(key);
319 }
320
321 reference find(const String& key)
322 {
323 return reference(this, key, super::find_bucket(key));
324 }
325 };
OLDNEW
« no previous file with comments | « compiled/String.h ('k') | compiled/StringScanner.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld