1 /* $OpenBSD: sym.c,v 1.9 2015/11/19 23:34:56 mmcc Exp $ */ 2 3 /* sym - symbol table routines */ 4 5 /* Copyright (c) 1990 The Regents of the University of California. */ 6 /* All rights reserved. */ 7 8 /* This code is derived from software contributed to Berkeley by */ 9 /* Vern Paxson. */ 10 11 /* The United States Government has rights in this work pursuant */ 12 /* to contract no. DE-AC03-76SF00098 between the United States */ 13 /* Department of Energy and the University of California. */ 14 15 /* This file is part of flex. */ 16 17 /* Redistribution and use in source and binary forms, with or without */ 18 /* modification, are permitted provided that the following conditions */ 19 /* are met: */ 20 21 /* 1. Redistributions of source code must retain the above copyright */ 22 /* notice, this list of conditions and the following disclaimer. */ 23 /* 2. Redistributions in binary form must reproduce the above copyright */ 24 /* notice, this list of conditions and the following disclaimer in the */ 25 /* documentation and/or other materials provided with the distribution. */ 26 27 /* Neither the name of the University nor the names of its contributors */ 28 /* may be used to endorse or promote products derived from this software */ 29 /* without specific prior written permission. */ 30 31 /* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 32 /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 33 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 34 /* PURPOSE. */ 35 36 #include "flexdef.h" 37 38 /* Variables for symbol tables: 39 * sctbl - start-condition symbol table 40 * ndtbl - name-definition symbol table 41 * ccltab - character class text symbol table 42 */ 43 44 struct hash_entry { 45 struct hash_entry *prev, *next; 46 char *name; 47 char *str_val; 48 int int_val; 49 }; 50 51 typedef struct hash_entry **hash_table; 52 53 #define NAME_TABLE_HASH_SIZE 101 54 #define START_COND_HASH_SIZE 101 55 #define CCL_HASH_SIZE 101 56 57 static struct hash_entry *ndtbl[NAME_TABLE_HASH_SIZE]; 58 static struct hash_entry *sctbl[START_COND_HASH_SIZE]; 59 static struct hash_entry *ccltab[CCL_HASH_SIZE]; 60 61 62 /* declare functions that have forward references */ 63 64 static int addsym PROTO ((char[], char *, int, hash_table, int)); 65 static struct hash_entry *findsym PROTO ((const char *sym, 66 hash_table table, 67 68 int table_size)); 69 static int hashfunct PROTO ((const char *, int)); 70 71 72 /* addsym - add symbol and definitions to symbol table 73 * 74 * -1 is returned if the symbol already exists, and the change not made. 75 */ 76 77 static int addsym (sym, str_def, int_def, table, table_size) 78 char sym[]; 79 char *str_def; 80 int int_def; 81 hash_table table; 82 int table_size; 83 { 84 int hash_val = hashfunct (sym, table_size); 85 struct hash_entry *sym_entry = table[hash_val]; 86 struct hash_entry *new_entry; 87 struct hash_entry *successor; 88 89 while (sym_entry) { 90 if (!strcmp (sym, sym_entry->name)) { /* entry already exists */ 91 return -1; 92 } 93 94 sym_entry = sym_entry->next; 95 } 96 97 /* create new entry */ 98 new_entry = (struct hash_entry *) 99 malloc (sizeof (struct hash_entry)); 100 101 if (new_entry == NULL) 102 flexfatal (_("symbol table memory allocation failed")); 103 104 if ((successor = table[hash_val]) != 0) { 105 new_entry->next = successor; 106 successor->prev = new_entry; 107 } 108 else 109 new_entry->next = NULL; 110 111 new_entry->prev = NULL; 112 new_entry->name = sym; 113 new_entry->str_val = str_def; 114 new_entry->int_val = int_def; 115 116 table[hash_val] = new_entry; 117 118 return 0; 119 } 120 121 122 /* cclinstal - save the text of a character class */ 123 124 void cclinstal (ccltxt, cclnum) 125 u_char ccltxt[]; 126 int cclnum; 127 { 128 /* We don't bother checking the return status because we are not 129 * called unless the symbol is new. 130 */ 131 132 (void) addsym ((char *) copy_unsigned_string (ccltxt), 133 (char *) 0, cclnum, ccltab, CCL_HASH_SIZE); 134 } 135 136 137 /* ccllookup - lookup the number associated with character class text 138 * 139 * Returns 0 if there's no CCL associated with the text. 140 */ 141 142 int ccllookup (ccltxt) 143 u_char ccltxt[]; 144 { 145 return findsym ((char *) ccltxt, ccltab, CCL_HASH_SIZE)->int_val; 146 } 147 148 149 /* findsym - find symbol in symbol table */ 150 151 static struct hash_entry *findsym (sym, table, table_size) 152 const char *sym; 153 hash_table table; 154 int table_size; 155 { 156 static struct hash_entry empty_entry = { 157 (struct hash_entry *) 0, (struct hash_entry *) 0, 158 (char *) 0, (char *) 0, 0, 159 }; 160 struct hash_entry *sym_entry = 161 162 table[hashfunct (sym, table_size)]; 163 164 while (sym_entry) { 165 if (!strcmp (sym, sym_entry->name)) 166 return sym_entry; 167 sym_entry = sym_entry->next; 168 } 169 170 return &empty_entry; 171 } 172 173 /* hashfunct - compute the hash value for "str" and hash size "hash_size" */ 174 175 static int hashfunct (str, hash_size) 176 const char *str; 177 int hash_size; 178 { 179 int hashval; 180 int locstr; 181 182 hashval = 0; 183 locstr = 0; 184 185 while (str[locstr]) { 186 hashval = (hashval << 1) + (unsigned char) str[locstr++]; 187 hashval %= hash_size; 188 } 189 190 return hashval; 191 } 192 193 194 /* ndinstal - install a name definition */ 195 196 void ndinstal (name, definition) 197 const char *name; 198 u_char definition[]; 199 { 200 201 if (addsym (copy_string (name), 202 (char *) copy_unsigned_string (definition), 0, 203 ndtbl, NAME_TABLE_HASH_SIZE)) 204 synerr (_("name defined twice")); 205 } 206 207 208 /* ndlookup - lookup a name definition 209 * 210 * Returns a nil pointer if the name definition does not exist. 211 */ 212 213 u_char *ndlookup (nd) 214 const char *nd; 215 { 216 return (u_char *) findsym (nd, ndtbl, NAME_TABLE_HASH_SIZE)->str_val; 217 } 218 219 220 /* scextend - increase the maximum number of start conditions */ 221 222 void scextend () 223 { 224 current_max_scs += MAX_SCS_INCREMENT; 225 226 ++num_reallocs; 227 228 scset = reallocate_integer_array (scset, current_max_scs); 229 scbol = reallocate_integer_array (scbol, current_max_scs); 230 scxclu = reallocate_integer_array (scxclu, current_max_scs); 231 sceof = reallocate_integer_array (sceof, current_max_scs); 232 scname = reallocate_char_ptr_array (scname, current_max_scs); 233 } 234 235 236 /* scinstal - make a start condition 237 * 238 * NOTE 239 * The start condition is "exclusive" if xcluflg is true. 240 */ 241 242 void scinstal (str, xcluflg) 243 const char *str; 244 int xcluflg; 245 { 246 247 if (++lastsc >= current_max_scs) 248 scextend (); 249 250 scname[lastsc] = copy_string (str); 251 252 if (addsym (scname[lastsc], (char *) 0, lastsc, 253 sctbl, START_COND_HASH_SIZE)) 254 format_pinpoint_message (_ 255 ("start condition %s declared twice"), 256 str); 257 258 scset[lastsc] = mkstate (SYM_EPSILON); 259 scbol[lastsc] = mkstate (SYM_EPSILON); 260 scxclu[lastsc] = xcluflg; 261 sceof[lastsc] = false; 262 } 263 264 265 /* sclookup - lookup the number associated with a start condition 266 * 267 * Returns 0 if no such start condition. 268 */ 269 270 int sclookup (str) 271 const char *str; 272 { 273 return findsym (str, sctbl, START_COND_HASH_SIZE)->int_val; 274 } 275