Statistics
| Branch: | Revision:

iof-bird-daemon / nest / a-set.c @ 261816b0

History | View | Annotate | Download (9.52 KB)

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
}