diff options
Diffstat (limited to 'nest/a-set.c')
-rw-r--r-- | nest/a-set.c | 743 |
1 files changed, 0 insertions, 743 deletions
diff --git a/nest/a-set.c b/nest/a-set.c deleted file mode 100644 index 40ed573c..00000000 --- a/nest/a-set.c +++ /dev/null @@ -1,743 +0,0 @@ -/* - * 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 <stdlib.h> - -#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(const struct adata *set, int way, int from, byte *buf, uint 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]; - const char *kind; - - type = ec >> 48; - kind = ec_subtype_str(type & 0xf0ff); - - if (!kind) { - bsprintf(tbuf, "unknown 0x%x", type); - kind = tbuf; - } - - 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(const struct adata *set, int from, byte *buf, uint size) -{ - u32 *z = int_set_get_data(set); - byte *end = buf + size - 64; - 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 -lc_format(byte *buf, lcomm lc) -{ - return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); -} - -int -lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize) -{ - 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; - } - - buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); - *buf++ = ' '; - } - - if (i != from2) - buf--; - - *buf = 0; - return 0; -} - -int -int_set_contains(const 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(const 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; -} - -int -lc_set_contains(const struct adata *list, lcomm val) -{ - 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; -} - -const struct adata * -int_set_prepend(struct linpool *pool, const 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; - - if (list) - memcpy(res->data + 4, list->data, list->length); - - * (u32 *) res->data = val; - - return res; -} - -const struct adata * -int_set_add(struct linpool *pool, const 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; - - if (list) - memcpy(res->data, list->data, list->length); - - * (u32 *) (res->data + len) = val; - - return res; -} - -const struct adata * -ec_set_add(struct linpool *pool, const 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 + olen); - l[0] = ec_hi(val); - l[1] = ec_lo(val); - - return res; -} - -const struct adata * -lc_set_add(struct linpool *pool, const struct adata *list, lcomm val) -{ - 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; -} - -const struct adata * -int_set_del(struct linpool *pool, const 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; -} - -const struct adata * -ec_set_del(struct linpool *pool, const 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; -} - -const struct adata * -lc_set_del(struct linpool *pool, const struct adata *list, lcomm val) -{ - 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; -} - -const struct adata * -int_set_union(struct linpool *pool, const struct adata *l1, const 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; -} - -const struct adata * -ec_set_union(struct linpool *pool, const struct adata *l1, const 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; -} - -const struct adata * -lc_set_union(struct linpool *pool, const struct adata *l1, const 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 += 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; -} - - -struct adata * -ec_set_del_nontrans(struct linpool *pool, const struct adata *set) -{ - 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 * -int_set_sort(struct linpool *pool, const struct adata *src) -{ - 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; -} - -int -int_set_min(const struct adata *list, u32 *val) -{ - if (!list) - return 0; - - u32 *l = (u32 *) list->data; - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - *val = *l++; - for (i = 1; i < len; i++, l++) - if (int_set_cmp(val, l) > 0) - *val = *l; - - return 1; -} - -int -int_set_max(const struct adata *list, u32 *val) -{ - if (!list) - return 0; - - u32 *l = (u32 *) list->data; - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - *val = *l++; - for (i = 1; i < len; i++, l++) - if (int_set_cmp(val, l) < 0) - *val = *l; - - return 1; -} - - -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 * -ec_set_sort(struct linpool *pool, const struct adata *src) -{ - 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; -} - -void -ec_set_sort_x(struct adata *set) -{ - /* Sort in place */ - qsort(set->data, set->length / 8, 8, ec_set_cmp); -} - -int -ec_set_min(const struct adata *list, u64 *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 2; - for (i = 2; i < len; i += 2, l += 2) - if (ec_set_cmp(res, l) > 0) - res = l; - - *val = ec_generic(res[0], res[1]); - return 1; -} - -int -ec_set_max(const struct adata *list, u64 *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 2; - for (i = 2; i < len; i += 2, l += 2) - if (ec_set_cmp(res, l) < 0) - res = l; - - *val = ec_generic(res[0], res[1]); - return 1; -} - - -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 * -lc_set_sort(struct linpool *pool, const struct adata *src) -{ - 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; -} - -int -lc_set_min(const struct adata *list, lcomm *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 3; - for (i = 3; i < len; i += 3, l += 3) - if (lc_set_cmp(res, l) > 0) - res = l; - - *val = (lcomm) { res[0], res[1], res[2] }; - return 1; -} - -int -lc_set_max(const struct adata *list, lcomm *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 3; - for (i = 3; i < len; i += 3, l += 3) - if (lc_set_cmp(res, l) < 0) - res = l; - - *val = (lcomm) { res[0], res[1], res[2] }; - return 1; -} - -int -int_set_walk(const struct adata *list, uint *pos, uint *val) -{ - if (!list) - return 0; - - if (*pos >= (uint) int_set_get_size(list)) - return 0; - - u32 *res = int_set_get_data(list) + *pos; - *val = *res; - *pos += 1; - - return 1; -} - -int -ec_set_walk(const struct adata *list, uint *pos, u64 *val) -{ - if (!list) - return 0; - - if (*pos >= (uint) int_set_get_size(list)) - return 0; - - u32 *res = int_set_get_data(list) + *pos; - *val = ec_generic(res[0], res[1]); - *pos += 2; - - return 1; -} - -int -lc_set_walk(const struct adata *list, uint *pos, lcomm *val) -{ - if (!list) - return 0; - - if (*pos >= (uint) int_set_get_size(list)) - return 0; - - u32 *res = int_set_get_data(list) + *pos; - *val = (lcomm) { res[0], res[1], res[2] }; - *pos += 3; - - return 1; -} |