Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code

Side by Side Diff: compiled/Map.h

Issue 29677755: Issue 6279 - Make HashContainer movable and optimize resizing by moving entries. (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore/
Patch Set: Created Jan. 23, 2018, 9: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 | « no previous file | compiled/StringMap.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 89 matching lines...) Expand 10 before | Expand all | Expand 10 after
100 template<typename Entry> 100 template<typename Entry>
101 class HashContainer 101 class HashContainer
102 { 102 {
103 public: 103 public:
104 typedef Entry entry_type; 104 typedef Entry entry_type;
105 typedef typename Entry::key_type_cref key_type_cref; 105 typedef typename Entry::key_type_cref key_type_cref;
106 typedef typename entry_type::size_type size_type; 106 typedef typename entry_type::size_type size_type;
107 typedef HashContainerIterator<Entry> const_iterator; 107 typedef HashContainerIterator<Entry> const_iterator;
108 typedef HashContainerReference<const Entry> const_reference; 108 typedef HashContainerReference<const Entry> const_reference;
109 109
110 private: 110 explicit HashContainer(HashContainer&& other) = default;
111 explicit HashContainer(const HashContainer& other); 111 HashContainer& operator=(HashContainer&&) = default;
112 void operator=(const HashContainer& other); 112
113 explicit HashContainer(const HashContainer& other) = delete;
114 void operator=(const HashContainer& other) = delete;
113 115
114 protected: 116 protected:
115 static constexpr size_type MIN_BUCKETS = 1; 117 static constexpr size_type MIN_BUCKETS = 1;
116 static constexpr double LOAD_FACTOR = 0.8; 118 static constexpr double LOAD_FACTOR = 0.8;
117 std::unique_ptr<entry_type[]> mBuckets; 119 std::unique_ptr<entry_type[]> mBuckets;
118 size_type mBucketCount; 120 size_type mBucketCount;
119 size_type mEntryCount; 121 size_type mEntryCount;
120 122
121 #if defined(DEBUG) 123 #if defined(DEBUG)
122 size_type mInsertCounter; 124 size_type mInsertCounter;
(...skipping 24 matching lines...) Expand all
147 mEntryCount = 0; 149 mEntryCount = 0;
148 mBucketCount = bucketCount; 150 mBucketCount = bucketCount;
149 allocate(); 151 allocate();
150 152
151 // Copy old entries into the new buffer 153 // Copy old entries into the new buffer
152 for (size_type i = 0; i < oldCount; i++) 154 for (size_type i = 0; i < oldCount; i++)
153 { 155 {
154 entry_type& entry = oldBuckets[i]; 156 entry_type& entry = oldBuckets[i];
155 if (!entry.is_invalid() && !entry.is_deleted()) 157 if (!entry.is_invalid() && !entry.is_deleted())
156 { 158 {
157 *find_bucket(entry.first) = entry; 159 *find_bucket(entry.first) = std::move(entry);
158 mEntryCount++; 160 mEntryCount++;
159 } 161 }
160 } 162 }
161 } 163 }
162 164
163 entry_type* assign(entry_type* existing, const entry_type& entry) 165 entry_type* _assign(entry_type* existing, const entry_type& entry)
164 { 166 {
165 if (existing->is_invalid()) 167 if (existing->is_invalid())
166 { 168 {
167 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) 169 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
168 { 170 {
169 resize(mBucketCount << 1); 171 resize(mBucketCount << 1);
170 existing = find_bucket(entry.first); 172 existing = find_bucket(entry.first);
171 } 173 }
172 mEntryCount++; 174 mEntryCount++;
173 #if defined(DEBUG) 175 #if defined(DEBUG)
174 mInsertCounter++; 176 mInsertCounter++;
175 #endif 177 #endif
176 } 178 }
179 return existing;
180 }
181
182 entry_type* assign(entry_type* existing, const entry_type& entry)
183 {
184 existing = _assign(existing, entry);
177 *existing = entry; 185 *existing = entry;
178 return existing; 186 return existing;
179 } 187 }
180 188
189 entry_type* assign(entry_type* existing, entry_type&& entry)
190 {
191 existing = _assign(existing, entry);
192 *existing = std::move(entry);
193 return existing;
194 }
195
181 void allocate() 196 void allocate()
182 { 197 {
183 mBuckets.reset(new entry_type[mBucketCount]); 198 mBuckets.reset(new entry_type[mBucketCount]);
184 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here 199 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here
185 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer"); 200 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
186 } 201 }
187 202
188 public: 203 public:
189 explicit HashContainer(size_type expectedEntries = 0) 204 explicit HashContainer(size_type expectedEntries = 0)
190 : mEntryCount(0) 205 : mEntryCount(0)
(...skipping 123 matching lines...) Expand 10 before | Expand all | Expand 10 after
314 const_reference find(key_type_cref key) const 329 const_reference find(key_type_cref key) const
315 { 330 {
316 return super::find(key); 331 return super::find(key);
317 } 332 }
318 333
319 reference find(key_type_cref key) 334 reference find(key_type_cref key)
320 { 335 {
321 return reference(this, key, super::find_bucket(key)); 336 return reference(this, key, super::find_bucket(key));
322 } 337 }
323 }; 338 };
OLDNEW
« no previous file with comments | « no previous file | compiled/StringMap.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld