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

[Hirokazu Honda]

Hi Laurent, Thanks for reviewing.


On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart
<laurent.pinchart at ideasonboard.com> wrote:
>
> Hi Hiro,
>
> Thank you for the patch.
>
> 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).

> 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.
-Hiro

>
> > +             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