summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorerdgeist <>2009-08-26 17:44:03 +0000
committererdgeist <>2009-08-26 17:44:03 +0000
commit0c8a17cbef002b60b7e458f110f9d930d17aa73e (patch)
tree022d3750f96d0a038d2a4b2349664ddd95cf5e3b
parent6c51fca9a1a657918ed66ea1154419a378515e0f (diff)
Optimize binary_search function
-rw-r--r--ot_vector.c58
1 files 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 @@
6/* System */ 6/* System */
7#include <stdlib.h> 7#include <stdlib.h>
8#include <string.h> 8#include <string.h>
9#include <strings.h>
9#include <stdint.h> 10#include <stdint.h>
10 11
11/* Opentracker */ 12/* Opentracker */
@@ -26,51 +27,26 @@ static int vector_compare_peer(const void *peer1, const void *peer2 ) {
26*/ 27*/
27void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, 28void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size,
28 size_t compare_size, int *exactmatch ) { 29 size_t compare_size, int *exactmatch ) {
29 size_t mc = member_count; 30 size_t interval = member_count * member_size;
30 int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1); 31
31 *exactmatch = 1; 32 while( interval ) {
32 33 uint8_t *lookat = ((uint8_t*)base) + interval / 2;
33 while( mc ) { 34 int cmp = memcmp( lookat, key, compare_size );
34 int32_t cmp = memcmp( lookat, key, compare_size ); 35 if(cmp == 0 ) {
35 if( cmp == 0 ) 36 base = lookat;
36 return (void *)lookat; 37 break;
37
38 if (cmp < 0) {
39 base = (void*)(lookat + member_size);
40 --mc;
41 } 38 }
42 39 if(cmp < 0) {
43 mc >>= 1; 40 base = lookat + member_size;
44 lookat = ((int8_t*)base) + member_size * (mc >> 1); 41 interval -= member_size;
45 }
46
47 *exactmatch = 0;
48 return (void*)lookat;
49}
50
51ot_peer *binary_search_peer( const ot_peer * const peer, const ot_peer * base, const size_t member_count, int *exactmatch ) {
52 size_t mc = member_count;
53 const ot_peer *lookat = base + (mc >> 1);
54 *exactmatch = 1;
55
56 while( mc ) {
57 int32_t cmp = memcmp(lookat,peer,OT_PEER_COMPARE_SIZE );
58 if(cmp == 0) return (ot_peer*)lookat;
59
60 if (cmp < 0) {
61 base = lookat + 1;
62 --mc;
63 } 42 }
64 43 interval /= 2;
65 mc >>= 1;
66 lookat = base + (mc >> 1);
67 } 44 }
68 45
69 *exactmatch = 0; 46 *exactmatch = interval;
70 return (ot_peer*)lookat; 47 return (void*)base;
71} 48}
72 49
73
74static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) { 50static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) {
75 unsigned int hash = 5381, i = OT_PEER_COMPARE_SIZE; 51 unsigned int hash = 5381, i = OT_PEER_COMPARE_SIZE;
76 uint8_t *p = (uint8_t*)peer; 52 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
112 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 88 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
113 if( vector->space < vector->size ) 89 if( vector->space < vector->size )
114 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 90 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
115 match = binary_search_peer( peer, vector->data, vector->size, exactmatch ); 91 match = (ot_peer*)binary_search( peer, vector->data, vector->size, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, exactmatch );
116 92
117 if( *exactmatch ) return match; 93 if( *exactmatch ) return match;
118 94
@@ -148,7 +124,7 @@ int vector_remove_peer( ot_vector *vector, ot_peer *peer ) {
148 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 124 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
149 125
150 end = ((ot_peer*)vector->data) + vector->size; 126 end = ((ot_peer*)vector->data) + vector->size;
151 match = binary_search_peer( peer, vector->data, vector->size, &exactmatch ); 127 match = (ot_peer*)binary_search( peer, vector->data, vector->size, sizeof(ot_peer), OT_PEER_COMPARE_SIZE, &exactmatch );
152 if( !exactmatch ) return 0; 128 if( !exactmatch ) return 0;
153 129
154 exactmatch = ( OT_PEERFLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1; 130 exactmatch = ( OT_PEERFLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1;