@@ -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>
@@ -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>
new file mode 100644
@@ -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 */
@@ -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__ */
There are currently two users, and lib.h is included everywhere. No functional change. Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> --- CC: Anthony PERARD <anthony.perard@vates.tech> CC: Michal Orzel <michal.orzel@amd.com> CC: Jan Beulich <jbeulich@suse.com> CC: Julien Grall <julien@xen.org> CC: Roger Pau Monné <roger.pau@citrix.com> CC: Stefano Stabellini <sstabellini@kernel.org> CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com> CC: Bertrand Marquis <bertrand.marquis@arm.com> 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