| 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 |