--- stack/stack.c 2002/02/13 00:16:00 1.75 +++ stack/stack.c 2002/02/16 00:51:32 1.88 @@ -1,4 +1,4 @@ -/* printf, sscanf, fgets, fprintf */ +/* printf, sscanf, fgets, fprintf, fopen, perror */ #include /* exit, EXIT_SUCCESS, malloc, free */ #include @@ -8,108 +8,37 @@ #include /* strcmp, strcpy, strlen, strcat, strdup */ #include +/* getopt, STDIN_FILENO, STDOUT_FILENO */ +#include +/* EX_NOINPUT, EX_USAGE */ +#include +/* 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 */ - int non_eval_flag; - char *in_string; /* Input pending to be read */ -} 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->in_string= NULL; - env->err= 0; - env->non_eval_flag= 0; + env->gc_limit= 20; + env->gc_count= 0; + + env->head= NULL; for(i= 0; isymbols[i]= NULL; + env->err= 0; + env->in_string= NULL; + env->free_string= NULL; + env->inputstream= stdin; + env->interactive= 1; } void printerr(const char* in_string) { 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 */ - } - free(val); /* Free the actual list value */ - break; - case integer: - case func: - case symb: - break; - } - } -} - /* Discard the top element of the stack. */ extern void toss(environment *env) { @@ -121,7 +50,6 @@ 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 */ } @@ -155,12 +83,110 @@ } } +value* new_val(environment *env) { + value *nval= malloc(sizeof(value)); + stackitem *nitem= malloc(sizeof(stackitem)); + + if(env->gc_count >= env->gc_limit) + gc_init(env); + + nval->content.ptr= NULL; + + nitem->item= nval; + nitem->next= env->gc_ref; + env->gc_ref= nitem; + + env->gc_count++; + + 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; + + while(iterator!=NULL) { + iterator->item->gc_garb= 1; + iterator= iterator->next; + } + + /* Mark */ + 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+20; + env->gc_ref= new_head; +} + /* 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; } @@ -168,11 +194,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=1; push_val(env, new_value); } @@ -180,12 +205,11 @@ /* 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=1; push_val(env, new_value); } @@ -211,7 +235,6 @@ } extern void mangle(environment *env){ - value *new_value; char *new_string; if((env->head)==NULL) { @@ -231,12 +254,7 @@ toss(env); if(env->err) return; - new_value= malloc(sizeof(value)); - new_value->content.ptr= new_string; - new_value->type= string; - new_value->refcount=1; - - push_val(env, new_value); + push_cstring(env, new_string); } /* Push a symbol onto the stack. */ @@ -254,11 +272,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); @@ -281,21 +298,20 @@ if(handle==NULL) /* If no handle */ handle= dlopen(NULL, RTLD_LAZY); - funcptr= dlsym(handle, in_string); /* Get function pointer */ + 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); + 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= 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); @@ -338,14 +354,17 @@ } /* Prints the top element of the stack. */ -void print_h(stackitem *stack_head) +void print_h(stackitem *stack_head, int noquote) { switch(stack_head->item->type) { case integer: printf("%d", stack_head->item->content.val); break; case string: - printf("%s", (char*)stack_head->item->content.ptr); + if(noquote) + printf("%s", (char*)stack_head->item->content.ptr); + else + printf("\"%s\"", (char*)stack_head->item->content.ptr); break; case symb: printf("%s", ((symbol *)(stack_head->item->content.ptr))->id); @@ -358,7 +377,7 @@ stack_head=(stackitem *)(stack_head->item->content.ptr); printf("[ "); while(stack_head != NULL) { - print_h(stack_head); + print_h(stack_head, noquote); printf(" "); stack_head=stack_head->next; } @@ -373,7 +392,8 @@ env->err=1; return; } - print_h(env->head); + print_h(env->head, 0); + nl(); } /* Prints the top element of the stack and then discards it. */ @@ -384,13 +404,30 @@ toss(env); } +extern void princ_(environment *env) { + if(env->head==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + print_h(env->head, 1); +} + +/* Prints the top element of the stack and then discards it. */ +extern void princ(environment *env) +{ + princ_(env); + if(env->err) return; + toss(env); +} + /* Only to be called by function printstack. */ void print_st(stackitem *stack_head, long counter) { if(stack_head->next != NULL) print_st(stack_head->next, counter+1); printf("%ld: ", counter); - print_h(stack_head); + print_h(stack_head, 0); nl(); } @@ -398,10 +435,10 @@ extern void printstack(environment *env) { if(env->head == NULL) { + printf("Stack Empty\n"); return; } print_st(env->head, 1); - nl(); } /* Swap the two top elements on the stack. */ @@ -474,14 +511,14 @@ value* temp_val; stackitem* iterator; + eval_start: + if(env->head==NULL) { printerr("Too Few Arguments"); env->err=1; return; } - eval_start: - switch(env->head->item->type) { /* if it's a symbol */ case symb: @@ -502,7 +539,6 @@ /* If it's a list */ case list: temp_val= env->head->item; - env->head->item->refcount++; toss(env); if(env->err) return; iterator= (stackitem*)temp_val->content.ptr; @@ -513,7 +549,6 @@ toss(env); if(env->err) return; if(iterator->next == NULL){ - free_val(temp_val); goto eval_start; } eval(env); @@ -521,7 +556,6 @@ } iterator= iterator->next; } - free_val(temp_val); return; default: @@ -586,10 +620,9 @@ } /* Push list */ - pack= malloc(sizeof(value)); + pack= new_val(env); pack->type= list; pack->content.ptr= temp; - pack->refcount= 1; push_val(env, pack); rev(env); @@ -620,7 +653,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 */ @@ -706,12 +738,9 @@ 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); /* Bind the symbol to the value */ sym->val= env->head->next->item; - sym->val->refcount++; /* Increase the reference counter */ toss(env); toss(env); } @@ -719,6 +748,25 @@ /* Quit stack. */ extern void quit(environment *env) { + long i; + + clear(env); + + if (env->err) return; + for(i= 0; isymbols[i]!= NULL) { + forget_sym(&(env->symbols[i])); + } + env->symbols[i]= NULL; + } + + gc_init(env); + + if(env->free_string!=NULL) + free(env->free_string); + + muntrace(); + exit(EXIT_SUCCESS); } @@ -744,12 +792,22 @@ } } +/* Internal forget function */ +void forget_sym(symbol **hash_entry) { + symbol *temp; + + temp= *hash_entry; + *hash_entry= (*hash_entry)->next; + + free(temp->id); + free(temp); +} + /* Forgets a symbol (remove it from the hash table) */ extern void forget(environment *env) { char* sym_id; stackitem *stack_head= env->head; - symbol **hash_entry, *temp; if(stack_head==NULL) { printerr("Too Few Arguments"); @@ -766,15 +824,7 @@ sym_id= ((symbol*)(stack_head->item->content.ptr))->id; toss(env); - hash_entry= hash(env->symbols, sym_id); - temp= *hash_entry; - *hash_entry= (*hash_entry)->next; - - if(temp->val!=NULL) { - free_val(temp->val); - } - free(temp->id); - free(temp); + return forget_sym(hash(env->symbols, sym_id)); } /* Returns the current error number to the stack */ @@ -782,21 +832,57 @@ push_int(env, env->err); } -extern void read(environment*); - -int main() +int main(int argc, char **argv) { environment myenv; + int c; /* getopt option character */ + + mtrace(); + init_env(&myenv); + myenv.interactive = isatty(STDIN_FILENO) && isatty(STDOUT_FILENO); + + while ((c = getopt (argc, argv, "i")) != -1) + switch (c) + { + case 'i': + myenv.interactive = 1; + break; + case '?': + fprintf (stderr, + "Unknown option character `\\x%x'.\n", + optopt); + return EX_USAGE; + default: + abort (); + } + + if (optind < argc) { + myenv.interactive = 0; + myenv.inputstream= fopen(argv[optind], "r"); + if(myenv.inputstream== NULL) { + perror(argv[0]); + exit (EX_NOINPUT); + } + } + while(1) { - if(myenv.in_string==NULL) - printstack(&myenv); - read(&myenv); - if(myenv.err) { - printf("(error %d) ", myenv.err); + if(myenv.in_string==NULL) { + if (myenv.interactive) { + if(myenv.err) { + printf("(error %d)\n", myenv.err); + } + nl(); + printstack(&myenv); + printf("> "); + } myenv.err=0; + } + sx_72656164(&myenv); + if (myenv.err==4) { + return EX_NOINPUT; } else if(myenv.head!=NULL && myenv.head->item->type==symb && ((symbol*)(myenv.head->item->content.ptr))->id[0]==';') { @@ -808,7 +894,7 @@ return EXIT_FAILURE; } -/* + */ +/* "+" */ extern void sx_2b(environment *env) { int a, b; size_t len; @@ -825,15 +911,12 @@ && env->head->next->item->type==string) { a_val= env->head->item; b_val= env->head->next->item; - a_val->refcount++; - b_val->refcount++; 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); free(new_string); return; @@ -846,19 +929,14 @@ 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); - } + toss(env); if(env->err) return; + + b=env->head->item->content.val; + toss(env); if(env->err) return; + push_int(env, a+b); } -/* - */ +/* "-" */ extern void sx_2d(environment *env) { int a, b; @@ -875,19 +953,13 @@ 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); } -/* > */ +/* ">" */ extern void sx_3e(environment *env) { int a, b; @@ -904,28 +976,20 @@ 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); 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; @@ -946,7 +1010,7 @@ 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->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 @@ -961,14 +1025,14 @@ return new_value; } -/* duplicates an item on the stack */ -extern void dup(environment *env) { +/* "dup"; duplicates an item on the stack */ +extern void sx_647570(environment *env) { if((env->head)==NULL) { printerr("Too Few Arguments"); env->err=1; return; } - push_val(env, copy_val(env->head->item)); + push_val(env, copy_val(env, env->head->item)); } /* "if", If-Then */ @@ -1038,7 +1102,7 @@ eval(env); } -/* while */ +/* "while" */ extern void sx_7768696c65(environment *env) { int truth; @@ -1051,11 +1115,9 @@ } loop= env->head->item; - loop->refcount++; toss(env); if(env->err) return; test= env->head->item; - test->refcount++; toss(env); if(env->err) return; do { @@ -1079,12 +1141,9 @@ } } while(truth); - - free_val(test); - free_val(loop); } -/* For-loop */ +/* "for"; For-loop */ extern void sx_666f72(environment *env) { value *loop, *foo; @@ -1103,11 +1162,9 @@ } loop= env->head->item; - loop->refcount++; toss(env); if(env->err) return; foo= env->head->item; - foo->refcount++; toss(env); if(env->err) return; iterator= foo->content.ptr; @@ -1118,12 +1175,9 @@ eval(env); if(env->err) return; iterator= iterator->next; } - - free_val(loop); - free_val(foo); } -/* 'to' */ +/* "to" */ extern void to(environment *env) { int i, start, ending; stackitem *temp_head; @@ -1158,9 +1212,8 @@ push_int(env, i); } - temp_val= malloc(sizeof(value)); + temp_val= new_val(env); temp_val->content.ptr= env->head; - temp_val->refcount= 1; temp_val->type= list; env->head= temp_head; push_val(env, temp_val); @@ -1170,63 +1223,80 @@ extern void readline(environment *env) { char in_string[101]; - fgets(in_string, 100, stdin); - push_cstring(env, in_string); + if(fgets(in_string, 100, env->inputstream)==NULL) + push_cstring(env, ""); + else + push_cstring(env, in_string); } -/* Read a value and place on stack */ -extern void read(environment *env) { - const char symbform[]= "%[a-zA-Z0-9!$%*+./:<=>?@^_~-]%[\001-\377]"; - const char strform[]= "\"%[^\"]\"%[\001-\377]"; - const char intform[]= "%i%[\001-\377]"; - const char blankform[]= "%*[ \t]%[\001-\377]"; - const char ebrackform[]= "%*1[]]%[\001-\377]"; - const char semicform[]= "%*1[;]%[\001-\377]"; - const char bbrackform[]= "%*1[[]%[\001-\377]"; +/* "read"; Read a value and place on stack */ +extern void sx_72656164(environment *env) { + const char symbform[]= "%[a-zA-Z0-9!$%*+./:<=>?@^_~-]%n"; + 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"; - int itemp; + int itemp, readlength= -1; static int depth= 0; - char *rest, *match; + char *match; size_t inlength; if(env->in_string==NULL) { + if(depth > 0 && env->interactive) { + printf("]> "); + } readline(env); if(env->err) return; + + if(((char *)(env->head->item->content.ptr))[0]=='\0'){ + env->err= 4; /* "" means EOF */ + return; + } env->in_string= malloc(strlen(env->head->item->content.ptr)+1); + env->free_string= env->in_string; /* Save the original pointer */ strcpy(env->in_string, env->head->item->content.ptr); toss(env); if(env->err) return; } inlength= strlen(env->in_string)+1; match= malloc(inlength); - rest= malloc(inlength); - if(sscanf(env->in_string, blankform, rest)) { + if(sscanf(env->in_string, blankform, &readlength)!=EOF + && readlength != -1) { ; - } else if(sscanf(env->in_string, intform, &itemp, rest) > 0) { + } else if(sscanf(env->in_string, intform, &itemp, &readlength) != EOF + && readlength != -1) { push_int(env, itemp); - } else if(sscanf(env->in_string, strform, match, rest) > 0) { + } else if(sscanf(env->in_string, strform, match, &readlength) != EOF + && readlength != -1) { push_cstring(env, match); - } else if(sscanf(env->in_string, symbform, match, rest) > 0) { + } else if(sscanf(env->in_string, symbform, match, &readlength) != EOF + && readlength != -1) { push_sym(env, match); - } else if(sscanf(env->in_string, ebrackform, rest) > 0) { + } else if(sscanf(env->in_string, ebrackform, &readlength) != EOF + && readlength != -1) { pack(env); if(env->err) return; - if(depth!=0) depth--; - } else if(sscanf(env->in_string, semicform, rest) > 0) { + if(depth != 0) depth--; + } else if(sscanf(env->in_string, semicform, &readlength) != EOF + && readlength != -1) { push_sym(env, ";"); - } else if(sscanf(env->in_string, bbrackform, rest) > 0) { + } else if(sscanf(env->in_string, bbrackform, &readlength) != EOF + && readlength != -1) { push_sym(env, "["); depth++; } else { - free(rest); - rest= NULL; + free(env->free_string); + env->in_string = env->free_string = NULL; + } + if ( env->in_string != NULL) { + env->in_string += readlength; } - - free(env->in_string); - free(match); - env->in_string= rest; + free(match); if(depth) - return read(env); + return sx_72656164(env); }