aboutsummaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
authorrsesek@chromium.org <rsesek@chromium.org@4c0a9323-5329-0410-9bdc-e9ce6186880e>2013-04-24 18:15:48 +0000
committerrsesek@chromium.org <rsesek@chromium.org@4c0a9323-5329-0410-9bdc-e9ce6186880e>2013-04-24 18:15:48 +0000
commit77acc6adabb7ff90a2de3636b48ee1ad2c52f525 (patch)
tree3c8af5e76ab45e393390ea90b7b98932a337ffb7 /src/common
parentImprove ARM CPU info reporting. (diff)
downloadbreakpad-77acc6adabb7ff90a2de3636b48ee1ad2c52f525.tar.xz
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
Diffstat (limited to 'src/common')
-rw-r--r--src/common/mac/BreakpadRelease.xcconfig1
-rw-r--r--src/common/simple_string_dictionary.cc98
-rw-r--r--src/common/simple_string_dictionary.h299
-rw-r--r--src/common/simple_string_dictionary_unittest.cc256
4 files changed, 367 insertions, 287 deletions
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