Add SimpleStringDictionary and its test

client/simple_string_dictionary.h

+// Copyright (c) 2007, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef COMMON_SIMPLE_STRING_DICTIONARY_H_
+#define COMMON_SIMPLE_STRING_DICTIONARY_H_
+
+#include <assert.h>
+#include <string.h>
+
+#include "common/basictypes.h"
+
+namespace google_breakpad {
+
+// 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),

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

I'm not sure these clang-format changes are actually improvements.

+          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) {
+    assert(other.key_size == key_size);
+    assert(other.value_size == value_size);
+    assert(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) {
+    assert(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 {
+    assert(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;
+    }
+
+    assert(key);
+    if (!key)
+      return;
+
+    // Key must not be an empty string.
+    assert(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;
+    }
+    assert(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) {
+    assert(key);
+    if (!key)
+      return;
+
+    Entry* entry = GetEntryForKey(key);
+    if (entry) {
+      entry->key[0] = '\0';
+      entry->value[0] = '\0';
+    }
+
+#ifndef NDEBUG
+    assert(GetEntryForKey(key) == NULL);
+#endif
+  }
+
+  // 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;
+
+}  // namespace google_breakpad
+
+#endif  // COMMON_SIMPLE_STRING_DICTIONARY_H_