new way to handle "growing" vectors

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; ref<L->refSize; 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; ref<L->refSize; 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 <string.h>
 
 
-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;
 }