1 /* Symbol table support
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3 James Bowman
4
5 Copyright (C) 2016 Molnar Karoly
6
7 This file is part of gputils.
8
9 gputils is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
12 any later version.
13
14 gputils is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with gputils; see the file COPYING. If not, write to
21 the Free Software Foundation, 59 Temple Place - Suite 330,
22 Boston, MA 02111-1307, USA. */
23
24 #include "stdhdr.h"
25 #include "libgputils.h"
26
27 #define HASH_TABLE_SIZE_MIN 5
28
29 struct symbol {
30 const char *name;
31 void *annotation;
32 hash128_t hash;
33 };
34
35 struct symbol_table {
36 symbol_table_t *prev;
37 symbol_t **symbol_array;
38 size_t symbol_array_size;
39 size_t num_symbol;
40 gp_boolean case_insensitive;
41 };
42
43 /*------------------------------------------------------------------------------------------------*/
44
45 static symbol_t *
_make_symbol(const char * String,hash128_t * Hash)46 _make_symbol(const char *String, hash128_t *Hash)
47 {
48 symbol_t *sym;
49
50 if (String == NULL) {
51 return NULL;
52 }
53
54 sym = GP_Malloc(sizeof(symbol_t));
55 sym->name = GP_Strdup(String);
56 sym->hash.low.u64 = Hash->low.u64;
57 sym->hash.high.u64 = Hash->high.u64;
58 sym->annotation = NULL;
59 return sym;
60 }
61
62 /*------------------------------------------------------------------------------------------------*/
63
64 static symbol_t *
_get_symbol_from_table(const symbol_table_t * Table,hash128_t * Hash)65 _get_symbol_from_table(const symbol_table_t *Table, hash128_t *Hash)
66 {
67 symbol_t **base;
68 symbol_t **current;
69 size_t mid;
70 size_t len;
71
72 assert(Table != NULL);
73 assert(Hash != NULL);
74
75 if ((Table->symbol_array == NULL) || (Table->num_symbol == 0)) {
76 return NULL;
77 }
78
79 base = Table->symbol_array;
80 len = Table->num_symbol;
81 do {
82 mid = len >> 1;
83 current = &base[mid];
84
85 if ((Hash->high.u64 == (*current)->hash.high.u64) && (Hash->low.u64 == (*current)->hash.low.u64)) {
86 /* Found the symbol. */
87 return *current;
88 }
89
90 if (len == 1) {
91 /* This is different int the least from the sought element. */
92 break;
93 }
94 else if ((Hash->high.u64 < (*current)->hash.high.u64) ||
95 ((Hash->high.u64 == (*current)->hash.high.u64) && (Hash->low.u64 < (*current)->hash.low.u64))) {
96 len = mid;
97 }
98 else {
99 len -= mid;
100 base = current;
101 }
102 }
103 while (len > 0);
104
105 return NULL;
106 }
107
108 /*------------------------------------------------------------------------------------------------*/
109
110 symbol_table_t *
gp_sym_push_table(symbol_table_t * Table,gp_boolean Case_insensitive)111 gp_sym_push_table(symbol_table_t *Table, gp_boolean Case_insensitive)
112 {
113 symbol_table_t *new_table;
114
115 new_table = GP_Calloc(1, sizeof(symbol_table_t));
116 new_table->prev = Table;
117 new_table->case_insensitive = Case_insensitive;
118 return new_table;
119 }
120
121 /*------------------------------------------------------------------------------------------------*/
122
123 symbol_table_t *
gp_sym_pop_table(symbol_table_t * Table)124 gp_sym_pop_table(symbol_table_t *Table)
125 {
126 assert(Table != NULL);
127
128 return Table->prev;
129 }
130
131 /*------------------------------------------------------------------------------------------------*/
132
133 void
gp_sym_set_guest_table(symbol_table_t * Table_host,symbol_table_t * Table_guest)134 gp_sym_set_guest_table(symbol_table_t *Table_host, symbol_table_t *Table_guest)
135 {
136 assert(Table_host != NULL);
137
138 Table_host->prev = Table_guest;
139 }
140
141 /*------------------------------------------------------------------------------------------------*/
142
143 symbol_table_t *
gp_sym_get_guest_table(symbol_table_t * Table)144 gp_sym_get_guest_table(symbol_table_t *Table)
145 {
146 assert(Table != NULL);
147
148 return Table->prev;
149 }
150
151 /*------------------------------------------------------------------------------------------------*/
152
153 symbol_t *
gp_sym_add_symbol(symbol_table_t * Table,const char * Name)154 gp_sym_add_symbol(symbol_table_t *Table, const char *Name)
155 {
156 symbol_t **base;
157 symbol_t **current;
158 symbol_t *sym;
159 size_t mid;
160 size_t idx;
161 size_t len;
162 hash128_t hash;
163
164 assert(Table != NULL);
165 assert(Name != NULL);
166 assert(Table->num_symbol <= UINT32_MAX);
167
168 if (Table->symbol_array == NULL) {
169 Table->symbol_array = (symbol_t **)GP_Malloc(HASH_TABLE_SIZE_MIN * sizeof(symbol_t *));
170 Table->symbol_array_size = HASH_TABLE_SIZE_MIN;
171 Table->num_symbol = 0;
172 }
173 else if (Table->num_symbol >= Table->symbol_array_size) {
174 /* Doubles the size of the table. */
175 len = Table->symbol_array_size * 2;
176 Table->symbol_array = (symbol_t **)GP_Realloc(Table->symbol_array, len * sizeof(symbol_t *));
177 Table->symbol_array_size = len;
178 }
179
180 gp_hash_init(&hash);
181 gp_hash_str(&hash, Name, Table->case_insensitive);
182
183 if (Table->num_symbol == 0) {
184 /* Empty the table. */
185 sym = _make_symbol(Name, &hash);
186 Table->symbol_array[0] = sym;
187 Table->num_symbol = 1;
188 return sym;
189 }
190
191 base = Table->symbol_array;
192 len = Table->num_symbol;
193 do {
194 mid = len >> 1;
195 current = &base[mid];
196
197 if ((hash.high.u64 == (*current)->hash.high.u64) && (hash.low.u64 == (*current)->hash.low.u64)) {
198 /* Found the symbol. */
199 return *current;
200 }
201
202 if (len == 1) {
203 /* This is different in the least from the sought element. */
204 base = Table->symbol_array;
205 idx = current - base;
206
207 if ((hash.high.u64 > (*current)->hash.high.u64) ||
208 ((hash.high.u64 == (*current)->hash.high.u64) && (hash.low.u64 > (*current)->hash.low.u64))) {
209 /* The new element is greather than this. */
210 ++idx;
211 }
212
213 len = (Table->num_symbol - idx) * sizeof(symbol_t *);
214 if (len > 0) {
215 /* The new element will not be the end of the table. */
216 memmove(&base[idx + 1], &base[idx], len);
217 }
218
219 sym = _make_symbol(Name, &hash);
220 base[idx] = sym;
221 ++(Table->num_symbol);
222 return sym;
223 }
224 else if ((hash.high.u64 < (*current)->hash.high.u64) ||
225 ((hash.high.u64 == (*current)->hash.high.u64) && (hash.low.u64 < (*current)->hash.low.u64))) {
226 len = mid;
227 }
228 else {
229 len -= mid;
230 base = current;
231 }
232 }
233 while (len > 0);
234
235 return NULL;
236 }
237
238 /*------------------------------------------------------------------------------------------------*/
239
240 gp_boolean
gp_sym_remove_symbol_with_index(symbol_table_t * Table,size_t Index)241 gp_sym_remove_symbol_with_index(symbol_table_t *Table, size_t Index)
242 {
243 symbol_t **base;
244 symbol_t *sym;
245 size_t len;
246
247 assert(Table != NULL);
248
249 if ((Table->symbol_array == NULL) || (Table->num_symbol == 0)) {
250 return false;
251 }
252
253 if (Index >= Table->num_symbol) {
254 return false;
255 }
256
257 len = (Table->num_symbol - Index - 1) * sizeof(symbol_t *);
258 base = Table->symbol_array;
259 sym = base[Index];
260
261 if (len > 0) {
262 memmove(&base[Index], &base[Index + 1], len);
263 }
264
265 --(Table->num_symbol);
266
267 if (sym->name != NULL) {
268 free((void *)sym->name);
269 }
270
271 free(sym);
272 return true;
273 }
274
275 /*------------------------------------------------------------------------------------------------*/
276
277 /* FIXME: gp_sym_remove_symbol does not search all of the symbol tables in the stack.
278 Maybe this is ok, but it seems wrong. */
279
280 gp_boolean
gp_sym_remove_symbol(symbol_table_t * Table,const char * Name)281 gp_sym_remove_symbol(symbol_table_t *Table, const char *Name)
282 {
283 symbol_t **base;
284 symbol_t **current;
285 size_t mid;
286 size_t len;
287 hash128_t hash;
288
289 assert(Table != NULL);
290 assert(Name != NULL);
291
292 if ((Table->symbol_array == NULL) || (Table->num_symbol == 0)) {
293 return false;
294 }
295
296 gp_hash_init(&hash);
297 gp_hash_str(&hash, Name, Table->case_insensitive);
298 base = Table->symbol_array;
299 len = Table->num_symbol;
300 do {
301 mid = len >> 1;
302 current = &base[mid];
303
304 if ((hash.high.u64 == (*current)->hash.high.u64) && (hash.low.u64 == (*current)->hash.low.u64)) {
305 /* Found the symbol. */
306 return gp_sym_remove_symbol_with_index(Table, current - Table->symbol_array);
307 }
308
309 if (len == 1) {
310 /* This is different int the least from the sought element. */
311 return false;
312 }
313 else if ((hash.high.u64 < (*current)->hash.high.u64) ||
314 ((hash.high.u64 == (*current)->hash.high.u64) && (hash.low.u64 < (*current)->hash.low.u64))) {
315 len = mid;
316 }
317 else {
318 len -= mid;
319 base = current;
320 }
321 }
322 while (len > 0);
323
324 return false;
325 }
326
327 /*------------------------------------------------------------------------------------------------*/
328
329 size_t
gp_sym_get_symbol_count(const symbol_table_t * Table)330 gp_sym_get_symbol_count(const symbol_table_t *Table)
331 {
332 assert(Table != NULL);
333
334 return Table->num_symbol;
335 }
336
337 /*------------------------------------------------------------------------------------------------*/
338
339 symbol_t *
gp_sym_get_symbol(const symbol_table_t * Table,const char * Name)340 gp_sym_get_symbol(const symbol_table_t *Table, const char *Name)
341 {
342 symbol_t *sym;
343 hash128_t hash;
344 gp_boolean first;
345 gp_boolean prev_case;
346
347 assert(Table != NULL);
348 assert(Name != NULL);
349
350 first = true;
351 prev_case = false;
352 while (Table != NULL) {
353 if (first || (Table->case_insensitive != prev_case)) {
354 gp_hash_init(&hash);
355 gp_hash_str(&hash, Name, Table->case_insensitive);
356 }
357
358 sym = _get_symbol_from_table(Table, &hash);
359 if (sym != NULL) {
360 return sym;
361 }
362
363 first = false;
364 prev_case = Table->case_insensitive;
365
366 /* If sym is still NULL, we didn't match. Try the prev table on the stack. */
367 Table = Table->prev;
368 }
369
370 return NULL;
371 }
372
373 /*------------------------------------------------------------------------------------------------*/
374
375 symbol_t *
gp_sym_get_symbol_len(const symbol_table_t * Table,const char * Name,size_t Len)376 gp_sym_get_symbol_len(const symbol_table_t *Table, const char *Name, size_t Len)
377 {
378 symbol_t *sym;
379 hash128_t hash;
380 gp_boolean first;
381 gp_boolean prev_case;
382
383 assert(Table != NULL);
384 assert(Name != NULL);
385
386 first = true;
387 prev_case = false;
388 while (Table != NULL) {
389 if (first || (Table->case_insensitive != prev_case)) {
390 gp_hash_init(&hash);
391 gp_hash_str_len(&hash, Name, Len, Table->case_insensitive);
392 }
393
394 sym = _get_symbol_from_table(Table, &hash);
395 if (sym != NULL) {
396 return sym;
397 }
398
399 first = false;
400 prev_case = Table->case_insensitive;
401
402 /* If sym is still NULL, we didn't match. Try the prev table on the stack. */
403 Table = Table->prev;
404 }
405
406 return NULL;
407 }
408
409 /*------------------------------------------------------------------------------------------------*/
410
411 symbol_t *
gp_sym_get_symbol_with_index(const symbol_table_t * Table,size_t Index)412 gp_sym_get_symbol_with_index(const symbol_table_t *Table, size_t Index)
413 {
414 assert(Table != NULL);
415 assert(Index < Table->num_symbol);
416
417 return Table->symbol_array[Index];
418 }
419
420 /*------------------------------------------------------------------------------------------------*/
421
422 const symbol_t **
gp_sym_clone_symbol_array(const symbol_table_t * Table,symbol_compare_t Cmp)423 gp_sym_clone_symbol_array(const symbol_table_t *Table, symbol_compare_t Cmp)
424 {
425 size_t size;
426 const symbol_t **array;
427
428 assert(Table != NULL);
429
430 if (Table->num_symbol == 0) {
431 return NULL;
432 }
433
434 size = Table->num_symbol * sizeof(symbol_t *);
435 array = (const symbol_t **)GP_Malloc(size);
436 memcpy(array, Table->symbol_array, size);
437
438 if (Cmp != NULL) {
439 qsort(array, Table->num_symbol, sizeof(symbol_t *), Cmp);
440 }
441
442 return array;
443 }
444
445 /*------------------------------------------------------------------------------------------------*/
446
447 void
gp_sym_annotate_symbol(symbol_t * Sym,void * Value)448 gp_sym_annotate_symbol(symbol_t *Sym, void *Value)
449 {
450 assert(Sym != NULL);
451
452 Sym->annotation = Value;
453 }
454
455 /*------------------------------------------------------------------------------------------------*/
456
457 const char *
gp_sym_get_symbol_name(const symbol_t * Sym)458 gp_sym_get_symbol_name(const symbol_t *Sym)
459 {
460 assert(Sym != NULL);
461
462 return Sym->name;
463 }
464
465 /*------------------------------------------------------------------------------------------------*/
466
467 void *
gp_sym_get_symbol_annotation(const symbol_t * Sym)468 gp_sym_get_symbol_annotation(const symbol_t *Sym)
469 {
470 assert(Sym != NULL);
471
472 return Sym->annotation;
473 }
474
475 /*------------------------------------------------------------------------------------------------*/
476
477 int
gp_sym_compare_fn(const void * P0,const void * P1)478 gp_sym_compare_fn(const void *P0, const void *P1)
479 {
480 const symbol_t *sym0 = *(const symbol_t **)P0;
481 const symbol_t *sym1 = *(const symbol_t **)P1;
482
483 return strcmp(sym0->name, sym1->name);
484 }
485
486 /*------------------------------------------------------------------------------------------------*/
487
488 int
gp_sym_version_compare_fn(const void * P0,const void * P1)489 gp_sym_version_compare_fn(const void *P0, const void *P1)
490 {
491 const symbol_t *sym0 = *(const symbol_t **)P0;
492 const symbol_t *sym1 = *(const symbol_t **)P1;
493
494 return strverscmp(sym0->name, sym1->name);
495 }
496