summaryrefslogtreecommitdiff
path: root/ot_vector.c
diff options
context:
space:
mode:
Diffstat (limited to 'ot_vector.c')
-rw-r--r--ot_vector.c239
1 files changed, 166 insertions, 73 deletions
diff --git a/ot_vector.c b/ot_vector.c
index 2dcbb08..2862763 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -6,69 +6,65 @@
6/* System */ 6/* System */
7#include <stdlib.h> 7#include <stdlib.h>
8#include <string.h> 8#include <string.h>
9#include <stdint.h>
10#include <stdio.h>
9 11
10/* Opentracker */ 12/* Opentracker */
11#include "trackerlogic.h" 13#include "trackerlogic.h"
12#include "ot_vector.h" 14#include "ot_vector.h"
13 15
14#ifdef _DEBUG_VECTOR 16/* Libowfat */
15#include <stdio.h> 17#include "uint32.h"
16
17static uint64_t vector_debug_inc[32];
18static uint64_t vector_debug_noinc[32];
19static uint64_t vector_debug_dec[32];
20static uint64_t vector_debug_nodec[32];
21static void vector_debug( size_t old_size, ssize_t diff_size, size_t old_space, ssize_t diff_space ) {
22 int x = 0;
23 while( old_space ) { old_space>>=1; ++x; }
24 old_size = old_size;
25
26 if( diff_size == -1 )
27 if( diff_space ) vector_debug_dec[x]++; else vector_debug_nodec[x]++;
28 else
29 if( diff_space ) vector_debug_inc[x]++; else vector_debug_noinc[x]++;
30
31}
32 18
33size_t vector_info( char * reply ) { 19static int vector_compare_peer(const void *peer1, const void *peer2 ) {
34 char * r = reply; 20 int32_t cmp = (int32_t)uint32_read(peer1) - (int32_t)uint32_read(peer2);
35 int i; 21 if (cmp == 0) cmp = ((int8_t*)peer1)[4] - ((int8_t*)peer2)[4];
36 for( i=1; i<28; ++i ) 22 if (cmp == 0) cmp = ((int8_t*)peer1)[5] - ((int8_t*)peer2)[5];
37 r += sprintf( r, " inc % 12d -> % 12d: % 16lld\n", 1<<(i-1), 8<<(i-1), vector_debug_inc[i] ); 23 return cmp;
38 for( i=1; i<28; ++i )
39 r += sprintf( r, "noinc % 12d -> % 12d: % 16lld\n", 1<<(i-1), 1<<(i-1), vector_debug_noinc[i] );
40 for( i=1; i<28; ++i )
41 r += sprintf( r, " dec % 12d -> % 12d: % 16lld\n", 1<<(i-1), 4<<(i-1), vector_debug_dec[i] );
42 for( i=1; i<28; ++i )
43 r += sprintf( r, "nodec % 12d -> % 12d: % 16lld\n", 1<<(i-1), 1<<(i-1), vector_debug_nodec[i] );
44 return r - reply;
45} 24}
46#endif
47 25
48/* This function gives us a binary search that returns a pointer, even if 26/* This function gives us a binary search that returns a pointer, even if
49 no exact match is found. In that case it sets exactmatch 0 and gives 27 no exact match is found. In that case it sets exactmatch 0 and gives
50 calling functions the chance to insert data 28 calling functions the chance to insert data
29
30 NOTE: Minimal compare_size is 4.
51*/ 31*/
52void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, 32void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size,
53 size_t compare_size, int *exactmatch ) { 33 size_t compare_size, int *exactmatch ) {
54 size_t mc = member_count; 34 size_t offs, mc = member_count;
55 uint8_t *lookat = ((uint8_t*)base) + member_size * (member_count >> 1); 35 int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1);
36 int32_t key_cache = (int32_t)uint32_read(key);
56 *exactmatch = 1; 37 *exactmatch = 1;
57 38
58 while( mc ) { 39 while( mc ) {
59 int cmp = memcmp( lookat, key, compare_size); 40 int32_t cmp = key_cache - (int32_t)uint32_read(lookat);
60 if (cmp == 0) return (void *)lookat; 41 if (cmp == 0) {
42 for( offs = 4; cmp == 0 && offs < compare_size; ++offs )
43 cmp = ((int8_t*)key)[offs] - lookat[offs];
44 if( cmp == 0 )
45 return (void *)lookat;
46 }
47
61 if (cmp < 0) { 48 if (cmp < 0) {
62 base = (void*)(lookat + member_size); 49 base = (void*)(lookat + member_size);
63 --mc; 50 --mc;
64 } 51 }
52
65 mc >>= 1; 53 mc >>= 1;
66 lookat = ((uint8_t*)base) + member_size * (mc >> 1); 54 lookat = ((int8_t*)base) + member_size * (mc >> 1);
67 } 55 }
56
68 *exactmatch = 0; 57 *exactmatch = 0;
69 return (void*)lookat; 58 return (void*)lookat;
70} 59}
71 60
61static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) {
62 unsigned int hash = 5381, i = 6;
63 uint8_t *p = (uint8_t*)peer;
64 while( i-- ) hash += (hash<<5) + *(p++);
65 return hash % bucket_count;
66}
67
72/* This is the generic insert operation for our vector type. 68/* This is the generic insert operation for our vector type.
73 It tries to locate the object at "key" with size "member_size" by comparing its first "compare_size" bytes with 69 It tries to locate the object at "key" with size "member_size" by comparing its first "compare_size" bytes with
74 those of objects in vector. Our special "binary_search" function does that and either returns the match or a 70 those of objects in vector. Our special "binary_search" function does that and either returns the match or a
@@ -78,17 +74,13 @@ void *binary_search( const void * const key, const void * base, const size_t mem
78*/ 74*/
79void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, size_t compare_size, int *exactmatch ) { 75void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, size_t compare_size, int *exactmatch ) {
80 uint8_t *match = binary_search( key, vector->data, vector->size, member_size, compare_size, exactmatch ); 76 uint8_t *match = binary_search( key, vector->data, vector->size, member_size, compare_size, exactmatch );
81#ifdef _DEBUG_VECTOR
82 size_t old_space = vector->space;
83#endif
84 77
85 if( *exactmatch ) return match; 78 if( *exactmatch ) return match;
86 79
87 if( vector->size + 1 >= vector->space ) { 80 if( vector->size + 1 > vector->space ) {
88 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; 81 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS;
89 uint8_t *new_data = realloc( vector->data, new_space * member_size ); 82 uint8_t *new_data = realloc( vector->data, new_space * member_size );
90 if( !new_data ) return NULL; 83 if( !new_data ) return NULL;
91
92 /* Adjust pointer if it moved by realloc */ 84 /* Adjust pointer if it moved by realloc */
93 match = new_data + (match - (uint8_t*)vector->data); 85 match = new_data + (match - (uint8_t*)vector->data);
94 86
@@ -97,56 +89,48 @@ void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, s
97 } 89 }
98 memmove( match + member_size, match, ((uint8_t*)vector->data) + member_size * vector->size - match ); 90 memmove( match + member_size, match, ((uint8_t*)vector->data) + member_size * vector->size - match );
99 91
100#ifdef _DEBUG_VECTOR
101 vector_debug( vector->size, 1, old_space, vector->space - old_space );
102#endif
103 vector->size++; 92 vector->size++;
104 return match; 93 return match;
105} 94}
106 95
96/* This function checks, whether our peer vector is a real vector
97 or a list of buckets and dispatches accordingly */
98ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exactmatch ) {
99 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
100 if( vector->space < vector->size )
101 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
102 return vector_find_or_insert( vector, peer, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, exactmatch );
103}
104
107/* This is the non-generic delete from vector-operation specialized for peers in pools. 105/* This is the non-generic delete from vector-operation specialized for peers in pools.
108 Set hysteresis == 0 if you expect the vector not to ever grow again.
109 It returns 0 if no peer was found (and thus not removed) 106 It returns 0 if no peer was found (and thus not removed)
110 1 if a non-seeding peer was removed 107 1 if a non-seeding peer was removed
111 2 if a seeding peer was removed 108 2 if a seeding peer was removed
112*/ 109*/
113int vector_remove_peer( ot_vector *vector, ot_peer *peer, int hysteresis ) { 110int vector_remove_peer( ot_vector *vector, ot_peer *peer ) {
114 int exactmatch; 111 int exactmatch;
115 size_t shrink_thresh = hysteresis ? OT_VECTOR_SHRINK_THRESH : OT_VECTOR_SHRINK_RATIO; 112 ot_peer *match, *end;
116 ot_peer *end = ((ot_peer*)vector->data) + vector->size;
117 ot_peer *match;
118#ifdef _DEBUG_VECTOR
119 size_t old_space = vector->space;
120#endif
121 113
122 if( !vector->size ) return 0; 114 if( !vector->size ) return 0;
123 match = binary_search( peer, vector->data, vector->size, sizeof( ot_peer ), OT_PEER_COMPARE_SIZE, &exactmatch ); 115
116 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
117 if( vector->space < vector->size )
118 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
124 119
120 end = ((ot_peer*)vector->data) + vector->size;
121 match = binary_search( peer, vector->data, vector->size, sizeof( ot_peer ), OT_PEER_COMPARE_SIZE, &exactmatch );
125 if( !exactmatch ) return 0; 122 if( !exactmatch ) return 0;
123
126 exactmatch = ( OT_FLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1; 124 exactmatch = ( OT_FLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1;
127 memmove( match, match + 1, sizeof(ot_peer) * ( end - match - 1 ) ); 125 memmove( match, match + 1, sizeof(ot_peer) * ( end - match - 1 ) );
128 if( ( --vector->size * shrink_thresh < vector->space ) && ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) { 126
129 vector->space /= OT_VECTOR_SHRINK_RATIO; 127 vector->size--;
130 vector->data = realloc( vector->data, vector->space * sizeof( ot_peer ) ); 128 vector_fixup_peers( vector );
131 }
132 if( !vector->size ) {
133 /* for peer pools its safe to let them go,
134 in 999 of 1000 this happens in older pools, that won't ever grow again */
135 free( vector->data );
136 vector->data = NULL;
137 vector->space = 0;
138 }
139#ifdef _DEBUG_VECTOR
140 vector_debug( vector->size+1, -1, old_space, vector->space - old_space );
141#endif
142 return exactmatch; 129 return exactmatch;
143} 130}
144 131
145void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) { 132void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) {
146 ot_torrent *end = ((ot_torrent*)vector->data) + vector->size; 133 ot_torrent *end = ((ot_torrent*)vector->data) + vector->size;
147#ifdef _DEBUG_VECTOR
148 size_t old_space = vector->space;
149#endif
150 134
151 if( !vector->size ) return; 135 if( !vector->size ) return;
152 136
@@ -159,9 +143,118 @@ void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) {
159 vector->space /= OT_VECTOR_SHRINK_RATIO; 143 vector->space /= OT_VECTOR_SHRINK_RATIO;
160 vector->data = realloc( vector->data, vector->space * sizeof( ot_torrent ) ); 144 vector->data = realloc( vector->data, vector->space * sizeof( ot_torrent ) );
161 } 145 }
162#ifdef _DEBUG_VECTOR 146}
163 vector_debug( vector->size+1, -1, old_space, vector->space - old_space ); 147
164#endif 148void vector_clean_list( ot_vector * vector, int num_buckets ) {
149 while( num_buckets-- )
150 free( vector[num_buckets].data );
151 free( vector );
152 return;
153}
154
155void vector_redistribute_buckets( ot_peerlist * peer_list ) {
156 int tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1;
157 ot_vector * bucket_list_new, * bucket_list_old = &peer_list->peers;
158
159 if( OT_PEERLIST_HASBUCKETS( peer_list ) ) {
160 num_buckets_old = peer_list->peers.size;
161 bucket_list_old = peer_list->peers.data;
162 }
163
164 if( peer_list->peer_count < 255 )
165 num_buckets_new = 1;
166 else if( peer_list->peer_count > 8192 )
167 num_buckets_new = 64;
168 else if( peer_list->peer_count >= 512 && peer_list->peer_count < 4096 )
169 num_buckets_new = 16;
170 else if( peer_list->peer_count < 512 && num_buckets_old <= 16 )
171 num_buckets_new = num_buckets_old;
172 else if( peer_list->peer_count < 512 )
173 num_buckets_new = 1;
174 else if( peer_list->peer_count < 8192 && num_buckets_old > 1 )
175 num_buckets_new = num_buckets_old;
176 else
177 num_buckets_new = 16;
178
179 if( num_buckets_new == num_buckets_old )
180 return;
181
182 /* Assume near perfect distribution */
183 bucket_list_new = malloc( num_buckets_new * sizeof( ot_vector ) );
184 if( !bucket_list_new) return;
185 bzero( bucket_list_new, num_buckets_new * sizeof( ot_vector ) );
186
187 tmp = peer_list->peer_count / num_buckets_new;
188 bucket_size_new = OT_VECTOR_MIN_MEMBERS;
189 while( bucket_size_new < tmp)
190 bucket_size_new *= OT_VECTOR_GROW_RATIO;
191
192 /* preallocate vectors to hold all peers */
193 for( bucket=0; bucket<num_buckets_new; ++bucket ) {
194 bucket_list_new[bucket].space = bucket_size_new;
195 bucket_list_new[bucket].data = malloc( bucket_size_new * sizeof(ot_peer) );
196 if( !bucket_list_new[bucket].data )
197 return vector_clean_list( bucket_list_new, num_buckets_new );
198 }
199
200 /* Now sort them into the correct bucket */
201 for( bucket=0; bucket<num_buckets_old; ++bucket ) {
202 ot_peer * peers_old = bucket_list_old[bucket].data, * peers_new;
203 int peer_count_old = bucket_list_old[bucket].size;
204 while( peer_count_old-- ) {
205 ot_vector * bucket_dest = bucket_list_new;
206 if( num_buckets_new > 1 )
207 bucket_dest += vector_hash_peer(peers_old, num_buckets_new);
208 if( bucket_dest->size + 1 > bucket_dest->space ) {
209 void * tmp = realloc( bucket_dest->data, sizeof(ot_peer) * OT_VECTOR_GROW_RATIO * bucket_dest->space );
210 if( !tmp ) return vector_clean_list( bucket_list_new, num_buckets_new );
211 bucket_dest->data = tmp;
212 bucket_dest->space *= OT_VECTOR_GROW_RATIO;
213 }
214 peers_new = (ot_peer*)bucket_dest->data;
215 *(uint64_t*)(peers_new + bucket_dest->size++) = *(uint64_t*)(peers_old++);
216 }
217 }
218
219 /* Now sort each bucket to later allow bsearch */
220 for( bucket=0; bucket<num_buckets_new; ++bucket )
221 qsort( bucket_list_new[bucket].data, bucket_list_new[bucket].size, sizeof( ot_peer ), vector_compare_peer );
222
223 /* Everything worked fine. Now link new bucket_list to peer_list */
224 if( OT_PEERLIST_HASBUCKETS( peer_list) )
225 vector_clean_list( (ot_vector*)peer_list->peers.data, peer_list->peers.size );
226 else
227 free( peer_list->peers.data );
228
229 if( num_buckets_new > 1 ) {
230 peer_list->peers.data = bucket_list_new;
231 peer_list->peers.size = num_buckets_new;
232 peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */
233 } else {
234 peer_list->peers.data = bucket_list_new->data;
235 peer_list->peers.size = bucket_list_new->size;
236 peer_list->peers.space = bucket_list_new->space;
237 free( bucket_list_new );
238 }
239}
240
241void vector_fixup_peers( ot_vector * vector ) {
242 int need_fix = 0;
243
244 if( !vector->size ) {
245 free( vector->data );
246 vector->data = NULL;
247 vector->space = 0;
248 return;
249 }
250
251 while( ( vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) &&
252 ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) {
253 vector->space /= OT_VECTOR_SHRINK_RATIO;
254 need_fix++;
255 }
256 if( need_fix )
257 vector->data = realloc( vector->data, vector->space * sizeof( ot_peer ) );
165} 258}
166 259
167const char *g_version_vector_c = "$Source$: $Revision$\n"; 260const char *g_version_vector_c = "$Source$: $Revision$\n";