From 334c6e4bbb97a4c0656e1b07c3e6a565f68eae2b Mon Sep 17 00:00:00 2001 From: erdgeist <> Date: Fri, 28 Nov 2008 22:21:10 +0000 Subject: The BIG refactoring [tm]. Too many changes to count them. If it doesn't suite you, revert to last version. --- ot_vector.c | 239 +++++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 166 insertions(+), 73 deletions(-) (limited to 'ot_vector.c') 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 @@ /* System */ #include #include +#include +#include /* Opentracker */ #include "trackerlogic.h" #include "ot_vector.h" -#ifdef _DEBUG_VECTOR -#include - -static uint64_t vector_debug_inc[32]; -static uint64_t vector_debug_noinc[32]; -static uint64_t vector_debug_dec[32]; -static uint64_t vector_debug_nodec[32]; -static void vector_debug( size_t old_size, ssize_t diff_size, size_t old_space, ssize_t diff_space ) { - int x = 0; - while( old_space ) { old_space>>=1; ++x; } - old_size = old_size; - - if( diff_size == -1 ) - if( diff_space ) vector_debug_dec[x]++; else vector_debug_nodec[x]++; - else - if( diff_space ) vector_debug_inc[x]++; else vector_debug_noinc[x]++; - -} +/* Libowfat */ +#include "uint32.h" -size_t vector_info( char * reply ) { - char * r = reply; - int i; - for( i=1; i<28; ++i ) - r += sprintf( r, " inc % 12d -> % 12d: % 16lld\n", 1<<(i-1), 8<<(i-1), vector_debug_inc[i] ); - for( i=1; i<28; ++i ) - r += sprintf( r, "noinc % 12d -> % 12d: % 16lld\n", 1<<(i-1), 1<<(i-1), vector_debug_noinc[i] ); - for( i=1; i<28; ++i ) - r += sprintf( r, " dec % 12d -> % 12d: % 16lld\n", 1<<(i-1), 4<<(i-1), vector_debug_dec[i] ); - for( i=1; i<28; ++i ) - r += sprintf( r, "nodec % 12d -> % 12d: % 16lld\n", 1<<(i-1), 1<<(i-1), vector_debug_nodec[i] ); - return r - reply; +static int vector_compare_peer(const void *peer1, const void *peer2 ) { + int32_t cmp = (int32_t)uint32_read(peer1) - (int32_t)uint32_read(peer2); + if (cmp == 0) cmp = ((int8_t*)peer1)[4] - ((int8_t*)peer2)[4]; + if (cmp == 0) cmp = ((int8_t*)peer1)[5] - ((int8_t*)peer2)[5]; + return cmp; } -#endif /* This function gives us a binary search that returns a pointer, even if no exact match is found. In that case it sets exactmatch 0 and gives calling functions the chance to insert data + + NOTE: Minimal compare_size is 4. */ void *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 ) { - size_t mc = member_count; - uint8_t *lookat = ((uint8_t*)base) + member_size * (member_count >> 1); + size_t offs, mc = member_count; + int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1); + int32_t key_cache = (int32_t)uint32_read(key); *exactmatch = 1; while( mc ) { - int cmp = memcmp( lookat, key, compare_size); - if (cmp == 0) return (void *)lookat; + int32_t cmp = key_cache - (int32_t)uint32_read(lookat); + if (cmp == 0) { + for( offs = 4; cmp == 0 && offs < compare_size; ++offs ) + cmp = ((int8_t*)key)[offs] - lookat[offs]; + if( cmp == 0 ) + return (void *)lookat; + } + if (cmp < 0) { base = (void*)(lookat + member_size); --mc; } + mc >>= 1; - lookat = ((uint8_t*)base) + member_size * (mc >> 1); + lookat = ((int8_t*)base) + member_size * (mc >> 1); } + *exactmatch = 0; return (void*)lookat; } +static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) { + unsigned int hash = 5381, i = 6; + uint8_t *p = (uint8_t*)peer; + while( i-- ) hash += (hash<<5) + *(p++); + return hash % bucket_count; +} + /* This is the generic insert operation for our vector type. It tries to locate the object at "key" with size "member_size" by comparing its first "compare_size" bytes with 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 */ void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, size_t compare_size, int *exactmatch ) { uint8_t *match = binary_search( key, vector->data, vector->size, member_size, compare_size, exactmatch ); -#ifdef _DEBUG_VECTOR - size_t old_space = vector->space; -#endif if( *exactmatch ) return match; - if( vector->size + 1 >= vector->space ) { + if( vector->size + 1 > vector->space ) { size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; uint8_t *new_data = realloc( vector->data, new_space * member_size ); if( !new_data ) return NULL; - /* Adjust pointer if it moved by realloc */ match = new_data + (match - (uint8_t*)vector->data); @@ -97,56 +89,48 @@ void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, s } memmove( match + member_size, match, ((uint8_t*)vector->data) + member_size * vector->size - match ); -#ifdef _DEBUG_VECTOR - vector_debug( vector->size, 1, old_space, vector->space - old_space ); -#endif vector->size++; return match; } +/* This function checks, whether our peer vector is a real vector + or a list of buckets and dispatches accordingly */ +ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exactmatch ) { + /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ + if( vector->space < vector->size ) + vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); + return vector_find_or_insert( vector, peer, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, exactmatch ); +} + /* This is the non-generic delete from vector-operation specialized for peers in pools. - Set hysteresis == 0 if you expect the vector not to ever grow again. It returns 0 if no peer was found (and thus not removed) 1 if a non-seeding peer was removed 2 if a seeding peer was removed */ -int vector_remove_peer( ot_vector *vector, ot_peer *peer, int hysteresis ) { +int vector_remove_peer( ot_vector *vector, ot_peer *peer ) { int exactmatch; - size_t shrink_thresh = hysteresis ? OT_VECTOR_SHRINK_THRESH : OT_VECTOR_SHRINK_RATIO; - ot_peer *end = ((ot_peer*)vector->data) + vector->size; - ot_peer *match; -#ifdef _DEBUG_VECTOR - size_t old_space = vector->space; -#endif + ot_peer *match, *end; if( !vector->size ) return 0; - match = binary_search( peer, vector->data, vector->size, sizeof( ot_peer ), OT_PEER_COMPARE_SIZE, &exactmatch ); + + /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ + if( vector->space < vector->size ) + vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); + end = ((ot_peer*)vector->data) + vector->size; + match = binary_search( peer, vector->data, vector->size, sizeof( ot_peer ), OT_PEER_COMPARE_SIZE, &exactmatch ); if( !exactmatch ) return 0; + exactmatch = ( OT_FLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1; memmove( match, match + 1, sizeof(ot_peer) * ( end - match - 1 ) ); - if( ( --vector->size * shrink_thresh < vector->space ) && ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) { - vector->space /= OT_VECTOR_SHRINK_RATIO; - vector->data = realloc( vector->data, vector->space * sizeof( ot_peer ) ); - } - if( !vector->size ) { - /* for peer pools its safe to let them go, - in 999 of 1000 this happens in older pools, that won't ever grow again */ - free( vector->data ); - vector->data = NULL; - vector->space = 0; - } -#ifdef _DEBUG_VECTOR - vector_debug( vector->size+1, -1, old_space, vector->space - old_space ); -#endif + + vector->size--; + vector_fixup_peers( vector ); return exactmatch; } void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) { ot_torrent *end = ((ot_torrent*)vector->data) + vector->size; -#ifdef _DEBUG_VECTOR - size_t old_space = vector->space; -#endif if( !vector->size ) return; @@ -159,9 +143,118 @@ void vector_remove_torrent( ot_vector *vector, ot_torrent *match ) { vector->space /= OT_VECTOR_SHRINK_RATIO; vector->data = realloc( vector->data, vector->space * sizeof( ot_torrent ) ); } -#ifdef _DEBUG_VECTOR - vector_debug( vector->size+1, -1, old_space, vector->space - old_space ); -#endif +} + +void vector_clean_list( ot_vector * vector, int num_buckets ) { + while( num_buckets-- ) + free( vector[num_buckets].data ); + free( vector ); + return; +} + +void vector_redistribute_buckets( ot_peerlist * peer_list ) { + int tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; + ot_vector * bucket_list_new, * bucket_list_old = &peer_list->peers; + + if( OT_PEERLIST_HASBUCKETS( peer_list ) ) { + num_buckets_old = peer_list->peers.size; + bucket_list_old = peer_list->peers.data; + } + + if( peer_list->peer_count < 255 ) + num_buckets_new = 1; + else if( peer_list->peer_count > 8192 ) + num_buckets_new = 64; + else if( peer_list->peer_count >= 512 && peer_list->peer_count < 4096 ) + num_buckets_new = 16; + else if( peer_list->peer_count < 512 && num_buckets_old <= 16 ) + num_buckets_new = num_buckets_old; + else if( peer_list->peer_count < 512 ) + num_buckets_new = 1; + else if( peer_list->peer_count < 8192 && num_buckets_old > 1 ) + num_buckets_new = num_buckets_old; + else + num_buckets_new = 16; + + if( num_buckets_new == num_buckets_old ) + return; + + /* Assume near perfect distribution */ + bucket_list_new = malloc( num_buckets_new * sizeof( ot_vector ) ); + if( !bucket_list_new) return; + bzero( bucket_list_new, num_buckets_new * sizeof( ot_vector ) ); + + tmp = peer_list->peer_count / num_buckets_new; + bucket_size_new = OT_VECTOR_MIN_MEMBERS; + while( bucket_size_new < tmp) + bucket_size_new *= OT_VECTOR_GROW_RATIO; + + /* preallocate vectors to hold all peers */ + for( bucket=0; bucket 1 ) + bucket_dest += vector_hash_peer(peers_old, num_buckets_new); + if( bucket_dest->size + 1 > bucket_dest->space ) { + void * tmp = realloc( bucket_dest->data, sizeof(ot_peer) * OT_VECTOR_GROW_RATIO * bucket_dest->space ); + if( !tmp ) return vector_clean_list( bucket_list_new, num_buckets_new ); + bucket_dest->data = tmp; + bucket_dest->space *= OT_VECTOR_GROW_RATIO; + } + peers_new = (ot_peer*)bucket_dest->data; + *(uint64_t*)(peers_new + bucket_dest->size++) = *(uint64_t*)(peers_old++); + } + } + + /* Now sort each bucket to later allow bsearch */ + for( bucket=0; bucketpeers.data, peer_list->peers.size ); + else + free( peer_list->peers.data ); + + if( num_buckets_new > 1 ) { + peer_list->peers.data = bucket_list_new; + peer_list->peers.size = num_buckets_new; + peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */ + } else { + peer_list->peers.data = bucket_list_new->data; + peer_list->peers.size = bucket_list_new->size; + peer_list->peers.space = bucket_list_new->space; + free( bucket_list_new ); + } +} + +void vector_fixup_peers( ot_vector * vector ) { + int need_fix = 0; + + if( !vector->size ) { + free( vector->data ); + vector->data = NULL; + vector->space = 0; + return; + } + + while( ( vector->size * OT_VECTOR_SHRINK_THRESH < vector->space ) && + ( vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS ) ) { + vector->space /= OT_VECTOR_SHRINK_RATIO; + need_fix++; + } + if( need_fix ) + vector->data = realloc( vector->data, vector->space * sizeof( ot_peer ) ); } const char *g_version_vector_c = "$Source$: $Revision$\n"; -- cgit v1.2.3