# HG changeset patch
# User William Astle <lost@l-w.ca>
# Date 1406995681 21600
# Node ID 3b5a45c6ab9296d48a718daf8a0a10e5caa530ce
# Parent  30b2bad9b5eb4bb0599488c5b7fc0cfd377bbda9
Speed improvement to lw_expr

Instead of using a singly linked list and doing the slow append algorithm
when adding an operand to an expression (scan from the start to find the
end), now maintain a tail pointer. Also maintain a previous pointer in each
entry. Benchmarking suggests this yields a rougly 30% improvement in
runtime.

Also refactor some of the code in lw_expr.c to make it somewhat clearer to
understand. For some values of clearer and understand.

diff -r 30b2bad9b5eb -r 3b5a45c6ab92 lwlib/lw_expr.c
--- a/lwlib/lw_expr.c	Thu Jul 31 17:20:11 2014 -0600
+++ b/lwlib/lw_expr.c	Sat Aug 02 10:08:01 2014 -0600
@@ -105,24 +105,43 @@
 	
 	r = lw_alloc(sizeof(struct lw_expr_priv));
 	r -> operands = NULL;
+	r -> operand_tail = NULL;
 	r -> value2 = NULL;
 	r -> type = lw_expr_type_int;
 	r -> value = 0;
 	return r;
 }
 
+static lw_expr_t lw_expr_remove_operand(lw_expr_t E, struct lw_expr_opers *o)
+{
+	lw_expr_t r;
+	if (E -> operands == o)
+		E -> operands = o -> next;
+	else
+		o -> prev -> next = o -> next;
+	
+	if (E -> operand_tail == o)
+		E -> operand_tail = o -> prev;
+	else
+		o -> next -> prev = o -> prev;
+	
+	r = o -> p;
+	lw_free(o);
+	return r;
+}
+
+void lw_expr_destroy(lw_expr_t E);
+static void lw_expr_remove_operands(lw_expr_t E)
+{
+	while (E -> operands)
+		lw_expr_destroy(lw_expr_remove_operand(E, E -> operands));
+}
+
 void lw_expr_destroy(lw_expr_t E)
 {
-	struct lw_expr_opers *o;
 	if (!E)
 		return;
-	while (E -> operands)
-	{
-		o = E -> operands;
-		E -> operands = o -> next;
-		lw_expr_destroy(o -> p);
-		lw_free(o);
-	}
+	lw_expr_remove_operands(E);
 	if (E -> type == lw_expr_type_var)
 		lw_free(E -> value2);
 	lw_free(E);
@@ -153,18 +172,18 @@
 
 void lw_expr_add_operand(lw_expr_t E, lw_expr_t O)
 {
-	struct lw_expr_opers *o, *t;
+	struct lw_expr_opers *o;
 	
 	o = lw_alloc(sizeof(struct lw_expr_opers));
 	o -> p = lw_expr_copy(O);
 	o -> next = NULL;
-	for (t = E -> operands; t && t -> next; t = t -> next)
-		/* do nothing */ ;
+	o -> prev = E -> operand_tail;
 	
-	if (t)
-		t -> next = o;
+	if (E -> operands)
+		E -> operand_tail -> next = o;
 	else
 		E -> operands = o;
+	E -> operand_tail = o;
 }
 
 lw_expr_t lw_expr_build_aux(int exprtype, va_list args)
@@ -422,18 +441,27 @@
 			lw_expr_simplify_sortconstfirst(o -> p);
 	}
 	
-	for (o = E -> operands; o; o = o -> next)
+	for (o = E -> operands; o; )
 	{
+		struct lw_expr_opers *o2;
+		o2 = o -> next;
 		if (o -> p -> type == lw_expr_type_int && o != E -> operands)
 		{
-			struct lw_expr_opers *o2;
-			for (o2 = E -> operands; o2 -> next != o; o2 = o2 -> next)
-				/* do nothing */ ;
-			o2 -> next = o -> next;
+			// because o cannot be the first operand, we don't have to
+			// handle the single element list here
+			o2 = o -> next;
+			if (E -> operand_tail == o)
+				E -> operand_tail = o -> prev;
+			o -> prev -> next = o -> next;
+			if (o -> next)
+				o -> next -> prev = o -> prev;
+			E -> operands -> prev = o;
 			o -> next = E -> operands;
+			o -> prev = NULL;
 			E -> operands = o;
-			o = o2;
+			E -> operands = o;
 		}
+		o = o2;
 	}
 }
 
