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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



use newly introduced bsearch_idx instead.

Signed-off-by: Thomas Meyer <thomas@xxxxxxxx>
---
 fs/xfs/libxfs/xfs_dir2_block.c | 30 ++++++++++++++++++------------
 1 file changed, 18 insertions(+), 12 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_dir2_block.c b/fs/xfs/libxfs/xfs_dir2_block.c
index 9595ced393dce..e484ec68944fb 100644
--- a/fs/xfs/libxfs/xfs_dir2_block.c
+++ b/fs/xfs/libxfs/xfs_dir2_block.c
@@ -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--;
 	}
-- 
2.21.0




[Index of Archives]     [XFS Filesystem Development (older mail)]     [Linux Filesystem Development]     [Linux Audio Users]     [Yosemite Trails]     [Linux Kernel]     [Linux RAID]     [Linux SCSI]


  Powered by Linux