iofbird / bird2.0.1 / nest / aset.c @ 6b3f1a54
History  View  Annotate  Download (11.4 KB)
1 
/*


2 
* BIRD  Set/Communitylist Operations

3 
*

4 
* (c) 2000 Martin Mares <mj@ucw.cz>

5 
* (c) 2000 Pavel Machek <pavel@ucw.cz>

6 
*

7 
* Can be freely distributed and used under the terms of the GNU GPL.

8 
*/

9  
10 
#include <stdlib.h> 
11  
12 
#include "nest/bird.h" 
13 
#include "nest/route.h" 
14 
#include "nest/attrs.h" 
15 
#include "lib/resource.h" 
16 
#include "lib/string.h" 
17  
18 
/**

19 
* int_set_format  format an &set for printing

20 
* @set: set attribute to be formatted

21 
* @way: style of format (0 for router ID list, 1 for community list)

22 
* @from: starting position in set

23 
* @buf: destination buffer

24 
* @size: size of buffer

25 
*

26 
* This function takes a set attribute and formats it. @way specifies

27 
* the style of format (router ID / community). @from argument can be

28 
* used to specify the first printed value for the purpose of printing

29 
* untruncated sets even with smaller buffers. If the output fits in

30 
* the buffer, 0 is returned, otherwise the position of the first not

31 
* printed item is returned. This value can be used as @from argument

32 
* in subsequent calls. If truncated output suffices, 1 can be

33 
* instead used as @from, in that case " ..." is eventually added at

34 
* the buffer to indicate truncation.

35 
*/

36 
int

37 
int_set_format(struct adata *set, int way, int from, byte *buf, uint size) 
38 
{ 
39 
u32 *z = (u32 *) set>data; 
40 
byte *end = buf + size  24;

41 
int from2 = MAX(from, 0); 
42 
int to = set>length / 4; 
43 
int i;

44  
45 
for (i = from2; i < to; i++)

46 
{ 
47 
if (buf > end)

48 
{ 
49 
if (from < 0) 
50 
strcpy(buf, " ...");

51 
else

52 
*buf = 0;

53 
return i;

54 
} 
55  
56 
if (i > from2)

57 
*buf++ = ' ';

58  
59 
if (way)

60 
buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff); 
61 
else

62 
buf += bsprintf(buf, "%R", z[i]);

63 
} 
64 
*buf = 0;

65 
return 0; 
66 
} 
67  
68 
int

69 
ec_format(byte *buf, u64 ec) 
70 
{ 
71 
u32 type, key, val; 
72 
char tbuf[16], *kind; 
73  
74 
type = ec >> 48;

75 
switch (type & 0xf0ff) 
76 
{ 
77 
case EC_RT: kind = "rt"; break; 
78 
case EC_RO: kind = "ro"; break; 
79  
80 
default:

81 
kind = tbuf; 
82 
bsprintf(kind, "unknown 0x%x", type);

83 
} 
84  
85 
switch (ec >> 56) 
86 
{ 
87 
/* RFC 4360 3.1. TwoOctet AS Specific Extended Community */

88 
case 0x00: 
89 
case 0x40: 
90 
key = (ec >> 32) & 0xFFFF; 
91 
val = ec; 
92 
return bsprintf(buf, "(%s, %u, %u)", kind, key, val); 
93  
94 
/* RFC 4360 3.2. IPv4 Address Specific Extended Community */

95 
case 0x01: 
96 
case 0x41: 
97 
key = ec >> 16;

98 
val = ec & 0xFFFF;

99 
return bsprintf(buf, "(%s, %R, %u)", kind, key, val); 
100  
101 
/* RFC 5668 4Octet AS Specific BGP Extended Community */

102 
case 0x02: 
103 
case 0x42: 
104 
key = ec >> 16;

105 
val = ec & 0xFFFF;

106 
return bsprintf(buf, "(%s, %u, %u)", kind, key, val); 
107  
108 
/* Generic format for unknown kinds of extended communities */

109 
default:

110 
key = ec >> 32;

111 
val = ec; 
112 
return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val); 
113 
} 
114  
115 
} 
116  
117 
int

118 
ec_set_format(struct adata *set, int from, byte *buf, uint size) 
119 
{ 
120 
u32 *z = int_set_get_data(set); 
121 
byte *end = buf + size  64;

122 
int from2 = MAX(from, 0); 
123 
int to = int_set_get_size(set);

124 
int i;

125  
126 
for (i = from2; i < to; i += 2) 
127 
{ 
128 
if (buf > end)

129 
{ 
130 
if (from < 0) 
131 
strcpy(buf, " ...");

132 
else

133 
*buf = 0;

134 
return i;

135 
} 
136  
137 
if (i > from2)

138 
*buf++ = ' ';

139  
140 
buf += ec_format(buf, ec_get(z, i)); 
141 
} 
142 
*buf = 0;

143 
return 0; 
144 
} 
145  
146 
int

