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