a-set.c 11.5 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*
 *	BIRD -- Set/Community-list Operations
 *
 *	(c) 2000 Martin Mares <mj@ucw.cz>
 *	(c) 2000 Pavel Machek <pavel@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

Ondřej Zajíček's avatar
Ondřej Zajíček committed
10 11
#include <stdlib.h>

12 13
#include "nest/bird.h"
#include "nest/route.h"
14
#include "nest/attrs.h"
15
#include "lib/resource.h"
16 17
#include "lib/string.h"

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
/**
 * int_set_format - format an &set for printing
 * @set: set attribute to be formatted
 * @way: style of format (0 for router ID list, 1 for community list)
 * @from: starting position in set
 * @buf: destination buffer
 * @size: size of buffer
 *
 * This function takes a set attribute and formats it. @way specifies
 * the style of format (router ID / community). @from argument can be
 * used to specify the first printed value for the purpose of printing
 * untruncated sets even with smaller buffers. If the output fits in
 * the buffer, 0 is returned, otherwise the position of the first not
 * printed item is returned. This value can be used as @from argument
 * in subsequent calls. If truncated output suffices, -1 can be
 * instead used as @from, in that case " ..." is eventually added at
 * the buffer to indicate truncation.
 */
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 43
  int to = set->length / 4;
  int i;
44

45
  for (i = from2; i < to; i++)
46 47 48
    {
      if (buf > end)
	{
49 50 51 52 53
	  if (from < 0)
	    strcpy(buf, " ...");
	  else
	    *buf = 0;
	  return i;
54
	}
55

56
      if (i > from2)
57 58
	*buf++ = ' ';

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 69 70 71
int
ec_format(byte *buf, u64 ec)
{
  u32 type, key, val;
72 73
  char tbuf[16];
  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 81
    kind = tbuf;
  }
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

  switch (ec >> 56)
    {
      /* RFC 4360 3.1.  Two-Octet AS Specific Extended Community */
    case 0x00:
    case 0x40:
      key = (ec >> 32) & 0xFFFF;
      val = ec;
      return bsprintf(buf, "(%s, %u, %u)", kind, key, val);

      /* RFC 4360 3.2.  IPv4 Address Specific Extended Community */
    case 0x01:
    case 0x41:
      key = ec >> 16;
      val = ec & 0xFFFF;
      return bsprintf(buf, "(%s, %R, %u)", kind, key, val);

      /* RFC 5668  4-Octet AS Specific BGP Extended Community */
    case 0x02:
    case 0x42:
      key = ec >> 16;
      val = ec & 0xFFFF;
      return bsprintf(buf, "(%s, %u, %u)", kind, key, val);

      /* Generic format for unknown kinds of extended communities */
    default:
      key = ec >> 32;
      val = ec;
      return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val);
    }

}

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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
  int from2 = MAX(from, 0);
  int to = int_set_get_size(set);
  int i;

  for (i = from2; i < to; i += 2)
    {
      if (buf > end)
	{
	  if (from < 0)
	    strcpy(buf, " ...");
	  else
	    *buf = 0;
	  return i;
	}

      if (i > from2)
	*buf++ = ' ';

      buf += ec_format(buf, ec_get(z, i));
    }
  *buf = 0;
  return 0;
}

144 145 146
int
lc_format(byte *buf, lcomm lc)
{
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 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
{
  u32 *d = (u32 *) set->data;
  byte *end = buf + bufsize - 64;
  int from2 = MAX(from, 0);
  int to = set->length / 4;
  int i;

  for (i = from2; i < to; i += 3)
    {
      if (buf > end)
	{
	  if (from < 0)
	    strcpy(buf, "...");
	  else
	    buf[-1] = 0;
	  return i;
	}

170
      buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]);
171 172 173 174 175 176 177 178 179 180
      *buf++ = ' ';
    }

  if (i != from2)
    buf--;

  *buf = 0;
  return 0;
}

181
int
182
int_set_contains(const struct adata *list, u32 val)
183
{
184 185 186
  if (!list)
    return 0;

187
  u32 *l = (u32 *) list->data;
188 189 190 191
  int len = int_set_get_size(list);
  int i;

  for (i = 0; i < len; i++)
192 193
    if (*l++ == val)
      return 1;
194 195 196 197 198

  return 0;
}

