From 0c8a17cbef002b60b7e458f110f9d930d17aa73e Mon Sep 17 00:00:00 2001
From: erdgeist <>
Date: Wed, 26 Aug 2009 17:44:03 +0000
Subject: Optimize binary_search function

---
 ot_vector.c | 58 +++++++++++++++++-----------------------------------------
 1 file changed, 17 insertions(+), 41 deletions(-)

diff --git a/ot_vector.c b/ot_vector.c
index cbb3fac..056fafb 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -6,6 +6,7 @@
 /* System */
 #include <stdlib.h>
 #include <string.h>
+#include <strings.h>
 #include <stdint.h>
 
 /* Opentracker */
@@ -26,51 +27,26 @@ static int vector_compare_peer(const void *peer1, const void *peer2 ) {
 */
 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;
-  int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1);
-  *exactmatch = 1;
-
-  while( mc ) {
-    int32_t cmp = memcmp( lookat, key, compare_size );
-    if( cmp == 0 )
-      return (void *)lookat;
-
-    if (cmp < 0) {
-      base = (void*)(lookat + member_size);
-      --mc;
+  size_t interval = member_count * member_size;
+
+  while( interval ) {
+    uint8_t *lookat = ((uint8_t*)base) + interval / 2;
+    int cmp = memcmp( lookat, key, compare_size );
+    if(cmp == 0 ) {
+      base = lookat;
+      break;
     }
-
-    mc >>= 1;
-    lookat = ((int8_t*)base) + member_size * (mc >> 1);
-  }
-
-  *exactmatch = 0;
-  return (void*)lookat;
-}
-
-ot_peer *binary_search_peer( const ot_peer * const peer, const ot_peer * base, const size_t member_count, int *exactmatch ) {
-  size_t   mc = member_count;
-  const ot_peer *lookat = base + (mc >> 1);
-  *exactmatch = 1;
-
-  while( mc ) {
-    int32_t cmp = memcmp(lookat,peer,OT_PEER_COMPARE_SIZE );
-    if(cmp == 0) return (ot_peer*)lookat;
-
-    if (cmp < 0) {
-      base = lookat + 1;
-      --mc;
+    if(cmp < 0) {
+      base = lookat + member_size;
+      interval -= member_size;
     }
-
-    mc >>= 1;
-    lookat = base + (mc >> 1);
+    interval /= 2;
   }
 
-  *exactmatch = 0;
-  return (ot_peer*)lookat;
+  *exactmatch = interval;
+  return (void*)base;
 }
 
-
 static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) {
   unsigned int hash = 5381, i = OT_PEER_COMPARE_SIZE;
   uint8_t *p = (uint8_t*)peer;
@@ -112,7 +88,7 @@ ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exac
   /* 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 );
-  match = binary_search_peer( peer, vector->data, vector->size, exactmatch );
+  match = (ot_peer*)binary_search( peer, vector->data, vector->size, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, exactmatch );
 
   if( *exactmatch ) return match;
 
@@ -148,7 +124,7 @@ int vector_remove_peer( ot_vector *vector, ot_peer *peer ) {
     vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
 
   end = ((ot_peer*)vector->data) + vector->size;
-  match = binary_search_peer( peer, vector->data, vector->size,  &exactmatch );
+  match = (ot_peer*)binary_search( peer, vector->data, vector->size, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, &exactmatch );
   if( !exactmatch ) return 0;
 
   exactmatch = ( OT_PEERFLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1;
-- 
cgit v1.2.3