[agd-cvs] server/src compile.c,1.22,1.23 compile.h,1.13,1.14 compile_options.h,1.14,1.15

[Peep P. <so...@us...>]

Update of /cvsroot/agd/server/src
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv11784

Modified Files:
	compile.c compile.h compile_options.h 
Log Message:
define_id now uses hash tables for identifiers

Index: compile.h
===================================================================
RCS file: /cvsroot/agd/server/src/compile.h,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- compile.h	7 Jun 2004 15:37:55 -0000	1.13
+++ compile.h	8 Jun 2004 20:24:10 -0000	1.14
@@ -11,30 +11,33 @@
 
 typedef struct {
 	char *name;
+	unsigned hashed_name;
+
 	int base_scope; /* The scope level at which this id was defined */
 	int index;
 	int type;
 	int lpc_type; /* The datatype of the id. Return type for functions. */
 	int has_been_called;
 
-	int *args; /*For ID_FUN_PROT and ID_FUN*/
-	int numarg;
+	int *args; /* For ID_FUN_PROT and ID_FUN. */
+	int num_arg;
 } def_id_t;
 
-def_id_t *define_id(char *name, int type, int lpc_type, int *args, int numarg);
+def_id_t *define_id(char *name, int type, int lpc_type, int *args, int num_arg);
 def_id_t *find_id(char *name);
 
 typedef struct {
 	int side_effect;
 	int type, direct_type;
+	int lval; /* If it can be used in lvalue context */
 } expr_t;
 
 int check_operand(int operator, int opr1, int opr2);
 
-int get_fun_index(object_t *ob, char *fun);
-void add_function(def_id_t *idp, int lineno/*, int **code, int codelen*/);
-void add_token(long int t);
-void add_two_tokens(long int t1, long int t2);
+/*int get_fun_index(object_t *ob, char *fun);*/
+void add_function(def_id_t *idp, int lineno);
+void add_token(int t);
+void add_two_tokens(int t1, int t2);
 def_id_t *add_variable(char *name, int lpc_type, int type);
 
 void redeclaration_error(def_id_t *id, int new_type);

Index: compile_options.h
===================================================================
RCS file: /cvsroot/agd/server/src/compile_options.h,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -d -r1.14 -r1.15
--- compile_options.h	7 Jun 2004 15:38:15 -0000	1.14
+++ compile_options.h	8 Jun 2004 20:24:11 -0000	1.15
@@ -35,18 +35,26 @@
    long will be cut off in the end. */
 #define NET_RECEIVEBUF 512
 
-/* Define this if you want to enable debugging for the driver. */
+/* Define this if you want to enable debugging for the driver.
+   There is no reason to disable debugging at this point - bugs lurk
+   at every corner. */
 #define DEBUG
 
 /* The type a function has if one isn't specified (e.g. create() { } )
- * Must be one of T_VOID, T_STRING, T_OBJECT or T_INT. */
+   Must be one of T_VOID, T_STRING, T_OBJECT or T_INT. */
 #define DEFAULT_FUNCTION_TYPE T_VOID
 
 /* Define this if you want to allow root to run AGD,
- * BUT ONLY IF YOU REALLY KNOW WHAT YOU ARE DOING!
- * AGD is probably not very secure at this point.
- * I will not take responsibility for anything that happens
- * because of this. */
+   BUT ONLY IF YOU REALLY KNOW WHAT YOU ARE DOING!
+   AGD is probably not very secure at this point.
+   I will not take responsibility for anything that happens
+   because of this. */
 #undef ALLOW_ROOT
 
+/* Size of global identifiers hash table. Should experiment with it. */
+#define GLOBAL_HASH_SIZE 1024
+
+/* Size of local identifiers hash table. Should experiment with it. */
+#define LOCAL_HASH_SIZE 10000
+
 #endif

Index: compile.c
===================================================================
RCS file: /cvsroot/agd/server/src/compile.c,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -d -r1.22 -r1.23
--- compile.c	7 Jun 2004 15:37:55 -0000	1.22
+++ compile.c	8 Jun 2004 20:24:10 -0000	1.23
@@ -23,15 +23,21 @@
 
 int compile_errors, compile_warnings;
 
