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 @@
 /* System */
 #include <stdlib.h>
 #include <string.h>
+#include <stdint.h>
+#include <stdio.h>
 
 /* Opentracker */
 #include "trackerlogic.h"
 #include "ot_vector.h"
 
-#ifdef _DEBUG_VECTOR
-#include <stdio.h>
-
-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<num_buckets_new; ++bucket ) {
+    bucket_list_new[bucket].space = bucket_size_new;
+    bucket_list_new[bucket].data  = malloc( bucket_size_new * sizeof(ot_peer) );
+    if( !bucket_list_new[bucket].data )
+      return vector_clean_list( bucket_list_new, num_buckets_new );
+  }
+
+  /* Now sort them into the correct bucket */
+  for( bucket=0; bucket<num_buckets_old; ++bucket ) {
+    ot_peer * peers_old = bucket_list_old[bucket].data, * peers_new;
+    int peer_count_old = bucket_list_old[bucket].size;
+    while( peer_count_old-- ) {
+      ot_vector * bucket_dest = bucket_list_new;
+      if( num_buckets_new > 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; bucket<num_buckets_new; ++bucket )
+    qsort( bucket_list_new[bucket].data, bucket_list_new[bucket].size, sizeof( ot_peer ), vector_compare_peer );
+
+  /* Everything worked fine. Now link new bucket_list to peer_list */
+  if( OT_PEERLIST_HASBUCKETS( peer_list) )
+    vector_clean_list( (ot_vector*)peer_list->peers.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";