Tor
0.4.6.0-alpha-dev
lib
container
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-2020, 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
)
util_bug.h
Macros to manage assertions, fatal and non-fatal.
IMPLEMENT_ORDER_FUNC
#define IMPLEMENT_ORDER_FUNC(funcname, elt_t)
Definition:
order.c:22
order.h
Header for order.c.
Generated by
1.8.20