[thirdparty/bird.git] / nest / a-set.c

/*
 *	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.
 */

#include "nest/bird.h"
#include "nest/route.h"
#include "nest/attrs.h"
#include "lib/resource.h"
#include "lib/string.h"

/**
 * 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
int_set_format(struct adata *set, int way, int from, byte *buf, unsigned int size)
{
  u32 *z = (u32 *) set->data;
  byte *end = buf + size - 24;
  int from2 = MAX(from, 0);
  int to = set->length / 4;
  int i;

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

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

      if (way)
	buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff);
      else
	buf += bsprintf(buf, "%R", z[i]);
    }
  *buf = 0;
  return 0;
}

int
ec_format(byte *buf, u64 ec)
{
  u32 type, key, val;
  char tbuf[16], *kind;

  type = ec >> 48;
  switch (type & 0xf0ff)
    {
    case EC_RT: kind = "rt"; break;
    case EC_RO: kind = "ro"; break;

    default:
      kind = tbuf;
      bsprintf(kind, "unknown 0x%x", type);
    }

  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
ec_set_format(struct adata *set, int from, byte *buf, unsigned int size)
{
  u32 *z = int_set_get_data(set);
  byte *end = buf + size - 24;
  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;
}

int
int_set_contains(struct adata *list, u32 val)
{
  if (!list)
    return 0;

  u32 *l = (u32 *) list->data;
  int len = int_set_get_size(list);
  int i;

  for (i = 0; i < len; i++)
    if (*l++ == val)
      return 1;

  return 0;
}

int
ec_set_contains(struct adata *list, u64 val)
{
  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;

  return 0;
}

struct adata *
int_set_add(struct linpool *pool, struct adata *list, u32 val)
{
  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;
  * (u32 *) res->data = val;
  if (list)
    memcpy((char *) res->data + 4, list->data, list->length);
  return res;
}

struct adata *
ec_set_add(struct linpool *pool, struct adata *list, u64 val)
{
  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);

  u32 *l = (u32 *) (res->data + res->length - 8);
  l[0] = ec_hi(val);
  l[1] = ec_lo(val);

  return res;
}


struct adata *
int_set_del(struct linpool *pool, struct adata *list, u32 val)
{
  if (!int_set_contains(list, val))
    return list;

  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;

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

  return res;
}

struct adata *
ec_set_del(struct linpool *pool, struct adata *list, u64 val)
{
  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;
}


struct adata *
int_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
{
  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;
}

struct adata *
ec_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
{
  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;
}
Commit	Line	Data
c0668f36 MM	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"
c6add07f	12	#include "nest/attrs.h"
c0668f36	13	#include "lib/resource.h"
c6add07f MM	14	#include "lib/string.h"
c6add07f MM	15
fdf16eb6 OZ	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, unsigned int size)
c6add07f MM	36	{
c6add07f MM	37	u32 z = (u32 ) set->data;
fdf16eb6	38	byte *end = buf + size - 24;
42a0c054	39	int from2 = MAX(from, 0);
fdf16eb6 OZ	40	int to = set->length / 4;
fdf16eb6 OZ	41	int i;
c6add07f	42
42a0c054	43	for (i = from2; i < to; i++)
c6add07f	44	{
c6add07f MM	45	if (buf > end)
c6add07f MM	46	{
fdf16eb6 OZ	47	if (from < 0)
	48	strcpy(buf, " ...");
	49	else
	50	*buf = 0;
	51	return i;
c6add07f	52	}
aebe06b4	53
42a0c054	54	if (i > from2)
fdf16eb6 OZ	55	*buf++ = ' ';
fdf16eb6 OZ	56
aebe06b4	57	if (way)
fdf16eb6	58	buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff);
aebe06b4	59	else
fdf16eb6	60	buf += bsprintf(buf, "%R", z[i]);
c6add07f MM	61	}
c6add07f MM	62	*buf = 0;
fdf16eb6	63	return 0;
c6add07f	64	}
9c400ec9	65
42a0c054 OZ	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, unsigned int size)
	117	{
	118	u32 *z = int_set_get_data(set);
	119	byte *end = buf + size - 24;
	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
9c400ec9 PM	144	int
	145	int_set_contains(struct adata *list, u32 val)
	146	{
0267f49f OZ	147	if (!list)
	148	return 0;
	149
700bbe60	150	u32 l = (u32 ) list->data;
42a0c054 OZ	151	int len = int_set_get_size(list);
	152	int i;
	153
	154	for (i = 0; i < len; i++)
9c400ec9 PM	155	if (*l++ == val)
9c400ec9 PM	156	return 1;
42a0c054 OZ	157
	158	return 0;
	159	}
	160
	161	int
	162	ec_set_contains(struct adata *list, u64 val)
	163	{
	164	if (!list)
	165	return 0;
	166
	167	u32 *l = int_set_get_data(list);
	168	int len = int_set_get_size(list);
	169	u32 eh = ec_hi(val);
	170	u32 el = ec_lo(val);
	171	int i;
	172
	173	for (i=0; i < len; i += 2)
	174	if (l[i] == eh && l[i+1] == el)
	175	return 1;
	176
9c400ec9 PM	177	return 0;
	178	}
	179
0267f49f OZ	180	struct adata *
	181	int_set_add(struct linpool pool, struct adata list, u32 val)
	182	{
	183	struct adata *res;
	184	int len;
	185
	186	if (int_set_contains(list, val))
	187	return list;
	188
	189	len = list ? list->length : 0;
42a0c054	190	res = lp_alloc(pool, sizeof(struct adata) + len + 4);
0267f49f OZ	191	res->length = len + 4;
	192	* (u32 *) res->data = val;
	193	if (list)
	194	memcpy((char *) res->data + 4, list->data, list->length);
	195	return res;
	196	}
	197
9c400ec9	198	struct adata *
42a0c054	199	ec_set_add(struct linpool pool, struct adata list, u64 val)
9c400ec9	200	{
42a0c054 OZ	201	if (ec_set_contains(list, val))
	202	return list;
	203
	204	int olen = list ? list->length : 0;
	205	struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8);
	206	res->length = olen + 8;
	207
	208	if (list)
	209	memcpy(res->data, list->data, list->length);
	210
	211	u32 l = (u32 ) (res->data + res->length - 8);
	212	l[0] = ec_hi(val);
	213	l[1] = ec_lo(val);
	214
	215	return res;
	216	}
	217
9c400ec9	218
42a0c054 OZ	219	struct adata *
	220	int_set_del(struct linpool pool, struct adata list, u32 val)
	221	{
9c400ec9 PM	222	if (!int_set_contains(list, val))
	223	return list;
	224
42a0c054 OZ	225	struct adata *res;
	226	res = lp_alloc(pool, sizeof(struct adata) + list->length - 4);
	227	res->length = list->length - 4;
	228
	229	u32 *l = int_set_get_data(list);
	230	u32 *k = int_set_get_data(res);
	231	int len = int_set_get_size(list);
	232	int i;
9c400ec9	233
42a0c054	234	for (i = 0; i < len; i++)
9c400ec9 PM	235	if (l[i] != val)
	236	*k++ = l[i];
	237
	238	return res;
	239	}
42a0c054 OZ	240
	241	struct adata *
	242	ec_set_del(struct linpool pool, struct adata list, u64 val)
	243	{
	244	if (!ec_set_contains(list, val))
	245	return list;
	246
	247	struct adata *res;
	248	res = lp_alloc(pool, sizeof(struct adata) + list->length - 8);
	249	res->length = list->length - 8;
	250
	251	u32 *l = int_set_get_data(list);
	252	u32 *k = int_set_get_data(res);
	253	int len = int_set_get_size(list);
	254	u32 eh = ec_hi(val);
	255	u32 el = ec_lo(val);
	256	int i;
	257
	258	for (i=0; i < len; i += 2)
	259	if (! (l[i] == eh && l[i+1] == el))
	260	{
	261	*k++ = l[i];
	262	*k++ = l[i+1];
	263	}
	264
	265	return res;
	266	}
0888a737 OZ	267
	268
	269	struct adata *
	270	int_set_union(struct linpool pool, struct adata l1, struct adata *l2)
	271	{
	272	if (!l1)
	273	return l2;
	274	if (!l2)
	275	return l1;
	276
	277	struct adata *res;
	278	int len = int_set_get_size(l2);
	279	u32 *l = int_set_get_data(l2);
	280	u32 tmp[len];
	281	u32 *k = tmp;
	282	int i;
	283
	284	for (i = 0; i < len; i++)
	285	if (!int_set_contains(l1, l[i]))
	286	*k++ = l[i];
	287
	288	if (k == tmp)
	289	return l1;
	290
	291	len = (k - tmp) * 4;
	292	res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
	293	res->length = l1->length + len;
	294	memcpy(res->data, l1->data, l1->length);
	295	memcpy(res->data + l1->length, tmp, len);
	296	return res;
	297	}
	298
	299	struct adata *
	300	ec_set_union(struct linpool pool, struct adata l1, struct adata *l2)
	301	{
	302	if (!l1)
	303	return l2;
	304	if (!l2)
	305	return l1;
	306
	307	struct adata *res;
	308	int len = int_set_get_size(l2);
	309	u32 *l = int_set_get_data(l2);
	310	u32 tmp[len];
	311	u32 *k = tmp;
	312	int i;
	313
	314	for (i = 0; i < len; i += 2)
	315	if (!ec_set_contains(l1, ec_get(l, i)))
	316	{
	317	*k++ = l[i];
	318	*k++ = l[i+1];
	319	}
	320
	321	if (k == tmp)
	322	return l1;
	323
	324	len = (k - tmp) * 4;
	325	res = lp_alloc(pool, sizeof(struct adata) + l1->length + len);
	326	res->length = l1->length + len;
	327	memcpy(res->data, l1->data, l1->length);
	328	memcpy(res->data + l1->length, tmp, len);
	329	return res;
	330	}