intervals: Do not sort cached set elements over and over again

When adding element(s) to a non-empty set, code merged the two lists and
sorted the result. With many individual 'add element' commands this
causes substantial overhead. Make use of the fact that
existing_set->init is sorted already, sort only the list of new elements
and use list_splice_sorted() to merge the two sorted lists.

Add set_sort_splice() and use it for set element overlap detection and
automerge.

A test case adding ~25k elements in individual commands completes in
about 1/4th of the time with this patch applied.

Joint work with Pablo.

Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
Signed-off-by: Phil Sutter <phil@nwl.cc>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

0 files changed, 0 insertions, 0 deletions