-/* For define_id. */
-int scope_level;
-int numlvars, numgvars,
-    numdfuns, numlfuns;
+#if 0
 /* These are arrays to pointers. realloc might
  * move the memory segments, and we have
  * pointers to this memory - that would get corrupted. */
 def_id_t **local_ids, **global_ids;
 int num_local_ids, num_global_ids;
+#endif
+
+/* For define_id. */
+int scope_level;
+int numlvars, numgvars,
+    numdfuns, numlfuns;
+
+list_t gid_tbl[GLOBAL_HASH_SIZE]; /* Hash table for global identifiers. */
+list_t lid_tbl[LOCAL_HASH_SIZE]; /* Hash table for local identifiers. */
 
 #if YYDEBUG
 extern int yydebug;
@@ -41,6 +47,17 @@
 
 extern FILE *yyin;
 
+unsigned strhash(char *s)
+{
+	int h = *s;
+	if(!h)
+		return 0;
+	for(s++;*s;s++)
+		h = (h<<5)-h+*s;
+	return h;
+}
+
+#if 0
 /* define_id functions. */
 def_id_t *define_id(char *name, int type, int lpc_type, int *args, int numarg)
 {
@@ -85,12 +102,176 @@
 	}
 
 #ifdef DEBUG
-	debug("define_id", "%s base_scope %d index %d\n", idp->name, idp->base_scope, idp->index);
+	debug("define_id", "%s [hash %u] base_scope %d index %d\n",
+			idp->name, strhash(idp->name), idp->base_scope, idp->index);
+#endif
+
+	return idp;
+}
 #endif
 
+int assign_index(int type)
+{
+	switch(type) {
+		case ID_ARG:
+		case ID_LVAR:
+			return numlvars++;
+		case ID_GVAR:
+			return numgvars++;
+		case ID_FUN_PROT:
+		case ID_FUN:
+			return numlfuns++;
+		case ID_DFUN:
+			return numdfuns++;
+		default:
+			printf("assign_index(): invalid def_id_t type %d\n", type);
+			break;
+	}
+}
+
+void unassign_index(int type)
+{
+	switch(type) {
+		case ID_ARG:
+		case ID_LVAR:
+			numlvars--;
+			break;
+		case ID_GVAR:
+			numgvars--;
+			break;
+		case ID_FUN_PROT:
+		case ID_FUN:
+			numlfuns--;
+			break;
+		case ID_DFUN:
+			numdfuns--;
+			break;
+	}
+}
+
+void redeclaration_error(def_id_t *id, int new_type)
+{
+	char *buf, *buf2;
+	buf = xmalloc(strlen(id->name) + 100);
+	sprintf(buf, "%s redeclared as ", id->name);
+	switch(new_type) {
+		case ID_ARG:
+			buf2 = "function argument";
+			break;
+		case ID_FUN:
+			buf2 = "local function";
+			break;
+		case ID_LVAR:
+			buf2 = "local variable";
+			break;
+		case ID_GVAR:
+			buf2 = "global variable";
+			break;
+		default:
+			buf2 = "idontknowwhat!";
+			break;
+	}
+	buf = strcat(buf, buf2);
+	comp_error(buf);
+	xfree(buf);
+}
+
+int redeclaration_allowed(def_id_t *target, int type)
+{
+	if(target->base_scope >= scope_level)
+		return 0;
+
+	if(target->type == ID_FUN_PROT || target->type == ID_DFUN)
+		return 0;
+
+	return 1;
+}
+def_id_t *define_id(char *name, int type, int lpc_type, int *args, int num_arg)
+{
+	unsigned hash;
+	list_t *elem;
+	def_id_t *idp;
+
+	idp = xmalloc(sizeof(def_id_t));
+	
+	hash = strhash(name);
+
+	if(type == ID_DFUN)
+		elem = &gid_tbl[hash % GLOBAL_HASH_SIZE];
+	else
+		elem = &lid_tbl[hash % LOCAL_HASH_SIZE];
+
+	if(elem->data) {
+		def_id_t *target;
+		list_t temp, *new_list;
+		
+		target = elem->data;
+		if(!redeclaration_allowed(target, type)) {
+			redeclaration_error(target, type);
+			return;
+		}
+		
+		printf("hash collision! \"%s\" && \"%s\" == %d!\n", name, target->name, hash);
+		
+		temp = *elem;
+		
+		new_list = xmalloc(sizeof(list_t));
+		new_list->data = temp.data;
+		new_list->next = temp.next;
+		elem->data = idp;
+		elem->next = new_list;
+	} else {
+		elem->data = idp;
+	}
+
+	idp->hashed_name = hash;
+	idp->name = stringdup(name);
+	idp->type = type;
+	idp->lpc_type = lpc_type;
+	idp->args = args;
+	idp->num_arg = num_arg;
+	idp->base_scope = scope_level;
+	idp->index = assign_index(idp->type);
+
 	return idp;
 }
 
