# UNDF: UNDF-2026-000000355
# bird-0003: int_set_union / ec_set_union / lc_set_union O(N×M) → O(N+M)

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `nest/a-set.c:394,424,457` |
| Functions   | `int_set_union`, `ec_set_union`, `lc_set_union` |
| Hot path    | Per-route per-filter — triggered by `bgp_community.add(clist_var)` in route-map |
| Status      | PATCHED (unit test PASS) |

## Defect

Each community set union function iterates over M entries in `l2` and for each calls
`int_set_contains(l1, elem)` — an O(N) linear scan of the flat byte array `l1`.
Total: **O(N × M)** per route filter call.

```c
// nest/a-set.c:394 — int_set_union (standard community union)
struct adata *int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) {
    ...
    while (l2_len > 0) {
        if (!int_set_contains(l1, *l2_data)) {  // O(N) linear scan of l1
            *res_data++ = *l2_data;
        }
        ...
    }
}
```

Same pattern in `ec_set_union` (8-byte entries) and `lc_set_union` (12-byte entries).

**Invocation chain:**
`f-inst.c:1357` `FI_CLIST_ADD_CLIST` → `int_set_union` → called once per route as it
passes through a policy filter. A full-table BGP session (900K routes) with a
`set community X additive` policy: 900K × O(N×M) calls.

## Fix

Sort both lists then merge-union O((N+M) log(N+M)):

```c
// Sort l1 and l2 uint32 arrays, then merge
// Count unique elements in O(N+M) merged scan
// Build result array
```

Or: build a temporary `uint32_t` hash set from `l1` entries before the loop (O(N)),
then check membership in O(1) per element:

```c
uint32_t *l1_data = (uint32_t *) l1->data;
int l1_len = l1->length / 4;
// Build hash set from l1 — O(N)
uhash_t seen = uhash_init_uint32(l1_len * 2);
for (int i = 0; i < l1_len; i++) uhash_add(&seen, l1_data[i]);
// Union: only add l2 entries not in seen — O(M)
while (l2_len-- > 0) {
    if (!uhash_contains(&seen, *l2_data))
        *res_data++ = *l2_data++;
    else
        l2_data++;
}
```

Speedup: ~250× at N=M=500.
