util/led/sym.c

   1 /*
   2  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   3  * See the copyright notice in the ACK home directory, in the file "Copyright".
   4  */
   5 #ifndef lint
   6 static char rcsid[] = "$Id: sym.c,v 3.4 1994/06/24 10:35:23 ceriel Exp $";
   7 #endif
   8
   9 /*
  10  * Symbol table management.
  11  */
  12
  13 #include <out.h>
  14 #include "const.h"
  15 #include "memory.h"
  16 #include "debug.h"
  17
  18 /*
  19  * Symbol table types. Each hash table entry contains the offset of a symbol
  20  * struct. `Sy_name' contains the offset the name in the piece of global
  21  * names. `Sy_next' contains the offset of the next symbol of which the
  22  * corresponding name has the same hash value.
  23  */
  24 struct symbol {
  25         ind_t   sy_name;
  26         ind_t   sy_next;
  27 };
  28
  29 #define NHASH   307             /* Size of hash table. Must be odd. */
  30
  31 static ind_t    hashtable[NHASH];
  32
  33 /*
  34  * Initialize the symbol table. All indices should be noticeably invalid.
  35  */
  36 init_symboltable()
  37 {
  38         register ind_t  *rap;
  39
  40         for (rap = hashtable; rap < &hashtable[NHASH]; rap++)
  41                 *rap = BADOFF;
  42 }
  43
  44 /*
  45  * Search for `string' in the symboltable. The hash value of `string' is in
  46  * `hashval'. The linked list belonging to the entry of hashval
  47  * in the hash table is followed. If the names match, a pointer to the outname
  48  * in this element of the list is returned. When a match cannot be found,
  49  * NIL is returned.
  50  */
  51 struct outname *
  52 searchname(string, hashval)
  53         char                    *string;
  54         int                     hashval;
  55 {
  56         register char           *rcp;
  57         register char           *namestring;
  58         register ind_t          symindex;
  59         register struct outname *name;
  60         register struct symbol  *sym;
  61
  62         symindex = hashtable[hashval];
  63         debug("looking for %s %d %ld:", string, hashval, hashtable[hashval], 0);
  64         while (symindex != BADOFF) {
  65                 sym = (struct symbol *)address(ALLOSYMB, symindex);
  66                 name = (struct outname *)address(ALLOGLOB, sym->sy_name);
  67                 namestring = address(ALLOGCHR, (ind_t)name->on_foff);
  68                 rcp = string;
  69                 debug("comp %s;", namestring, 0, 0, 0);
  70                 while (*rcp == *namestring++)
  71                         if (*rcp++ == '\0') {
  72                                 debug("found %x, %x, %lx\n",
  73                                         name->on_type, name->on_desc, name->on_valu, 0);
  74                                 return name;
  75                         }
  76                 symindex = sym->sy_next;
  77         }
  78         /* Not found. */
  79         debug("not found\n", 0, 0, 0, 0);
  80         return (struct outname *)0;
  81 }
  82
  83 /*
  84  * Enter a new name in the symbol table. We must copy everything to a
  85  * new entry. `Name' is a private copy, i.e. the pointer to it will not be
  86  * destroyed by allocation. However, the string of which name->on_foff is the
  87  * offset can be destroyed, so we save it first.
  88  */
  89 entername(name, hashval)
  90         struct outname  *name;
  91         int             hashval;
  92 {
  93         ind_t           savindex;
  94         ind_t           symindex;
  95         ind_t           namindex;
  96         register struct symbol  *sym;
  97         struct outname  *newname;
  98         extern ind_t    savechar();
  99         extern ind_t    hard_alloc();
 100
 101         debug("entername %s %d %x %x", modulptr((ind_t)name->on_foff), hashval, name->on_type, name->on_desc);
 102         savindex = savechar(ALLOGCHR, (ind_t)name->on_foff);
 103         symindex = hard_alloc(ALLOSYMB, (long)sizeof(struct symbol));
 104         debug("; %ld\n", symindex, 0, 0, 0);
 105         namindex = hard_alloc(ALLOGLOB, (long)sizeof(struct outname));
 106         if (savindex == BADOFF || symindex == BADOFF || namindex == BADOFF)
 107                 fatal("symbol table overflow");
 108         sym = (struct symbol *)address(ALLOSYMB, symindex);
 109         sym->sy_name = namindex;
 110         newname = (struct outname *)address(ALLOGLOB, namindex);
 111         *newname = *name;
 112         newname->on_foff = savindex;
 113         sym->sy_next = hashtable[hashval];
 114         hashtable[hashval] = symindex;
 115 }
 116
 117 /*
 118  * Return the index of `name' in the symbol table in the order in which
 119  * it was entered. We need a REAL index, not a byte offset.
 120  */
 121 unsigned
 122 indexof(name)
 123         struct outname  *name;
 124 {
 125         return name - (struct outname *)address(ALLOGLOB, (ind_t)0);
 126 }
 127
 128 /*
 129  * Assign an integer to the string in p.
 130  * 0 <= hash(p) < NHASH, so it can - and will - be used
 131  * as index in a hash table.
 132  */
 133 int
 134 hash(p)
 135         register char           *p;
 136 {
 137         register unsigned short h = 0;
 138         register int            c;
 139
 140         while (c = *p++) {
 141                 h <<= 2;
 142                 h += c;
 143         }
 144         return h % NHASH;
 145 }