about summary refs log tree commit diff
path: root/stdlib/bsearch.c
diff options
context:
space:
mode:
Diffstat (limited to 'stdlib/bsearch.c')
-rw-r--r--stdlib/bsearch.c51
1 files changed, 51 insertions, 0 deletions
diff --git a/stdlib/bsearch.c b/stdlib/bsearch.c
new file mode 100644
index 0000000000..d798eabd2b
--- /dev/null
+++ b/stdlib/bsearch.c
@@ -0,0 +1,51 @@
+/* Copyright (C) 1991, 1992 Free Software Foundation, Inc.
+This file is part of the GNU C Library.
+
+The GNU C Library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Library General Public License as
+published by the Free Software Foundation; either version 2 of the
+License, or (at your option) any later version.
+
+The GNU C Library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Library General Public License for more details.
+
+You should have received a copy of the GNU Library General Public
+License along with the GNU C Library; see the file COPYING.LIB.  If
+not, write to the Free Software Foundation, Inc., 675 Mass Ave,
+Cambridge, MA 02139, USA.  */
+
+#include <ansidecl.h>
+#include <stdlib.h>
+
+
+/* Perform a binary search for KEY in BASE which has NMEMB elements
+   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
+PTR
+DEFUN(bsearch, (key, base, nmemb, size, compar),
+      register CONST PTR key AND register CONST PTR base AND
+      size_t nmemb AND register size_t size AND
+      register int EXFUN((*compar), (CONST PTR, CONST PTR)))
+{
+  register size_t l, u, idx;
+  register CONST PTR p;
+  register int comparison;
+
+  l = 0;
+  u = nmemb;
+  while (l < u)
+    {
+      idx = (l + u) / 2;
+      p = (PTR) (((CONST char *) base) + (idx * size));
+      comparison = (*compar)(key, p);
+      if (comparison < 0)
+	u = idx;
+      else if (comparison > 0)
+	l = idx + 1;
+      else
+	return (PTR) p;
+    }
+
+  return NULL;
+}