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

[Laurent Pinchart]

Hi Jacopo,

On Thu, Jun 25, 2020 at 09:47:21AM +0200, Jacopo Mondi wrote:
> Hi Laurent,
>    I still wonder why we don't have this in STL...

If you ever find an answer, I'll be interested to know :-)

> On Thu, Jun 25, 2020 at 04:23:35AM +0300, 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)
> 
> Keys are unique and sorted in maps, can't we return a vector ? Is this
> meant to support multimaps too ? If that's not desired, can we use
> std::map<class Key, T> as the template parameter ?
> 
> (To be honest, calling this on a multimap opens one question: do we
> want the -unique- keys, or all the keys ? The number of keys, if
> unique, would be less than the number of actual entries in the map...
> This makes me feel we want this for maps only)

I'd rather make this specific to std::map for now. Returning a vector
would make sense, and I think that's what I'd prefer. Maybe this is why
STL doesn't have a std::map::keys() method, they couldn't decide what
container it should return ;-)

> > +{
> > +	std::set<typename T::key_type> keys;
> > +	std::transform(map.begin(), map.end(), std::inserter(keys, keys.end()),
> > +		       [](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",
> > +		};
> 
> How are keys sorted here ?

std::map<> and std::set<> are sorted automatically. I think the test
should actually use a different order in the initializer list of
expectedKeys, just to show it gets sorted.

> > +
> > +		const std::set<std::string> keys = utils::map_keys(map);
> > +		if (keys != expectedKeys) {
> 
> This matches the sorting order of expectedKeys by chance ? I see
> std::set::operator== assuming lhs and rhs to be sorted equally
> 
> > +			cerr << "utils::map_keys() test failed" << endl;
> > +			return TestFail;
> > +		}
> > +
> >  		return TestPass;
> >  	}
> >  };

-- 
Regards,

Laurent Pinchart