cvs/stack/stack.c

/* printf */
#include <stdio.h>
/* EXIT_SUCCESS */
#include <stdlib.h>
/* NULL */
#include <stddef.h>
/* dlopen, dlsym, dlerror */
#include <dlfcn.h>

#define HASHTBLSIZE 65536

typedef struct stack_item
{
  enum {value, string, ref, func, symbol, list} type;
  union {
    void* ptr;
    int val;
  } content;

  char* id;
  struct stack_item* next;
} stackitem;


typedef stackitem* hashtbl[HASHTBLSIZE];
typedef void (*funcp)(stackitem**);


/* Initiates a newly created hash table. */
void init_hashtbl(hashtbl out_hash)
{
  long i;

  for(i= 0; i<HASHTBLSIZE; i++)
    out_hash[i]= NULL;
}

/* Returns a pointer to an element in the hash table. */
stackitem** hash(hashtbl in_hashtbl, const char* in_string)
{
  long i= 0;
  unsigned long out_hash= 0;
  char key= 0;
  stackitem** position;
  
  while(1){
    key= in_string[i++];
    if(key=='\0')
      break;
    out_hash= out_hash*32+key;
  }

  out_hash= out_hash%HASHTBLSIZE;
  position= &(in_hashtbl[out_hash]);

  while(1){
    if(*position==NULL)
      return position;
    
    if(strcmp(in_string, (*position)->id)==0)
      return position;

    position= &((*position)->next);
  }
}

/* Generic push function. */
int push(stackitem** stack_head, stackitem* in_item)
{
  in_item->next= *stack_head;
  *stack_head= in_item;
  return 1;
}

/* Push a value on the stack. */
int push_val(stackitem** stack_head, int in_val) 
{
  stackitem* new_item= malloc(sizeof(stackitem));
  new_item->content.val= in_val;
  new_item->type= value;

  push(stack_head, new_item);
  return 1;
}

/* Copy a string onto the stack. */
int push_cstring(stackitem** stack_head, const char* in_string)
{
  stackitem* new_item= malloc(sizeof(stackitem));
  new_item->content.ptr= malloc(strlen(in_string)+1);
  strcpy(new_item->content.ptr, in_string);
  new_item->type= string;

  push(stack_head, new_item);
  return 1;
}

/* Create a new hash entry. */
int mk_hashentry(hashtbl in_hashtbl, stackitem* in_item, const char* id)
{
  in_item->id= malloc(strlen(id)+1);

  strcpy(in_item->id, id);
  push(hash(in_hashtbl, id), in_item);

  return 1;
}

/* Define a function a new function in the hash table. */
void def_func(hashtbl in_hashtbl, funcp in_func, const char* id)
{
  stackitem* temp= malloc(sizeof(stackitem));

  temp->type= func;
  temp->content.ptr= in_func;

  mk_hashentry(in_hashtbl, temp, id);
}

/* Define a new symbol in the hash table. */
void def_sym(hashtbl in_hashtbl, const char* id)
{
  stackitem* temp= malloc(sizeof(stackitem));
  
  temp->type= symbol;

  mk_hashentry(in_hashtbl, temp, id);
}

/* Push a reference to an entry in the hash table onto the stack. */
int push_ref(stackitem** stack_head, hashtbl in_hash, const char* in_string)
{
  static void* handle= NULL;
  void* symbol;

  stackitem* new_item= malloc(sizeof(stackitem));
  new_item->content.ptr= *hash(in_hash, in_string);
  new_item->type= ref;

  if(new_item->content.ptr==NULL) {
    if(handle==NULL)
      handle= dlopen(NULL, RTLD_LAZY);    

    symbol= dlsym(handle, in_string);
    if(dlerror()==NULL) 
      def_func(in_hash, symbol, in_string);
    else
      def_sym(in_hash, in_string);
      
    new_item->content.ptr= *hash(in_hash, in_string);
    new_item->type= ref;
  }

  push(stack_head, new_item);
  return 1;
}

/* Discard the top element of the stack. */
extern void toss(stackitem** stack_head)
{
  stackitem* temp= *stack_head;

  if((*stack_head)==NULL)
    return;
  
  if((*stack_head)->type==string)
    free((*stack_head)->content.ptr);

  *stack_head= (*stack_head)->next;
  free(temp);
}

