Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / nest / a-set.c @ 6b3f1a54

History | View | Annotate | Download (11.4 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 <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.  Two-Octet 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  4-Octet 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 non-transitive 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
}