nest/a-set.c

   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 }