summaryrefslogtreecommitdiff
path: root/ot_vector.c
diff options
context:
space:
mode:
Diffstat (limited to 'ot_vector.c')
-rw-r--r--ot_vector.c83
1 files changed, 50 insertions, 33 deletions
diff --git a/ot_vector.c b/ot_vector.c
index 2a632b2..c38f05d 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -17,8 +17,11 @@
17#include "uint32.h" 17#include "uint32.h"
18#include "uint16.h" 18#include "uint16.h"
19 19
20static int vector_compare_peer(const void *peer1, const void *peer2 ) { 20static int vector_compare_peer6(const void *peer1, const void *peer2 ) {
21 return memcmp( peer1, peer2, OT_PEER_COMPARE_SIZE ); 21 return memcmp( peer1, peer2, OT_PEER_COMPARE_SIZE6 );
22}
23static int vector_compare_peer4(const void *peer1, const void *peer2 ) {
24 return memcmp( peer1, peer2, OT_PEER_COMPARE_SIZE4 );
22} 25}
23 26
24/* This function gives us a binary search that returns a pointer, even if 27/* This function gives us a binary search that returns a pointer, even if
@@ -47,10 +50,10 @@ void *binary_search( const void * const key, const void * base, const size_t mem
47 return (void*)base; 50 return (void*)base;
48} 51}
49 52
50static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) { 53static uint8_t vector_hash_peer( ot_peer const *peer, size_t compare_size, int bucket_count ) {
51 unsigned int hash = 5381, i = OT_PEER_COMPARE_SIZE; 54 unsigned int hash = 5381;
52 uint8_t *p = (uint8_t*)peer; 55 uint8_t *p = (uint8_t*)peer;
53 while( i-- ) hash += (hash<<5) + *(p++); 56 while( compare_size-- ) hash += (hash<<5) + *(p++);
54 return hash % bucket_count; 57 return hash % bucket_count;
55} 58}
56 59
@@ -82,27 +85,37 @@ void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, s
82 return match; 85 return match;
83} 86}
84 87
85ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exactmatch ) { 88ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer const *peer, size_t peer_size, int *exactmatch ) {
86 ot_peer *match; 89 ot_peer *match, *end;
90 const size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size);
91 size_t match_to_end;
87 92
88 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 93 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
89 if( vector->space < vector->size ) 94 if( vector->space < vector->size )
90 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 95 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, compare_size, vector->size );
91 match = (ot_peer*)binary_search( peer, vector->data, vector->size, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, exactmatch ); 96 match = binary_search( peer, vector->data, vector->size, peer_size, compare_size, exactmatch );
92 97
93 if( *exactmatch ) return match; 98 if( *exactmatch ) return match;
94 99
100 /* This is the amount of bytes that needs to be pushed backwards by peer_size bytes to make room for new peer */
101 end = (ot_peer*)vector->data + vector->size * peer_size;
102 match_to_end = end - match;
103
95 if( vector->size + 1 > vector->space ) { 104 if( vector->size + 1 > vector->space ) {
105 ptrdiff_t offset = match - (ot_peer*)vector->data;
96 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; 106 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS;
97 ot_peer *new_data = realloc( vector->data, new_space * sizeof(ot_peer) ); 107 ot_peer *new_data = realloc( vector->data, new_space * peer_size );
108
98 if( !new_data ) return NULL; 109 if( !new_data ) return NULL;
99 /* Adjust pointer if it moved by realloc */ 110 /* Adjust pointer if it moved by realloc */
100 match = new_data + (match - (ot_peer*)vector->data); 111 match = new_data + offset;
101 112
102 vector->data = new_data; 113 vector->data = new_data;
103 vector->space = new_space; 114 vector->space = new_space;
104 } 115 }
105 memmove( match + 1, match, sizeof(ot_peer) * ( ((ot_peer*)vector->data) + vector->size - match ) ); 116
117 /* Here we're guaranteed to have enough space in vector to move the block of peers after insertion point */
118 memmove( match + peer_size, match, match_to_end);
106 119
107 vector->size++; 120 vector->size++;
108 return match; 121 return match;
@@ -113,26 +126,27 @@ ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exac
113 1 if a non-seeding peer was removed 126 1 if a non-seeding peer was removed
114 2 if a seeding peer was removed 127 2 if a seeding peer was removed
115*/ 128*/
116int vector_remove_peer( ot_vector *vector, ot_peer *peer ) { 129int vector_remove_peer( ot_vector *vector, ot_peer const *peer, size_t peer_size) {
117 int exactmatch; 130 int exactmatch, was_seeder;
118 ot_peer *match, *end; 131 ot_peer *match, *end;
132 size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size);
119 133
120 if( !vector->size ) return 0; 134 if( !vector->size ) return 0;
121 135
122 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 136 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
123 if( vector->space < vector->size ) 137 if( vector->space < vector->size )
124 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 138 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, compare_size, vector->size );
125 139
126 end = ((ot_peer*)vector->data) + vector->size; 140 end = ((ot_peer*)vector->data) + peer_size * vector->size;
127 match = (ot_peer*)binary_search( peer, vector->data, vector->size, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, &exactmatch ); 141 match = (ot_peer*)binary_search( peer, vector->data, vector->size, peer_size, compare_size, &exactmatch );
128 if( !exactmatch ) return 0; 142 if( !exactmatch ) return 0;
129 143
130 exactmatch = ( OT_PEERFLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1; 144 was_seeder = ( OT_PEERFLAG_D( match, peer_size ) & PEER_FLAG_SEEDING ) ? 2 : 1;
131 memmove( match, match + 1, sizeof(ot_peer) * ( end - match - 1 ) ); 145 memmove( match, match + peer_size, end - match - peer_size );
132 146
133 vector->size--; 147 vector->size--;
134 vector_fixup_peers( vector ); 148 vector_fixup_peers( vector, peer_size );
135 return exactmatch; 149 return was_seeder;
136} 150}
137 151
138void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) { 152void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) {
@@ -142,7 +156,8 @@ void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) {
142 156
143 /* If this is being called after a unsuccessful malloc() for peer_list 157 /* If this is being called after a unsuccessful malloc() for peer_list
144 in add_peer_to_torrent, match->peer_list actually might be NULL */ 158 in add_peer_to_torrent, match->peer_list actually might be NULL */
145 if( match->peer_list) free_peerlist( match->peer_list ); 159 if( match->peer_list6) free_peerlist( match->peer_list6 );
160 if( match->peer_list4) free_peerlist( match->peer_list4 );
146 161
147 memmove( match, match + 1, sizeof(ot_torrent) * ( end - match - 1 ) ); 162 memmove( match, match + 1, sizeof(ot_torrent) * ( end - match - 1 ) );
148 if( ( --vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) && ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) { 163 if( ( --vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) && ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) {
@@ -158,9 +173,11 @@ void vector_clean_list( ot_vector * vector, int num_buckets ) {
158 return; 173 return;
159} 174}
160 175
161void vector_redistribute_buckets( ot_peerlist * peer_list ) { 176void vector_redistribute_buckets( ot_peerlist * peer_list, size_t peer_size ) {
162 int tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; 177 int tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1;
163 ot_vector * bucket_list_new, * bucket_list_old = &peer_list->peers; 178 ot_vector * bucket_list_new, * bucket_list_old = &peer_list->peers;
179 int (*sort_func)(const void *, const void *) =
180 peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4;
164 181
165 if( OT_PEERLIST_HASBUCKETS( peer_list ) ) { 182 if( OT_PEERLIST_HASBUCKETS( peer_list ) ) {
166 num_buckets_old = peer_list->peers.size; 183 num_buckets_old = peer_list->peers.size;
@@ -198,33 +215,33 @@ void vector_redistribute_buckets( ot_peerlist * peer_list ) {
198 /* preallocate vectors to hold all peers */ 215 /* preallocate vectors to hold all peers */
199 for( bucket=0; bucket<num_buckets_new; ++bucket ) { 216 for( bucket=0; bucket<num_buckets_new; ++bucket ) {
200 bucket_list_new[bucket].space = bucket_size_new; 217 bucket_list_new[bucket].space = bucket_size_new;
201 bucket_list_new[bucket].data = malloc( bucket_size_new * sizeof(ot_peer) ); 218 bucket_list_new[bucket].data = malloc( bucket_size_new * peer_size );
202 if( !bucket_list_new[bucket].data ) 219 if( !bucket_list_new[bucket].data )
203 return vector_clean_list( bucket_list_new, num_buckets_new ); 220 return vector_clean_list( bucket_list_new, num_buckets_new );
204 } 221 }
205 222
206 /* Now sort them into the correct bucket */ 223 /* Now sort them into the correct bucket */
207 for( bucket=0; bucket<num_buckets_old; ++bucket ) { 224 for( bucket=0; bucket<num_buckets_old; ++bucket ) {
208 ot_peer * peers_old = bucket_list_old[bucket].data, * peers_new; 225 ot_peer * peers_old = bucket_list_old[bucket].data;
209 int peer_count_old = bucket_list_old[bucket].size; 226 int peer_count_old = bucket_list_old[bucket].size;
210 while( peer_count_old-- ) { 227 while( peer_count_old-- ) {
211 ot_vector * bucket_dest = bucket_list_new; 228 ot_vector * bucket_dest = bucket_list_new;
212 if( num_buckets_new > 1 ) 229 if( num_buckets_new > 1 )
213 bucket_dest += vector_hash_peer(peers_old, num_buckets_new); 230 bucket_dest += vector_hash_peer(peers_old, OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size), num_buckets_new);
214 if( bucket_dest->size + 1 > bucket_dest->space ) { 231 if( bucket_dest->size + 1 > bucket_dest->space ) {
215 void * tmp = realloc( bucket_dest->data, sizeof(ot_peer) * OT_VECTOR_GROW_RATIO * bucket_dest->space ); 232 void * tmp = realloc( bucket_dest->data, peer_size * OT_VECTOR_GROW_RATIO * bucket_dest->space );
216 if( !tmp ) return vector_clean_list( bucket_list_new, num_buckets_new ); 233 if( !tmp ) return vector_clean_list( bucket_list_new, num_buckets_new );
217 bucket_dest->data = tmp; 234 bucket_dest->data = tmp;
218 bucket_dest->space *= OT_VECTOR_GROW_RATIO; 235 bucket_dest->space *= OT_VECTOR_GROW_RATIO;
219 } 236 }
220 peers_new = (ot_peer*)bucket_dest->data; 237 memcpy((ot_peer*)bucket_dest->data + peer_size * bucket_dest->size++, peers_old, peer_size);
221 memcpy(peers_new + bucket_dest->size++, peers_old++, sizeof(ot_peer)); 238 peers_old += peer_size;
222 } 239 }
223 } 240 }
224 241
225 /* Now sort each bucket to later allow bsearch */ 242 /* Now sort each bucket to later allow bsearch */
226 for( bucket=0; bucket<num_buckets_new; ++bucket ) 243 for( bucket=0; bucket<num_buckets_new; ++bucket )
227 qsort( bucket_list_new[bucket].data, bucket_list_new[bucket].size, sizeof( ot_peer ), vector_compare_peer ); 244 qsort( bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func );
228 245
229 /* Everything worked fine. Now link new bucket_list to peer_list */ 246 /* Everything worked fine. Now link new bucket_list to peer_list */
230 if( OT_PEERLIST_HASBUCKETS( peer_list) ) 247 if( OT_PEERLIST_HASBUCKETS( peer_list) )
@@ -244,7 +261,7 @@ void vector_redistribute_buckets( ot_peerlist * peer_list ) {
244 } 261 }
245} 262}
246 263
247void vector_fixup_peers( ot_vector * vector ) { 264void vector_fixup_peers( ot_vector * vector, size_t peer_size ) {
248 int need_fix = 0; 265 int need_fix = 0;
249 266
250 if( !vector->size ) { 267 if( !vector->size ) {
@@ -260,7 +277,7 @@ void vector_fixup_peers( ot_vector * vector ) {
260 need_fix++; 277 need_fix++;
261 } 278 }
262 if( need_fix ) 279 if( need_fix )
263 vector->data = realloc( vector->data, vector->space * sizeof( ot_peer ) ); 280 vector->data = realloc( vector->data, vector->space * peer_size );
264} 281}
265 282
266const char *g_version_vector_c = "$Source$: $Revision$\n"; 283const char *g_version_vector_c = "$Source$: $Revision$\n";