Add SimpleStringDictionary and its test

client/simple_string_dictionary.h

Index: client/simple_string_dictionary.h
diff --git a/client/simple_string_dictionary.h b/client/simple_string_dictionary.h
new file mode 100644
index 0000000000000000000000000000000000000000..68c6c1bd38a6d5f8c3d9ce9bc867c6bc2aac418c
--- /dev/null
+++ b/client/simple_string_dictionary.h
@@ -0,0 +1,242 @@
+// Copyright 2014 The Crashpad Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_
+#define CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_
+
+#include <string.h>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace crashpad {
+
+// Opaque type for the serialized representation of a NonAllocatingMap. One is
+// created in NonAllocatingMap::Serialize and can be deserialized using one of
+// the constructors.
+struct SerializedNonAllocatingMap;
+
+// NonAllocatingMap is an implementation of a map/dictionary collection that
+// uses a fixed amount of storage, so that it does not perform any dynamic
+// allocations for its operations.
+//
+// The actual map storage (the Entry) is guaranteed to be POD, so that it can be
+// transmitted over various IPC mechanisms.
+//
+// The template parameters control the amount of storage used for the key,
+// value, and map. The KeySize and ValueSize are measured in bytes, not glyphs,
+// and includes space for a \0 byte. This gives space for KeySize-1 and
+// ValueSize-1 characters in an entry. NumEntries is the total number of entries
+// that will fit in the map.
+template <size_t KeySize, size_t ValueSize, size_t NumEntries>
+class NonAllocatingMap {
+ public:
+  // Constant and publicly accessible versions of the template parameters.
+  static const size_t key_size = KeySize;
+  static const size_t value_size = ValueSize;
+  static const size_t num_entries = NumEntries;
+
+  // An Entry object is a single entry in the map. If the key is a 0-length
+  // NUL-terminated string, the entry is empty.
+  struct Entry {
+    char key[KeySize];
+    char value[ValueSize];
+
+    bool is_active() const { return key[0] != '\0'; }
+  };
+
+  // An Iterator can be used to iterate over all the active entries in a
+  // NonAllocatingMap.
+  class Iterator {
+   public:
+    explicit Iterator(const NonAllocatingMap& map) : map_(map), current_(0) {}
+
+    // Returns the next entry in the map, or NULL if at the end of the
+    // collection.
+    const Entry* Next() {
+      while (current_ < map_.num_entries) {
+        const Entry* entry = &map_.entries_[current_++];
+        if (entry->is_active()) {
+          return entry;
+        }
+      }
+      return NULL;
+    }
+
+   private:
+    const NonAllocatingMap& map_;
+    size_t current_;
+
+    DISALLOW_COPY_AND_ASSIGN(Iterator);
+  };
+
+  NonAllocatingMap() : entries_() {}
+
+  NonAllocatingMap(const NonAllocatingMap& other) { *this = other; }
+
+  NonAllocatingMap& operator=(const NonAllocatingMap& other) {
+    DCHECK(other.key_size == key_size);

[Robert Sesek, 2014/08/21 16:55:16]

DCHECK_EQ

[Mark Mentovai, 2014/08/22 14:05:26]

rsesek wrote:
You would think so, but then in debug mode, you get

Undefined symbols for architecture x86_64:
  "crashpad::SimpleStringDictionary<10ul, 10ul, 10ul>::key_size", referenced
from:
      crashpad::SimpleStringDictionary<10ul, 10ul,
10ul>::operator=(crashpad::SimpleStringDictionary<10ul, 10ul, 10ul> const&) in
client_test.simple_string_dictionary_test.o

(for num_entries and value_size too). This is because the part of the logging
system that prints out the values of the two sides passes them by const
reference, and the reference winds up assuming that storage has been allocated
for the constants, but there has been no explicit instantiation of these
constants. There’s no way to do the explicit instantiation without forecasting
what values people will use as template parameters.

However, I don’t think that these checks are actually necessary. The language
already treats a template class parameter as though it had the same template
parameters as the template class that it’s found in, and this is a distinct and
unconvertible type from template instantiations with any different template
parameters. (This is why you can’t use the
std::basic_string<>::basic_string(const std::basic_string&) constructor to
initialize a std::string from a std::wstring.)

+    DCHECK(other.value_size == value_size);
+    DCHECK(other.num_entries == num_entries);
+    if (other.key_size == key_size && other.value_size == value_size &&
+        other.num_entries == num_entries) {
+      memcpy(entries_, other.entries_, sizeof(entries_));
+    }
+    return *this;
+  }
+
+  // Constructs a map from its serialized form. |map| should be the out
+  // parameter from Serialize() and |size| should be its return value.
+  NonAllocatingMap(const SerializedNonAllocatingMap* map, size_t size) {
+    DCHECK_EQ(size, sizeof(entries_));
+    if (size == sizeof(entries_)) {
+      memcpy(entries_, map, size);
+    }
+  }
+
+  // Returns the number of active key/value pairs. The upper limit for this is
+  // NumEntries.
+  size_t GetCount() const {
+    size_t count = 0;
+    for (size_t i = 0; i < num_entries; ++i) {
+      if (entries_[i].is_active()) {
+        ++count;
+      }
+    }
+    return count;
+  }
+
+  // Given |key|, returns its corresponding |value|. |key| must not be NULL. If
+  // the key is not found, NULL is returned.
+  const char* GetValueForKey(const char* key) const {
+    DCHECK(key);
+    if (!key) {
+      return NULL;
+    }
+
+    const Entry* entry = GetConstEntryForKey(key);
+    if (!entry) {
+      return NULL;
+    }
+
+    return entry->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) {
+    if (!value) {
+      RemoveKey(key);
+      return;
+    }
+
+    DCHECK(key);
+    if (!key) {
+      return;
+    }
+
+    // Key must not be an empty string.
+    DCHECK_NE(key[0], '\0');
+    if (key[0] == '\0') {
+      return;
+    }
+
+    Entry* entry = GetEntryForKey(key);
+
+    // If it does not yet exist, attempt to insert it.
+    if (!entry) {
+      for (size_t i = 0; i < num_entries; ++i) {
+        if (!entries_[i].is_active()) {
+          entry = &entries_[i];
+
+          strncpy(entry->key, key, key_size);
+          entry->key[key_size - 1] = '\0';
+
+          break;
+        }
+      }
+    }
+
+    // If the map is out of space, entry will be NULL.
+    if (!entry) {
+      return;
+    }
+
+#ifndef NDEBUG
+    // Sanity check that the key only appears once.
+    int count = 0;
+    for (size_t i = 0; i < num_entries; ++i) {
+      if (strncmp(entries_[i].key, key, key_size) == 0) {
+        ++count;
+      }
+    }
+    DCHECK_EQ(count, 1);
+#endif
+
+    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.
+  void RemoveKey(const char* key) {
+    DCHECK(key);
+    if (!key) {
+      return;
+    }
+
+    Entry* entry = GetEntryForKey(key);
+    if (entry) {
+      entry->key[0] = '\0';
+      entry->value[0] = '\0';
+    }
+
+    DCHECK_EQ(GetEntryForKey(key), static_cast<void*>(NULL));
+  }
+
+  // Places a serialized version of the map into |map| and returns the size.
+  // Both of these should be passed to the deserializing constructor. Note that
+  // the serialized |map| is scoped to the lifetime of the non-serialized
+  // instance of this class. The |map| can be copied across IPC boundaries.
+  size_t Serialize(const SerializedNonAllocatingMap** map) const {
+    *map = reinterpret_cast<const SerializedNonAllocatingMap*>(entries_);
+    return sizeof(entries_);
+  }
+
+ private:
+  const Entry* GetConstEntryForKey(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 NULL;
+  }
+
+  Entry* GetEntryForKey(const char* key) {
+    return const_cast<Entry*>(GetConstEntryForKey(key));
+  }
+
+  Entry entries_[NumEntries];
+};
+
+// For historical reasons this specialized version is available with the same
+// size factors as a previous implementation.
+typedef NonAllocatingMap<256, 256, 64> SimpleStringDictionary;

[Robert Sesek, 2014/08/21 16:55:16]

Since you've named this file simple_string_dictionary.h and renamed the test,
why not rename the template class and use default template parameters instead.

[Mark Mentovai, 2014/08/22 14:05:26]

rsesek wrote:
Are you OK with having to instantiate it as SimpleStringDictionary<> with an
empty <> then?

[Robert Sesek, 2014/08/22 17:04:56]

I think so, yes. Or you could provide another typedef. I just think it's weird
that the bulk of this file is NonAllocatingMap but it's named for a single line
typedef. The only reason I did that in breakpad is because renaming files in
breakpad is painful.

+
+}  // namespace crashpad
+
+#endif  // CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_