@@ -585,7 +613,8 @@
 				lw_free(E -> value2);
 			*E = *te;
 			E -> operands = NULL;
-	
+			E -> operand_tail = NULL;
+			
 			if (te -> type == lw_expr_type_var)
 				E -> value2 = lw_strdup(te -> value2);
 			for (o = te -> operands; o; o = o -> next)
@@ -616,6 +645,7 @@
 				lw_free(E -> value2);
 			*E = *te;
 			E -> operands = NULL;
+			E -> operand_tail = NULL;
 	
 			if (te -> type == lw_expr_type_var)
 				E -> value2 = lw_strdup(te -> value2);
@@ -641,20 +671,32 @@
 		{
 			if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_plus)
 			{
-				struct lw_expr_opers *o2;
-				// we have a + operation - bring operands up
-				
-				for (o2 = E -> operands; o2 && o2 -> next != o; o2 = o2 -> next)
-					/* do nothing */ ;
-				if (o2)
-					o2 -> next = o -> p -> operands;
-				else
-					E -> operands = o -> p -> operands;
-				for (o2 = o -> p -> operands; o2 -> next; o2 = o2 -> next)
-					/* do nothing */ ;
-				o2 -> next = o -> next;
+				if (o -> p -> operands)
+				{
+					if (E -> operands == NULL)
+					{
+						E -> operands = o -> p -> operands;
+						E -> operand_tail = o -> p -> operand_tail;
+					}
+					else
+					{
+						E -> operand_tail -> next = o -> p -> operands;
+						o -> p -> operands -> prev = E -> operand_tail;
+						E -> operand_tail = o -> p -> operand_tail;
+					}
+					o -> p -> operands = NULL;
+					o -> p -> operand_tail = NULL;
+				}
 				o -> p -> operands = NULL;
 				lw_expr_destroy(o -> p);
+				if (o -> prev)
+					o -> prev -> next = o -> next;
+				else
+					E -> operands = o -> next;
+				if (o -> next)
+					o -> next -> prev = o -> prev;
+				else
+					E -> operand_tail = o -> prev;
 				lw_free(o);
 				goto tryagainplus;
 			}
@@ -669,20 +711,32 @@
 		{
 			if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_times)
 			{
-				struct lw_expr_opers *o2;
-				// we have a + operation - bring operands up
-				
-				for (o2 = E -> operands; o2 && o2 -> next != o; o2 = o2 -> next)
-					/* do nothing */ ;
-				if (o2)
-					o2 -> next = o -> p -> operands;
-				else
-					E -> operands = o -> p -> operands;
-				for (o2 = o -> p -> operands; o2 -> next; o2 = o2 -> next)
-					/* do nothing */ ;
-				o2 -> next = o -> next;
+				if (o -> p -> operands)
+				{
+					if (E -> operands == NULL)
+					{
+						E -> operands = o -> p -> operands;
+						E -> operand_tail = o -> p -> operand_tail;
+					}
+					else
+					{
+						E -> operand_tail -> next = o -> p -> operands;
+						o -> p -> operands -> prev = E -> operand_tail;
+						E -> operand_tail = o -> p -> operand_tail;
+					}
+					o -> p -> operands = NULL;
+					o -> p -> operand_tail = NULL;
+				}
 				o -> p -> operands = NULL;
 				lw_expr_destroy(o -> p);
+				if (o -> prev)
+					o -> prev -> next = o -> next;
+				else
+					E -> operands = o -> next;
+				if (o -> next)
+					o -> next -> prev = o -> prev;
+				else
+					E -> operand_tail = o -> prev;
 				lw_free(o);
 				goto tryagaintimes;
 			}
@@ -785,13 +839,7 @@
 		
 		}
 		
-		while (E -> operands)
-		{
-			o = E -> operands;
-			E -> operands = o -> next;
-			lw_expr_destroy(o -> p);
-			lw_free(o);
-		}
+		lw_expr_remove_operands(E);
 		E -> type = lw_expr_type_int;
 		E -> value = tr;
 		return;
@@ -804,7 +852,9 @@
 		
 		e1 = lw_expr_create();
 		e1 -> operands = E -> operands;
+		e1 -> operand_tail = E -> operand_tail;
 		E -> operands = 0;