/* Print newline. */
extern void nl()
{
  printf("\n");
}

/* Prints the top element of the stack. */
void print_(stackitem** stack_head)
{
  if((*stack_head)==NULL)
    return;

  switch((*stack_head)->type) {
  case value:
    printf("%d", (*stack_head)->content.val);
    break;
  case string:
    printf("%s", (char*)(*stack_head)->content.ptr);
    break;
  case ref:
    printf("%s", ((stackitem*)(*stack_head)->content.ptr)->id);
    break;
  case symbol:
  default:
    printf("%p", (*stack_head)->content.ptr);
    break;
  }
}

/* Prints the top element of the stack and then discards it. */
extern void print(stackitem** stack_head)
{
  print_(stack_head);
  toss(stack_head);
}

/* 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_(&stack_head);
  nl();
}

/* Prints the stack. */
extern void printstack(stackitem** stack_head)
{
  if(*stack_head != NULL) {
    print_st(*stack_head, 1);
    printf("\n");
  }
}

/* If the top element is a reference, determine if it's a reference to a
   function, and if it is execute and pop the reference and execute the
   function. */
extern void eval(stackitem** stack_head)
{
  funcp in_func;

  if((*stack_head)==NULL || (*stack_head)->type!=ref)
    return;

  if(((stackitem*)(*stack_head)->content.ptr)->type==func) {
    in_func= (funcp)((stackitem*)(*stack_head)->content.ptr)->content.ptr;
    toss(stack_head); 
    (*in_func)(stack_head);
    return;
  }
}

/* Parse input. */
int stack_read(stackitem** stack_head, hashtbl in_hash, char* in_line) 
{
  char *temp, *rest;
  int itemp;
  size_t inlength= strlen(in_line)+1;
  int convert= 0;

  temp= malloc(inlength);
  rest= malloc(inlength);

  do {
    if((convert= sscanf(in_line, "\"%[^\"\n\r]\" %[^\n\r]", temp, rest))) {
      push_cstring(stack_head, temp);
      break;
    }
 
    if((convert= sscanf(in_line, "%d %[^\n\r]", &itemp, rest))) {
      push_val(stack_head, itemp);
      break;
    }
 
    if((convert= sscanf(in_line, "\\%c%[^\n\r]", temp, rest))) {
      temp[1]= '\0'; 
      push_ref(stack_head, in_hash, temp);
      break;
    } 
      
    if((convert= sscanf(in_line, "%[^ ;\n\r]%[^\n\r]", temp, rest))) {
        push_ref(stack_head, in_hash, temp);
        break;
    }
  
    if((convert= sscanf(in_line, "%c%[^\n\r]", temp, rest)) && *temp==';') {
      eval(stack_head);
      break;
    }
  } while(0);


  free(temp);

  if(convert<2) {
    free(rest);
    return 0;
  }
   
  stack_read(stack_head, in_hash, rest);
  
  free(rest);
  return 1;
}

/* Make a list. */
extern void pack(stackitem** stack_head)
{
  void* delimiter;
  stackitem *iterator, *temp, *pack;

  if((*stack_head)==NULL)
    return;

  delimiter= (*stack_head)->content.ptr;
  toss(stack_head);

  iterator= *stack_head;

  while(iterator->next!=NULL && iterator->next->content.ptr!=delimiter)
    iterator= iterator->next;

  temp= *stack_head;
  *stack_head= iterator->next;
  iterator->next= NULL;
  
  if(*stack_head!=NULL && (*stack_head)->content.ptr==delimiter)
    toss(stack_head);

  pack= malloc(sizeof(stackitem));
  pack->type= list;
  pack->content.ptr= temp;

  push(stack_head, pack);
}

/* Push elements of the list on the stack. */
extern void expand(stackitem** stack_head)
{
  stackitem *temp, *new_head;

  if((*stack_head)==NULL || (*stack_head)->type!=list)
    return;

  new_head= temp= (*stack_head)->content.ptr;
  toss(stack_head);

  while(temp->next!=NULL)
    temp= temp->next;

  temp->next= *stack_head;
  *stack_head= new_head;
}

