1: /*
2: * BIRD -- Set/Community-list 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(const 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];
73: const char *kind;
74:
75: type = ec >> 48;
76: kind = ec_subtype_str(type & 0xf0ff);
77:
78: if (!kind) {
79: bsprintf(tbuf, "unknown 0x%x", type);
80: kind = tbuf;
81: }
82:
83: switch (ec >> 56)
84: {
85: /* RFC 4360 3.1. Two-Octet AS Specific Extended Community */
86: case 0x00:
87: case 0x40:
88: key = (ec >> 32) & 0xFFFF;
89: val = ec;
90: return bsprintf(buf, "(%s, %u, %u)", kind, key, val);
91:
92: /* RFC 4360 3.2. IPv4 Address Specific Extended Community */
93: case 0x01:
94: case 0x41:
95: key = ec >> 16;
96: val = ec & 0xFFFF;
97: return bsprintf(buf, "(%s, %R, %u)", kind, key, val);
98:
99: /* RFC 5668 4-Octet AS Specific BGP Extended Community */
100: case 0x02:
101: case 0x42:
102: key = ec >> 16;
103: val = ec & 0xFFFF;
104: return bsprintf(buf, "(%s, %u, %u)", kind, key, val);
105:
106: /* Generic format for unknown kinds of extended communities */
107: default:
108: key = ec >> 32;
109: val = ec;
110: return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val);
111: }
112:
113: }
114:
115: int
116: ec_set_format(const struct adata *set, int from, byte *buf, uint size)
117: {
118: u32 *z = int_set_get_data(set);
119: byte *end = buf + size - 64;
120: int from2 = MAX(from, 0);
121: int to = int_set_get_size(set);
122: int i;
123:
124: for (i = from2; i < to; i += 2)
125: {
126: if (buf > end)
127: {
128: if (from < 0)
129: strcpy(buf, " ...");
130: else
131: *buf = 0;
132: return i;
133: }
134:
135: if (i > from2)
136: *buf++ = ' ';
137:
138: buf += ec_format(buf, ec_get(z, i));
139: }
140: *buf = 0;
141: return 0;
142: }
143:
144: int
145: lc_format(byte *buf, lcomm lc)
146: {
147: return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2);
148: }
149:
150: int
151: lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize)
152: {
153: u32 *d = (u32 *) set->data;
154: byte *end = buf + bufsize - 64;
155: int from2 = MAX(from, 0);
156: int to = set->length / 4;
157: int i;
158:
159: for (i = from2; i < to; i += 3)
160: {
161: if (buf > end)
162: {
163: if (from < 0)
164: strcpy(buf, "...");
165: else
166: buf[-1] = 0;
167: return i;
168: }
169:
170: buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]);
171: *buf++ = ' ';
172: }
173:
174: if (i != from2)
175: buf--;
176:
177: *buf = 0;
178: return 0;
179: }
180:
181: int
182: int_set_contains(const struct adata *list, u32 val)
183: {
184: if (!list)
185: return 0;
186:
187: u32 *l = (u32 *) list->data;
188: int len = int_set_get_size(list);
189: int i;
190:
191: for (i = 0; i < len; i++)
192: if (*l++ == val)
193: return 1;
194:
195: return 0;
196: }
197:
198: int
199: ec_set_contains(const struct adata *list, u64 val)
200: {
201: if (!list)
202: return 0;
203:
204: u32 *l = int_set_get_data(list);
205: int len = int_set_get_size(list);
206: u32 eh = ec_hi(val);
207: u32 el = ec_lo(val);
208: int i;
209:
210: for (i=0; i < len; i += 2)
211: if (l[i] == eh && l[i+1] == el)
212: return 1;
213:
214: return 0;
215: }
216:
217: int
218: lc_set_contains(const struct adata *list, lcomm val)
219: {
220: if (!list)
221: return 0;
222:
223: u32 *l = int_set_get_data(list);
224: int len = int_set_get_size(list);
225: int i;
226:
227: for (i = 0; i < len; i += 3)
228: if (lc_match(l, i, val))
229: return 1;
230:
231: return 0;
232: }
233:
234: const struct adata *
235: int_set_prepend(struct linpool *pool, const struct adata *list, u32 val)
236: {
237: struct adata *res;
238: int len;
239:
240: if (int_set_contains(list, val))
241: return list;
242:
243: len = list ? list->length : 0;
244: res = lp_alloc(pool, sizeof(struct adata) + len + 4);
245: res->length = len + 4;
246:
247: if (list)
248: memcpy(res->data + 4, list->data, list->length);
249:
250: * (u32 *) res->data = val;
251:
252: return res;
253: }
254:
255: const struct adata *
256: int_set_add(struct linpool *pool, const struct adata *list, u32 val)
257: {
258: struct adata *res;
259: int len;
260:
261: if (int_set_contains(list, val))
262: return list;
263:
264: len = list ? list->length : 0;
265: res = lp_alloc(pool, sizeof(struct adata) + len + 4);
266: res->length = len + 4;
267:
268: if (list)
269: memcpy(res->data, list->data, list->length);
270:
271: * (u32 *) (res->data + len) = val;
272:
273: return res;
274: }
275:
276: const struct adata *
277: ec_set_add(struct linpool *pool, const struct adata *list, u64 val)
278: {
279: if (ec_set_contains(list, val))
280: return list;
281:
282: int olen = list ? list->length : 0;
283: struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8);
284: res->length = olen + 8;
285:
286: if (list)
287: memcpy(res->data, list->data, list->length);
288:
289: u32 *l = (u32 *) (res->data + olen);
290: l[0] = ec_hi(val);
291: l[1] = ec_lo(val);
292:
293: return res;
294: }
295:
296: const struct adata *
297: lc_set_add(struct linpool *pool, const struct adata *list, lcomm val)
298: {
299: if (lc_set_contains(list, val))
300: return list;
301:
302: int olen = list ? list->length : 0;
303: struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH);
304: res->length = olen + LCOMM_LENGTH;
305:
306: if (list)
307: memcpy(res->data, list->data, list->length);
308:
309: lc_put((u32 *) (res->data + olen), val);
310:
311: return res;
312: }
313:
314: const struct adata *
315: int_set_del(struct linpool *pool, const struct adata *list, u32 val)
316: {
317: if (!int_set_contains(list, val))
318: return list;
319:
320: struct adata *res;
321: res = lp_alloc(pool, sizeof(struct adata) + list->length - 4);
322: res->length = list->length - 4;
323:
324: u32 *l = int_set_get_data(list);
325: u32 *k = int_set_get_data(res);
326: int len = int_set_get_size(list);
327: int i;
328:
329: for (i = 0; i < len; i++)
330: if (l[i] != val)
331: *k++ = l[i];
332:
333: return res;
334: }
335:
336: const struct adata *
337: ec_set_del(struct linpool *pool, const struct adata *list, u64 val)
338: {
339: if (!ec_set_contains(list, val))
340: return list;
341:
342: struct adata *res;
343: res = lp_alloc(pool, sizeof(struct adata) + list->length - 8);
344: res->length = list->length - 8;
345:
346: u32 *l = int_set_get_data(list);
347: u32 *k = int_set_get_data(res);
348: int len = int_set_get_size(list);
349: u32 eh = ec_hi(val);
350: u32 el = ec_lo(val);
351: int i;
352:
353: for (i=0; i < len; i += 2)
354: if (! (l[i] == eh && l[i+1] == el))
355: {
356: *k++ = l[i];
357: *k++ = l[i+1];
358: }
359:
360: return res;
361: }
362:
363: const struct adata *
364: lc_set_del(struct linpool *pool, const struct adata *list, lcomm val)
365: {
366: if (!lc_set_contains(list, val))
367: return list;
368:
369: struct adata *res;
370: res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH);
371: res->length = list->length - LCOMM_LENGTH;
372:
373: u32 *l = int_set_get_data(list);
374: u32 *k = int_set_get_data(res);
375: int len = int_set_get_size(list);
376: int i;
377:
378: for (i=0; i < len; i += 3)
379: if (! lc_match(l, i, val))
380: k = lc_copy(k, l+i);
381:
382: return res;
383: }
384:
385: const struct adata *
386: int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
387: {
388: if (!l1)
389: return l2;
390: if (!l2)
391: return l1;
392:
393: struct adata *res;
394: int len = int_set_get_size(l2);
395: u32 *l = int_set_get_data(l2);
396: u32 tmp[len];
397: u32 *k = tmp;
398: int i;
399:
400: for (i = 0; i < len; i++)
401: if (!int_set_contains(l1, l[i]))
402: *k++ = l[i];
403:
404: if (k == tmp)
405: return l1;
406:
407: len = (k - tmp) * 4;
408: res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
409: res->length = l1->length + len;
410: memcpy(res->data, l1->data, l1->length);
411: memcpy(res->data + l1->length, tmp, len);
412: return res;
413: }
414:
415: const struct adata *
416: ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
417: {
418: if (!l1)
419: return l2;
420: if (!l2)
421: return l1;
422:
423: struct adata *res;
424: int len = int_set_get_size(l2);
425: u32 *l = int_set_get_data(l2);
426: u32 tmp[len];
427: u32 *k = tmp;
428: int i;
429:
430: for (i = 0; i < len; i += 2)
431: if (!ec_set_contains(l1, ec_get(l, i)))
432: {
433: *k++ = l[i];
434: *k++ = l[i+1];
435: }
436:
437: if (k == tmp)
438: return l1;
439:
440: len = (k - tmp) * 4;
441: res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
442: res->length = l1->length + len;
443: memcpy(res->data, l1->data, l1->length);
444: memcpy(res->data + l1->length, tmp, len);
445: return res;
446: }
447:
448: const struct adata *
449: lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
450: {
451: if (!l1)
452: return l2;
453: if (!l2)
454: return l1;
455:
456: struct adata *res;
457: int len = int_set_get_size(l2);
458: u32 *l = int_set_get_data(l2);
459: u32 tmp[len];
460: u32 *k = tmp;
461: int i;
462:
463: for (i = 0; i < len; i += 3)
464: if (!lc_set_contains(l1, lc_get(l, i)))
465: k = lc_copy(k, l+i);
466:
467: if (k == tmp)
468: return l1;
469:
470: len = (k - tmp) * 4;
471: res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
472: res->length = l1->length + len;
473: memcpy(res->data, l1->data, l1->length);
474: memcpy(res->data + l1->length, tmp, len);
475: return res;
476: }
477:
478:
479: struct adata *
480: ec_set_del_nontrans(struct linpool *pool, const struct adata *set)
481: {
482: adata *res = lp_alloc_adata(pool, set->length);
483: u32 *src = int_set_get_data(set);
484: u32 *dst = int_set_get_data(res);
485: int len = int_set_get_size(set);
486: int i;
487:
488: /* Remove non-transitive communities (EC_TBIT set) */
489: for (i = 0; i < len; i += 2)
490: {
491: if (src[i] & EC_TBIT)
492: continue;
493:
494: *dst++ = src[i];
495: *dst++ = src[i+1];
496: }
497:
498: res->length = ((byte *) dst) - res->data;
499:
500: return res;
501: }
502:
503: static int
504: int_set_cmp(const void *X, const void *Y)
505: {
506: const u32 *x = X, *y = Y;
507: return (*x < *y) ? -1 : (*x > *y) ? 1 : 0;
508: }
509:
510: struct adata *
511: int_set_sort(struct linpool *pool, const struct adata *src)
512: {
513: struct adata *dst = lp_alloc_adata(pool, src->length);
514: memcpy(dst->data, src->data, src->length);
515: qsort(dst->data, dst->length / 4, 4, int_set_cmp);
516: return dst;
517: }
518:
519:
520: static int
521: ec_set_cmp(const void *X, const void *Y)
522: {
523: u64 x = ec_get(X, 0);
524: u64 y = ec_get(Y, 0);
525: return (x < y) ? -1 : (x > y) ? 1 : 0;
526: }
527:
528: struct adata *
529: ec_set_sort(struct linpool *pool, const struct adata *src)
530: {
531: struct adata *dst = lp_alloc_adata(pool, src->length);
532: memcpy(dst->data, src->data, src->length);
533: qsort(dst->data, dst->length / 8, 8, ec_set_cmp);
534: return dst;
535: }
536:
537: void
538: ec_set_sort_x(struct adata *set)
539: {
540: /* Sort in place */
541: qsort(set->data, set->length / 8, 8, ec_set_cmp);
542: }
543:
544:
545: static int
546: lc_set_cmp(const void *X, const void *Y)
547: {
548: const u32 *x = X, *y = Y;
549: if (x[0] != y[0])
550: return (x[0] > y[0]) ? 1 : -1;
551: if (x[1] != y[1])
552: return (x[1] > y[1]) ? 1 : -1;
553: if (x[2] != y[2])
554: return (x[2] > y[2]) ? 1 : -1;
555: return 0;
556: }
557:
558: struct adata *
559: lc_set_sort(struct linpool *pool, const struct adata *src)
560: {
561: struct adata *dst = lp_alloc_adata(pool, src->length);
562: memcpy(dst->data, src->data, src->length);
563: qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp);
564: return dst;
565: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to a-set.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / nest