Skip to contentSkip to conversation

lib/bsearch.c: introduce bsearch_idx

PATCH In review Thomas Meyer 2 participants 3 messages Oct 19, 2019

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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.

---
 include/linux/bsearch.h |  7 +++++
 lib/bsearch.c           | 62 +++++++++++++++++++++++++++++++++--------
 2 files changed, 58 insertions(+), 11 deletions(-)
include/linux/bsearch.h +7 -0
index 62b1eb3488584..0c40c8b39b881 100644
@@ -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 */
lib/bsearch.c +51 -11

87 lines not on this page · raw message

Signature · 1 line
2.21.0
#1 lore raw

PATCH 2/2 xfs: replace homemade binary search

use newly introduced bsearch_idx instead.

---
 fs/xfs/libxfs/xfs_dir2_block.c | 30 ++++++++++++++++++------------
 1 file changed, 18 insertions(+), 12 deletions(-)
fs/xfs/libxfs/xfs_dir2_block.c +18 -12
index 9595ced393dce..e484ec68944fb 100644
@@ -20,6 +20,7 @@
 #include "xfs_error.h"
 #include "xfs_trace.h"
 #include "xfs_log.h"
+#include <linux/bsearch.h>
 
 /*
  * Local function prototypes.
@@ -314,6 +315,19 @@ xfs_dir2_block_compact(
 		xfs_dir2_data_freescan(args->dp, hdr, needlog);
 }
 
+static int cmp_hashval(const void *key, const void *elt)
+{
+	xfs_dahash_t _search_key = *(xfs_dahash_t *)key;
+	xfs_dahash_t _curren_key = be32_to_cpu((
+				(xfs_dir2_leaf_entry_t *) elt)->hashval);
+
+	if (_search_key == _curren_key)
+		return 0;
+	else if (_search_key < _curren_key)
+		return -1;
+	return 1;
+}
+
 /*
  * Add an entry to a block directory.
  */
@@ -331,19 +345,17 @@ xfs_dir2_block_addname(
 	xfs_dir2_data_unused_t	*dup;		/* block unused entry */
 	int			error;		/* error return value */
 	xfs_dir2_data_unused_t	*enddup=NULL;	/* unused at end of data */
-	xfs_dahash_t		hash;		/* hash value of found entry */
-	int			high;		/* high index for binary srch */
 	int			highstale;	/* high stale index */
 	int			lfloghigh=0;	/* last final leaf to log */
 	int			lfloglow=0;	/* first final leaf to log */
 	int			len;		/* length of the new entry */
-	int			low;		/* low index for binary srch */
 	int			lowstale;	/* low stale index */
 	int			mid=0;		/* midpoint for binary srch */
 	int			needlog;	/* need to log header */
 	int			needscan;	/* need to rescan freespace */
 	__be16			*tagp;		/* pointer to tag value */
 	xfs_trans_t		*tp;		/* transaction structure */
+	struct bsearch_result	idx;		/* bsearch result */
 
 	trace_xfs_dir2_block_addname(args);
 
@@ -420,15 +432,9 @@ xfs_dir2_block_addname(
 	/*
 	 * Find the slot that's first lower than our hash value, -1 if none.
 	 */
-	for (low = 0, high = be32_to_cpu(btp->count) - 1; low <= high; ) {
-		mid = (low + high) >> 1;
-		if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)
-			break;
-		if (hash < args->hashval)
-			low = mid + 1;
-		else
-			high = mid - 1;
-	}
+	idx = bsearch_idx(&args->hashval, blp, be32_to_cpu(btp->count) - 1,
+			  sizeof(xfs_dir2_leaf_entry_t), cmp_hashval);
+	mid = idx.idx;
 	while (mid >= 0 && be32_to_cpu(blp[mid].hashval) >= args->hashval) {
 		mid--;
 	}
Signature · 1 line
2.21.0
#2 lore raw

Re: [PATCH 2/2] xfs: replace homemade binary search

Quoted 3 lines · Thomas Meyer

use newly introduced bsearch_idx instead.

What is the point? This adds more code, and makes it slower by adding an indirect function call.