--- stack/stack.c 2002/02/15 12:45:28 1.85 +++ stack/stack.c 2002/03/07 01:21:07 1.90 @@ -15,71 +15,18 @@ /* mtrace, muntrace */ #include -#define HASHTBLSIZE 2048 - -/* First, define some types. */ - -/* A value of some type */ -typedef struct { - enum { - integer, - string, - func, /* Function pointer */ - symb, - list - } type; /* Type of stack element */ - - union { - void *ptr; /* Pointer to the content */ - int val; /* ...or an integer */ - } content; /* Stores a pointer or an integer */ - - int refcount; /* Reference counter */ - -} value; - -/* A symbol with a name and possible value */ -/* (These do not need reference counters, they are kept unique by - hashing.) */ -typedef struct symbol_struct { - char *id; /* Symbol name */ - value *val; /* The value (if any) bound to it */ - struct symbol_struct *next; /* In case of hashing conflicts, a */ -} symbol; /* symbol is a kind of stack item. */ - -/* A type for a hash table for symbols */ -typedef symbol *hashtbl[HASHTBLSIZE]; /* Hash table declaration */ - -/* An item (value) on a stack */ -typedef struct stackitem_struct -{ - value *item; /* The value on the stack */ - /* (This is never NULL) */ - struct stackitem_struct *next; /* Next item */ -} stackitem; - -/* An environment; gives access to the stack and a hash table of - defined symbols */ -typedef struct { - stackitem *head; /* Head of the stack */ - hashtbl symbols; /* Hash table of all variable bindings */ - int err; /* Error flag */ - char *in_string; /* Input pending to be read */ - char *free_string; /* Free this string when all input is - read from in_string */ - FILE *inputstream; /* stdin or a file, most likely */ - int interactive; /* print prompts, stack, etc */ -} environment; - -/* A type for pointers to external functions */ -typedef void (*funcp)(environment *); /* funcp is a pointer to a void - function (environment *) */ +#include "stack.h" /* Initialize a newly created environment */ void init_env(environment *env) { int i; + env->gc_limit= 20; + env->gc_count= 0; + env->gc_ref= NULL; + env->gc_protect= NULL; + env->head= NULL; for(i= 0; isymbols[i]= NULL; @@ -94,39 +41,6 @@ fprintf(stderr, "Err: %s\n", in_string); } -/* Throw away a value */ -void free_val(value *val){ - stackitem *item, *temp; - - val->refcount--; /* Decrease the reference count */ - if(val->refcount == 0){ - switch (val->type){ /* and free the contents if necessary */ - case string: - free(val->content.ptr); - break; - case list: /* lists needs to be freed recursively */ - item=val->content.ptr; - while(item != NULL) { /* for all stack items */ - free_val(item->item); /* free the value */ - temp=item->next; /* save next ptr */ - free(item); /* free the stackitem */ - item=temp; /* go to next stackitem */ - } - break; - case integer: - case func: - break; - case symb: - free(((symbol*)(val->content.ptr))->id); - if(((symbol*)(val->content.ptr))->val!=NULL) - free_val(((symbol*)(val->content.ptr))->val); - free(val->content.ptr); - break; - } - free(val); /* Free the actual value structure */ - } -} - /* Discard the top element of the stack. */ extern void toss(environment *env) { @@ -134,13 +48,14 @@ if((env->head)==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } - free_val(env->head->item); /* Free the value */ env->head= env->head->next; /* Remove the top stack item */ free(temp); /* Free the old top stack item */ + + gc_init(env); } /* Returns a pointer to a pointer to an element in the hash table. */ @@ -172,12 +87,136 @@ } } +value* new_val(environment *env) { + value *nval= malloc(sizeof(value)); + stackitem *nitem= malloc(sizeof(stackitem)); + + nval->content.ptr= NULL; + protect(env, nval); + + gc_init(env); + + nitem->item= nval; + nitem->next= env->gc_ref; + env->gc_ref= nitem; + + env->gc_count++; + unprotect(env); + + return nval; +} + +void gc_mark(value *val) { + stackitem *iterator; + + if(val==NULL || val->gc_garb==0) + return; + + val->gc_garb= 0; + + if(val->type==list) { + iterator= val->content.ptr; + + while(iterator!=NULL) { + gc_mark(iterator->item); + iterator= iterator->next; + } + } +} + +extern void gc_init(environment *env) { + stackitem *new_head= NULL, *titem, *iterator= env->gc_ref; + symbol *tsymb; + int i; + + if(env->gc_count < env->gc_limit) + return; + + while(iterator!=NULL) { + iterator->item->gc_garb= 1; + iterator= iterator->next; + } + + /* Mark */ + iterator= env->gc_protect; + while(iterator!=NULL) { + gc_mark(iterator->item); + iterator= iterator->next; + } + + iterator= env->head; + while(iterator!=NULL) { + gc_mark(iterator->item); + iterator= iterator->next; + } + + for(i= 0; isymbols[i]; + while(tsymb!=NULL) { + gc_mark(tsymb->val); + tsymb= tsymb->next; + } + } + + env->gc_count= 0; + + /* Sweep */ + while(env->gc_ref!=NULL) { + + if(env->gc_ref->item->gc_garb) { + switch(env->gc_ref->item->type) { + case string: + free(env->gc_ref->item->content.ptr); + break; + case integer: + break; + case list: + while(env->gc_ref->item->content.ptr!=NULL) { + titem= env->gc_ref->item->content.ptr; + env->gc_ref->item->content.ptr= titem->next; + free(titem); + } + break; + default: + break; + } + free(env->gc_ref->item); + titem= env->gc_ref->next; + free(env->gc_ref); + env->gc_ref= titem; + } else { + titem= env->gc_ref->next; + env->gc_ref->next= new_head; + new_head= env->gc_ref; + env->gc_ref= titem; + env->gc_count++; + } + } + + env->gc_limit= env->gc_count*2; + env->gc_ref= new_head; +} + +void protect(environment *env, value *val) +{ + stackitem *new_item= malloc(sizeof(stackitem)); + new_item->item= val; + new_item->next= env->gc_protect; + env->gc_protect= new_item; +} + +void unprotect(environment *env) +{ + stackitem *temp= env->gc_protect; + env->gc_protect= env->gc_protect->next; + free(temp); +} + /* Push a value onto the stack */ void push_val(environment *env, value *val) { stackitem *new_item= malloc(sizeof(stackitem)); new_item->item= val; - val->refcount++; new_item->next= env->head; env->head= new_item; } @@ -185,11 +224,10 @@ /* Push an integer onto the stack. */ void push_int(environment *env, int in_val) { - value *new_value= malloc(sizeof(value)); + value *new_value= new_val(env); new_value->content.val= in_val; new_value->type= integer; - new_value->refcount= 0; push_val(env, new_value); } @@ -197,32 +235,30 @@ /* Copy a string onto the stack. */ void push_cstring(environment *env, const char *in_string) { - value *new_value= malloc(sizeof(value)); + value *new_value= new_val(env); new_value->content.ptr= malloc(strlen(in_string)+1); strcpy(new_value->content.ptr, in_string); new_value->type= string; - new_value->refcount= 0; push_val(env, new_value); } /* Mangle a symbol name to a valid C identifier name */ char *mangle_str(const char *old_string){ - char validchars[] - ="0123456789abcdef"; + char validchars[]= "0123456789abcdef"; char *new_string, *current; - new_string=malloc((strlen(old_string)*2)+4); + new_string= malloc((strlen(old_string)*2)+4); strcpy(new_string, "sx_"); /* Stack eXternal */ - current=new_string+3; + current= new_string+3; while(old_string[0] != '\0'){ - current[0]=validchars[(unsigned char)(old_string[0])/16]; - current[1]=validchars[(unsigned char)(old_string[0])%16]; - current+=2; + current[0]= validchars[(unsigned char)(old_string[0])/16]; + current[1]= validchars[(unsigned char)(old_string[0])%16]; + current+= 2; old_string++; } - current[0]='\0'; + current[0]= '\0'; return new_string; /* The caller must free() it */ } @@ -232,13 +268,13 @@ if((env->head)==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } if(env->head->item->type!=string) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } @@ -265,11 +301,10 @@ const char *dlerr; /* Dynamic linker error */ char *mangled; /* Mangled function name */ - new_value= malloc(sizeof(value)); + new_value= new_val(env); /* The new value is a symbol */ new_value->type= symb; - new_value->refcount= 1; /* Look up the symbol name in the hash table */ new_symbol= hash(env->symbols, in_string); @@ -292,21 +327,20 @@ if(handle==NULL) /* If no handle */ handle= dlopen(NULL, RTLD_LAZY); - funcptr= dlsym(handle, in_string); /* Get function pointer */ - dlerr=dlerror(); + mangled= mangle_str(in_string); /* mangle the name */ + funcptr= dlsym(handle, mangled); /* and try to find it */ + free(mangled); + dlerr= dlerror(); if(dlerr != NULL) { /* If no function was found */ - mangled=mangle_str(in_string); - funcptr= dlsym(handle, mangled); /* try mangling it */ - free(mangled); - dlerr=dlerror(); + funcptr= dlsym(handle, in_string); /* Get function pointer */ + dlerr= dlerror(); } if(dlerr==NULL) { /* If a function was found */ - new_fvalue= malloc(sizeof(value)); /* Create a new value */ - new_fvalue->type=func; /* The new value is a function pointer */ - new_fvalue->content.ptr=funcptr; /* Store function pointer */ + new_fvalue= new_val(env); /* Create a new value */ + new_fvalue->type= func; /* The new value is a function pointer */ + new_fvalue->content.ptr= funcptr; /* Store function pointer */ (*new_symbol)->val= new_fvalue; /* Bind the symbol to the new function value */ - new_fvalue->refcount= 1; } } push_val(env, new_value); @@ -492,9 +526,11 @@ env->err=3; return; } + protect(env, val); toss(env); /* toss the symbol */ if(env->err) return; push_val(env, val); /* Return its bound value */ + unprotect(env); } /* If the top element is a symbol, determine if it's bound to a @@ -529,23 +565,26 @@ in_func= (funcp)(env->head->item->content.ptr); toss(env); if(env->err) return; - return (*in_func)(env); + return in_func(env); /* If it's a list */ case list: temp_val= env->head->item; - env->head->item->refcount++; + protect(env, temp_val); toss(env); if(env->err) return; iterator= (stackitem*)temp_val->content.ptr; + unprotect(env); + while(iterator!=NULL) { push_val(env, iterator->item); + if(env->head->item->type==symb && strcmp(";", ((symbol*)(env->head->item->content.ptr))->id)==0) { toss(env); if(env->err) return; + if(iterator->next == NULL){ - free_val(temp_val); goto eval_start; } eval(env); @@ -553,7 +592,6 @@ } iterator= iterator->next; } - free_val(temp_val); return; default: @@ -567,25 +605,25 @@ if((env->head)==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } if(env->head->item->type!=list) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } - old_head=(stackitem *)(env->head->item->content.ptr); - new_head=NULL; + old_head= (stackitem *)(env->head->item->content.ptr); + new_head= NULL; while(old_head != NULL){ - item=old_head; - old_head=old_head->next; - item->next=new_head; - new_head=item; + item= old_head; + old_head= old_head->next; + item->next= new_head; + new_head= item; } - env->head->item->content.ptr=new_head; + env->head->item->content.ptr= new_head; } /* Make a list. */ @@ -618,10 +656,9 @@ } /* Push list */ - pack= malloc(sizeof(value)); + pack= new_val(env); pack->type= list; pack->content.ptr= temp; - pack->refcount= 0; push_val(env, pack); rev(env); @@ -635,12 +672,12 @@ /* Is top element a list? */ if(env->head==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } if(env->head->item->type!=list) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } @@ -652,7 +689,6 @@ /* The first list element is the new stack head */ new_head= temp= env->head->item->content.ptr; - env->head->item->refcount++; toss(env); /* Find the end of the list */ @@ -673,7 +709,7 @@ if((env->head)==NULL || env->head->next==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } @@ -693,13 +729,13 @@ if((env->head)==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } if(env->head->item->type!=integer) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } @@ -724,34 +760,25 @@ /* Needs two values on the stack, the top one must be a symbol */ if(env->head==NULL || env->head->next==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } if(env->head->item->type!=symb) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } /* long names are a pain */ - sym=env->head->item->content.ptr; - - /* if the symbol was bound to something else, throw it away */ - if(sym->val != NULL) - free_val(sym->val); + sym= env->head->item->content.ptr; /* Bind the symbol to the value */ sym->val= env->head->next->item; - sym->val->refcount++; /* Increase the reference counter */ toss(env); toss(env); } -extern void clear(environment *); -void forget_sym(symbol **); -extern void words(environment *); - /* Quit stack. */ extern void quit(environment *env) { @@ -767,6 +794,9 @@ env->symbols[i]= NULL; } + env->gc_limit= 0; + gc_init(env); + if(env->free_string!=NULL) free(env->free_string); @@ -804,9 +834,6 @@ temp= *hash_entry; *hash_entry= (*hash_entry)->next; - if(temp->val!=NULL) { - free_val(temp->val); - } free(temp->id); free(temp); } @@ -840,8 +867,6 @@ push_int(env, env->err); } -extern void sx_72656164(environment*); - int main(int argc, char **argv) { environment myenv; @@ -899,6 +924,7 @@ toss(&myenv); /* No error check in main */ eval(&myenv); } + gc_init(&myenv); } quit(&myenv); return EXIT_FAILURE; @@ -913,7 +939,7 @@ if((env->head)==NULL || env->head->next==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } @@ -921,16 +947,15 @@ && env->head->next->item->type==string) { a_val= env->head->item; b_val= env->head->next->item; - a_val->refcount++; - b_val->refcount++; + protect(env, a_val); protect(env, b_val); toss(env); if(env->err) return; toss(env); if(env->err) return; len= strlen(a_val->content.ptr)+strlen(b_val->content.ptr)+1; new_string= malloc(len); strcpy(new_string, b_val->content.ptr); strcat(new_string, a_val->content.ptr); - free_val(a_val); free_val(b_val); push_cstring(env, new_string); + unprotect(env); unprotect(env); free(new_string); return; } @@ -941,17 +966,12 @@ env->err=2; return; } - a=env->head->item->content.val; - toss(env); - if(env->err) return; - if(env->head->item->refcount == 1) - env->head->item->content.val += a; - else { - b=env->head->item->content.val; - toss(env); - if(env->err) return; - push_int(env, a+b); - } + a= env->head->item->content.val; + toss(env); if(env->err) return; + + b= env->head->item->content.val; + toss(env); if(env->err) return; + push_int(env, a+b); } /* "-" */ @@ -970,17 +990,12 @@ env->err=2; return; } + a=env->head->item->content.val; - toss(env); - if(env->err) return; - if(env->head->item->refcount == 1) - env->head->item->content.val -= a; - else { - b=env->head->item->content.val; - toss(env); - if(env->err) return; - push_int(env, b-a); - } + toss(env); if(env->err) return; + b=env->head->item->content.val; + toss(env); if(env->err) return; + push_int(env, b-a); } /* ">" */ @@ -999,61 +1014,58 @@ env->err=2; return; } + a=env->head->item->content.val; - toss(env); - if(env->err) return; - if(env->head->item->refcount == 1) - env->head->item->content.val = (env->head->item->content.val > a); - else { - b=env->head->item->content.val; - toss(env); - if(env->err) return; - push_int(env, b>a); - } + toss(env); if(env->err) return; + b=env->head->item->content.val; + toss(env); if(env->err) return; + push_int(env, b>a); } /* Return copy of a value */ -value *copy_val(value *old_value){ +value *copy_val(environment *env, value *old_value){ stackitem *old_item, *new_item, *prev_item; - value *new_value=malloc(sizeof(value)); + value *new_value= new_val(env); + + protect(env, old_value); + new_value->type= old_value->type; - new_value->type=old_value->type; - new_value->refcount=0; /* This is increased if/when this - value is referenced somewhere, like - in a stack item or a variable */ switch(old_value->type){ case integer: - new_value->content.val=old_value->content.val; + new_value->content.val= old_value->content.val; break; case string: - (char *)(new_value->content.ptr) - = strdup((char *)(old_value->content.ptr)); + (char *)(new_value->content.ptr)= + strdup((char *)(old_value->content.ptr)); break; case func: case symb: - new_value->content.ptr=old_value->content.ptr; + new_value->content.ptr= old_value->content.ptr; break; case list: - new_value->content.ptr=NULL; + new_value->content.ptr= NULL; - prev_item=NULL; - old_item=(stackitem *)(old_value->content.ptr); + prev_item= NULL; + old_item= (stackitem*)(old_value->content.ptr); while(old_item != NULL) { /* While list is not empty */ new_item= malloc(sizeof(stackitem)); - new_item->item=copy_val(old_item->item); /* recurse */ - new_item->next=NULL; + new_item->item= copy_val(env, old_item->item); /* recurse */ + new_item->next= NULL; if(prev_item != NULL) /* If this wasn't the first item */ - prev_item->next=new_item; /* point the previous item to the + prev_item->next= new_item; /* point the previous item to the new item */ else - new_value->content.ptr=new_item; - old_item=old_item->next; - prev_item=new_item; + new_value->content.ptr= new_item; + old_item= old_item->next; + prev_item= new_item; } break; } + + unprotect(env); + return new_value; } @@ -1061,10 +1073,10 @@ extern void sx_647570(environment *env) { if((env->head)==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } - push_val(env, copy_val(env->head->item)); + push_val(env, copy_val(env, env->head->item)); } /* "if", If-Then */ @@ -1074,7 +1086,7 @@ if((env->head)==NULL || env->head->next==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } @@ -1147,11 +1159,11 @@ } loop= env->head->item; - loop->refcount++; + protect(env, loop); toss(env); if(env->err) return; test= env->head->item; - test->refcount++; + protect(env, test); toss(env); if(env->err) return; do { @@ -1160,7 +1172,7 @@ if(env->head->item->type != integer) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } @@ -1176,34 +1188,81 @@ } while(truth); - free_val(test); - free_val(loop); + unprotect(env); unprotect(env); } -/* "for"; For-loop */ + +/* "for"; for-loop */ extern void sx_666f72(environment *env) { + value *loop; + int foo1, foo2; + + if(env->head==NULL || env->head->next==NULL + || env->head->next->next==NULL) { + printerr("Too Few Arguments"); + env->err= 1; + return; + } + + if(env->head->next->item->type!=integer + || env->head->next->next->item->type!=integer) { + printerr("Bad Argument Type"); + env->err= 2; + return; + } + + loop= env->head->item; + protect(env, loop); + toss(env); if(env->err) return; + + foo2= env->head->item->content.val; + toss(env); if(env->err) return; + + foo1= env->head->item->content.val; + toss(env); if(env->err) return; + + if(foo1<=foo2) { + while(foo1<=foo2) { + push_int(env, foo1); + push_val(env, loop); + eval(env); if(env->err) return; + foo1++; + } + } else { + while(foo1>=foo2) { + push_int(env, foo1); + push_val(env, loop); + eval(env); if(env->err) return; + foo1--; + } + } + unprotect(env); +} + +/* Variant of for-loop */ +extern void foreach(environment *env) { value *loop, *foo; stackitem *iterator; if((env->head)==NULL || env->head->next==NULL) { printerr("Too Few Arguments"); - env->err=1; + env->err= 1; return; } if(env->head->next->item->type != list) { printerr("Bad Argument Type"); - env->err=2; + env->err= 2; return; } loop= env->head->item; - loop->refcount++; + protect(env, loop); toss(env); if(env->err) return; foo= env->head->item; - foo->refcount++; + protect(env, foo); toss(env); if(env->err) return; iterator= foo->content.ptr; @@ -1214,9 +1273,7 @@ eval(env); if(env->err) return; iterator= iterator->next; } - - free_val(loop); - free_val(foo); + unprotect(env); unprotect(env); } /* "to" */ @@ -1254,9 +1311,8 @@ push_int(env, i); } - temp_val= malloc(sizeof(value)); + temp_val= new_val(env); temp_val->content.ptr= env->head; - temp_val->refcount= 0; temp_val->type= list; env->head= temp_head; push_val(env, temp_val); @@ -1278,9 +1334,9 @@ const char strform[]= "\"%[^\"]\"%n"; const char intform[]= "%i%n"; const char blankform[]= "%*[ \t]%n"; - const char ebrackform[]= "%*1[]]%n"; - const char semicform[]= "%*1[;]%n"; - const char bbrackform[]= "%*1[[]%n"; + const char ebrackform[]= "]%n"; + const char semicform[]= ";%n"; + const char bbrackform[]= "[%n"; int itemp, readlength= -1; static int depth= 0;