kdenlive-0001: ThumbnailCache m_storedOnDisk vector<int> std::find dedup O(C*P*V) MEDIUM
kdenlive-0002: TimelineModel clipIds vector std::find in mix loop O(N^2) MEDIUM
kdenlive-0003: TimelineController sorted_clips vector std::find in moveGroup O(N^2) MEDIUM
kdenlive-0004: TimelineModel all_items list std::find in resize O(N^2) MEDIUM
shotcut-0001: PlaylistProxyModel m_hashes vector std::find in filterAcceptsRow O(N^2) MEDIUM
5/5 unit tests PASS
libtorrent-0001: file_storage::get_or_add_path std::find on m_paths vector O(F*P) MEDIUM 250x
qBittorrent: CLEAN (QSet/QHash throughout for membership tests)
CWE-407: is_contained(BlockList, Succ) inside nested for loops in
computeOutliningColdRegionsInfo. Fix: SmallPtrSet for O(1) membership.
GCC deep scan: CLEAN (bitmaps/hash_sets throughout).
rustc: Exemplary use of FxHashSet/BitSet/IntervalSet throughout;
no linear membership tests on hot paths.
swift-0001: LoadableByAddress.cpp StructLoweringState uses SmallVector
with std::find for largeLoadableArgs/applies membership — O(I×A)
per function, 322x overhead at A=500. Fix: SmallPtrSet shadow.
minio-0001: healingTracker.isHealed() slices.Contains O(B×H) MEDIUM 25x
minio-0002: isBucketDecommissioned() slices.Contains O(P×D) MEDIUM 24x
minio-0003: isGroupDescEqual/isUserInfoEqual slices.Contains O(M²) MEDIUM 13x
etcd: maps + interval trees throughout; no CWE-407 defects found
tidb-0001: partition drop name lookup O(P×D) → O(P+D) (27x at P=8192)
tidb-0002: predicate simplification (merged into tidb-0002 in prior commit)
tidb-0003: list partition group intersect O(G²) → O(G) (renumbered from 0002)
scylladb-0001: UNDF stamp added
istio-0001: gateway reportGatewayStatus addressesToReport dedup O(I^2)
pilot/pkg/config/kube/gateway/conversion.go +
pilot/pkg/config/kube/agentgateway/gateway_status.go
Fix: map[string]struct{} seen-set replaces slices.Contains on growing list
argo-cd-0001: mergeIgnoreDifferences O(P^2) per field type
util/argo/diff/ignore.go
Fix: pre-compute sets for JQPathExpressions/JSONPointers/ManagedFieldsManagers
Both: 2/2 unit tests PASS; 3.4x and 3.7x speedup measured
curl-0001 (UNDF-2026-000000040): lib/http_aws_sigv4.c make_headers() sorts
canonical SigV4 headers using an O(H^2) bubble sort (do/while/for). Every
SigV4 HTTP request pays H^2 comparisons. At H=200: 35,024 vs 794 (44x).
Fix: qsort on a temporary pointer array, O(H log H).
ffmpeg-0001 (UNDF-2026-000000070): libavfilter/formats.c MERGE_FORMATS macro
intersects two pixel-format lists via nested loop O(A*B). With ~380 pixel
formats (AV_PIX_FMT_NB), worst case is 144,400 comparisons per link per
avfilter_graph_config() call. At A=B=380: 72,390 vs 3,420 (21x).
Fix: sort b, bsearch for membership, O((A+B) log B).
Unit tests: CurlTest.java, FFmpegTest.java — both PASS.
sdl-0001: SDL_gamepad.c SDL_PrivateAddMappingForGUID — O(M) tail walk of
s_pSupportedGamepads linked list on every mapping insert → O(M²) bulk load.
SDL_GameControllerDB ships >30 000 entries; fix: tail pointer s_pLastSupportedGamepad.
box2d-0001: broad_phase.c b2UnBufferMove — linear scan through moveArray to
find proxy key on destroy (acknowledged by code comment) → O(N²) on bulk destroy.
Fix: index map (proxyKey → slot) for O(1) swap-remove.
bullet3-0001: btGhostObject::addOverlappingObjectInternal uses
findLinearSearch (O(N) pointer scan) on every broadphase pair-update
callback. With N objects overlapping a ghost, each tick is O(N²). Fix:
btHashMap<btHashPtr,int> shadow index → O(1) add/remove. 250x at N=500.
three-0001: NodeBuilder.addNode/addSequentialNode use Array.includes
(O(N)) per node during shader build traversal → O(N²). StackNode.generate
uses nodes.indexOf inside filter → O(N²). Fix: shadow with Set → O(1). 250x
at N=500.
nomad-0005: scheduler/reconciler/reconcile_cluster.go
handleReconnectingAllocs slices.Contains(replacements, alloc.ID)
O(A×R) inner linear scan — replaced with map[string]struct{} O(1)
Also confirm envoy-0001 through envoy-0004 were previously scanned
(UNDF-63, 390, 391, 699) and nomad-0001 through nomad-0004 (UNDF-476..479).
