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: Fixed annotation for hash buffers Created Jan. 28, 2016, 5:07 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<class 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<class 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 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 annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buf fer");
129
130 for (size_type i = 0; i < oldCount; i++)
131 {
132 entry_type& entry = oldBuckets[i];
133 if (!entry.first.is_invalid())
134 {
135 *find_entry(entry.first) = entry;
136 mEntryCount++;
137 }
138 }
139
140 delete[] oldBuckets;
141 }
142
143 entry_type* assign(entry_type* existing, const entry_type& entry)
144 {
145 bool added = existing->first.is_invalid();
146 *existing = entry;
147 if (added)
148 {
149 mEntryCount++;
150 if (mEntryCount >= mBucketCount * LOAD_FACTOR)
151 {
152 resize(mBucketCount << 1);
153 existing = find_entry(entry.first);
154 }
155 }
156 return existing;
157 }
158
159 public:
160 void insert(const entry_type& entry)
161 {
162 assign(find_entry(entry.first), entry);
163 }
164
165 iterator find(const String& key) const
166 {
167 entry_type* entry = find_entry(key);
168 if (entry->first.is_invalid())
169 return end();
170 else
171 return iterator(entry, mBuckets + mBucketCount);
172 }
173
174 iterator begin() const
175 {
176 return iterator(mBuckets, mBuckets + mBucketCount);
177 }
178
179 iterator end() const
180 {
181 return iterator(mBuckets + mBucketCount, mBuckets + mBucketCount);
182 }
183 };
184
185 struct _StringSetEntry
186 {
187 _StringSetEntry() {}
188 _StringSetEntry(const String& key)
189 : first(key)
190 {
191 }
192
193 String first;
194 };
195
196 class StringSet : public _HashContainer<_StringSetEntry>
197 {
198 };
199
200 template<class T>
201 struct _StringMapEntry
202 {
203 _StringMapEntry() {}
204 _StringMapEntry(const String& key)
205 : first(key)
206 {
207 }
208 _StringMapEntry(const String& key, T value)
209 : first(key), second(value)
210 {
211 }
212
213 String first;
214 T second;
215 };
216
217 template<class T>
218 class StringMap : public _HashContainer<_StringMapEntry<T>>
219 {
220 public:
221 typedef _HashContainer<_StringMapEntry<T>> super;
222 typedef typename super::size_type size_type;
223 typedef typename super::entry_type entry_type;
224
225 explicit StringMap(size_type expectedEntries = 0)
226 : super(expectedEntries)
227 {
228 }
229
230 StringMap(std::initializer_list<entry_type> list)
231 : super(list.size())
232 {
233 for (auto it = list.begin(); it != list.end(); ++it)
234 super::insert(*it);
235 }
236
237 ~StringMap()
238 {
239 }
240
241 T& operator[](const String& key)
242 {
243 entry_type* entry = super::find_entry(key);
244 if (entry->first.is_invalid())
245 entry = super::assign(entry, key);
246 return entry->second;
247 }
248 };
249
250 #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