CVSROOT: /cvs
Module name: src
Changes by: [email protected] 2026/11/16 09:42:29
Modified files:
usr.sbin/rpki-client: aspa.c
Log message:
rpki-client: rework aspa_insert_vaps()
The merge loop in aspa_insert_vaps() is too smart and has tripped us all up
repeatedly. While it won't matter much due to size constraints, its worst
case is O(n*m), which isn't great.
Let's make this easier to follow and reason about. A linear sweep merges
and deduplicates the two arrays question until one of them is consumed,
then fill in the tail of the one that remains non-empty. Both arrays are
strictly monotonic, and this property is clearly preserved by the new
approach.
The other bit that is obvious is that the merge loop is O(n + m). The price
we pay is a bit more code and an extra allocation.
ok claudio job