On Mon, 16 Nov 2015, Paul Jakma wrote:
Hmm, might it be better instead to make nexthop_add do an insertion sort (O(n) even with a linked-list), so that the above becomes an O(n) prefix comparison rather than O(n^2) (and NEXTHOP_FLAG_MATCHED disappears).
Oh, that's O(n) for any given run of whatever non-preemptive thread, I'd hope. Over all the insertions on a nexthop it could of course become O(n^2) again, but may still save time as the above O(n^2) version could get called again and again and again I think.
One other comment on this patch, it really could use unit tests. That's one thing that's made me nervous in the past reforming the RIB and why some of my own RIB and nexthop reform and recursive patches I didn't push them much - I didn't have a way to prove them.
Could we have a test harness? regards, -- Paul Jakma [email protected] @pjakma Key ID: 64A2FF6A Fortune: Computers are like air conditioners. Both stop working, if you open windows. -- Adam Heath _______________________________________________ Quagga-dev mailing list [email protected] https://lists.quagga.net/mailman/listinfo/quagga-dev
