# HG changeset patch
# User William Astle <lost@l-w.ca>
# Date 1331503554 21600
# Node ID 17bd59f045afa07684865fb72f47ed35dbe04cd5
# Parent  f8b33b3a45ac87a72037f0a5def9eed1c7e759b1
Changed symbol table to use a binary tree.

Changed symbol table to use a binary tree. Hopefully this improves table
lookups some but the tree really needs to be balanced at some point.

diff -r f8b33b3a45ac -r 17bd59f045af lwasm/lwasm.h
--- a/lwasm/lwasm.h	Wed Jan 25 22:39:17 2012 -0700
+++ b/lwasm/lwasm.h	Sun Mar 11 16:05:54 2012 -0600
@@ -204,7 +204,9 @@
 	int flags;							// flags for the symbol
 	sectiontab_t *section;				// section the symbol is defined in
 	lw_expr_t value;					// symbol value
-	struct symtabe *next;				// next symbol in the table
+	struct symtabe *left;				// left subtree pointer
+	struct symtabe *right;				// right subtree pointer
+	struct symtabe *nextver;			// next lower version
 };
 
 typedef struct
diff -r f8b33b3a45ac -r 17bd59f045af lwasm/output.c
--- a/lwasm/output.c	Wed Jan 25 22:39:17 2012 -0700
+++ b/lwasm/output.c	Sun Mar 11 16:05:54 2012 -0600
@@ -367,6 +367,66 @@
 	return 0;
 }
 
+void write_code_obj_auxsym(asmstate_t *as, FILE *of, sectiontab_t *s, struct symtabe *se2)
+{
+	struct symtabe *se;
+	unsigned char buf[16];
+		
+	if (!se2)
+		return;
+	write_code_obj_auxsym(as, of, s, se2 -> left);
+	
+	for (se = se2; se; se = se -> nextver)
+	{
+		lw_expr_t te;
+		
+		debug_message(as, 200, "Consider symbol %s (%p) for export in section %p", se -> symbol, se -> section, s);
+		
+		// ignore symbols not in this section
+		if (se -> section != s)
+			continue;
+		
+		debug_message(as, 200, "  In section");
+			
+		if (se -> flags & symbol_flag_set)
+			continue;
+			
+		debug_message(as, 200, "  Not symbol_flag_set");
+			
+		te = lw_expr_copy(se -> value);
+		debug_message(as, 200, "  Value=%s", lw_expr_print(te));
+		as -> exportcheck = 1;
+		as -> csect = s;
+		lwasm_reduce_expr(as, te);
+		as -> exportcheck = 0;
+
+		debug_message(as, 200, "  Value2=%s", lw_expr_print(te));
+			
+		// don't output non-constant symbols
+		if (!lw_expr_istype(te, lw_expr_type_int))
+		{
+			lw_expr_destroy(te);
+			continue;
+		}
+
+		writebytes(se -> symbol, strlen(se -> symbol), 1, of);
+		if (se -> context >= 0)
+		{
+			writebytes("\x01", 1, 1, of);
+			sprintf((char *)buf, "%d", se -> context);
+			writebytes(buf, strlen((char *)buf), 1, of);
+		}
+		// the "" is NOT an error
+		writebytes("", 1, 1, of);
+			
+		// write the address
+		buf[0] = (lw_expr_intval(te) >> 8) & 0xff;
+		buf[1] = lw_expr_intval(te) & 0xff;
+		writebytes(buf, 2, 1, of);
+		lw_expr_destroy(te);
+	}
+	write_code_obj_auxsym(as, of, s, se2 -> right);
+}
 
 void write_code_obj(asmstate_t *as, FILE *of)
 {
@@ -374,7 +434,6 @@
 	sectiontab_t *s;
 	reloctab_t *re;
 	exportlist_t *ex;
-	struct symtabe *se;
 
 	int i;
 	unsigned char buf[16];
@@ -443,55 +502,8 @@
 			// address 0; "\0" is not an error
 			writebytes("\0", 2, 1, of);
 		}
