Revision 16ae4927 topology.c

View differences:

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