order.c (2259B)
1 /* Copyright (c) 2003-2004, Roger Dingledine 2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. 3 * Copyright (c) 2007-2021, The Tor Project, Inc. */ 4 /* See LICENSE for licensing information */ 5 6 /** 7 * \file order.c 8 * \brief Functions for finding the n'th element of an array. 9 **/ 10 11 #include <stdlib.h> 12 13 #include "lib/container/order.h" 14 #include "lib/log/util_bug.h" 15 16 /** Declare a function called <b>funcname</b> that acts as a find_nth_FOO 17 * function for an array of type <b>elt_t</b>*. 18 * 19 * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding 20 * the kth element of an n-element list can be done in O(n). Then again, this 21 * implementation is not in critical path, and it is obviously correct. */ 22 #define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ 23 static int \ 24 _cmp_ ## elt_t(const void *_a, const void *_b) \ 25 { \ 26 const elt_t *a = _a, *b = _b; \ 27 if (*a<*b) \ 28 return -1; \ 29 else if (*a>*b) \ 30 return 1; \ 31 else \ 32 return 0; \ 33 } \ 34 elt_t \ 35 funcname(elt_t *array, int n_elements, int nth) \ 36 { \ 37 tor_assert(nth >= 0); \ 38 tor_assert(nth < n_elements); \ 39 qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ 40 return array[nth]; \ 41 } 42 43 IMPLEMENT_ORDER_FUNC(find_nth_int, int) 44 IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) 45 IMPLEMENT_ORDER_FUNC(find_nth_double, double) 46 IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) 47 IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t) 48 IMPLEMENT_ORDER_FUNC(find_nth_long, long)