From 219e8de3c9edf9958c10fa21ac2fd046fd3dadfa Mon Sep 17 00:00:00 2001 From: Subhransu Mohanty Date: Wed, 2 Sep 2020 11:25:10 +0900 Subject: [PATCH] refactor Dictionary class. - use range for and algorithms instead of iterators. - use std::string_view as argument for Remove() and Find() Api. - remove redundant apis. Change-Id: I88954d471f736982a400c2e2dae62456db17c1b2 --- .../src/dali-toolkit-internal/CMakeLists.txt | 1 + .../dali-toolkit-internal/utc-Dali-Dictionary.cpp | 284 +++++++++++++++++++++ dali-toolkit/internal/builder/dictionary.h | 174 +++++-------- 3 files changed, 350 insertions(+), 109 deletions(-) create mode 100644 automated-tests/src/dali-toolkit-internal/utc-Dali-Dictionary.cpp diff --git a/automated-tests/src/dali-toolkit-internal/CMakeLists.txt b/automated-tests/src/dali-toolkit-internal/CMakeLists.txt index 5ff5890..ddd196c 100755 --- a/automated-tests/src/dali-toolkit-internal/CMakeLists.txt +++ b/automated-tests/src/dali-toolkit-internal/CMakeLists.txt @@ -12,6 +12,7 @@ SET(TC_SOURCES utc-Dali-ColorConversion.cpp utc-Dali-Control-internal.cpp utc-Dali-DebugRendering.cpp + utc-Dali-Dictionary.cpp utc-Dali-FeedbackStyle.cpp utc-Dali-ItemView-internal.cpp utc-Dali-LogicalModel.cpp diff --git a/automated-tests/src/dali-toolkit-internal/utc-Dali-Dictionary.cpp b/automated-tests/src/dali-toolkit-internal/utc-Dali-Dictionary.cpp new file mode 100644 index 0000000..698377e --- /dev/null +++ b/automated-tests/src/dali-toolkit-internal/utc-Dali-Dictionary.cpp @@ -0,0 +1,284 @@ +/* + * Copyright (c) 2020 Samsung Electronics Co., Ltd. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include +using namespace Dali::Toolkit::Internal; + + +std::string_view test_keys[20] = +{ + "testkey0", "testkey1", "testkey2", "testkey3", "testkey4", "testkey5", "testkey6", "testkey7", "testkey8", "testkey9", + "testkey10", "testkey11", "testkey12", "testkey13", "testkey14", "testkey15", "testkey16", "testkey17", "testkey18", "testkey19" +}; + +std::string_view testKeys[20] = +{ + "TestKey0", "TestKey1", "TestKey2", "TestKey3", "TestKey4", "TestKey5", "TestKey6", "TestKey7", "TestKey8", "TestKey9", + "TestKey10", "TestKey11", "TestKey12", "TestKey13", "TestKey14", "TestKey15", "TestKey16", "TestKey17", "TestKey18", "TestKey19" +}; + + +int UtcDaliBuilderDictionaryNew(void) +{ + Dictionary dictionary; + + DictionaryKeys keys; + dictionary.GetKeys(keys); + + DALI_TEST_CHECK( keys.empty() ); + DALI_TEST_EQUALS( keys.size(), 0, TEST_LOCATION ); + END_TEST; +} + + +int UtcDaliBuilderDictionaryAdd1(void) +{ + Dictionary dictionary; + + for(int i=0; i<10; i++) + { + char buffer[16]; + sprintf(buffer, "testkey%d",i); + bool added=false; + if(i%2 == 0) + { + added = dictionary.Add(std::string(buffer), i); + } + else + { + added = dictionary.Add(buffer, i); + } + DALI_TEST_EQUALS(added, true, TEST_LOCATION); + } + + DictionaryKeys keys; + dictionary.GetKeys(keys); + + DALI_TEST_EQUALS( keys.size(), 10, TEST_LOCATION ); + for(int i=0; i<10; i++) + { + char buffer[16]; + sprintf(buffer, "testkey%d",i); + auto iter = std::find(keys.begin(), keys.end(), std::string(buffer)); + DALI_TEST_CHECK(iter != keys.end()); + } + + END_TEST; +} + +int UtcDaliBuilderDictionaryAdd2(void) +{ + Dictionary dictionary; + + for(int i=0; i<10; i++) + { + char buffer[16]; + sprintf(buffer, "testkey%d",i); + bool added=false; + if(i%2 == 0) + { + added = dictionary.Add(std::string(buffer), i); + } + else + { + added = dictionary.Add(buffer, i); + } + DALI_TEST_EQUALS(added, true, TEST_LOCATION); + } + + DictionaryKeys keys; + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 10, TEST_LOCATION ); + + bool added = dictionary.Add("testkey5", 1); + DALI_TEST_EQUALS(added, false, TEST_LOCATION); + DALI_TEST_EQUALS(*dictionary.Find("testkey5"), 5, TEST_LOCATION); + + dictionary.Clear(); + DALI_TEST_EQUALS(dictionary.Begin()==dictionary.End(), true, TEST_LOCATION); + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 0, TEST_LOCATION ); + + END_TEST; +} + + +int UtcDaliBuilderDictionaryRemoveP(void) +{ + Dictionary dictionary; + + for(int i=0; i<10; i++) + { + bool added=false; + added = dictionary.Add(std::string(testKeys[i]), i); + DALI_TEST_EQUALS(added, true, TEST_LOCATION); + } + + DictionaryKeys keys; + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 10, TEST_LOCATION ); + + for(int i=0; i<10; i++) + { + if(i%2==0) + { + dictionary.Remove(test_keys[i]); // Should fail (case sensitive) + } + else + { + dictionary.Remove(testKeys[i]); + } + } + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 5, TEST_LOCATION ); + + dictionary.Clear(); + DALI_TEST_EQUALS(dictionary.Begin()==dictionary.End(), true, TEST_LOCATION); + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 0, TEST_LOCATION ); + + END_TEST; +} + + +int UtcDaliBuilderDictionaryRemoveN(void) +{ + Dictionary dictionary; + + for(int i=0; i<10; i++) + { + bool added=false; + added = dictionary.Add(std::string(testKeys[i]), i); + DALI_TEST_EQUALS(added, true, TEST_LOCATION); + } + + DictionaryKeys keys; + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 10, TEST_LOCATION ); + + dictionary.Remove("randomkey"); + dictionary.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 10, TEST_LOCATION ); + + END_TEST; +} + + +int UtcDaliBuilderDictionaryMerge1(void) +{ + // Test that "overlapping" dicts merge into 1 successfully + Dictionary dictionary1; + + for(int i=0; i<10; i++) + { + dictionary1.Add(std::string(test_keys[i]), i); + } + + Dictionary dictionary2; + for(int i=0; i<20; i++) + { + dictionary2.Add(std::string(testKeys[i]), i); + } + + dictionary1.Merge(dictionary2); + DictionaryKeys keys; + dictionary1.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 30, TEST_LOCATION ); // Now have 2 case versions of 10 keys :/ - broken by design? + + for(int i=0; i<20;++i) + { + // Check both cases of keys + auto ptr1 = dictionary1.FindConst(test_keys[i]); + auto ptr2 = dictionary1.FindConst(testKeys[i]); + + DALI_TEST_CHECK( nullptr != ptr1 ); + DALI_TEST_CHECK( nullptr != ptr2 ); + } + + END_TEST; +} + +int UtcDaliBuilderDictionaryMerge2(void) +{ + // Test that non-overlapping dicts merge successfully + Dictionary dictionary1; + for(int i=0; i<10; i++) // Add first 10 from lowercase keys + { + dictionary1.Add(std::string(test_keys[i]), i); + } + + Dictionary dictionary2; + for(int i=10; i<20; i++) // add last 10 from capitalized keys + { + dictionary2.Add(std::string(testKeys[i]), i); + } + + dictionary1.Merge(dictionary2); + DictionaryKeys keys; + dictionary1.GetKeys(keys); + DALI_TEST_EQUALS( keys.size(), 20, TEST_LOCATION ); // check it's an amalgam of both + + for(int i=0; i<20;++i) + { + // Check both cases of keys + DALI_TEST_CHECK( nullptr != dictionary1.FindConst(test_keys[i])); + DALI_TEST_CHECK( nullptr != dictionary1.FindConst(testKeys[i])); + } + + END_TEST; +} + + +template +struct TestElement +{ + std::string key; + EntryType entry; + TestElement(std::string name, EntryType entry) + : key(std::move(name)), + entry(std::move(entry)) + { + } +}; + +int UtcDaliBuilderDictionaryFindP(void) +{ + // Test that non-overlapping dicts merge successfully + Dictionary dictionary; + for(int i=0; i<10; i++) // Add first 10 from lowercase keys + { + dictionary.Add(std::string(test_keys[i]), i); + } + + // Test that the entries can be directly modified + for(int i=0; i<10; i++) + { + auto entryPtr = dictionary.Find(testKeys[i]); + DALI_TEST_CHECK( entryPtr != nullptr ); + *entryPtr = i+10; + } + + for(int i=0; i<10; ++i) + { + auto entryPtr = dictionary.Find(testKeys[i]); + DALI_TEST_CHECK( entryPtr != nullptr ); + DALI_TEST_EQUALS( *entryPtr, i+10, TEST_LOCATION ); + } + + END_TEST; +} diff --git a/dali-toolkit/internal/builder/dictionary.h b/dali-toolkit/internal/builder/dictionary.h index 65c7e18..a3036d9 100644 --- a/dali-toolkit/internal/builder/dictionary.h +++ b/dali-toolkit/internal/builder/dictionary.h @@ -2,7 +2,7 @@ #define DALI_TOOLKIT_INTERNAL_BUILDER_DICTIONARY_H /* - * Copyright (c) 2017 Samsung Electronics Co., Ltd. + * Copyright (c) 2020 Samsung Electronics Co., Ltd. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -39,17 +39,16 @@ namespace Internal * It enables lookup of keys via case-insensitive match. */ +using DictionaryKeys = std::vector; -typedef std::vector DictionaryKeys; inline void Merge( DictionaryKeys& toDict, const DictionaryKeys& fromDict ) { - for( DictionaryKeys::const_iterator fromIter = fromDict.begin(); fromIter != fromDict.end(); ++fromIter ) + for(const auto& element : fromDict) { - const std::string& fromKey = (*fromIter); - DictionaryKeys::iterator toIter = std::find( toDict.begin(), toDict.end(), fromKey ); - if( toIter == toDict.end() ) + auto iter = std::find(toDict.cbegin(), toDict.cend(), element); + if(iter == toDict.cend()) { - toDict.push_back( fromKey ); + toDict.push_back(element); } } } @@ -66,105 +65,97 @@ private: { std::string key; EntryType entry; - Element( const std::string&name, EntryType entry ) - : key( name ), - entry( entry ) + Element(std::string name, EntryType entry) + : key(std::move(name)), + entry(std::move(entry)) { } }; - typedef std::vector Elements; + using Elements = std::vector; Elements container; + auto FindElementCaseInsensitive(std::string_view key) const + { + return std::find_if( + Begin(), End(), [key](auto& e) { return Dali::CaseInsensitiveStringCompare(e.key, key); }); + } + + auto FindElement(std::string_view key) + { + return std::find_if(container.begin(), container.end(), [key](auto& e){ + return bool(key == e.key); + }); + } + public: /** * Only allow const iteration over the dictionary */ - typedef typename Elements::const_iterator iterator; + using iterator = typename Elements::const_iterator; /** * Constructor */ - Dictionary() - { - } + Dictionary() = default; /** * Add a key value pair to the dictionary. * If the entry does not already exist, add it to the dictionary - * using a shallow copy */ - bool Add( const std::string& name, const EntryType& entry ) + bool Add(std::string name, EntryType entry) { - for( typename Elements::iterator iter = container.begin(); iter != container.end(); ++iter ) + auto iter = FindElement(name); + if(iter != End()) { - if( iter->key == name ) - { - return false; - } + return false; } - container.push_back( Element(name, entry) ); + + container.push_back(Element(std::move(name), std::move(entry))); return true; } /** * Add a key-value pair to the dictionary * If the entry does not already exist, add it to the dictionary - * (shallow copy) */ - bool Add( const char* name, const EntryType& entry ) + bool Add(const char* name, EntryType entry) { - bool result=false; - if( name != NULL ) + if(name != nullptr) { - std::string theName(name); - result=Add(theName, entry); + return Add(std::string(name), std::move(entry)); } - return result; + return false; } /** * Remove a key value pair from the dictionary. */ - void Remove( const std::string& name ) + void Remove(std::string_view name) { - for( typename Elements::iterator iter = container.begin(); iter != container.end(); ++iter ) + if(!name.empty()) { - if( iter->key == name ) + auto iter = FindElement(name); + + if(iter != End()) { container.erase( iter ); - break; } } } - /** - * Remove a key value pair from the dictionary. - */ - void Remove( const char* name ) - { - if( name != NULL ) - { - std::string theName(name); - Remove(theName); - } - } - void Merge( const Dictionary& dictionary ) { - for( typename Elements::const_iterator fromIter = dictionary.container.begin(); fromIter != dictionary.container.end(); ++fromIter ) + for(const auto& element : dictionary.container) { - bool found=false; - for( typename Elements::iterator toIter = container.begin(); toIter != container.end(); ++toIter ) + auto iter = FindElement(element.key); + + if(iter == End()) { - if( fromIter->key == toIter->key ) - { - found=true; - toIter->entry = fromIter->entry; - } + container.push_back(Element(element.key, element.entry)); } - if( !found ) + else { - container.push_back( Element(fromIter->key, fromIter->entry) ); + iter->entry = element.entry; } } } @@ -173,92 +164,57 @@ public: * Find the element in the dictionary pointed at by key, and * insensitive search, and return a const pointer to it, or NULL */ - const EntryType* FindConst( const std::string& key ) const + const EntryType* FindConst(std::string_view key) const { if( ! key.empty() ) { - for( typename Elements::const_iterator iter = container.begin(); iter != container.end(); ++iter ) + auto iter = FindElementCaseInsensitive(key); + + if(iter != End()) { - if( Dali::CaseInsensitiveStringCompare(iter->key, key )) - { - const EntryType* result = &(iter->entry); - return result; - } + return &(iter->entry); } } - return NULL; + return nullptr; } /** * Find the element in the dictionary pointed at by key using a case * insensitive search, and return a non-const pointer to it, or NULL */ - EntryType* Find( const std::string& key ) const + EntryType* Find(std::string_view key) const { - EntryType* result = NULL; if( ! key.empty() ) { - for( typename Elements::const_iterator iter = container.begin(); iter != container.end(); ++iter ) + auto iter = FindElementCaseInsensitive(key); + + if(iter != End()) { - if( Dali::CaseInsensitiveStringCompare(iter->key, key )) - { - // Const cast because of const_iterator. const_iterator because, STL. - result = const_cast(&(iter->entry)); - } + return const_cast(&(iter->entry)); } } - return result; - } - - /** - * Find the element in the dictionary pointed at by key using a case - * insensitive search, and return a const pointer to it, or NULL - */ - const EntryType* FindConst( const char* key ) const - { - if( key != NULL ) - { - std::string theKey(key); - return FindConst( theKey ); - } - return NULL; + return nullptr; } - /** - * Find the element in the dictionary pointed at by key using a case - * insensitive search, and return a non-const pointer to it, or NULL - */ - EntryType* Find( const char* key ) const - { - if( key != NULL ) - { - std::string theKey(key); - return Find( theKey ); - } - return NULL; - } - /** - * Return an iterator pointing at the first entry in the dictionary - */ - typename Elements::const_iterator Begin() const + iterator Begin() const { - return container.begin(); + return container.cbegin(); } /** * Return an iterator pointing past the last entry in the dictionary */ - typename Elements::const_iterator End() const + iterator End() const { - return container.end(); + return container.cend(); } void GetKeys( DictionaryKeys& keys ) const { keys.clear(); - for( typename Elements::const_iterator iter = container.begin(); iter != container.end(); ++iter ) + for(const auto& element : container) { - keys.push_back( (*iter).key ); + keys.push_back(element.key); } } -- 2.7.4