From 1cecd3a53107f7f670cf011201c1da3a33b795b6 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sat, 24 Jan 2015 18:43:37 +0100 Subject: cmListCommand: Use std::find algorithm for FIND subcommand. Use a ostringstream to account for the input being a variable of type size_t as a result of using std::distance. There is no single format string which portably accepts a size_t. --- Source/cmListCommand.cxx | 18 +++++++----------- 1 file changed, 7 insertions(+), 11 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index dd0cfa9..ae13fdf 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -284,18 +284,14 @@ bool cmListCommand::HandleFindCommand(std::vector const& args) return true; } - std::vector::iterator it; - unsigned int index = 0; - for ( it = varArgsExpanded.begin(); it != varArgsExpanded.end(); ++ it ) + std::vector::iterator it = + std::find(varArgsExpanded.begin(), varArgsExpanded.end(), args[2]); + if (it != varArgsExpanded.end()) { - if ( *it == args[2] ) - { - char indexString[32]; - sprintf(indexString, "%d", index); - this->Makefile->AddDefinition(variableName, indexString); - return true; - } - index++; + std::ostringstream indexStream; + indexStream << std::distance(varArgsExpanded.begin(), it); + this->Makefile->AddDefinition(variableName, indexStream.str().c_str()); + return true; } this->Makefile->AddDefinition(variableName, "-1"); -- cgit v0.12 From 67a26764b536992a966cacab4811c2d30624405c Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 18:02:56 +0100 Subject: cmListCommand: Implement REVERSE subcommand with std::reverse. --- Source/cmListCommand.cxx | 11 ++--------- 1 file changed, 2 insertions(+), 9 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index ae13fdf..22d8b0e 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -410,15 +410,8 @@ bool cmListCommand return false; } - std::string value; - std::vector::reverse_iterator it; - const char* sep = ""; - for ( it = varArgsExpanded.rbegin(); it != varArgsExpanded.rend(); ++ it ) - { - value += sep; - value += it->c_str(); - sep = ";"; - } + std::reverse(varArgsExpanded.begin(), varArgsExpanded.end()); + std::string value = cmJoin(varArgsExpanded, ";"); this->Makefile->AddDefinition(listName, value.c_str()); return true; -- cgit v0.12 From 069f2440c471e89dfe2ecf6778bbab16e9fbe491 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Thu, 12 Feb 2015 20:07:20 +0100 Subject: cmListCommand: Convert loop to find algorithm. --- Source/cmListCommand.cxx | 13 +------------ 1 file changed, 1 insertion(+), 12 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index 22d8b0e..826632f 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -104,19 +104,8 @@ bool cmListCommand::GetList(std::vector& list, } // expand the variable into a list cmSystemTools::ExpandListArgument(listString, list, true); - // check the list for empty values - bool hasEmpty = false; - for(std::vector::iterator i = list.begin(); - i != list.end(); ++i) - { - if(i->empty()) - { - hasEmpty = true; - break; - } - } // if no empty elements then just return - if(!hasEmpty) + if (std::find(list.begin(), list.end(), std::string()) == list.end()) { return true; } -- cgit v0.12 From 0b5cf0dabd430dfe1289e865b1b51c41066338a7 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Thu, 12 Feb 2015 18:47:10 +0100 Subject: cmAlgorithms: Implement algorithm for removing indexes. Implement ContainerAlgorithms::RemoveN to remove N elements to the end of a container by rotating. The rotate is implemented in terms of the efficient swap algorithm, optimized even more in the standard library implementation when the compiler supports the rvalue-references feature to move elements. Implement cmRemoveN with a Range API for completeness. std::rotate in C++11 is specified to return an iterator, but c++98 specifies it to return void. libstdc++ 5.0 will be the first version to have the correct return type. Implement ContainerAlgorithms::Rotate in terms of std::rotate and return the correct iterator from it. While std::rotate requires forward iterators, this workaround means cmRotate requires bidirectional iterators. As most of CMake uses random access iterators anyway, this should not be a problem. Implement cmRemoveIndices in terms of the RemoveN algorithm, such that each element which is not removed is rotated only once. This can not use the cmRemoveN range-API algorithm because that would require creating a new range, but the range must be taken by reference and so it can't be a temporary. These remove algorithms are not part of the STL and I couldn't find them anywhere else either. --- Source/cmAlgorithms.h | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index ad2b9c1..70fdff6 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -138,6 +138,22 @@ private: const_iterator End; }; +template +BiDirIt Rotate(BiDirIt first, BiDirIt middle, BiDirIt last) +{ + typename std::iterator_traits::difference_type dist = + std::distance(first, middle); + std::rotate(first, middle, last); + std::advance(last, -dist); + return last; +} + +template +Iter RemoveN(Iter i1, Iter i2, size_t n) +{ + return ContainerAlgorithms::Rotate(i1, i1 + n, i2); +} + } template @@ -188,4 +204,26 @@ std::string cmJoin(Range const& r, std::string delimiter) return cmJoin(r, delimiter.c_str()); }; +template +typename Range::const_iterator cmRemoveN(Range& r, size_t n) +{ + return ContainerAlgorithms::RemoveN(r.begin(), r.end(), n); +} + +template +typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) +{ + typename InputRange::const_iterator remIt = rem.begin(); + + typename Range::iterator writer = r.begin() + *remIt; + ++remIt; + size_t count = 1; + for ( ; writer != r.end() && remIt != rem.end(); ++count, ++remIt) + { + writer = ContainerAlgorithms::RemoveN(writer, r.begin() + *remIt, count); + } + writer = ContainerAlgorithms::RemoveN(writer, r.end(), count); + return writer; +} + #endif -- cgit v0.12 From 6a22e40147b7df5285a67b63249562ecbeff112e Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 15:23:43 +0100 Subject: cmListCommand: Use cmRemoveIndices for REMOVE_AT subcommand. Avoid repeatedly looping over the indices to process elements (even without breaking out of the loop when the element is found). --- Source/cmListCommand.cxx | 25 +++++++++---------------- 1 file changed, 9 insertions(+), 16 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index 826632f..93c6d66 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -527,26 +527,19 @@ bool cmListCommand::HandleRemoveAtCommand( removed.push_back(static_cast(item)); } + std::sort(removed.begin(), removed.end()); + removed.erase(std::unique(removed.begin(), removed.end()), removed.end()); + + varArgsExpanded.erase(cmRemoveIndices(varArgsExpanded, removed), + varArgsExpanded.end()); + std::string value; const char* sep = ""; for ( cc = 0; cc < varArgsExpanded.size(); ++ cc ) { - size_t kk; - bool found = false; - for ( kk = 0; kk < removed.size(); ++ kk ) - { - if ( cc == removed[kk] ) - { - found = true; - } - } - - if ( !found ) - { - value += sep; - value += varArgsExpanded[cc]; - sep = ";"; - } + value += sep; + value += varArgsExpanded[cc]; + sep = ";"; } this->Makefile->AddDefinition(listName, value.c_str()); -- cgit v0.12 From a77af8f1301b6a9964c187ffff7a1893a80fbe90 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 15:46:30 +0100 Subject: cmListCommand: Replace joining loop with cmJoin algorithm. --- Source/cmListCommand.cxx | 10 ++-------- 1 file changed, 2 insertions(+), 8 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index 93c6d66..592681b 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -533,14 +533,8 @@ bool cmListCommand::HandleRemoveAtCommand( varArgsExpanded.erase(cmRemoveIndices(varArgsExpanded, removed), varArgsExpanded.end()); - std::string value; - const char* sep = ""; - for ( cc = 0; cc < varArgsExpanded.size(); ++ cc ) - { - value += sep; - value += varArgsExpanded[cc]; - sep = ";"; - } + std::string value = cmJoin(varArgsExpanded, ";"); + this->Makefile->AddDefinition(listName, value.c_str()); return true; -- cgit v0.12 From 050958a3286f69c577fe5d03407800cbe0367898 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 18:58:36 +0100 Subject: cmAlgorithms: Add cmRemoveMatching algorithm. Implement it in terms of std::remove_if with a binary search through a matching range. --- Source/cmAlgorithms.h | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 70fdff6..0f162a2 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -154,6 +154,23 @@ Iter RemoveN(Iter i1, Iter i2, size_t n) return ContainerAlgorithms::Rotate(i1, i1 + n, i2); } +template +struct BinarySearcher +{ + typedef typename Range::value_type argument_type; + BinarySearcher(Range const& r) + : m_range(r) + { + } + + bool operator()(argument_type const& item) + { + return std::binary_search(m_range.begin(), m_range.end(), item); + } +private: + Range const& m_range; +}; + } template @@ -226,4 +243,11 @@ typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) return writer; } +template +typename Range::const_iterator cmRemoveMatching(Range &r, MatchRange const& m) +{ + return std::remove_if(r.begin(), r.end(), + ContainerAlgorithms::BinarySearcher(m)); +} + #endif -- cgit v0.12 From 3cfe7a4ca876c496f9b491e4175fd1c9be24f3d7 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 16:00:54 +0100 Subject: cmListCommand: Implement REMOVE_ITEM in terms of cmRemoveMatching. --- Source/cmListCommand.cxx | 22 ++++++---------------- 1 file changed, 6 insertions(+), 16 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index 592681b..50adce6 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -355,23 +355,13 @@ bool cmListCommand return false; } - size_t cc; - for ( cc = 2; cc < args.size(); ++ cc ) - { - size_t kk = 0; - while ( kk < varArgsExpanded.size() ) - { - if ( varArgsExpanded[kk] == args[cc] ) - { - varArgsExpanded.erase(varArgsExpanded.begin()+kk); - } - else - { - kk ++; - } - } - } + std::vector remove(args.begin() + 2, args.end()); + std::sort(remove.begin(), remove.end()); + remove.erase(std::unique(remove.begin(), remove.end()), remove.end()); + varArgsExpanded.erase( + cmRemoveMatching(varArgsExpanded, remove), + varArgsExpanded.end()); std::string value = cmJoin(varArgsExpanded, ";"); this->Makefile->AddDefinition(listName, value.c_str()); -- cgit v0.12 From cebeed248606ba92597b7e32a5b0be1f474f7a91 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 19:08:12 +0100 Subject: cmAlgorithms: Add cmRemoveDuplicates algorithm. Start by creating a vector to hold a unique values of the input range. We expect that in most cases, there will be relatively few duplicates, so reserving enough memory for a complete copy is worthwhile. Unlike a solution involving a std::set, this algorithm allocates all the memory it needs in one go and in one place, so it is more cache friendly. Populate the unique copy with a lower_bound insert algorithm and record the indices of duplicates. This is the same complexity as the std::set insert algorithm, but without the need to allocate memory on the heap and other disadvantages of std::set. Remove the duplicates with the cmRemoveIndices algorithm. --- Source/cmAlgorithms.h | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 0f162a2..a996088 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -250,4 +250,33 @@ typename Range::const_iterator cmRemoveMatching(Range &r, MatchRange const& m) ContainerAlgorithms::BinarySearcher(m)); } +template +typename Range::const_iterator cmRemoveDuplicates(Range& r) +{ + std::vector unique; + unique.reserve(r.size()); + std::vector indices; + size_t count = 0; + for(typename Range::const_iterator it = r.begin(); + it != r.end(); ++it, ++count) + { + typename Range::iterator low = + std::lower_bound(unique.begin(), unique.end(), *it); + if (low == unique.end() || *low != *it) + { + unique.insert(low, *it); + } + else + { + indices.push_back(count); + } + } + if (indices.empty()) + { + return r.end(); + } + std::sort(indices.begin(), indices.end()); + return cmRemoveIndices(r, indices); +} + #endif -- cgit v0.12 From 1c7c35c3723abfb91f5e9a986ccd4f7e70683baf Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 16:22:08 +0100 Subject: cmListCommand: Replace remove duplicates loop with algorithm. --- Source/cmListCommand.cxx | 21 +++------------------ 1 file changed, 3 insertions(+), 18 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index 50adce6..e2ebe0a 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -418,24 +418,9 @@ bool cmListCommand return false; } - std::string value; - - - std::set unique; - std::vector::iterator it; - const char* sep = ""; - for ( it = varArgsExpanded.begin(); it != varArgsExpanded.end(); ++ it ) - { - if (unique.find(*it) != unique.end()) - { - continue; - } - unique.insert(*it); - value += sep; - value += it->c_str(); - sep = ";"; - } - + varArgsExpanded.erase(cmRemoveDuplicates(varArgsExpanded), + varArgsExpanded.end()); + std::string value = cmJoin(varArgsExpanded, ";"); this->Makefile->AddDefinition(listName, value.c_str()); return true; -- cgit v0.12 From 116459d34fab6327906e901753611636f84a16c1 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 15:48:51 +0100 Subject: cmListCommand: Avoid needlessly erasing from vectors. The entire vector will be destroyed at once at the end of the scope, and the remove algorithms already give us the end of the range of interesting values, so just use those sentinals. --- Source/cmListCommand.cxx | 38 +++++++++++++++++++++----------------- 1 file changed, 21 insertions(+), 17 deletions(-) diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx index e2ebe0a..98dcef1 100644 --- a/Source/cmListCommand.cxx +++ b/Source/cmListCommand.cxx @@ -357,13 +357,14 @@ bool cmListCommand std::vector remove(args.begin() + 2, args.end()); std::sort(remove.begin(), remove.end()); - remove.erase(std::unique(remove.begin(), remove.end()), remove.end()); - - varArgsExpanded.erase( - cmRemoveMatching(varArgsExpanded, remove), - varArgsExpanded.end()); - - std::string value = cmJoin(varArgsExpanded, ";"); + std::vector::const_iterator remEnd = + std::unique(remove.begin(), remove.end()); + std::vector::const_iterator remBegin = remove.begin(); + + std::vector::const_iterator argsEnd = + cmRemoveMatching(varArgsExpanded, cmRange(remBegin, remEnd)); + std::vector::const_iterator argsBegin = varArgsExpanded.begin(); + std::string value = cmJoin(cmRange(argsBegin, argsEnd), ";"); this->Makefile->AddDefinition(listName, value.c_str()); return true; } @@ -418,9 +419,11 @@ bool cmListCommand return false; } - varArgsExpanded.erase(cmRemoveDuplicates(varArgsExpanded), - varArgsExpanded.end()); - std::string value = cmJoin(varArgsExpanded, ";"); + std::vector::const_iterator argsEnd = + cmRemoveDuplicates(varArgsExpanded); + std::vector::const_iterator argsBegin = + varArgsExpanded.begin(); + std::string value = cmJoin(cmRange(argsBegin, argsEnd), ";"); this->Makefile->AddDefinition(listName, value.c_str()); return true; @@ -503,13 +506,14 @@ bool cmListCommand::HandleRemoveAtCommand( } std::sort(removed.begin(), removed.end()); - removed.erase(std::unique(removed.begin(), removed.end()), removed.end()); - - varArgsExpanded.erase(cmRemoveIndices(varArgsExpanded, removed), - varArgsExpanded.end()); - - std::string value = cmJoin(varArgsExpanded, ";"); - + std::vector::const_iterator remEnd = + std::unique(removed.begin(), removed.end()); + std::vector::const_iterator remBegin = removed.begin(); + + std::vector::const_iterator argsEnd = + cmRemoveIndices(varArgsExpanded, cmRange(remBegin, remEnd)); + std::vector::const_iterator argsBegin = varArgsExpanded.begin(); + std::string value = cmJoin(cmRange(argsBegin, argsEnd), ";"); this->Makefile->AddDefinition(listName, value.c_str()); return true; -- cgit v0.12