Annotation of embedaddon/bird/nest/a-set.c, revision 1.1.1.1
1.1 misho 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 "nest/bird.h"
11: #include "nest/route.h"
12: #include "nest/attrs.h"
13: #include "lib/resource.h"
14: #include "lib/string.h"
15:
16: /**
17: * int_set_format - format an &set for printing
18: * @set: set attribute to be formatted
19: * @way: style of format (0 for router ID list, 1 for community list)
20: * @from: starting position in set
21: * @buf: destination buffer
22: * @size: size of buffer
23: *
24: * This function takes a set attribute and formats it. @way specifies
25: * the style of format (router ID / community). @from argument can be
26: * used to specify the first printed value for the purpose of printing
27: * untruncated sets even with smaller buffers. If the output fits in
28: * the buffer, 0 is returned, otherwise the position of the first not
29: * printed item is returned. This value can be used as @from argument
30: * in subsequent calls. If truncated output suffices, -1 can be
31: * instead used as @from, in that case " ..." is eventually added at
32: * the buffer to indicate truncation.
33: */
34: int
35: int_set_format(struct adata *set, int way, int from, byte *buf, uint size)
36: {
37: u32 *z = (u32 *) set->data;
38: byte *end = buf + size - 24;
39: int from2 = MAX(from, 0);
40: int to = set->length / 4;
41: int i;
42:
43: for (i = from2; i < to; i++)
44: {
45: if (buf > end)
46: {
47: if (from < 0)
48: strcpy(buf, " ...");
49: else
50: *buf = 0;
51: return i;
52: }
53:
54: if (i > from2)
55: *buf++ = ' ';
56:
57: if (way)
58: buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff);
59: else
60: buf += bsprintf(buf, "%R", z[i]);
61: }
62: *buf = 0;
63: return 0;
64: }
65:
66: int
67: ec_format(byte *buf, u64 ec)
68: {
69: u32 type, key, val;
70: char tbuf[16], *kind;
71:
72: type = ec >> 48;
73: switch (type & 0xf0ff)
74: {
75: case EC_RT: kind = "rt"; break;
76: case EC_RO: kind = "ro"; break;
77:
78: default:
79: kind = tbuf;
80: bsprintf(kind, "unknown 0x%x", type);
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(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(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(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(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(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: struct adata *
235: int_set_prepend(struct linpool *pool, 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: struct adata *
256: int_set_add(struct linpool *pool, 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: struct adata *
277: ec_set_add(struct linpool *pool, 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: struct adata *
297: lc_set_add(struct linpool *pool, 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: struct adata *
315: int_set_del(struct linpool *pool, 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: struct adata *
337: ec_set_del(struct linpool *pool, 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: struct adata *
364: lc_set_del(struct linpool *pool, 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: struct adata *
386: int_set_union(struct linpool *pool, struct adata *l1, 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: struct adata *
416: ec_set_union(struct linpool *pool, struct adata *l1, 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: struct adata *
449: lc_set_union(struct linpool *pool, struct adata *l1, 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: }
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 / bird / nest