6 files changed, 156 insertions, 58 deletions

diff --git a/core/CMakeLists.txt b/core/CMakeLists.txt
index eacb772c..55a41912 100644
--- a/core/CMakeLists.txt
+++ b/core/CMakeLists.txt
@@ -8,7 +8,9 @@ set(core_sources
         net_crypto.c
         friend_requests.c
         LAN_discovery.c
-        Messenger.c)
+        Messenger.c
+        util.c
+        ping.c)
 
 if(SHARED_TOXCORE)
         add_library(toxcore SHARED ${core_sources})
diff --git a/core/DHT.c b/core/DHT.c
index f6c48a6d..f0b32df5 100644
--- a/core/DHT.c
+++ b/core/DHT.c
@@ -24,6 +24,7 @@
 /*----------------------------------------------------------------------------------*/
 
 #include "DHT.h"
+#include "ping.h"
 
 /* maximum number of clients stored per friend. */
 #define MAX_FRIEND_CLIENTS 8
@@ -109,7 +110,6 @@ uint8_t             self_secret_key[crypto_box_SECRETKEYBYTES];
 static Client_data  close_clientlist[LCLIENT_LIST];
 static Friend *     friends_list;
 static uint16_t     num_friends;
-static Pinged       pings[LPING_ARRAY];
 static Pinged       send_nodes[LSEND_NODES_ARRAY];
 
 /*----------------------------------------------------------------------------------*/
@@ -426,35 +426,6 @@ static void returnedip_ports(IP_Port ip_port, uint8_t * client_id, uint8_t * nod
     }
 }
 
-/* check if we are currently pinging an ip_port and/or a ping_id variables with
- * values of zero will not be checked. If we are already, return 1 else return 0
- *
- * TODO: optimize this 
- */
-static int is_pinging(IP_Port ip_port, uint64_t ping_id)
-{
-    uint32_t i;
-    uint8_t pinging;
-    uint64_t temp_time = unix_time();
-
-    for (i = 0; i < LPING_ARRAY; ++i ) {
-        if (!is_timeout(temp_time, pings[i].timestamp, PING_TIMEOUT)) {
-            pinging = 0;
-
-            if (ip_port.ip.i != 0 && ipport_equal(pings[i].ip_port, ip_port))
-                    ++pinging;
-
-            if (ping_id != 0 && pings[i].ping_id == ping_id)
-                ++pinging;
-
-            if (pinging == ((ping_id != 0) + (ip_port.ip.i != 0)))
-                return 1;
-        }
-    }
-
-    return 0;
-}
-
 /* Same as last function but for get_node requests. */
 static int is_gettingnodes(IP_Port ip_port, uint64_t ping_id)
 {
@@ -480,32 +451,6 @@ static int is_gettingnodes(IP_Port ip_port, uint64_t ping_id)
     return 0;
 }
 
