LEFT | RIGHT |
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 |
(...skipping 92 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
103 template<typename Entry> | 103 template<typename Entry> |
104 class HashContainer | 104 class HashContainer |
105 { | 105 { |
106 public: | 106 public: |
107 typedef Entry entry_type; | 107 typedef Entry entry_type; |
108 typedef typename Entry::key_type_cref key_type_cref; | 108 typedef typename Entry::key_type_cref key_type_cref; |
109 typedef typename entry_type::size_type size_type; | 109 typedef typename entry_type::size_type size_type; |
110 typedef HashContainerIterator<Entry> const_iterator; | 110 typedef HashContainerIterator<Entry> const_iterator; |
111 typedef HashContainerReference<const Entry> const_reference; | 111 typedef HashContainerReference<const Entry> const_reference; |
112 | 112 |
113 private: | 113 explicit HashContainer(HashContainer&& other) = default; |
114 explicit HashContainer(const HashContainer& other); | 114 HashContainer& operator=(HashContainer&&) = default; |
115 void operator=(const HashContainer& other); | 115 |
| 116 explicit HashContainer(const HashContainer& other) = delete; |
| 117 void operator=(const HashContainer& other) = delete; |
116 | 118 |
117 protected: | 119 protected: |
118 static constexpr size_type MIN_BUCKETS = 1; | 120 static constexpr size_type MIN_BUCKETS = 1; |
119 static constexpr double LOAD_FACTOR = 0.8; | 121 static constexpr double LOAD_FACTOR = 0.8; |
120 std::unique_ptr<entry_type[]> mBuckets; | 122 std::unique_ptr<entry_type[]> mBuckets; |
121 size_type mBucketCount; | 123 size_type mBucketCount; |
122 size_type mEntryCount; | 124 size_type mEntryCount; |
123 | 125 |
124 #if defined(DEBUG) | 126 #if defined(DEBUG) |
125 size_type mInsertCounter; | 127 size_type mInsertCounter; |
(...skipping 16 matching lines...) Expand all Loading... |
142 } | 144 } |
143 } | 145 } |
144 | 146 |
145 void resize(size_type bucketCount) | 147 void resize(size_type bucketCount) |
146 { | 148 { |
147 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets)); | 149 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets)); |
148 size_type oldCount = mBucketCount; | 150 size_type oldCount = mBucketCount; |
149 | 151 |
150 mEntryCount = 0; | 152 mEntryCount = 0; |
151 mBucketCount = bucketCount; | 153 mBucketCount = bucketCount; |
152 mBuckets.reset(new entry_type[mBucketCount]); | 154 allocate(); |
153 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle
ctor/issues/2 here | |
154 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t
able buffer"); | |
155 | 155 |
156 // Copy old entries into the new buffer | 156 // Copy old entries into the new buffer |
157 for (size_type i = 0; i < oldCount; i++) | 157 for (size_type i = 0; i < oldCount; i++) |
158 { | 158 { |
159 entry_type& entry = oldBuckets[i]; | 159 entry_type& entry = oldBuckets[i]; |
160 if (!entry.is_invalid() && !entry.is_deleted()) | 160 if (!entry.is_invalid() && !entry.is_deleted()) |
161 { | 161 { |
162 *find_bucket(entry.first) = entry; | 162 *find_bucket(entry.first) = std::move(entry); |
163 mEntryCount++; | 163 mEntryCount++; |
164 } | 164 } |
165 } | 165 } |
166 } | 166 } |
167 | 167 |
168 entry_type* assign(entry_type* existing, const entry_type& entry) | 168 // Prepare the bucket for assigning entry at key. |
| 169 entry_type* prepare_bucket(entry_type* existing, key_type_cref key) |
169 { | 170 { |
170 if (existing->is_invalid()) | 171 if (existing->is_invalid()) |
171 { | 172 { |
172 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) | 173 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) |
173 { | 174 { |
174 resize(mBucketCount << 1); | 175 resize(mBucketCount << 1); |
175 existing = find_bucket(entry.first); | 176 existing = find_bucket(key); |
176 } | 177 } |
177 mEntryCount++; | 178 mEntryCount++; |
178 #if defined(DEBUG) | 179 #if defined(DEBUG) |
179 mInsertCounter++; | 180 mInsertCounter++; |
180 #endif | 181 #endif |
181 } | 182 } |
| 183 return existing; |
| 184 } |
| 185 |
| 186 entry_type* assign(entry_type* existing, const entry_type& entry) |
| 187 { |
| 188 existing = prepare_bucket(existing, entry.first); |
182 *existing = entry; | 189 *existing = entry; |
183 return existing; | 190 return existing; |
| 191 } |
| 192 |
| 193 entry_type* assign(entry_type* existing, entry_type&& entry) |
| 194 { |
| 195 existing = prepare_bucket(existing, entry.first); |
| 196 *existing = std::move(entry); |
| 197 return existing; |
| 198 } |
| 199 |
| 200 void allocate() |
| 201 { |
| 202 mBuckets.reset(new entry_type[mBucketCount]); |
| 203 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle
ctor/issues/2 here |
| 204 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t
able buffer"); |
184 } | 205 } |
185 | 206 |
186 public: | 207 public: |
187 explicit HashContainer(size_type expectedEntries = 0) | 208 explicit HashContainer(size_type expectedEntries = 0) |
188 : mEntryCount(0) | 209 : mEntryCount(0) |
189 { | 210 { |
190 expectedEntries = ceil(expectedEntries / LOAD_FACTOR); | 211 expectedEntries = ceil(expectedEntries / LOAD_FACTOR); |
191 mBucketCount = MIN_BUCKETS; | 212 mBucketCount = MIN_BUCKETS; |
192 while (mBucketCount < expectedEntries) | 213 while (mBucketCount < expectedEntries) |
193 mBucketCount <<= 1; | 214 mBucketCount <<= 1; |
194 | 215 |
195 mBuckets.reset(new entry_type[mBucketCount]); | 216 allocate(); |
196 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle
ctor/issues/2 here | 217 } |
197 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t
able buffer"); | 218 |
| 219 void clear() |
| 220 { |
| 221 mEntryCount = 0; |
| 222 allocate(); |
198 } | 223 } |
199 | 224 |
200 void insert(const entry_type& entry) | 225 void insert(const entry_type& entry) |
201 { | 226 { |
202 assign(find_bucket(entry.first), entry); | 227 assign(find_bucket(entry.first), entry); |
203 } | 228 } |
204 | 229 |
205 bool erase(key_type_cref key) | 230 bool erase(key_type_cref key) |
206 { | 231 { |
207 entry_type* entry = find_bucket(key); | 232 entry_type* entry = find_bucket(key); |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
310 return super::find(key); | 335 return super::find(key); |
311 } | 336 } |
312 | 337 |
313 reference find(key_type_cref key) | 338 reference find(key_type_cref key) |
314 { | 339 { |
315 return reference(this, key, super::find_bucket(key)); | 340 return reference(this, key, super::find_bucket(key)); |
316 } | 341 } |
317 }; | 342 }; |
318 | 343 |
319 ABP_NS_END | 344 ABP_NS_END |
LEFT | RIGHT |