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