ltt/branches/poly/misc/parser.c

   1 /*
   2
   3 parser.c: Generate helper declarations and functions to trace events
   4   from an event description file.
   5
   6 Copyright (C) 2002, Xianxiu Yang
   7 Copyright (C) 2002, Michel Dagenais
   8 This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; version 2 of the License.
  11
  12 This program is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  20 */
  21
  22 /* This program reads the ".event" event definitions input files
  23    specified as command line arguments and generates corresponding
  24    ".c" and ".h" files required to trace such events in the kernel.
  25
  26    The program uses a very simple tokenizer, called from a hand written
  27    recursive descent parser to fill a data structure describing the events.
  28    The result is a sequence of events definitions which refer to type
  29    definitions.
  30
  31    A table of named types is maintained to allow refering to types by name
  32    when the same type is used at several places. Finally a sequence of
  33    all types is maintained to facilitate the freeing of all type
  34    information when the processing of an ".event" file is finished. */
  35
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include <stdio.h>
  39 #include <stdarg.h>
  40 #include <linux/errno.h>
  41
  42
  43 #include "parser.h"
  44
  45
  46 /*****************************************************************************
  47  *Function name
  48  *    getSize    : translate from string to integer
  49  *Input params
  50  *    in         : input file handle
  51  *Return values
  52  *    size
  53  *****************************************************************************/
  54 int getSize(parse_file *in){
  55   char *token;
  56
  57   token = getToken(in);
  58   if(in->type == NUMBER) {
  59     if(strcmp(token,"1") == 0) return 0;
  60     else if(strcmp(token,"2") == 0) return 1;
  61     else if(strcmp(token,"4") == 0) return 2;
  62     else if(strcmp(token,"8") == 0) return 3;
  63   }
  64   else if(in->type == NAME) {
  65     if(strcmp(token,"short") == 0) return 4;
  66     else if(strcmp(token,"medium") == 0) return 5;
  67     else if(strcmp(token,"long") == 0) return 6;
  68   }
  69   in->error(in,"incorrect size specification");
  70   return -1;
  71 }
  72
  73 /*****************************************************************************
  74  *Function name
  75  *    error_callback  : print out error info
  76  *Input params
  77  *    in              : input file handle
  78  *    msg             : message to be printed
  79  ****************************************************************************/
  80 void error_callback(parse_file *in, char *msg){
  81   if(in)
  82     printf("Error in file %s, line %d: %s\n", in->name, in->lineno, msg);
  83   else
  84     printf("%s\n",msg);
  85   exit(1);
  86 }
  87
  88 /*****************************************************************************
  89  *Function name
  90  *    memAlloc  : allocate memory
  91  *Input params
  92  *    size      : required memory size
  93  *return value
  94  *    void *    : pointer to allocate memory or NULL
  95  ****************************************************************************/
  96 void * memAlloc(int size){
  97   void *addr = malloc(size);
  98   if(!addr){
  99     printf("Failed to allocate memory");
 100     exit(1);
 101   }
 102   return addr;
 103 }
 104
 105 /*****************************************************************************
 106  *Function name
 107  *    allocAndCopy : allocate memory and initialize it
 108  *Input params
 109  *    str          : string to be put in memory
 110  *return value
 111  *    char *       : pointer to allocate memory or NULL
 112  ****************************************************************************/
 113 char *allocAndCopy(char *str){
 114   char *addr = (char *)memAlloc(strlen(str)+1);
 115   strcpy(addr,str);
 116   return addr;
 117 }
 118
 119
 120 /*****************************************************************************
 121  *Function name
 122  *    parseEvent    : generate event from event definition
 123  *Input params
 124  *    in            : input file handle
 125  *    ev            : new event
 126  *Output params
 127  *    ev            : new event (parameters are passed to it)
 128  ****************************************************************************/
 129 void parseEvent(parse_file *in, event * ev, sequence * unnamed_types, table * named_types) {
 130   char *token;
 131   type_descriptor *t;
 132
 133   getLParenthesis(in);
 134   token = getName(in);
 135   ev->name = allocAndCopy(token);
 136   getComa(in);
 137
 138   token = getQuotedString(in);
 139   ev->description = allocAndCopy(token);
 140
 141   token = getToken(in); //token either is a ',' or a ')'
 142   if(in->type == COMA) token = getName(in);
 143   ungetToken(in);
 144
 145   /* We have a possibly empty list of fields, containing struct implied */
 146   if((in->type == NAME && strcmp(token,"field") == 0) ||
 147       in->type == RPARENTHESIS) {
 148     /* Insert an unnamed struct type */
 149     t = (type_descriptor *)memAlloc(sizeof(type_descriptor));
 150     t->type = STRUCT;
 151     t->fmt = NULL;
 152     if(in->type == NAME) parseFields(in,t, unnamed_types, named_types);
 153     else if(in->type == RPARENTHESIS) sequence_init(&(t->fields));
 154     sequence_push(unnamed_types,t);
 155     ev->type = t;
 156   }
 157
 158   /* Or a complete type declaration but it must be a struct */
 159   else if(in->type == NAME){
 160     ev->type = parseType(in,NULL, unnamed_types, named_types);
 161     if(ev->type->type != STRUCT && ev->type->type != NONE) in->error(in,"type must be a struct");
 162   }else in->error(in,"not a struct type");
 163
 164   getRParenthesis(in);
 165   getSemiColon(in);
 166 }
 167
 168 /*****************************************************************************
 169  *Function name
 170  *    parseField  : get field infomation from buffer
 171  *Input params
 172  *    in          : input file handle
 173  *    t           : type descriptor
 174  ****************************************************************************/
 175 void parseFields(parse_file *in, type_descriptor *t, sequence * unnamed_types, table * named_types) {
 176   char * token;
 177   field *f;
 178
 179   sequence_init(&(t->fields));
 180
 181   token = getToken(in);
 182   while(in->type == NAME && strcmp(token,"field") == 0) {
 183     f = (field *)memAlloc(sizeof(field));
 184     sequence_push(&(t->fields),f);
 185
 186     getLParenthesis(in);
 187     f->name = (char *)allocAndCopy(getName(in));
 188     getComa(in);
 189     f->description = (char *)allocAndCopy(getQuotedString(in));
 190     getComa(in);
 191     f->type = parseType(in,NULL, unnamed_types, named_types);
 192     getRParenthesis(in);
 193
 194     token = getToken(in);
 195     if(in->type == COMA) token = getName(in);
 196     else ungetToken(in); // no more fields, it must be a ')'
 197   }
 198
 199   if(in->type == NAME && strcmp(token,"field") != 0)
 200     in->error(in,"not a field");
 201 }
 202
 203
 204 /*****************************************************************************
 205  *Function name
 206  *    parseType      : get type information, type can be :
 207  *                     Primitive:
 208  *                        int(size,fmt); uint(size,fmt); float(size,fmt);
 209  *                        string(fmt); enum(size,fmt,(label1,label2...))
 210  *                     Compound:
 211  *                        array(arraySize, type); sequence(lengthSize,type)
 212  *                        struct(field(name,type,description)...)
 213  *                     type name:
 214  *                        type(name,type)
 215  *Input params
 216  *    in               : input file handle
 217  *    inType           : a type descriptor
 218  *Return values
 219  *    type_descriptor* : a type descriptor
 220  ****************************************************************************/
 221 type_descriptor *parseType(parse_file *in, type_descriptor *inType, sequence * unnamed_types, table * named_types) {
 222   char *token, *car;
 223   type_descriptor *t;
 224
 225   if(inType == NULL) {
 226     t = (type_descriptor *) memAlloc(sizeof(type_descriptor));
 227     t->type = NONE;
 228     t->fmt = NULL;
 229     sequence_push(unnamed_types,t);
 230   }
 231   else t = inType;
 232
 233   token = getName(in);
 234
 235   if(strcmp(token,"struct") == 0) {
 236     t->type = STRUCT;
 237     getLParenthesis(in);
 238     parseFields(in,t, unnamed_types, named_types);
 239     getRParenthesis(in);
 240   }
 241   else if(strcmp(token,"array") == 0) {
 242     t->type = ARRAY;
 243     getLParenthesis(in);
 244     t->size = getNumber(in);
 245     getComa(in);
 246     t->nested_type = parseType(in,NULL, unnamed_types, named_types);
 247     getRParenthesis(in);
 248   }
 249   else if(strcmp(token,"sequence") == 0) {
 250     t->type = SEQUENCE;
 251     getLParenthesis(in);
 252     t->size = getSize(in);
 253     getComa(in);
 254     t->nested_type = parseType(in,NULL, unnamed_types, named_types);
 255     getRParenthesis(in);
 256   }
 257   else if(strcmp(token,"enum") == 0) {
 258     t->type = ENUM;
 259     sequence_init(&(t->labels));
 260     getLParenthesis(in);
 261     t->size = getSize(in);
 262     getComa(in);
 263     token = getToken(in);
 264     if(in->type == QUOTEDSTRING){
 265       t->fmt = allocAndCopy(token);
 266       getComa(in);
 267     }else ungetToken(in);
 268     getLParenthesis(in);
 269
 270     token = getToken(in);
 271     while(in->type != RPARENTHESIS) {
 272       if(in->type != NAME) in->error(in,"Name token was expected");
 273       car = allocAndCopy(token);
 274       token = getToken(in);
 275       if(in->type == COMA){
 276         sequence_push(&(t->labels),allocAndCopy(car));
 277         token = getName(in);
 278       }else if(in->type == EQUAL){ //label followed by '=' and a number, e.x. label1 = 1,
 279         car = appendString(car, token);
 280         token = getToken(in);
 281         if(in->type != NUMBER) in->error(in,"Number token was expected");
 282         car = appendString(car, token);
 283         sequence_push(&(t->labels),allocAndCopy(car));
 284         token = getToken(in);
 285         if(in->type == COMA) token = getName(in);
 286         else ungetToken(in);
 287       }else{
 288         sequence_push(&(t->labels),allocAndCopy(car));
 289         ungetToken(in);
 290       }
 291     }
 292     getRParenthesis(in);
 293     getRParenthesis(in);
 294   }
 295   else if(strcmp(token,"int") == 0) {
 296     t->type = INT;
 297     getLParenthesis(in);
 298     t->size = getSize(in);
 299     token = getToken(in);
 300     if(in->type == COMA) {
 301       token = getQuotedString(in);
 302       t->fmt = allocAndCopy(token);
 303     }
 304     else ungetToken(in);
 305     getRParenthesis(in);
 306   }
 307   else if(strcmp(token,"uint") == 0) {
 308     t->type = UINT;
 309     getLParenthesis(in);
 310     t->size = getSize(in);
 311     token = getToken(in);
 312     if(in->type == COMA) {
 313       token = getQuotedString(in);
 314       t->fmt = allocAndCopy(token);
 315     }
 316     else ungetToken(in);
 317     getRParenthesis(in);
 318   }
 319   else if(strcmp(token,"float") == 0) {
 320     t->type = FLOAT;
 321     getLParenthesis(in);
 322     t->size = getSize(in);
 323     token = getToken(in);
 324     if(in->type == COMA) {
 325       token = getQuotedString(in);
 326       t->fmt = allocAndCopy(token);
 327     }
 328     else ungetToken(in);
 329     getRParenthesis(in);
 330   }
 331   else if(strcmp(token,"string") == 0) {
 332     t->type = STRING;
 333     getLParenthesis(in);
 334     token = getToken(in);
 335     if(in->type == QUOTEDSTRING) t->fmt = allocAndCopy(token);
 336     else ungetToken(in);
 337     getRParenthesis(in);
 338   }
 339   else {
 340     /* Must be a named type */
 341     if(inType != NULL)
 342       in->error(in,"Named type cannot refer to a named type");
 343     else {
 344       free(t);
 345       sequence_pop(unnamed_types);
 346       return(find_named_type(token, named_types));
 347     }
 348   }
 349
 350   return t;
 351 }
 352
 353 /*****************************************************************************
 354  *Function name
 355  *    find_named_type     : find a named type from hash table
 356  *Input params
 357  *    name                : type name
 358  *Return values
 359  *    type_descriptor *   : a type descriptor
 360  *****************************************************************************/
 361
 362 type_descriptor * find_named_type(char *name, table * named_types)
 363 {
 364   type_descriptor *t;
 365
 366   t = table_find(named_types,name);
 367   if(t == NULL) {
 368     t = (type_descriptor *)memAlloc(sizeof(type_descriptor));
 369     t->type = NONE;
 370     t->fmt = NULL;
 371     table_insert(named_types,allocAndCopy(name),t);
 372   }
 373   return t;
 374 }
 375
 376 /*****************************************************************************
 377  *Function name
 378  *    parseTypeDefinition : get type information from type definition
 379  *Input params
 380  *    in                  : input file handle
 381  *****************************************************************************/
 382 void parseTypeDefinition(parse_file * in, sequence * unnamed_types, table * named_types){
 383   char *token;
 384   type_descriptor *t;
 385
 386   getLParenthesis(in);
 387   token = getName(in);
 388   t = find_named_type(token, named_types);
 389   getComa(in);
 390
 391   if(t->type != NONE) in->error(in,"redefinition of named type");
 392   parseType(in,t, unnamed_types, named_types);
 393
 394   getRParenthesis(in);
 395   getSemiColon(in);
 396 }
 397
 398 /**************************************************************************
 399  * Function :
 400  *    getComa, getName, getNumber, getLParenthesis, getRParenthesis, getEqual
 401  * Description :
 402  *    Read a token from the input file, check its type, return it scontent.
 403  *
 404  * Parameters :
 405  *    in , input file handle.
 406  *
 407  * Return values :
 408  *    address of token content.
 409  *
 410  **************************************************************************/
 411
 412 char *getName(parse_file * in) {
 413   char *token;
 414
 415   token = getToken(in);
 416   if(in->type != NAME) in->error(in,"Name token was expected");
 417   return token;
 418 }
 419
 420 int getNumber(parse_file * in) {
 421   char *token;
 422
 423   token = getToken(in);
 424   if(in->type != NUMBER) in->error(in, "Number token was expected");
 425   return atoi(token);
 426 }
 427
 428 char *getComa(parse_file * in) {
 429   char *token;
 430
 431   token = getToken(in);
 432   if(in->type != COMA) in->error(in, "Coma token was expected");
 433   return token;
 434 }
 435
 436 char *getLParenthesis(parse_file * in) {
 437   char *token;
 438
 439   token = getToken(in);
 440   if(in->type != LPARENTHESIS) in->error(in, "Left parenthesis was expected");
 441   return token;
 442 }
 443
 444 char *getRParenthesis(parse_file * in) {
 445   char *token;
 446
 447   token = getToken(in);
 448   if(in->type != RPARENTHESIS) in->error(in, "Right parenthesis was expected");
 449   return token;
 450 }
 451
 452 char *getQuotedString(parse_file * in) {
 453   char *token;
 454
 455   token = getToken(in);
 456   if(in->type != QUOTEDSTRING) in->error(in, "quoted string was expected");
 457   return token;
 458 }
 459
 460 char * getSemiColon(parse_file *in){
 461   char *token;
 462
 463   token = getToken(in);
 464   if(in->type != SEMICOLON) in->error(in, "semicolon was expected");
 465   return token;
 466 }
 467
 468 char * getEqual(parse_file *in){
 469   char *token;
 470
 471   token = getToken(in);
 472   if(in->type != EQUAL) in->error(in, "equal was expected");
 473   return token;
 474 }
 475
 476 /******************************************************************
 477  * Function :
 478  *    getToken, ungetToken
 479  * Description :
 480  *    Read a token from the input file and return its type and content.
 481  *    Line numbers are accounted for and whitespace/comments are skipped.
 482  *
 483  * Parameters :
 484  *    in, input file handle.
 485  *
 486  * Return values :
 487  *    address of token content.
 488  *
 489  ******************************************************************/
 490
 491 void ungetToken(parse_file * in)
 492 {
 493   in->unget = 1;
 494 }
 495
 496 char *getToken(parse_file * in)
 497 {
 498   FILE *fp = in->fp;
 499   char car, car1;
 500   int pos = 0, escaped;
 501
 502   if(in->unget == 1) {
 503     in->unget = 0;
 504     return in->buffer;
 505   }
 506
 507   /* skip whitespace and comments */
 508
 509   while((car = getc(fp)) != EOF) {
 510     if(car == '/') {
 511       car1 = getc(fp);
 512       if(car1 == '*') skipComment(in);
 513       else if(car1 == '/') skipEOL(in);
 514       else {
 515         car1 = ungetc(car1,fp);
 516         break;
 517       }
 518     }
 519     else if(car == '\n') in->lineno++;
 520     else if(!isspace(car)) break;
 521   }
 522
 523   switch(car) {
 524     case EOF:
 525       in->type = ENDFILE;
 526       break;
 527     case ',':
 528       in->type = COMA;
 529       in->buffer[pos] = car;
 530       pos++;
 531       break;
 532     case '(':
 533       in->type = LPARENTHESIS;
 534       in->buffer[pos] = car;
 535       pos++;
 536       break;
 537     case ')':
 538       in->type = RPARENTHESIS;
 539       in->buffer[pos] = car;
 540       pos++;
 541       break;
 542     case ';':
 543       in->type = SEMICOLON;
 544       in->buffer[pos] = car;
 545       pos++;
 546       break;
 547     case '=':
 548       in->type = EQUAL;
 549       in->buffer[pos] = car;
 550       pos++;
 551       break;
 552     case '"':
 553       escaped = 0;
 554       while((car = getc(fp)) != EOF && pos < BUFFER_SIZE) {
 555         if(car == '\\' && escaped == 0) {
 556           in->buffer[pos] = car;
 557           pos++;
 558           escaped = 1;
 559           continue;
 560         }
 561         if(car == '"' && escaped == 0) break;
 562         if(car == '\n' && escaped == 0) {
 563           in->error(in, "non escaped newline inside quoted string");
 564         }
 565         if(car == '\n') in->lineno++;
 566         in->buffer[pos] = car;
 567         pos++;
 568         escaped = 0;
 569       }
 570       if(car == EOF) in->error(in,"no ending quotemark");
 571       if(pos == BUFFER_SIZE) in->error(in, "quoted string token too large");
 572       in->type = QUOTEDSTRING;
 573       break;
 574     default:
 575       if(isdigit(car)) {
 576         in->buffer[pos] = car;
 577         pos++;
 578         while((car = getc(fp)) != EOF && pos < BUFFER_SIZE) {
 579           if(!isdigit(car)) {
 580             ungetc(car,fp);
 581             break;
 582           }
 583           in->buffer[pos] = car;
 584           pos++;
 585         }
 586         if(car == EOF) ungetc(car,fp);
 587         if(pos == BUFFER_SIZE) in->error(in, "number token too large");
 588         in->type = NUMBER;
 589       }
 590       else if(isalpha(car)) {
 591         in->buffer[0] = car;
 592         pos = 1;
 593         while((car = getc(fp)) != EOF && pos < BUFFER_SIZE) {
 594           if(!isalnum(car)) {
 595             ungetc(car,fp);
 596             break;
 597           }
 598           in->buffer[pos] = car;
 599           pos++;
 600         }
 601         if(car == EOF) ungetc(car,fp);
 602         if(pos == BUFFER_SIZE) in->error(in, "name token too large");
 603         in->type = NAME;
 604       }
 605       else in->error(in, "invalid character, unrecognized token");
 606   }
 607   in->buffer[pos] = 0;
 608   return in->buffer;
 609 }
 610
 611 void skipComment(parse_file * in)
 612 {
 613   char car;
 614   while((car = getc(in->fp)) != EOF) {
 615     if(car == '\n') in->lineno++;
 616     else if(car == '*') {
 617       car = getc(in->fp);
 618       if(car ==EOF) break;
 619       if(car == '/') return;
 620       ungetc(car,in->fp);
 621     }
 622   }
 623   if(car == EOF) in->error(in,"comment begining with '/*' has no ending '*/'");
 624 }
 625
 626 void skipEOL(parse_file * in)
 627 {
 628   char car;
 629   while((car = getc(in->fp)) != EOF) {
 630     if(car == '\n') {
 631       ungetc(car,in->fp);
 632       break;
 633     }
 634   }
 635   if(car == EOF)ungetc(car, in->fp);
 636 }
 637
 638 int isalpha(char c){
 639   int i,j;
 640   if(c == '_')return 1;
 641   i = c - 'a';
 642   j = c - 'A';
 643   if((i>=0 && i<26) || (j>=0 && j<26)) return 1;
 644   return 0;
 645 }
 646
 647 int isalnum(char c){
 648   return (isalpha(c) || isdigit(c));
 649 }
 650
 651 /*****************************************************************************
 652  *Function name
 653  *    checkNamedTypesImplemented : check if all named types have definition
 654  ****************************************************************************/
 655 void checkNamedTypesImplemented(table * named_types){
 656   type_descriptor *t;
 657   int pos;
 658   char str[256];
 659
 660   for(pos = 0 ; pos < named_types->values.position; pos++) {
 661     t = (type_descriptor *) named_types->values.array[pos];
 662     if(t->type == NONE){
 663       sprintf(str,"named type '%s' has no definition",(char*)named_types->keys.array[pos]);
 664       error_callback(NULL,str);
 665     }
 666   }
 667 }
 668
 669
 670 /*****************************************************************************
 671  *Function name
 672  *    generateChecksum  : generate checksum for the facility
 673  *Input Params
 674  *    facName           : name of facility
 675  *Output Params
 676  *    checksum          : checksum for the facility
 677  ****************************************************************************/
 678 void generateChecksum( char* facName, unsigned long * checksum, sequence * events){
 679   unsigned long crc ;
 680   int pos, nestedStruct;
 681   event * ev;
 682   char str[256];
 683
 684   crc = crc32(facName);
 685   for(pos = 0; pos < events->position; pos++){
 686     ev = (event *)(events->array[pos]);
 687     ev->nested = 0; //by default, event has no nested struct
 688     crc = partial_crc32(ev->name,crc);
 689     nestedStruct = 0;
 690     if(ev->type->type != STRUCT){
 691       sprintf(str,"event '%s' has a type other than STRUCT",ev->name);
 692       error_callback(NULL, str);
 693     }
 694     crc = getTypeChecksum(crc, ev->type,&nestedStruct);
 695     if(nestedStruct ) ev->nested = 1;
 696   }
 697   *checksum = crc;
 698 }
 699
 700 /*****************************************************************************
 701  *Function name
 702  *   getTypeChecksum    : generate checksum by type info
 703  *Input Params
 704  *    crc               : checksum generated so far
 705  *    type              : type descriptor containing type info
 706  *Return value
 707  *    unsigned long     : checksum
 708  *****************************************************************************/
 709 unsigned long getTypeChecksum(unsigned long aCrc, type_descriptor * type, int * nestedStruct){
 710   unsigned long crc = aCrc;
 711   char * str = NULL, buf[16];
 712   int flag = 0, pos, max, min;
 713   field * fld;
 714   data_type dt;
 715
 716   switch(type->type){
 717     case INT:
 718       str = intOutputTypes[type->size];
 719       break;
 720     case UINT:
 721       str = uintOutputTypes[type->size];
 722       break;
 723     case FLOAT:
 724       str = floatOutputTypes[type->size];
 725       break;
 726     case STRING:
 727       str = allocAndCopy("string");
 728       flag = 1;
 729       break;
 730     case ENUM:
 731       str = appendString("enum ", uintOutputTypes[type->size]);
 732       flag = 1;
 733       break;
 734     case ARRAY:
 735       sprintf(buf,"%d\0",type->size);
 736       str = appendString("array ",buf);
 737       flag = 1;
 738       break;
 739     case SEQUENCE:
 740       sprintf(buf,"%d\0",type->size);
 741       str = appendString("sequence ",buf);
 742       flag = 1;
 743       break;
 744     case STRUCT:
 745       str = allocAndCopy("struct");
 746       flag = 1;
 747       break;
 748     default:
 749       error_callback(NULL, "named type has no definition");
 750       break;
 751   }
 752
 753   crc = partial_crc32(str,crc);
 754   if(flag) free(str);
 755
 756   if(type->fmt) crc = partial_crc32(type->fmt,crc);
 757
 758   if(type->type == ARRAY || type->type == SEQUENCE){
 759     dt = type->nested_type->type;
 760     if(dt == ARRAY || dt == SEQUENCE || dt == STRUCT) *nestedStruct += 1;
 761     crc = getTypeChecksum(crc,type->nested_type,nestedStruct);
 762   }else if(type->type == STRUCT){
 763     if(type->fields.position != 0){//not a empty struct
 764       max = 0;
 765       for(pos =0; pos < type->fields.position; pos++){
 766         min = 0;
 767         fld = (field *) type->fields.array[pos];
 768         crc = partial_crc32(fld->name,crc);
 769         if(fld->type->type == STRUCT) min++;
 770         crc = getTypeChecksum(crc, fld->type,&min);
 771         if(min>max) max = min;
 772       }
 773       *nestedStruct += max;
 774     }
 775   }else if(type->type == ENUM){
 776     for(pos = 0; pos < type->labels.position; pos++)
 777       crc = partial_crc32((char*)type->labels.array[pos],crc);
 778   }
 779
 780   return crc;
 781 }
 782
 783
 784 /* Event type descriptors */
 785 void freeType(type_descriptor * tp){
 786   int pos2;
 787   field *f;
 788
 789   if(tp->fmt != NULL) free(tp->fmt);
 790   if(tp->type == ENUM) {
 791     for(pos2 = 0; pos2 < tp->labels.position; pos2++) {
 792       free(tp->labels.array[pos2]);
 793     }
 794     sequence_dispose(&(tp->labels));
 795   }
 796   if(tp->type == STRUCT) {
 797     for(pos2 = 0; pos2 < tp->fields.position; pos2++) {
 798       f = (field *) tp->fields.array[pos2];
 799       free(f->name);
 800       free(f->description);
 801       free(f);
 802     }
 803     sequence_dispose(&(tp->fields));
 804   }
 805 }
 806
 807 void freeNamedType(table * t){
 808   int pos;
 809   type_descriptor * td;
 810
 811   for(pos = 0 ; pos < t->keys.position; pos++) {
 812     free((char *)t->keys.array[pos]);
 813     td = (type_descriptor*)t->values.array[pos];
 814     freeType(td);
 815     free(td);
 816   }
 817 }
 818
 819 void freeTypes(sequence *t) {
 820   int pos, pos2;
 821   type_descriptor *tp;
 822   field *f;
 823
 824   for(pos = 0 ; pos < t->position; pos++) {
 825     tp = (type_descriptor *)t->array[pos];
 826     freeType(tp);
 827     free(tp);
 828   }
 829 }
 830
 831 void freeEvents(sequence *t) {
 832   int pos;
 833   event *ev;
 834
 835   for(pos = 0 ; pos < t->position; pos++) {
 836     ev = (event *) t->array[pos];
 837     free(ev->name);
 838     free(ev->description);
 839     free(ev);
 840   }
 841
 842 }
 843
 844
 845 /* Extensible array */
 846
 847 void sequence_init(sequence *t) {
 848   t->size = 10;
 849   t->position = 0;
 850   t->array = (void **)memAlloc(t->size * sizeof(void *));
 851 }
 852
 853 void sequence_dispose(sequence *t) {
 854   t->size = 0;
 855   free(t->array);
 856   t->array = NULL;
 857 }
 858
 859 void sequence_push(sequence *t, void *elem) {
 860   void **tmp;
 861
 862   if(t->position >= t->size) {
 863     tmp = t->array;
 864     t->array = (void **)memAlloc(t->size * 2 * sizeof(void *));
 865     memcpy(t->array, tmp, t->size * sizeof(void *));
 866     t->size = t->size * 2;
 867     free(tmp);
 868   }
 869   t->array[t->position] = elem;
 870   t->position++;
 871 }
 872
 873 void *sequence_pop(sequence *t) {
 874   return t->array[t->position--];
 875 }
 876
 877
 878 /* Hash table API, implementation is just linear search for now */
 879
 880 void table_init(table *t) {
 881   sequence_init(&(t->keys));
 882   sequence_init(&(t->values));
 883 }
 884
 885 void table_dispose(table *t) {
 886   sequence_dispose(&(t->keys));
 887   sequence_dispose(&(t->values));
 888 }
 889
 890 void table_insert(table *t, char *key, void *value) {
 891   sequence_push(&(t->keys),key);
 892   sequence_push(&(t->values),value);
 893 }
 894
 895 void *table_find(table *t, char *key) {
 896   int pos;
 897   for(pos = 0 ; pos < t->keys.position; pos++) {
 898     if(strcmp((char *)key,(char *)t->keys.array[pos]) == 0)
 899       return(t->values.array[pos]);
 900   }
 901   return NULL;
 902 }
 903
 904
 905 /* Concatenate strings */
 906
 907 char *appendString(char *s, char *suffix) {
 908   char *tmp;
 909
 910   tmp = (char *)memAlloc(strlen(s) + strlen(suffix) + 1);
 911   strcpy(tmp,s);
 912   strcat(tmp,suffix);
 913   return tmp;
 914 }
 915
 916