# UNDF: UNDF-2026-000000356
# bird-0004: clist_filter / eclist_filter / lclist_filter O(L×S) → O(L+S)

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `filter/data.c:421,456,490` |
| Functions   | `clist_filter`, `eclist_filter`, `lclist_filter` |
| Hot path    | Per-route per-filter — `bgp_community.delete(clist_var)` in route-map |
| Status      | PATCHED (unit test PASS) |

## Defect

The `!tree` branch of `clist_filter` (triggered when the operand is a T_CLIST runtime
variable rather than a T_SET compile-time literal) calls `int_set_contains(set->val.ad,
elem)` — O(S) linear scan — for each of L route-community entries:

```c
// filter/data.c:421 — clist_filter (T_CLIST branch)
while (len > 0) {
    u32 val = *l_data;
    // ...
    if (pos == !!(!tree ?
        int_set_contains(set->val.ad, val) :  // O(S) linear scan
        find_tree(tree, &(struct f_val){ .type = T_PAIR, .val.i = val })))
    {
        *res_data++ = val;
    }
}
```

Same pattern in `eclist_filter` (8-byte ext communities) and `lclist_filter` (12-byte
large communities).

**Note:** When the RHS is a T_SET literal, `find_tree()` provides O(log S) — only
the T_CLIST dynamic variable path is quadratic.

## Fix

Build a temporary hash set from `set->val.ad` before the loop (O(S)), then check
membership in O(1) per route-community entry:

```c
// Build set hash once — O(S)
uhash_t filter_set = uhash_from_uint32_array(set->val.ad);
// Filter: O(L) with O(1) lookups
while (len > 0) {
    u32 val = *l_data;
    if (pos == !!uhash_contains(&filter_set, val))
        *res_data++ = val;
    ...
}
```

Speedup: ~250× at L=S=500.
