[PATCH 1/2] lib/bsearch.c: introduce bsearch_idx

* [PATCH 1/2] lib/bsearch.c: introduce bsearch_idx
@ 2019-10-19  7:20 Thomas Meyer
  2019-10-19  7:20 ` [PATCH 2/2] xfs: replace homemade binary search Thomas Meyer
  0 siblings, 1 reply; 3+ messages in thread
From: Thomas Meyer @ 2019-10-19  7:20 UTC (permalink / raw)
  To: linux-kernel, linux-xfs; +Cc: Thomas Meyer

many existing bsearch implementations don't want to have the pointer to the
found element, but the index position, or if the searched element doesn't
exist, the index position the search element would be placed in the array.

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
 include/linux/bsearch.h |  7 +++++
 lib/bsearch.c           | 62 +++++++++++++++++++++++++++++++++--------
 2 files changed, 58 insertions(+), 11 deletions(-)

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
index 62b1eb3488584..0c40c8b39b881 100644
--- a/include/linux/bsearch.h
+++ b/include/linux/bsearch.h
@@ -7,4 +7,11 @@
 void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	      int (*cmp)(const void *key, const void *elt));
 
+struct bsearch_result { size_t idx; bool found; };
+
+struct bsearch_result bsearch_idx(const void *key, const void *base,
+		      size_t num,
+		      size_t size,
+		      int (*cmp)(const void *key, const void *elt));
+
 #endif /* _LINUX_BSEARCH_H */
diff --git a/lib/bsearch.c b/lib/bsearch.c
index 8baa839681628..5c46d0ec1e473 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -10,8 +10,8 @@
 #include <linux/bsearch.h>
 #include <linux/kprobes.h>
 
-/*
- * bsearch - binary search an array of elements
+/**
+ * bsearch() - binary search an array of elements
  * @key: pointer to item being searched for
  * @base: pointer to first element to search
  * @num: number of elements
@@ -27,28 +27,68 @@
  * could compare the string with the struct's name field.  However, if
  * the key and elements in the array are of the same type, you can use
  * the same comparison function for both sort() and bsearch().
+ *
+ * Return: Either a pointer to the search element or NULL if not found.
  */
 void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	      int (*cmp)(const void *key, const void *elt))
 {
-	const char *pivot;
+	struct bsearch_result idx = bsearch_idx(key, base, num, size, cmp);
+
+	if (idx.found == true)
+		return (void *)base + idx.idx * size;
+
+	return NULL;
+}
+EXPORT_SYMBOL(bsearch);
+NOKPROBE_SYMBOL(bsearch);
+
+/**
+ * bsearch_idx() - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Returns an index position and a bool if an exact match was found
+ * if an exact match was found the idx is the index in the base array.
+ * if no exact match was found the idx will point the the next higher index
+ * entry in the base array. this can also be base[num], i.e. after the actual
+ * allocated array.
+ */
+struct bsearch_result bsearch_idx(const void *key, const void *base,
+				  size_t num,
+				  size_t size,
+				  int (*cmp)(const void *key, const void *elt))
+{
+	struct bsearch_result res = { .found = false };
 	int result;
+	size_t base_idx = 0;
+	size_t pivot_idx;
 
 	while (num > 0) {
-		pivot = base + (num >> 1) * size;
-		result = cmp(key, pivot);
+		pivot_idx = base_idx + (num >> 1);
+		result = cmp(key, base + pivot_idx * size);
 
-		if (result == 0)
-			return (void *)pivot;
+		if (result == 0) {
+			res.idx = pivot_idx;
+			res.found = true;
+			return res;
+		}
 
 		if (result > 0) {
-			base = pivot + size;
+			base_idx = pivot_idx + 1;
 			num--;
 		}
 		num >>= 1;
 	}
 
-	return NULL;
+	res.idx = base_idx;
+	return res;
 }
-EXPORT_SYMBOL(bsearch);
-NOKPROBE_SYMBOL(bsearch);
+EXPORT_SYMBOL(bsearch_idx);
-- 
2.21.0


^ permalink raw reply related	[flat|nested] 3+ messages in thread