147 
lc_format(byte *buf, lcomm lc) 
148 
{ 
149 
return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); 
150 
} 
151  
152 
int

153 
lc_set_format(struct adata *set, int from, byte *buf, uint bufsize) 
154 
{ 
155 
u32 *d = (u32 *) set>data; 
156 
byte *end = buf + bufsize  64;

157 
int from2 = MAX(from, 0); 
158 
int to = set>length / 4; 
159 
int i;

160  
161 
for (i = from2; i < to; i += 3) 
162 
{ 
163 
if (buf > end)

164 
{ 
165 
if (from < 0) 
166 
strcpy(buf, "...");

167 
else

168 
buf[1] = 0; 
169 
return i;

170 
} 
171  
172 
buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); 
173 
*buf++ = ' ';

174 
} 
175  
176 
if (i != from2)

177 
buf; 
178  
179 
*buf = 0;

180 
return 0; 
181 
} 
182  
183 
int

184 
int_set_contains(struct adata *list, u32 val)

185 
{ 
186 
if (!list)

187 
return 0; 
188  
189 
u32 *l = (u32 *) list>data; 
190 
int len = int_set_get_size(list);

191 
int i;

192  
193 
for (i = 0; i < len; i++) 
194 
if (*l++ == val)

195 
return 1; 
196  
197 
return 0; 
198 
} 
199  
200 
int

201 
ec_set_contains(struct adata *list, u64 val)

202 
{ 
203 
if (!list)

204 
return 0; 
205  
206 
u32 *l = int_set_get_data(list); 
207 
int len = int_set_get_size(list);

208 
u32 eh = ec_hi(val); 
209 
u32 el = ec_lo(val); 
210 
int i;

211  
212 
for (i=0; i < len; i += 2) 
213 
if (l[i] == eh && l[i+1] == el) 
214 
return 1; 
215  
216 
return 0; 
217 
} 
218  
219 
int

220 
lc_set_contains(struct adata *list, lcomm val)

221 
{ 
222 
if (!list)

223 
return 0; 
224  
225 
u32 *l = int_set_get_data(list); 
226 
int len = int_set_get_size(list);

227 
int i;

228  
229 
for (i = 0; i < len; i += 3) 
230 
if (lc_match(l, i, val))

231 
return 1; 
232  
233 
return 0; 
234 
} 
235  
236 
struct adata *

237 
int_set_prepend(struct linpool *pool, struct adata *list, u32 val) 
238 
{ 
239 
struct adata *res;

240 
int len;

241  
242 
if (int_set_contains(list, val))

243 
return list;

244  
245 
len = list ? list>length : 0;

246 
res = lp_alloc(pool, sizeof(struct adata) + len + 4); 
247 
res>length = len + 4;

248  
249 
if (list)

250 
memcpy(res>data + 4, list>data, list>length);

251  
252 
* (u32 *) res>data = val; 
253  
254 
return res;

255 
} 
256  
257 
struct adata *

258 
int_set_add(struct linpool *pool, struct adata *list, u32 val) 
259 
{ 
260 
struct adata *res;

261 
int len;

262  
263 
if (int_set_contains(list, val))

264 
return list;

265  
266 
len = list ? list>length : 0;

267 
res = lp_alloc(pool, sizeof(struct adata) + len + 4); 
268 
res>length = len + 4;

269  
270 
if (list)

271 
memcpy(res>data, list>data, list>length); 
272  
273 
* (u32 *) (res>data + len) = val; 
274  
275 
return res;

276 
} 
277  
278 
struct adata *

279 
ec_set_add(struct linpool *pool, struct adata *list, u64 val) 
280 
{ 
281 
if (ec_set_contains(list, val))

282 
return list;

283  
284 
int olen = list ? list>length : 0; 
285 
struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8); 
286 
res>length = olen + 8;

287  
288 
if (list)

289 
memcpy(res>data, list>data, list>length); 
290  
291 
u32 *l = (u32 *) (res>data + olen); 
292 
l[0] = ec_hi(val);

293 
l[1] = ec_lo(val);

294  
295 
return res;

296 
} 
297  
298 
struct adata *

