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: Remove unneeded ctor. Rename _assign() Created Jan. 24, 2018, 7:31 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/IntMap.h ('k') | 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 // Prepare the bucket for assigning entry at key.
166 entry_type* prepare_bucket(entry_type* existing, key_type_cref key)
164 { 167 {
165 if (existing->is_invalid()) 168 if (existing->is_invalid())
166 { 169 {
167 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) 170 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
168 { 171 {
169 resize(mBucketCount << 1); 172 resize(mBucketCount << 1);
170 existing = find_bucket(entry.first); 173 existing = find_bucket(key);
171 } 174 }
172 mEntryCount++; 175 mEntryCount++;
173 #if defined(DEBUG) 176 #if defined(DEBUG)
174 mInsertCounter++; 177 mInsertCounter++;
175 #endif 178 #endif
176 } 179 }
180 return existing;
181 }
182
183 entry_type* assign(entry_type* existing, const entry_type& entry)
184 {
185 existing = prepare_bucket(existing, entry.first);
177 *existing = entry; 186 *existing = entry;
178 return existing; 187 return existing;
179 } 188 }
180 189
190 entry_type* assign(entry_type* existing, entry_type&& entry)
191 {
192 existing = prepare_bucket(existing, entry.first);
193 *existing = std::move(entry);
194 return existing;
195 }
196
181 void allocate() 197 void allocate()
182 { 198 {
183 mBuckets.reset(new entry_type[mBucketCount]); 199 mBuckets.reset(new entry_type[mBucketCount]);
184 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle ctor/issues/2 here 200 // 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"); 201 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t able buffer");
186 } 202 }
187 203
188 public: 204 public:
189 explicit HashContainer(size_type expectedEntries = 0) 205 explicit HashContainer(size_type expectedEntries = 0)
190 : mEntryCount(0) 206 : mEntryCount(0)
(...skipping 123 matching lines...) Expand 10 before | Expand all | Expand 10 after
314 const_reference find(key_type_cref key) const 330 const_reference find(key_type_cref key) const
315 { 331 {
316 return super::find(key); 332 return super::find(key);
317 } 333 }
318 334
319 reference find(key_type_cref key) 335 reference find(key_type_cref key)
320 { 336 {
321 return reference(this, key, super::find_bucket(key)); 337 return reference(this, key, super::find_bucket(key));
322 } 338 }
323 }; 339 };
OLDNEW
« no previous file with comments | « compiled/IntMap.h ('k') | compiled/StringMap.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld