Rewrite SimpleStringDictionary with NonAllocatingMap.

NonAllocatingMap has a near-identical interface, but is significantly less code,
more customizable, and has storage that is POD.

BUG=http://code.google.com/p/chromium/issues/detail?id=77656

Review URL: https://breakpad.appspot.com/568002

git-svn-id: http://google-breakpad.googlecode.com/svn/trunk@1161 4c0a9323-5329-0410-9bdc-e9ce6186880e

8 files changed, 384 insertions, 307 deletions

diff --git a/src/client/ios/Breakpad.mm b/src/client/ios/Breakpad.mm
index 39f4dc07..e8c4240b 100644
--- a/src/client/ios/Breakpad.mm
+++ b/src/client/ios/Breakpad.mm
@@ -67,9 +67,7 @@
 
 using google_breakpad::ConfigFile;
 using google_breakpad::EnsureDirectoryPathExists;
-using google_breakpad::KeyValueEntry;
 using google_breakpad::SimpleStringDictionary;
-using google_breakpad::SimpleStringDictionaryIterator;
 
 //=============================================================================
 // We want any memory allocations which are used by breakpad during the
@@ -469,10 +467,10 @@ void Breakpad::UploadData(NSData *data, NSString *name,
                           NSDictionary *server_parameters) {
   NSMutableDictionary *config = [NSMutableDictionary dictionary];
 
-  SimpleStringDictionaryIterator it(*config_params_);
-  while (const KeyValueEntry *next = it.Next()) {
-    [config setValue:[NSString stringWithUTF8String:next->GetValue()]
-              forKey:[NSString stringWithUTF8String:next->GetKey()]];
+  SimpleStringDictionary::Iterator it(*config_params_);
+  while (const SimpleStringDictionary::Entry *next = it.Next()) {
+    [config setValue:[NSString stringWithUTF8String:next->value]
+              forKey:[NSString stringWithUTF8String:next->key]];
   }
 
   Uploader *uploader =
diff --git a/src/client/mac/Framework/Breakpad.mm b/src/client/mac/Framework/Breakpad.mm
index 71555e8f..8967be1e 100644
--- a/src/client/mac/Framework/Breakpad.mm
+++ b/src/client/mac/Framework/Breakpad.mm
@@ -66,13 +66,11 @@
 #define catch(X)  if (false)
 #endif  // __EXCEPTIONS
 
-using google_breakpad::KeyValueEntry;
 using google_breakpad::MachPortSender;
 using google_breakpad::MachReceiveMessage;
 using google_breakpad::MachSendMessage;
 using google_breakpad::ReceivePort;
 using google_breakpad::SimpleStringDictionary;
-using google_breakpad::SimpleStringDictionaryIterator;
 
 //=============================================================================
 // We want any memory allocations which are used by breakpad during the
@@ -697,8 +695,8 @@ bool Breakpad::HandleException(int exception_type,
 
   if (result == KERN_SUCCESS) {
     // Now, send a series of key-value pairs to the Inspector.
-    const KeyValueEntry *entry = NULL;
-    SimpleStringDictionaryIterator iter(*config_params_);
+    const SimpleStringDictionary::Entry *entry = NULL;
+    SimpleStringDictionary::Iterator iter(*config_params_);
 
     while ( (entry = iter.Next()) ) {
       KeyValueMessageData keyvalue_data(*entry);
diff --git a/src/client/mac/crash_generation/ConfigFile.mm b/src/client/mac/crash_generation/ConfigFile.mm
index 0b7f0e15..7ff25378 100644
--- a/src/client/mac/crash_generation/ConfigFile.mm
+++ b/src/client/mac/crash_generation/ConfigFile.mm
@@ -166,15 +166,15 @@ void ConfigFile::WriteFile(const char* directory,
   BOOL result = YES;
   const SimpleStringDictionary &dictionary = *configurationParameters;
 
-  const KeyValueEntry *entry = NULL;
-  SimpleStringDictionaryIterator iter(dictionary);
+  const SimpleStringDictionary::Entry *entry = NULL;
+  SimpleStringDictionary::Iterator iter(dictionary);
 
   while ((entry = iter.Next())) {
     DEBUGLOG(stderr,
              "config: (%s) -> (%s)\n",
-             entry->GetKey(),
-             entry->GetValue());
-    result = AppendConfigString(entry->GetKey(), entry->GetValue());
+             entry->key,
+             entry->value);
+    result = AppendConfigString(entry->key, entry->value);
 
     if (!result)
       break;
diff --git a/src/client/mac/crash_generation/Inspector.h b/src/client/mac/crash_generation/Inspector.h
index 890e2157..4fb62f6b 100644
--- a/src/client/mac/crash_generation/Inspector.h
+++ b/src/client/mac/crash_generation/Inspector.h
@@ -65,13 +65,14 @@ struct InspectorInfo {
 struct KeyValueMessageData {
  public:
   KeyValueMessageData() {}
-  KeyValueMessageData(const google_breakpad::KeyValueEntry &inEntry) {
-    strlcpy(key, inEntry.GetKey(), sizeof(key) );
-    strlcpy(value, inEntry.GetValue(), sizeof(value) );
+  explicit KeyValueMessageData(
+      const google_breakpad::SimpleStringDictionary::Entry &inEntry) {
+    strlcpy(key, inEntry.key, sizeof(key) );
+    strlcpy(value, inEntry.value, sizeof(value) );
   }
 
-  char key[google_breakpad::KeyValueEntry::MAX_STRING_STORAGE_SIZE];
-  char value[google_breakpad::KeyValueEntry::MAX_STRING_STORAGE_SIZE];
+  char key[google_breakpad::SimpleStringDictionary::key_size];
+  char value[google_breakpad::SimpleStringDictionary::value_size];
 };
 
 using std::string;
diff --git a/src/common/mac/BreakpadRelease.xcconfig b/src/common/mac/BreakpadRelease.xcconfig
index af209a42..920f277d 100644
--- a/src/common/mac/BreakpadRelease.xcconfig
+++ b/src/common/mac/BreakpadRelease.xcconfig
@@ -31,3 +31,4 @@
 
 GCC_OPTIMIZATION_LEVEL = s
 GCC_WARN_UNINITIALIZED_AUTOS = YES
+GCC_PREPROCESSOR_DEFINITIONS = $(inherited) NDEBUG
diff --git a/src/common/simple_string_dictionary.cc b/src/common/simple_string_dictionary.cc
index f28ee9ef..e0a74cee 100644
--- a/src/common/simple_string_dictionary.cc
+++ b/src/common/simple_string_dictionary.cc
@@ -27,103 +27,19 @@
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
-#include <assert.h>
-
 #include "common/simple_string_dictionary.h"
 
 namespace google_breakpad {
 
-//==============================================================================
-const KeyValueEntry *SimpleStringDictionary::GetEntry(int i) const {
-  return (i >= 0 && i < MAX_NUM_ENTRIES) ? &entries_[i] : NULL;
-}
-
-//==============================================================================
-int SimpleStringDictionary::GetCount() const {
-  int count = 0;
-  for (int i = 0; i < MAX_NUM_ENTRIES; ++i) {
-    if (entries_[i].IsActive() ) {
-      ++count;
-    }
-  }
-
-  return count;
-}
-
-//==============================================================================
-const char *SimpleStringDictionary::GetValueForKey(const char *key) const {
-  assert(key);
-  if (!key)
-    return NULL;
-
-  for (int i = 0; i < MAX_NUM_ENTRIES; ++i) {
-    const KeyValueEntry &entry = entries_[i];
-    if (entry.IsActive() && !strcmp(entry.GetKey(), key)) {
-      return entry.GetValue();
-    }
-  }
-
-  return NULL;
-}
-
-//==============================================================================
-void SimpleStringDictionary::SetKeyValue(const char *key,
-                                         const char *value) {
-  if (!value) {
-    RemoveKey(key);
-    return;
-  }
-
-  // key must not be NULL
-  assert(key);
-  if (!key)
-    return;
-
-  // key must not be empty string
-  assert(key[0] != '\0');
-  if (key[0] == '\0')
-    return;
-
-  int free_index = -1;
-
-  // check if key already exists
-  for (int i = 0; i < MAX_NUM_ENTRIES; ++i) {
-    KeyValueEntry &entry = entries_[i];
-
-    if (entry.IsActive()) {
-      if (!strcmp(entry.GetKey(), key)) {
-        entry.SetValue(value);
-        return;
-      }
-    } else {
-      // Make a note of an empty slot
-      if (free_index == -1) {
-        free_index = i;
-      }
-    }
-  }
-
-  // check if we've run out of space
-  assert(free_index != -1);
-
-  // Put new key into an empty slot (if found)
-  if (free_index != -1) {
-    entries_[free_index].SetKeyValue(key, value);
-  }
-}
+namespace {
 
-//==============================================================================
-void SimpleStringDictionary::RemoveKey(const char *key) {
-  assert(key);
-  if (!key)
-    return;
+// In C++98 (ISO 14882), section 9.5.1 says that a union cannot have a member
+// with a non-trivial ctor, copy ctor, dtor, or assignment operator. Use this
+// property to ensure that Entry remains POD.
+union Compile_Assert {
+  NonAllocatingMap<1, 1, 1>::Entry Compile_Assert__entry_must_be_pod;
+};
 
-  for (int i = 0; i < MAX_NUM_ENTRIES; ++i) {
-    if (!strcmp(entries_[i].GetKey(), key)) {
-      entries_[i].Clear();
-      return;
-    }
-  }
 }
 
 }  // namespace google_breakpad
diff --git a/src/common/simple_string_dictionary.h b/src/common/simple_string_dictionary.h
index 26bcba57..20440f60 100644
--- a/src/common/simple_string_dictionary.h
+++ b/src/common/simple_string_dictionary.h
@@ -30,165 +30,232 @@
 #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 {
 
-//==============================================================================
-// SimpleStringDictionary (and associated class KeyValueEntry) implement a very
-// basic dictionary container class.  It has the property of not making any
-// memory allocations when getting and setting values.  But it is not very
-// efficient, with calls to get and set values operating in linear time.
-// It has the additional limitation of having a fairly small fixed capacity of
-// SimpleStringDictionary::MAX_NUM_ENTRIES entries.  An assert() will fire if
-// the client attempts to set more than this number of key/value pairs.
-// Ordinarilly a C++ programmer would use something like the std::map template
-// class, or on the Macintosh would often choose CFDictionary or NSDictionary.
-// But these dictionary classes may call malloc() during get and set operations.
-// Google Breakpad requires that no memory allocations be made in code running
-// in its exception handling thread, so it uses SimpleStringDictionary as the
-// underlying implementation for the GoogleBreakpad.framework APIs:
-// GoogleBreakpadSetKeyValue(),  GoogleBreakpadKeyValue(), and
-// GoogleBreakpadRemoveKeyValue()
-//
+// 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;
 
-//==============================================================================
-// KeyValueEntry
+// 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.
 //
-// A helper class used by SimpleStringDictionary representing a single
-// storage cell for a key/value pair.  Each key and value string are
-// limited to MAX_STRING_STORAGE_SIZE-1 bytes (not glyphs).  This class
-// performs no memory allocations.  It has methods for setting  and getting
-// key and value strings.
+// The actual map storage (the Entry) is guaranteed to be POD, so that it can
+// be transmitted over various IPC mechanisms.
 //
-class KeyValueEntry {
+// 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:
-  KeyValueEntry() {
-    Clear();
+  // 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_() {
   }
 
-  KeyValueEntry(const char *key, const char *value) {
-    SetKeyValue(key, value);
+  NonAllocatingMap(const NonAllocatingMap& other) {
+    *this = other;
   }
 
-  void SetKeyValue(const char *key, const char *value) {
-    if (!key) {
-      key = "";
-    }
-    if (!value) {
-      value = "";
+  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;
+  }
 
-    strncpy(key_, key, sizeof(key_));
-    strncpy(value_, value, sizeof(value_));
-    key_[sizeof(key_) - 1] = '\0';
-    value_[sizeof(value_) - 1] = '\0';
+  // 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);
+    }
   }
 
-  void SetValue(const char *value) {
-    if (!value) {
-      value = "";
+  // 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;
+      }
     }
-    strncpy(value_, value, sizeof(value_));
-    value_[sizeof(value_) - 1] = '\0';
-  };
+    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;
 
-  // Removes the key/value
-  void Clear() {
-    memset(key_, 0, sizeof(key_));
-    memset(value_, 0, sizeof(value_));
+    return entry->value;
   }
 
-  bool IsActive() const { return key_[0] != '\0'; }
-  const char *GetKey() const { return key_; }
-  const char *GetValue() const { return 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.
+  void SetKeyValue(const char* key, const char* value) {
+    if (!value) {
+      RemoveKey(key);
+      return;
+    }
 
-  // Don't change this without considering the fixed size
-  // of MachMessage (in MachIPC.h)
-  // (see also struct KeyValueMessageData in Inspector.h)
-  enum {MAX_STRING_STORAGE_SIZE = 256};
+    assert(key);
+    if (!key)
+      return;
 
- private:
-  char key_[MAX_STRING_STORAGE_SIZE];
-  char value_[MAX_STRING_STORAGE_SIZE];
-};
+    // Key must not be an empty string.
+    assert(key[0] != '\0');
+    if (key[0] == '\0')
+      return;
 
-//==============================================================================
-// This class is not an efficient dictionary, but for the purposes of breakpad
-// will be just fine.  We're just dealing with ten or so distinct
-// key/value pairs.  The idea is to avoid any malloc() or free() calls
-// in certain important methods to be called when a process is in a
-// crashed state.  Each key and value string are limited to
-// KeyValueEntry::MAX_STRING_STORAGE_SIZE-1 bytes (not glyphs).  Strings passed
-// in exceeding this length will be truncated.
-//
-class SimpleStringDictionary {
- public:
-  SimpleStringDictionary() {};  // entries will all be cleared
+    Entry* entry = GetEntryForKey(key);
 
-  // Returns the number of active key/value pairs.  The upper limit for this
-  // is MAX_NUM_ENTRIES.
-  int GetCount() const;
+    // 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];
 
-  // Given |key|, returns its corresponding |value|.
-  // If |key| is NULL, an assert will fire or NULL will be returned.  If |key|
-  // is not found or is an empty string, NULL is returned.
-  const char *GetValueForKey(const char *key) const;
+          assert(strlen(key) < key_size);
 
-  // Stores a string |value| represented by |key|.  If |key| is NULL or an empty
-  // string, this will assert (or do nothing).  If |value| is NULL then
-  // the |key| will be removed.  An empty string is OK for |value|.
-  void SetKeyValue(const char *key, const char *value);
+          strncpy(entry->key, key, key_size);
+          entry->key[key_size - 1] = '\0';
 
-  // Given |key|, removes any associated value.  It will assert (or do nothing)
-  // if NULL is passed in.  It will do nothing if |key| is not found.
-  void RemoveKey(const char *key);
+          break;
+        }
+      }
+    }
 
-  // This is the maximum number of key/value pairs which may be set in the
-  // dictionary.  An assert may fire if more values than this are set.
-  // Don't change this without also changing comment in GoogleBreakpad.h
-  enum {MAX_NUM_ENTRIES = 64};
+    // If the map is out of space, entry will be NULL.
+    assert(entry);
 
- private:
-  friend class SimpleStringDictionaryIterator;
+#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
 
-  const KeyValueEntry *GetEntry(int i) const;
+    assert(strlen(value) < value_size);
+    strncpy(entry->value, value, value_size);
+    entry->value[value_size - 1] = '\0';
+  }
 
-  KeyValueEntry entries_[MAX_NUM_ENTRIES];
-};
+  // 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;
 
-//==============================================================================
-class SimpleStringDictionaryIterator {
- public:
-  SimpleStringDictionaryIterator(const SimpleStringDictionary &dict)
-    : dict_(dict), i_(0) {
+    Entry* entry = GetEntryForKey(key);
+    if (entry) {
+      entry->key[0] = '\0';
+      entry->value[0] = '\0';
     }
 
-  // Initializes iterator to the beginning (may later call Next() )
-  void Start() {
-    i_ = 0;
+#ifndef NDEBUG
+    assert(GetEntryForKey(key) == NULL);
+#endif
   }
 
-  // like the nextObject method of NSEnumerator (in Cocoa)
-  // returns NULL when there are no more entries
-  //
-  const KeyValueEntry* Next() {
-    for (; i_ < SimpleStringDictionary::MAX_NUM_ENTRIES; ++i_) {
-      const KeyValueEntry *entry = dict_.GetEntry(i_);
-      if (entry->IsActive()) {
-        i_++;   // move to next entry for next time
-        return entry;
+  // 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;
+  }
 
-    return NULL;  // reached end of array
+  Entry* GetEntryForKey(const char* key) {
+    return const_cast<Entry*>(GetConstEntryForKey(key));
   }
 
- private:
-  const SimpleStringDictionary& dict_;
-  int i_;
+  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_
diff --git a/src/common/simple_string_dictionary_unittest.cc b/src/common/simple_string_dictionary_unittest.cc
index ff02115e..ec05cfaa 100644
--- a/src/common/simple_string_dictionary_unittest.cc
+++ b/src/common/simple_string_dictionary_unittest.cc
@@ -32,99 +32,106 @@
 
 namespace google_breakpad {
 
-//==============================================================================
-TEST(SimpleStringDictionaryTest, KeyValueEntry) {
-  KeyValueEntry entry;
-
-  // Verify that initial state is correct
-  EXPECT_FALSE(entry.IsActive());
-  EXPECT_EQ(strlen(entry.GetKey()), 0u);
-  EXPECT_EQ(strlen(entry.GetValue()), 0u);
-
-  // Try setting a key/value and then verify
-  entry.SetKeyValue("key1", "value1");
-  EXPECT_STREQ(entry.GetKey(), "key1");
-  EXPECT_STREQ(entry.GetValue(), "value1");
-
-  // Try setting a new value
-  entry.SetValue("value3");
-
-  // Make sure the new value took
-  EXPECT_STREQ(entry.GetValue(), "value3");
-
-  // Make sure the key didn't change
-  EXPECT_STREQ(entry.GetKey(), "key1");
-
-  // Try setting a new key/value and then verify
-  entry.SetKeyValue("key2", "value2");
-  EXPECT_STREQ(entry.GetKey(), "key2");
-  EXPECT_STREQ(entry.GetValue(), "value2");
-
-  // Clear the entry and verify the key and value are empty strings
-  entry.Clear();
-  EXPECT_FALSE(entry.IsActive());
-  EXPECT_EQ(strlen(entry.GetKey()), 0u);
-  EXPECT_EQ(strlen(entry.GetValue()), 0u);
+TEST(NonAllocatingMapTest, Entry) {
+  typedef NonAllocatingMap<5, 9, 15> TestMap;
+  TestMap map;
+
+  const TestMap::Entry* entry = TestMap::Iterator(map).Next();
+  EXPECT_FALSE(entry);
+
+  // Try setting a key/value and then verify.
+  map.SetKeyValue("key1", "value1");
+  entry = TestMap::Iterator(map).Next();
+  ASSERT_TRUE(entry);
+  EXPECT_STREQ(entry->key, "key1");
+  EXPECT_STREQ(entry->value, "value1");
+
+  // Try setting a new value.
+  map.SetKeyValue("key1", "value3");
+  EXPECT_STREQ(entry->value, "value3");
+
+  // Make sure the key didn't change.
+  EXPECT_STREQ(entry->key, "key1");
+
+  // Clear the entry and verify the key and value are empty strings.
+  map.RemoveKey("key1");
+  EXPECT_FALSE(entry->is_active());
+  EXPECT_EQ(strlen(entry->key), 0u);
+  EXPECT_EQ(strlen(entry->value), 0u);
 }
 
-TEST(SimpleStringDictionaryTest, EmptyKeyValueCombos) {
-  KeyValueEntry entry;
-  entry.SetKeyValue(NULL, NULL);
-  EXPECT_STREQ(entry.GetKey(), "");
-  EXPECT_STREQ(entry.GetValue(), "");
-}
-
-
-//==============================================================================
-TEST(SimpleStringDictionaryTest, SimpleStringDictionary) {
+TEST(NonAllocatingMapTest, SimpleStringDictionary) {
   // Make a new dictionary
-  SimpleStringDictionary *dict = new SimpleStringDictionary();
-  ASSERT_TRUE(dict);
+  SimpleStringDictionary dict;
 
   // Set three distinct values on three keys
-  dict->SetKeyValue("key1", "value1");
-  dict->SetKeyValue("key2", "value2");
-  dict->SetKeyValue("key3", "value3");
-
-  EXPECT_NE(dict->GetValueForKey("key1"), "value1");
-  EXPECT_NE(dict->GetValueForKey("key2"), "value2");
-  EXPECT_NE(dict->GetValueForKey("key3"), "value3");
-  EXPECT_EQ(dict->GetCount(), 3);
+  dict.SetKeyValue("key1", "value1");
+  dict.SetKeyValue("key2", "value2");
+  dict.SetKeyValue("key3", "value3");
+
+  EXPECT_NE(dict.GetValueForKey("key1"), "value1");
+  EXPECT_NE(dict.GetValueForKey("key2"), "value2");
+  EXPECT_NE(dict.GetValueForKey("key3"), "value3");
+  EXPECT_EQ(dict.GetCount(), 3u);
   // try an unknown key
-  EXPECT_FALSE(dict->GetValueForKey("key4"));
+  EXPECT_FALSE(dict.GetValueForKey("key4"));
 
   // Remove a key
-  dict->RemoveKey("key3");
+  dict.RemoveKey("key3");
 
   // Now make sure it's not there anymore
-  EXPECT_FALSE(dict->GetValueForKey("key3"));
+  EXPECT_FALSE(dict.GetValueForKey("key3"));
 
   // Remove by setting value to NULL
-  dict->SetKeyValue("key2", NULL);
+  dict.SetKeyValue("key2", NULL);
 
   // Now make sure it's not there anymore
-  EXPECT_FALSE(dict->GetValueForKey("key2"));
+  EXPECT_FALSE(dict.GetValueForKey("key2"));
 }
 
-//==============================================================================
-// The idea behind this test is to add a bunch of values to the dictionary,
-// remove some in the middle, then add a few more in.  We then create a
-// SimpleStringDictionaryIterator and iterate through the dictionary, taking
-// note of the key/value pairs we see.  We then verify that it iterates
-// through exactly the number of key/value pairs we expect, and that they
-// match one-for-one with what we would expect.  In all cases we're setting
-// key value pairs of the form:
-//
-// key<n>/value<n>   (like key0/value0, key17,value17, etc.)
-//
-TEST(SimpleStringDictionaryTest, SimpleStringDictionaryIterator) {
-  SimpleStringDictionary *dict = new SimpleStringDictionary();
+TEST(NonAllocatingMapTest, CopyAndAssign) {
+  NonAllocatingMap<10, 10, 10> map;
+  map.SetKeyValue("one", "a");
+  map.SetKeyValue("two", "b");
+  map.SetKeyValue("three", "c");
+  map.RemoveKey("two");
+  EXPECT_EQ(2u, map.GetCount());
+
+  // Test copy.
+  NonAllocatingMap<10, 10, 10> map_copy(map);
+  EXPECT_EQ(2u, map_copy.GetCount());
+  EXPECT_STREQ("a", map_copy.GetValueForKey("one"));
+  EXPECT_STREQ("c", map_copy.GetValueForKey("three"));
+  map_copy.SetKeyValue("four", "d");
+  EXPECT_STREQ("d", map_copy.GetValueForKey("four"));
+  EXPECT_FALSE(map.GetValueForKey("four"));
+
+  // Test assign.
+  NonAllocatingMap<10, 10, 10> map_assign;
+  map_assign = map;
+  EXPECT_EQ(2u, map_assign.GetCount());
+  EXPECT_STREQ("a", map_assign.GetValueForKey("one"));
+  EXPECT_STREQ("c", map_assign.GetValueForKey("three"));
+  map_assign.SetKeyValue("four", "d");
+  EXPECT_STREQ("d", map_assign.GetValueForKey("four"));
+  EXPECT_FALSE(map.GetValueForKey("four"));
+
+  map.RemoveKey("one");
+  EXPECT_FALSE(map.GetValueForKey("one"));
+  EXPECT_STREQ("a", map_copy.GetValueForKey("one"));
+  EXPECT_STREQ("a", map_assign.GetValueForKey("one"));
+}
+
+// Add a bunch of values to the dictionary, remove some entries in the middle,
+// and then add more.
+TEST(NonAllocatingMapTest, Iterator) {
+  SimpleStringDictionary* dict = new SimpleStringDictionary();
   ASSERT_TRUE(dict);
 
-  char key[KeyValueEntry::MAX_STRING_STORAGE_SIZE];
-  char value[KeyValueEntry::MAX_STRING_STORAGE_SIZE];
+  char key[SimpleStringDictionary::key_size];
+  char value[SimpleStringDictionary::value_size];
 
-  const int kDictionaryCapacity = SimpleStringDictionary::MAX_NUM_ENTRIES;
+  const int kDictionaryCapacity = SimpleStringDictionary::num_entries;
   const int kPartitionIndex = kDictionaryCapacity - 5;
 
   // We assume at least this size in the tests below
@@ -163,7 +170,7 @@ TEST(SimpleStringDictionaryTest, SimpleStringDictionaryIterator) {
   expectedDictionarySize += kDictionaryCapacity - kPartitionIndex;
 
   // Now create an iterator on the dictionary
-  SimpleStringDictionaryIterator iter(*dict);
+  SimpleStringDictionary::Iterator iter(*dict);
 
   // We then verify that it iterates through exactly the number of
   // key/value pairs we expect, and that they match one-for-one with what we
@@ -175,18 +182,17 @@ TEST(SimpleStringDictionaryTest, SimpleStringDictionaryIterator) {
 
   int totalCount = 0;
 
-  const KeyValueEntry *entry;
-
+  const SimpleStringDictionary::Entry* entry;
   while ((entry = iter.Next())) {
     totalCount++;
 
     // Extract keyNumber from a string of the form key<keyNumber>
     int keyNumber;
-    sscanf(entry->GetKey(), "key%d", &keyNumber);
+    sscanf(entry->key, "key%d", &keyNumber);
 
     // Extract valueNumber from a string of the form value<valueNumber>
     int valueNumber;
-    sscanf(entry->GetValue(), "value%d", &valueNumber);
+    sscanf(entry->value, "value%d", &valueNumber);
 
     // The value number should equal the key number since that's how we set them
     EXPECT_EQ(keyNumber, valueNumber);
@@ -207,7 +213,7 @@ TEST(SimpleStringDictionaryTest, SimpleStringDictionaryIterator) {
 
   // Make sure each of the key/value pairs showed up exactly one time, except
   // for the ones which we removed.
-  for (int i = 0; i < kDictionaryCapacity; ++i) {
+  for (size_t i = 0; i < kDictionaryCapacity; ++i) {
     // Skip over key7, key18, key23, and key31, since we removed them
     if (!(i == 7 || i == 18 || i == 23 || i == 31)) {
       EXPECT_EQ(count[i], 1);
@@ -218,4 +224,94 @@ TEST(SimpleStringDictionaryTest, SimpleStringDictionaryIterator) {
   EXPECT_EQ(totalCount, expectedDictionarySize);
 }
 
+
+TEST(NonAllocatingMapTest, AddRemove) {
+  NonAllocatingMap<5, 7, 6> map;
+  map.SetKeyValue("rob", "ert");
+  map.SetKeyValue("mike", "pink");
+  map.SetKeyValue("mark", "allays");
+
+  EXPECT_EQ(3u, map.GetCount());
+  EXPECT_STREQ("ert", map.GetValueForKey("rob"));
+  EXPECT_STREQ("pink", map.GetValueForKey("mike"));
+  EXPECT_STREQ("allays", map.GetValueForKey("mark"));
+
+  map.RemoveKey("mike");
+
+  EXPECT_EQ(2u, map.GetCount());
+  EXPECT_FALSE(map.GetValueForKey("mike"));
+
+  map.SetKeyValue("mark", "mal");
+  EXPECT_EQ(2u, map.GetCount());
+  EXPECT_STREQ("mal", map.GetValueForKey("mark"));
+
+  map.RemoveKey("mark");
+  EXPECT_EQ(1u, map.GetCount());
+  EXPECT_FALSE(map.GetValueForKey("mark"));
+}
+
+TEST(NonAllocatingMapTest, Serialize) {
+  typedef NonAllocatingMap<4, 5, 7> TestMap;
+  TestMap map;
+  map.SetKeyValue("one", "abc");
+  map.SetKeyValue("two", "def");
+  map.SetKeyValue("tre", "hig");
+
+  EXPECT_STREQ("abc", map.GetValueForKey("one"));
+  EXPECT_STREQ("def", map.GetValueForKey("two"));
+  EXPECT_STREQ("hig", map.GetValueForKey("tre"));
+
+  const SerializedNonAllocatingMap* serialized;
+  size_t size = map.Serialize(&serialized);
+
+  SerializedNonAllocatingMap* serialized_copy =
+      reinterpret_cast<SerializedNonAllocatingMap*>(malloc(size));
+  ASSERT_TRUE(serialized_copy);
+  memcpy(serialized_copy, serialized, size);
+
+  TestMap deserialized(serialized_copy, size);
+  free(serialized_copy);
+
+  EXPECT_EQ(3u, deserialized.GetCount());
+  EXPECT_STREQ("abc", deserialized.GetValueForKey("one"));
+  EXPECT_STREQ("def", deserialized.GetValueForKey("two"));
+  EXPECT_STREQ("hig", deserialized.GetValueForKey("tre"));
+}
+
+#ifndef NDEBUG
+
+TEST(NonAllocatingMapTest, OutOfSpace) {
+  NonAllocatingMap<3, 2, 2> map;
+  map.SetKeyValue("a", "1");
+  map.SetKeyValue("b", "2");
+  ASSERT_DEATH(map.SetKeyValue("c", "3"), "");
+}
+
+TEST(NonAllocatingMapTest, KeyTooLong) {
+  NonAllocatingMap<3, 10, 12> map;
+  map.SetKeyValue("ab", "cdefghi");
+  ASSERT_DEATH(map.SetKeyValue("abcdef", "1"), "");
+}
+
+TEST(NonAllocatingMapTest, ValueTooLong) {
+  NonAllocatingMap<9, 3, 8> map;
+  map.SetKeyValue("abcd", "ab");
+  ASSERT_DEATH(map.SetKeyValue("abcd", "abc"), "");
+}
+
+TEST(NonAllocatingMapTest, NullKey) {
+  NonAllocatingMap<4, 6, 6> map;
+  ASSERT_DEATH(map.SetKeyValue(NULL, "hello"), "");
+
+  map.SetKeyValue("hi", "there");
+  ASSERT_DEATH(map.GetValueForKey(NULL), "");
+  EXPECT_STREQ("there", map.GetValueForKey("hi"));
+
+  ASSERT_DEATH(map.GetValueForKey(NULL), "");
+  map.RemoveKey("hi");
+  EXPECT_EQ(0u, map.GetCount());
+}
+
+#endif  // !NDEBUG
+
 }  // namespace google_breakpad