[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [PATCH] xen/bsearch: Split out of lib.h into it's own header
There are currently two users, and lib.h is included everywhere. No functional change. Signed-off-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx> --- CC: Anthony PERARD <anthony.perard@xxxxxxxxxx> CC: Michal Orzel <michal.orzel@xxxxxxx> CC: Jan Beulich <jbeulich@xxxxxxxx> CC: Julien Grall <julien@xxxxxxx> CC: Roger Pau Monné <roger.pau@xxxxxxxxxx> CC: Stefano Stabellini <sstabellini@xxxxxxxxxx> CC: Volodymyr Babchuk <Volodymyr_Babchuk@xxxxxxxx> CC: Bertrand Marquis <bertrand.marquis@xxxxxxx> This will marginally improve compile times, but mostly it's about splitting up lib.h --- xen/arch/arm/io.c | 1 + xen/arch/arm/vgic/vgic-mmio.c | 1 + xen/include/xen/bsearch.h | 50 +++++++++++++++++++++++++++++++++++ xen/include/xen/lib.h | 43 ------------------------------ 4 files changed, 52 insertions(+), 43 deletions(-) create mode 100644 xen/include/xen/bsearch.h diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c index 96c740d5636c..653428e16c1f 100644 --- a/xen/arch/arm/io.c +++ b/xen/arch/arm/io.c @@ -7,6 +7,7 @@ * Copyright (c) 2011 Citrix Systems. */ +#include <xen/bsearch.h> #include <xen/ioreq.h> #include <xen/lib.h> #include <xen/spinlock.h> diff --git a/xen/arch/arm/vgic/vgic-mmio.c b/xen/arch/arm/vgic/vgic-mmio.c index bd4caf7fc326..4ad350c21c8b 100644 --- a/xen/arch/arm/vgic/vgic-mmio.c +++ b/xen/arch/arm/vgic/vgic-mmio.c @@ -13,6 +13,7 @@ */ #include <xen/bitops.h> +#include <xen/bsearch.h> #include <xen/lib.h> #include <xen/sched.h> #include <asm/new_vgic.h> diff --git a/xen/include/xen/bsearch.h b/xen/include/xen/bsearch.h new file mode 100644 index 000000000000..544fe83e2cfc --- /dev/null +++ b/xen/include/xen/bsearch.h @@ -0,0 +1,50 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef XEN_BSEARCH_H +#define XEN_BSEARCH_H + +#include <xen/types.h> + +/* + * 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 + * @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. + * + * Note that the key need not have the same type as the elements in + * the array, e.g. key could be a string and the comparison function + * 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(). + */ +#ifndef BSEARCH_IMPLEMENTATION +extern gnu_inline +#endif +void *bsearch(const void *key, const void *base, size_t num, size_t size, + int (*cmp)(const void *key, const void *elt)) +{ + size_t start = 0, end = num; + int result; + + while ( start < end ) + { + size_t mid = start + (end - start) / 2; + + result = cmp(key, base + mid * size); + if ( result < 0 ) + end = mid; + else if ( result > 0 ) + start = mid + 1; + else + return (void *)base + mid * size; + } + + return NULL; +} + +#endif /* XEN_BSEARCH_H */ diff --git a/xen/include/xen/lib.h b/xen/include/xen/lib.h index 130f96791f75..7060b5d5b658 100644 --- a/xen/include/xen/lib.h +++ b/xen/include/xen/lib.h @@ -159,49 +159,6 @@ void cf_check dump_execstate(const struct cpu_user_regs *regs); void init_constructors(void); -/* - * 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 - * @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. - * - * Note that the key need not have the same type as the elements in - * the array, e.g. key could be a string and the comparison function - * 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(). - */ -#ifndef BSEARCH_IMPLEMENTATION -extern gnu_inline -#endif -void *bsearch(const void *key, const void *base, size_t num, size_t size, - int (*cmp)(const void *key, const void *elt)) -{ - size_t start = 0, end = num; - int result; - - while ( start < end ) - { - size_t mid = start + (end - start) / 2; - - result = cmp(key, base + mid * size); - if ( result < 0 ) - end = mid; - else if ( result > 0 ) - start = mid + 1; - else - return (void *)base + mid * size; - } - - return NULL; -} - #endif /* __ASSEMBLY__ */ #endif /* __LIB_H__ */ -- 2.39.5
|
![]() |
Lists.xenproject.org is hosted with RackSpace, monitoring our |