lib/bsearch.c: introduce bsearch_idx
Subsystems (2)
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 <[email protected]>
--- include/linux/bsearch.h | 7 +++++ lib/bsearch.c | 62 +++++++++++++++++++++++++++++++++-------- 2 files changed, 58 insertions(+), 11 deletions(-)
include/linux/bsearch.h +7 -0
@@ -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
PATCH 2/2 xfs: replace homemade binary search
use newly introduced bsearch_idx instead.
Signed-off-by Thomas Meyer <[email protected]>
--- fs/xfs/libxfs/xfs_dir2_block.c | 30 ++++++++++++++++++------------ 1 file changed, 18 insertions(+), 12 deletions(-)
fs/xfs/libxfs/xfs_dir2_block.c +18 -12
@@ -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
Re: [PATCH 2/2] xfs: replace homemade binary search
Quoted 3 lines · Thomas Meyer
use newly introduced
bsearch_idxinstead.Signed-off-by Thomas Meyer <[email protected]>
What is the point? This adds more code, and makes it slower by adding an indirect function call.