Split container.c based on container types, and minimize includes

Minimizing includes revealed other places includes were necessary.

1 files changed, 51 insertions, 0 deletions

diff --git a/src/lib/container/order.c b/src/lib/container/order.c
new file mode 100644
index 0000000000..599f833007
--- /dev/null
+++ b/src/lib/container/order.c
@@ -0,0 +1,51 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file container.c
+ * \brief Implements a smartlist (a resizable array) along
+ * with helper functions to use smartlists.  Also includes
+ * hash table implementations of a string-to-void* map, and of
+ * a digest-to-void* map.
+ **/
+
+#include <stdlib.h>
+
+#include "lib/container/order.h"
+#include "common/util_bug.h"
+
+/** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
+ * 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 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. */
+#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)
+IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
+IMPLEMENT_ORDER_FUNC(find_nth_long, long)