[libcamera-devel] [PATCH] libcamera: utils: Add map_keys() function

[Umang Jain]

Hi Laurent,

On 6/25/20 7:58 PM, Laurent Pinchart wrote:
> Hi Umang,
>
> On Thu, Jun 25, 2020 at 08:12:12AM +0000, Umang Jain wrote:
>> On 6/25/20 6:53 AM, Laurent Pinchart wrote:
>>> Add a map_keys() function to the utils namespace to extract keys from a
>>> map.
>>>
>>> Signed-off-by: Laurent Pinchart <laurent.pinchart at ideasonboard.com>
>>> ---
>>>    include/libcamera/internal/utils.h | 10 ++++++++++
>>>    src/libcamera/utils.cpp            |  7 +++++++
>>>    test/utils.cpp                     | 21 +++++++++++++++++++++
>>>    3 files changed, 38 insertions(+)
>>>
>>> diff --git a/include/libcamera/internal/utils.h b/include/libcamera/internal/utils.h
>>> index 0953423ee8d0..4fe4843922a9 100644
>>> --- a/include/libcamera/internal/utils.h
>>> +++ b/include/libcamera/internal/utils.h
>>> @@ -11,6 +11,7 @@
>>>    #include <chrono>
>>>    #include <memory>
>>>    #include <ostream>
>>> +#include <set>
>>>    #include <sstream>
>>>    #include <string>
>>>    #include <string.h>
>>> @@ -36,6 +37,15 @@ const char *basename(const char *path);
>>>    char *secure_getenv(const char *name);
>>>    std::string dirname(const std::string &path);
>>>    
>>> +template<typename T>
>>> +std::set<typename T::key_type> map_keys(const T &map)
>>> +{
>>> +	std::set<typename T::key_type> keys;
>>> +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
>> I am not able to wrap my head around keys.end() as the beginning
>> position for the insertor? keys.end() points to `past-the-end`element
>> which should not be de-referenced, as claimed in the online docs. Can
>> you explain why we cannot use:
>>
>> std::inserter(keys, keys.begin()) ?
> std::inserter() is a helper that return a std::insert_iterator. An
> std::insert_iterator is an iterator that invokes the insert() function of
> the container it is related to in its operator=(). Calling
>
> 	iter = value;
>
> on an std::insert_iterator results in
>
> 	iter = container->insert(iter, value);
> 	++iter;
>
> while calling operator++() directly on the iterator is a no-op.
>
> The insert() function of STL containers takes an iterator as a parameter
> to specify the insertion position. The insertion happens just prior to
> iterator. For std::list and std::vector that's guaranteed, while for
> std::map and std::set that's just a hint: maps and sets are sorted by
> key, so the insertion position depends on the key. Still, passing the
> correct hint to insert() for map and set can help with performances.
Ah Ok. The insertion happening 'just prior to iterator' was the key point
I was missing here. Plus got clear from your explanation about the 
performance
bit of what's happening. Thanks!
>
> Using keys.end() will thus result in the new element being inserted just
> before the end of the container. As they map is sorted by key, the
> std::transform call will insert the keys in the set in increasing order.
> end() is thus the correct hint in that case. begin() would work too, but
> would result in worse performances, as the insert() function would
> realize that the hint is not correct, and will look up the correct
> position. See https://en.cppreference.com/w/cpp/container/map/insert
> that states
>
> Complexity
>
> [...]
>
> 4-6) Amortized constant if the insertion happens in the position just
> before the hint, logarithmic in the size of the container otherwise.
>
>>> +		       [](const auto &value) { return value.first; });
>>> +	return keys;
>>> +}
>>> +
>>>    template<class InputIt1, class InputIt2>
>>>    unsigned int set_overlap(InputIt1 first1, InputIt1 last1,
>>>    			 InputIt2 first2, InputIt2 last2)
>>> diff --git a/src/libcamera/utils.cpp b/src/libcamera/utils.cpp
>>> index d55338fe681a..1eb8970a5bbc 100644
>>> --- a/src/libcamera/utils.cpp
>>> +++ b/src/libcamera/utils.cpp
>>> @@ -127,6 +127,13 @@ std::string dirname(const std::string &path)
>>>    	return path.substr(0, pos + 1);
>>>    }
>>>    
>>> +/**
>>> + * \fn std::set<typename T::key_type> map_keys(const T &map)
>>> + * \brief Retrieve the keys of a std::map<>
>>> + * \param[in] map The map whose keys to retrieve
>>> + * \return A std::set<> containing the keys of \a map
>>> + */
>>> +
>>>    /**
>>>     * \fn libcamera::utils::set_overlap(InputIt1 first1, InputIt1 last1,
>>>     *				     InputIt2 first2, InputIt2 last2)
>>> diff --git a/test/utils.cpp b/test/utils.cpp
>>> index 66b91f1203e1..a9d072030f1c 100644
>>> --- a/test/utils.cpp
>>> +++ b/test/utils.cpp
>>> @@ -6,6 +6,8 @@
>>>     */
>>>    
>>>    #include <iostream>
>>> +#include <map>
>>> +#include <set>
>>>    #include <sstream>
>>>    #include <string>
>>>    #include <vector>
>>> @@ -144,6 +146,25 @@ protected:
>>>    		if (TestPass != testDirname())
>>>    			return TestFail;
>>>    
>>> +
>>> +		/* utils::map_keys() test. */
>>> +		const std::map<std::string, unsigned int> map{
>>> +			{ "zero", 0 },
>>> +			{ "one", 1 },
>>> +			{ "two", 2 },
>>> +		};
>>> +		const std::set<std::string> expectedKeys{
>>> +			"zero",
>>> +			"one",
>>> +			"two",
>>> +		};
>>> +
>>> +		const std::set<std::string> keys = utils::map_keys(map);
>>> +		if (keys != expectedKeys) {
>>> +			cerr << "utils::map_keys() test failed" << endl;
>>> +			return TestFail;
>>> +		}
>>> +
>>>    		return TestPass;
>>>    	}
>>>    };