int
199
ec_set_contains(const struct adata *list, u64 val)
200 201 202 203 204 205 206 207 208 209 210 211 212 213
{
  if (!list)
    return 0;

  u32 *l = int_set_get_data(list);
  int len = int_set_get_size(list);
  u32 eh = ec_hi(val);
  u32 el = ec_lo(val);
  int i;

  for (i=0; i < len; i += 2)
    if (l[i] == eh && l[i+1] == el)
      return 1;

214 215 216
  return 0;
}

217
int
218
lc_set_contains(const struct adata *list, lcomm val)
219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
{
  if (!list)
    return 0;

  u32 *l = int_set_get_data(list);
  int len = int_set_get_size(list);
  int i;

  for (i = 0; i < len; i += 3)
    if (lc_match(l, i, val))
      return 1;

  return 0;
}

234 235
const struct adata *
int_set_prepend(struct linpool *pool, const struct adata *list, u32 val)
236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
{
  struct adata *res;
  int len;

  if (int_set_contains(list, val))
    return list;

  len = list ? list->length : 0;
  res = lp_alloc(pool, sizeof(struct adata) + len + 4);
  res->length = len + 4;

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

  * (u32 *) res->data = val;

  return res;
}
254

255 256
const struct adata *
int_set_add(struct linpool *pool, const struct adata *list, u32 val)
257 258 259 260 261 262 263 264
{
  struct adata *res;
  int len;

  if (int_set_contains(list, val))
    return list;

  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 270
    memcpy(res->data, list->data, list->length);

271
  * (u32 *) (res->data + len) = val;
272

273 274 275
  return res;
}

276 277
const struct adata *
ec_set_add(struct linpool *pool, const struct adata *list, u64 val)
278
{
279 280 281 282 283 284 285 286 287 288
  if (ec_set_contains(list, val))
    return list;

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

  if (list)
    memcpy(res->data, list->data, list->length);

289
  u32 *l = (u32 *) (res->data + olen);
290 291 292 293 294 295
  l[0] = ec_hi(val);
  l[1] = ec_lo(val);

  return res;
}

296 297
const struct adata *
lc_set_add(struct linpool *pool, const struct adata *list, lcomm val)
298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
{
  if (lc_set_contains(list, val))
    return list;

  int olen = list ? list->length : 0;
  struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH);
  res->length = olen + LCOMM_LENGTH;

  if (list)
    memcpy(res->data, list->data, list->length);

  lc_put((u32 *) (res->data + olen), val);

  return res;
}
313

314 315
const struct adata *
int_set_del(struct linpool *pool, const struct adata *list, u32 val)
316
{
317 318 319
  if (!int_set_contains(list, val))
    return list;

320 321 322 323 324 325 326 327
  struct adata *res;
  res = lp_alloc(pool, sizeof(struct adata) + list->length - 4);
  res->length = list->length - 4;

  u32 *l = int_set_get_data(list);
  u32 *k = int_set_get_data(res);
  int len = int_set_get_size(list);
  int i;
328

329
  for (i = 0; i < len; i++)
330 331 332 333 334
    if (l[i] != val)
      *k++ = l[i];

  return res;
}
335

336 337
const struct adata *
ec_set_del(struct linpool *pool, const struct adata *list, u64 val)
338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361
{
  if (!ec_set_contains(list, val))
    return list;

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

  u32 *l = int_set_get_data(list);
  u32 *k = int_set_get_data(res);
  int len = int_set_get_size(list);
  u32 eh = ec_hi(val);
  u32 el = ec_lo(val);
  int i;

  for (i=0; i < len; i += 2)
    if (! (l[i] == eh && l[i+1] == el))
      {
	*k++ = l[i];
	*k++ = l[i+1];
      }

  return res;
}
362

363 364
const struct adata *
lc_set_del(struct linpool *pool, const struct adata *list, lcomm val)
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383
{
  if (!lc_set_contains(list, val))
    return list;

  struct adata *res;
  res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH);
  res->length = list->length - LCOMM_LENGTH;

  u32 *l = int_set_get_data(list);
  u32 *k = int_set_get_data(res);
  int len = int_set_get_size(list);
  int i;

  for (i=0; i < len; i += 3)
    if (! lc_match(l, i, val))
      k = lc_copy(k, l+i);

  return res;
}
384

385 386
const struct adata *
int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
{
  if (!l1)
    return l2;
  if (!l2)
    return l1;

  struct adata *res;
  int len = int_set_get_size(l2);
  u32 *l = int_set_get_data(l2);
  u32 tmp[len];
  u32 *k = tmp;
  int i;

  for (i = 0; i < len; i++)
    if (!int_set_contains(l1, l[i]))
      *k++ = l[i];

  if (k == tmp)
    return l1;

  len = (k - tmp) * 4;
  res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
  res->length = l1->length + len;
  memcpy(res->data, l1->data, l1->length);
  memcpy(res->data + l1->length, tmp, len);
  return res;
}

