acl: improve rules sorting
authorMark Smith <marsmith@akamai.com>
Wed, 26 Aug 2015 19:25:18 +0000 (15:25 -0400)
committerThomas Monjalon <thomas.monjalon@6wind.com>
Sat, 24 Oct 2015 20:52:53 +0000 (22:52 +0200)
commitfd4b6f78adcb85b437450be0d560773bdbb71f69
tree1084f3ed71b1676922fae1d8abf741a9df02afea
parent7acf894d07d1cfbab50c525300e5c61fce2468d6
acl: improve rules sorting

Replace O(n^2) list sort with an O(n log n) merge sort.
The merge sort is based on the solution suggested in:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Tested sort_rules() improvement:
100K rules: O(n^2):  31382 milliseconds; O(n log n): 10 milliseconds
259K rules: O(n^2): 133753 milliseconds; O(n log n): 22 milliseconds

Signed-off-by: Mark Smith <marsmith@akamai.com>
Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
lib/librte_acl/acl_bld.c