[PATCH V4 09/11] xen: Add generic implementation of binary search

[Shanker Donthineni <shankerd@codeaurora.org>]

This patch adds the generic implementation of binary search algorithm
whcih is copied from Linux kernel. Only coding style changes to match
the general XEN coding style. No functional changes.

Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
---
 xen/common/Makefile       |  1 +
 xen/common/bsearch.c      | 52 +++++++++++++++++++++++++++++++++++++++++++++++
 xen/include/xen/bsearch.h |  9 ++++++++
 3 files changed, 62 insertions(+)
 create mode 100644 xen/common/bsearch.c
 create mode 100644 xen/include/xen/bsearch.h

diff --git a/xen/common/Makefile b/xen/common/Makefile
index 2a83261..2fa36a4 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -41,6 +41,7 @@ obj-y += schedule.o
 obj-y += shutdown.o
 obj-y += softirq.o
 obj-y += sort.o
+obj-y += bsearch.o
 obj-y += smp.o
 obj-y += spinlock.o
 obj-y += stop_machine.o
diff --git a/xen/common/bsearch.c b/xen/common/bsearch.c
new file mode 100644
index 0000000..0946762
--- /dev/null
+++ b/xen/common/bsearch.c
@@ -0,0 +1,52 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <xen/bsearch.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().
+ */
+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;
+}
diff --git a/xen/include/xen/bsearch.h b/xen/include/xen/bsearch.h
new file mode 100644
index 0000000..07cf604
--- /dev/null
+++ b/xen/include/xen/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef __XEN_BSEARCH_H__
+#define __XEN_BSEARCH_H__
+
+#include <xen/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt));
+
+#endif /* __XEN_BSEARCH_H__ */
-- 
Qualcomm Technologies, Inc. on behalf of Qualcomm Innovation Center, Inc. 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
a Linux Foundation Collaborative Project


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel