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>

2 files changed, 79 insertions, 31 deletions

diff --git a/src/common/simple_string_dictionary.h b/src/common/simple_string_dictionary.h
index 28c4bf1c..94849205 100644
--- a/src/common/simple_string_dictionary.h
+++ b/src/common/simple_string_dictionary.h
@@ -147,39 +147,42 @@ class NonAllocatingMap {
     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 @@ class NonAllocatingMap {
     }
 
     // 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 @@ class NonAllocatingMap {
     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 @@ class NonAllocatingMap {
   }
 
  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 34f4b9ef..e7b8fd76 100644
--- a/src/common/simple_string_dictionary_unittest.cc
+++ b/src/common/simple_string_dictionary_unittest.cc
@@ -288,6 +288,37 @@ TEST(NonAllocatingMapTest, OutOfSpace) {
   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) {