+static def_id_t *find_elem(list_t *tbl, unsigned tbl_size, unsigned hash) {
+	list_t *list;
+	def_id_t *idp;
+	
+	list = &tbl[hash % tbl_size];
+	if(list->data) {
+		list_t *p;
+		for(p=list; p; p=p->next) {
+			idp = p->data;
+			if(idp->hashed_name == hash)
+				return idp;
+		}
+	}
+
+	return NULL;
+}
+
+def_id_t *find_id(char *name)
+{
+	def_id_t *idp;
+	unsigned hash = strhash(name);
+	
+	/* First look in global table. */
+	idp = find_elem(gid_tbl, GLOBAL_HASH_SIZE, hash);
+	if(idp)
+		return idp;
+	
+	/* Now look in local table. */
+	idp = find_elem(lid_tbl, LOCAL_HASH_SIZE, hash);
+	if(idp)
+		return idp;
+
+	return NULL;
+}
+
+#if 0
 def_id_t *find_id(char *name)
 {
 	def_id_t *idp;
@@ -117,7 +298,9 @@
 	}
 	return NULL;
 }
+#endif
 
+#if 0
 void pop_scope()
 {
 	int i;
@@ -128,12 +311,68 @@
 /*			if(id->type == ID_LVAR || id->type == ID_ARG) { }
 			else if(id->type == ID_GVAR) { }*/
 			id->base_scope = -1; /* Temporary hack until identifiers use hash tables. */
+			switch(id->type) {
+				case ID_ARG:
+				case ID_LVAR:
+					numlvars--;
+					break;
+				case ID_GVAR:
+					numgvars--;
+					break;
+				case ID_FUN_PROT:
+				case ID_FUN:
+					numlfuns--;
+					break;
+				case ID_DFUN:
+					numdfuns--;
+					break;
+			}
+			
 			xfree(id->name);
 			if(id->args)
 				xfree(id->args);
 		}
 	}
 }
+#endif
+
+void clean_ids(list_t *tbl, unsigned tbl_size)
+{
+	def_id_t *idp;
+	int i;
+	
+	for(i=0;i<tbl_size;i++) {
+		if(tbl[i].data) {
+			idp = tbl[i].data;
+			if(idp->base_scope > scope_level) {
+				unassign_index(idp->type);
+				xfree(idp->name);
+				if(idp->args)
+					xfree(idp->args);
+				xfree(idp);
+
+				if(tbl[i].next) {
+					list_t *temp;
+					temp = tbl[i].next;
+					tbl[i] = *temp;
+					i--; /* Look over this chain again. */
+				} else {
+					tbl[i].data = NULL;
+				}
+			}
+		}
+	}
+
+}
+
+void pop_scope()
+{
+	scope_level--;
+
+	/* Ok, this is as ugly as it gets.. find another way. */
+	clean_ids(gid_tbl, GLOBAL_HASH_SIZE);
+	clean_ids(lid_tbl, LOCAL_HASH_SIZE);
+}
 
 /* Operator argument checking functions and definitions. */
 typedef struct {
@@ -256,7 +495,7 @@
 	}
 }
 
-void add_function(def_id_t *idp, int lineno/*, long int *code, int codelen*/)
+void add_function(def_id_t *idp, int lineno)
 {
 	if(idp->index < this_prog->numfunc) {
 		/* Adding a definition for a prototype. */
@@ -264,15 +503,12 @@
 		f = this_prog->functions[idp->index];
 		f->type = idp->lpc_type;
 		f->args = idp->args;
-		f->numarg = idp->numarg;
-/*		f->code = code;
-		f->codelen = codelen;*/
+		f->num_arg = idp->num_arg;
 		f->lineno = lineno;
 	} else {
 		curr_fun_check();
 		curr_fun->type = idp->lpc_type;
 		curr_fun->args = idp->args;
-/*		curr_fun->code = code;*/
 		curr_fun->lineno = lineno;
 		
 		this_prog->numfunc++;
@@ -286,20 +522,20 @@
 	}
 }
 
