diff options
| author | Nick Mathewson <nickm@torproject.org> | 2007-09-17 18:27:49 +0000 |
|---|---|---|
| committer | Nick Mathewson <nickm@torproject.org> | 2007-09-17 18:27:49 +0000 |
| commit | 8c139678038832cf982ab2ef3a25679ff677c491 (patch) | |
| tree | 67036be82e4014a736d44aa36fb9d794ddb54985 /src/common/container.c | |
| parent | 93d4ad974318f48b4def653f94d7088bdc6b4e09 (diff) | |
| download | tor-8c139678038832cf982ab2ef3a25679ff677c491.tar.gz tor-8c139678038832cf982ab2ef3a25679ff677c491.zip | |
r14448@Kushana: nickm | 2007-09-17 14:26:56 -0400
Unify all of the divergent median/nth-percentile code in container.[ch]
svn:r11457
Diffstat (limited to 'src/common/container.c')
| -rw-r--r-- | src/common/container.c | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/src/common/container.c b/src/common/container.c index a148af2663..d8b910738c 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -1133,3 +1133,35 @@ digestmap_size(const digestmap_t *map) return HT_SIZE(&map->head); } +/** declare a function called <b>funcname</b> that acts as a find_nth_XXX + * function for an array of type <b>elt_t</b>*. + * + * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding + * the nth element of a list can be done in O(n). Then again, this + * implementation is not in critical path, and it is obviously correct. */ +#define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ + static int \ + _cmp_ ## elt_t(const void *_a, const void *_b) \ + { \ + const elt_t *a = _a, *b = _b; \ + if (*a<*b) \ + return -1; \ + else if (*a>*b) \ + return 1; \ + else \ + return 0; \ + } \ + elt_t \ + funcname(elt_t *array, int n_elements, int nth) \ + { \ + tor_assert(nth >= 0); \ + tor_assert(nth < n_elements); \ + qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ + return array[nth]; \ + } + +IMPLEMENT_ORDER_FUNC(find_nth_int, int) +IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) +IMPLEMENT_ORDER_FUNC(find_nth_double, double) +IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) + |