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: Minor improvements Created Feb. 6, 2016, 8:29 a.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
7 #include "String.h"
8 #include "debug.h"
9
10 template<typename Entry>
11 struct _HashContainerIterator
12 {
13 typedef Entry entry_type;
14 typedef _HashContainerIterator<Entry> iterator;
15
16 const entry_type* mPos;
17 const entry_type* mEnd;
18
19 explicit _HashContainerIterator(const entry_type* start, const entry_type* end )
20 : mPos(start), mEnd(end)
21 {
22 if (mPos != mEnd && mPos->first.is_invalid())
23 ++(*this);
24 }
25
26 _HashContainerIterator()
27 {
28 }
29
30 const entry_type& operator*() const
31 {
32 return *mPos;
33 }
34
35 const entry_type* operator->() const
36 {
37 return mPos;
38 }
39
40 iterator& operator++()
41 {
42 do {
43 ++mPos;
44 } while(mPos != mEnd && mPos->first.is_invalid());
45 return *this;
46 }
47
48 bool operator==(const iterator& it) const
49 {
50 return mPos == it.mPos;
51 }
52
53 bool operator!=(const iterator& it) const
54 {
55 return mPos != it.mPos;
56 }
57 };
58
59 template<typename Entry>
60 class _HashContainer
61 {
62 public:
63 typedef Entry entry_type;
64 typedef size_t size_type;
65 typedef _HashContainerIterator<Entry> iterator;
66
67 private:
68 _HashContainer(const _HashContainer& other) {}
69 void operator=(const _HashContainer& other) {}
70
71 protected:
72 static constexpr size_type MIN_BUCKETS = 1;
73 static constexpr double LOAD_FACTOR = 0.8;
74 entry_type* mBuckets;
75 size_type mBucketCount;
76 size_type mEntryCount;
77
78 explicit _HashContainer(size_type expectedEntries = 0)
79 : mEntryCount(0)
80 {
81 expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
82 mBucketCount = MIN_BUCKETS;
83 while (mBucketCount < expectedEntries)
84 mBucketCount <<= 1;
85
86 mBuckets = new entry_type[mBucketCount];
87 // Working around https://github.com/waywardmonkeys/emscripten-trace-collect or/issues/2 here
88 annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buf fer");
89 }
90
91 ~_HashContainer()
92 {
93 delete[] mBuckets;
94 }
95
96 static size_type hash(const String& str)
97 {
98 // FNV-1a hash function
99 size_type result = 2166136261;
100 for (String::size_type i = 0; i < str.length(); i++)
101 result = (result ^ str[i]) * 16777619;
102 return result;
103 }
104
105 entry_type* find_entry(const String& key) const
106 {
107 size_type h = hash(key);
108
109 // This does quadratic probing, effectively the following formula is used:
110 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
111 for (size_type i = 0; ; ++i)
112 {
113 entry_type* entry = mBuckets + h % mBucketCount;
114 if (entry->first.is_invalid() || entry->first.equals(key))
115 return entry;
116 h += i;
117 }
118 }
119
120 void resize(size_type bucketCount)
121 {
122 entry_type* oldBuckets = mBuckets;
123 size_type oldCount = mBucketCount;
124
125 mEntryCount = 0;
126 mBucketCount = bucketCount;
127 mBuckets = new entry_type[mBucketCount];
128 // Working around https://github.com/waywardmonkeys/emscripten-trace-collect or/issues/2 here
129 annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buf fer");
130
131 for (size_type i = 0; i < oldCount; i++)
132 {
133 entry_type& entry = oldBuckets[i];
134 if (!entry.first.is_invalid())
135 {
136 *find_entry(entry.first) = entry;
137 mEntryCount++;
138 }
139 }
140
141 delete[] oldBuckets;
142 }
143
144 entry_type* assign(entry_type* existing, const entry_type& entry)
145 {
146 bool added = existing->first.is_invalid();
147 *existing = entry;
148 if (added)
149 {
150 mEntryCount++;
151 if (mEntryCount >= mBucketCount * LOAD_FACTOR)
152 {
153 resize(mBucketCount << 1);
154 existing = find_entry(entry.first);
155 }
156 }
157 return existing;
158 }
159
160 public:
161 void insert(const entry_type& entry)
162 {
163 assign(find_entry(entry.first), entry);
164 }
165
166 iterator find(const String& key) const
167 {
168 entry_type* entry = find_entry(key);
169 if (entry->first.is_invalid())
170 return end();
171 else
172 return iterator(entry, mBuckets + mBucketCount);
173 }
174
175 iterator begin() const
176 {
177 return iterator(mBuckets, mBuckets + mBucketCount);
178 }
179
180 iterator end() const
181 {
182 return iterator(mBuckets + mBucketCount, mBuckets + mBucketCount);
183 }
184 };
185
186 struct _StringSetEntry
187 {
188 _StringSetEntry() {}
189 _StringSetEntry(const String& key)
190 : first(key)
191 {
192 }
193
194 DependentString first;
195 };
196
197 class StringSet : public _HashContainer<_StringSetEntry>
198 {
199 };
200
201 template<typename T>
202 struct _StringMapEntry
203 {
204 _StringMapEntry() {}
205 _StringMapEntry(const String& key)
206 : first(key)
207 {
208 }
209 _StringMapEntry(const String& key, T value)
210 : first(key), second(value)
211 {
212 }
213
214 DependentString first;
215 T second;
216 };
217
218 template<typename T>
219 class StringMap : public _HashContainer<_StringMapEntry<T>>
220 {
221 public:
222 typedef _HashContainer<_StringMapEntry<T>> super;
223 typedef typename super::size_type size_type;
224 typedef typename super::entry_type entry_type;
225
226 explicit StringMap(size_type expectedEntries = 0)
227 : super(expectedEntries)
228 {
229 }
230
231 StringMap(std::initializer_list<entry_type> list)
232 : super(list.size())
233 {
234 for (auto it = list.begin(); it != list.end(); ++it)
235 super::insert(*it);
236 }
237
238 ~StringMap()
239 {
240 }
241
242 T& operator[](const String& key)
243 {
244 entry_type* entry = super::find_entry(key);
245 if (entry->first.is_invalid())
246 entry = super::assign(entry, key);
247 return entry->second;
248 }
249 };
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