• R/O
  • HTTP
  • SSH
  • HTTPS

thirdparty-breakpad: Commit

Breakpad, a crash reporter, from Google.

Original home: https://chromium.googlesource.com/breakpad/breakpad/


Commit MetaInfo

Révision8a0edac9abfec72e0a86aebd6a0a38761c7c8962 (tree)
l'heure2017-11-08 08:24:48
AuteurRobert Sesek <rsesek@chro...>
CommiterRobert Sesek

Message de Log

Add index-based set functionality to NonAllocatingMap.

This enables repeatedly setting a value based on index, which avoids a
linear scan of the entry table after the first SetKeyValue().

Bug: chromium:598854
Change-Id: I9964670a09dcd8ff76180d031a373f20990bf4d8
Reviewed-on: https://chromium-review.googlesource.com/757579
Reviewed-by: Mark Mentovai <mark@chromium.org>

Change Summary

Modification

--- a/src/common/simple_string_dictionary.h
+++ b/src/common/simple_string_dictionary.h
@@ -147,39 +147,42 @@ class NonAllocatingMap {
147147 if (!key)
148148 return NULL;
149149
150- const Entry* entry = GetConstEntryForKey(key);
151- if (!entry)
150+ size_t index = GetEntryIndexForKey(key);
151+ if (index == num_entries)
152152 return NULL;
153153
154- return entry->value;
154+ return entries_[index].value;
155155 }
156156
157157 // Stores |value| into |key|, replacing the existing value if |key| is
158158 // already present. |key| must not be NULL. If |value| is NULL, the key is
159159 // removed from the map. If there is no more space in the map, then the
160- // operation silently fails.
161- void SetKeyValue(const char* key, const char* value) {
160+ // operation silently fails. Returns an index into the map that can be used
161+ // to quickly access the entry, or |num_entries| on failure or when clearing
162+ // a key with a null value.
163+ size_t SetKeyValue(const char* key, const char* value) {
162164 if (!value) {
163165 RemoveKey(key);
164- return;
166+ return num_entries;
165167 }
166168
167169 assert(key);
168170 if (!key)
169- return;
171+ return num_entries;
170172
171173 // Key must not be an empty string.
172174 assert(key[0] != '\0');
173175 if (key[0] == '\0')
174- return;
176+ return num_entries;
175177
176- Entry* entry = GetEntryForKey(key);
178+ size_t entry_index = GetEntryIndexForKey(key);
177179
178180 // If it does not yet exist, attempt to insert it.
179- if (!entry) {
181+ if (entry_index == num_entries) {
180182 for (size_t i = 0; i < num_entries; ++i) {
181183 if (!entries_[i].is_active()) {
182- entry = &entries_[i];
184+ entry_index = i;
185+ Entry* entry = &entries_[i];
183186
184187 strncpy(entry->key, key, key_size);
185188 entry->key[key_size - 1] = '\0';
@@ -190,8 +193,8 @@ class NonAllocatingMap {
190193 }
191194
192195 // If the map is out of space, entry will be NULL.
193- if (!entry)
194- return;
196+ if (entry_index == num_entries)
197+ return num_entries;
195198
196199 #ifndef NDEBUG
197200 // Sanity check that the key only appears once.
@@ -203,28 +206,46 @@ class NonAllocatingMap {
203206 assert(count == 1);
204207 #endif
205208
209+ strncpy(entries_[entry_index].value, value, value_size);
210+ entries_[entry_index].value[value_size - 1] = '\0';
211+
212+ return entry_index;
213+ }
214+
215+ // Sets a value for a key that has already been set with SetKeyValue(), using
216+ // the index returned from that function.
217+ void SetValueAtIndex(size_t index, const char* value) {
218+ assert(index < num_entries);
219+ if (index >= num_entries)
220+ return;
221+
222+ Entry* entry = &entries_[index];
223+ assert(entry->key[0] != '\0');
224+
206225 strncpy(entry->value, value, value_size);
207226 entry->value[value_size - 1] = '\0';
208227 }
209228
210229 // Given |key|, removes any associated value. |key| must not be NULL. If
211- // the key is not found, this is a noop.
230+ // the key is not found, this is a noop. This invalidates the index
231+ // returned by SetKeyValue().
212232 bool RemoveKey(const char* key) {
213233 assert(key);
214234 if (!key)
215235 return false;
216236
217- Entry* entry = GetEntryForKey(key);
218- if (entry) {
219- entry->key[0] = '\0';
220- entry->value[0] = '\0';
221- return true;
222- }
237+ return RemoveAtIndex(GetEntryIndexForKey(key));
238+ }
223239
224-#ifndef NDEBUG
225- assert(GetEntryForKey(key) == NULL);
226-#endif
227- return false;
240+ // Removes a value and key using an index that was returned from
241+ // SetKeyValue(). After a call to this function, the index is invalidated.
242+ bool RemoveAtIndex(size_t index) {
243+ if (index >= num_entries)
244+ return false;
245+
246+ entries_[index].key[0] = '\0';
247+ entries_[index].value[0] = '\0';
248+ return true;
228249 }
229250
230251 // Places a serialized version of the map into |map| and returns the size.
@@ -237,17 +258,13 @@ class NonAllocatingMap {
237258 }
238259
239260 private:
240- const Entry* GetConstEntryForKey(const char* key) const {
261+ size_t GetEntryIndexForKey(const char* key) const {
241262 for (size_t i = 0; i < num_entries; ++i) {
242263 if (strncmp(key, entries_[i].key, key_size) == 0) {
243- return &entries_[i];
264+ return i;
244265 }
245266 }
246- return NULL;
247- }
248-
249- Entry* GetEntryForKey(const char* key) {
250- return const_cast<Entry*>(GetConstEntryForKey(key));
267+ return num_entries;
251268 }
252269
253270 Entry entries_[NumEntries];
--- a/src/common/simple_string_dictionary_unittest.cc
+++ b/src/common/simple_string_dictionary_unittest.cc
@@ -288,6 +288,37 @@ TEST(NonAllocatingMapTest, OutOfSpace) {
288288 EXPECT_FALSE(map.GetValueForKey("c"));
289289 }
290290
291+TEST(NonAllocatingMapTest, ByIndex) {
292+ NonAllocatingMap<10, 10, 3> map;
293+
294+ size_t index1 = map.SetKeyValue("test", "one");
295+ EXPECT_TRUE(index1 >= 0 && index1 <= map.num_entries);
296+
297+ size_t index2 = map.SetKeyValue("moo", "foo");
298+ EXPECT_TRUE(index2 >= 0 && index2 <= map.num_entries);
299+ EXPECT_NE(index1, index2);
300+
301+ size_t index3 = map.SetKeyValue("blob", "kebab");
302+ EXPECT_TRUE(index3 >= 0 && index3 <= map.num_entries);
303+ EXPECT_NE(index2, index3);
304+
305+ size_t index4 = map.SetKeyValue("nogo", "full");
306+ EXPECT_TRUE(index4 == map.num_entries);
307+
308+ EXPECT_STREQ("one", map.GetValueForKey("test"));
309+ EXPECT_STREQ("foo", map.GetValueForKey("moo"));
310+ EXPECT_STREQ("kebab", map.GetValueForKey("blob"));
311+
312+ map.SetValueAtIndex(index2, "booo");
313+ EXPECT_STREQ("booo", map.GetValueForKey("moo"));
314+
315+ EXPECT_TRUE(map.RemoveAtIndex(index1));
316+ EXPECT_FALSE(map.GetValueForKey("test"));
317+
318+ EXPECT_FALSE(map.RemoveAtIndex(map.num_entries));
319+ EXPECT_FALSE(map.RemoveAtIndex(9999));
320+}
321+
291322 #ifndef NDEBUG
292323
293324 TEST(NonAllocatingMapTest, NullKey) {
Afficher sur ancien navigateur de dépôt.