Reduced number of realloc calls bs_list does

1 files changed, 73 insertions, 25 deletions

diff --git a/toxcore/list.c b/toxcore/list.c
index c513afab..b380f0e7 100644
--- a/toxcore/list.c
+++ b/toxcore/list.c
@@ -63,7 +63,7 @@ static int find(const BS_LIST *list, const void *data)
     //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);
+        int r = memcmp(data, list->data + list->element_size * i, list->element_size);
 
         if (r == 0) {
             return i;
@@ -105,14 +105,52 @@ static int find(const BS_LIST *list, const void *data)
     }
 }
 
+/* Resized the list list
+ *
+ * return value:
+ *  1 : success
+ *  0 : failure
+ */
+static int resize(BS_LIST *list, uint32_t new_size)
+{
+    void *p;
+
+    p = realloc(list->data, list->element_size * new_size);
+
+    if (!p) {
+        return 0;
+    } else {
+        list->data = p;
+    }
+
+    p = realloc(list->ids, sizeof(int) * new_size);
 
-void bs_list_init(BS_LIST *list, uint32_t element_size)
+    if (!p) {
+        return 0;
+    } else {
+        list->ids = p;
+    }
+
+    return 1;
+}
+
+
+int bs_list_init(BS_LIST *list, uint32_t element_size, uint32_t initial_capacity)
 {
     //set initial values
     list->n = 0;
-    list->size = element_size;
-    list->data = NULL;
-    list->ids = NULL;
+    list->element_size = element_size;
+    if (initial_capacity == 0) {
+        list->data = NULL;
+        list->ids = NULL;
+    } else {
+        if (!resize(list, initial_capacity)) {
+            return 0;
+        }
+    }
+    list->capacity = initial_capacity;
+
+    return 1;
 }
 
 void bs_list_free(BS_LIST *list)
@@ -147,28 +185,19 @@ int bs_list_add(BS_LIST *list, const void *data, int id)
 
     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;
+    //increase the size of the arrays if needed
+    if (list->n == list->capacity) {
+        // 1.5 * n + 1
+        const uint32_t new_capacity = list->n + list->n/2 + 1;
+        if (!resize(list, new_capacity)) {
+            return 0;
+        }
+        list->capacity = new_capacity;
     }
 
     //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);
+    memmove(list->data + (i + 1) * list->element_size, list->data + i * list->element_size, (list->n - i) * list->element_size);
+    memcpy(list->data + i * list->element_size, data, list->element_size);
 
     //insert id to id array
     memmove(&list->ids[i + 1], &list->ids[i], (list->n - i) * sizeof(int));
@@ -193,10 +222,29 @@ int bs_list_remove(BS_LIST *list, const void *data, int id)
         return 0;
     }
 
+    //decrease the size of the arrays if needed
+    if (list->n < list->capacity/2) {
+        const uint32_t new_capacity = list->capacity/2;
+        if (!resize(list, new_capacity)) {
+            return 0;
+        }
+        list->capacity = new_capacity;
+    }
+
     list->n--;
 
-    memmove(list->data + i * list->size, list->data + (i + 1) * list->size, (list->n - i) * list->size);
+    memmove(list->data + i * list->element_size, list->data + (i + 1) * list->element_size, (list->n - i) * list->element_size);
     memmove(&list->ids[i], &list->ids[i + 1], (list->n - i) * sizeof(int));
 
     return 1;
 }
+
+int bs_list_trim(BS_LIST *list)
+{
+    if (!resize(list, list->n)) {
+        return 0;
+    }
+
+    list->capacity = list->n;
+    return 1;
+}