streamers / nodeid_set.c @ 3c2cbe48
History  View  Annotate  Download (2.53 KB)
1 
/*


2 
* Copyright (c) 2010 Csaba Kiraly

3 
* Copyright (c) 2010 Luca Abeni

4 
*

5 
* This is free software; see gpl3.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 
static void shuffle(void *base, int nmemb, int 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, int nmemb) { 
31 
shuffle(base, nmemb, sizeof(struct nodeID *)); 
32 
} 
33  
34 
int nidset_filter(const struct nodeID **dst, int *dst_size, const struct nodeID **src, int src_size, bool(*f)(const struct nodeID *)) { 
35 
int i;

36 
int 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, int *dst_size, const struct nodeID **bs, int bs_size, const struct nodeID **as, int as_size) { 
54 
int i, j;

55 
int 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(int *i, const struct nodeID **ids, int 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, int *dst_size, const struct nodeID **as, int as_size, const struct nodeID **bs, int bs_size) { 
86 
int r;

87 
int i;

88 
int 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, int *dst_size, int max_size, const struct nodeID **as, int 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 
} 