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

[Hirokazu Honda]

On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart
<laurent.pinchart at ideasonboard.com> wrote:
>
> 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.
>

I forgot mentioning there is no guaranteed upon traversing std::unordered_map.
https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c

So I think as long as std::unordered_map is used, the original
implementation is problematic?
-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