[igt-dev] [PATCH i-g-t] lib: Use a bsearch to find the module name

[Jani Nikula]

On Mon, 03 Sep 2018, Chris Wilson <chris at chris-wilson.co.uk> wrote:
> Quoting Petri Latvala (2018-09-03 10:39:31)
>> On Sat, Sep 01, 2018 at 07:09:11PM +0100, Chris Wilson wrote:
>> > Even with a small number of known drivers (6), a bsearch will take at
>> > most 3 steps, whereas the linear search will take 3 steps on average. In
>> > the future with more known drivers, the logN bsearch will be even more
>> > advantageous.
>> > 
>> > Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
>> > Cc: Katarzyna Dec <katarzyna.dec at intel.com>
>> > ---
>> >  lib/drmtest.c | 12 +++++++++---
>> >  1 file changed, 9 insertions(+), 3 deletions(-)
>> > 
>> > diff --git a/lib/drmtest.c b/lib/drmtest.c
>> > index 93228f900..bfb38f1e9 100644
>> > --- a/lib/drmtest.c
>> > +++ b/lib/drmtest.c
>> > @@ -222,9 +222,15 @@ static int open_device(const char *name, unsigned int chipset)
>> >       if (__get_drm_device_name(fd, dev_name, sizeof(dev_name) - 1) == -1)
>> >               goto err;
>> >  
>> > -     for (const struct module *m = modules; m->module; m++) {
>> > -             if (strcmp(m->module, dev_name) == 0) {
>> > -                     chip = m->bit;
>> > +     for (int start = 0, end = ARRAY_SIZE(modules) - 1; start < end; ){
>> > +             int mid = start + (end - start) / 2;
>> > +             int ret = strcmp(modules[mid].module, dev_name);
>> > +             if (ret < 0) {
>> > +                     end = mid;
>> > +             } else if (ret > 0) {
>> > +                     start = mid + 1;
>> 
>> 
>> Isn't this the wrong way around?
>
> * blinks.
>
> Yes. Shame on me for assuming that a run through igt was good enough to
> flush out the kinks. It just happens that vgem occupies the initial mid,
> so anything that wanted vgem-only got it; everything else hit the
> DRIVER_ANY.
>
> amdgpu -> skip. Ah. Hmm, that should have been flagged :|

Just sayin'


diff --git a/lib/drmtest.c b/lib/drmtest.c
index adff1a81fffb..3a050211146e 100644
--- a/lib/drmtest.c
+++ b/lib/drmtest.c
@@ -209,11 +209,19 @@ static const struct module {
 	{}
 };
 
+static int module_compare(const void *_m1, const void *_m2)
+{
+	const struct module *m1 = _m1, *m2 = _m2;
+
+	return strcmp(m1->module, m2->module);
+}
+
 static int open_device(const char *name, unsigned int chipset)
 {
 	char dev_name[16] = "";
 	int chip = DRIVER_ANY;
 	int fd;
+	struct module key, *res;
 
 	fd = open(name, O_RDWR);
 	if (fd == -1)
@@ -222,18 +230,11 @@ static int open_device(const char *name, unsigned int chipset)
 	if (__get_drm_device_name(fd, dev_name, sizeof(dev_name) - 1) == -1)
 		goto err;
 
-	for (int start = 0, end = ARRAY_SIZE(modules) - 1; start < end; ){
-		int mid = start + (end - start) / 2;
-		int ret = strcmp(modules[mid].module, dev_name);
-		if (ret < 0) {
-			start = mid + 1;
-		} else if (ret > 0) {
-			end = mid;
-		} else {
-			chip = modules[mid].bit;
-			break;
-		}
-	}
+	key.module = dev_name;
+	res = bsearch(&key, modules, ARRAY_SIZE(modules) - 1,
+		      sizeof(modules[0]), module_compare);
+	if (res)
+		chip = res->bit;
 	if (chipset & chip)
 		return fd;
 

-- 
Jani Nikula, Intel Open Source Graphics Center