5 files changed, 286 insertions, 9 deletions

diff --git a/toxcore/Makefile.inc b/toxcore/Makefile.inc
index 7c1cf66e..4278457a 100644
--- a/toxcore/Makefile.inc
+++ b/toxcore/Makefile.inc
@@ -41,6 +41,8 @@ libtoxcore_la_SOURCES = ../toxcore/DHT.h \
                         ../toxcore/TCP_client.c \
                         ../toxcore/TCP_server.h \
                         ../toxcore/TCP_server.c \
+                        ../toxcore/list.c \
+                        ../toxcore/list.h \
                         ../toxcore/misc_tools.h
 
 libtoxcore_la_CFLAGS =  -I$(top_srcdir) \
diff --git a/toxcore/TCP_server.c b/toxcore/TCP_server.c
index ceab5f10..a47f74e2 100644
--- a/toxcore/TCP_server.c
+++ b/toxcore/TCP_server.c
@@ -99,15 +99,7 @@ static int realloc_connection(TCP_Server *TCP_server, uint32_t num)
  */
 static int get_TCP_connection_index(TCP_Server *TCP_server, uint8_t *public_key)
 {
-    //TODO optimize this function.
-    uint32_t i;
-
-    for (i = 0; i < TCP_server->size_accepted_connections; ++i) {
-        if (memcmp(TCP_server->accepted_connection_array[i].public_key, public_key, crypto_box_PUBLICKEYBYTES) == 0)
-            return i;
-    }
-
-    return -1;
+    return list_find(&TCP_server->accepted_key_list, public_key);
 }
 
 
@@ -148,12 +140,16 @@ static int add_accepted(TCP_Server *TCP_server, TCP_Secure_Connection *con)
         return -1;
     }
 
+    if (!list_add(&TCP_server->accepted_key_list, con->public_key, index))
+        return -1;
+
     memcpy(&TCP_server->accepted_connection_array[index], con, sizeof(TCP_Secure_Connection));
     TCP_server->accepted_connection_array[index].status = TCP_STATUS_CONFIRMED;
     ++TCP_server->num_accepted_connections;
     TCP_server->accepted_connection_array[index].identifier = ++TCP_server->counter;
     TCP_server->accepted_connection_array[index].last_pinged = unix_time();
     TCP_server->accepted_connection_array[index].ping_id = 0;
+
     return index;
 }
 
@@ -170,6 +166,9 @@ static int del_accepted(TCP_Server *TCP_server, int index)
     if (TCP_server->accepted_connection_array[index].status == TCP_STATUS_NO_STATUS)
         return -1;
 
+    if (!list_remove(&TCP_server->accepted_key_list, TCP_server->accepted_connection_array[index].public_key, index))
+        return -1;
+
     memset(&TCP_server->accepted_connection_array[index], 0, sizeof(TCP_Secure_Connection));
     --TCP_server->num_accepted_connections;
 
@@ -888,6 +887,9 @@ TCP_Server *new_TCP_server(uint8_t ipv6_enabled, uint16_t num_sockets, uint16_t
 
     memcpy(temp->public_key, public_key, crypto_box_PUBLICKEYBYTES);
     memcpy(temp->secret_key, secret_key, crypto_box_SECRETKEYBYTES);
+
+    list_init(&temp->accepted_key_list, crypto_box_PUBLICKEYBYTES);
+
     return temp;
 }
 
@@ -1040,6 +1042,8 @@ void kill_TCP_server(TCP_Server *TCP_server)
         set_callback_handle_recv_1(TCP_server->onion, NULL, NULL);
     }
 
+    list_free(&TCP_server->accepted_key_list);
+
     free(TCP_server->socks_listening);
     free(TCP_server);
 }
diff --git a/toxcore/TCP_server.h b/toxcore/TCP_server.h
index fc8c234b..7fd4d976 100644
--- a/toxcore/TCP_server.h
+++ b/toxcore/TCP_server.h
@@ -25,6 +25,7 @@
 
 #include "crypto_core.h"
 #include "onion.h"
+#include "list.h"
 
 #if defined(_WIN32) || defined(__WIN32__) || defined(WIN32) || defined(__MACH__)
 #define MSG_NOSIGNAL 0
