[Intel-gfx] [PATCH] lib: Typesafe generator macro for bsearch

Chris Wilson chris at chris-wilson.co.uk
Thu Sep 29 20:41:56 UTC 2016


Sometimes a callout to a generic bsearch() library function is
substantial overhead for a small search utility. For these situations,
macro generate a type-specific bsearch routine.

Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
Cc: Rusty Russell <rusty at rustcorp.com.au>
Cc: Alessio Igor Bogani <abogani at kernel.org>
---
 include/linux/bsearch.h | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
index 90b1aa867224..b5669e945c10 100644
--- a/include/linux/bsearch.h
+++ b/include/linux/bsearch.h
@@ -6,4 +6,22 @@
 void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	      int (*cmp)(const void *key, const void *elt));
 
+#define BSEARCH(key, base, num, cmp) ({					\
+	unsigned long start__ = 0, end__ = (num);			\
+	typeof(base) result__ = NULL;					\
+	while (start__ < end__) {					\
+		unsigned long mid__ = (start__ + end__) / 2;		\
+		int ret__ = (cmp)((key), (base) + mid__);		\
+		if (ret__ < 0) {					\
+			end__ = mid__;					\
+		} else if (ret__ > 0) {					\
+			start__ = mid__ + 1;				\
+		} else {						\
+			result__ = (base) + mid__;			\
+			break;						\
+		}							\
+	}								\
+	result__;							\
+})
+
 #endif /* _LINUX_BSEARCH_H */
-- 
2.9.3



More information about the Intel-gfx mailing list