git: 9front

Download patch

ref: c6ce7106c61a1145e420290e90f62580c6f04d21
parent: 5c84080c8bd348ee4179205f18f54536f3474f2d
author: cinap_lenrek <cinap_lenrek@felloff.net>
date: Wed Jul 23 11:28:37 EDT 2014 

rc: fix slow Xqdol(), avoid recursion in conclist(), estrdup(), avoid copying

Xqdol() used to take quadratic time because of strcat(),
the code isnt really needed as list2str() aready does the
same thing in linear time without the strcat().

add estrdup() which uses emalloc() so allocation error are
catched.

move strdups() of name from callers into newvar().

avoid recursion of conclist(), and avoid copying of word
strings by providing Newword() function which doesnt copy
the word string.


--- a/sys/src/cmd/rc/code.c
+++ b/sys/src/cmd/rc/code.c
@@ -56,7 +56,7 @@
 cleanhere(char *f)
 {
 	emitf(Xdelhere);
-	emits(strdup(f));
+	emits(estrdup(f));
 }
 
 char*
@@ -258,7 +258,7 @@
 		else{
 			emitf(Xmark);
 			emitf(Xword);
-			emits(strdup("*"));
+			emits(estrdup("*"));
 			emitf(Xdol);
 		}
 		emitf(Xmark);		/* dummy value for Xlocal */
@@ -275,7 +275,7 @@
 		break;
 	case WORD:
 		emitf(Xword);
-		emits(strdup(t->str));
+		emits(estrdup(t->str));
 		break;
 	case DUP:
 		if(t->rtype==DUPFD){
--- a/sys/src/cmd/rc/exec.c
+++ b/sys/src/cmd/rc/exec.c
@@ -28,23 +28,33 @@
 }
 
 word*
-newword(char *wd, word *next)
+Newword(char *wd, word *next)
 {
 	word *p = new(word);
-	p->word = strdup(wd);
+	p->word = wd;
 	p->next = next;
 	return p;
 }
-
 void
-pushword(char *wd)
+Pushword(char *wd)
 {
 	if(runq->argv==0)
 		panic("pushword but no argv!", 0);
-	runq->argv->words = newword(wd, runq->argv->words);
+	runq->argv->words = Newword(wd, runq->argv->words);
 }
 
+word*
+newword(char *wd, word *next)
+{
+	return Newword(estrdup(wd), next);
+}
 void