299 
lc_set_add(struct linpool *pool, struct adata *list, lcomm val) 
300 
{ 
301 
if (lc_set_contains(list, val))

302 
return list;

303  
304 
int olen = list ? list>length : 0; 
305 
struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH); 
306 
res>length = olen + LCOMM_LENGTH; 
307  
308 
if (list)

309 
memcpy(res>data, list>data, list>length); 
310  
311 
lc_put((u32 *) (res>data + olen), val); 
312  
313 
return res;

314 
} 
315  
316 
struct adata *

317 
int_set_del(struct linpool *pool, struct adata *list, u32 val) 
318 
{ 
319 
if (!int_set_contains(list, val))

320 
return list;

321  
322 
struct adata *res;

323 
res = lp_alloc(pool, sizeof(struct adata) + list>length  4); 
324 
res>length = list>length  4;

325  
326 
u32 *l = int_set_get_data(list); 
327 
u32 *k = int_set_get_data(res); 
328 
int len = int_set_get_size(list);

329 
int i;

330  
331 
for (i = 0; i < len; i++) 
332 
if (l[i] != val)

333 
*k++ = l[i]; 
334  
335 
return res;

336 
} 
337  
338 
struct adata *

339 
ec_set_del(struct linpool *pool, struct adata *list, u64 val) 
340 
{ 
341 
if (!ec_set_contains(list, val))

342 
return list;

343  
344 
struct adata *res;

345 
res = lp_alloc(pool, sizeof(struct adata) + list>length  8); 
346 
res>length = list>length  8;

347  
348 
u32 *l = int_set_get_data(list); 
349 
u32 *k = int_set_get_data(res); 
350 
int len = int_set_get_size(list);

351 
u32 eh = ec_hi(val); 
352 
u32 el = ec_lo(val); 
353 
int i;

354  
355 
for (i=0; i < len; i += 2) 
356 
if (! (l[i] == eh && l[i+1] == el)) 
357 
{ 
358 
*k++ = l[i]; 
359 
*k++ = l[i+1];

360 
} 
361  
362 
return res;

363 
} 
364  
365 
struct adata *

366 
lc_set_del(struct linpool *pool, struct adata *list, lcomm val) 
367 
{ 
368 
if (!lc_set_contains(list, val))

369 
return list;

370  
371 
struct adata *res;

372 
res = lp_alloc(pool, sizeof(struct adata) + list>length  LCOMM_LENGTH); 
373 
res>length = list>length  LCOMM_LENGTH; 
374  
375 
u32 *l = int_set_get_data(list); 
376 
u32 *k = int_set_get_data(res); 
377 
int len = int_set_get_size(list);

378 
int i;

379  
380 
for (i=0; i < len; i += 3) 
381 
if (! lc_match(l, i, val))

382 
k = lc_copy(k, l+i); 
383  
384 
return res;

385 
} 
386  
387 
struct adata *

388 
int_set_union(struct linpool *pool, struct adata *l1, struct adata *l2) 
389 
{ 
390 
if (!l1)

391 
return l2;

392 
if (!l2)

393 
return l1;

394  
395 
struct adata *res;

396 
int len = int_set_get_size(l2);

397 
u32 *l = int_set_get_data(l2); 
398 
u32 tmp[len]; 
399 
u32 *k = tmp; 
400 
int i;

401  
402 
for (i = 0; i < len; i++) 
403 
if (!int_set_contains(l1, l[i]))

404 
*k++ = l[i]; 
405  
406 
if (k == tmp)

407 
return l1;

408  
409 
len = (k  tmp) * 4;

410 
res = lp_alloc(pool, sizeof(struct adata) + l1>length + len); 
411 
res>length = l1>length + len; 
412 
memcpy(res>data, l1>data, l1>length); 
413 
memcpy(res>data + l1>length, tmp, len); 
414 
return res;

415 
} 
416  
417 
struct adata *

418 
ec_set_union(struct linpool *pool, struct adata *l1, struct adata *l2) 
419 
{ 
420 
if (!l1)

421 
return l2;

422 
if (!l2)

423 
return l1;

424  
425 
struct adata *res;

426 
int len = int_set_get_size(l2);

427 
u32 *l = int_set_get_data(l2); 
428 
u32 tmp[len]; 
429 
u32 *k = tmp; 
430 
int i;

431  
432 
for (i = 0; i < len; i += 2) 
433 
if (!ec_set_contains(l1, ec_get(l, i)))

434 
{ 
435 
*k++ = l[i]; 
436 
*k++ = l[i+1];

437 
} 
438  
439 
if (k == tmp)

440 
return l1;

441  
442 
len = (k  tmp) * 4;

443 
res = lp_alloc(pool, sizeof(struct adata) + l1>length + len); 
444 
res>length = l1>length + len; 
445 
memcpy(res>data, l1>data, l1>length); 
446 
memcpy(res>data + l1>length, tmp, len); 
447 
return res;

448 
} 
449  
450 
struct adata *

