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