Tor  0.4.7.0-alpha-dev
order.c
Go to the documentation of this file.
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)
#define IMPLEMENT_ORDER_FUNC(funcname, elt_t)
Definition: order.c:22
Header for order.c.
Macros to manage assertions, fatal and non-fatal.