/* Swap the two top elements on the stack. */
extern void swap(stackitem** stack_head)
{
  stackitem* temp= (*stack_head);
  
  if((*stack_head)==NULL || (*stack_head)->next==NULL)
    return;

  *stack_head= (*stack_head)->next;
  temp->next= (*stack_head)->next;
  (*stack_head)->next= temp;
} 

/* Compares two elements by reference. */
extern void eq(stackitem** stack_head)
{
  void *left, *right;
  int result;

  if((*stack_head)==NULL || (*stack_head)->next==NULL)
    return;

  left= (*stack_head)->content.ptr;
  swap(stack_head);
  right= (*stack_head)->content.ptr;
  result= (left==right);
  
  toss(stack_head); toss(stack_head);
  push_val(stack_head, (left==right));
}

/* Negates the top element on the stack. */
extern void not(stackitem** stack_head)
{
  int value;

  if((*stack_head)==NULL)
    return;

  value= (*stack_head)->content.val;
  toss(stack_head);
  push_val(stack_head, !value);
}

/* Compares the two top elements on the stack and return 0 if they're the
   same. */
extern void neq(stackitem** stack_head)
{
  eq(stack_head);
  not(stack_head);
}

/* Give a symbol some content. */
extern void def(stackitem** stack_head)
{
  stackitem *temp, *value;

  if(*stack_head==NULL || (*stack_head)->next==NULL 
     || (*stack_head)->type!=ref)
    return;

  temp= (*stack_head)->content.ptr;
  value= (*stack_head)->next;
  temp->content= value->content;
  value->content.ptr=NULL;
  temp->type= value->type;

  toss(stack_head); toss(stack_head);
} 

/* Quit stack. */
extern void quit()
{
  exit(EXIT_SUCCESS);
}

int main()
{
  stackitem* s= NULL;
  hashtbl myhash;
  char in_string[100];

  init_hashtbl(myhash);

  printf("okidok\n ");

  while(fgets(in_string, 100, stdin) != NULL) {
    stack_read(&s, myhash, in_string);
    printf("okidok\n ");
  }

  exit(EXIT_SUCCESS);
}