-		for (se = as -> symtab.head; se; se = se -> next)
-		{
-			lw_expr_t te;
-			
-			debug_message(as, 200, "Consider symbol %s (%p) for export in section %p", se -> symbol, se -> section, s);
-			
-			// ignore symbols not in this section
-			if (se -> section != s)
-				continue;
-			
-			debug_message(as, 200, "  In section");
-			
-			if (se -> flags & symbol_flag_set)
-				continue;
-			
-			debug_message(as, 200, "  Not symbol_flag_set");
-			
-			te = lw_expr_copy(se -> value);
-			debug_message(as, 200, "  Value=%s", lw_expr_print(te));
-			as -> exportcheck = 1;
-			as -> csect = s;
-			lwasm_reduce_expr(as, te);
-			as -> exportcheck = 0;
-
-			debug_message(as, 200, "  Value2=%s", lw_expr_print(te));
-			
-			// don't output non-constant symbols
-			if (!lw_expr_istype(te, lw_expr_type_int))
-			{
-				lw_expr_destroy(te);
-				continue;
-			}
-
-			writebytes(se -> symbol, strlen(se -> symbol), 1, of);
-			if (se -> context >= 0)
-			{
-				writebytes("\x01", 1, 1, of);
-				sprintf((char *)buf, "%d", se -> context);
-				writebytes(buf, strlen((char *)buf), 1, of);
-			}
-			// the "" is NOT an error
-			writebytes("", 1, 1, of);
-			
-			// write the address
-			buf[0] = (lw_expr_intval(te) >> 8) & 0xff;
-			buf[1] = lw_expr_intval(te) & 0xff;
-			writebytes(buf, 2, 1, of);
-			lw_expr_destroy(te);
-		}	
+		
+		write_code_obj_auxsym(as, of, s, as -> symtab.head);
 		// flag end of local symbol table - "" is NOT an error
 		writebytes("", 1, 1, of);
 		
diff -r f8b33b3a45ac -r 17bd59f045af lwasm/symbol.c
--- a/lwasm/symbol.c	Wed Jan 25 22:39:17 2012 -0700
+++ b/lwasm/symbol.c	Sun Mar 11 16:05:54 2012 -0600
@@ -29,6 +29,7 @@
 
 #include "lwasm.h"
 
+#if 0
 struct symtabe *symbol_findprev(asmstate_t *as, struct symtabe *se)
 {
 	struct symtabe *se1, *se2;
@@ -72,16 +73,17 @@
 	}
 	return se2;
 }
