order.c File Reference

Functions for finding the n'th element of an array. More...

#include <stdlib.h>
#include "lib/container/order.h"
#include "lib/log/util_bug.h"

Go to the source code of this file.

Macros
#define	IMPLEMENT_ORDER_FUNC(funcname, elt_t)

Detailed Description

Functions for finding the n'th element of an array.

Definition in file order.c.

Macro Definition Documentation

IMPLEMENT_ORDER_FUNC

#define IMPLEMENT_ORDER_FUNC	(		funcname,
			elt_t
	)

Value:

  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];                                          \
  }

Declare a function called funcname that acts as a find_nth_FOO function for an array of type elt_t*.

NOTE: The implementation kind of sucks: It's O(n log n), whereas finding the kth element of an n-element list can be done in O(n). Then again, this implementation is not in critical path, and it is obviously correct.

Definition at line 22 of file order.c.