From 8efca839fc616573bbc5d05ce6e6d8b87991ae93 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sat, 20 Feb 2016 22:24:08 +0100 Subject: add bsearch MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/stdlib/bsearch.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) create mode 100644 src/stdlib/bsearch.c (limited to 'src/stdlib') diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c new file mode 100644 index 0000000..c459ea4 --- /dev/null +++ b/src/stdlib/bsearch.c @@ -0,0 +1,70 @@ +/** + * slibc — Yet another C library + * Copyright © 2015, 2016 Mattias Andrée (maandree@member.fsf.org) + * + * 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, either version 3 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ +#include + + +# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers" + + + +/** + * Search for an item in a sorted list of comparable + * elements. The list must be sorted in ascending order. + * The function usually implements binary search, + * as is done in this implementation. + * + * @etymology (B)inary (search). + * + * @param sought The sought item. + * @param list The beginning of the list to search. + * @param n The number of elements in the list. + * @param width The width, in bytes, of each element in the list. + * @param compar A function that shall compare two items, and return + * a value less than, equal to, or greater than zero + * if the first argument is less than, equal to, or + * greater than the second argument, respectively. + * @return The address of an arbritrart element in `list` that + * is equal to `sought`, or `NULL` if no such element + * can be found (does not exist, or because `list` + * is not properly sorted.) + * + * @since Always. + */ +void* (bsearch)(const void* sought, const void* list, size_t n, size_t width, + int (*compar)(const void*, const void*)) +{ + int cmp, i; + char* test; + if (n == 0) + return NULL; + for (;;) + { + i = n >> 1; + test = (char*)list + i * width; + cmp = compar(sought, test); + if (!i) + return cmp ? NULL : test; + else if (cmp < 0) + n = i; + else if (cmp > 0) + n -= i, list = test; + else + return test; + } +} + -- cgit v1.2.3-70-g09d2