linux-kernel - [PATCH 1/2] lib/bsearch.c: introduce bsearch

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20191019072033.17744-1-thomas@m3y3r.de>
Date:   Sat, 19 Oct 2019 09:20:32 +0200
From:   Thomas Meyer <thomas@...3r.de>
To:     linux-kernel@...r.kernel.org, linux-xfs@...r.kernel.org
Cc:     Thomas Meyer <thomas@...3r.de>
Subject: [PATCH 1/2] lib/bsearch.c: introduce bsearch_idx

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@...3r.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