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

Commit Message

Shanker Donthineni July 14, 2016, 4:18 p.m. UTC

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 <[e-mail]>
---
 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

Comments

Julien Grall July 14, 2016, 4:28 p.m. UTC | #1

Hi Shanker,

Can you please try to thread properly your series, and re-number it with 
the correct amount of patch if some have been applied.

It will avoid people to wondering if they missed some e-mails.

On 14/07/16 17:18, Shanker Donthineni wrote:
> 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.

Usually, the coding style is not changed in verbatim copy of Linux 
source code in order to make easier the sync.

Also, I would appreciate if you can mention the version Linux at the 
time of the sync for similar reason.

Regards,

Patch

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 <[e-mail]>
+ *
+ * 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__ */