From 44521b21e542831a95de0c63271cd38d1cd4d394 Mon Sep 17 00:00:00 2001
From: Waldemar Celes <celes@tecgraf.puc-rio.br>
Date: Wed, 20 Apr 1994 19:07:57 -0300
Subject: Implementacao da nova estrategia para armazenar os arrays em lista
encadeada.
---
hash.c | 120 +++++++++++++++++++++++++++++++++++++++++++++++------------
hash.h | 10 ++---
opcode.c | 10 ++---
opcode.h | 3 +-
table.c | 128 ++++++++++++++++++++++++++-------------------------------------
table.h | 26 +++++++------
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.
@@ -158,66 +159,65 @@ 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,32 +247,10 @@ 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.
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
--
cgit v1.2.3-55-g6feb