3 files changed, 72 insertions, 21 deletions

diff --git a/toxcore/DHT.c b/toxcore/DHT.c
index 529456a2..307b1e33 100644
--- a/toxcore/DHT.c
+++ b/toxcore/DHT.c
@@ -25,6 +25,7 @@
 
 #include "DHT.h"
 #include "ping.h"
+#include "misc_tools.h"
 
 /* The number of seconds for a non responsive node to become bad. */
 #define BAD_NODE_TIMEOUT 70
@@ -86,6 +87,17 @@ static int id_closest(uint8_t *id, uint8_t *id1, uint8_t *id2)
     return 0;
 }
 
+/* Turns the result of id_closest into something quick_sort can use.
+ * Assumes p1->c1 == p2->c1.
+ */
+static int client_id_cmp(ClientPair p1, ClientPair p2)
+{
+    int c = id_closest(p1.c1.client_id, p1.c2.client_id, p2.c2.client_id);
+    if (c == 2)
+        return -1;
+    return c;
+}
+
 static int ipport_equal(IP_Port a, IP_Port b)
 {
     return (a.ip.uint32 == b.ip.uint32) && (a.port == b.port);
@@ -277,33 +289,28 @@ static int replace_bad(    Client_data    *list,
 
     return 1;
 }
-/* Sort the list. It will be sorted from furthest to closest.
-  TODO: this is innefficient and needs to be optimized. */
+
+/*Sort the list. It will be sorted from furthest to closest. 
+ * Turns list into data that quick sort can use and reverts it back.
+ */
 static void sort_list(Client_data *list, uint32_t length, uint8_t *comp_client_id)
 {
-    if (length == 0)
-        return;
-
-    uint32_t i, count;
-
-    while (1) {
-        count = 0;
-
-        for (i = 0; i < (length - 1); ++i) {
-            if (id_closest(comp_client_id, list[i].client_id, list[i + 1].client_id) == 1) {
-                Client_data temp = list[i + 1];
-                list[i + 1] = list[i];
-                list[i] = temp;
-                ++count;
-            }
-        }
+    Client_data cd;
+    ClientPair pairs[length];
+    uint32_t i;
 
-        if (count == 0)
-            return;
+    /* Create the quicksort function. See misc_tools.h for the definition. */
+    make_quick_sort(ClientPair); 
+    memcpy(cd.client_id, comp_client_id, CLIENT_ID_SIZE);
+    for (i = 0; i < length; ++i) {
+        pairs[i].c1 = cd;
+        pairs[i].c2 = list[i];
     }
+    ClientPair_quick_sort(pairs, length, client_id_cmp);
+    for (i = 0; i < length; ++i)
+        list[i] = pairs[i].c2;
 }
 
-
 /* Replace the first good node that is further to the comp_client_id than that of the client_id in the list */
 static int replace_good(   Client_data    *list,
                            uint32_t        length,
diff --git a/toxcore/DHT.h b/toxcore/DHT.h
index b53801b5..d0afda35 100644
--- a/toxcore/DHT.h
+++ b/toxcore/DHT.h
@@ -55,6 +55,12 @@ typedef struct {
     uint64_t    ret_timestamp;
 } Client_data;
 
+/* Used in the comparison function for sorting lists of Client_data. */
+typedef struct {
+    Client_data c1;
+    Client_data c2;
+} ClientPair;
+
 /*----------------------------------------------------------------------------------*/
 
 typedef struct {
diff --git a/toxcore/misc_tools.h b/toxcore/misc_tools.h
index 5f4cfea4..4d62a856 100644
--- a/toxcore/misc_tools.h
+++ b/toxcore/misc_tools.h
@@ -186,4 +186,42 @@ static inline void tox_array_pop(tox_array *arr, uint32_t num)
     type *tmp_name = &tox_array_get(arr, 0, type); uint32_t tmp_name ## _i = 0; \
     for (; tmp_name ## _i < (arr)->len; tmp_name = &tox_array_get(arr, ++ tmp_name ## _i, type))
 
+/****************************Algorithms***************************
+ * Macro/generic definitions for useful algorithms
+ *****************************************************************/
+
+/* Creates a new quick_sort implementation for arrays of the specified type.
+ * For a type T (eg: int, char), creates a function named T_quick_sort.
+ *
+ * Quick Sort: Complexity O(nlogn)
+ * arr   - the array to sort
+ * n     - the sort index (should be called with n = length(arr))
+ * cmpfn - a function that compares two values of type type. 
+ *         Must return -1, 0, 1 for a < b, a == b, and a > b respectively.
+ */
+#define make_quick_sort(type) \
+void type##_quick_sort(type *arr, int n, int (*cmpfn)(type, type)) \
+{ \
+    if ((n) < 2) \
+        return; \
+    type _p_ = (arr)[(n) / 2]; \
+    type *_l_ = (arr); \
+    type *_r_ = (arr) + n - 1; \
+    while (_l_ <= _r_) { \
+        if (cmpfn(*_l_, _p_) == -1) { \
+            ++_l_; \
+            continue; \
+        } \
+        if (cmpfn(*_r_, _p_) == 1) { \
+            --_r_; \
+            continue; \
+        } \
+        type _t_ = *_l_; \
+        *_l_++ = *_r_; \
+        *_r_-- = _t_; \
+    } \
+    type##_quick_sort((arr), _r_ - (arr) + 1, cmpfn); \
+    type##_quick_sort(_l_, (arr) + n - _l_, cmpfn); \
+}
+
 #endif // MISC_TOOLS_H