summaryrefslogtreecommitdiff
path: root/ot_vector.c
diff options
context:
space:
mode:
authorerdgeist <>2008-12-05 20:36:00 +0000
committererdgeist <>2008-12-05 20:36:00 +0000
commit08d9c342d41d8714ba8f3c7e8e2199e77c4bdabc (patch)
tree07faa404a8793b062e0e925828c2497822635741 /ot_vector.c
parent23be5c4d55d0bf028619064e8d5700dd1af6e1a3 (diff)
Add specialized vector functions to handle peers in sorted lists
Assume that compare_size is a mulptiple of 4 in all non-specialized cases and load int32_t to compare.
Diffstat (limited to 'ot_vector.c')
-rw-r--r--ot_vector.c70
1 files changed, 58 insertions, 12 deletions
diff --git a/ot_vector.c b/ot_vector.c
index 2862763..1738884 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -15,11 +15,14 @@
15 15
16/* Libowfat */ 16/* Libowfat */
17#include "uint32.h" 17#include "uint32.h"
18#include "uint16.h"
19
20#define READ16(addr,offs) ((int16_t)uint16_read((offs)+(uint8_t*)(addr)))
21#define READ32(addr,offs) ((int32_t)uint32_read((offs)+(uint8_t*)(addr)))
18 22
19static int vector_compare_peer(const void *peer1, const void *peer2 ) { 23static int vector_compare_peer(const void *peer1, const void *peer2 ) {
20 int32_t cmp = (int32_t)uint32_read(peer1) - (int32_t)uint32_read(peer2); 24 int32_t cmp = READ32(peer1,0) - READ32(peer2,0);
21 if (cmp == 0) cmp = ((int8_t*)peer1)[4] - ((int8_t*)peer2)[4]; 25 if (cmp == 0) cmp = READ16(peer1,4) - READ16(peer2,4);
22 if (cmp == 0) cmp = ((int8_t*)peer1)[5] - ((int8_t*)peer2)[5];
23 return cmp; 26 return cmp;
24} 27}
25 28
@@ -27,20 +30,20 @@ static int vector_compare_peer(const void *peer1, const void *peer2 ) {
27 no exact match is found. In that case it sets exactmatch 0 and gives 30 no exact match is found. In that case it sets exactmatch 0 and gives
28 calling functions the chance to insert data 31 calling functions the chance to insert data
29 32
30 NOTE: Minimal compare_size is 4. 33 NOTE: Minimal compare_size is 4, member_size must be a multiple of 4
31*/ 34*/
32void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, 35void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size,
33 size_t compare_size, int *exactmatch ) { 36 size_t compare_size, int *exactmatch ) {
34 size_t offs, mc = member_count; 37 size_t offs, mc = member_count;
35 int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1); 38 int8_t *lookat = ((int8_t*)base) + member_size * (mc >> 1);
36 int32_t key_cache = (int32_t)uint32_read(key); 39 int32_t key_cache = READ32(key,0);
37 *exactmatch = 1; 40 *exactmatch = 1;
38 41
39 while( mc ) { 42 while( mc ) {
40 int32_t cmp = key_cache - (int32_t)uint32_read(lookat); 43 int32_t cmp = key_cache - (int32_t)uint32_read(lookat);
41 if (cmp == 0) { 44 if (cmp == 0) {
42 for( offs = 4; cmp == 0 && offs < compare_size; ++offs ) 45 for( offs = 4; cmp == 0 && offs < compare_size; offs += 4 )
43 cmp = ((int8_t*)key)[offs] - lookat[offs]; 46 cmp = READ32(key,offs) - READ32(lookat,offs);
44 if( cmp == 0 ) 47 if( cmp == 0 )
45 return (void *)lookat; 48 return (void *)lookat;
46 } 49 }
@@ -58,6 +61,32 @@ void *binary_search( const void * const key, const void * base, const size_t mem
58 return (void*)lookat; 61 return (void*)lookat;
59} 62}
60 63
64ot_peer *binary_search_peer( const ot_peer * const peer, const ot_peer * base, const size_t member_count, int *exactmatch ) {
65 size_t mc = member_count;
66 const ot_peer *lookat = base + (mc >> 1);
67 int32_t low = READ32(peer,0);
68 int16_t high = READ16(peer,4);
69 *exactmatch = 1;
70
71 while( mc ) {
72 int32_t cmp = low - READ32(lookat,0);
73 if(cmp == 0) cmp = high - READ16(lookat,4);
74 if(cmp == 0) return (ot_peer*)lookat;
75
76 if (cmp < 0) {
77 base = lookat + 1;
78 --mc;
79 }
80
81 mc >>= 1;
82 lookat = base + (mc >> 1);
83 }
84
85 *exactmatch = 0;
86 return (ot_peer*)lookat;
87}
88
89
61static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) { 90static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) {
62 unsigned int hash = 5381, i = 6; 91 unsigned int hash = 5381, i = 6;
63 uint8_t *p = (uint8_t*)peer; 92 uint8_t *p = (uint8_t*)peer;
@@ -93,13 +122,30 @@ void *vector_find_or_insert( ot_vector *vector, void *key, size_t member_size, s
93 return match; 122 return match;
94} 123}
95 124
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 ) { 125ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exactmatch ) {
126 ot_peer *match;
127
99 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ 128 /* If space is zero but size is set, we're dealing with a list of vector->size buckets */
100 if( vector->space < vector->size ) 129 if( vector->space < vector->size )
101 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 130 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 ); 131 match = binary_search_peer( peer, vector->data, vector->size, exactmatch );
132
133 if( *exactmatch ) return match;
134
135 if( vector->size + 1 > vector->space ) {
136 size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS;
137 ot_peer *new_data = realloc( vector->data, new_space * sizeof(ot_peer) );
138 if( !new_data ) return NULL;
139 /* Adjust pointer if it moved by realloc */
140 match = new_data + (match - (ot_peer*)vector->data);
141
142 vector->data = new_data;
143 vector->space = new_space;
144 }
145 memmove( match + 1, match, sizeof(ot_peer) * ( ((ot_peer*)vector->data) + vector->size - match ) );
146
147 vector->size++;
148 return match;
103} 149}
104 150
105/* This is the non-generic delete from vector-operation specialized for peers in pools. 151/* This is the non-generic delete from vector-operation specialized for peers in pools.
@@ -118,7 +164,7 @@ int vector_remove_peer( ot_vector *vector, ot_peer *peer ) {
118 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size ); 164 vector = ((ot_vector*)vector->data) + vector_hash_peer(peer, vector->size );
119 165
120 end = ((ot_peer*)vector->data) + vector->size; 166 end = ((ot_peer*)vector->data) + vector->size;
121 match = binary_search( peer, vector->data, vector->size, sizeof( ot_peer ), OT_PEER_COMPARE_SIZE, &exactmatch ); 167 match = binary_search_peer( peer, vector->data, vector->size, &exactmatch );
122 if( !exactmatch ) return 0; 168 if( !exactmatch ) return 0;
123 169
124 exactmatch = ( OT_FLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1; 170 exactmatch = ( OT_FLAG( match ) & PEER_FLAG_SEEDING ) ? 2 : 1;