void* st_insert (SYMTAB *tab, const char *name, int type,                 unsigned size){                               /* --- insert a symbol */  unsigned h;                   /* hash value */  int i;                        /* index of hash bucket */  STE *ste;                     /* to traverse bucket list */  STE *nel;                     /* new symbol table element */  assert(tab && name            /* check the function arguments */      && ((size >= sizeof(int)) || (tab->vsz == INT_MAX)));  if ((tab->cnt /4 > tab->size) /* if buckets are rather full and */  &&  (tab->size   < tab->max)) /* table does not have maximal size, */    _reorg(tab);                /* reorganize the hash table */  h   = tab->hash(name, type);  /* compute the hash value and */  i   = h % tab->size;          /* the index of the hash bucket */  ste = tab->bvec[i];           /* get first element in bucket */  while (ste) {                 /* traverse the bucket list */    if ((type == ste->type)     /* if symbol found */    &&  (strcmp(name, ste->name) == 0))      break;                    /* abort the loop */    ste = ste->succ;            /* otherwise get the successor */  }                             /* element in the hash bucket */  if (ste                       /* if symbol found on current level */  && (ste->level == tab->level))    return EXISTS;              /* return 'symbol exists' */  #ifdef NIMAPFN                /* if name/identifier map management */  if (tab->cnt >= tab->vsz) {   /* if the identifier vector is full */    int vsz, **tmp;             /* (new) id vector and its size */    vsz = tab->vsz +((tab->vsz > BLKSIZE) ? tab->vsz >> 1 : BLKSIZE);    tmp = (int**)realloc(tab->ids, vsz *sizeof(int*));    if (!tmp) return NULL;      /* resize the identifier vector and */    tab->ids = tmp; tab->vsz = vsz;  /* set new vector and its size */  }                             /* (no resizing for symbol tables */  #endif                        /* since then tab->vsz = MAX_INT) */  nel = (STE*)malloc(sizeof(STE) +size +strlen(name) +1);  if (!nel) return NULL;        /* allocate memory for new symbol */  nel->name    = (char*)(nel+1) +size;         /* and organize it */  strcpy(nel->name, name);      /* note the symbol name, */  nel->type    = type;          /* the symbol type, and the */  nel->level   = tab->level;    /* current visibility level */  nel->succ    = tab->bvec[i];  /* insert new symbol at the head */  tab->bvec[i] = nel++;         /* of the bucket list */  #ifdef NIMAPFN                /* if name/identifier maps are */  if (tab->ids) {               /* supported and this is such a map */    tab->ids[tab->cnt] = (int*)nel;    *(int*)nel = tab->cnt;      /* store the new symbol */  }                             /* in the identifier vector */  #endif                        /* and set the symbol identifier */  tab->cnt++;                   /* increment the symbol counter */  return nel;                   /* return pointer to data field */}  /* st_insert() *//*--------------------------------------------------------------------*/int st_remove (SYMTAB *tab, const char *name, int type){                               /* --- remove a symbol/all symbols */  int i;                        /* index of hash bucket */  STE **p, *ste;                /* to traverse bucket list */  assert(tab);                  /* check for a valid symbol table */  /* --- remove all symbols --- */  if (!name) {                  /* if no symbol name given */    _delsym(tab);               /* delete all symbols */    tab->cnt = tab->level = 0;  /* reset visibility level */    return 0;                   /* and symbol counter */  }                             /* and return 'ok' */  /* --- remove one symbol --- */  i = tab->hash(name, type) % tab->size;  p = tab->bvec +i;             /* compute index of hash bucket */  while (*p) {                  /* and traverse bucket list */    if (((*p)->type == type)    /* if symbol found */    &&  (strcmp(name, (*p)->name) == 0))      break;                    /* abort loop */    p = &(*p)->succ;            /* otherwise get successor */  }                             /* in hash bucket */  ste = *p;                     /* if the symbol does not exist, */  if (!ste) return -1;          /* abort the function */  *p = ste->succ;               /* remove symbol from hash bucket */  if (tab->delfn) tab->delfn(ste +1);   /* delete user data */  free(ste);                    /* and symbol table element */  tab->cnt--;                   /* decrement symbol counter */  return 0;                     /* return 'ok' */}  /* st_remove() *//*--------------------------------------------------------------------*/void* st_lookup (SYMTAB *tab, const char *name, int type){                               /* --- look up a symbol */  int i;                        /* index of hash bucket */  STE *ste;                     /* to traverse bucket list */  assert(tab && name);          /* check arguments */  i   = tab->hash(name, type) % tab->size;  ste = tab->bvec[i];           /* compute index of hash bucket */  while (ste) {                 /* and traverse bucket list */    if ((ste->type == type)     /* if symbol found */    &&  (strcmp(name, ste->name) == 0))      return ste +1;            /* return pointer to assoc. data */    ste = ste->succ;            /* otherwise get successor */  }                             /* in hash bucket */  return NULL;                  /* return 'not found' */}  /* st_lookup() *//*--------------------------------------------------------------------*/void st_endblk (SYMTAB *tab){                               /* --- remove one visibility level */  int i;                        /* loop variable */  STE *ste, *tmp;               /* to traverse bucket lists */  assert(tab);                  /* check for a valid symbol table */  if (tab->level <= 0) return;  /* if on level 0, abort */  for (i = tab->size; --i >= 0; ) {  /* traverse bucket vector */    ste = tab->bvec[i];         /* get next bucket list */    while (ste                  /* and remove all symbols */    &&    (ste->level >= tab->level)) {  /* of higher level */      tmp = ste;                /* note symbol and */      ste = ste->succ;          /* get successor */      if (tab->delfn) tab->delfn(tmp +1);      free(tmp);                /* delete user data and */      tab->cnt--;               /* symbol table element */    }                           /* and decrement symbol counter */    tab->bvec[i] = ste;         /* set new start of bucket list */  }  tab->level--;                 /* go up one level */}  /* st_endblk() *//*--------------------------------------------------------------------*/#ifndef NDEBUGvoid st_stats (const SYMTAB *tab){                               /* --- compute and print statistics */  const STE *ste;               /* to traverse bucket lists */  int i;                        /* loop variable */  int used;                     /* number of used hash buckets */  int len;                      /* length of current bucket list */  int min, max;                 /* min. and max. bucket list length */  int cnts[10];                 /* counter for bucket list lengths */  assert(tab);                  /* check for a valid symbol table */  min = INT_MAX; max = used = 0;/* initialize variables */  for (i = 10; --i >= 0; ) cnts[i] = 0;  for (i = tab->size; --i >= 0; ) { /* traverse bucket vector */    len = 0;                    /* determine bucket list length */    for (ste = tab->bvec[i]; ste; ste = ste->succ) len++;    if (len > 0) used++;        /* count used hash buckets */    if (len < min) min = len;   /* determine minimal and */    if (len > max) max = len;   /* maximal list length */    cnts[(len >= 9) ? 9 : len]++;  }                             /* count list length */  printf("number of symbols     : %d\n", tab->cnt);  printf("number of hash buckets: %d\n", tab->size);  printf("used hash buckets     : %d\n", used);  printf("minimal list length   : %d\n", min);  printf("maximal list length   : %d\n", max);  printf("average list length   : %g\n", (double)tab->cnt/tab->size);  printf("ditto, of used buckets: %g\n", (double)tab->cnt/used);  printf("length distribution   :\n");  for (i = 0; i < 9; i++) printf("%3d ", i);  printf(" >8\n");  for (i = 0; i < 9; i++) printf("%3d ", cnts[i]);  printf("%3d\n", cnts[9]);}  /* st_stats() */#endif/*----------------------------------------------------------------------  Name/Identifier Map Functions----------------------------------------------------------------------*/#ifdef NIMAPFNNIMAP* nim_create (int init, int max, HASHFN hash, SYMFN delfn){                               /* --- create a name/identifier map */  NIMAP *nim;                   /* created name/identifier map */  nim = st_create(init, max, hash, delfn);  if (!nim) return NULL;        /* create a name/identifier map */  nim->vsz = 0;                 /* and clear the id. vector size */  return nim;                   /* return created name/id map */}  /* nim_create() *//*--------------------------------------------------------------------*/void nim_sort (NIMAP *nim, SYMCMPFN cmpfn, void *data,               int *map, int dir){                               /* --- sort name/identifier map */  int i;                        /* loop variable */  int **p;                      /* to traverse the value vector */  assert(nim && cmpfn);         /* check the function arguments */  v_sort(nim->ids, nim->cnt, cmpfn, data);  if (!map) {                   /* if no conversion map is requested */    for (p = nim->ids +(i = nim->cnt); --i >= 0; )      **--p = i; }              /* just set new identifiers */  else {                        /* if a conversion map is requested, */    p = nim->ids +(i = nim->cnt);      /* traverse the sorted vector */    if (dir < 0)                /* if backward map (i.e. new -> old) */      while (--i >= 0) { map[i] = **--p; **p = i; }    else                        /* if forward  map (i.e. old -> new) */      while (--i >= 0) { map[**--p] = i; **p = i; }  }                             /* (build conversion map) */}  /* nim_sort() *//*--------------------------------------------------------------------*/void nim_trunc (NIMAP *nim, int n){                               /* --- truncate name/identifier map */  int *id;                      /* to access the identifiers */  while (nim->cnt > n) {        /* while to remove mappings */    id = nim->ids[nim->cnt -1]; /* get the identifier object */    st_remove(nim, st_name(id), 0);  }                             /* remove the symbol table element */}  /* nim_trunc() */#endif