| 1 | /*
|
|---|
| 2 | Unix SMB/CIFS implementation.
|
|---|
| 3 |
|
|---|
| 4 | a generic binary search macro
|
|---|
| 5 |
|
|---|
| 6 | Copyright (C) Andrew Tridgell 2009
|
|---|
| 7 |
|
|---|
| 8 | This program is free software; you can redistribute it and/or modify
|
|---|
| 9 | it under the terms of the GNU General Public License as published by
|
|---|
| 10 | the Free Software Foundation; either version 3 of the License, or
|
|---|
| 11 | (at your option) any later version.
|
|---|
| 12 |
|
|---|
| 13 | This program is distributed in the hope that it will be useful,
|
|---|
| 14 | but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|---|
| 16 | GNU General Public License for more details.
|
|---|
| 17 |
|
|---|
| 18 | You should have received a copy of the GNU General Public License
|
|---|
| 19 | along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|---|
| 20 | */
|
|---|
| 21 |
|
|---|
| 22 | #ifndef _BINSEARCH_H
|
|---|
| 23 | #define _BINSEARCH_H
|
|---|
| 24 |
|
|---|
| 25 | /* a binary array search, where the array is an array of pointers to structures,
|
|---|
| 26 | and we want to find a match for 'target' on 'field' in those structures.
|
|---|
| 27 |
|
|---|
| 28 | Inputs:
|
|---|
| 29 | array: base pointer to an array of structures
|
|---|
| 30 | arrray_size: number of elements in the array
|
|---|
| 31 | field: the name of the field in the structure we are keying off
|
|---|
| 32 | target: the field value we are looking for
|
|---|
| 33 | comparison_fn: the comparison function
|
|---|
| 34 | result: where the result of the search is put
|
|---|
| 35 |
|
|---|
| 36 | if the element is found, then 'result' is set to point to the found array element. If not,
|
|---|
| 37 | then 'result' is set to NULL.
|
|---|
| 38 |
|
|---|
| 39 | The array is assumed to be sorted by the same comparison_fn as the
|
|---|
| 40 | search (with, for example, qsort)
|
|---|
| 41 | */
|
|---|
| 42 | #define BINARY_ARRAY_SEARCH_P(array, array_size, field, target, comparison_fn, result) do { \
|
|---|
| 43 | int32_t _b, _e; \
|
|---|
| 44 | (result) = NULL; \
|
|---|
| 45 | if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
|
|---|
| 46 | int32_t _i = (_b+_e)/2; \
|
|---|
| 47 | int _r = comparison_fn(target, array[_i]->field); \
|
|---|
| 48 | if (_r == 0) { (result) = array[_i]; break; } \
|
|---|
| 49 | if (_r < 0) _e = _i - 1; else _b = _i + 1; \
|
|---|
| 50 | }} } while (0)
|
|---|
| 51 |
|
|---|
| 52 | /*
|
|---|
| 53 | like BINARY_ARRAY_SEARCH_P, but assumes that the array is an array
|
|---|
| 54 | of structures, rather than pointers to structures
|
|---|
| 55 |
|
|---|
| 56 | result points to the found structure, or NULL
|
|---|
| 57 | */
|
|---|
| 58 | #define BINARY_ARRAY_SEARCH(array, array_size, field, target, comparison_fn, result) do { \
|
|---|
| 59 | int32_t _b, _e; \
|
|---|
| 60 | (result) = NULL; \
|
|---|
| 61 | if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
|
|---|
| 62 | int32_t _i = (_b+_e)/2; \
|
|---|
| 63 | int _r = comparison_fn(target, array[_i].field); \
|
|---|
| 64 | if (_r == 0) { (result) = &array[_i]; break; } \
|
|---|
| 65 | if (_r < 0) _e = _i - 1; else _b = _i + 1; \
|
|---|
| 66 | }} } while (0)
|
|---|
| 67 |
|
|---|
| 68 | /*
|
|---|
| 69 | like BINARY_ARRAY_SEARCH_P, but assumes that the array is an array
|
|---|
| 70 | of elements, rather than pointers to structures
|
|---|
| 71 |
|
|---|
| 72 | result points to the found structure, or NULL
|
|---|
| 73 | */
|
|---|
| 74 | #define BINARY_ARRAY_SEARCH_V(array, array_size, target, comparison_fn, result) do { \
|
|---|
| 75 | int32_t _b, _e; \
|
|---|
| 76 | (result) = NULL; \
|
|---|
| 77 | if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
|
|---|
| 78 | int32_t _i = (_b+_e)/2; \
|
|---|
| 79 | int _r = comparison_fn(target, array[_i]); \
|
|---|
| 80 | if (_r == 0) { (result) = &array[_i]; break; } \
|
|---|
| 81 | if (_r < 0) _e = _i - 1; else _b = _i + 1; \
|
|---|
| 82 | }} } while (0)
|
|---|
| 83 |
|
|---|
| 84 | #endif
|
|---|
