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

Thomas Meyer
2019-10-19T07:43:22Z

use newly introduced bsearch_idx instead.

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
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