From 77acc6adabb7ff90a2de3636b48ee1ad2c52f525 Mon Sep 17 00:00:00 2001 From: "rsesek@chromium.org" Date: Wed, 24 Apr 2013 18:15:48 +0000 Subject: 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 --- src/client/ios/Breakpad.mm | 10 +- src/client/mac/Framework/Breakpad.mm | 6 +- src/client/mac/crash_generation/ConfigFile.mm | 10 +- src/client/mac/crash_generation/Inspector.h | 11 +- src/common/mac/BreakpadRelease.xcconfig | 1 + src/common/simple_string_dictionary.cc | 98 +------- src/common/simple_string_dictionary.h | 299 +++++++++++++++--------- src/common/simple_string_dictionary_unittest.cc | 256 +++++++++++++------- 8 files changed, 384 insertions(+), 307 deletions(-) (limited to 'src') 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 - #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 #include +#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 +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(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(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/value (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 int keyNumber; - sscanf(entry->GetKey(), "key%d", &keyNumber); + sscanf(entry->key, "key%d", &keyNumber); // Extract valueNumber from a string of the form value 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(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 -- cgit v1.2.1