451 
lc_set_union(struct linpool *pool, struct adata *l1, struct adata *l2) 
452 
{ 
453 
if (!l1)

454 
return l2;

455 
if (!l2)

456 
return l1;

457  
458 
struct adata *res;

459 
int len = int_set_get_size(l2);

460 
u32 *l = int_set_get_data(l2); 
461 
u32 tmp[len]; 
462 
u32 *k = tmp; 
463 
int i;

464  
465 
for (i = 0; i < len; i += 3) 
466 
if (!lc_set_contains(l1, lc_get(l, i)))

467 
k = lc_copy(k, l+i); 
468  
469 
if (k == tmp)

470 
return l1;

471  
472 
len = (k  tmp) * 4;

473 
res = lp_alloc(pool, sizeof(struct adata) + l1>length + len); 
474 
res>length = l1>length + len; 
475 
memcpy(res>data, l1>data, l1>length); 
476 
memcpy(res>data + l1>length, tmp, len); 
477 
return res;

478 
} 
479  
480  
481 
struct adata *

482 
ec_set_del_nontrans(struct linpool *pool, struct adata *set) 
483 
{ 
484 
adata *res = lp_alloc_adata(pool, set>length); 
485 
u32 *src = int_set_get_data(set); 
486 
u32 *dst = int_set_get_data(res); 
487 
int len = int_set_get_size(set);

488 
int i;

489  
490 
/* Remove nontransitive communities (EC_TBIT set) */

491 
for (i = 0; i < len; i += 2) 
492 
{ 
493 
if (src[i] & EC_TBIT)

494 
continue;

495  
496 
*dst++ = src[i]; 
497 
*dst++ = src[i+1];

498 
} 
499  
500 
res>length = ((byte *) dst)  res>data; 
501  
502 
return res;

503 
} 
504  
505 
static int 
506 
int_set_cmp(const void *X, const void *Y) 
507 
{ 
508 
const u32 *x = X, *y = Y;

509 
return (*x < *y) ? 1 : (*x > *y) ? 1 : 0; 
510 
} 
511  
512 
struct adata *

513 
int_set_sort(struct linpool *pool, struct adata *src) 
514 
{ 
515 
struct adata *dst = lp_alloc_adata(pool, src>length);

516 
memcpy(dst>data, src>data, src>length); 
517 
qsort(dst>data, dst>length / 4, 4, int_set_cmp); 
518 
return dst;

519 
} 
520  
521  
522 
static int 
523 
ec_set_cmp(const void *X, const void *Y) 
524 
{ 
525 
u64 x = ec_get(X, 0);

526 
u64 y = ec_get(Y, 0);

527 
return (x < y) ? 1 : (x > y) ? 1 : 0; 
528 
} 
529  
530 
struct adata *

531 
ec_set_sort(struct linpool *pool, struct adata *src) 
532 
{ 
533 
struct adata *dst = lp_alloc_adata(pool, src>length);

534 
memcpy(dst>data, src>data, src>length); 
535 
qsort(dst>data, dst>length / 8, 8, ec_set_cmp); 
536 
return dst;

537 
} 
538  
539 
void

540 
ec_set_sort_x(struct adata *set)

541 
{ 
542 
/* Sort in place */

543 
qsort(set>data, set>length / 8, 8, ec_set_cmp); 
544 
} 
545  
546  
547 
static int 
548 
lc_set_cmp(const void *X, const void *Y) 
549 
{ 
550 
const u32 *x = X, *y = Y;

551 
if (x[0] != y[0]) 
552 
return (x[0] > y[0]) ? 1 : 1; 
553 
if (x[1] != y[1]) 
554 
return (x[1] > y[1]) ? 1 : 1; 
555 
if (x[2] != y[2]) 
556 
return (x[2] > y[2]) ? 1 : 1; 
557 
return 0; 
558 
} 
559  
560 
struct adata *

561 
lc_set_sort(struct linpool *pool, struct adata *src) 
562 
{ 
563 
struct adata *dst = lp_alloc_adata(pool, src>length);

564 
memcpy(dst>data, src>data, src>length); 
565 
qsort(dst>data, dst>length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp); 
566 
return dst;

567 
} 