Revision 16ae4927

View differences:

Makefile
74 74
OBJS += topology-ALTO.o
75 75
OBJS += config.o
76 76
else
77
OBJS += topology.o
77
OBJS += topology.o nodeid_set.o
78 78
endif
79 79

  
80 80
OBJS += chunk_signaling.o
nodeid_set.c
1
/*
2
 *  Copyright (c) 2010 Csaba Kiraly
3
 *  Copyright (c) 2010 Luca Abeni
4
 *
5
 *  This is free software; see gpl-3.0.txt
6
 */
7
#include <string.h>
8
#include <stdlib.h>
9
#include <stdint.h>
10
#include <net_helper.h>
11

  
12
#include "nodeid_set.h"
13

  
14
#define MIN(A,B) (((A) < (B)) ? (A) : (B))
15

  
16
// The usual shuffle
17
void shuffle(void *base, size_t nmemb, size_t size) {
18
  int i;
19
  unsigned char t[size];
20
  unsigned char* b = base;
21

  
22
  for (i = nmemb - 1; i > 0; i--) {
23
    int newpos = (rand()/(RAND_MAX + 1.0)) * (i + 1);
24
    memcpy(t, b + size * newpos, size);
25
    memmove(b + size * newpos, b + size * i, size);
26
    memcpy(b + size * i, t, size);
27
  }
28
}
29

  
30
void nidset_shuffle(const struct nodeID **base, size_t nmemb) {
31
  shuffle(base, nmemb, sizeof(struct nodeID *));
32
}
33

  
34
int nidset_filter(const struct nodeID **dst, size_t *dst_size, const struct nodeID **src, size_t src_size, bool(*f)(const struct nodeID *)) {
35
  size_t i;
36
  size_t max_size = *dst_size;
37
  *dst_size = 0;
38

  
39
  for (i = 0; i < src_size; i++) {
40
    if (f(src[i])) {
41
      if (*dst_size < max_size) {
42
        dst[(*dst_size)++] = src[i];
43
      } else {
44
        return -1;
45
      }
46
    }
47
  }
48

  
49
  return 0;
50
}
51

  
52
// B \ A
53
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) {
54
  size_t i, j;
55
  size_t max_size = *dst_size;
56
  *dst_size = 0;
57

  
58
  for (i = 0; i < bs_size; i++) {
59
    for (j = 0; j < as_size; j++) {
60
      if (nodeid_equal(bs[i], as[j])) {
61
        break;
62
      }
63
    }
64
    if (j >= as_size) {
65
      if (*dst_size < max_size) {
66
        dst[(*dst_size)++] = bs[i];
67
      } else {
68
        return -1;
69
      }
70
    }
71
  }
72

  
73
  return 0;
74
}
75

  
76
bool nidset_find(size_t *i, const struct nodeID **ids, size_t ids_size, const struct nodeID *id) {
77
  for (*i = 0; *i < ids_size; (*i)++) {
78
    if (nodeid_equal(ids[*i],id)) {
79
      return true;
80
    }
81
  }
82
  return false;
83
}
84

  
85
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) {
86
  int r;
87
  size_t i;
88
  size_t max_size = *dst_size;
89

  
90
  i = MIN(as_size, max_size);
91
  memcpy(dst, as, i * sizeof(struct nodeID*));
92
  *dst_size = i;
93
  if (i < as_size) return -1;
94

  
95
  max_size -= *dst_size;
96
  r = nidset_complement(dst + *dst_size, &max_size, bs, bs_size, as, as_size);
97
  *dst_size += max_size;
98

  
99
  return r;
100
}
101

  
102
int nidset_add_i(const struct nodeID **dst, size_t *dst_size, size_t max_size, const struct nodeID **as, size_t as_size) {
103
  int r;
104

  
105
  max_size -= *dst_size;
106
  r = nidset_complement(dst + *dst_size, &max_size, as, as_size, dst, *dst_size);
107
  *dst_size += max_size;
108

  
109
  return r;
110
}
nodeid_set.h
1
/*
2
 *  Copyright (c) 2010 Csaba Kiraly
3
 *  Copyright (c) 2010 Luca Abeni
4
 *
5
 *  This is free software; see gpl-3.0.txt
6
 */
7

  
8
#ifndef NODEID_SET_H
9
#define NODEID_SET_H
10

  
11
#include <stdbool.h>
12

  
13
struct nodeID;
14

  
15
// The usual shuffle
16
void shuffle(void *base, size_t nmemb, size_t size);
17

  
18
void nidset_shuffle(const struct nodeID **base, size_t nmemb);
19

  
20
int nidset_filter(const struct nodeID **dst, size_t *dst_size, const struct nodeID **src, size_t src_size, bool(*f)(const struct nodeID *));
21

  
22
// B \ A
23
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);
24

  
25
bool nidset_find(size_t *i, const struct nodeID **ids, size_t ids_size, const struct nodeID *id);
26

  
27
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);
28

  
29
int nidset_add_i(const struct nodeID **dst, size_t *dst_size, size_t max_size, const struct nodeID **as, size_t as_size);
30

  
31
#endif	/* NODEID_SET_H */
32

  
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