1 /*
2 * $Id: wce_bsearch.c 20 2006-11-18 17:00:30Z mloskot $
3 *
4 * Defines bsearch() function.
5 *
6 * Created by Mateusz Loskot (mateusz@loskot.net)
7 *
8 * Copyright (c) 2006 Mateusz Loskot
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining
11 * a copy of this software and associated documentation files (the "Software"),
12 * to deal in the Software without restriction, including without limitation
13 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 * and/or sell copies of the Software, and to permit persons to whom
15 * the Software is furnished to do so, subject to the following conditions:
16 *
17 * The above copyright notice and this permission notice shall be included
18 * in all copies or substantial portions of the Software.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
23 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
24 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
25 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH
26 * THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 *
28 * MIT License:
29 * http://opensource.org/licenses/mit-license.php
30 *
31 */
32
33 #include <stdlib.h>
34 #include <assert.h>
35 #include <wce_types.h>
36
37 /*******************************************************************************
38 * wceex_bsearch - TODO
39 *
40 * Description:
41 *
42 * Return:
43 *
44 *
45 * Reference:
46 * IEEE 1003.1, 2004 Edition
47 *******************************************************************************/
48
wceex_bsearch(const void * key,const void * base,size_t num,size_t width,int (* compare)(const void *,const void *))49 void* wceex_bsearch(const void *key, const void *base, size_t num, size_t width,
50 int (*compare)(const void *, const void *))
51 {
52 size_t left;
53 size_t middle;
54 size_t right;
55 int res;
56
57 /* input parameters validation */
58 assert(key != NULL);
59 assert(base != NULL);
60 assert(compare != NULL);
61
62 res = 0;
63 left = 0;
64 right = num - 1;
65
66 while (left <= right)
67 {
68 middle = (left + right) / 2;
69
70 res = compare(((char*) base + (width * middle)), key);
71 if (res > 0)
72 {
73 /* search from middle to left */
74 right = middle - 1;
75 }
76 else if (res < 0)
77 {
78 /* search from middle to right */
79 left = middle + 1;
80 }
81 else if (res == 0)
82 {
83 /* middle points to the key element. */
84 return ((char*) base + (width * middle));
85 }
86 }
87
88 /* key not found */
89 return NULL;
90 }