r14448@Kushana: nickm | 2007-09-17 14:26:56 -0400

 Unify all of the divergent median/nth-percentile code in container.[ch]


svn:r11457

2 files changed, 61 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)
+
diff --git a/src/common/container.h b/src/common/container.h
index 668befdd6e..1f58b30557 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -310,5 +310,34 @@ bitarray_is_set(bitarray_t *b, int bit)
   return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
 }
 
+/* These functions, given an <b>array</b> of <b>n_elements</b>, return the
+ * <b>nth</b> lowest element. <b>nth</b>=0 gives the lowest element;
+ * <b>n_elements</b>-1 gives the highest; and (<b>n_elements</b>-1) / 2 gives
+ * the median.  As a side effect, the elements of <b>array</b> are sorted. */
+int find_nth_int(int *array, int n_elements, int nth);
+time_t find_nth_time(time_t *array, int n_elements, int nth);
+double find_nth_double(double *array, int n_elements, int nth);
+uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth);
+static INLINE int
+median_int(int *array, int n_elements)
+{
+  return find_nth_int(array, n_elements, (n_elements-1)/2);
+}
+static INLINE time_t
+median_time(time_t *array, int n_elements)
+{
+  return find_nth_time(array, n_elements, (n_elements-1)/2);
+}
+static INLINE double
+median_double(double *array, int n_elements)
+{
+  return find_nth_double(array, n_elements, (n_elements-1)/2);
+}
+static INLINE uint32_t
+median_uint32(uint32_t *array, int n_elements)
+{
+  return find_nth_uint32(array, n_elements, (n_elements-1)/2);
+}
+
 #endif