Line data    Source code

       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         186 : IMPLEMENT_ORDER_FUNC(find_nth_int, int)
      44         251 : IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
      45          50 : IMPLEMENT_ORDER_FUNC(find_nth_double, double)
      46         269 : IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
      47         279 : IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
      48           9 : IMPLEMENT_ORDER_FUNC(find_nth_long, long)