1/*	$NetBSD: sets.c,v 1.15 2009/03/18 17:06:53 cegger Exp $	*/
2
3/*
4 * This code is such a kludge that I don't want to put my name on it.
5 * It was a ridiculously fast hack and needs rewriting.
6 * However it does work...
7 */
8
9#include <sys/cdefs.h>
10__KERNEL_RCSID(0, "$NetBSD: sets.c,v 1.15 2009/03/18 17:06:53 cegger Exp $");
11
12#include "main.h"
13#include "malloc.h"
14#include "sets.h"
15#include "debug.h"
16#include <stdio.h>
17
18#include <sys/types.h>
19#include <stdlib.h>
20#include <string.h>
21#include <signal.h>
22
23struct Object *CurrentEvent = (struct Object *)0;
24struct Object *Objtree;
25struct Object dummy;
26/*
27 * define a set w/ type and name
28 * return a set number
29 */
30#undef NULL
31#define NULL (struct Object *)0
32
33static FILE *Sfile, *Efile;
34extern FILE *astringfile;
35char *Noname = "Unnamed set\0";
36
37void dumptree();
38void defineitem();
39
40void
41initsets(FILE *f,FILE *s)
42{
43	static char errorstring[20];
44	extern struct Object *SameState;
45	Efile = f;
46	Sfile = s;
47
48	IFDEBUG(X)
49		fprintf(astringfile, "char *%s_sstring[] = {\n", protocol);
50	ENDDEBUG
51	sprintf(errorstring, "%sERROR", ST_PREFIX);
52	defineitem(STATESET, errorstring, (char *)0);	/* state 0 */
53	SameState = (struct Object *) Malloc( sizeof (struct Object) );
54	SameState->obj_kind = OBJ_ITEM;
55	SameState->obj_type = STATESET;
56	SameState->obj_name = "SAME";
57	SameState->obj_struc = (char *)0;
58	SameState->obj_number = 0;
59	SameState->obj_members = (struct Object *)0;
60	SameState->obj_left = (struct Object *)0;
61	SameState->obj_right = (struct Object *)0;
62	SameState->obj_parent = (struct Object *)0;
63}
64
65/*
66 * get a set based on its type and name
67 * returns address of an Object, may be set or item
68 */
69
70struct Object *lookup(type, name)
71unsigned char type;
72char *name;
73{
74	register struct Object *p = Objtree;
75	int val = 1 ;
76
77	IFDEBUG(o)
78		fprintf(stdout,"lookup 0x%x,%s \n",
79			type, name);
80	ENDDEBUG
81
82	while( p && val ) {
83		IFDEBUG(o)
84		fprintf(OUT, "lookup strcmp %p,%s, %p,%s\n",
85			name, name, OBJ_NAME(p), OBJ_NAME(p));
86		ENDDEBUG
87		if( p->obj_name == (char *)0 ) {
88			fprintf(stderr, "Unnamed set in table!\n");
89			Exit(-1);
90		}
91		val =  (int) strcmp(name, OBJ_NAME(p));
92		if(val < 0) {
93			/* left */
94			p = p->obj_left;
95		} else if (val > 0) {
96			/* right */
97			p = p->obj_right;
98		}
99	}
100	if( p && ( p->obj_type != type)) {
101		fprintf(stdout, "lookup(0x%x,%s) found wrong obj type 0x%x\n",
102			type,name, p->obj_type);
103		p = NULL;
104	}
105	IFDEBUG(o)
106		fprintf(stdout,"lookup 0x%x,%s returning %p\n",type, name, p);
107	ENDDEBUG
108	return(p);
109}
110
111static int states_done  = 0;
112
113void
114end_states(FILE *f)
115{
116	register unsigned n = Nstates;
117	register int i;
118	extern char Eventshiftstring[];
119
120	states_done = 1;
121
122	for( i = 0; ;i++) {
123		if( (n >>= 1) <= 0 ) break;
124	}
125	Eventshift = i+1;
126	IFDEBUG(d)
127		fprintf(OUT, "Eventshift=%d\n", Eventshift);
128	ENDDEBUG
129	sprintf(Eventshiftstring, "%d",Eventshift);
130	fprintf(f, "struct %s_event {\n\tint ev_number;\n", &protocol[0]);
131	IFDEBUG(X)
132		/* finish sstring[] & start estring[] */
133		fprintf(astringfile,
134		"};\n\nchar *%s_estring[] = {\n", protocol);
135	ENDDEBUG
136}
137
138int FirstEventAttribute = 1;
139
140static void
141insert(struct Object *o)
142{
143	struct Object *p = Objtree;
144	struct Object **q = &Objtree;
145	int val=1;
146
147
148	if (o->obj_name == (char *)0) {
149		fprintf(stderr, "Internal Error: inserting unnamed object\n");
150		Exit(-1);
151	}
152	if( o->obj_type == STATESET) {
153		if( states_done )  {
154			fprintf(stderr, "No states may be defined after *TRANSITIONS\n");
155			Exit(-1);
156		}
157		o->obj_number =  Nstates++ ;
158		if(Nstates > MAXSTATES) {
159			fprintf(stderr, "Too many states\n");
160			Exit(-1);
161		}
162		fprintf(Sfile, "#define %s 0x%x\n", o->obj_name, o->obj_number);
163		IFDEBUG(X)
164			fprintf(astringfile, "\"%s(0x%x)\",\n", o->obj_name, o->obj_number);
165		ENDDEBUG
166	} else {
167		/* EVENTSET */
168		if( ! states_done )  {
169			fprintf(stderr, "states must precede events\n");
170			Exit(-1);
171		}
172		o->obj_number =  Nevents++ ;
173		if(Nevents > MAXEVENTS) {
174			fprintf(stderr, "Too many events\n");
175			Exit(-1);
176		}
177		if(o->obj_struc)  {
178			if( FirstEventAttribute ) {
179				fprintf(Efile,  "\n\tunion{\n"); /*} */
180				FirstEventAttribute = 0;
181			}
182			fprintf(Efile,
183			"struct %s %s%s;\n\n", o->obj_struc, EV_PREFIX,  o->obj_name);
184		}
185		fprintf(Efile, "#define %s 0x%x\n", o->obj_name, o->obj_number);
186		IFDEBUG(X)
187			fprintf(astringfile, "\"%s(0x%x)\",\n", o->obj_name, o->obj_number);
188		ENDDEBUG
189	}
190	IFDEBUG(o)
191		fprintf(OUT, "insert(%s)\n", OBJ_NAME(o) );
192		if(o->obj_right != NULL) {
193			fprintf(OUT, "insert: unclean Object right\n");
194			exit(1);
195		}
196		if(o->obj_left != NULL) {
197			fprintf(OUT, "insert: unclean Object left\n");
198			exit(1);
199		}
200		fflush(OUT);
201	ENDDEBUG
202
203	while( val ) {
204		if(p == NULL) {
205			*q = o;
206			o->obj_parent = (struct Object *)q;
207			break;
208		}
209		if(!(val = strcmp(o->obj_name, p->obj_name)) ) {
210			/* equal */
211			fprintf(stderr, "re-inserting %s\n",o->obj_name);
212			exit(1);
213		}
214		if(val < 0) {
215			/* left */
216			q = &p->obj_left;
217			p = p->obj_left;
218		} else {
219			/* right */
220			q = &p->obj_right;
221			p = p->obj_right;
222		}
223	}
224	IFDEBUG(a)
225		dumptree(Objtree,0);
226	ENDDEBUG
227}
228
229void
230delete(struct Object *o)
231{
232	register struct Object *p = o->obj_right;
233	register struct Object *q;
234	register struct Object *newparent;
235	register struct Object **np_childlink;
236
237	IFDEBUG(T)
238		fprintf(stdout, "delete(%p)\n", o);
239		dumptree(Objtree,0);
240	ENDDEBUG
241
242	/* q <== lowest valued node of the right subtree */
243	while( p ) {
244		q = p;
245		p = p->obj_left;
246	}
247
248	if (o->obj_parent == (struct Object *)&Objtree)  {
249		newparent =  (struct Object *)&Objtree;
250		np_childlink = (struct Object **)&Objtree;
251	} else if(o->obj_parent->obj_left == o)  {
252		newparent = o->obj_parent;
253		np_childlink = &(o->obj_parent->obj_left);
254	} else {
255		newparent = o->obj_parent;
256		np_childlink = &(o->obj_parent->obj_right);
257	}
258	IFDEBUG(T)
259		fprintf(OUT, "newparent=%p\n", newparent);
260	ENDDEBUG
261
262	if (q) { /* q gets the left, parent gets the right */
263		IFDEBUG(T)
264			fprintf(OUT, "delete: q null\n");
265		ENDDEBUG
266		q->obj_left = p;
267		if(p) p->obj_parent = q;
268		p = o->obj_right;
269	} else { /* parent(instead of q) gets the left ; there is no right  */
270		IFDEBUG(T)
271			fprintf(OUT, "delete: q not null\n");
272		ENDDEBUG
273		p = o->obj_left;
274	}
275	*np_childlink = p;
276	if(p)
277		p->obj_parent = newparent;
278
279	IFDEBUG(T)
280		fprintf(OUT, "After deleting %p\n",o);
281		dumptree(Objtree,0);
282	ENDDEBUG
283}
284
285struct Object *
286defineset(unsigned char type, char *adr, int keep)
287{
288	struct Object *onew;
289	IFDEBUG(o)
290		printf("defineset(0x%x,%s, %s)\n", type , adr, keep?"KEEP":"NO_KEEP");
291	ENDDEBUG
292
293	onew = (struct Object *)Malloc(sizeof (struct Object));
294	memset(onew, 0, sizeof(struct Object));
295	onew->obj_name = adr;
296	onew->obj_kind = OBJ_SET;
297	onew->obj_type = type;
298	if(keep)
299		insert( onew );
300		/* address already stashed before calling defineset */
301	IFDEBUG(o)
302		printf("defineset(0x%x,%s) returning %p\n", type , adr, onew);
303		dumptree(Objtree,0);
304	ENDDEBUG
305	return(onew);
306}
307
308void
309dumpit(char *o, char *s)
310{
311	register unsigned i;
312
313IFDEBUG(o)
314	fprintf(OUT, "object %p, %s\n",o, s);
315	for(i=0; i< sizeof(struct Object); i+=4) {
316		fprintf(OUT, "0x%x: 0x%x 0x%x 0x%x 0x%x\n",
317		*((int *)o), *o, *(o+1), *(o+2), *(o+3) );
318	}
319ENDDEBUG
320}
321
322void
323defineitem(unsigned char type, char *adr, char *struc)
324{
325	struct Object *onew;
326	IFDEBUG(o)
327		printf("defineitem(0x%x, %s at %p, %s)\n", type, adr, adr, struc);
328	ENDDEBUG
329
330	if((onew = lookup( type, adr ))) {
331		fprintf(stderr,
332	"Internal error at defineitem: trying to redefine obj type 0x%x, adr %s\n",
333			type, adr);
334		exit(1);
335	} else {
336		onew = (struct Object *)Malloc(sizeof (struct Object));
337		memset(onew, 0, sizeof(struct Object));
338		onew->obj_name = stash(adr);
339		onew->obj_kind = OBJ_ITEM;
340		onew->obj_type =  type;
341		onew->obj_struc = struc?stash(struc):struc;
342		insert( onew );
343	}
344	IFDEBUG(o)
345		fprintf(OUT, "defineitem(0x%x, %s) returning %p\n", type, adr, onew);
346	ENDDEBUG
347}
348
349void
350member(struct Object *o, char *adr)
351{
352	struct Object *onew, *oold;
353	IFDEBUG(o)
354		printf("member(%p, %s)\n", o, adr);
355	ENDDEBUG
356
357	oold = lookup(  o->obj_type, adr );
358
359	onew = (struct Object *)Malloc(sizeof (struct Object));
360	if( oold == NULL ) {
361		extern int lineno;
362
363		fprintf(stderr,
364		"Warning at line %d: set definition of %s causes definition of\n",
365			lineno, OBJ_NAME(o));
366		fprintf(stderr, "\t (previously undefined) member %s\n", adr);
367		memset(onew, 0, sizeof(struct Object));
368		onew->obj_name = stash(adr);
369		onew->obj_kind = OBJ_ITEM;
370		onew->obj_type = o->obj_type;
371		onew->obj_members = NULL;
372		insert( onew );
373	} else {
374		if(oold->obj_kind != OBJ_ITEM) {
375			fprintf(stderr, "Sets cannot be members of sets; %s\n", adr);
376			exit(1);
377		}
378		memcpy(onew, oold, sizeof(struct Object));
379		onew->obj_members = onew->obj_left = onew->obj_right = NULL;
380	}
381	onew->obj_members = o->obj_members;
382	o->obj_members = onew;
383}
384
385struct Object *Lookup(type, name)
386unsigned char type;
387char *name;
388{
389	register struct Object *o = lookup(type,name);
390
391	if(o == NULL) {
392		fprintf(stderr, "Trying to use undefined %s: %s\n",
393			type==STATESET?"state":"event", name);
394		Exit(-1);
395	}
396	return(o);
397}
398
399void
400AddCurrentEventName(register char **x)
401{
402	register char *n = EV_PREFIX; ;
403
404	if( CurrentEvent == (struct Object *)0 ) {
405		fprintf(stderr, "No event named!  BARF!\n"); Exit(-1);
406	}
407
408	if( ! CurrentEvent->obj_struc ) {
409		fprintf(stderr, "No attributes for current event!\n"); Exit(-1);
410	}
411
412	/* add prefix first */
413	while(*n) {
414		*(*x)++ = *n++;
415	}
416
417	n = CurrentEvent->obj_name;
418
419	while(*n) {
420		*(*x)++ = *n++;
421	}
422}
423
424void
425dumptree(register struct Object *o,int i)
426{
427	register int j;
428
429	if(o == NULL) {
430		for(j=0; j<i; j++)
431			fputc(' ', stdout);
432		fprintf(stdout, "%3d NULL\n", i);
433	} else {
434		dumptree(o->obj_left, i+1);
435		for(j=0; j<i; j++)
436			fputc(' ', stdout);
437		fprintf(stdout, "%3d %p: %s\n", i,o, OBJ_NAME(o));
438		dumptree(o->obj_right, i+1);
439	}
440}
441
442void
443dump(int c,int a)
444{
445	fprintf(stderr, "dump: c 0x%x, a 0x%x\n",c,a);
446
447	raise(SIGFPE);
448	kill(0, SIGQUIT);
449}
450
451void
452dump_trans( pred, oldstate, newstate, action, event )
453	struct Object *oldstate, *newstate, *event;
454	char *pred, *action;
455{
456	extern int transno;
457	struct Object *o;
458
459	fprintf(stdout, "\n%d:  ", transno);
460#define dumpit(x)\
461	if((x)->obj_kind == OBJ_SET) {\
462		o = (x)->obj_members; fprintf( stdout, "[ " );\
463		while(o) { fprintf(stdout, "%s ", o->obj_name); o = o->obj_members; }\
464		fprintf( stdout, " ] ");\
465	} else { fprintf(stdout, "%s ", (x)->obj_name); }
466
467	dumpit(newstate);
468	fprintf(stdout, " <== ");
469	dumpit(oldstate);
470	dumpit(event);
471	fprintf(stdout, "\n\t\t%s\n\t\t%s\n", pred?pred:"DEFAULT",
472		action);
473}
474