-void add_token(long int t)
+void add_token(int t)
 {
-		curr_fun_check();
-		curr_fun->codelen++;
-		curr_fun->code = xrealloc(curr_fun->code, sizeof(long int) * curr_fun->codelen);
-		curr_fun->code[curr_fun->codelen-1] = t;
+	curr_fun_check();
+	curr_fun->codelen++;
+	curr_fun->code = xrealloc(curr_fun->code, sizeof(int) * curr_fun->codelen);
+	curr_fun->code[curr_fun->codelen-1] = t;
 }
 
-void add_two_tokens(long int t1, long int t2)
+void add_two_tokens(int t1, int t2)
 {
-		curr_fun_check();
-		curr_fun->code = xrealloc(curr_fun->code, sizeof(long int) * (curr_fun->codelen+2));
-		curr_fun->code[curr_fun->codelen++] = t1;
-		curr_fun->code[curr_fun->codelen++] = t2;
+	curr_fun_check();
+	curr_fun->code = xrealloc(curr_fun->code, sizeof(int) * (curr_fun->codelen+2));
+	curr_fun->code[curr_fun->codelen++] = t1;
+	curr_fun->code[curr_fun->codelen++] = t2;
 }
 
 def_id_t *add_variable(char *name, int lpc_type, int type)
@@ -326,33 +562,6 @@
 	return define_id(name, type, lpc_type, NULL, 0);
 }
 
-void redeclaration_error(def_id_t *id, int new_type)
-{
-	char *buf, *buf2;
-	buf = xmalloc(strlen(id->name) + 16);
-	sprintf(buf, "%s redeclared as ", id->name);
-	switch(new_type) {
-		case ID_ARG:
-			buf2 = "function argument";
-			break;
-		case ID_FUN:
-			buf2 = "local function";
-			break;
-		case ID_LVAR:
-			buf2 = "local variable";
-			break;
-		case ID_GVAR:
-			buf2 = "global variable";
-			break;
-		default:
-			buf2 = "idontknowwhat!";
-			break;
-	}
-	buf = strcat(buf, buf2);
-	comp_error(buf);
-	xfree(buf);
-}
-
 /* This does the actual formatting. */
 void display_error(char *s)
 {
@@ -385,7 +594,7 @@
 	
 	numlvars = numgvars = 0;
 	numdfuns = numlfuns = 0;
-	num_local_ids = 0;
+/*	num_local_ids = 0;*/
 
 	yylloc.first_line = yylloc.first_column = 1;
 	yyreset();
@@ -397,16 +606,24 @@
 int check_fun_definitions(void)
 {
 	int i;
-	for(i=0;i<num_local_ids;i++) {
-		def_id_t *id = local_ids[i];
-		if(id->type == ID_FUN_PROT && id->has_been_called) {
-			char *buf;
-			buf = xmalloc(strlen(id->name) + 43);
-			sprintf(buf, "function %s has been called, "
-				     "but not defined", id->name);
-			comp_error(buf);
-			xfree(buf);
-			return 1;
+	for(i=0;i<LOCAL_HASH_SIZE;i++) {
+		if(lid_tbl[i].data) {
+			def_id_t *id = lid_tbl[i].data;
+			if(id->type == ID_FUN_PROT && id->has_been_called) {
+				char *buf;
+				buf = xmalloc(strlen(id->name) + 43);
+				sprintf(buf, "function %s has been called, "
+					     "but not defined", id->name);
+				comp_error(buf);
+				xfree(buf);
+				return 1;
+			}
+
+			if(lid_tbl[i].next) {
+				list_t *tmp = lid_tbl[i].next;
+				lid_tbl[i] = *tmp;
+				i--; /* Check this list_t again. */
+			}
 		}
 	}
 	return 0;
@@ -440,7 +657,7 @@
 	}
 
 	prog = xmalloc(sizeof(program_t));
-	memset(prog, 0, sizeof(program_t));
+	memset(prog, 0, sizeof *prog);
 	this_prog = prog;
 
 	parse_init();