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>
diff --git a/src/common/simple_string_dictionary.h b/src/common/simple_string_dictionary.h
index 28c4bf1..9484920 100644
--- a/src/common/simple_string_dictionary.h
+++ b/src/common/simple_string_dictionary.h
@@ -147,39 +147,42 @@
if (!key)
return NULL;
- const Entry* entry = GetConstEntryForKey(key);
- if (!entry)
+ size_t index = GetEntryIndexForKey(key);
+ if (index == num_entries)
return NULL;
- return entry->value;
+ return entries_[index].value;
}
// Stores |value| into |key|, replacing the existing value if |key| is
// already present. |key| must not be NULL. If |value| is NULL, the key is
// removed from the map. If there is no more space in the map, then the
- // operation silently fails.
- void SetKeyValue(const char* key, const char* value) {
+ // operation silently fails. Returns an index into the map that can be used
+ // to quickly access the entry, or |num_entries| on failure or when clearing
+ // a key with a null value.
+ size_t SetKeyValue(const char* key, const char* value) {
if (!value) {
RemoveKey(key);
- return;
+ return num_entries;
}
assert(key);
if (!key)
- return;
+ return num_entries;
// Key must not be an empty string.
assert(key[0] != '\0');
if (key[0] == '\0')
- return;
+ return num_entries;
- Entry* entry = GetEntryForKey(key);
+ size_t entry_index = GetEntryIndexForKey(key);
// If it does not yet exist, attempt to insert it.
- if (!entry) {
+ if (entry_index == num_entries) {
for (size_t i = 0; i < num_entries; ++i) {
if (!entries_[i].is_active()) {
- entry = &entries_[i];
+ entry_index = i;
+ Entry* entry = &entries_[i];
strncpy(entry->key, key, key_size);
entry->key[key_size - 1] = '\0';
@@ -190,8 +193,8 @@
}
// If the map is out of space, entry will be NULL.
- if (!entry)
- return;
+ if (entry_index == num_entries)
+ return num_entries;
#ifndef NDEBUG
// Sanity check that the key only appears once.
@@ -203,28 +206,46 @@
assert(count == 1);
#endif
+ strncpy(entries_[entry_index].value, value, value_size);
+ entries_[entry_index].value[value_size - 1] = '\0';
+
+ return entry_index;
+ }
+
+ // Sets a value for a key that has already been set with SetKeyValue(), using
+ // the index returned from that function.
+ void SetValueAtIndex(size_t index, const char* value) {
+ assert(index < num_entries);
+ if (index >= num_entries)
+ return;
+
+ Entry* entry = &entries_[index];
+ assert(entry->key[0] != '\0');
+
strncpy(entry->value, value, value_size);
entry->value[value_size - 1] = '\0';
}
// Given |key|, removes any associated value. |key| must not be NULL. If
- // the key is not found, this is a noop.
+ // the key is not found, this is a noop. This invalidates the index
+ // returned by SetKeyValue().
bool RemoveKey(const char* key) {
assert(key);
if (!key)
return false;
- Entry* entry = GetEntryForKey(key);
- if (entry) {
- entry->key[0] = '\0';
- entry->value[0] = '\0';
- return true;
- }
+ return RemoveAtIndex(GetEntryIndexForKey(key));
+ }
-#ifndef NDEBUG
- assert(GetEntryForKey(key) == NULL);
-#endif
- return false;
+ // Removes a value and key using an index that was returned from
+ // SetKeyValue(). After a call to this function, the index is invalidated.
+ bool RemoveAtIndex(size_t index) {
+ if (index >= num_entries)
+ return false;
+
+ entries_[index].key[0] = '\0';
+ entries_[index].value[0] = '\0';
+ return true;
}
// Places a serialized version of the map into |map| and returns the size.
@@ -237,17 +258,13 @@
}
private:
- const Entry* GetConstEntryForKey(const char* key) const {
+ size_t GetEntryIndexForKey(const char* key) const {
for (size_t i = 0; i < num_entries; ++i) {
if (strncmp(key, entries_[i].key, key_size) == 0) {
- return &entries_[i];
+ return i;
}
}
- return NULL;
- }
-
- Entry* GetEntryForKey(const char* key) {
- return const_cast<Entry*>(GetConstEntryForKey(key));
+ return num_entries;
}
Entry entries_[NumEntries];
diff --git a/src/common/simple_string_dictionary_unittest.cc b/src/common/simple_string_dictionary_unittest.cc
index 34f4b9e..e7b8fd7 100644
--- a/src/common/simple_string_dictionary_unittest.cc
+++ b/src/common/simple_string_dictionary_unittest.cc
@@ -288,6 +288,37 @@
EXPECT_FALSE(map.GetValueForKey("c"));
}
+TEST(NonAllocatingMapTest, ByIndex) {
+ NonAllocatingMap<10, 10, 3> map;
+
+ size_t index1 = map.SetKeyValue("test", "one");
+ EXPECT_TRUE(index1 >= 0 && index1 <= map.num_entries);
+
+ size_t index2 = map.SetKeyValue("moo", "foo");
+ EXPECT_TRUE(index2 >= 0 && index2 <= map.num_entries);
+ EXPECT_NE(index1, index2);
+
+ size_t index3 = map.SetKeyValue("blob", "kebab");
+ EXPECT_TRUE(index3 >= 0 && index3 <= map.num_entries);
+ EXPECT_NE(index2, index3);
+
+ size_t index4 = map.SetKeyValue("nogo", "full");
+ EXPECT_TRUE(index4 == map.num_entries);
+
+ EXPECT_STREQ("one", map.GetValueForKey("test"));
+ EXPECT_STREQ("foo", map.GetValueForKey("moo"));
+ EXPECT_STREQ("kebab", map.GetValueForKey("blob"));
+
+ map.SetValueAtIndex(index2, "booo");
+ EXPECT_STREQ("booo", map.GetValueForKey("moo"));
+
+ EXPECT_TRUE(map.RemoveAtIndex(index1));
+ EXPECT_FALSE(map.GetValueForKey("test"));
+
+ EXPECT_FALSE(map.RemoveAtIndex(map.num_entries));
+ EXPECT_FALSE(map.RemoveAtIndex(9999));
+}
+
#ifndef NDEBUG
TEST(NonAllocatingMapTest, NullKey) {
