Replaces the algorithm for building balanced trees.

Changes the time complexity of the algorithm from O(n^2) to O(n*log(n)).
This speeds up loading of huge DEC-IX config from 128 s to 15 s. It also
makes the code significantly simpler.

1 files changed, 15 insertions, 0 deletions

diff --git a/filter/test.conf b/filter/test.conf
index fb35afb..395699b 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -131,6 +131,9 @@ prefix px;
 ip p;
 pair pp;
 int set is;
+int set is1;
+int set is2;
+int set is3;
 prefix set pxs;
 string s;
 {
@@ -156,6 +159,18 @@ string s;
 	print "  must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2;
 	print "  data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1.0.0.0/9 ~ [ 1.0.0.0/8- ], ",", 1.2.0.0/17 ~ [ 1.0.0.0/8{ 15 , 16 } ], ",", true && false;
 
+	is1 = [2, 3, 5, 8, 11, 15, 17, 19];
+	is2 = [19, 17, 15, 11, 8, 5, 3, 2];
+	is3 = [5, 17, 2, 11, 8, 15, 3, 19];
+
+	print "  must be true:  ", 2 ~ is1, "  ", 2 ~ is2, "  ", 2 ~ is3;
+	print "  must be false: ", 4 ~ is1, " ", 4 ~ is2, " ", 4 ~ is3;
+	print "  must be false: ", 10 ~ is1, " ", 10 ~ is2, " ", 10 ~ is3;
+	print "  must be true:  ", 15 ~ is1, "  ", 15 ~ is2, "  ", 15 ~ is3;
+	print "  must be false: ", 18 ~ is1, " ", 18 ~ is2, " ", 18 ~ is3;
+	print "  must be true:  ", 19 ~ is1, "  ", 19 ~ is2, "  ", 19 ~ is3;
+	print "  must be false: ", 20 ~ is1, " ", 20 ~ is2, " ", 20 ~ is3;
+
 	px = 1.2.0.0/18;
 	print "Testing prefixes: 1.2.0.0/18 = ", px;
 	print "  must be true:  ",	192.168.0.0/16 ~ 192.168.0.0/16, " ", 192.168.0.0/17 ~ 192.168.0.0/16, " ", 192.168.254.0/24 ~ 192.168.0.0/16;