diff mbox

lib: Typesafe generator macro for bsearch

Message ID 20160929204156.31824-1-chris@chris-wilson.co.uk (mailing list archive)
State New, archived
Headers show

Commit Message

Chris Wilson Sept. 29, 2016, 8:41 p.m. UTC 
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@chris-wilson.co.uk>
Cc: Rusty Russell <rusty@rustcorp.com.au>
Cc: Alessio Igor Bogani <abogani@kernel.org>
---
 include/linux/bsearch.h | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)
diff mbox

Patch

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 */