Re: [PATCH v4 08/19] media: rc: Use binary search for adding or updating a scancode

[Sean Young <sean@mess.org>]

On Fri, Sep 11, 2026 at 10:10:52AM +0200, Hans Verkuil wrote:
> On 08/09/2026 17:51, Sean Young wrote:
> > We can have up to 1024 scancodes entries which are always sorted, so make
> > this a little faster.
> > 
> > Signed-off-by: Sean Young <sean@mess.org>
> > ---
> >  drivers/media/rc/rc-main.c | 20 +++++++++++++-------
> >  1 file changed, 13 insertions(+), 7 deletions(-)
> > 
> > diff --git a/drivers/media/rc/rc-main.c b/drivers/media/rc/rc-main.c
> > index 924b13fff753..795ac0fe4858 100644
> > --- a/drivers/media/rc/rc-main.c
> > +++ b/drivers/media/rc/rc-main.c
> > @@ -391,7 +391,7 @@ static unsigned int ir_establish_scancode(struct rc_dev *dev,
> >  					  struct rc_map *rc_map,
> >  					  u64 scancode, bool resize)
> >  {
> > -	unsigned int i;
> > +	unsigned int i, lo, hi;
> >  
> >  	lockdep_assert_held(&rc_map->lock);
> >  
> > @@ -406,15 +406,21 @@ static unsigned int ir_establish_scancode(struct rc_dev *dev,
> >  	if (dev->scancode_mask)
> >  		scancode &= dev->scancode_mask;
> >  
> > -	/* First check if we already have a mapping for this ir command */
> > -	for (i = 0; i < rc_map->len; i++) {
> > +	/*
> > +	 * Binary search for an existing mapping for this ir command.
> > +	 */
> > +	lo = 0;
> > +	hi = rc_map->len;
> > +	while (lo < hi) {
> > +		i = lo + (hi - lo) / 2;
> >  		if (rc_map->scan[i].scancode == scancode)
> >  			return i;
> > -
> > -		/* Keytable is sorted from lowest to highest scancode */
> > -		if (rc_map->scan[i].scancode >= scancode)
> > -			break;
> > +		if (rc_map->scan[i].scancode < scancode)
> > +			lo = i + 1;
> > +		else
> > +			hi = i;
> >  	}
> > +	i = lo;
> 
> Can you use bsearch() for this? (lib/bsearch.c)

We want to insert an entry if it does not already exist. bsearch()
does not give us an index if there is no match.

Arguably this should be an extension of lib/bsearch.c but I'm not
clear what form that would take.

Thanks,

Sean