[libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the controls order assumption in updateControls()

[Laurent Pinchart]

Hi Hiro,

On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:
> On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:
> > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:
> > > The original updateControls() has the assumption that ctrls and
> > > v4l2Ctrls lists in the same order. It is dependent on the caller
> > > implementation though. This changes updateControls()
> > > implementation so that it works without the assumption.
> > >
> > > Signed-off-by: Hirokazu Honda <hiroh at chromium.org>
> > > ---
> > >  src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------
> > >  1 file changed, 13 insertions(+), 13 deletions(-)
> > >
> > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp
> > > index d4a9bb75..8fd79934 100644
> > > --- a/src/libcamera/v4l2_device.cpp
> > > +++ b/src/libcamera/v4l2_device.cpp
> > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,
> > >                               const struct v4l2_ext_control *v4l2Ctrls,
> > >                               unsigned int count)
> > >  {
> > > -     unsigned int i = 0;
> > > -     for (auto &ctrl : *ctrls) {
> > > -             if (i == count)
> > > -                     break;
> > > -
> > > -             const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];
> > > -             unsigned int id = ctrl.first;
> > > -             ControlValue &value = ctrl.second;
> > > +     for (unsigned int i = 0; i < count; i++) {
> > > +             const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];
> > > +             const unsigned int id = v4l2Ctrl.id;
> > > +             if (!ctrls->contains(id)) {
> > > +                     LOG(V4L2, Error) << "ControlList doesn't contain id: "
> > > +                                      << id;
> > > +                     return;
> > > +             }
> > >
> > > -             const auto iter = controls_.find(id);
> > > -             switch (iter->first->type()) {
> > > +             ControlValue value = ctrls->get(id);
> >
> > This is less efficient, as the function now runs with O(n^2) complexity.
> 
> Can you explain me why the time complexity is O(n^2)?
> Since controls_ is based on std::unordered_map, find(), contains(),
> get() and set() should be O(1).
> So I think this is still O(n).

You're right that it's not O(n^2) as we use an unordered map.
std::unordered_map::find() is "constant on average, worst case linear in
the size of the container".

> > Given that updateControls() is private, why is requiring ctrls and
> > v4l2Ctrls to have the same order a problem ? The requirement should be
> > documented, but does it cause any issue ?
> 
> I think the restriction is strange and unnecessary, and a caller might
> have to pre-process to keep that.
> Well, so far, the caller is only V4L2Device and we don't need anything
> to keep the rule.

That was my point, it's a private function of the class :-) As all
callers currently guarantee the order, I'd defer this change until we
have a use case.

> > > +             switch (value.type()) {
> > >               case ControlTypeInteger64:
> > > -                     value.set<int64_t>(v4l2Ctrl->value64);
> > > +                     value.set<int64_t>(v4l2Ctrl.value64);
> > >                       break;
> > >
> > >               case ControlTypeByte:
> > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,
> > >                        * \todo To be changed when support for string controls
> > >                        * will be added.
> > >                        */
> > > -                     value.set<int32_t>(v4l2Ctrl->value);
> > > +                     value.set<int32_t>(v4l2Ctrl.value);
> > >                       break;
> > >               }
> > >
> > > -             i++;
> > > +             ctrls->set(id, value);
> > >       }
> > >  }
> > >

-- 
Regards,

Laurent Pinchart