diff options
author | jilles <jilles@FreeBSD.org> | 2015-10-11 21:33:00 +0000 |
---|---|---|
committer | jilles <jilles@FreeBSD.org> | 2015-10-11 21:33:00 +0000 |
commit | 5edc3be36a94a4e6d00b23f4a78f7a34f298354a (patch) | |
tree | de27811dc69dd87b6197cb836792e2f49ede3869 /bin/sh | |
parent | 4b946e6d78df59fc08a27d0a0830f287a59ff27f (diff) | |
download | FreeBSD-src-5edc3be36a94a4e6d00b23f4a78f7a34f298354a.zip FreeBSD-src-5edc3be36a94a4e6d00b23f4a78f7a34f298354a.tar.gz |
sh: Make struct arglist an array instead of a linked list.
This simplifies the code (e.g. allowing use of qsort(3) instead of a
hand-rolled mergesort) and should have better cache properties.
The waste of unused args arrays after resizes is approximately the same as
the savings from getting rid of the next pointers.
At the same time, remove a piece of global state and move some duplicated
code into a function.
Diffstat (limited to 'bin/sh')
-rw-r--r-- | bin/sh/eval.c | 89 | ||||
-rw-r--r-- | bin/sh/eval.h | 2 | ||||
-rw-r--r-- | bin/sh/expand.c | 215 | ||||
-rw-r--r-- | bin/sh/expand.h | 13 | ||||
-rw-r--r-- | bin/sh/var.c | 28 | ||||
-rw-r--r-- | bin/sh/var.h | 4 |
6 files changed, 136 insertions, 215 deletions
diff --git a/bin/sh/eval.c b/bin/sh/eval.c index 51206d9..dfbbc04 100644 --- a/bin/sh/eval.c +++ b/bin/sh/eval.c @@ -82,7 +82,7 @@ static int builtin_flags; /* evalcommand flags for builtins */ char *commandname; -struct strlist *cmdenviron; +struct arglist *cmdenviron; int exitstatus; /* exit status of last command */ int oexitstatus; /* saved exit status */ @@ -352,20 +352,19 @@ evalfor(union node *n, int flags) { struct arglist arglist; union node *argp; - struct strlist *sp; + int i; int status; - arglist.lastp = &arglist.list; + emptyarglist(&arglist); for (argp = n->nfor.args ; argp ; argp = argp->narg.next) { oexitstatus = exitstatus; expandarg(argp, &arglist, EXP_FULL | EXP_TILDE); } - *arglist.lastp = NULL; loopnest++; status = 0; - for (sp = arglist.list ; sp ; sp = sp->next) { - setvar(n->nfor.var, sp->text, 0); + for (i = 0; i < arglist.count; i++) { + setvar(n->nfor.var, arglist.args[i], 0); evaltree(n->nfor.body, flags); status = exitstatus; if (evalskip) { @@ -396,12 +395,12 @@ evalcase(union node *n) union node *patp; struct arglist arglist; - arglist.lastp = &arglist.list; + emptyarglist(&arglist); oexitstatus = exitstatus; expandarg(n->ncase.expr, &arglist, EXP_TILDE); for (cp = n->ncase.cases ; cp ; cp = cp->nclist.next) { for (patp = cp->nclist.pattern ; patp ; patp = patp->narg.next) { - if (casematch(patp, arglist.list->text)) { + if (casematch(patp, arglist.args[0])) { while (cp->nclist.next && cp->type == NCLISTFALLTHRU && cp->nclist.body == NULL) @@ -508,7 +507,7 @@ exphere(union node *redir, struct arglist *fn) else { handler = &jmploc; expandarg(redir->nhere.doc, fn, 0); - redir->nhere.expdoc = fn->list->text; + redir->nhere.expdoc = fn->args[0]; INTOFF; } handler = savehandler; @@ -532,7 +531,7 @@ expredir(union node *n) for (redir = n ; redir ; redir = redir->nfile.next) { struct arglist fn; - fn.lastp = &fn.list; + emptyarglist(&fn); switch (redir->type) { case NFROM: case NTO: @@ -540,13 +539,13 @@ expredir(union node *n) case NAPPEND: case NCLOBBER: expandarg(redir->nfile.fname, &fn, EXP_TILDE); - redir->nfile.expfname = fn.list->text; + redir->nfile.expfname = fn.args[0]; break; case NFROMFD: case NTOFD: if (redir->ndup.vname) { expandarg(redir->ndup.vname, &fn, EXP_TILDE); - fixredir(redir, fn.list->text, 1); + fixredir(redir, fn.args[0], 1); } break; case NXHERE: @@ -753,28 +752,30 @@ isdeclarationcmd(struct narg *arg) static void xtracecommand(struct arglist *varlist, struct arglist *arglist) { - struct strlist *sp; char sep = 0; - const char *p, *ps4; + const char *text, *p, *ps4; + int i; ps4 = expandstr(ps4val()); out2str(ps4 != NULL ? ps4 : ps4val()); - for (sp = varlist->list ; sp ; sp = sp->next) { + for (i = 0; i < varlist->count; i++) { + text = varlist->args[i]; if (sep != 0) out2c(' '); - p = strchr(sp->text, '='); + p = strchr(text, '='); if (p != NULL) { p++; - outbin(sp->text, p - sp->text, out2); + outbin(text, p - text, out2); out2qstr(p); } else - out2qstr(sp->text); + out2qstr(text); sep = ' '; } - for (sp = arglist->list ; sp ; sp = sp->next) { + for (i = 0; i < arglist->count; i++) { + text = arglist->args[i]; if (sep != 0) out2c(' '); - out2qstr(sp->text); + out2qstr(text); sep = ' '; } out2c('\n'); @@ -822,7 +823,6 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) int argc; char **envp; int varflag; - struct strlist *sp; int mode; int pip[2]; struct cmdentry cmdentry; @@ -838,11 +838,12 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) int realstatus; int do_clearcmdentry; const char *path = pathval(); + int i; /* First expand the arguments. */ TRACE(("evalcommand(%p, %d) called\n", (void *)cmd, flags)); - arglist.lastp = &arglist.list; - varlist.lastp = &varlist.list; + emptyarglist(&arglist); + emptyarglist(&varlist); varflag = 1; jp = NULL; do_clearcmdentry = 0; @@ -857,25 +858,17 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) varflag = isdeclarationcmd(&argp->narg) ? 2 : 0; expandarg(argp, &arglist, EXP_FULL | EXP_TILDE); } - *arglist.lastp = NULL; - *varlist.lastp = NULL; expredir(cmd->ncmd.redirect); - argc = 0; - for (sp = arglist.list ; sp ; sp = sp->next) - argc++; + argc = arglist.count; /* Add one slot at the beginning for tryexec(). */ argv = stalloc(sizeof (char *) * (argc + 2)); argv++; - for (sp = arglist.list ; sp ; sp = sp->next) { - TRACE(("evalcommand arg: %s\n", sp->text)); - *argv++ = sp->text; - } - *argv = NULL; + memcpy(argv, arglist.args, sizeof(*argv) * argc); + argv[argc] = NULL; lastarg = NULL; if (iflag && funcnest == 0 && argc > 0) - lastarg = argv[-1]; - argv -= argc; + lastarg = argv[argc - 1]; /* Print the command if xflag is set. */ if (xflag) @@ -895,9 +888,9 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) * Modify the command lookup path, if a PATH= assignment * is present */ - for (sp = varlist.list ; sp ; sp = sp->next) - if (strncmp(sp->text, PATH, sizeof(PATH) - 1) == 0) { - path = sp->text + sizeof(PATH) - 1; + for (i = 0; i < varlist.count; i++) + if (strncmp(varlist.args[i], PATH, sizeof(PATH) - 1) == 0) { + path = varlist.args[i] + sizeof(PATH) - 1; /* * On `PATH=... command`, we need to make * sure that the command isn't using the @@ -999,7 +992,7 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) } if (cmdentry.cmdtype == CMDNORMAL && cmd->ncmd.redirect == NULL && - varlist.list == NULL && + varlist.count == 0 && (mode == FORK_FG || mode == FORK_NOJOB) && !disvforkset() && !iflag && !mflag) { vforkexecshell(jp, argv, environment(), path, @@ -1053,8 +1046,8 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) funcnest++; redirect(cmd->ncmd.redirect, REDIR_PUSH); INTON; - for (sp = varlist.list ; sp ; sp = sp->next) - mklocal(sp->text); + for (i = 0; i < varlist.count; i++) + mklocal(varlist.args[i]); exitstatus = oexitstatus; evaltree(getfuncnode(cmdentry.u.func), flags & (EV_TESTED | EV_EXIT)); @@ -1087,7 +1080,7 @@ evalcommand(union node *cmd, int flags, struct backcmd *backcmd) } savecmdname = commandname; savetopfile = getcurrentfile(); - cmdenviron = varlist.list; + cmdenviron = &varlist; e = -1; savehandler = handler; if (setjmp(jmploc.loc)) { @@ -1152,8 +1145,8 @@ cmddone: trputs("normal command: "); trargs(argv); #endif redirect(cmd->ncmd.redirect, 0); - for (sp = varlist.list ; sp ; sp = sp->next) - setvareq(sp->text, VEXPORT|VSTACK); + for (i = 0; i < varlist.count; i++) + setvareq(varlist.args[i], VEXPORT|VSTACK); envp = environment(); shellexec(argv, envp, path, cmdentry.u.index); /*NOTREACHED*/ @@ -1336,6 +1329,8 @@ truecmd(int argc __unused, char **argv __unused) int execcmd(int argc, char **argv) { + int i; + /* * Because we have historically not supported any options, * only treat "--" specially. @@ -1343,13 +1338,11 @@ execcmd(int argc, char **argv) if (argc > 1 && strcmp(argv[1], "--") == 0) argc--, argv++; if (argc > 1) { - struct strlist *sp; - iflag = 0; /* exit on error */ mflag = 0; optschanged(); - for (sp = cmdenviron; sp ; sp = sp->next) - setvareq(sp->text, VEXPORT|VSTACK); + for (i = 0; i < cmdenviron->count; i++) + setvareq(cmdenviron->args[i], VEXPORT|VSTACK); shellexec(argv + 1, environment(), pathval(), 0); } diff --git a/bin/sh/eval.h b/bin/sh/eval.h index d4092be..e781336 100644 --- a/bin/sh/eval.h +++ b/bin/sh/eval.h @@ -36,7 +36,7 @@ extern char *commandname; /* currently executing command */ extern int exitstatus; /* exit status of last command */ extern int oexitstatus; /* saved exit status */ -extern struct strlist *cmdenviron; /* environment for builtin command */ +extern struct arglist *cmdenviron; /* environment for builtin command */ struct backcmd { /* result of evalbackcmd */ diff --git a/bin/sh/expand.c b/bin/sh/expand.c index 88d80ea..567b8a4 100644 --- a/bin/sh/expand.c +++ b/bin/sh/expand.c @@ -96,7 +96,6 @@ static char *expdest; /* output of current string */ static struct nodelist *argbackq; /* list of back quote expressions */ static struct ifsregion ifsfirst; /* first struct in list of ifs regions */ static struct ifsregion *ifslastp; /* last struct in list */ -static struct arglist exparg; /* holds expanded arg list */ static char *argstr(char *, int); static char *exptilde(char *, int); @@ -110,15 +109,43 @@ static void varvalue(const char *, int, int, int); static void recordregion(int, int, int); static void removerecordregions(int); static void ifsbreakup(char *, struct arglist *); -static void expandmeta(struct strlist *); -static void expmeta(char *, char *); -static void addfname(char *); -static struct strlist *expsort(struct strlist *); -static struct strlist *msort(struct strlist *, int); +static void expandmeta(struct arglist *, struct arglist *); +static void expmeta(char *, char *, struct arglist *); +static int expsortcmp(const void *, const void *); static int patmatch(const char *, const char *, int); static char *cvtnum(int, char *); +static void appendarglist(struct arglist *, char *); static int collate_range_cmp(wchar_t, wchar_t); +void +emptyarglist(struct arglist *list) +{ + + list->args = list->smallarg; + list->count = 0; + list->capacity = sizeof(list->smallarg) / sizeof(list->smallarg[0]); +} + +static void +appendarglist(struct arglist *list, char *str) +{ + char **newargs; + int newcapacity; + + if (list->count >= list->capacity) { + newcapacity = list->capacity * 2; + if (newcapacity < 16) + newcapacity = 16; + if (newcapacity > INT_MAX / (int)sizeof(newargs[0])) + error("Too many entries in arglist"); + newargs = stalloc(newcapacity * sizeof(newargs[0])); + memcpy(newargs, list->args, list->count * sizeof(newargs[0])); + list->args = newargs; + list->capacity = newcapacity; + } + list->args[list->count++] = str; +} + static int collate_range_cmp(wchar_t c1, wchar_t c2) { @@ -157,7 +184,7 @@ stputs_quotes(const char *data, const char *syntax, char *p) void expandarg(union node *arg, struct arglist *arglist, int flag) { - struct strlist *sp; + struct arglist exparg; char *p; argbackq = arg->narg.backquote; @@ -171,18 +198,12 @@ expandarg(union node *arg, struct arglist *arglist, int flag) } STPUTC('\0', expdest); p = grabstackstr(expdest); - exparg.lastp = &exparg.list; + emptyarglist(&exparg); if (flag & EXP_FULL) { ifsbreakup(p, &exparg); - *exparg.lastp = NULL; - exparg.lastp = &exparg.list; - expandmeta(exparg.list); - } else { - sp = (struct strlist *)stalloc(sizeof (struct strlist)); - sp->text = p; - *exparg.lastp = sp; - exparg.lastp = &sp->next; - } + expandmeta(&exparg, arglist); + } else + appendarglist(arglist, p); while (ifsfirst.next != NULL) { struct ifsregion *ifsp; INTOFF; @@ -191,11 +212,6 @@ expandarg(union node *arg, struct arglist *arglist, int flag) ifsfirst.next = ifsp; INTON; } - *exparg.lastp = NULL; - if (exparg.list) { - *arglist->lastp = exparg.list; - arglist->lastp = exparg.lastp; - } } @@ -984,7 +1000,6 @@ static void ifsbreakup(char *string, struct arglist *arglist) { struct ifsregion *ifsp; - struct strlist *sp; char *start; char *p; char *q; @@ -996,10 +1011,7 @@ ifsbreakup(char *string, struct arglist *arglist) if (ifslastp == NULL) { /* Return entire argument, IFS doesn't apply to any of it */ - sp = (struct strlist *)stalloc(sizeof *sp); - sp->text = start; - *arglist->lastp = sp; - arglist->lastp = &sp->next; + appendarglist(arglist, start); return; } @@ -1038,10 +1050,7 @@ ifsbreakup(char *string, struct arglist *arglist) /* Save this argument... */ *q = '\0'; - sp = (struct strlist *)stalloc(sizeof *sp); - sp->text = start; - *arglist->lastp = sp; - arglist->lastp = &sp->next; + appendarglist(arglist, start); p++; if (ifsspc != NULL) { @@ -1071,12 +1080,8 @@ ifsbreakup(char *string, struct arglist *arglist) * Some recent clarification of the Posix spec say that it * should only generate one.... */ - if (had_param_ch || *start != 0) { - sp = (struct strlist *)stalloc(sizeof *sp); - sp->text = start; - *arglist->lastp = sp; - arglist->lastp = &sp->next; - } + if (had_param_ch || *start != 0) + appendarglist(arglist, start); } @@ -1086,45 +1091,42 @@ static char expdir[PATH_MAX]; /* * Perform pathname generation and remove control characters. * At this point, the only control characters should be CTLESC and CTLQUOTEMARK. - * The results are stored in the list exparg. + * The results are stored in the list dstlist. */ static void -expandmeta(struct strlist *str) +expandmeta(struct arglist *srclist, struct arglist *dstlist) { char *p; - struct strlist **savelastp; - struct strlist *sp; + int firstmatch; + int i; char c; - while (str) { - savelastp = exparg.lastp; + for (i = 0; i < srclist->count; i++) { + firstmatch = dstlist->count; if (!fflag) { - p = str->text; + p = srclist->args[i]; for (; (c = *p) != '\0'; p++) { /* fast check for meta chars */ if (c == '*' || c == '?' || c == '[') { INTOFF; - expmeta(expdir, str->text); + expmeta(expdir, srclist->args[i], + dstlist); INTON; break; } } } - if (exparg.lastp == savelastp) { + if (dstlist->count == firstmatch) { /* * no matches */ - *exparg.lastp = str; - rmescapes(str->text); - exparg.lastp = &str->next; + rmescapes(srclist->args[i]); + appendarglist(dstlist, srclist->args[i]); } else { - *exparg.lastp = NULL; - *savelastp = sp = expsort(*savelastp); - while (sp->next != NULL) - sp = sp->next; - exparg.lastp = &sp->next; + qsort(&dstlist->args[firstmatch], + dstlist->count - firstmatch, + sizeof(dstlist->args[0]), expsortcmp); } - str = str->next; } } @@ -1134,7 +1136,7 @@ expandmeta(struct strlist *str) */ static void -expmeta(char *enddir, char *name) +expmeta(char *enddir, char *name, struct arglist *arglist) { const char *p; const char *q; @@ -1199,7 +1201,7 @@ expmeta(char *enddir, char *name) return; } if (metaflag == 0 || lstat(expdir, &statb) >= 0) - addfname(expdir); + appendarglist(arglist, stsavestr(expdir)); return; } endname = name + (p - name); @@ -1251,7 +1253,7 @@ expmeta(char *enddir, char *name) continue; memcpy(enddir, dp->d_name, namlen + 1); if (atend) - addfname(expdir); + appendarglist(arglist, stsavestr(expdir)); else { if (dp->d_type != DT_UNKNOWN && dp->d_type != DT_DIR && @@ -1261,7 +1263,7 @@ expmeta(char *enddir, char *name) continue; enddir[namlen] = '/'; enddir[namlen + 1] = '\0'; - expmeta(enddir + namlen + 1, endname); + expmeta(enddir + namlen + 1, endname, arglist); } } } @@ -1271,81 +1273,13 @@ expmeta(char *enddir, char *name) } -/* - * Add a file name to the list. - */ - -static void -addfname(char *name) -{ - char *p; - struct strlist *sp; - - p = stsavestr(name); - sp = (struct strlist *)stalloc(sizeof *sp); - sp->text = p; - *exparg.lastp = sp; - exparg.lastp = &sp->next; -} - - -/* - * Sort the results of file name expansion. It calculates the number of - * strings to sort and then calls msort (short for merge sort) to do the - * work. - */ - -static struct strlist * -expsort(struct strlist *str) +static int +expsortcmp(const void *p1, const void *p2) { - int len; - struct strlist *sp; - - len = 0; - for (sp = str ; sp ; sp = sp->next) - len++; - return msort(str, len); -} + const char *s1 = *(const char * const *)p1; + const char *s2 = *(const char * const *)p2; - -static struct strlist * -msort(struct strlist *list, int len) -{ - struct strlist *p, *q = NULL; - struct strlist **lpp; - int half; - int n; - - if (len <= 1) - return list; - half = len >> 1; - p = list; - for (n = half ; --n >= 0 ; ) { - q = p; - p = p->next; - } - q->next = NULL; /* terminate first half of list */ - q = msort(list, half); /* sort first half of list */ - p = msort(p, len - half); /* sort second half */ - lpp = &list; - for (;;) { - if (strcmp(p->text, q->text) < 0) { - *lpp = p; - lpp = &p->next; - if ((p = *lpp) == NULL) { - *lpp = q; - break; - } - } else { - *lpp = q; - lpp = &q->next; - if ((q = *lpp) == NULL) { - *lpp = p; - break; - } - } - } - return list; + return (strcmp(s1, s2)); } @@ -1666,11 +1600,11 @@ freebsd_wordexpcmd(int argc __unused, char **argv __unused) { struct arglist arglist; union node *args, *n; - struct strlist *sp; - size_t count, len; + size_t len; int ch; int protected = 0; int fd = -1; + int i; while ((ch = nextopt("f:p")) != '\0') { switch (ch) { @@ -1699,14 +1633,13 @@ freebsd_wordexpcmd(int argc __unused, char **argv __unused) } } outcslow(' ', out1); - arglist.lastp = &arglist.list; + emptyarglist(&arglist); for (n = args; n != NULL; n = n->narg.next) expandarg(n, &arglist, EXP_FULL | EXP_TILDE); - *arglist.lastp = NULL; - for (sp = arglist.list, count = len = 0; sp; sp = sp->next) - count++, len += strlen(sp->text); - out1fmt("%016zx %016zx", count, len); - for (sp = arglist.list; sp; sp = sp->next) - outbin(sp->text, strlen(sp->text) + 1, out1); + for (i = 0, len = 0; i < arglist.count; i++) + len += strlen(arglist.args[i]); + out1fmt("%016x %016zx", arglist.count, len); + for (i = 0; i < arglist.count; i++) + outbin(arglist.args[i], strlen(arglist.args[i]) + 1, out1); return (0); } diff --git a/bin/sh/expand.h b/bin/sh/expand.h index 93c80f3..c377156 100644 --- a/bin/sh/expand.h +++ b/bin/sh/expand.h @@ -33,15 +33,11 @@ * $FreeBSD$ */ -struct strlist { - struct strlist *next; - char *text; -}; - - struct arglist { - struct strlist *list; - struct strlist **lastp; + char **args; + int count; + int capacity; + char *smallarg[1]; }; /* @@ -55,6 +51,7 @@ struct arglist { #define EXP_LIT_QUOTED 0x40 /* for EXP_SPLIT_LIT, start off quoted */ +void emptyarglist(struct arglist *); union node; void expandarg(union node *, struct arglist *, int); void rmescapes(char *); diff --git a/bin/sh/var.c b/bin/sh/var.c index f60dea1..cfba0ba 100644 --- a/bin/sh/var.c +++ b/bin/sh/var.c @@ -403,14 +403,13 @@ setvareq_const(const char *s, int flags) */ void -listsetvar(struct strlist *list, int flags) +listsetvar(struct arglist *list, int flags) { - struct strlist *lp; + int i; INTOFF; - for (lp = list ; lp ; lp = lp->next) { - setvareq(savestr(lp->text), flags); - } + for (i = 0; i < list->count; i++) + setvareq(savestr(list->args[i]), flags); INTON; } @@ -442,14 +441,14 @@ lookupvar(const char *name) char * bltinlookup(const char *name, int doall) { - struct strlist *sp; struct var *v; char *result; + int i; result = NULL; - for (sp = cmdenviron ; sp ; sp = sp->next) { - if (varequal(sp->text, name)) - result = strchr(sp->text, '=') + 1; + if (cmdenviron) for (i = 0; i < cmdenviron->count; i++) { + if (varequal(cmdenviron->args[i], name)) + result = strchr(cmdenviron->args[i], '=') + 1; } if (result != NULL) return result; @@ -468,13 +467,12 @@ bltinlookup(const char *name, int doall) void bltinsetlocale(void) { - struct strlist *lp; int act = 0; char *loc, *locdef; int i; - for (lp = cmdenviron ; lp ; lp = lp->next) { - if (localevar(lp->text)) { + if (cmdenviron) for (i = 0; i < cmdenviron->count; i++) { + if (localevar(cmdenviron->args[i])) { act = 1; break; } @@ -507,11 +505,11 @@ bltinsetlocale(void) void bltinunsetlocale(void) { - struct strlist *lp; + int i; INTOFF; - for (lp = cmdenviron ; lp ; lp = lp->next) { - if (localevar(lp->text)) { + if (cmdenviron) for (i = 0; i < cmdenviron->count; i++) { + if (localevar(cmdenviron->args[i])) { setlocale(LC_ALL, ""); updatecharset(); return; diff --git a/bin/sh/var.h b/bin/sh/var.h index 6e831ae..ede13cf 100644 --- a/bin/sh/var.h +++ b/bin/sh/var.h @@ -114,8 +114,8 @@ extern int initial_localeisutf8; void initvar(void); void setvar(const char *, const char *, int); void setvareq(char *, int); -struct strlist; -void listsetvar(struct strlist *, int); +struct arglist; +void listsetvar(struct arglist *, int); char *lookupvar(const char *); char *bltinlookup(const char *, int); void bltinsetlocale(void); |