All of lore.kernel.org
 help / color / mirror / Atom feed
From: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
To: greg@kroah.com
Cc: linux-kbuild@vger.kernel.org, carmelo73@gmail.com,
	linux-kernel@vger.kernel.org, rusty@rustcorp.com.au,
	Tim Abbott <tabbott@ksplice.com>,
	Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Subject: [PATCH 07/10] lib: Add generic binary search function to the kernel.
Date: Tue,  3 Nov 2009 10:06:19 +0000	[thread overview]
Message-ID: <1257242782-10496-8-git-send-email-alan-jenkins@tuffmail.co.uk> (raw)
In-Reply-To: <9b2b86520911020852q49c55695rb05d87090fa9ad33@mail.gmail.com>

From: Tim Abbott <tabbott@ksplice.com>

There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them).  Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.

This generic binary search implementation comes from Ksplice.  It has
the same basic API as the C library bsearch() function.  Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.

Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    2 +-
 lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/bsearch.h
 create mode 100644 lib/bsearch.c

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/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 /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index 2e78277..fb60af1 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y	+= kobject.o kref.o klist.o
 
 obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
 	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-	 string_helpers.o gcd.o
+	 string_helpers.o gcd.o bsearch.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..4297c98
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,53 @@
+/*
+ * 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 <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to data to sort
+ * @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))
+{
+	int start = 0, end = num - 1, mid, result;
+	if (num == 0)
+		return NULL;
+
+	while (start <= end) {
+		mid = (start + end) / 2;
+		result = cmp(key, base + mid * size);
+		if (result < 0)
+			end = mid - 1;
+		else if (result > 0)
+			start = mid + 1;
+		else
+			return (void *)base + mid * size;
+	}
+
+	return NULL;
+}
+EXPORT_SYMBOL(bsearch);
-- 
1.6.3.2


  parent reply	other threads:[~2009-11-03 10:08 UTC|newest]

Thread overview: 57+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2009-11-02 16:52 Fast LKM symbol resolution Alan Jenkins
2009-11-03  3:55 ` Greg KH
2009-11-03 10:06 ` [PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search) Alan Jenkins
2009-11-03 15:58   ` Greg KH
2009-11-05 12:17     ` Rusty Russell
2009-11-03 10:06 ` [PATCH 01/10] ARM: use unified discard definition in linker script Alan Jenkins
2009-11-03 10:06 ` [PATCH 02/10] ARM: unexport symbols used to implement floating point emulation Alan Jenkins
2009-11-03 10:06 ` [PATCH 03/10] module: extract __EXPORT_SYMBOL from module.h into mod_export.h Alan Jenkins
2009-11-03 10:06 ` [PATCH 04/10] module: make MODULE_SYMBOL_PREFIX into a CONFIG option Alan Jenkins
2009-11-03 10:19   ` Mike Frysinger
2009-11-03 10:19     ` Mike Frysinger
2009-11-03 12:16     ` Alan Jenkins
2009-11-03 12:30       ` Mike Frysinger
2009-11-03 12:30         ` Mike Frysinger
2009-11-03 13:29         ` Paul Mundt
2009-11-03 13:39           ` Mike Frysinger
2009-11-03 13:39             ` Mike Frysinger
2009-11-03 13:46             ` Paul Mundt
2009-11-03 13:58               ` Mike Frysinger
2009-11-03 13:58                 ` Mike Frysinger
2009-11-03 14:07                 ` Paul Mundt
2009-11-03 10:06 ` [PATCH 05/10] kbuild: sort the list of symbols exported by the kernel (__ksymtab) Alan Jenkins
2009-11-04  8:19   ` Rusty Russell
2009-11-04 10:00     ` Alan Jenkins
2009-11-04 11:12       ` Mike Frysinger
2009-11-04 11:12         ` Mike Frysinger
2009-11-04 17:19       ` Sam Ravnborg
2009-11-05 14:24         ` Alan Jenkins
2009-11-05 16:17           ` Mike Frysinger
2009-11-05 16:17             ` Mike Frysinger
2009-11-09  3:17           ` Rusty Russell
2009-11-20 22:20             ` Tony Luck
2009-11-20 22:20               ` Tony Luck
2009-11-21  0:02               ` Alan Jenkins
2009-11-23 19:53                 ` Alex Chiang
2009-11-23 22:44                   ` Alan Jenkins
2009-11-24  0:57                   ` Rusty Russell
2009-11-24  5:39                     ` James Bottomley
2009-11-24  9:28                       ` Alan Jenkins
2009-11-24 22:43                         ` James Bottomley
2009-11-25  9:15                           ` Alan Jenkins
2009-11-25 15:08                             ` James Bottomley
2009-11-25 17:01                               ` Alan Jenkins
2009-11-27 11:03                               ` Rusty Russell
2009-11-26  0:40   ` Andrew Morton
2009-11-26 17:14     ` Alan Jenkins
2009-11-03 10:06 ` [PATCH 06/10] module: refactor symbol tables and try to reduce code size of each_symbol() Alan Jenkins
2009-11-04  8:28   ` Rusty Russell
2009-11-04  9:45     ` Alan Jenkins
2009-11-03 10:06 ` Alan Jenkins [this message]
2009-11-03 10:06 ` [PATCH 08/10] lib: bsearch - remove redundant special case for arrays of size 0 Alan Jenkins
2009-11-03 10:06 ` [PATCH 09/10] module: speed up find_symbol() using binary search on the builtin symbol tables Alan Jenkins
2009-11-04  8:31   ` Rusty Russell
2009-11-03 10:06 ` [PATCH 10/10] module: fix is_exported() to return true for all types of exports Alan Jenkins
2009-11-04  8:32   ` Rusty Russell
2009-11-06  5:37 ` Fast LKM symbol resolution Carmelo Amoroso
2009-11-07 20:59 [PATCH 0/10] module: Speed up symbol resolution during module loading (using binary search) Alan Jenkins
2009-11-07 21:03 ` [PATCH 07/10] lib: Add generic binary search function to the kernel Alan Jenkins

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=1257242782-10496-8-git-send-email-alan-jenkins@tuffmail.co.uk \
    --to=alan-jenkins@tuffmail.co.uk \
    --cc=carmelo73@gmail.com \
    --cc=greg@kroah.com \
    --cc=linux-kbuild@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=rusty@rustcorp.com.au \
    --cc=tabbott@ksplice.com \
    --subject='Re: [PATCH 07/10] lib: Add generic binary search function to the kernel.' \
    /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

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.