diff options
Diffstat (limited to 'ot_vector.c')
-rw-r--r-- | ot_vector.c | 70 |
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 | ||
19 | static int vector_compare_peer(const void *peer1, const void *peer2 ) { | 23 | static 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 | */ |
32 | void *binary_search( const void * const key, const void * base, const size_t member_count, const size_t member_size, | 35 | void *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 | ||
64 | ot_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 | |||
61 | static uint8_t vector_hash_peer( ot_peer *peer, int bucket_count ) { | 90 | static 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 */ | ||
98 | ot_peer *vector_find_or_insert_peer( ot_vector *vector, ot_peer *peer, int *exactmatch ) { | 125 | ot_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; |