diff options
-rw-r--r-- | ot_vector.c | 26 |
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 | */ |
31 | void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, | 31 | void *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; |