@@ -110,6 +111,8 @@ typedef struct {
     uint32_t num_accepted_connections;
 
     uint64_t counter;
+
+    LIST accepted_key_list;
 } TCP_Server;
 
 /* Create new TCP server instance.
diff --git a/toxcore/list.c b/toxcore/list.c
new file mode 100644
index 00000000..2904d15b
--- /dev/null
+++ b/toxcore/list.c
@@ -0,0 +1,198 @@
+/* list.h
+ *
+ * Simple struct with functions to create a list which associates ids with data
+ * -Allows for finding ids associated with data such as IPs or public keys in a short time
+ * -Should only be used if there are relatively few add/remove calls to the list
+ *
+ *  Copyright (C) 2014 Tox project All Rights Reserved.
+ *
+ *  This file is part of Tox.
+ *
+ *  Tox is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation, either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  Tox is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with Tox.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "list.h"
+
+/* Basically, the elements in the list are placed in order so that they can be searched for easily
+ * -each element is seen as a big-endian integer when ordering them
+ * -the ids array is maintained so that each id always matches
+ * -the search algorithm cuts down the time to find the id associated with a piece of data
+ *   at the cost of slow add/remove functions for large lists
+ * -Starts at 1/2 of the array, compares the element in the array with the data,
+ *   then moves +/- 1/4 of the array depending on whether the value is greater or lower,
+ *   then +- 1/8, etc, until the value is matched or its position where it should be in the array is found
+ * -some considerations since the array size is never perfect
+ */
+
+#define INDEX(i) (~i)
+
+/* Find data in list
+ *
+ * return value:
+ *  >= 0 : id associated with data
+ *  < 0  : no match, returns index (return value is INDEX(index)) where
+ *         the data should be inserted
+ */
+static int find(LIST *list, void *data)
+{
+    //should work well, but could be improved
+    if (list->n == 0) {
+        return INDEX(0);
+    }
+
+    uint32_t i = list->n / 2; //current position in the array
+    uint32_t delta = i / 2;   //how much we move in the array
+
+    int d = -1; //used to determine if closest match is found
+    //closest match is found if we move back to where we have already been
+
+    while (1) {
+        int r = memcmp(data, list->data + list->size * i, list->size);
+
+        if (r == 0) {
+            return list->ids[i];
+        }
+
+        if (r > 0) {
+            //data is greater
+            //move down
+            i += delta;
+
+            if (d == 0 || i == list->n) {
+                //reached bottom of list, or closest match
+                return INDEX(i);
+            }
+
+            delta = (delta) / 2;
+
+            if (delta == 0) {
+                delta = 1;
+                d = 1;
+            }
+        } else {
+            //data is smaller
+            if (d == 1 || i == 0) {
+                //reached top or list or closest match
+                return INDEX(i);
+            }
+
+            //move up
+            i -= delta;
+
+            delta = (delta) / 2;
+
+            if (delta == 0) {
+                delta = 1;
+                d = 0;
+            }
+        }
+    }
+}
+
+
+void list_init(LIST *list, uint32_t element_size)
+{
+    //set initial values
+    list->n = 0;
+    list->size = element_size;
+    list->data = NULL;
+    list->ids = NULL;
+}
+
+void list_free(LIST *list)
+{
+    //free both arrays
+    free(list->data);
+    free(list->ids);
+}
+
+int list_find(LIST *list, void *data)
+{
+    int r = find(list, data);
+
+    //return only -1 and positive values
+    if (r < 0) {
+        r = -1;
+    }
+
+    return r;
+}
+
+int list_add(LIST *list, void *data, int id)
+{
+    //find where the new element should be inserted
+    //see: return value of find()
+    int i = find(list, data);
+
+    if (i >= 0) {
+        //already in list
+        return 0;
+    }
+
+    i = ~i;
+
+    //increase the size of the arrays by one
+    void *p;
+
+    p = realloc(list->data, list->size * (list->n + 1));
+
+    if (!p) {
+        return 0;
+    } else {
+        list->data = p;
+    }
+
+    p = realloc(list->ids, sizeof(int) * (list->n + 1));
+
+    if (!p) {
+        return 0;
+    } else {
+        list->ids = p;
+    }
+
+    //insert data to element array
+    memmove(list->data + (i + 1) * list->size, list->data + i * list->size, (list->n - i) * list->size);
+    memcpy(list->data + i * list->size, data, list->size);
+
+    //insert id to id array
+    memmove(&list->ids[i + 1], &list->ids[i], (list->n - i) * sizeof(int));
+    list->ids[i] = id;
+
+    //increase n
+    list->n++;
+
+    return 1;
+}
+
+int list_remove(LIST *list, void *data, int id)
+{
+    int i = find(list, data);
+
+    if (i < 0) {
+        return 0;
+    }
+
+    if (list->ids[i] != id) {
+        //this should never happen
+        return 0;
+    }
+
+    list->n--;
+
+    memmove(list->data + i * list->size, list->data + (i + 1) * list->size, (list->n - i) * list->size);
+    memmove(&list->ids[i], &list->ids[i + 1], (list->n - i) * sizeof(int));
+
+    return 1;
+}
diff --git a/toxcore/list.h b/toxcore/list.h
new file mode 100644
index 00000000..299c010d
--- /dev/null
+++ b/toxcore/list.h
@@ -0,0 +1,70 @@
+/* list.h
+ *
+ * Simple struct with functions to create a list which associates ids with data
+ * -Allows for finding ids associated with data such as IPs or public keys in a short time
+ * -Should only be used if there are relatively few add/remove calls to the list
+ *
+ *  Copyright (C) 2014 Tox project All Rights Reserved.
+ *
+ *  This file is part of Tox.
+ *
+ *  Tox is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation, either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  Tox is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with Tox.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#ifndef LIST_H
+#define LIST_H
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+typedef struct {
+    uint32_t n; //number of elements
+    uint32_t size; //size of the elements
+    void *data; //array of elements
+    int *ids; //array of element ids
+} LIST;
+
+/* Initialize a list, element_size is the size of the elements in the list */
+void list_init(LIST *list, uint32_t element_size);
+
+/* Free a list initiated with list_init */
+void list_free(LIST *list);
+
+/* Retrieve the id of an element in the list
+ *
+ * return value:
+ *  >= 0 : id associated with data
+ *  -1   : failure
+ */
+int list_find(LIST *list, void *data);
+
+/* Add an element with associated id to the list
+ *
+ * return value:
+ *  1 : success
+ *  0 : failure (data already in list)
+ */
+int list_add(LIST *list, void *data, int id);
+
+/* Remove element from the list
+ *
+ * return value:
+ *  1 : success
+ *  0 : failure (element not found or id does not match
+ */
+int list_remove(LIST *list, void *data, int id);
+
+#endif