415 416
const struct adata *
ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446
{
  if (!l1)
    return l2;
  if (!l2)
    return l1;

  struct adata *res;
  int len = int_set_get_size(l2);
  u32 *l = int_set_get_data(l2);
  u32 tmp[len];
  u32 *k = tmp;
  int i;

  for (i = 0; i < len; i += 2)
    if (!ec_set_contains(l1, ec_get(l, i)))
      {
	*k++ = l[i];
	*k++ = l[i+1];
      }

  if (k == tmp)
    return l1;

  len = (k - tmp) * 4;
  res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
  res->length = l1->length + len;
  memcpy(res->data, l1->data, l1->length);
  memcpy(res->data + l1->length, tmp, len);
  return res;
}
447

448 449
const struct adata *
lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476
{
  if (!l1)
    return l2;
  if (!l2)
    return l1;

  struct adata *res;
  int len = int_set_get_size(l2);
  u32 *l = int_set_get_data(l2);
  u32 tmp[len];
  u32 *k = tmp;
  int i;

  for (i = 0; i < len; i += 3)
    if (!lc_set_contains(l1, lc_get(l, i)))
      k = lc_copy(k, l+i);

  if (k == tmp)
    return l1;

  len = (k - tmp) * 4;
  res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
  res->length = l1->length + len;
  memcpy(res->data, l1->data, l1->length);
  memcpy(res->data + l1->length, tmp, len);
  return res;
}
Ondřej Zajíček's avatar
Ondřej Zajíček committed
477 478 479


struct adata *
480
ec_set_del_nontrans(struct linpool *pool, const struct adata *set)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
{
  adata *res = lp_alloc_adata(pool, set->length);
  u32 *src = int_set_get_data(set);
  u32 *dst = int_set_get_data(res);
  int len = int_set_get_size(set);
  int i;

  /* Remove non-transitive communities (EC_TBIT set) */
  for (i = 0; i < len; i += 2)
  {
    if (src[i] & EC_TBIT)
      continue;

    *dst++ = src[i];
    *dst++ = src[i+1];
  }

  res->length = ((byte *) dst) - res->data;

  return res;
}

static int
int_set_cmp(const void *X, const void *Y)
{
  const u32 *x = X, *y = Y;
  return (*x < *y) ? -1 : (*x > *y) ? 1 : 0;
}

struct adata *
511
int_set_sort(struct linpool *pool, const struct adata *src)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528
{
  struct adata *dst = lp_alloc_adata(pool, src->length);
  memcpy(dst->data, src->data, src->length);
  qsort(dst->data, dst->length / 4, 4, int_set_cmp);
  return dst;
}


static int
ec_set_cmp(const void *X, const void *Y)
{
  u64 x = ec_get(X, 0);
  u64 y = ec_get(Y, 0);
  return (x < y) ? -1 : (x > y) ? 1 : 0;
}

struct adata *
529
ec_set_sort(struct linpool *pool, const struct adata *src)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
530 531 532 533 534 535 536
{
  struct adata *dst = lp_alloc_adata(pool, src->length);
  memcpy(dst->data, src->data, src->length);
  qsort(dst->data, dst->length / 8, 8, ec_set_cmp);
  return dst;
}

537 538 539 540 541 542 543
void
ec_set_sort_x(struct adata *set)
{
  /* Sort in place */
  qsort(set->data, set->length / 8, 8, ec_set_cmp);
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
544 545 546 547 548 549 550 551 552 553 554 555 556 557 558

static int
lc_set_cmp(const void *X, const void *Y)
{
  const u32 *x = X, *y = Y;
  if (x[0] != y[0])
    return (x[0] > y[0]) ? 1 : -1;
  if (x[1] != y[1])
    return (x[1] > y[1]) ? 1 : -1;
  if (x[2] != y[2])
    return (x[2] > y[2]) ? 1 : -1;
  return 0;
}

struct adata *
559
lc_set_sort(struct linpool *pool, const struct adata *src)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
560 561 562 563 564 565
{
  struct adata *dst = lp_alloc_adata(pool, src->length);
  memcpy(dst->data, src->data, src->length);
  qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp);
  return dst;
}