-
+#endif
 struct symtabe *register_symbol(asmstate_t *as, line_t *cl, char *sym, lw_expr_t val, int flags)
 {
-	struct symtabe *se;
+	struct symtabe *se, *nse;
 	struct symtabe *sprev;
 	int islocal = 0;
 	int context = -1;
 	int version = -1;
 	char *cp;
-
+	int cdir;
+	
 	debug_message(as, 200, "Register symbol %s (%02X), %s", sym, flags, lw_expr_print(val));
 
 	if (!(flags & symbol_flag_nocheck))
@@ -123,24 +125,33 @@
 		context = cl -> context;
 	
 	// first, look up symbol to see if it is already defined
-	for (se = as -> symtab.head; se; se = se -> next)
+	cdir = 0;
+	for (se = as -> symtab.head, sprev = NULL; se; )
 	{
-		debug_message(as, 300, "Symbol add lookup: %p, %p", se, se -> next);
-		if (!strcmp(sym, se -> symbol))
+		int ndir;
+		debug_message(as, 300, "Symbol add lookup: %p", se);
+		ndir = strcmp(sym, se->symbol);
+		if (!ndir && se -> context != context)
 		{
-			if (se -> context != context)
-				continue;
+			ndir = (context < se -> context) ? -1 : 1;
+		}
+		if (!ndir)
+		{
 			if ((flags & symbol_flag_set) && (se -> flags & symbol_flag_set))
 			{
-				if (version < se -> version)
-					version = se -> version;
-					continue;
+				version = se -> version;
 			}
 			break;
 		}
+		cdir = ndir;
+		sprev = se;
+		if (cdir < 0)
+			se = se -> left;
+		else
+			se = se -> right;
 	}
 
-	if (se)
+	if (se && version == -1)
 	{
 		// multiply defined symbol
 		lwasm_register_error(as, cl, "Multiply defined symbol (%s)", sym);
@@ -156,34 +167,45 @@
 	// symbol table entries
 	lwasm_reduce_expr(as, val);
 
-	se = lw_alloc(sizeof(struct symtabe));
-	se -> context = context;
-	se -> version = version;
-	se -> flags = flags;
+	nse = lw_alloc(sizeof(struct symtabe));
+	nse -> context = context;
+	nse -> version = version;
+	nse -> flags = flags;
 	if (CURPRAGMA(cl, PRAGMA_NOLIST))
 	{
-		se -> flags |= symbol_flag_nolist;
+		nse -> flags |= symbol_flag_nolist;
 	}
-	se -> value = lw_expr_copy(val);
-	se -> symbol = lw_strdup(sym);
+	nse -> value = lw_expr_copy(val);
+	nse -> symbol = lw_strdup(sym);
+	nse -> right = NULL;
+	nse -> left = NULL;
+	nse -> nextver = NULL;
+	if (se)
+	{
+		nse -> nextver = se;
+		nse -> left = se -> left;
+		nse -> right = se -> right;
+		se -> left = NULL;
+		se -> right = NULL;
+	}
 	if (cl)
-		se -> section = cl -> csect;
+		nse -> section = cl -> csect;
 	else
-		se -> section = NULL;
-	sprev = symbol_findprev(as, se);
+		nse -> section = NULL;
 	if (!sprev)
 	{
 		debug_message(as, 200, "Adding symbol at head of symbol table");
-		se -> next = as -> symtab.head;
-		as -> symtab.head = se;
+		as -> symtab.head = nse;
 	}
 	else
 	{
 		debug_message(as, 200, "Adding symbol in middle of symbol table");
-		se -> next = sprev -> next;
-		sprev -> next = se;
+		if (cdir < 0)
+			sprev -> left = nse;
+		else
+			sprev -> right = nse;
 	}
-	return se;
+	return nse;
 }
 
 // for "SET" symbols, always returns the LAST definition of the
@@ -199,8 +221,9 @@
 struct symtabe * lookup_symbol(asmstate_t *as, line_t *cl, char *sym)
 {
 	int local = 0;
-	struct symtabe *s, *s2;
-
+	struct symtabe *s;
+	int cdir;
+	
 	// check if this is a local symbol
 	if (strchr(sym, '@') || strchr(sym, '?'))
 		local = 1;
@@ -214,27 +237,26 @@
 	if (!cl && local)
 		return NULL;
 	
-	for (s = as -> symtab.head, s2 = NULL; s; s = s -> next)
+	for (s = as -> symtab.head; s; )
 	{
-		if (!strcmp(sym, s -> symbol))
+		cdir = strcmp(sym, s->symbol);
+		if (!cdir)
 		{
 			if (local && s -> context != cl -> context)
-				continue;
-			
-			if (s -> flags & symbol_flag_set)
 			{
-				// look for highest version of symbol
-				if (!s2 || (s -> version > s2 -> version))
-					s2 = s;
-				continue;
-			}
-			break;
+				cdir = (cl -> context < s -> context) ? -1 : 1;
+			}	
 		}
+		
+		if (!cdir)
+			return s;
+		
+		if (cdir < 0)
+			s = s -> left;
+		else
+			s = s -> right;
 	}
-	if (!s && s2)
-		s = s2;
-	
-	return s;
+	return NULL;
 }
 
 struct listinfo
@@ -268,18 +290,21 @@
 	return 0;
 }
 
-void list_symbols(asmstate_t *as, FILE *of)
+void list_symbols_aux(asmstate_t *as, FILE *of, struct symtabe *se)
 {
 	struct symtabe *s;
 	lw_expr_t te;
 	struct listinfo li;
 
 	li.as = as;
-		
-	fprintf(of, "\nSymbol Table:\n");
+	
+	if (!se)
+		return;
 	
-	for (s = as -> symtab.head; s; s = s -> next)
-	{
+	list_symbols_aux(as, of, se -> left);
+	
+	for (s = se; s; s = s -> nextver)
+	{	
 		if (s -> flags & symbol_flag_nolist)
 			continue;
 		lwasm_reduce_expr(as, s -> value);
@@ -332,4 +357,12 @@
 		}
 		lw_expr_destroy(te);
 	}
+	
+	list_symbols_aux(as, of, se -> right);
 }
+
+void list_symbols(asmstate_t *as, FILE *of)
+{
+	fprintf(of, "\nSymbol Table:\n");
+	list_symbols_aux(as, of, as -> symtab.head);
+}