Rev 4874 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /* |
2 | * bsearch.c |
||
3 | * Original Author: G. Haley |
||
4 | * Rewritten by: G. Noer |
||
5 | * |
||
6 | * Searches an array of nmemb members, the initial member of which is pointed |
||
7 | * to by base, for a member that matches the object pointed to by key. The |
||
8 | * contents of the array shall be in ascending order according to a comparison |
||
9 | * function pointed to by compar. The function shall return an integer less |
||
10 | * than, equal to or greater than zero if the first argument is considered to be |
||
11 | * respectively less than, equal to or greater than the second. Returns a |
||
12 | * pointer to the matching member of the array, or a null pointer if no match |
||
13 | * is found. |
||
14 | */ |
||
15 | |||
16 | /* |
||
17 | FUNCTION |
||
18 | < |
||
19 | |||
20 | INDEX |
||
21 | bsearch |
||
22 | |||
23 | ANSI_SYNOPSIS |
||
24 | #include |
||
25 | void *bsearch(const void *<[key]>, const void *<[base]>, |
||
26 | size_t <[nmemb]>, size_t <[size]>, |
||
27 | int (*<[compar]>)(const void *, const void *)); |
||
28 | |||
29 | TRAD_SYNOPSIS |
||
30 | #include |
||
31 | char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>) |
||
32 | char *<[key]>; |
||
33 | char *<[base]>; |
||
34 | size_t <[nmemb]>, <[size]>; |
||
35 | int (*<[compar]>)(); |
||
36 | |||
37 | DESCRIPTION |
||
38 | < |
||
39 | that matches <[key]>, using binary search. <[nmemb]> is the element |
||
40 | count of the array; <[size]> is the size of each element. |
||
41 | |||
42 | The array must be sorted in ascending order with respect to the |
||
43 | comparison function <[compar]> (which you supply as the last argument of |
||
44 | < |
||
45 | |||
46 | You must define the comparison function <<(*<[compar]>)>> to have two |
||
47 | arguments; its result must be negative if the first argument is |
||
48 | less than the second, zero if the two arguments match, and |
||
49 | positive if the first argument is greater than the second (where |
||
50 | ``less than'' and ``greater than'' refer to whatever arbitrary |
||
51 | ordering is appropriate). |
||
52 | |||
53 | RETURNS |
||
54 | Returns a pointer to an element of <[array]> that matches <[key]>. If |
||
55 | more than one matching element is available, the result may point to |
||
56 | any of them. |
||
57 | |||
58 | PORTABILITY |
||
59 | < |
||
60 | |||
61 | No supporting OS subroutines are required. |
||
62 | */ |
||
63 | |||
64 | #include |
||
65 | |||
66 | _PTR |
||
67 | _DEFUN (bsearch, (key, base, nmemb, size, compar), |
||
68 | _CONST _PTR key _AND |
||
69 | _CONST _PTR base _AND |
||
70 | size_t nmemb _AND |
||
71 | size_t size _AND |
||
72 | int _EXFNPTR(compar, (const _PTR, const _PTR))) |
||
73 | { |
||
74 | _PTR current; |
||
75 | size_t lower = 0; |
||
76 | size_t upper = nmemb; |
||
77 | size_t index; |
||
78 | int result; |
||
79 | |||
80 | if (nmemb == 0 || size == 0) |
||
81 | return NULL; |
||
82 | |||
83 | while (lower < upper) |
||
84 | { |
||
85 | index = (lower + upper) / 2; |
||
86 | current = (_PTR) (((char *) base) + (index * size)); |
||
87 | |||
88 | result = compar (key, current); |
||
89 | |||
90 | if (result < 0) |
||
91 | upper = index; |
||
92 | else if (result > 0) |
||
93 | lower = index + 1; |
||
94 | else |
||
95 | return current; |
||
96 | } |
||
97 | |||
98 | return NULL; |
||
99 | }>> |
||
100 |