hash.c

   1
   2 /********************************************
   3 hash.c
   4 copyright 1991, Michael D. Brennan
   5
   6 This is a source file for mawk, an implementation of
   7 the AWK programming language.
   8
   9 Mawk is distributed without warranty under the terms of
  10 the GNU General Public License, version 2, 1991.
  11 ********************************************/
  12
  13
  14 /* $Log: hash.c,v $
  15  * Revision 1.3  1994/10/08  19:15:43  mike
  16  * remove SM_DOS
  17  *
  18  * Revision 1.2  1993/07/16  00:17:35  mike
  19  * cleanup
  20  *
  21  * Revision 1.1.1.1  1993/07/03  18:58:14  mike
  22  * move source to cvs
  23  *
  24  * Revision 5.1  1991/12/05  07:56:05  brennan
  25  * 1.1 pre-release
  26  *
  27 */
  28
  29
  30 /* hash.c */
  31
  32 #include "mawk.h"
  33 #include "memory.h"
  34 #include "symtype.h"
  35
  36
  37 unsigned
  38 hash(s)
  39    register char *s ;
  40 {
  41    register unsigned h = 0 ;
  42
  43    while (*s)  h += h + *s++ ;
  44    return h ;
  45 }
  46
  47 typedef struct hash
  48 {
  49    struct hash *link ;
  50    SYMTAB symtab ;
  51 } HASHNODE ;
  52
  53 static HASHNODE *PROTO(delete, (char *)) ;
  54
  55 static HASHNODE *hash_table[HASH_PRIME] ;
  56
  57 /*
  58 insert a string in the symbol table.
  59 Caller knows the symbol is not there
  60 -- used for initialization
  61 */
  62
  63 SYMTAB *
  64 insert(s)
  65    char *s ;
  66 {
  67    register HASHNODE *p = ZMALLOC(HASHNODE) ;
  68    register unsigned h ;
  69
  70    p->link = hash_table[h = hash(s) % HASH_PRIME] ;
  71    p->symtab.name = s ;
  72    hash_table[h] = p ;
  73    return &p->symtab ;
  74 }
  75
  76 /* Find s in the symbol table,
  77    if not there insert it,  s must be dup'ed  */
  78
  79 SYMTAB *
  80 find(s)
  81    char *s ;
  82 {
  83    register HASHNODE *p ;
  84    HASHNODE *q ;
  85    unsigned h ;
  86
  87    p = hash_table[h = hash(s) % HASH_PRIME] ;
  88    q = (HASHNODE *) 0 ;
  89    while (1)
  90    {
  91       if (!p)
  92       {
  93          p = ZMALLOC(HASHNODE) ;
  94          p->symtab.type = ST_NONE ;
  95          p->symtab.name = strcpy(zmalloc(strlen(s) + 1), s) ;
  96          break ;
  97       }
  98
  99       if (strcmp(p->symtab.name, s) == 0)       /* found */
 100       {
 101          if (!q)                /* already at the front */
 102             return &p->symtab ;
 103          else  /* delete from the list */
 104          {
 105             q->link = p->link ;  break ;
 106          }
 107       }
 108
 109       q = p ; p = p->link ;
 110    }
 111    /* put p on front of the list */
 112    p->link = hash_table[h] ;
 113    hash_table[h] = p ;
 114    return &p->symtab ;
 115 }
 116
 117
 118 /* remove a node from the hash table
 119    return a ptr to the node */
 120
 121 static unsigned last_hash ;
 122
 123 static HASHNODE *
 124 delete(s)
 125    char *s ;
 126 {
 127    register HASHNODE *p ;
 128    HASHNODE *q = (HASHNODE *) 0 ;
 129    unsigned h ;
 130
 131    p = hash_table[last_hash = h = hash(s) % HASH_PRIME] ;
 132    while (p)
 133    {
 134       if (strcmp(p->symtab.name, s) == 0)       /* found */
 135       {
 136          if (q)  q->link = p->link ;
 137          else  hash_table[h] = p->link ;
 138          return p ;
 139       }
 140       else
 141       {
 142          q = p ; p = p->link ;
 143       }
 144    }
 145
 146 #ifdef  DEBUG                   /* we should not ever get here */
 147    bozo("delete") ;
 148 #endif
 149    return (HASHNODE *) 0 ;
 150 }
 151
 152 /* when processing user functions,  global ids which are
 153    replaced by local ids are saved on this list */
 154
 155 static HASHNODE *save_list ;
 156
 157 /* store a global id on the save list,
 158    return a ptr to the local symtab  */
 159 SYMTAB *
 160 save_id(s)
 161    char *s ;
 162 {
 163    HASHNODE *p, *q ;
 164    unsigned h ;
 165
 166    p = delete(s) ;
 167    q = ZMALLOC(HASHNODE) ;
 168    q->symtab.type = ST_LOCAL_NONE ;
 169    q->symtab.name = p->symtab.name ;
 170    /* put q in the hash table */
 171    q->link = hash_table[h = last_hash] ;
 172    hash_table[h] = q ;
 173
 174    /* save p */
 175    p->link = save_list ; save_list = p ;
 176
 177    return &q->symtab ;
 178 }
 179
 180 /* restore all global indentifiers */
 181 void
 182 restore_ids()
 183 {
 184    register HASHNODE *p, *q ;
 185    register unsigned h ;
 186
 187    q = save_list ; save_list = (HASHNODE *) 0 ;
 188    while (q)
 189    {
 190       p = q ; q = q->link ;
 191       zfree(delete(p->symtab.name), sizeof(HASHNODE)) ;
 192       p->link = hash_table[h = last_hash] ;
 193       hash_table[h] = p ;
 194    }
 195 }
 196
 197
 198 /* search the symbol table backwards for the
 199    disassembler.  This is slow -- so what
 200 */
 201
 202
 203 char *
 204 reverse_find(type, ptr)
 205    int type ;
 206    PTR ptr ;
 207 {
 208    CELL *cp ;
 209    ARRAY array ;
 210    static char uk[] = "unknown" ;
 211
 212    int i ;
 213    HASHNODE *p ;
 214
 215
 216    switch (type)
 217    {
 218       case ST_VAR:
 219       case ST_FIELD:
 220          cp = *(CELL **) ptr ;
 221          break ;
 222
 223       case ST_ARRAY:
 224          array = *(ARRAY *) ptr ;
 225          break ;
 226
 227       default:
 228          return uk ;
 229    }
 230
 231    for (i = 0; i < HASH_PRIME; i++)
 232    {
 233       p = hash_table[i] ;
 234       while (p)
 235       {
 236          if (p->symtab.type == type)
 237          {
 238             switch (type)
 239             {
 240                case ST_VAR:
 241                case ST_FIELD:
 242                   if (cp == p->symtab.stval.cp)
 243                      return p->symtab.name ;
 244                   break ;
 245
 246                case ST_ARRAY:
 247                   if (array == p->symtab.stval.array)
 248                      return p->symtab.name ;
 249                   break ;
 250             }
 251          }
 252
 253          p = p->link ;
 254       }
 255    }
 256    return uk ;
 257 }
 258