From 26d1e21c89a481c2368ba934da8e192a164d8f99 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Thu, 25 Feb 1999 12:16:26 -0300 Subject: new way to handle "growing" vectors --- lgc.c | 20 ++++++++------------ lmem.c | 47 +++++++++++++++++++++++++---------------------- lmem.h | 8 ++++---- lparser.c | 31 +++++++++---------------------- ltm.c | 11 +++++------ 5 files changed, 51 insertions(+), 66 deletions(-) diff --git a/lgc.c b/lgc.c index ba75ef26..dca1bb98 100644 --- a/lgc.c +++ b/lgc.c @@ -1,5 +1,5 @@ /* -** $Id: lgc.c,v 1.19 1998/07/12 16:10:38 roberto Exp roberto $ +** $Id: lgc.c,v 1.20 1999/01/22 18:08:03 roberto Exp roberto $ ** Garbage Collector ** See Copyright Notice in lua.h */ @@ -29,23 +29,19 @@ static int markobject (TObject *o); */ -int luaC_ref (TObject *o, int lock) -{ +int luaC_ref (TObject *o, int lock) { int ref; if (ttype(o) == LUA_T_NIL) ref = -1; /* special ref for nil */ else { for (ref=0; refrefSize; ref++) if (L->refArray[ref].status == FREE) - goto found; - /* no more empty spaces */ { - int oldSize = L->refSize; - L->refSize = luaM_growvector(&L->refArray, L->refSize, struct ref, - refEM, MAX_INT); - for (ref=oldSize; refrefSize; ref++) - L->refArray[ref].status = FREE; - ref = oldSize; - } found: + break; + if (ref == L->refSize) { /* no more empty spaces? */ + L->refArray = luaM_growvector(L->refArray, L->refSize, 1, struct ref, + refEM, MAX_INT); + L->refSize++; + } L->refArray[ref].o = *o; L->refArray[ref].status = lock ? LOCK : HOLD; } diff --git a/lmem.c b/lmem.c index a1379f24..b4947b6c 100644 --- a/lmem.c +++ b/lmem.c @@ -1,5 +1,5 @@ /* -** $Id: lmem.c,v 1.9 1999/01/22 18:08:57 roberto Exp roberto $ +** $Id: lmem.c,v 1.10 1999/02/24 17:55:51 roberto Exp roberto $ ** Interface to Memory Manager ** See Copyright Notice in lua.h */ @@ -23,21 +23,36 @@ #endif +#define MINSIZE 16 /* minimum size for "growing" vectors */ -#ifndef DEBUG -int luaM_growaux (void **block, unsigned long nelems, int size, +static unsigned long power2 (unsigned long n) { + unsigned long p = MINSIZE; + while (p<=n) p<<=1; + return p; +} + + +void *luaM_growaux (void *block, unsigned long nelems, int inc, int size, char *errormsg, unsigned long limit) { - if (nelems >= limit) - lua_error(errormsg); - nelems = (nelems == 0) ? 32 : nelems*2; - if (nelems > limit) - nelems = limit; - *block = luaM_realloc(*block, nelems*size); - return (int)nelems; + unsigned long newn = nelems+inc; + if ((newn ^ nelems) > nelems) { /* cross a power of 2 boundary? */ + if (newn >= limit) + lua_error(errormsg); + newn = power2(newn); + if (newn > limit) + newn = limit; + return luaM_realloc(block, newn*size); + } + else { + LUA_ASSERT(power2(nelems) == power2(newn), "bad arithmetic"); + return block; + } } +#ifndef DEBUG + /* ** generic allocation routine. */ @@ -63,18 +78,6 @@ void *luaM_realloc (void *block, unsigned long size) { #include -int luaM_growaux (void **block, unsigned long nelems, int size, - char *errormsg, unsigned long limit) { - if (nelems >= limit) - lua_error(errormsg); - nelems = nelems+1; - if (nelems > limit) - nelems = limit; - *block = luaM_realloc(*block, nelems*size); - return (int)nelems; -} - - #define HEADER (sizeof(double)) #define MARK 55 diff --git a/lmem.h b/lmem.h index 4741b7f6..c8e015d6 100644 --- a/lmem.h +++ b/lmem.h @@ -1,5 +1,5 @@ /* -** $Id: lmem.h,v 1.5 1997/12/17 20:48:58 roberto Exp roberto $ +** $Id: lmem.h,v 1.6 1998/12/15 14:59:43 roberto Exp roberto $ ** Interface to Memory Manager ** See Copyright Notice in lua.h */ @@ -18,15 +18,15 @@ #define memEM "not enough memory" void *luaM_realloc (void *oldblock, unsigned long size); -int luaM_growaux (void **block, unsigned long nelems, int size, +void *luaM_growaux (void *block, unsigned long nelems, int inc, int size, char *errormsg, unsigned long limit); #define luaM_free(b) luaM_realloc((b), 0) #define luaM_malloc(t) luaM_realloc(NULL, (t)) #define luaM_new(t) ((t *)luaM_malloc(sizeof(t))) #define luaM_newvector(n,t) ((t *)luaM_malloc((n)*sizeof(t))) -#define luaM_growvector(old,n,t,e,l) \ - (luaM_growaux((void**)old,n,sizeof(t),e,l)) +#define luaM_growvector(old,nelems,inc,t,e,l) \ + ((t *)luaM_growaux(old,nelems,inc,sizeof(t),e,l)) #define luaM_reallocvector(v,n,t) ((t *)luaM_realloc(v,(n)*sizeof(t))) diff --git a/lparser.c b/lparser.c index 03e05102..4978f8e3 100644 --- a/lparser.c +++ b/lparser.c @@ -1,5 +1,5 @@ /* -** $Id: lparser.c,v 1.21 1999/02/24 15:37:19 roberto Exp roberto $ +** $Id: lparser.c,v 1.22 1999/02/24 17:55:51 roberto Exp roberto $ ** LL(1) Parser and code generator for Lua ** See Copyright Notice in lua.h */ @@ -89,10 +89,7 @@ typedef struct FuncState { int maxstacksize; /* maximum number of values on activation register */ int nlocalvar; /* number of active local variables */ int nupvalues; /* number of upvalues */ - int nvars; /* number of entries in f->locvars */ - int maxcode; /* size of f->code */ - int maxvars; /* size of f->locvars (-1 if no debug information) */ - int maxconsts; /* size of f->consts */ + int nvars; /* number of entries in f->locvars (-1 if no debug information) */ int lastsetline; /* line where last SETLINE was issued */ vardesc upvalues[MAXUPVALUES]; /* upvalues */ TaggedString *localvar[MAXLOCALS]; /* store local variable names */ @@ -134,9 +131,7 @@ static void var_or_func_tail (LexState *ls, vardesc *v); static void check_pc (FuncState *fs, int n) { - if (fs->pc+n > fs->maxcode) - fs->maxcode = luaM_growvector(&fs->f->code, fs->maxcode+n, - Byte, codeEM, MAX_INT); + fs->f->code = luaM_growvector(fs->f->code, fs->pc, n, Byte, codeEM, MAX_INT); } @@ -221,9 +216,8 @@ static void code_constant (LexState *ls, int c) { static int next_constant (FuncState *fs) { TProtoFunc *f = fs->f; - if (f->nconsts >= fs->maxconsts) - fs->maxconsts = luaM_growvector(&f->consts, fs->maxconsts, TObject, - constantEM, MAX_ARG); + f->consts = luaM_growvector(f->consts, f->nconsts, 1, TObject, + constantEM, MAX_ARG); return f->nconsts++; } @@ -293,11 +287,9 @@ static void flush_list (LexState *ls, int m, int n) { static void luaI_registerlocalvar (FuncState *fs, TaggedString *varname, int line) { - if (fs->maxvars != -1) { /* debug information? */ + if (fs->nvars != -1) { /* debug information? */ TProtoFunc *f = fs->f; - if (fs->nvars >= fs->maxvars) - fs->maxvars = luaM_growvector(&f->locvars, fs->maxvars, - LocVar, "", MAX_INT); + f->locvars = luaM_growvector(f->locvars, fs->nvars, 1, LocVar, "", MAX_INT); f->locvars[fs->nvars].varname = varname; f->locvars[fs->nvars].line = line; fs->nvars++; @@ -555,13 +547,8 @@ static void init_state (LexState *ls, FuncState *fs, TaggedString *filename) { fs->f = f; f->fileName = filename; fs->pc = 0; - fs->maxcode = 0; f->code = NULL; - fs->maxconsts = 0; - if (L->debug) - fs->nvars = fs->maxvars = 0; - else - fs->maxvars = -1; /* flag no debug information */ + fs->nvars = (L->debug) ? 0 : -1; /* flag no debug information? */ code_byte(fs, 0); /* to be filled with maxstacksize */ code_byte(fs, 0); /* to be filled with arg information */ /* push function (to avoid GC) */ @@ -577,7 +564,7 @@ static void close_func (LexState *ls) { f->code[0] = (Byte)fs->maxstacksize; f->code = luaM_reallocvector(f->code, fs->pc, Byte); f->consts = luaM_reallocvector(f->consts, f->nconsts, TObject); - if (fs->maxvars != -1) { /* debug information? */ + if (fs->nvars != -1) { /* debug information? */ luaI_registerlocalvar(fs, NULL, -1); /* flag end of vector */ f->locvars = luaM_reallocvector(f->locvars, fs->nvars, LocVar); } diff --git a/ltm.c b/ltm.c index bc9d0faa..78620286 100644 --- a/ltm.c +++ b/ltm.c @@ -1,5 +1,5 @@ /* -** $Id: ltm.c,v 1.20 1999/01/15 13:11:57 roberto Exp roberto $ +** $Id: ltm.c,v 1.21 1999/02/04 18:59:31 roberto Exp roberto $ ** Tag methods ** See Copyright Notice in lua.h */ @@ -58,9 +58,9 @@ static void init_entry (int tag) { void luaT_init (void) { int t; - L->IMtable_size = NUM_TAGS*2; L->last_tag = -(NUM_TAGS-1); - L->IMtable = luaM_newvector(L->IMtable_size, struct IM); + L->IMtable = luaM_growvector(L->IMtable, 0, NUM_TAGS, + struct IM, memEM, MAX_INT); for (t=L->last_tag; t<=0; t++) init_entry(t); } @@ -68,9 +68,8 @@ void luaT_init (void) { int lua_newtag (void) { --L->last_tag; - if ((-L->last_tag) >= L->IMtable_size) - L->IMtable_size = luaM_growvector(&L->IMtable, L->IMtable_size, - struct IM, memEM, MAX_INT); + L->IMtable = luaM_growvector(L->IMtable, -(L->last_tag), 1, + struct IM, memEM, MAX_INT); init_entry(L->last_tag); return L->last_tag; } -- cgit v1.2.3-55-g6feb