From: Shanker Donthineni <shankerd@codeaurora.org>
To: xen-devel <xen-devel@lists.xensource.com>,
Julien Grall <julien.grall@arm.com>,
Stefano Stabellini <sstabellini@kernel.org>
Cc: Philip Elcan <pelcan@codeaurora.org>,
Wei Liu <wei.liu2@citrix.com>,
Vikram Sethi <vikrams@codeaurora.org>,
George Dunlap <George.Dunlap@eu.citrix.com>,
Andrew Cooper <andrew.cooper3@citrix.com>,
Ian Jackson <ian.jackson@eu.citrix.com>, Tim Deegan <tim@xen.org>,
Jan Beulich <jbeulich@suse.com>,
Shanker Donthineni <shankerd@codeaurora.org>
Subject: [PATCH V3 2/4] xen: Add generic implementation of binary search
Date: Wed, 20 Jul 2016 09:00:54 -0500 [thread overview]
Message-ID: <1469023256-6487-3-git-send-email-shankerd@codeaurora.org> (raw)
In-Reply-To: <1469023256-6487-1-git-send-email-shankerd@codeaurora.org>
This patch adds the generic implementation of binary search algorithm
which is copied from Linux kernel v4.7-rc7. No functional changes.
Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Julien Grall <julien.grall@arm.com>
---
Changes since v2:
Fixed the compilation issue due to a missing ';'.
Fixed typo.
Changes since v1:
Removed the header file xen/include/xen/bsearch.h.
Defined function bsearch() prototype in the header file xen/lib.h.
xen/common/Makefile | 1 +
xen/common/bsearch.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
xen/include/xen/lib.h | 3 +++
3 files changed, 55 insertions(+)
create mode 100644 xen/common/bsearch.c
diff --git a/xen/common/Makefile b/xen/common/Makefile
index dbf00c6..f8123c2 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -43,6 +43,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..7090930
--- /dev/null
+++ b/xen/common/bsearch.c
@@ -0,0 +1,51 @@
+/*
+ * 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/lib.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/lib.h b/xen/include/xen/lib.h
index b1b0fb2..b90d582 100644
--- a/xen/include/xen/lib.h
+++ b/xen/include/xen/lib.h
@@ -153,4 +153,7 @@ void dump_execstate(struct cpu_user_regs *);
void init_constructors(void);
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+ int (*cmp)(const void *key, const void *elt));
+
#endif /* __LIB_H__ */
--
Qualcomm Datacenter Technologies, Inc. on behalf of the Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
next prev parent reply other threads:[~2016-07-20 14:00 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-07-20 14:00 [PATCH V3 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
2016-07-20 14:00 ` [PATCH V3 1/4] arm/io: Use separate memory allocation for mmio handlers Shanker Donthineni
2016-07-20 14:00 ` Shanker Donthineni [this message]
2016-08-01 12:46 ` [PATCH V3 2/4] xen: Add generic implementation of binary search Jan Beulich
2016-08-01 12:49 ` Andrew Cooper
2016-07-20 14:00 ` [PATCH V3 3/4] xen/arm: io: Use binary search for mmio handler lookup Shanker Donthineni
2016-07-26 21:02 ` Julien Grall
2016-07-20 14:00 ` [PATCH V3 4/4] arm/vgic: Change fixed number of mmio handlers to variable number Shanker Donthineni
2016-07-26 21:02 ` Julien Grall
2016-07-26 22:16 ` [PATCH V3 0/4] Change fixed mmio handlers to a " Stefano Stabellini
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1469023256-6487-3-git-send-email-shankerd@codeaurora.org \
--to=shankerd@codeaurora.org \
--cc=George.Dunlap@eu.citrix.com \
--cc=andrew.cooper3@citrix.com \
--cc=ian.jackson@eu.citrix.com \
--cc=jbeulich@suse.com \
--cc=julien.grall@arm.com \
--cc=pelcan@codeaurora.org \
--cc=sstabellini@kernel.org \
--cc=tim@xen.org \
--cc=vikrams@codeaurora.org \
--cc=wei.liu2@citrix.com \
--cc=xen-devel@lists.xensource.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).