Revision 16ae4927 topology.c
topology.c | ||
---|---|---|
22 | 22 |
#include "compatibility/timer.h" |
23 | 23 |
|
24 | 24 |
#include "topology.h" |
25 |
#include "nodeid_set.h" |
|
25 | 26 |
#include "streaming.h" |
26 | 27 |
#include "dbg.h" |
27 | 28 |
#include "measures.h" |
... | ... | |
215 | 216 |
return (desiredness(n) == 1); |
216 | 217 |
} |
217 | 218 |
|
218 |
// The usual shuffle |
|
219 |
static void shuffle(void *base, size_t nmemb, size_t size) { |
|
220 |
int i; |
|
221 |
unsigned char t[size]; |
|
222 |
unsigned char* b = base; |
|
223 |
|
|
224 |
for (i = nmemb - 1; i > 0; i--) { |
|
225 |
int newpos = (rand()/(RAND_MAX + 1.0)) * (i + 1); |
|
226 |
memcpy(t, b + size * newpos, size); |
|
227 |
memmove(b + size * newpos, b + size * i, size); |
|
228 |
memcpy(b + size * i, t, size); |
|
229 |
} |
|
230 |
} |
|
231 |
|
|
232 |
static void nidset_shuffle(const struct nodeID **base, size_t nmemb) { |
|
233 |
shuffle(base, nmemb, sizeof(struct nodeID *)); |
|
234 |
} |
|
235 |
|
|
236 |
static int nidset_filter(const struct nodeID **dst, size_t *dst_size, const struct nodeID **src, size_t src_size, bool(*f)(const struct nodeID *)) { |
|
237 |
size_t i; |
|
238 |
size_t max_size = *dst_size; |
|
239 |
*dst_size = 0; |
|
240 |
|
|
241 |
for (i = 0; i < src_size; i++) { |
|
242 |
if (f(src[i])) { |
|
243 |
if (*dst_size < max_size) { |
|
244 |
dst[(*dst_size)++] = src[i]; |
|
245 |
} else { |
|
246 |
return -1; |
|
247 |
} |
|
248 |
} |
|
249 |
} |
|
250 |
|
|
251 |
return 0; |
|
252 |
} |
|
253 |
|
|
254 |
// B \ A |
|
255 |
static int nidset_complement(const struct nodeID **dst, size_t *dst_size, const struct nodeID **bs, size_t bs_size, const struct nodeID **as, size_t as_size) { |
|
256 |
size_t i, j; |
|
257 |
size_t max_size = *dst_size; |
|
258 |
*dst_size = 0; |
|
259 |
|
|
260 |
for (i = 0; i < bs_size; i++) { |
|
261 |
for (j = 0; j < as_size; j++) { |
|
262 |
if (nodeid_equal(bs[i], as[j])) { |
|
263 |
break; |
|
264 |
} |
|
265 |
} |
|
266 |
if (j >= as_size) { |
|
267 |
if (*dst_size < max_size) { |
|
268 |
dst[(*dst_size)++] = bs[i]; |
|
269 |
} else { |
|
270 |
return -1; |
|
271 |
} |
|
272 |
} |
|
273 |
} |
|
274 |
|
|
275 |
return 0; |
|
276 |
} |
|
277 |
|
|
278 |
static bool nidset_find(size_t *i, const struct nodeID **ids, size_t ids_size, const struct nodeID *id) { |
|
279 |
for (*i = 0; *i < ids_size; (*i)++) { |
|
280 |
if (nodeid_equal(ids[*i],id)) { |
|
281 |
return true; |
|
282 |
} |
|
283 |
} |
|
284 |
return false; |
|
285 |
} |
|
286 |
|
|
287 |
static int nidset_add(const struct nodeID **dst, size_t *dst_size, const struct nodeID **as, size_t as_size, const struct nodeID **bs, size_t bs_size) { |
|
288 |
int r; |
|
289 |
size_t i; |
|
290 |
size_t max_size = *dst_size; |
|
291 |
|
|
292 |
i = MIN(as_size, max_size); |
|
293 |
memcpy(dst, as, i * sizeof(struct nodeID*)); |
|
294 |
*dst_size = i; |
|
295 |
if (i < as_size) return -1; |
|
296 |
|
|
297 |
max_size -= *dst_size; |
|
298 |
r = nidset_complement(dst + *dst_size, &max_size, bs, bs_size, as, as_size); |
|
299 |
*dst_size += max_size; |
|
300 |
|
|
301 |
return r; |
|
302 |
} |
|
303 |
|
|
304 |
static int nidset_add_i(const struct nodeID **dst, size_t *dst_size, size_t max_size, const struct nodeID **as, size_t as_size) { |
|
305 |
int r; |
|
306 |
|
|
307 |
max_size -= *dst_size; |
|
308 |
r = nidset_complement(dst + *dst_size, &max_size, as, as_size, dst, *dst_size); |
|
309 |
*dst_size += max_size; |
|
310 |
|
|
311 |
return r; |
|
312 |
} |
|
313 |
|
|
314 | 219 |
// currently it just makes the peerset grow |
315 | 220 |
void update_peers(struct nodeID *from, const uint8_t *buff, int len) |
316 | 221 |
{ |
Also available in: Unified diff