Implementacao da nova estrategia para armazenar os arrays

em lista encadeada.

6 files changed, 175 insertions, 122 deletions

diff --git a/hash.c b/hash.c
index 1704acfe..549338a1 100644
--- a/hash.c
+++ b/hash.c
@@ -4,7 +4,7 @@
 ** Luiz Henrique de Figueiredo - 17 Aug 90
 */
 
-char *rcs_hash="$Id: hash.c,v 1.1 1993/12/17 18:41:19 celes Exp celes $";
+char *rcs_hash="$Id: hash.c,v 1.2 1994/03/28 15:14:02 celes Exp celes $";
 
 #include <string.h>
 #include <stdlib.h>
@@ -26,10 +26,23 @@ char *rcs_hash="$Id: hash.c,v 1.1 1993/12/17 18:41:19 celes Exp celes $";
 #define nhash(t)        ((t)->nhash)
 #define nodelist(t)     ((t)->list)
 #define list(t,i)       ((t)->list[i])
+#define markarray(t)    ((t)->mark)
 #define ref_tag(n)      (tag(&(n)->ref))
 #define ref_nvalue(n)   (nvalue(&(n)->ref))
 #define ref_svalue(n)   (svalue(&(n)->ref))
 
+#ifndef ARRAYBLOCK
+#define ARRAYBLOCK 50
+#endif
+
+typedef struct ArrayList
+{
+ Hash *array;
+ struct ArrayList *next;
+} ArrayList;
+
+static ArrayList *listhead = NULL;
+
 static int head (Hash *t, Object *ref)          /* hash function */
 {
  if (tag(ref) == T_NUMBER) return (((int)nvalue(ref))%nhash(t));
@@ -91,7 +104,7 @@ static void freelist (Node *n)
 /*
 ** Create a new hash. Return the hash pointer or NULL on error.
 */
-Hash *lua_hashcreate (unsigned int nhash)
+static Hash *hashcreate (unsigned int nhash)
 {
  Hash *t = new (Hash);
  if (t == NULL)
@@ -113,7 +126,7 @@ Hash *lua_hashcreate (unsigned int nhash)
 /*
 ** Delete a hash
 */
-void lua_hashdelete (Hash *h)
+static void hashdelete (Hash *h)
 {
  int i;
  for (i=0; i<nhash(h); i++)
@@ -122,6 +135,86 @@ void lua_hashdelete (Hash *h)
  free(h);
 }
 
+
+/*
+** Mark a hash and check its elements 
+*/
+void lua_hashmark (Hash *h)
+{
+ if (markarray(h) == 0)
+ {
+  int i;
+  markarray(h) = 1;
+  for (i=0; i<nhash(h); i++)
+  {
+   Node *n;
+   for (n = list(h,i); n != NULL; n = n->next)
+   {
+    lua_markobject(&n->ref);
+    lua_markobject(&n->val);
+   }
+  }
+ } 
+}
+ 
+/*
+** Garbage collection to arrays
+** Delete all unmarked arrays.
+*/
+void lua_hashcollector (void)
+{
+ ArrayList *curr = listhead, *prev = NULL;
+ while (curr != NULL)
+ {
+  ArrayList *next = curr->next;
+  if (markarray(curr->array) != 1)
+  {
+   if (prev == NULL) listhead = next;
+   else              prev->next = next;
+   hashdelete(curr->array);
+   free(curr);
+  }
+  else
+  {
+   markarray(curr->array) = 0;
+   prev = curr;
+  }
+  curr = next;
+ }
+}
+
+
+/*
+** Create a new array
+** This function insert the new array at array list. It also
+** execute garbage collection if the number of array created
+** exceed a pre-defined range.
+*/
+Hash *lua_createarray (int nhash)
+{
+ ArrayList *new = new(ArrayList);
+ if (new == NULL)
+ {
+  lua_error ("not enough memory");
+  return NULL;
+ }
+ new->array = hashcreate(nhash);
+ if (new->array == NULL)
+ {
+  lua_error ("not enough memory");
+  return NULL;
+ }
+
+ if (lua_nentity == lua_block)
+  lua_pack(); 
+
+ lua_nentity++;
+ new->next = listhead;
+ listhead = new;
+ return new->array;
+}
+
+
 /*
 ** If the hash node is present, return its pointer, otherwise create a new
 ** node for the given reference and also return its pointer.
@@ -151,26 +244,6 @@ Object *lua_hashdefine (Hash *t, Object *ref)
  return (&n->val);
 }
 
-/*
-** Mark a hash and check its elements 
-*/
-void lua_hashmark (Hash *h)
-{
- int i;
- 
- markarray(h) = 1;
- 
- for (i=0; i<nhash(h); i++)
- {
-  Node *n;
-  for (n = list(h,i); n != NULL; n = n->next)
-  {
-   lua_markobject (&n->ref);
-   lua_markobject (&n->val);
-  }
- }
-}
-
 
 /*
 ** Internal function to manipulate arrays. 
@@ -178,7 +251,6 @@ void lua_hashmark (Hash *h)
 ** in the hash.
 ** This function pushs the element value and its reference to the stack.
 */
-#include "lua.h"
 static void firstnode (Hash *a, int h)
 {
  if (h < nhash(a))
diff --git a/hash.h b/hash.h
index 0a66a492..cea34df1 100644
--- a/hash.h
+++ b/hash.h
@@ -2,7 +2,7 @@
 ** hash.h
 ** hash manager for lua
 ** Luiz Henrique de Figueiredo - 17 Aug 90
-** $Id: $
+** $Id: hash.h,v 1.1 1993/12/17 18:41:19 celes Exp celes $
 */
 
 #ifndef hash_h
@@ -22,13 +22,11 @@ typedef struct Hash
  Node         **list;
 } Hash;
 
-#define markarray(t)            ((t)->mark)
 
-Hash    *lua_hashcreate (unsigned int nhash);
-void     lua_hashdelete (Hash *h);
+Hash    *lua_createarray (int nhash);
+void     lua_hashmark (Hash *h);
+void     lua_hashcollector (void);
 Object  *lua_hashdefine (Hash *t, Object *ref);
-void     lua_hashmark   (Hash *h);
-
 void     lua_next (void);
 
 #endif
diff --git a/opcode.c b/opcode.c
index aaf38b51..261baa5d 100644
--- a/opcode.c
+++ b/opcode.c
@@ -3,7 +3,7 @@
 ** TecCGraf - PUC-Rio
 */
 
-char *rcs_opcode="$Id: opcode.c,v 1.3 1994/03/28 15:14:02 celes Exp celes $";
+char *rcs_opcode="$Id: opcode.c,v 1.4 1994/04/13 21:37:20 celes Exp celes $";
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -319,7 +319,7 @@ int lua_execute (Byte *pc)
      if (tonumber(top-1)) return 1;
      if (nvalue(top-1) <= 0) nvalue(top-1) = 101;
     }
-    avalue(top-1) = lua_createarray(lua_hashcreate(nvalue(top-1)));
+    avalue(top-1) = lua_createarray(nvalue(top-1));
     if (avalue(top-1) == NULL)
      return 1;
     tag(top-1) = T_ARRAY;
@@ -603,13 +603,13 @@ int lua_execute (Byte *pc)
 
 
 /*
-** Mark all strings and arrays used by any object stored at stack.
+** Traverse all objects on stack
 */
-void lua_markstack (void)
+void lua_travstack (void (*fn)(Object *))
 {
  Object *o;
  for (o = top-1; o >= stack; o--)
-  lua_markobject (o);
+  fn (o);
 }
 
 /*
diff --git a/opcode.h b/opcode.h
index f48e50fd..38202f6e 100644
--- a/opcode.h
+++ b/opcode.h
@@ -1,6 +1,6 @@
 /*
 ** TeCGraf - PUC-Rio
-** $Id: opcode.h,v 1.3 1994/02/13 20:35:53 roberto Exp celes $
+** $Id: opcode.h,v 1.4 1994/04/13 21:37:20 celes Exp celes $
 */
 
 #ifndef opcode_h
@@ -159,5 +159,6 @@ void 	lua_obj2number (void);
 void    lua_print      (void);
 void    lua_internaldofile (void);
 void    lua_internaldostring (void);
+void    lua_travstack (void (*fn)(Object *));
 
 #endif
diff --git a/table.c b/table.c
index abbb8850..5d2f1b28 100644
--- a/table.c
+++ b/table.c
@@ -3,7 +3,7 @@
 ** Module to control static tables
 */
 
-char *rcs_table="$Id: table.c,v 1.4 1994/04/06 12:55:08 celes Exp celes $";
+char *rcs_table="$Id: table.c,v 1.5 1994/04/13 22:10:21 celes Exp celes $";
 
 #include <stdlib.h>
 #include <string.h>
@@ -75,18 +75,19 @@ static char 	       *stringbuffer[MAXSTRING];
 char                  **lua_string = stringbuffer;
 Word                    lua_nstring=0;
 
-#ifndef MAXARRAY
-#define MAXARRAY        512
-#endif
-static Hash             *arraybuffer[MAXARRAY];
-Hash                  **lua_array = arraybuffer;
-Word                    lua_narray=0;
-
 #define MAXFILE         20
 char                   *lua_file[MAXFILE];
 int                     lua_nfile;
 
 
+#define markstring(s)   (*((s)-1))
+
+
+/* Variables to controll garbage collection */
+Word lua_block=10; /* to check when garbage collector will be called */
+Word lua_nentity;   /* counter of new entities (strings and arrays) */
+
+
 /*
 ** Given a name, search it at symbol table and return its index. If not
 ** found, allocate at end of table, checking oveflow and return its index.
@@ -159,65 +160,64 @@ int lua_findconstant (char *s)
 
 
 /*
+** Traverse symbol table objects
+*/
+void lua_travsymbol (void (*fn)(Object *))
+{
+ int i;
+ for (i=0; i<lua_ntable; i++)
+  fn(&s_object(i));
+}
+
+
+/*
 ** Mark an object if it is a string or a unmarked array.
 */
 void lua_markobject (Object *o)
 {
  if (tag(o) == T_STRING)
-  lua_markstring (svalue(o)) = 1;
- else if (tag(o) == T_ARRAY && markarray(avalue(o)) == 0)
+  markstring (svalue(o)) = 1;
+ else if (tag(o) == T_ARRAY)
    lua_hashmark (avalue(o));
 }
 
+
 /*
-** Mark all strings and arrays used by any object stored at symbol table.
+** Garbage collection. 
+** Delete all unused strings and arrays.
 */
-static void lua_marktable (void)
+void lua_pack (void)
 {
- int i;
- for (i=0; i<lua_ntable; i++)
-  lua_markobject (&s_object(i));
+ /* mark stack strings */
+ lua_travstack(lua_markobject);
+ 
+ /* mark symbol table strings */
+ lua_travsymbol(lua_markobject);
+
+ lua_stringcollector();
+ lua_hashcollector();
+
+ lua_nentity = 0;      /* reset counter */
 } 
 
 /*
-** Simulate a garbage colection. When string table or array table overflows,
-** this function check if all allocated strings and arrays are in use. If
-** there are unused ones, pack (compress) the tables.
+** Garbage collection to atrings.
+** Delete all unmarked strings
 */
-static void lua_pack (void)
+void lua_stringcollector (void)
 {
- lua_markstack ();
- lua_marktable ();
- 
- { /* pack string */
-  int i, j;
-  for (i=j=0; i<lua_nstring; i++)
-   if (lua_markstring(lua_string[i]) == 1)
-   {
-    lua_string[j++] = lua_string[i];
-    lua_markstring(lua_string[i]) = 0;
-   }
-   else
-   {
-    free (lua_string[i]-1);
-   }
-  lua_nstring = j;
- }
-
- { /* pack array */
-  int i, j;
-  for (i=j=0; i<lua_narray; i++)
-   if (markarray(lua_array[i]) == 1)
-   {
-    lua_array[j++] = lua_array[i];
-    markarray(lua_array[i]) = 0;
-   }
-   else
-   {
-    lua_hashdelete (lua_array[i]);
-   }
-  lua_narray = j;
- }
+ int i, j;
+ for (i=j=0; i<lua_nstring; i++)
+  if (markstring(lua_string[i]) == 1)
+  {
+   lua_string[j++] = lua_string[i];
+   markstring(lua_string[i]) = 0;
+  }
+  else
+  {
+   free (lua_string[i]-1);
+  }
+ lua_nstring = j;
 }
 
 /*
@@ -237,7 +237,7 @@ char *lua_createstring (char *s)
    return lua_string[i];
   }
 
- if (lua_nstring >= MAXSTRING-1)
+ if (lua_nentity == lua_block || lua_nstring >= MAXSTRING-1)
  {
   lua_pack ();
   if (lua_nstring >= MAXSTRING-1)
@@ -247,33 +247,11 @@ char *lua_createstring (char *s)
   }
  } 
  lua_string[lua_nstring++] = s;
+ lua_nentity++;
  return s;
 }
 
 /*
-** Allocate a new array, already created, at array table. The function puts 
-** it at the end of the table, checking overflow, and returns its own pointer,
-** or NULL on error.
-*/
-void *lua_createarray (void *a)
-{
- if (a == NULL) return NULL;
- 
- if (lua_narray >= MAXARRAY-1)
- {
-  lua_pack ();
-  if (lua_narray >= MAXARRAY-1)
-  {
-   lua_error ("indexed table overflow");
-   return NULL;
-  }
- } 
- lua_array[lua_narray++] = a;
- return a;
-}
-
-
-/*
 ** Add a file name at file table, checking overflow. This function also set
 ** the external variable "lua_filename" with the function filename set.
 ** Return 0 on success or 1 on error.
diff --git a/table.h b/table.h
index ca246dc6..17be39e4 100644
--- a/table.h
+++ b/table.h
@@ -1,7 +1,7 @@
 /*
 ** Module to control static tables
 ** TeCGraf - PUC-Rio
-** $Id: table.h,v 1.1 1993/12/17 18:41:19 celes Exp roberto $
+** $Id: table.h,v 1.2 1993/12/22 21:15:16 roberto Exp celes $
 */
 
 #ifndef table_h
@@ -22,17 +22,21 @@ extern Word    lua_narray;
 extern char   *lua_file[];
 extern int     lua_nfile;
 
-#define lua_markstring(s)       (*((s)-1))
+extern Word    lua_block;
+extern Word    lua_nentity;
 
 
-int   lua_findsymbol           (char *s);
-int   lua_findconstant         (char *s);
-void  lua_markobject           (Object *o);
-char *lua_createstring         (char *s);
-void *lua_createarray          (void *a);
-int   lua_addfile              (char *fn);
-int   lua_delfile              (void);
-char *lua_filename             (void);
-void  lua_nextvar              (void);
+
+int   lua_findsymbol      (char *s);
+int   lua_findconstant    (char *s);
+void  lua_travsymbol      (void (*fn)(Object *));
+void  lua_markobject      (Object *o);
+void  lua_pack            (void);
+void  lua_stringcollector (void);
+char *lua_createstring    (char *s);
+int   lua_addfile         (char *fn);
+int   lua_delfile         (void);
+char *lua_filename        (void);
+void  lua_nextvar         (void);
 
 #endif