-/* Add a new ping request to the list of ping requests
- * returns the ping_id to put in the ping request
- * returns 0 if problem.
- *
- * TODO: optimize this
- */
-static uint64_t add_pinging(IP_Port ip_port)
-{
-    uint32_t i, j;
-    uint64_t ping_id = ((uint64_t)random_int() << 32) + random_int();
-    uint64_t temp_time = unix_time();
-
-    for(i = 0; i < PING_TIMEOUT; ++i ) {
-        for(j = 0; j < LPING_ARRAY; ++j ) {
-            if(is_timeout(temp_time, pings[j].timestamp, PING_TIMEOUT - i)) {
-                pings[j].timestamp = temp_time;
-                pings[j].ip_port = ip_port;
-                pings[j].ping_id = ping_id;
-                return ping_id;
-            }
-        }
-    }
-
-    return 0;
-}
-
 /* Same but for get node requests */
 static uint64_t add_gettingnodes(IP_Port ip_port)
 {
@@ -536,7 +481,7 @@ static int pingreq(IP_Port ip_port, uint8_t * public_key)
     if(id_equal(public_key, self_public_key) || is_pinging(ip_port, 0))
         return 1;
 
-    uint64_t ping_id = add_pinging(ip_port);
+    uint64_t ping_id = add_ping(ip_port);
     if(ping_id == 0)
         return 1;
 
@@ -1301,6 +1246,8 @@ void DHT_save(uint8_t * data)
  */
 int DHT_load(uint8_t * data, uint32_t size)
 {
+    init_ping();
+
     if(size < sizeof(close_clientlist))
         return -1;
 
diff --git a/core/ping.c b/core/ping.c
new file mode 100644
index 00000000..8a7d534f
--- /dev/null
+++ b/core/ping.c
@@ -0,0 +1,95 @@
+/*
+ * ping.c -- Buffered pinging using cyclic arrays.
+ *
+ * This file is donated to the Tox Project.
+ * Copyright 2013  plutooo
+ */
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#include "network.h"
+#include "util.h"
+
+#define PING_NUM_MAX 256
+#define PING_TIMEOUT 5 // 5s
+
+typedef struct {
+  IP_Port  ipp;
+  uint64_t id;
+  uint64_t timestamp;
+} pinged_t;
+
+static pinged_t pings[PING_NUM_MAX];
+static size_t   num_pings;
+static size_t   pos_pings;
+
+
+void init_ping() {
+  num_pings = 0;
+  pos_pings = 0;
+}
+
+static bool is_timeout(uint64_t time) {
+  return (time + PING_TIMEOUT) < now();
+}
+
+static void remove_timeouts() { // O(n)
+  size_t i, id;
+  size_t new_pos = pos_pings;
+  size_t new_num = num_pings;
+
+  // Loop through buffer, oldest first
+  for(i=0; i<num_pings; i++) {
+    id = (pos_pings + i) % PING_NUM_MAX;
+
+    if(is_timeout(pings[id].timestamp)) {
+      new_pos++;
+      new_num--;
+    }
+    // Break here because list is sorted.
+    else
+      break;
+  }
+
+  num_pings = new_num;
+  pos_pings = new_pos % PING_NUM_MAX;
+}
+
+uint64_t add_ping(IP_Port ipp) { // O(n)
+  size_t p;
+  
+  remove_timeouts();
+
+  // Remove oldest ping if full buffer
+  if(num_pings == PING_NUM_MAX) {
+    num_pings--;
+    pos_pings = (pos_pings + 1) % PING_NUM_MAX;
+  }
+
+  // Insert new ping at end of list
+  p = (pos_pings + num_pings) % PING_NUM_MAX;
+
+  pings[p].ipp       = ipp;
+  pings[p].timestamp = now();
+  pings[p].id        = random_64b();
+
+  num_pings++;
+  return pings[p].id;
+}
+
+bool is_pinging(IP_Port ipp, uint64_t ping_id) { // O(n)
+  size_t i, id;
+
+  remove_timeouts();
+
+  for(i=0; i<num_pings; i++) {
+    id = (pos_pings + i) % PING_NUM_MAX;
+
+    if(ipp_eq(pings[id].ipp, ipp) && pings[id].id == ping_id) {
+      return true;
+    }
+  }
+
+  return false;
+}
diff --git a/core/ping.h b/core/ping.h
new file mode 100644
index 00000000..1d23df97
--- /dev/null
+++ b/core/ping.h
@@ -0,0 +1,13 @@
+/*
+ * ping.h -- Buffered pinging using cyclic arrays.
+ *
+ * This file is donated to the Tox Project.
+ * Copyright 2013  plutooo
+ */
+
+#include <stdbool.h>
+
+void init_ping();
+uint64_t add_ping(IP_Port ipp);
+bool is_pinging(IP_Port ipp, uint64_t ping_id);
+
diff --git a/core/util.c b/core/util.c
new file mode 100644
index 00000000..6b40dad7
--- /dev/null
+++ b/core/util.c
@@ -0,0 +1,31 @@
+/*
+ * util.c -- Utilities.
+ *
+ * This file is donated to the Tox Project.
+ * Copyright 2013  plutooo
+ */
+
+#include <time.h>
+#include <stdint.h>
+#include <stdbool.h>
+
+#include "network.h"
+
+uint64_t now() {
+  return time(NULL);
+}
+
+uint64_t random_64b() {
+  uint64_t r;
+
+  // This is probably not random enough?
+  r = random_int();
+  r <<= 32;
+  r |= random_int();
+
+  return r;
+}
+
+bool ipp_eq(IP_Port a, IP_Port b) {
+  return (a.ip.i == b.ip.i) && (a.port == b.port);
+}
diff --git a/core/util.h b/core/util.h
new file mode 100644
index 00000000..aab2ead9
--- /dev/null
+++ b/core/util.h
@@ -0,0 +1,10 @@
+/*
+ * util.h -- Utilities.
+ *
+ * This file is donated to the Tox Project.
+ * Copyright 2013  plutooo
+ */
+
+uint64_t now();
+uint64_t random_64b();
+bool ipp_eq(IP_Port a, IP_Port b);