diff options
| -rw-r--r-- | ChangeLog | 7 | ||||
| -rw-r--r-- | Src/mem.c | 8 | ||||
| -rw-r--r-- | Src/parse.c | 50 | ||||
| -rw-r--r-- | Src/zsh.h | 4 |
4 files changed, 39 insertions, 30 deletions
diff --git a/ChangeLog b/ChangeLog index 72808221d..ced314428 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2001-03-07 Sven Wischnowsky <wischnow@zsh.org> + + * 13589: Src/mem.c, Src/parse.c, Src/zsh.h: two optimisations; use + a binary tree to avoid duplicate strings in ecstrcode(); keep a + pointer to newly allocated heaps to avoid having to search for a + heap with free space in most cases + 2001-03-07 Andrej Borsenkow <bor@zsh.org> * unposted: configure.in, aczsh.m4: support building with diff --git a/Src/mem.c b/Src/mem.c index 5c995c634..9f88dddaa 100644 --- a/Src/mem.c +++ b/Src/mem.c @@ -105,7 +105,8 @@ union mem_align { static Heap heaps; -/* first heap with free space, not always correct */ +/* a heap with free space, not always correct (it will be the last heap + * if that was newly allocated but it may also be another one) */ static Heap fheap; @@ -297,7 +298,8 @@ zhalloc(size_t size) /* find a heap with enough free space */ - for (h = (fheap ? fheap : heaps); h; h = h->next) { + for (h = ((fheap && HEAP_ARENA_SIZE >= (size + fheap->used)) ? fheap : heaps); + h; h = h->next) { if (HEAP_ARENA_SIZE >= (n = size + h->used)) { void *ret; @@ -364,7 +366,7 @@ zhalloc(size_t size) hp->next = h; else heaps = h; - fheap = NULL; + fheap = h; unqueue_signals(); return arena(h); diff --git a/Src/parse.c b/Src/parse.c index 5f0938546..cf3fe237a 100644 --- a/Src/parse.c +++ b/Src/parse.c @@ -211,9 +211,9 @@ struct heredocs *hdocs; * containing the characters. Longer strings are encoded as the offset * into the strs character array stored in the eprog struct shifted by * two and ored with the bit pattern 0x. - * The ecstr() function that adds the code for a string uses a simple - * list of strings already added so that long strings are encoded only - * once. + * The ecstrcode() function that adds the code for a string uses a simple + * binary tree of strings already added so that long strings are encoded + * only once. * * Note also that in the eprog struct the pattern, code, and string * arrays all point to the same memory block. @@ -320,19 +320,18 @@ ecstrcode(char *s) } return c; } else { - Eccstr p, q = NULL; + Eccstr p, *pp; + int cmp; - for (p = ecstrs; p; q = p, p = p->next) - if (p->nfunc == ecnfunc && !strcmp(s, p->str)) + for (pp = &ecstrs; (p = *pp); ) { + if (!(cmp = p->nfunc - ecnfunc) && !(cmp = strcmp(p->str, s))) return p->offs; - - p = (Eccstr) zhalloc(sizeof(*p)); - p->next = NULL; - if (q) - q->next = p; - else - ecstrs = p; + pp = (cmp < 0 ? &(p->left) : &(p->right)); + } + p = *pp = (Eccstr) zhalloc(sizeof(*p)); + p->left = p->right = 0; p->offs = ((ecsoffs - ecssub) << 2) | (t ? 1 : 0); + p->aoffs = ecsoffs; p->str = s; p->nfunc = ecnfunc; ecsoffs += l; @@ -341,12 +340,7 @@ ecstrcode(char *s) } } -static int -ecstr(char *s) -{ - return ecadd(ecstrcode(s)); -} - +#define ecstr(S) ecadd(ecstrcode(S)) #define par_save_list(C) \ do { \ @@ -379,12 +373,20 @@ init_parse(void) /* Build eprog. */ +static void +copy_ecstr(Eccstr s, char *p) +{ + while (s) { + memcpy(p + s->aoffs, s->str, strlen(s->str) + 1); + copy_ecstr(s->left, p); + s = s->right; + } +} + static Eprog bld_eprog(void) { Eprog ret; - Eccstr p; - char *q; int l; ecadd(WCB_END()); @@ -403,10 +405,8 @@ bld_eprog(void) for (l = 0; l < ecnpats; l++) ret->pats[l] = dummy_patprog1; memcpy(ret->prog, ecbuf, ecused * sizeof(wordcode)); - for (p = ecstrs, q = ret->strs; p; p = p->next, q += l) { - l = strlen(p->str) + 1; - memcpy(q, p->str, l); - } + copy_ecstr(ecstrs, ret->strs); + zfree(ecbuf, eclen); ecbuf = NULL; diff --git a/Src/zsh.h b/Src/zsh.h index bfc9052b6..baafdb0e6 100644 --- a/Src/zsh.h +++ b/Src/zsh.h @@ -522,9 +522,9 @@ struct estate { typedef struct eccstr *Eccstr; struct eccstr { - Eccstr next; + Eccstr left, right; char *str; - wordcode offs; + wordcode offs, aoffs; int nfunc; }; |