/* Local Variables: */
/* compile-command:"make CFLAGS=\"-Wall -g -rdynamic -ldl\" stack" */
/* End: */
1	masse	1.1	/* printf */
2			#include <stdio.h>
3			/* EXIT_SUCCESS */
4			#include <stdlib.h>
5			/* NULL */
6			#include <stddef.h>
7	teddy	1.3	/* dlopen, dlsym, dlerror */
8	masse	1.1	#include <dlfcn.h>
9
10			#define HASHTBLSIZE 65536
11
12			typedef struct stack_item
13			{
14	masse	1.7	enum {value, string, ref, func, symbol, list} type;
15	masse	1.1	union {
16			void* ptr;
17			int val;
18			} content;
19
20			char* id;
21			struct stack_item* next;
22			} stackitem;
23
24
25			typedef stackitem* hashtbl[HASHTBLSIZE];
26			typedef void (funcp)(stackitem*);
27
28	masse	1.14
29			/* Initiates a newly created hash table. */
30	masse	1.1	void init_hashtbl(hashtbl out_hash)
31			{
32			long i;
33
34			for(i= 0; i<HASHTBLSIZE; i++)
35			out_hash[i]= NULL;
36			}
37
38	masse	1.14	/* Returns a pointer to an element in the hash table. */
39	masse	1.1	stackitem** hash(hashtbl in_hashtbl, const char* in_string)
40			{
41			long i= 0;
42			unsigned long out_hash= 0;
43			char key= 0;
44			stackitem** position;
45
46			while(1){
47			key= in_string[i++];
48			if(key=='\0')
49			break;
50			out_hash= out_hash*32+key;
51			}
52
53			out_hash= out_hash%HASHTBLSIZE;
54			position= &(in_hashtbl[out_hash]);
55
56			while(1){
57			if(*position==NULL)
58			return position;
59
60			if(strcmp(in_string, (*position)->id)==0)
61			return position;
62
63			position= &((*position)->next);
64			}
65			}
66
67	masse	1.14	/* Generic push function. */
68	masse	1.1	int push(stackitem** stack_head, stackitem* in_item)
69			{
70			in_item->next= *stack_head;
71			*stack_head= in_item;
72			return 1;
73			}
74
75	masse	1.14	/* Push a value on the stack. */
76	masse	1.1	int push_val(stackitem** stack_head, int in_val)
77			{
78			stackitem* new_item= malloc(sizeof(stackitem));
79			new_item->content.val= in_val;
80			new_item->type= value;
81
82			push(stack_head, new_item);
83			return 1;
84			}
85
86	masse	1.14	/* Copy a string onto the stack. */
87	masse	1.1	int push_cstring(stackitem** stack_head, const char* in_string)
88			{
89			stackitem* new_item= malloc(sizeof(stackitem));
90			new_item->content.ptr= malloc(strlen(in_string)+1);
91			strcpy(new_item->content.ptr, in_string);
92			new_item->type= string;
93
94			push(stack_head, new_item);
95			return 1;
96			}
97
98	masse	1.14	/* Create a new hash entry. */
99	masse	1.1	int mk_hashentry(hashtbl in_hashtbl, stackitem* in_item, const char* id)
100			{
101			in_item->id= malloc(strlen(id)+1);
102
103			strcpy(in_item->id, id);
104			push(hash(in_hashtbl, id), in_item);
105
106			return 1;
107			}
108
109	masse	1.14	/* Define a function a new function in the hash table. */
110	masse	1.1	void def_func(hashtbl in_hashtbl, funcp in_func, const char* id)
111			{
112			stackitem* temp= malloc(sizeof(stackitem));
113
114			temp->type= func;
115			temp->content.ptr= in_func;
116
117			mk_hashentry(in_hashtbl, temp, id);
118			}
119
120	masse	1.14	/* Define a new symbol in the hash table. */
121	masse	1.4	void def_sym(hashtbl in_hashtbl, const char* id)
122			{
123			stackitem* temp= malloc(sizeof(stackitem));
124
125			temp->type= symbol;
126
127			mk_hashentry(in_hashtbl, temp, id);
128			}
129
130	masse	1.14	/* Push a reference to an entry in the hash table onto the stack. */
131	masse	1.1	int push_ref(stackitem** stack_head, hashtbl in_hash, const char* in_string)
132			{
133	masse	1.6	static void* handle= NULL;
134	masse	1.1	void* symbol;
135	masse	1.6
136	masse	1.1	stackitem* new_item= malloc(sizeof(stackitem));
137			new_item->content.ptr= *hash(in_hash, in_string);
138			new_item->type= ref;
139
140	masse	1.9	if(new_item->content.ptr==NULL) {
141			if(handle==NULL)
142			handle= dlopen(NULL, RTLD_LAZY);
143	masse	1.6
144	masse	1.1	symbol= dlsym(handle, in_string);
145	masse	1.4	if(dlerror()==NULL)
146	masse	1.1	def_func(in_hash, symbol, in_string);
147	masse	1.4	else
148			def_sym(in_hash, in_string);
149
150			new_item->content.ptr= *hash(in_hash, in_string);
151			new_item->type= ref;
152	masse	1.1	}
153
154			push(stack_head, new_item);
155			return 1;
156			}
157
158	masse	1.14	/* Discard the top element of the stack. */
159	masse	1.1	extern void toss(stackitem** stack_head)
160			{
161			stackitem* temp= *stack_head;
162
163	masse	1.7	if((*stack_head)==NULL)
164			return;
165
166			if((*stack_head)->type==string)
167			free((*stack_head)->content.ptr);
168
169	masse	1.1	stack_head= (stack_head)->next;
170			free(temp);
171			}
172
173	masse	1.14	/* Print newline. */
174	masse	1.8	extern void nl()
175			{
176			printf("\n");
177			}
178	masse	1.1
179	masse	1.14	/* Prints the top element of the stack. */
180	masse	1.11	void print_(stackitem** stack_head)
181	masse	1.8	{
182			if((*stack_head)==NULL)
183			return;
184	masse	1.1
185	masse	1.8	switch((*stack_head)->type) {
186	teddy	1.2	case value:
187	masse	1.8	printf("%d", (*stack_head)->content.val);
188	teddy	1.2	break;
189			case string:
190	masse	1.8	printf("%s", (char)(stack_head)->content.ptr);
191	teddy	1.2	break;
192			case ref:
193	masse	1.8	printf("%s", ((stackitem)(stack_head)->content.ptr)->id);
194	masse	1.6	break;
195	masse	1.4	case symbol:
196	masse	1.7	default:
197	masse	1.8	printf("%p", (*stack_head)->content.ptr);
198	teddy	1.2	break;
199			}
200	masse	1.1	}
201
202	masse	1.14	/* Prints the top element of the stack and then discards it. */
203	masse	1.8	extern void print(stackitem** stack_head)
204			{
205	masse	1.11	print_(stack_head);
206	masse	1.8	toss(stack_head);
207			}
208
209	masse	1.14	/* Only to be called by function printstack. */
210	masse	1.8	void print_st(stackitem* stack_head, long counter)
211			{
212			if(stack_head->next != NULL)
213			print_st(stack_head->next, counter+1);
214
215			printf("%ld: ", counter);
216	masse	1.11	print_(&stack_head);
217	masse	1.8	nl();
218			}
219
220	masse	1.14	/* Prints the stack. */
221	masse	1.1	extern void printstack(stackitem** stack_head)
222			{
223			if(*stack_head != NULL) {
224			print_st(*stack_head, 1);
225			printf("\n");
226			}
227			}
228
229	masse	1.14	/* If the top element is a reference, determine if it's a reference to a
230			function, and if it is execute and pop the reference and execute the
231			function. */
232	masse	1.1	extern void eval(stackitem** stack_head)
233			{
234			funcp in_func;
235
236			if((stack_head)==NULL \|\| (stack_head)->type!=ref)
237			return;
238
239			if(((stackitem)(stack_head)->content.ptr)->type==func) {
240			in_func= (funcp)((stackitem)(stack_head)->content.ptr)->content.ptr;
241			toss(stack_head);
242			(*in_func)(stack_head);
243			return;
244			}
245			}
246
247	masse	1.14	/* Parse input. */
248	masse	1.1	int stack_read(stackitem** stack_head, hashtbl in_hash, char* in_line)
249			{
250			char temp, rest;
251			int itemp;
252			size_t inlength= strlen(in_line)+1;
253			int convert= 0;
254
255			temp= malloc(inlength);
256			rest= malloc(inlength);
257
258	masse	1.15	do {
259			if((convert= sscanf(in_line, "\"%[^\"\n\r]\" %[^\n\r]", temp, rest))) {
260			push_cstring(stack_head, temp);
261			break;
262			}
263
264			if((convert= sscanf(in_line, "%d %[^\n\r]", &itemp, rest))) {
265			push_val(stack_head, itemp);
266			break;
267			}
268
269			if((convert= sscanf(in_line, "\\%c%[^\n\r]", temp, rest))) {
270			temp[1]= '\0';
271			push_ref(stack_head, in_hash, temp);
272			break;
273			}
274
275			if((convert= sscanf(in_line, "%[^ ;\n\r]%[^\n\r]", temp, rest))) {
276			push_ref(stack_head, in_hash, temp);
277			break;
278			}
279
280			if((convert= sscanf(in_line, "%c%[^\n\r]", temp, rest)) && *temp==';') {
281	masse	1.1	eval(stack_head);
282	masse	1.15	break;
283			}
284			} while(0);
285
286	masse	1.1
287			free(temp);
288
289			if(convert<2) {
290			free(rest);
291			return 0;
292			}
293
294			stack_read(stack_head, in_hash, rest);
295
296			free(rest);
297			return 1;
298			}
299
300	masse	1.14	/* Make a list. */
301	masse	1.7	extern void pack(stackitem** stack_head)
302			{
303			void* delimiter;
304			stackitem iterator, temp, *pack;
305
306			if((*stack_head)==NULL)
307			return;
308
309			delimiter= (*stack_head)->content.ptr;
310			toss(stack_head);
311
312			iterator= *stack_head;
313
314			while(iterator->next!=NULL && iterator->next->content.ptr!=delimiter)
315			iterator= iterator->next;
316
317			temp= *stack_head;
318			*stack_head= iterator->next;
319			iterator->next= NULL;
320
321			if(stack_head!=NULL && (stack_head)->content.ptr==delimiter)
322			toss(stack_head);
323
324			pack= malloc(sizeof(stackitem));
325			pack->type= list;
326			pack->content.ptr= temp;
327
328			push(stack_head, pack);
329			}
330	masse	1.1
331	masse	1.14	/* Push elements of the list on the stack. */
332	masse	1.8	extern void expand(stackitem** stack_head)
333	masse	1.1	{
334	masse	1.8	stackitem temp, new_head;
335
336			if((stack_head)==NULL \|\| (stack_head)->type!=list)
337			return;
338
339			new_head= temp= (*stack_head)->content.ptr;
340			toss(stack_head);
341
342			while(temp->next!=NULL)
343			temp= temp->next;
344
345			temp->next= *stack_head;
346			*stack_head= new_head;
347	teddy	1.5	}
348
349	masse	1.14	/* Swap the two top elements on the stack. */
350	masse	1.10	extern void swap(stackitem** stack_head)
351			{
352			stackitem* temp= (*stack_head);
353
354			if((stack_head)==NULL \|\| (stack_head)->next==NULL)
355			return;
356
357			stack_head= (stack_head)->next;
358			temp->next= (*stack_head)->next;
359			(*stack_head)->next= temp;
360			}
361	masse	1.11
362	masse	1.14	/* Compares two elements by reference. */
363	masse	1.11	extern void eq(stackitem** stack_head)
364			{
365			void left, right;
366			int result;
367
368			if((stack_head)==NULL \|\| (stack_head)->next==NULL)
369			return;
370
371			left= (*stack_head)->content.ptr;
372	masse	1.12	swap(stack_head);
373			right= (*stack_head)->content.ptr;
374	masse	1.11	result= (left==right);
375
376			toss(stack_head); toss(stack_head);
377			push_val(stack_head, (left==right));
378			}
379
380	masse	1.14	/* Negates the top element on the stack. */
381	masse	1.11	extern void not(stackitem** stack_head)
382			{
383			int value;
384
385			if((*stack_head)==NULL)
386			return;
387
388			value= (*stack_head)->content.val;
389			toss(stack_head);
390			push_val(stack_head, !value);
391			}
392
393	masse	1.14	/* Compares the two top elements on the stack and return 0 if they're the
394			same. */
395	masse	1.11	extern void neq(stackitem** stack_head)
396			{
397			eq(stack_head);
398			not(stack_head);
399			}
400	masse	1.12
401	masse	1.14	/* Give a symbol some content. */
402	masse	1.12	extern void def(stackitem** stack_head)
403			{
404			stackitem temp, value;
405
406			if(stack_head==NULL \|\| (stack_head)->next==NULL
407			\|\| (*stack_head)->type!=ref)
408			return;
409
410			temp= (*stack_head)->content.ptr;
411			value= (*stack_head)->next;
412			temp->content= value->content;
413			value->content.ptr=NULL;
414			temp->type= value->type;
415
416			toss(stack_head); toss(stack_head);
417			}
418	masse	1.10
419	masse	1.14	/* Quit stack. */
420	teddy	1.5	extern void quit()
421			{
422			exit(EXIT_SUCCESS);
423	masse	1.1	}
424
425			int main()
426			{
427			stackitem* s= NULL;
428			hashtbl myhash;
429			char in_string[100];
430
431			init_hashtbl(myhash);
432
433			printf("okidok\n ");
434
435			while(fgets(in_string, 100, stdin) != NULL) {
436			stack_read(&s, myhash, in_string);
437			printf("okidok\n ");
438			}
439
440	masse	1.10	exit(EXIT_SUCCESS);
441	masse	1.1	}
442	teddy	1.3
443			/* Local Variables: */
444			/* compile-command:"make CFLAGS=\"-Wall -g -rdynamic -ldl\" stack" */
445			/* End: */