diff options
author | irungentoo <irungentoo@gmail.com> | 2014-06-21 21:48:33 -0400 |
---|---|---|
committer | irungentoo <irungentoo@gmail.com> | 2014-06-21 21:48:33 -0400 |
commit | f3c09d1854adc4b9b7873216b6b5837f76575bba (patch) | |
tree | 9e1ae85bc4fe71495095f9e1dd65507cfb3253c6 /toxcore | |
parent | 74485a5cf5f7eb8e5bee735b3c093b4af5b6cef5 (diff) | |
parent | a32d270330a34e8188e7d6ac7770932bb9b9d161 (diff) |
Merge branch 'list-fix' of https://github.com/nurupo/InsertProjectNameHere
Diffstat (limited to 'toxcore')
-rw-r--r-- | toxcore/TCP_server.c | 2 | ||||
-rw-r--r-- | toxcore/list.c | 98 | ||||
-rw-r--r-- | toxcore/list.h | 21 | ||||
-rw-r--r-- | toxcore/net_crypto.c | 2 |
4 files changed, 93 insertions, 30 deletions
diff --git a/toxcore/TCP_server.c b/toxcore/TCP_server.c index 5652513e..578784d0 100644 --- a/toxcore/TCP_server.c +++ b/toxcore/TCP_server.c | |||
@@ -915,7 +915,7 @@ TCP_Server *new_TCP_server(uint8_t ipv6_enabled, uint16_t num_sockets, uint16_t | |||
915 | memcpy(temp->public_key, public_key, crypto_box_PUBLICKEYBYTES); | 915 | memcpy(temp->public_key, public_key, crypto_box_PUBLICKEYBYTES); |
916 | memcpy(temp->secret_key, secret_key, crypto_box_SECRETKEYBYTES); | 916 | memcpy(temp->secret_key, secret_key, crypto_box_SECRETKEYBYTES); |
917 | 917 | ||
918 | bs_list_init(&temp->accepted_key_list, crypto_box_PUBLICKEYBYTES); | 918 | bs_list_init(&temp->accepted_key_list, crypto_box_PUBLICKEYBYTES, 8); |
919 | 919 | ||
920 | return temp; | 920 | return temp; |
921 | } | 921 | } |
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) | |||
63 | //closest match is found if we move back to where we have already been | 63 | //closest match is found if we move back to where we have already been |
64 | 64 | ||
65 | while (1) { | 65 | while (1) { |
66 | int r = memcmp(data, list->data + list->size * i, list->size); | 66 | int r = memcmp(data, list->data + list->element_size * i, list->element_size); |
67 | 67 | ||
68 | if (r == 0) { | 68 | if (r == 0) { |
69 | return i; | 69 | return i; |
@@ -105,14 +105,52 @@ static int find(const BS_LIST *list, const void *data) | |||
105 | } | 105 | } |
106 | } | 106 | } |
107 | 107 | ||
108 | /* Resized the list list | ||
109 | * | ||
110 | * return value: | ||
111 | * 1 : success | ||
112 | * 0 : failure | ||
113 | */ | ||
114 | static int resize(BS_LIST *list, uint32_t new_size) | ||
115 | { | ||
116 | void *p; | ||
117 | |||
118 | p = realloc(list->data, list->element_size * new_size); | ||
119 | |||
120 | if (!p) { | ||
121 | return 0; | ||
122 | } else { | ||
123 | list->data = p; | ||
124 | } | ||
125 | |||
126 | p = realloc(list->ids, sizeof(int) * new_size); | ||
108 | 127 | ||
109 | void bs_list_init(BS_LIST *list, uint32_t element_size) | 128 | if (!p) { |
129 | return 0; | ||
130 | } else { | ||
131 | list->ids = p; | ||
132 | } | ||
133 | |||
134 | return 1; | ||
135 | } | ||
136 | |||
137 | |||
138 | int bs_list_init(BS_LIST *list, uint32_t element_size, uint32_t initial_capacity) | ||
110 | { | 139 | { |
111 | //set initial values | 140 | //set initial values |
112 | list->n = 0; | 141 | list->n = 0; |
113 | list->size = element_size; | 142 | list->element_size = element_size; |
114 | list->data = NULL; | 143 | if (initial_capacity == 0) { |
115 | list->ids = NULL; | 144 | list->data = NULL; |
145 | list->ids = NULL; | ||
146 | } else { | ||
147 | if (!resize(list, initial_capacity)) { | ||
148 | return 0; | ||
149 | } | ||
150 | } | ||
151 | list->capacity = initial_capacity; | ||
152 | |||
153 | return 1; | ||
116 | } | 154 | } |
117 | 155 | ||
118 | void bs_list_free(BS_LIST *list) | 156 | void bs_list_free(BS_LIST *list) |
@@ -147,28 +185,19 @@ int bs_list_add(BS_LIST *list, const void *data, int id) | |||
147 | 185 | ||
148 | i = ~i; | 186 | i = ~i; |
149 | 187 | ||
150 | //increase the size of the arrays by one | 188 | //increase the size of the arrays if needed |
151 | void *p; | 189 | if (list->n == list->capacity) { |
152 | 190 | // 1.5 * n + 1 | |
153 | p = realloc(list->data, list->size * (list->n + 1)); | 191 | const uint32_t new_capacity = list->n + list->n/2 + 1; |
154 | 192 | if (!resize(list, new_capacity)) { | |
155 | if (!p) { | 193 | return 0; |
156 | return 0; | 194 | } |
157 | } else { | 195 | list->capacity = new_capacity; |
158 | list->data = p; | ||
159 | } | ||
160 | |||
161 | p = realloc(list->ids, sizeof(int) * (list->n + 1)); | ||
162 | |||
163 | if (!p) { | ||
164 | return 0; | ||
165 | } else { | ||
166 | list->ids = p; | ||
167 | } | 196 | } |
168 | 197 | ||
169 | //insert data to element array | 198 | //insert data to element array |
170 | memmove(list->data + (i + 1) * list->size, list->data + i * list->size, (list->n - i) * list->size); | 199 | memmove(list->data + (i + 1) * list->element_size, list->data + i * list->element_size, (list->n - i) * list->element_size); |
171 | memcpy(list->data + i * list->size, data, list->size); | 200 | memcpy(list->data + i * list->element_size, data, list->element_size); |
172 | 201 | ||
173 | //insert id to id array | 202 | //insert id to id array |
174 | memmove(&list->ids[i + 1], &list->ids[i], (list->n - i) * sizeof(int)); | 203 | 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) | |||
193 | return 0; | 222 | return 0; |
194 | } | 223 | } |
195 | 224 | ||
225 | //decrease the size of the arrays if needed | ||
226 | if (list->n < list->capacity/2) { | ||
227 | const uint32_t new_capacity = list->capacity/2; | ||
228 | if (!resize(list, new_capacity)) { | ||
229 | return 0; | ||
230 | } | ||
231 | list->capacity = new_capacity; | ||
232 | } | ||
233 | |||
196 | list->n--; | 234 | list->n--; |
197 | 235 | ||
198 | memmove(list->data + i * list->size, list->data + (i + 1) * list->size, (list->n - i) * list->size); | 236 | memmove(list->data + i * list->element_size, list->data + (i + 1) * list->element_size, (list->n - i) * list->element_size); |
199 | memmove(&list->ids[i], &list->ids[i + 1], (list->n - i) * sizeof(int)); | 237 | memmove(&list->ids[i], &list->ids[i + 1], (list->n - i) * sizeof(int)); |
200 | 238 | ||
201 | return 1; | 239 | return 1; |
202 | } | 240 | } |
241 | |||
242 | int bs_list_trim(BS_LIST *list) | ||
243 | { | ||
244 | if (!resize(list, list->n)) { | ||
245 | return 0; | ||
246 | } | ||
247 | |||
248 | list->capacity = list->n; | ||
249 | return 1; | ||
250 | } | ||
diff --git a/toxcore/list.h b/toxcore/list.h index 1a1fe57d..03ac04dd 100644 --- a/toxcore/list.h +++ b/toxcore/list.h | |||
@@ -32,13 +32,20 @@ | |||
32 | 32 | ||
33 | typedef struct { | 33 | typedef struct { |
34 | uint32_t n; //number of elements | 34 | uint32_t n; //number of elements |
35 | uint32_t size; //size of the elements | 35 | uint32_t capacity; //number of elements memory is allocated for |
36 | uint32_t element_size; //size of the elements | ||
36 | void *data; //array of elements | 37 | void *data; //array of elements |
37 | int *ids; //array of element ids | 38 | int *ids; //array of element ids |
38 | } BS_LIST; | 39 | } BS_LIST; |
39 | 40 | ||
40 | /* Initialize a list, element_size is the size of the elements in the list */ | 41 | /* Initialize a list, element_size is the size of the elements in the list and |
41 | void bs_list_init(BS_LIST *list, uint32_t element_size); | 42 | * initial_capacity is the number of elements the memory will be initially allocated for |
43 | * | ||
44 | * return value: | ||
45 | * 1 : success | ||
46 | * 0 : failure | ||
47 | */ | ||
48 | int bs_list_init(BS_LIST *list, uint32_t element_size, uint32_t initial_capacity); | ||
42 | 49 | ||
43 | /* Free a list initiated with list_init */ | 50 | /* Free a list initiated with list_init */ |
44 | void bs_list_free(BS_LIST *list); | 51 | void bs_list_free(BS_LIST *list); |
@@ -67,4 +74,12 @@ int bs_list_add(BS_LIST *list, const void *data, int id); | |||
67 | */ | 74 | */ |
68 | int bs_list_remove(BS_LIST *list, const void *data, int id); | 75 | int bs_list_remove(BS_LIST *list, const void *data, int id); |
69 | 76 | ||
77 | /* Removes the memory overhead | ||
78 | * | ||
79 | * return value: | ||
80 | * 1 : success | ||
81 | * 0 : failure | ||
82 | */ | ||
83 | int bs_list_trim(BS_LIST *list); | ||
84 | |||
70 | #endif | 85 | #endif |
diff --git a/toxcore/net_crypto.c b/toxcore/net_crypto.c index 0e88c86c..1fac8edd 100644 --- a/toxcore/net_crypto.c +++ b/toxcore/net_crypto.c | |||
@@ -2507,7 +2507,7 @@ Net_Crypto *new_net_crypto(DHT *dht) | |||
2507 | networking_registerhandler(dht->net, NET_PACKET_CRYPTO_HS, &udp_handle_packet, temp); | 2507 | networking_registerhandler(dht->net, NET_PACKET_CRYPTO_HS, &udp_handle_packet, temp); |
2508 | networking_registerhandler(dht->net, NET_PACKET_CRYPTO_DATA, &udp_handle_packet, temp); | 2508 | networking_registerhandler(dht->net, NET_PACKET_CRYPTO_DATA, &udp_handle_packet, temp); |
2509 | 2509 | ||
2510 | bs_list_init(&temp->ip_port_list, sizeof(IP_Port)); | 2510 | bs_list_init(&temp->ip_port_list, sizeof(IP_Port), 8); |
2511 | return temp; | 2511 | return temp; |
2512 | } | 2512 | } |
2513 | 2513 | ||