diff options
author | redwire <redwire@riseup.net> | 2013-08-30 18:10:00 -0230 |
---|---|---|
committer | redwire <redwire@riseup.net> | 2013-08-30 18:10:00 -0230 |
commit | 4247eec9698dce1bf82d17e4713a54bad080baca (patch) | |
tree | 054ddc4fb6d5acab57816fcc49b0be2a21611c53 /toxcore/DHT.c | |
parent | dcabd6421c424b025d093812263e02dcc775a210 (diff) |
Wrote a quicksort macro and modified sort_list to use it
Diffstat (limited to 'toxcore/DHT.c')
-rw-r--r-- | toxcore/DHT.c | 49 |
1 files changed, 28 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 @@ | |||
25 | 25 | ||
26 | #include "DHT.h" | 26 | #include "DHT.h" |
27 | #include "ping.h" | 27 | #include "ping.h" |
28 | #include "misc_tools.h" | ||
28 | 29 | ||
29 | /* The number of seconds for a non responsive node to become bad. */ | 30 | /* The number of seconds for a non responsive node to become bad. */ |
30 | #define BAD_NODE_TIMEOUT 70 | 31 | #define BAD_NODE_TIMEOUT 70 |
@@ -86,6 +87,17 @@ static int id_closest(uint8_t *id, uint8_t *id1, uint8_t *id2) | |||
86 | return 0; | 87 | return 0; |
87 | } | 88 | } |
88 | 89 | ||
90 | /* Turns the result of id_closest into something quick_sort can use. | ||
91 | * Assumes p1->c1 == p2->c1. | ||
92 | */ | ||
93 | static int client_id_cmp(ClientPair p1, ClientPair p2) | ||
94 | { | ||
95 | int c = id_closest(p1.c1.client_id, p1.c2.client_id, p2.c2.client_id); | ||
96 | if (c == 2) | ||
97 | return -1; | ||
98 | return c; | ||
99 | } | ||
100 | |||
89 | static int ipport_equal(IP_Port a, IP_Port b) | 101 | static int ipport_equal(IP_Port a, IP_Port b) |
90 | { | 102 | { |
91 | return (a.ip.uint32 == b.ip.uint32) && (a.port == b.port); | 103 | return (a.ip.uint32 == b.ip.uint32) && (a.port == b.port); |
@@ -277,33 +289,28 @@ static int replace_bad( Client_data *list, | |||
277 | 289 | ||
278 | return 1; | 290 | return 1; |
279 | } | 291 | } |
280 | /* Sort the list. It will be sorted from furthest to closest. | 292 | |
281 | TODO: this is innefficient and needs to be optimized. */ | 293 | /*Sort the list. It will be sorted from furthest to closest. |
294 | * Turns list into data that quick sort can use and reverts it back. | ||
295 | */ | ||
282 | static void sort_list(Client_data *list, uint32_t length, uint8_t *comp_client_id) | 296 | static void sort_list(Client_data *list, uint32_t length, uint8_t *comp_client_id) |
283 | { | 297 | { |
284 | if (length == 0) | 298 | Client_data cd; |
285 | return; | 299 | ClientPair pairs[length]; |
286 | 300 | uint32_t i; | |
287 | uint32_t i, count; | ||
288 | |||
289 | while (1) { | ||
290 | count = 0; | ||
291 | |||
292 | for (i = 0; i < (length - 1); ++i) { | ||
293 | if (id_closest(comp_client_id, list[i].client_id, list[i + 1].client_id) == 1) { | ||
294 | Client_data temp = list[i + 1]; | ||
295 | list[i + 1] = list[i]; | ||
296 | list[i] = temp; | ||
297 | ++count; | ||
298 | } | ||
299 | } | ||
300 | 301 | ||
301 | if (count == 0) | 302 | /* Create the quicksort function. See misc_tools.h for the definition. */ |
302 | return; | 303 | make_quick_sort(ClientPair); |
304 | memcpy(cd.client_id, comp_client_id, CLIENT_ID_SIZE); | ||
305 | for (i = 0; i < length; ++i) { | ||
306 | pairs[i].c1 = cd; | ||
307 | pairs[i].c2 = list[i]; | ||
303 | } | 308 | } |
309 | ClientPair_quick_sort(pairs, length, client_id_cmp); | ||
310 | for (i = 0; i < length; ++i) | ||
311 | list[i] = pairs[i].c2; | ||
304 | } | 312 | } |
305 | 313 | ||
306 | |||
307 | /* Replace the first good node that is further to the comp_client_id than that of the client_id in the list */ | 314 | /* Replace the first good node that is further to the comp_client_id than that of the client_id in the list */ |
308 | static int replace_good( Client_data *list, | 315 | static int replace_good( Client_data *list, |
309 | uint32_t length, | 316 | uint32_t length, |