1 /* $OpenBSD: sym.c,v 1.10 2024/11/09 18:03:44 op 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 (char sym[], char *str_def, int int_def, hash_table table, 78 int table_size) 79 { 80 int hash_val = hashfunct (sym, table_size); 81 struct hash_entry *sym_entry = table[hash_val]; 82 struct hash_entry *new_entry; 83 struct hash_entry *successor; 84 85 while (sym_entry) { 86 if (!strcmp (sym, sym_entry->name)) { /* entry already exists */ 87 return -1; 88 } 89 90 sym_entry = sym_entry->next; 91 } 92 93 /* create new entry */ 94 new_entry = (struct hash_entry *) 95 malloc (sizeof (struct hash_entry)); 96 97 if (new_entry == NULL) 98 flexfatal (_("symbol table memory allocation failed")); 99 100 if ((successor = table[hash_val]) != 0) { 101 new_entry->next = successor; 102 successor->prev = new_entry; 103 } 104 else 105 new_entry->next = NULL; 106 107 new_entry->prev = NULL; 108 new_entry->name = sym; 109 new_entry->str_val = str_def; 110 new_entry->int_val = int_def; 111 112 table[hash_val] = new_entry; 113 114 return 0; 115 } 116 117 118 /* cclinstal - save the text of a character class */ 119 120 void cclinstal (unsigned char ccltxt[], int cclnum) 121 { 122 /* We don't bother checking the return status because we are not 123 * called unless the symbol is new. 124 */ 125 126 (void) addsym ((char *) copy_unsigned_string (ccltxt), 127 (char *) 0, cclnum, ccltab, CCL_HASH_SIZE); 128 } 129 130 131 /* ccllookup - lookup the number associated with character class text 132 * 133 * Returns 0 if there's no CCL associated with the text. 134 */ 135 136 int ccllookup (unsigned char ccltxt[]) 137 { 138 return findsym ((char *) ccltxt, ccltab, CCL_HASH_SIZE)->int_val; 139 } 140 141 142 /* findsym - find symbol in symbol table */ 143 144 static struct hash_entry *findsym (const char *sym, hash_table table, 145 int table_size) 146 { 147 static struct hash_entry empty_entry = { 148 (struct hash_entry *) 0, (struct hash_entry *) 0, 149 (char *) 0, (char *) 0, 0, 150 }; 151 struct hash_entry *sym_entry = 152 153 table[hashfunct (sym, table_size)]; 154 155 while (sym_entry) { 156 if (!strcmp (sym, sym_entry->name)) 157 return sym_entry; 158 sym_entry = sym_entry->next; 159 } 160 161 return &empty_entry; 162 } 163 164 /* hashfunct - compute the hash value for "str" and hash size "hash_size" */ 165 166 static int hashfunct (const char *str, int hash_size) 167 { 168 int hashval; 169 int locstr; 170 171 hashval = 0; 172 locstr = 0; 173 174 while (str[locstr]) { 175 hashval = (hashval << 1) + (unsigned char) str[locstr++]; 176 hashval %= hash_size; 177 } 178 179 return hashval; 180 } 181 182 183 /* ndinstal - install a name definition */ 184 185 void ndinstal (const char *name, unsigned char definition[]) 186 { 187 if (addsym (copy_string (name), 188 (char *) copy_unsigned_string (definition), 0, 189 ndtbl, NAME_TABLE_HASH_SIZE)) 190 synerr (_("name defined twice")); 191 } 192 193 194 /* ndlookup - lookup a name definition 195 * 196 * Returns a nil pointer if the name definition does not exist. 197 */ 198 199 u_char *ndlookup (const char *nd) 200 { 201 return (u_char *) findsym (nd, ndtbl, NAME_TABLE_HASH_SIZE)->str_val; 202 } 203 204 205 /* scextend - increase the maximum number of start conditions */ 206 207 void scextend (void) 208 { 209 current_max_scs += MAX_SCS_INCREMENT; 210 211 ++num_reallocs; 212 213 scset = reallocate_integer_array (scset, current_max_scs); 214 scbol = reallocate_integer_array (scbol, current_max_scs); 215 scxclu = reallocate_integer_array (scxclu, current_max_scs); 216 sceof = reallocate_integer_array (sceof, current_max_scs); 217 scname = reallocate_char_ptr_array (scname, current_max_scs); 218 } 219 220 221 /* scinstal - make a start condition 222 * 223 * NOTE 224 * The start condition is "exclusive" if xcluflg is true. 225 */ 226 227 void scinstal (const char *str, int xcluflg) 228 { 229 if (++lastsc >= current_max_scs) 230 scextend (); 231 232 scname[lastsc] = copy_string (str); 233 234 if (addsym (scname[lastsc], (char *) 0, lastsc, 235 sctbl, START_COND_HASH_SIZE)) 236 format_pinpoint_message (_ 237 ("start condition %s declared twice"), 238 str); 239 240 scset[lastsc] = mkstate (SYM_EPSILON); 241 scbol[lastsc] = mkstate (SYM_EPSILON); 242 scxclu[lastsc] = xcluflg; 243 sceof[lastsc] = false; 244 } 245 246 247 /* sclookup - lookup the number associated with a start condition 248 * 249 * Returns 0 if no such start condition. 250 */ 251 252 int sclookup (const char *str) 253 { 254 return findsym (str, sctbl, START_COND_HASH_SIZE)->int_val; 255 } 256