summaryrefslogtreecommitdiff
path: root/ot_vector.c
diff options
context:
space:
mode:
Diffstat (limited to 'ot_vector.c')
-rw-r--r--ot_vector.c236
1 files changed, 119 insertions, 117 deletions
diff --git a/ot_vector.c b/ot_vector.c
index 479e832..744306f 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -4,43 +4,37 @@
4 $id$ */ 4 $id$ */
5 5
6/* System */ 6/* System */
7#include <stddef.h>
8#include <stdint.h>
7#include <stdlib.h> 9#include <stdlib.h>
8#include <string.h> 10#include <string.h>
9#include <strings.h> 11#include <strings.h>
10#include <stdint.h>
11#include <stddef.h>
12 12
13/* Opentracker */ 13/* Opentracker */
14#include "trackerlogic.h" 14#include "trackerlogic.h"
15#include "ot_vector.h"
16 15
17/* Libowfat */ 16/* Libowfat */
18#include "uint32.h"
19#include "uint16.h" 17#include "uint16.h"
18#include "uint32.h"
20 19
21static int vector_compare_peer6(const void *peer1, const void *peer2 ) { 20static int vector_compare_peer6(const void *peer1, const void *peer2) { return memcmp(peer1, peer2, OT_PEER_COMPARE_SIZE6); }
22 return memcmp( peer1, peer2, OT_PEER_COMPARE_SIZE6 ); 21static int vector_compare_peer4(const void *peer1, const void *peer2) { return memcmp(peer1, peer2, OT_PEER_COMPARE_SIZE4); }
23}
24static int vector_compare_peer4(const void *peer1, const void *peer2 ) {
25 return memcmp( peer1, peer2, OT_PEER_COMPARE_SIZE4 );
26}
27 22
28/* This function gives us a binary search that returns a pointer, even if 23/* This function gives us a binary search that returns a pointer, even if
29 no exact match is found. In that case it sets exactmatch 0 and gives 24 no exact match is found. In that case it sets exactmatch 0 and gives
30 calling functions the chance to insert data 25 calling functions the chance to insert data
31*/ 26*/
32void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, 27void *binary_search(const void *const key, const void *base, const size_t member_count, const size_t member_size, size_t compare_size, int *exactmatch) {
33 size_t compare_size, int *exactmatch ) {
34 size_t interval = member_count; 28 size_t interval = member_count;
35 29
36 while( interval ) { 30 while (interval) {
37 uint8_t *lookat = ((uint8_t*)base) + member_size * ( interval / 2 ); 31 uint8_t *lookat = ((uint8_t *)base) + member_size * (interval / 2);
38 int cmp = memcmp( lookat, key, compare_size ); 32 int cmp = memcmp(lookat, key, compare_size);
39 if(cmp == 0 ) { 33 if (cmp == 0) {
40 base = lookat; 34 base = lookat;
41 break; 35 break;
42 } 36 }
43 if(cmp < 0) { 37 if (cmp < 0) {
44 base = lookat + member_size; 38 base = lookat + member_size;
45 interval--; 39 interval--;
46 } 40 }
@@ -48,13 +42,14 @@ void *binary_search( const void * const key, const void * base, const size_t mem
48 } 42 }
49 43
50 *exactmatch = interval; 44 *exactmatch = interval;
51 return (void*)base; 45 return (void *)base;
52} 46}
53 47
54static uint8_t vector_hash_peer( ot_peer const *peer, size_t compare_size, int bucket_count ) { 48static uint8_t vector_hash_peer(ot_peer const *peer, size_t compare_size, int bucket_count) {
55 unsigned int hash = 5381; 49 unsigned int hash = 5381;
56 uint8_t *p = (uint8_t*)peer; 50 uint8_t *p = (uint8_t *)peer;
57 while( compare_size-- ) hash += (hash<<5) + *(p++); 51 while (compare_size--)
52 hash += (hash << 5) + *(p++);
58 return hash % bucket_count; 53 return hash % bucket_count;
59} 54}
60 55
@@ -65,58 +60,62 @@ static uint8_t vector_hash_peer( ot_peer const *peer, size_t compare_size, int b
65 if it wasn't found in vector. Caller needs to check the passed "exactmatch" variable to see, whether an insert 60 if it wasn't found in vector. Caller needs to check the passed "exactmatch" variable to see, whether an insert
66 took place. If resizing the vector failed, NULL is returned, else the pointer to the object in vector. 61 took place. If resizing the vector failed, NULL is returned, else the pointer to the object in vector.
67*/ 62*/
68void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, size_t compare_size, int *exactmatch ) { 63void *vector_find_or_insert(ot_vector *vector, void *key, size_t member_size, size_t compare_size, int *exactmatch) {
69 uint8_t *match = binary_search( key, vector->data, vector->size, member_size, compare_size, exactmatch ); 64 uint8_t *match = binary_search(key, vector->data, vector->size, member_size, compare_size, exactmatch);
70 65
71 if( *exactmatch ) return match; 66 if (*exactmatch)
67 return match;
72 68
73 if( vector->size + 1 > vector->space ) { 69 if (vector->size + 1 > vector->space) {
74 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; 70 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS;
75 uint8_t *new_data = realloc( vector->data, new_space * member_size ); 71 uint8_t *new_data = realloc(vector->data, new_space * member_size);
76 if( !new_data ) return NULL; 72 if (!new_data)
73 return NULL;
77 /* Adjust pointer if it moved by realloc */ 74 /* Adjust pointer if it moved by realloc */
78 match = new_data + (match - (uint8_t*)vector->data); 75 match = new_data + (match - (uint8_t *)vector->data);
79 76
80 vector->data = new_data; 77 vector->data = new_data;
81 vector->space = new_space; 78 vector->space = new_space;
82 } 79 }
83 memmove( match + member_size, match, ((uint8_t*)vector->data) + member_size * vector->size - match ); 80 memmove(match + member_size, match, ((uint8_t *)vector->data) + member_size * vector->size - match);
84 81
85 vector->size++; 82 vector->size++;
86 return match; 83 return match;
87} 84}
88 85
89ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer const *peer, size_t peer_size, int *exactmatch ) { 86ot_peer *vector_find_or_insert_peer(ot_vector *vector, ot_peer const *peer, size_t peer_size, int *exactmatch) {
90 ot_peer *match, *end; 87 ot_peer *match, *end;
91 const size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); 88 const size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size);
92 size_t match_to_end; 89 size_t match_to_end;
93 90
94 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 91 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
95 if( vector->space < vector->size ) 92 if (vector->space < vector->size)
96 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, compare_size, vector->size ); 93 vector = ((ot_vector *)vector->data) + vector_hash_peer(peer, compare_size, vector->size);
97 match = binary_search( peer, vector->data, vector->size, peer_size, compare_size, exactmatch ); 94 match = binary_search(peer, vector->data, vector->size, peer_size, compare_size, exactmatch);
98 95
99 if( *exactmatch ) return match; 96 if (*exactmatch)
97 return match;
100 98
101 /* This is the amount of bytes that needs to be pushed backwards by peer_size bytes to make room for new peer */ 99 /* This is the amount of bytes that needs to be pushed backwards by peer_size bytes to make room for new peer */
102 end = (ot_peer*)vector->data + vector->size * peer_size; 100 end = (ot_peer *)vector->data + vector->size * peer_size;
103 match_to_end = end - match; 101 match_to_end = end - match;
104 102
105 if( vector->size + 1 > vector->space ) { 103 if (vector->size + 1 > vector->space) {
106 ptrdiff_t offset = match - (ot_peer*)vector->data; 104 ptrdiff_t offset = match - (ot_peer *)vector->data;
107 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; 105 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS;
108 ot_peer *new_data = realloc( vector->data, new_space * peer_size ); 106 ot_peer *new_data = realloc(vector->data, new_space * peer_size);
109 107
110 if( !new_data ) return NULL; 108 if (!new_data)
109 return NULL;
111 /* Adjust pointer if it moved by realloc */ 110 /* Adjust pointer if it moved by realloc */
112 match = new_data + offset; 111 match = new_data + offset;
113 112
114 vector->data = new_data; 113 vector->data = new_data;
115 vector->space = new_space; 114 vector->space = new_space;
116 } 115 }
117 116
118 /* Here we're guaranteed to have enough space in vector to move the block of peers after insertion point */ 117 /* Here we're guaranteed to have enough space in vector to move the block of peers after insertion point */
119 memmove( match + peer_size, match, match_to_end); 118 memmove(match + peer_size, match, match_to_end);
120 119
121 vector->size++; 120 vector->size++;
122 return match; 121 return match;
@@ -127,130 +126,134 @@ ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer const *peer, siz
127 1 if a non-seeding peer was removed 126 1 if a non-seeding peer was removed
128 2 if a seeding peer was removed 127 2 if a seeding peer was removed
129*/ 128*/
130int vector_remove_peer( ot_vector *vector, ot_peer const *peer, size_t peer_size) { 129int vector_remove_peer(ot_vector *vector, ot_peer const *peer, size_t peer_size) {
131 int exactmatch, was_seeder; 130 int exactmatch, was_seeder;
132 ot_peer *match, *end; 131 ot_peer *match, *end;
133 size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); 132 size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size);
134 133
135 if( !vector->size ) return 0; 134 if (!vector->size)
135 return 0;
136 136
137 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 137 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
138 if( vector->space < vector->size ) 138 if (vector->space < vector->size)
139 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, compare_size, vector->size ); 139 vector = ((ot_vector *)vector->data) + vector_hash_peer(peer, compare_size, vector->size);
140 140
141 end = ((ot_peer*)vector->data) + peer_size * vector->size; 141 end = ((ot_peer *)vector->data) + peer_size * vector->size;
142 match = (ot_peer*)binary_search( peer, vector->data, vector->size, peer_size, compare_size, &exactmatch ); 142 match = (ot_peer *)binary_search(peer, vector->data, vector->size, peer_size, compare_size, &exactmatch);
143 if( !exactmatch ) return 0; 143 if (!exactmatch)
144 return 0;
144 145
145 was_seeder = ( OT_PEERFLAG_D( match, peer_size ) & PEER_FLAG_SEEDING ) ? 2 : 1; 146 was_seeder = (OT_PEERFLAG_D(match, peer_size) & PEER_FLAG_SEEDING) ? 2 : 1;
146 memmove( match, match + peer_size, end - match - peer_size ); 147 memmove(match, match + peer_size, end - match - peer_size);
147 148
148 vector->size--; 149 vector->size--;
149 vector_fixup_peers( vector, peer_size ); 150 vector_fixup_peers(vector, peer_size);
150 return was_seeder; 151 return was_seeder;
151} 152}
152 153
153void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) { 154void vector_remove_torrent(ot_vector *vector, ot_torrent *match) {
154 ot_torrent *end = ((ot_torrent*)vector->data) + vector->size; 155 ot_torrent *end = ((ot_torrent *)vector->data) + vector->size;
155 156
156 if( !vector->size ) return; 157 if (!vector->size)
158 return;
157 159
158 /* If this is being called after a unsuccessful malloc() for peer_list 160 /* If this is being called after a unsuccessful malloc() for peer_list
159 in add_peer_to_torrent, match->peer_list actually might be NULL */ 161 in add_peer_to_torrent, match->peer_list actually might be NULL */
160 free_peerlist( match->peer_list6 ); 162 free_peerlist(match->peer_list6);
161 free_peerlist( match->peer_list4 ); 163 free_peerlist(match->peer_list4);
162 164
163 memmove( match, match + 1, sizeof(ot_torrent) * ( end - match - 1 ) ); 165 memmove(match, match + 1, sizeof(ot_torrent) * (end - match - 1));
164 if( ( --vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) && ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) { 166 if ((--vector->size * OT_VECTOR_SHRINK_THRESH < vector->space) && (vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS)) {
165 vector->space /= OT_VECTOR_SHRINK_RATIO; 167 vector->space /= OT_VECTOR_SHRINK_RATIO;
166 vector->data = realloc( vector->data, vector->space * sizeof( ot_torrent ) ); 168 vector->data = realloc(vector->data, vector->space * sizeof(ot_torrent));
167 } 169 }
168} 170}
169 171
170void vector_clean_list( ot_vector * vector, int num_buckets ) { 172void vector_clean_list(ot_vector *vector, int num_buckets) {
171 while( num_buckets-- ) 173 while (num_buckets--)
172 free( vector[num_buckets].data ); 174 free(vector[num_buckets].data);
173 free( vector ); 175 free(vector);
174 return; 176 return;
175} 177}
176 178
177void vector_redistribute_buckets( ot_peerlist * peer_list, size_t peer_size ) { 179void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) {
178 int tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; 180 int tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1;
179 ot_vector * bucket_list_new, * bucket_list_old = &peer_list->peers; 181 ot_vector *bucket_list_new, *bucket_list_old = &peer_list->peers;
180 int (*sort_func)(const void *, const void *) = 182 int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4;
181 peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4;
182 183
183 if( OT_PEERLIST_HASBUCKETS( peer_list ) ) { 184 if (OT_PEERLIST_HASBUCKETS(peer_list)) {
184 num_buckets_old = peer_list->peers.size; 185 num_buckets_old = peer_list->peers.size;
185 bucket_list_old = peer_list->peers.data; 186 bucket_list_old = peer_list->peers.data;
186 } 187 }
187 188
188 if( peer_list->peer_count < 255 ) 189 if (peer_list->peer_count < 255)
189 num_buckets_new = 1; 190 num_buckets_new = 1;
190 else if( peer_list->peer_count > 8192 ) 191 else if (peer_list->peer_count > 8192)
191 num_buckets_new = 64; 192 num_buckets_new = 64;
192 else if( peer_list->peer_count >= 512 && peer_list->peer_count < 4096 ) 193 else if (peer_list->peer_count >= 512 && peer_list->peer_count < 4096)
193 num_buckets_new = 16; 194 num_buckets_new = 16;
194 else if( peer_list->peer_count < 512 && num_buckets_old <= 16 ) 195 else if (peer_list->peer_count < 512 && num_buckets_old <= 16)
195 num_buckets_new = num_buckets_old; 196 num_buckets_new = num_buckets_old;
196 else if( peer_list->peer_count < 512 ) 197 else if (peer_list->peer_count < 512)
197 num_buckets_new = 1; 198 num_buckets_new = 1;
198 else if( peer_list->peer_count < 8192 && num_buckets_old > 1 ) 199 else if (peer_list->peer_count < 8192 && num_buckets_old > 1)
199 num_buckets_new = num_buckets_old; 200 num_buckets_new = num_buckets_old;
200 else 201 else
201 num_buckets_new = 16; 202 num_buckets_new = 16;
202 203
203 if( num_buckets_new == num_buckets_old ) 204 if (num_buckets_new == num_buckets_old)
204 return; 205 return;
205 206
206 /* Assume near perfect distribution */ 207 /* Assume near perfect distribution */
207 bucket_list_new = malloc( num_buckets_new * sizeof( ot_vector ) ); 208 bucket_list_new = malloc(num_buckets_new * sizeof(ot_vector));
208 if( !bucket_list_new) return; 209 if (!bucket_list_new)
209 bzero( bucket_list_new, num_buckets_new * sizeof( ot_vector ) ); 210 return;
211 bzero(bucket_list_new, num_buckets_new * sizeof(ot_vector));
210 212
211 tmp = peer_list->peer_count / num_buckets_new; 213 tmp = peer_list->peer_count / num_buckets_new;
212 bucket_size_new = OT_VECTOR_MIN_MEMBERS; 214 bucket_size_new = OT_VECTOR_MIN_MEMBERS;
213 while( bucket_size_new < tmp) 215 while (bucket_size_new < tmp)
214 bucket_size_new *= OT_VECTOR_GROW_RATIO; 216 bucket_size_new *= OT_VECTOR_GROW_RATIO;
215 217
216 /* preallocate vectors to hold all peers */ 218 /* preallocate vectors to hold all peers */
217 for( bucket=0; bucket<num_buckets_new; ++bucket ) { 219 for (bucket = 0; bucket < num_buckets_new; ++bucket) {
218 bucket_list_new[bucket].space = bucket_size_new; 220 bucket_list_new[bucket].space = bucket_size_new;
219 bucket_list_new[bucket].data = malloc( bucket_size_new * peer_size ); 221 bucket_list_new[bucket].data = malloc(bucket_size_new * peer_size);
220 if( !bucket_list_new[bucket].data ) 222 if (!bucket_list_new[bucket].data)
221 return vector_clean_list( bucket_list_new, num_buckets_new ); 223 return vector_clean_list(bucket_list_new, num_buckets_new);
222 } 224 }
223 225
224 /* Now sort them into the correct bucket */ 226 /* Now sort them into the correct bucket */
225 for( bucket=0; bucket<num_buckets_old; ++bucket ) { 227 for (bucket = 0; bucket < num_buckets_old; ++bucket) {
226 ot_peer * peers_old = bucket_list_old[bucket].data; 228 ot_peer *peers_old = bucket_list_old[bucket].data;
227 int peer_count_old = bucket_list_old[bucket].size; 229 int peer_count_old = bucket_list_old[bucket].size;
228 while( peer_count_old-- ) { 230 while (peer_count_old--) {
229 ot_vector * bucket_dest = bucket_list_new; 231 ot_vector *bucket_dest = bucket_list_new;
230 if( num_buckets_new > 1 ) 232 if (num_buckets_new > 1)
231 bucket_dest += vector_hash_peer(peers_old, OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size), num_buckets_new); 233 bucket_dest += vector_hash_peer(peers_old, OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size), num_buckets_new);
232 if( bucket_dest->size + 1 > bucket_dest->space ) { 234 if (bucket_dest->size + 1 > bucket_dest->space) {
233 void * tmp = realloc( bucket_dest->data, peer_size * OT_VECTOR_GROW_RATIO * bucket_dest->space ); 235 void *tmp = realloc(bucket_dest->data, peer_size * OT_VECTOR_GROW_RATIO * bucket_dest->space);
234 if( !tmp ) return vector_clean_list( bucket_list_new, num_buckets_new ); 236 if (!tmp)
237 return vector_clean_list(bucket_list_new, num_buckets_new);
235 bucket_dest->data = tmp; 238 bucket_dest->data = tmp;
236 bucket_dest->space *= OT_VECTOR_GROW_RATIO; 239 bucket_dest->space *= OT_VECTOR_GROW_RATIO;
237 } 240 }
238 memcpy((ot_peer*)bucket_dest->data + peer_size * bucket_dest->size++, peers_old, peer_size); 241 memcpy((ot_peer *)bucket_dest->data + peer_size * bucket_dest->size++, peers_old, peer_size);
239 peers_old += peer_size; 242 peers_old += peer_size;
240 } 243 }
241 } 244 }
242 245
243 /* Now sort each bucket to later allow bsearch */ 246 /* Now sort each bucket to later allow bsearch */
244 for( bucket=0; bucket<num_buckets_new; ++bucket ) 247 for (bucket = 0; bucket < num_buckets_new; ++bucket)
245 qsort( bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func ); 248 qsort(bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func);
246 249
247 /* Everything worked fine. Now link new bucket_list to peer_list */ 250 /* Everything worked fine. Now link new bucket_list to peer_list */
248 if( OT_PEERLIST_HASBUCKETS( peer_list) ) 251 if (OT_PEERLIST_HASBUCKETS(peer_list))
249 vector_clean_list( (ot_vector*)peer_list->peers.data, peer_list->peers.size ); 252 vector_clean_list((ot_vector *)peer_list->peers.data, peer_list->peers.size);
250 else 253 else
251 free( peer_list->peers.data ); 254 free(peer_list->peers.data);
252 255
253 if( num_buckets_new > 1 ) { 256 if (num_buckets_new > 1) {
254 peer_list->peers.data = bucket_list_new; 257 peer_list->peers.data = bucket_list_new;
255 peer_list->peers.size = num_buckets_new; 258 peer_list->peers.size = num_buckets_new;
256 peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */ 259 peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */
@@ -258,27 +261,26 @@ void vector_redistribute_buckets( ot_peerlist * peer_list, size_t peer_size ) {
258 peer_list->peers.data = bucket_list_new->data; 261 peer_list->peers.data = bucket_list_new->data;
259 peer_list->peers.size = bucket_list_new->size; 262 peer_list->peers.size = bucket_list_new->size;
260 peer_list->peers.space = bucket_list_new->space; 263 peer_list->peers.space = bucket_list_new->space;
261 free( bucket_list_new ); 264 free(bucket_list_new);
262 } 265 }
263} 266}
264 267
265void vector_fixup_peers( ot_vector * vector, size_t peer_size ) { 268void vector_fixup_peers(ot_vector *vector, size_t peer_size) {
266 int need_fix = 0; 269 int need_fix = 0;
267 270
268 if( !vector->size ) { 271 if (!vector->size) {
269 free( vector->data ); 272 free(vector->data);
270 vector->data = NULL; 273 vector->data = NULL;
271 vector->space = 0; 274 vector->space = 0;
272 return; 275 return;
273 } 276 }
274 277
275 while( ( vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) && 278 while ((vector->size * OT_VECTOR_SHRINK_THRESH < vector->space) && (vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS)) {
276 ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) {
277 vector->space /= OT_VECTOR_SHRINK_RATIO; 279 vector->space /= OT_VECTOR_SHRINK_RATIO;
278 need_fix++; 280 need_fix++;
279 } 281 }
280 if( need_fix ) 282 if (need_fix)
281 vector->data = realloc( vector->data, vector->space * peer_size ); 283 vector->data = realloc(vector->data, vector->space * peer_size);
282} 284}
283 285
284const char *g_version_vector_c = "$Source$: $Revision$\n"; 286const char *g_version_vector_c = "$Source$: $Revision$\n";