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.

11 files changed, 64 insertions, 53 deletions

diff --git a/sys/src/cmd/rc/code.c b/sys/src/cmd/rc/code.c
index 3618838e3..7d1abbb3a 100644
--- a/sys/src/cmd/rc/code.c
+++ b/sys/src/cmd/rc/code.c
@@ -56,7 +56,7 @@ void
 cleanhere(char *f)
 {
 	emitf(Xdelhere);
-	emits(strdup(f));
+	emits(estrdup(f));
 }
 
 char*
@@ -258,7 +258,7 @@ outcode(tree *t, int eflag)
 		else{
 			emitf(Xmark);
 			emitf(Xword);
-			emits(strdup("*"));
+			emits(estrdup("*"));
 			emitf(Xdol);
 		}
 		emitf(Xmark);		/* dummy value for Xlocal */
@@ -275,7 +275,7 @@ outcode(tree *t, int eflag)
 		break;
 	case WORD:
 		emitf(Xword);
-		emits(strdup(t->str));
+		emits(estrdup(t->str));
 		break;
 	case DUP:
 		if(t->rtype==DUPFD){
diff --git a/sys/src/cmd/rc/exec.c b/sys/src/cmd/rc/exec.c
index c0fb8593f..a037d1df4 100644
--- a/sys/src/cmd/rc/exec.c
+++ b/sys/src/cmd/rc/exec.c
@@ -28,20 +28,30 @@ start(code *c, int pc, var *local)
 }
 
 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
@@ -113,7 +123,7 @@ var*
 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 @@ main(int argc, char *argv[])
 	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 @@ Xexit(void)
 			--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 @@ Xcase(void)
 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 @@ Xdol(void)
 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 @@ Xqdol(void)
 	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 @@ Xlocal(void)
 		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;
diff --git a/sys/src/cmd/rc/haventfork.c b/sys/src/cmd/rc/haventfork.c
index 52c16ac65..aa97f5c58 100644
--- a/sys/src/cmd/rc/haventfork.c
+++ b/sys/src/cmd/rc/haventfork.c
@@ -14,7 +14,7 @@ rcargv(char *s)
 	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'])
diff --git a/sys/src/cmd/rc/here.c b/sys/src/cmd/rc/here.c
index d10ed6aa8..5dbff855f 100644
--- a/sys/src/cmd/rc/here.c
+++ b/sys/src/cmd/rc/here.c
@@ -34,7 +34,7 @@ heredoc(tree *tag)
 	h->tag = tag;
 	hexnum(&tmp[9], getpid());
 	hexnum(&tmp[14], ser++);
-	h->name = strdup(tmp);
+	h->name = estrdup(tmp);
 	return token(tmp, WORD);
 }
 /*
diff --git a/sys/src/cmd/rc/rc.h b/sys/src/cmd/rc/rc.h
index 2e1d9ae59..eec0e068f 100644
--- a/sys/src/cmd/rc/rc.h
+++ b/sys/src/cmd/rc/rc.h
@@ -103,6 +103,7 @@ void *Realloc(void *, ulong);
 void *emalloc(long);
 void *erealloc(void *, long);
 void efree(void *);
+char *estrdup(char*);
 
 #define	NOFILE	128		/* should come from <param.h> */
 
diff --git a/sys/src/cmd/rc/simple.c b/sys/src/cmd/rc/simple.c
index d4b897cd1..fb50ce31d 100644
--- a/sys/src/cmd/rc/simple.c
+++ b/sys/src/cmd/rc/simple.c
@@ -131,7 +131,7 @@ execfunc(var *func)
 	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 @@ execcd(void)
 				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,14 +355,14 @@ execdot(void)
 		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){
 		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 @@ execwhatis(void){	/* mildly wrong -- should fork before writing */
 						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);
diff --git a/sys/src/cmd/rc/subr.c b/sys/src/cmd/rc/subr.c
index b0fc80005..ee5550a8d 100644
--- a/sys/src/cmd/rc/subr.c
+++ b/sys/src/cmd/rc/subr.c
@@ -30,6 +30,19 @@ efree(void *p)
 		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
diff --git a/sys/src/cmd/rc/trap.c b/sys/src/cmd/rc/trap.c
index a572cac37..fa7e35832 100644
--- a/sys/src/cmd/rc/trap.c
+++ b/sys/src/cmd/rc/trap.c
@@ -18,7 +18,7 @@ dotrap(void)
 		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;
diff --git a/sys/src/cmd/rc/tree.c b/sys/src/cmd/rc/tree.c
index a2cd1af69..f7d0b4cf4 100644
--- a/sys/src/cmd/rc/tree.c
+++ b/sys/src/cmd/rc/tree.c
@@ -111,7 +111,7 @@ simplemung(tree *t)
 	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
diff --git a/sys/src/cmd/rc/unix.c b/sys/src/cmd/rc/unix.c
index 1a5a4a8c0..31c6e2145 100644
--- a/sys/src/cmd/rc/unix.c
+++ b/sys/src/cmd/rc/unix.c
@@ -256,7 +256,7 @@ register struct word *args, *path;
 		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:
diff --git a/sys/src/cmd/rc/var.c b/sys/src/cmd/rc/var.c
index a96af06d6..f6b8dbb09 100644
--- a/sys/src/cmd/rc/var.c
+++ b/sys/src/cmd/rc/var.c
@@ -63,7 +63,7 @@ gvlook(char *name)
 	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*