+		E -> operand_tail = NULL;
 		
 		for (o = e1 -> operands; o; o = o -> next)
 		{
@@ -829,7 +879,9 @@
 		
 		e1 = lw_expr_create();
 		e1 -> operands = E -> operands;
+		e1 -> operand_tail = E -> operand_tail;
 		E -> operands = 0;
+		E -> operand_tail = NULL;
 		
 		for (o = e1 -> operands; o; o = o -> next)
 		{
@@ -854,13 +906,7 @@
 			if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0)
 			{
 				// one operand of times is 0, replace operation with 0
-				while (E -> operands)
-				{
-					o = E -> operands;
-					E -> operands = o -> next;
-					lw_expr_destroy(o -> p);
-					lw_free(o);
-				}
+				lw_expr_remove_operands(E);
 				E -> type = lw_expr_type_int;
 				E -> value = 0;
 				return;
@@ -964,9 +1010,7 @@
 				{
 					r = lw_expr_copy(o -> p);
 				}
-				E -> operands = o -> next;
-				lw_expr_destroy(o -> p);
-				lw_free(o);
+				lw_expr_destroy(lw_expr_remove_operand(E, E -> operands));
 			}
 			*E = *r;
 			lw_free(r);
@@ -975,13 +1019,7 @@
 		else if (c == 0)
 		{
 			// replace with 0
-			while (E -> operands)
-			{
-				o = E -> operands;
-				E -> operands = o -> next;
-				lw_expr_destroy(o -> p);
-				lw_free(o);
-			}
+			lw_expr_remove_operands(E);
 			E -> type = lw_expr_type_int;
 			E -> value = 0;
 			return;
@@ -991,26 +1029,12 @@
 			// collapse out zero terms
 			struct lw_expr_opers *o2;
 			
-			for (o = E -> operands; o; o = o -> next)
+			for (o = E -> operands; o; o = o2)
 			{
+				o2 = o -> next;
 				if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0)
 				{
-					if (o == E -> operands)
-					{
-						E -> operands = o -> next;
-						lw_expr_destroy(o -> p);
-						lw_free(o);
-						o = E -> operands;
-					}
-					else
-					{
-						for (o2 = E -> operands; o2 -> next == o; o2 = o2 -> next)
-							/* do nothing */ ;
-						o2 -> next = o -> next;
-						lw_expr_destroy(o -> p);
-						lw_free(o);
-						o = o2;
-					}
+					lw_expr_destroy(lw_expr_remove_operand(E, o));
 				}
 			}
 		}
@@ -1035,6 +1059,7 @@
 					lw_free(E -> operands -> next);
 					lw_free(E -> operands);
 					E -> operands = NULL;
+					E -> operand_tail = NULL;
 					E -> value = lw_expr_oper_plus;
 					
 					for (o = E2 -> operands; o; o = o -> next)
@@ -1043,9 +1068,6 @@
 						lw_expr_add_operand(E, t1);
 						lw_expr_destroy(t1);
 					}
-					
-					lw_expr_destroy(E2);
-					lw_expr_destroy(E3);
 				}
 			}
 			else if (E -> operands -> next -> p -> type == lw_expr_type_int)
@@ -1058,6 +1080,7 @@
 					lw_free(E -> operands -> next);
 					lw_free(E -> operands);
 					E -> operands = NULL;
+					E -> operand_tail = NULL;
 					E -> value = lw_expr_oper_plus;
 					
 					for (o = E2 -> operands; o; o = o -> next)
diff -r 30b2bad9b5eb -r 3b5a45c6ab92 lwlib/lw_expr.h
--- a/lwlib/lw_expr.h	Thu Jul 31 17:20:11 2014 -0600
+++ b/lwlib/lw_expr.h	Sat Aug 02 10:08:01 2014 -0600
@@ -58,6 +58,7 @@
 {
 	lw_expr_t p;
 	struct lw_expr_opers *next;
+	struct lw_expr_opers *prev;
 };
 
 struct lw_expr_priv
@@ -66,6 +67,7 @@
 	int value;							// integer value
 	void *value2;						// misc pointer value
 	struct lw_expr_opers *operands;		// ptr to list of operands (for operators)
+	struct lw_expr_opers *operand_tail;	// ptr to last operand
 };
 
 typedef lw_expr_t lw_expr_fn_t(int t, void *ptr, void *priv);