]>
Commit | Line | Data |
---|---|---|
2aa62f2b | 1 | /** @file\r |
2 | Binary search utility function.\r | |
3 | \r | |
4 | This utility makes use of a comparison function to search arrays of\r | |
5 | unspecified type. Where an argument declared as size_t nmemb specifies the\r | |
6 | length of the array for a function, nmemb can have the value zero on a call\r | |
7 | to that function; the comparison function is not called, a search finds no\r | |
8 | matching element. Pointer arguments on such a call shall still have valid\r | |
9 | values.\r | |
10 | \r | |
11 | The implementation shall ensure that the second argument of the comparison\r | |
12 | function is a pointer to an element of the array. The first argument shall\r | |
13 | equal key.\r | |
14 | \r | |
15 | The comparison function shall not alter the contents of the array. The\r | |
16 | implementation may reorder elements of the array between calls to the\r | |
17 | comparison function, but shall not alter the contents of any individual\r | |
18 | element.\r | |
19 | \r | |
20 | When the same objects (consisting of size bytes, irrespective of their\r | |
21 | current positions in the array) are passed more than once to the comparison\r | |
22 | function, the results shall be consistent with one another. That is, the same\r | |
23 | object shall always compare the same way with the key.\r | |
24 | \r | |
25 | A sequence point occurs immediately before and immediately after each call to\r | |
26 | the comparison function, and also between any call to the comparison function\r | |
27 | and any movement of the objects passed as arguments to that call.\r | |
28 | \r | |
29 | Copyright (c) 2010, Intel Corporation. All rights reserved.<BR>\r | |
30 | \r | |
31 | * Copyright (c) 1990, 1993\r | |
32 | * The Regents of the University of California. All rights reserved.\r | |
33 | *\r | |
34 | * Redistribution and use in source and binary forms, with or without\r | |
35 | * modification, are permitted provided that the following conditions\r | |
36 | * are met:\r | |
37 | * 1. Redistributions of source code must retain the above copyright\r | |
38 | * notice, this list of conditions and the following disclaimer.\r | |
39 | * 2. Redistributions in binary form must reproduce the above copyright\r | |
40 | * notice, this list of conditions and the following disclaimer in the\r | |
41 | * documentation and/or other materials provided with the distribution.\r | |
42 | * 4. Neither the name of the University nor the names of its contributors\r | |
43 | * may be used to endorse or promote products derived from this software\r | |
44 | * without specific prior written permission.\r | |
45 | *\r | |
46 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND\r | |
47 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\r | |
48 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\r | |
49 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE\r | |
50 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\r | |
51 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS\r | |
52 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)\r | |
53 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT\r | |
54 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY\r | |
55 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r | |
56 | * SUCH DAMAGE.\r | |
57 | \r | |
58 | ("$FreeBSD: src/lib/libc/stdlib/bsearch.c,v 1.4.10.1.2.1 2009/10/25 01:10:29 kensmith Exp $");\r | |
59 | **/\r | |
60 | #include <LibConfig.h>\r | |
61 | #include <sys/EfiCdefs.h>\r | |
62 | #include <stdlib.h>\r | |
63 | \r | |
64 | /*\r | |
65 | * Perform a binary search.\r | |
66 | *\r | |
67 | * The code below is a bit sneaky. After a comparison fails, we\r | |
68 | * divide the work in half by moving either left or right. If lim\r | |
69 | * is odd, moving left simply involves halving lim: e.g., when lim\r | |
70 | * is 5 we look at item 2, so we change lim to 2 so that we will\r | |
71 | * look at items 0 & 1. If lim is even, the same applies. If lim\r | |
72 | * is odd, moving right again involes halving lim, this time moving\r | |
73 | * the base up one item past p: e.g., when lim is 5 we change base\r | |
74 | * to item 3 and make lim 2 so that we will look at items 3 and 4.\r | |
75 | * If lim is even, however, we have to shrink it by one before\r | |
76 | * halving: e.g., when lim is 4, we still looked at item 2, so we\r | |
77 | * have to make lim 3, then halve, obtaining 1, so that we will only\r | |
78 | * look at item 3.\r | |
79 | */\r | |
80 | void *\r | |
81 | bsearch(\r | |
82 | const void *key,\r | |
83 | const void *base0,\r | |
84 | size_t nmemb,\r | |
85 | size_t size,\r | |
86 | int (*compar)(const void *, const void *)\r | |
87 | )\r | |
88 | {\r | |
89 | const char *base = base0;\r | |
90 | size_t lim;\r | |
91 | int cmp;\r | |
92 | const void *p;\r | |
93 | \r | |
94 | for (lim = nmemb; lim != 0; lim >>= 1) {\r | |
95 | p = base + (lim >> 1) * size;\r | |
96 | cmp = (*compar)(key, p);\r | |
97 | if (cmp == 0)\r | |
98 | return ((void *)p);\r | |
99 | if (cmp > 0) { /* key > p: move right */\r | |
100 | base = (char *)p + size;\r | |
101 | lim--;\r | |
102 | } /* else move left */\r | |
103 | }\r | |
104 | return (NULL);\r | |
105 | }\r |