Mercurial > ecos
annotate packages/language/c/libc/current/src/stdlib/bsearch.cxx @ 64:c38311975d4f ecos-sw-2000-01-28
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
| author | jlarmour |
|---|---|
| date | Fri, 28 Jan 2000 04:59:39 +0000 |
| parents | 443894e2e912 |
| children | bf00f99aec69 |
| rev | line source |
|---|---|
| 0 | 1 //=========================================================================== |
| 2 // | |
| 3 // bsearch.cxx | |
| 4 // | |
| 5 // ANSI standard binary search function defined in section 7.10.5.1 | |
| 6 // of the standard | |
| 7 // | |
| 8 //=========================================================================== | |
| 9 //####COPYRIGHTBEGIN#### | |
|
64
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
10 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
11 // ------------------------------------------- |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
12 // The contents of this file are subject to the Red Hat eCos Public License |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
13 // Version 1.0 (the "License"); you may not use this file except in |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
14 // compliance with the License. You may obtain a copy of the License at |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
15 // http://sourceware.cygnus.com/ecos |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
16 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
17 // Software distributed under the License is distributed on an |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
18 // basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
19 // License for the specific language governing rights and limitations under |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
20 // the License. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
21 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
22 // The Original Code is eCos - Embedded Configurable Operating System, |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
23 // released September 30, 1998. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
24 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
25 // The Initial Developer of the Original Code is Red Hat. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
26 // Portions created by Red Hat are |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
27 // Copyright (C) 1998, 1999, 2000 Red Hat, Inc. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
28 // All Rights Reserved. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
29 // ------------------------------------------- |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
30 // |
| 0 | 31 //####COPYRIGHTEND#### |
| 32 //=========================================================================== | |
| 33 //#####DESCRIPTIONBEGIN#### | |
| 34 // | |
| 35 // Author(s): jlarmour | |
| 2 | 36 // Contributors: jlarmour |
| 0 | 37 // Date: 1998-02-13 |
| 38 // Purpose: | |
| 39 // Description: | |
| 40 // Usage: | |
| 41 // | |
| 42 //####DESCRIPTIONEND#### | |
| 43 // | |
| 44 //=========================================================================== | |
| 45 | |
| 46 // CONFIGURATION | |
| 47 | |
| 48 #include <pkgconf/libc.h> // Configuration header | |
| 49 | |
| 50 // Include the C library? | |
| 51 #ifdef CYGPKG_LIBC | |
| 52 | |
| 53 // INCLUDES | |
| 54 | |
| 55 #include <cyg/infra/cyg_type.h> // Common type definitions and support | |
| 56 #include <cyg/infra/cyg_trac.h> // Tracing support | |
| 57 #include <cyg/infra/cyg_ass.h> // Assertion support | |
| 58 #include <stdlib.h> // Header for all stdlib functions | |
| 59 // (like this one) | |
| 60 #include "clibincl/stdlibsupp.hxx" // Support for stdlib functions | |
| 61 | |
| 62 // TRACING | |
| 63 | |
| 64 # if defined(CYGDBG_USE_TRACING) && \ | |
| 65 defined(CYGNUM_LIBC_BSEARCH_TRACE_LEVEL) | |
| 66 static int bsearch_trace = CYGNUM_LIBC_BSEARCH_TRACE_LEVEL; | |
| 67 # define TL1 (0 < bsearch_trace) | |
| 68 # else | |
| 69 # define TL1 (0) | |
| 70 # endif | |
| 71 | |
| 72 | |
| 73 // EXPORTED SYMBOLS | |
| 74 | |
| 75 externC void * | |
| 76 bsearch( const void *key, const void *base, size_t nmemb, size_t size, | |
| 77 Cyg_comparison_fn_t compar ) CYGPRI_LIBC_WEAK_ALIAS("_bsearch"); | |
| 78 | |
| 79 // FUNCTIONS | |
| 80 | |
| 81 externC void * | |
| 82 _bsearch( const void *key, const void *base, size_t nmemb, size_t size, | |
| 83 Cyg_comparison_fn_t compar ) | |
| 84 { | |
| 85 CYG_REPORT_FUNCNAMETYPE( "_bsearch", "returning %08x" ); | |
| 86 | |
| 87 CYG_REPORT_FUNCARG5( "key=%08x, base=%08x, nmemb=%d, size=%d, " | |
| 88 "compar=%08x", key, base, nmemb, size, compar ); | |
| 89 | |
| 90 CYG_CHECK_DATA_PTR( key, "key is not a valid pointer!" ); | |
| 91 CYG_CHECK_DATA_PTR( base, "base is not a valid pointer!" ); | |
| 92 CYG_CHECK_FUNC_PTR( compar, "compar is not a valid function pointer!" ); | |
| 93 | |
| 94 CYG_ADDRESS current; | |
| 95 size_t lower = 0; | |
| 96 size_t upper = nmemb; | |
| 97 size_t index; | |
| 98 int result; | |
| 99 | |
| 100 if (nmemb == 0 || size == 0) | |
| 101 { | |
| 102 CYG_TRACE2( TL1, "Warning! either nmemb (%d) or size (%d) is 0", | |
| 103 nmemb, size ); | |
| 104 CYG_REPORT_RETVAL( NULL ); | |
| 105 return NULL; | |
| 106 } // if | |
| 107 | |
| 108 while (lower < upper) | |
| 109 { | |
| 110 index = (lower + upper) / 2; | |
| 111 current = (CYG_ADDRESS) (((char *) base) + (index * size)); | |
| 112 | |
| 113 CYG_TRACE2( TL1, "About to call comparison function with " | |
| 114 "key=%08x, current=%08x", key, current ); | |
| 115 result = compar (key, (void *) current); | |
| 116 CYG_TRACE1( TL1, "Comparison function returned %d", result ); | |
| 117 | |
| 118 if (result < 0) | |
| 119 upper = index; | |
| 120 else if (result > 0) | |
| 121 lower = index + 1; | |
| 122 else | |
| 123 { | |
| 124 CYG_REPORT_RETVAL( current ); | |
| 125 return (void *)current; | |
| 126 } // else | |
| 127 } // while | |
| 128 | |
| 129 CYG_REPORT_RETVAL( NULL ); | |
| 130 return NULL; | |
| 131 } // _bsearch() | |
| 132 | |
| 133 #endif // ifdef CYGPKG_LIBC | |
| 134 | |
| 135 // EOF bsearch.cxx |