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

[Laurent Pinchart]

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.

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;
> >   	}
> >   };

-- 
Regards,

Laurent Pinchart