summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ot_vector.c26
1 files changed, 13 insertions, 13 deletions
diff --git a/ot_vector.c b/ot_vector.c
index f92f7ac..29bdd49 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -25,7 +25,7 @@ static int vector_compare_peer(const void *peer1, const void *peer2 ) {
25/* This function gives us a binary search that returns a pointer, even if 25/* This function gives us a binary search that returns a pointer, even if
26 no exact match is found. In that case it sets exactmatch 0 and gives 26 no exact match is found. In that case it sets exactmatch 0 and gives
27 calling functions the chance to insert data 27 calling functions the chance to insert data
28 28
29 NOTE: Minimal compare_size is 4, member_size must be a multiple of 4 29 NOTE: Minimal compare_size is 4, member_size must be a multiple of 4
30*/ 30*/
31void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, 31void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size,
@@ -34,7 +34,7 @@ void *binary_search( const void * const key, const void * base, const size_t mem
34 int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1); 34 int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1);
35 int32_t key_cache = READ32(key,0); 35 int32_t key_cache = READ32(key,0);
36 *exactmatch = 1; 36 *exactmatch = 1;
37 37
38 while( mc ) { 38 while( mc ) {
39 int32_t cmp = READ32(lookat,0) - key_cache; 39 int32_t cmp = READ32(lookat,0) - key_cache;
40 if (cmp == 0) { 40 if (cmp == 0) {
@@ -63,9 +63,9 @@ ot_peer *binary_search_peer( const ot_peer * const peer, const ot_peer * base, c
63 int32_t low = READ32(peer,0); 63 int32_t low = READ32(peer,0);
64 int16_t high = READ16(peer,4); 64 int16_t high = READ16(peer,4);
65 *exactmatch = 1; 65 *exactmatch = 1;
66 66
67 while( mc ) { 67 while( mc ) {
68 int32_t cmp = READ32(lookat,0) - low; 68 int32_t cmp = READ32(lookat,0) - low;
69 if(cmp == 0) cmp = READ16(lookat,4) - high; 69 if(cmp == 0) cmp = READ16(lookat,4) - high;
70 if(cmp == 0) return (ot_peer*)lookat; 70 if(cmp == 0) return (ot_peer*)lookat;
71 71
@@ -77,7 +77,7 @@ ot_peer *binary_search_peer( const ot_peer * const peer, const ot_peer * base, c
77 mc >>= 1; 77 mc >>= 1;
78 lookat = base + (mc >> 1); 78 lookat = base + (mc >> 1);
79 } 79 }
80 80
81 *exactmatch = 0; 81 *exactmatch = 0;
82 return (ot_peer*)lookat; 82 return (ot_peer*)lookat;
83} 83}
@@ -127,19 +127,19 @@ ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exac
127 match = binary_search_peer( peer, vector->data, vector->size, exactmatch ); 127 match = binary_search_peer( peer, vector->data, vector->size, exactmatch );
128 128
129 if( *exactmatch ) return match; 129 if( *exactmatch ) return match;
130 130
131 if( vector->size + 1 > vector->space ) { 131 if( vector->size + 1 > vector->space ) {
132 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; 132 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS;
133 ot_peer *new_data = realloc( vector->data, new_space * sizeof(ot_peer) ); 133 ot_peer *new_data = realloc( vector->data, new_space * sizeof(ot_peer) );
134 if( !new_data ) return NULL; 134 if( !new_data ) return NULL;
135 /* Adjust pointer if it moved by realloc */ 135 /* Adjust pointer if it moved by realloc */
136 match = new_data + (match - (ot_peer*)vector->data); 136 match = new_data + (match - (ot_peer*)vector->data);
137 137
138 vector->data = new_data; 138 vector->data = new_data;
139 vector->space = new_space; 139 vector->space = new_space;
140 } 140 }
141 memmove( match + 1, match, sizeof(ot_peer) * ( ((ot_peer*)vector->data) + vector->size - match ) ); 141 memmove( match + 1, match, sizeof(ot_peer) * ( ((ot_peer*)vector->data) + vector->size - match ) );
142 142
143 vector->size++; 143 vector->size++;
144 return match; 144 return match;
145} 145}
@@ -154,7 +154,7 @@ int vector_remove_peer( ot_vector *vector, ot_peer *peer ) {
154 ot_peer *match, *end; 154 ot_peer *match, *end;
155 155
156 if( !vector->size ) return 0; 156 if( !vector->size ) return 0;
157 157
158 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 158 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
159 if( vector->space < vector->size ) 159 if( vector->space < vector->size )
160 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 160 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
@@ -209,7 +209,7 @@ void vector_redistribute_buckets( ot_peerlist * peer_list ) {
209 num_buckets_new = 64; 209 num_buckets_new = 64;
210 else if( peer_list->peer_count >= 512 && peer_list->peer_count < 4096 ) 210 else if( peer_list->peer_count >= 512 && peer_list->peer_count < 4096 )
211 num_buckets_new = 16; 211 num_buckets_new = 16;
212 else if( peer_list->peer_count < 512 && num_buckets_old <= 16 ) 212 else if( peer_list->peer_count < 512 && num_buckets_old <= 16 )
213 num_buckets_new = num_buckets_old; 213 num_buckets_new = num_buckets_old;
214 else if( peer_list->peer_count < 512 ) 214 else if( peer_list->peer_count < 512 )
215 num_buckets_new = 1; 215 num_buckets_new = 1;
@@ -229,7 +229,7 @@ void vector_redistribute_buckets( ot_peerlist * peer_list ) {
229 tmp = peer_list->peer_count / num_buckets_new; 229 tmp = peer_list->peer_count / num_buckets_new;
230 bucket_size_new = OT_VECTOR_MIN_MEMBERS; 230 bucket_size_new = OT_VECTOR_MIN_MEMBERS;
231 while( bucket_size_new < tmp) 231 while( bucket_size_new < tmp)
232 bucket_size_new *= OT_VECTOR_GROW_RATIO; 232 bucket_size_new *= OT_VECTOR_GROW_RATIO;
233 233
234 /* preallocate vectors to hold all peers */ 234 /* preallocate vectors to hold all peers */
235 for( bucket=0; bucket<num_buckets_new; ++bucket ) { 235 for( bucket=0; bucket<num_buckets_new; ++bucket ) {
@@ -267,7 +267,7 @@ void vector_redistribute_buckets( ot_peerlist * peer_list ) {
267 vector_clean_list( (ot_vector*)peer_list->peers.data, peer_list->peers.size ); 267 vector_clean_list( (ot_vector*)peer_list->peers.data, peer_list->peers.size );
268 else 268 else
269 free( peer_list->peers.data ); 269 free( peer_list->peers.data );
270 270
271 if( num_buckets_new > 1 ) { 271 if( num_buckets_new > 1 ) {
272 peer_list->peers.data = bucket_list_new; 272 peer_list->peers.data = bucket_list_new;
273 peer_list->peers.size = num_buckets_new; 273 peer_list->peers.size = num_buckets_new;
@@ -289,7 +289,7 @@ void vector_fixup_peers( ot_vector * vector ) {
289 vector->space = 0; 289 vector->space = 0;
290 return; 290 return;
291 } 291 }
292 292
293 while( ( vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) && 293 while( ( vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) &&
294 ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) { 294 ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) {
295 vector->space /= OT_VECTOR_SHRINK_RATIO; 295 vector->space /= OT_VECTOR_SHRINK_RATIO;