+pushword(char *wd)
+{
+	Pushword(estrdup(wd));
+}
+
+void
 popword(void)
 {
 	word *p;
@@ -113,7 +123,7 @@
 newvar(char *name, var *next)
 {
 	var *v = new(var);
-	v->name = name;
+	v->name = estrdup(name);
 	v->val = 0;
 	v->fn = 0;
 	v->changed = 0;
@@ -174,7 +184,7 @@
 	start(bootstrap, 1, (var *)0);
 	/* prime bootstrap argv */
 	pushlist();
-	argv0 = strdup(argv[0]);
+	argv0 = estrdup(argv[0]);
 	for(i = argc-1;i!=0;--i) pushword(argv[i]);
 	for(;;){
 		if(flag['r'])
@@ -304,7 +314,7 @@
 			--runq->pc;
 			starval = vlook("*")->val;
 			start(trapreq->fn, trapreq->pc, (struct var *)0);
-			runq->local = newvar(strdup("*"), runq->local);
+			runq->local = newvar("*", runq->local);
 			runq->local->val = copywords(starval, (struct word *)0);
 			runq->local->changed = 1;
 			runq->redir = runq->startredir = 0;
@@ -548,16 +558,21 @@
 word*
 conclist(word *lp, word *rp, word *tail)
 {
-	char *buf;
-	word *v;
-	if(lp->next || rp->next)
-		tail = conclist(lp->next==0? lp: lp->next,
-			rp->next==0? rp: rp->next, tail);
-	buf = emalloc(strlen(lp->word)+strlen((char *)rp->word)+1);
-	strcpy(buf, lp->word);
-	strcat(buf, rp->word);
-	v = newword(buf, tail);
-	efree(buf);
+	word *v, *p, **end;
+	int ln, rn;
+
+	for(end = &v;;){
+		ln = strlen(lp->word), rn = strlen(rp->word);
+		p = Newword(emalloc(ln+rn+1), (word *)0);
+		Memcpy(p->word, lp->word, ln);
+		Memcpy(p->word+ln, rp->word, rn+1);
+		*end = p, end = &p->next;
+		if(lp->next == 0 && rp->next == 0)
+			break;
+		if(lp->next) lp = lp->next;
+		if(rp->next) rp = rp->next;
+	}
+	*end = tail;
 	return v;
 }
 
@@ -647,9 +662,8 @@
 void
 Xqdol(void)
 {
-	word *a, *p;
 	char *s;
-	int n;
+	word *a;
 	if(count(runq->argv->words)!=1){
 		Xerror1("variable name not singleton!");
 		return;
@@ -658,24 +672,7 @@
 	deglob(s);
 	a = vlook(s)->val;
 	poplist();
-	n = count(a);
-	if(n==0){
-		pushword("");
-		return;
-	}
-	for(p = a;p;p = p->next) n+=strlen(p->word);
-	s = emalloc(n);
-	if(a){
-		strcpy(s, a->word);
-		for(p = a->next;p;p = p->next){
-			strcat(s, " ");
-			strcat(s, p->word);
-		}
-	}
-	else
-		s[0]='\0';
-	pushword(s);
-	efree(s);
+	Pushword(list2str(a));
 }
 
 word*
@@ -780,7 +777,7 @@
 		return;
 	}
 	deglob(runq->argv->words->word);
-	runq->local = newvar(strdup(runq->argv->words->word), runq->local);
+	runq->local = newvar(runq->argv->words->word, runq->local);
 	poplist();
 	globlist();
 	runq->local->val = runq->argv->words;
--- a/sys/src/cmd/rc/haventfork.c
+++ b/sys/src/cmd/rc/haventfork.c
@@ -14,7 +14,7 @@
 	word *p;
 
 	p = vlook("*")->val;
-	argv = malloc((count(p)+6)*sizeof(char*));
+	argv = emalloc((count(p)+6)*sizeof(char*));
 	argc = 0;
 	argv[argc++] = argv0;
 	if(flag['e'])
--- a/sys/src/cmd/rc/here.c
+++ b/sys/src/cmd/rc/here.c
@@ -34,7 +34,7 @@
 	h->tag = tag;
 	hexnum(&tmp[9], getpid());
 	hexnum(&tmp[14], ser++);
-	h->name = strdup(tmp);
+	h->name = estrdup(tmp);
 	return token(tmp, WORD);
 }
 /*
--- a/sys/src/cmd/rc/rc.h
+++ b/sys/src/cmd/rc/rc.h
@@ -103,6 +103,7 @@
 void *emalloc(long);
 void *erealloc(void *, long);
 void efree(void *);
+char *estrdup(char*);
 
 #define	NOFILE	128		/* should come from <param.h> */
 
--- a/sys/src/cmd/rc/simple.c
+++ b/sys/src/cmd/rc/simple.c
@@ -131,7 +131,7 @@
 	runq->argv->words = 0;
 	poplist();
 	start(func->fn, func->pc, runq->local);
-	runq->local = newvar(strdup("*"), runq->local);
+	runq->local = newvar("*", runq->local);
 	runq->local->val = starval;
 	runq->local->changed = 1;
 }
@@ -172,7 +172,7 @@
 				dir = smprint("%s/%s", cdpath->word,
 					a->next->word);
 			else
-				dir = strdup(a->next->word);
+				dir = estrdup(a->next->word);
 
 			if(dochdir(dir) >= 0){
 				if(cdpath->word[0] != '\0' &&
@@ -355,7 +355,7 @@
 		Xerror1("Usage: . [-i] file [arg ...]");
 		return;
 	}
-	zero = strdup(p->argv->words->word);
+	zero = estrdup(p->argv->words->word);
 	popword();
 	fd = -1;
 	for(path = searchpath(zero); path; path = path->next){
@@ -362,7 +362,7 @@
 		if(path->word[0] != '\0')
 			file = smprint("%s/%s", path->word, zero);
 		else
-			file = strdup(zero);
+			file = estrdup(zero);
 
 		fd = open(file, 0);
 		free(file);
@@ -480,7 +480,7 @@
 						file = smprint("%s/%s",
 							path->word, a->word);
 					else
-						file = strdup(a->word);
+						file = estrdup(a->word);
 					if(Executable(file)){
 						pfmt(out, "%s\n", file);
 						free(file);
--- a/sys/src/cmd/rc/subr.c
+++ b/sys/src/cmd/rc/subr.c
@@ -30,6 +30,19 @@
 		free(p);
 	else pfmt(err, "free 0\n");
 }
+
+char*
+estrdup(char *s)
+{
+	char *d;
+	int n;
+
+	n = strlen(s)+1;
+	d = emalloc(n);
+	Memcpy(d, s, n);
+	return d;
+}
+
 extern int lastword, lastdol;
 
 void
--- a/sys/src/cmd/rc/trap.c
+++ b/sys/src/cmd/rc/trap.c
@@ -18,7 +18,7 @@
 		trapreq = vlook(Signame[i]);
 		if(trapreq->fn){
 			start(trapreq->fn, trapreq->pc, (struct var *)0);
-			runq->local = newvar(strdup("*"), runq->local);
+			runq->local = newvar("*", runq->local);
 			runq->local->val = copywords(starval, (struct word *)0);
 			runq->local->changed = 1;
 			runq->redir = runq->startredir = 0;
--- a/sys/src/cmd/rc/tree.c
+++ b/sys/src/cmd/rc/tree.c
@@ -111,7 +111,7 @@
 	t = tree1(SIMPLE, t);
 	s = openstr();
 	pfmt(s, "%t", t);
-	t->str = strdup((char *)s->strp);
+	t->str = estrdup((char *)s->strp);
 	closeio(s);
 	for(u = t->child[0];u->type==ARGLIST;u = u->child[0]){
 		if(u->child[1]->type==DUP
--- a/sys/src/cmd/rc/unix.c
+++ b/sys/src/cmd/rc/unix.c
@@ -256,7 +256,7 @@
 		case ENOEXEC:
 			pfmt(err, "%s: Bourne again\n", argv[1]);
 			argv[0]="sh";
-			argv[1] = strdup(file);
+			argv[1] = estrdup(file);
 			execve("/bin/sh", argv, env);
 			goto Bad;
 		case ETXTBSY:
--- a/sys/src/cmd/rc/var.c
+++ b/sys/src/cmd/rc/var.c
@@ -63,7 +63,7 @@
 	int h = hash(name, NVAR);
 	var *v;
 	for(v = gvar[h];v;v = v->next) if(strcmp(v->name, name)==0) return v;
-	return gvar[h] = newvar(strdup(name), gvar[h]);
+	return gvar[h] = newvar(name, gvar[h]);
 }
 
 var*
-- 
⑨