algorithm.h (1931B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #ifndef ALGORITHM_H 17 #define ALGORITHM_H 18 19 #include "rsys.h" 20 21 /* Search the first element in an array of `nmemb' objects pointed by `base', 22 * the first member that is *not* less than `key'. The size of each member of 23 * the array is specified by `size'. The array should be in ascending order 24 * according to the `compar' functor. This function is expected to have two 25 * arguments which point to the `key' object and an array member, in that 26 * order, and should return an integer less than, equal to, or greater than 27 * zero if the key object is found, respectively, to be less than, to match, or 28 * be greater than the array member. Return NULL if all array members compare 29 * less than `key'. */ 30 static INLINE void* 31 search_lower_bound 32 (const void* key, 33 const void* base, 34 size_t nmemb, 35 size_t size, 36 int (*compar)(const void*, const void*)) 37 { 38 #define AT(Base, Id) (void*)((const char*)(Base) + (Id)*size) 39 size_t lo = 0, hi = nmemb - 1; 40 while(lo < hi) { 41 size_t mid = (lo + hi) / 2; 42 if(compar(key, AT(base, mid)) > 0) { 43 lo = mid + 1; 44 } else { 45 hi = mid; 46 } 47 } 48 return compar(key, AT(base, lo)) > 0 ? NULL : AT(base, lo); 49 #undef AT 50 } 51 52 #endif /* ALGORITHM_H */