# UNDF: UNDF-2026-000000589
# kicad-0002: zone_filler.cpp std::find O(Z²×L²) → O(Z×L log(Z×L)) with ordered set

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `pcbnew/zone_filler.cpp:998` |
| Function    | `ZONE_FILLER::Fill()` — iterative refill with removed islands |
| Hot path    | Zone fill / DRC with copper island removal on complex boards |
| Status      | PATCHED (unit test PASS) |

## Defect

The iterative refill path accumulates zones needing refill in a `std::vector` and
uses `std::find` O(N) for deduplication inside a triple nested loop:

```cpp
// zone_filler.cpp:998
std::vector<std::pair<ZONE*, PCB_LAYER_ID>> zonesToRefill;

for( ZONE* zoneWithIsland : zonesWithRemovedIslands )     // Z_r removed-island zones
{
    for( ZONE* zone : aZones )                            // Z total zones
    {
        for( PCB_LAYER_ID layer : commonLayers )          // L copper layers
        {
            auto fillItem = std::make_pair( zone, layer );
            if( std::find( zonesToRefill.begin(),
                           zonesToRefill.end(), fillItem ) // O(Z×L) linear scan
                    == zonesToRefill.end() )
                zonesToRefill.push_back( fillItem );
        }
    }
}
```

With Z=50 zones, L=4 layers, Z_r=10 zones with islands:
- **Before:** 10 × 50 × 4 × (50×4) = **400,000 comparisons** per refill pass
- **After:** 10 × 50 × 4 × O(1) = **2,000 operations** (200×)

## Fix

Replace `std::vector` with `std::set<std::pair<ZONE*, PCB_LAYER_ID>>` or
`std::unordered_set` with a custom hash:

```cpp
struct PairHash {
    size_t operator()(const std::pair<ZONE*, PCB_LAYER_ID>& p) const {
        return std::hash<ZONE*>()(p.first) ^ (std::hash<int>()(p.second) << 16);
    }
};
std::unordered_set<std::pair<ZONE*, PCB_LAYER_ID>, PairHash> zonesToRefill;

// Insert: O(1) average — dedup is automatic
zonesToRefill.insert( std::make_pair( zone, layer ) );
```

Convert back to `std::vector` for the subsequent `Fill` call if needed.

Speedup: ~200× at Z=50, L=4.
