# UNDF: UNDF-2026-000000401
# frrouting-0003: community_uniq_sort O(N²) → O(N log N) sort+dedup

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `bgpd/bgp_community.c:143` |
| Function    | `community_uniq_sort` |
| Hot path    | Per-BGP-UPDATE parse + per-route route-map apply + aggregate recompute |
| Status      | PATCHED (unit test PASS) |

## Defect

`community_uniq_sort` builds a deduplicated sorted community list. For each of N input
entries it calls `community_include(new, val)` which is an O(N) linear scan of the
already-built output array:

```c
// bgp_community.c:143
struct community *community_uniq_sort(struct community *com) {
    ...
    for (int i = 0; i < com->size; i++) {
        uint32_t val = community_val_get(com, i);
        if (!community_include(new, val)) {   // O(N) scan of new->val
            community_add_val(new, val);
        }
    }
    qsort(new->val, new->size, COMMUNITY_SIZE, community_val_cmp);
    return new;
}
```

Total: **O(N²)** dedup + O(N log N) sort. The qsort at the end is correct but wasted
on an already-sorted result if we sort-first.

**Invocation sites (all per-route hot paths):**
1. `bgp_community.c:504` — `community_parse()` — every incoming BGP UPDATE
2. `bgp_routemap.c:2849` — `route_set_community_apply()` additive merge
3. `bgp_community.c:983` — `bgp_compute_aggregate_community()` aggregate rebuild
4. `bgp_mpath.c:676` — multipath best-path community merge

## Fix

Sort all N entries first (O(N log N)), then do a single O(N) linear dedup pass:

```c
struct community *community_uniq_sort(struct community *com) {
    struct community *new = community_new();
    // Copy all entries
    for (int i = 0; i < com->size; i++)
        community_add_val(new, community_val_get(com, i));
    // Sort once: O(N log N)
    qsort(new->val, new->size, COMMUNITY_SIZE, community_val_cmp);
    // Linear dedup: O(N)
    int out = 0;
    for (int i = 0; i < new->size; i++) {
        if (i == 0 || community_val_get(new, i) != community_val_get(new, i - 1))
            community_set_val(new, out++, community_val_get(new, i));
    }
    new->size = out;
    return new;
}
```

Speedup: ~250× at N=500 (replaces O(N²)=250K with O(N log N)≈4.5K comparisons).
