Commit | Line | Data |
---|---|---|
fecd2382 RP |
1 | /* hash.c - hash table lookup strings - |
2 | Copyright (C) 1987, 1990, 1991 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GAS, the GNU Assembler. | |
5 | ||
6 | GAS is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 1, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GAS is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GAS; see the file COPYING. If not, write to | |
18 | the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ | |
19 | ||
20 | /* static const char rcsid[] = "$Id$"; */ | |
21 | ||
22 | /* | |
23 | * BUGS, GRIPES, APOLOGIA etc. | |
24 | * | |
25 | * A typical user doesn't need ALL this: I intend to make a library out | |
26 | * of it one day - Dean Elsner. | |
27 | * Also, I want to change the definition of a symbol to (address,length) | |
28 | * so I can put arbitrary binary in the names stored. [see hsh.c for that] | |
29 | * | |
30 | * This slime is common coupled inside the module. Com-coupling (and other | |
31 | * vandalism) was done to speed running time. The interfaces at the | |
32 | * module's edges are adequately clean. | |
33 | * | |
34 | * There is no way to (a) run a test script through this heap and (b) | |
35 | * compare results with previous scripts, to see if we have broken any | |
36 | * code. Use GNU (f)utilities to do this. A few commands assist test. | |
37 | * The testing is awkward: it tries to be both batch & interactive. | |
38 | * For now, interactive rules! | |
39 | */ | |
40 | \f | |
41 | /* | |
42 | * The idea is to implement a symbol table. A test jig is here. | |
43 | * Symbols are arbitrary strings; they can't contain '\0'. | |
44 | * [See hsh.c for a more general symbol flavour.] | |
45 | * Each symbol is associated with a char*, which can point to anything | |
46 | * you want, allowing an arbitrary property list for each symbol. | |
47 | * | |
48 | * The basic operations are: | |
49 | * | |
50 | * new creates symbol table, returns handle | |
51 | * find (symbol) returns char* | |
52 | * insert (symbol,char*) error if symbol already in table | |
53 | * delete (symbol) returns char* if symbol was in table | |
54 | * apply so you can delete all symbols before die() | |
55 | * die destroy symbol table (free up memory) | |
56 | * | |
57 | * Supplementary functions include: | |
58 | * | |
59 | * say how big? what % full? | |
60 | * replace (symbol,newval) report previous value | |
61 | * jam (symbol,value) assert symbol:=value | |
62 | * | |
63 | * You, the caller, have control over errors: this just reports them. | |
64 | * | |
65 | * This package requires malloc(), free(). | |
66 | * Malloc(size) returns NULL or address of char[size]. | |
67 | * Free(address) frees same. | |
68 | */ | |
69 | \f | |
70 | /* | |
71 | * The code and its structures are re-enterent. | |
72 | * Before you do anything else, you must call hash_new() which will | |
73 | * return the address of a hash-table-control-block (or NULL if there | |
74 | * is not enough memory). You then use this address as a handle of the | |
75 | * symbol table by passing it to all the other hash_...() functions. | |
76 | * The only approved way to recover the memory used by the symbol table | |
77 | * is to call hash_die() with the handle of the symbol table. | |
78 | * | |
79 | * Before you call hash_die() you normally delete anything pointed to | |
80 | * by individual symbols. After hash_die() you can't use that symbol | |
81 | * table again. | |
82 | * | |
83 | * The char* you associate with a symbol may not be NULL (0) because | |
84 | * NULL is returned whenever a symbol is not in the table. Any other | |
85 | * value is OK, except DELETED, #defined below. | |
86 | * | |
87 | * When you supply a symbol string for insertion, YOU MUST PRESERVE THE | |
88 | * STRING until that symbol is deleted from the table. The reason is that | |
89 | * only the address you supply, NOT the symbol string itself, is stored | |
90 | * in the symbol table. | |
91 | * | |
92 | * You may delete and add symbols arbitrarily. | |
93 | * Any or all symbols may have the same 'value' (char *). In fact, these | |
94 | * routines don't do anything with your symbol values. | |
95 | * | |
96 | * You have no right to know where the symbol:char* mapping is stored, | |
97 | * because it moves around in memory; also because we may change how it | |
98 | * works and we don't want to break your code do we? However the handle | |
99 | * (address of struct hash_control) is never changed in | |
100 | * the life of the symbol table. | |
101 | * | |
102 | * What you CAN find out about a symbol table is: | |
103 | * how many slots are in the hash table? | |
104 | * how many slots are filled with symbols? | |
105 | * (total hashes,collisions) for (reads,writes) (*) | |
106 | * All of the above values vary in time. | |
107 | * (*) some of these numbers will not be meaningful if we change the | |
108 | * internals. | |
109 | */ | |
110 | \f | |
111 | /* | |
112 | * I N T E R N A L | |
113 | * | |
114 | * Hash table is an array of hash_entries; each entry is a pointer to a | |
115 | * a string and a user-supplied value 1 char* wide. | |
116 | * | |
117 | * The array always has 2 ** n elements, n>0, n integer. | |
118 | * There is also a 'wall' entry after the array, which is always empty | |
119 | * and acts as a sentinel to stop running off the end of the array. | |
120 | * When the array gets too full, we create a new array twice as large | |
121 | * and re-hash the symbols into the new array, then forget the old array. | |
122 | * (Of course, we copy the values into the new array before we junk the | |
123 | * old array!) | |
124 | * | |
125 | */ | |
126 | ||
127 | #include <stdio.h> | |
128 | ||
129 | #ifndef FALSE | |
130 | #define FALSE (0) | |
131 | #define TRUE (!FALSE) | |
132 | #endif /* no FALSE yet */ | |
133 | ||
134 | #include <ctype.h> | |
135 | #define min(a, b) ((a) < (b) ? (a) : (b)) | |
136 | ||
137 | #include "as.h" | |
138 | ||
139 | #define error as_fatal | |
140 | ||
141 | #define DELETED ((char *)1) /* guarenteed invalid address */ | |
142 | #define START_POWER (11) /* power of two: size of new hash table *//* JF was 6 */ | |
143 | /* JF These next two aren't used any more. */ | |
144 | /* #define START_SIZE (64) / * 2 ** START_POWER */ | |
145 | /* #define START_FULL (32) / * number of entries before table expands */ | |
146 | #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED) | |
147 | /* above TRUE if a symbol is in entry @ ptr */ | |
148 | ||
149 | #define STAT_SIZE (0) /* number of slots in hash table */ | |
150 | /* the wall does not count here */ | |
151 | /* we expect this is always a power of 2 */ | |
152 | #define STAT_ACCESS (1) /* number of hash_ask()s */ | |
153 | #define STAT__READ (0) /* reading */ | |
154 | #define STAT__WRITE (1) /* writing */ | |
155 | #define STAT_COLLIDE (3) /* number of collisions (total) */ | |
156 | /* this may exceed STAT_ACCESS if we have */ | |
157 | /* lots of collisions/access */ | |
158 | #define STAT_USED (5) /* slots used right now */ | |
159 | #define STATLENGTH (6) /* size of statistics block */ | |
160 | #if STATLENGTH != HASH_STATLENGTH | |
161 | Panic! Please make #include "stat.h" agree with previous definitions! | |
162 | #endif | |
163 | ||
164 | /* #define SUSPECT to do runtime checks */ | |
165 | /* #define TEST to be a test jig for hash...() */ | |
166 | ||
167 | #ifdef TEST /* TEST: use smaller hash table */ | |
168 | #undef START_POWER | |
169 | #define START_POWER (3) | |
170 | #undef START_SIZE | |
171 | #define START_SIZE (8) | |
172 | #undef START_FULL | |
173 | #define START_FULL (4) | |
174 | #endif | |
175 | \f | |
176 | /*------------------ plan ---------------------------------- i = internal | |
177 | ||
178 | struct hash_control * c; | |
179 | struct hash_entry * e; i | |
180 | int b[z]; buffer for statistics | |
181 | z size of b | |
182 | char * s; symbol string (address) [ key ] | |
183 | char * v; value string (address) [datum] | |
184 | boolean f; TRUE if we found s in hash table i | |
185 | char * t; error string; "" means OK | |
186 | int a; access type [0...n) i | |
187 | ||
188 | c=hash_new () create new hash_control | |
189 | ||
190 | hash_die (c) destroy hash_control (and hash table) | |
191 | table should be empty. | |
192 | doesn't check if table is empty. | |
193 | c has no meaning after this. | |
194 | ||
195 | hash_say (c,b,z) report statistics of hash_control. | |
196 | also report number of available statistics. | |
197 | ||
198 | v=hash_delete (c,s) delete symbol, return old value if any. | |
199 | ask() NULL means no old value. | |
200 | f | |
201 | ||
202 | v=hash_replace (c,s,v) replace old value of s with v. | |
203 | ask() NULL means no old value: no table change. | |
204 | f | |
205 | ||
206 | t=hash_insert (c,s,v) insert (s,v) in c. | |
207 | ask() return error string. | |
208 | f it is an error to insert if s is already | |
209 | in table. | |
210 | if any error, c is unchanged. | |
211 | ||
212 | t=hash_jam (c,s,v) assert that new value of s will be v. i | |
213 | ask() it may decide to GROW the table. i | |
214 | f i | |
215 | grow() i | |
216 | t=hash_grow (c) grow the hash table. i | |
217 | jam() will invoke JAM. i | |
218 | ||
219 | ?=hash_apply (c,y) apply y() to every symbol in c. | |
220 | y evtries visited in 'unspecified' order. | |
221 | ||
222 | v=hash_find (c,s) return value of s, or NULL if s not in c. | |
223 | ask() | |
224 | f | |
225 | ||
226 | f,e=hash_ask() (c,s,a) return slot where s SHOULD live. i | |
227 | code() maintain collision stats in c. i | |
228 | ||
229 | .=hash_code (c,s) compute hash-code for s, i | |
230 | from parameters of c. i | |
231 | ||
232 | */ | |
233 | \f | |
234 | static char hash_found; /* returned by hash_ask() to stop extra */ | |
235 | /* testing. hash_ask() wants to return both */ | |
236 | /* a slot and a status. This is the status. */ | |
237 | /* TRUE: found symbol */ | |
238 | /* FALSE: absent: empty or deleted slot */ | |
239 | /* Also returned by hash_jam(). */ | |
240 | /* TRUE: we replaced a value */ | |
241 | /* FALSE: we inserted a value */ | |
242 | ||
243 | static struct hash_entry * hash_ask(); | |
244 | static int hash_code (); | |
245 | static char * hash_grow(); | |
246 | \f | |
247 | /* | |
248 | * h a s h _ n e w ( ) | |
249 | * | |
250 | */ | |
251 | struct hash_control * | |
252 | hash_new() /* create a new hash table */ | |
253 | /* return NULL if failed */ | |
254 | /* return handle (address of struct hash) */ | |
255 | { | |
256 | register struct hash_control * retval; | |
257 | register struct hash_entry * room; /* points to hash table */ | |
258 | register struct hash_entry * wall; | |
259 | register struct hash_entry * entry; | |
260 | register int * ip; /* scan stats block of struct hash_control */ | |
261 | register int * nd; /* limit of stats block */ | |
262 | ||
263 | if (( room = (struct hash_entry *) malloc( sizeof(struct | |
264 | hash_entry)*((1<<START_POWER) + 1) ) ) != NULL) | |
265 | /* +1 for the wall entry */ | |
266 | { | |
267 | if (( retval = (struct hash_control *) malloc(sizeof(struct | |
268 | hash_control)) ) != NULL) | |
269 | { | |
270 | nd = retval->hash_stat + STATLENGTH; | |
271 | for (ip=retval->hash_stat; ip<nd; ip++) | |
272 | { | |
273 | *ip = 0; | |
274 | } | |
275 | ||
276 | retval -> hash_stat[STAT_SIZE] = 1<<START_POWER; | |
277 | retval -> hash_mask = (1<<START_POWER) - 1; | |
278 | retval -> hash_sizelog = START_POWER; | |
279 | /* works for 1's compl ok */ | |
280 | retval -> hash_where = room; | |
281 | retval -> hash_wall = | |
282 | wall = room + (1<<START_POWER); | |
283 | retval -> hash_full = (1<<START_POWER)/2; | |
284 | for (entry=room; entry<=wall; entry++) | |
285 | { | |
286 | entry->hash_string = NULL; | |
287 | } | |
288 | } | |
289 | } | |
290 | else | |
291 | { | |
292 | retval = NULL; /* no room for table: fake a failure */ | |
293 | } | |
294 | return(retval); /* return NULL or set-up structs */ | |
295 | } | |
296 | ||
297 | /* | |
298 | * h a s h _ d i e ( ) | |
299 | * | |
300 | * Table should be empty, but this is not checked. | |
301 | * To empty the table, try hash_apply()ing a symbol deleter. | |
302 | * Return to free memory both the hash table and it's control | |
303 | * block. | |
304 | * 'handle' has no meaning after this function. | |
305 | * No errors are recoverable. | |
306 | */ | |
307 | void | |
308 | hash_die(handle) | |
309 | struct hash_control * handle; | |
310 | { | |
311 | free((char *)handle->hash_where); | |
312 | free((char *)handle); | |
313 | } | |
314 | \f | |
315 | /* | |
316 | * h a s h _ s a y ( ) | |
317 | * | |
318 | * Return the size of the statistics table, and as many statistics as | |
319 | * we can until either (a) we have run out of statistics or (b) caller | |
320 | * has run out of buffer. | |
321 | * NOTE: hash_say treats all statistics alike. | |
322 | * These numbers may change with time, due to insertions, deletions | |
323 | * and expansions of the table. | |
324 | * The first "statistic" returned is the length of hash_stat[]. | |
325 | * Then contents of hash_stat[] are read out (in ascending order) | |
326 | * until your buffer or hash_stat[] is exausted. | |
327 | */ | |
328 | void | |
329 | hash_say(handle,buffer,bufsiz) | |
330 | register struct hash_control * handle; | |
331 | register int buffer[/*bufsiz*/]; | |
332 | register int bufsiz; | |
333 | { | |
334 | register int * nd; /* limit of statistics block */ | |
335 | register int * ip; /* scan statistics */ | |
336 | ||
337 | ip = handle -> hash_stat; | |
338 | nd = ip + min(bufsiz-1,STATLENGTH); | |
339 | if (bufsiz>0) /* trust nothing! bufsiz<=0 is dangerous */ | |
340 | { | |
341 | *buffer++ = STATLENGTH; | |
342 | for (; ip<nd; ip++,buffer++) | |
343 | { | |
344 | *buffer = *ip; | |
345 | } | |
346 | } | |
347 | } | |
348 | \f | |
349 | /* | |
350 | * h a s h _ d e l e t e ( ) | |
351 | * | |
352 | * Try to delete a symbol from the table. | |
353 | * If it was there, return its value (and adjust STAT_USED). | |
354 | * Otherwise, return NULL. | |
355 | * Anyway, the symbol is not present after this function. | |
356 | * | |
357 | */ | |
358 | char * /* NULL if string not in table, else */ | |
359 | /* returns value of deleted symbol */ | |
360 | hash_delete(handle,string) | |
361 | register struct hash_control * handle; | |
362 | register char * string; | |
363 | { | |
364 | register char * retval; /* NULL if string not in table */ | |
365 | register struct hash_entry * entry; /* NULL or entry of this symbol */ | |
366 | ||
367 | entry = hash_ask(handle,string,STAT__WRITE); | |
368 | if (hash_found) | |
369 | { | |
370 | retval = entry -> hash_value; | |
371 | entry -> hash_string = DELETED; /* mark as deleted */ | |
372 | handle -> hash_stat[STAT_USED] -= 1; /* slots-in-use count */ | |
373 | #ifdef SUSPECT | |
374 | if (handle->hash_stat[STAT_USED]<0) | |
375 | { | |
376 | error("hash_delete"); | |
377 | } | |
378 | #endif /* def SUSPECT */ | |
379 | } | |
380 | else | |
381 | { | |
382 | retval = NULL; | |
383 | } | |
384 | return(retval); | |
385 | } | |
386 | \f | |
387 | /* | |
388 | * h a s h _ r e p l a c e ( ) | |
389 | * | |
390 | * Try to replace the old value of a symbol with a new value. | |
391 | * Normally return the old value. | |
392 | * Return NULL and don't change the table if the symbol is not already | |
393 | * in the table. | |
394 | */ | |
395 | char * | |
396 | hash_replace(handle,string,value) | |
397 | register struct hash_control * handle; | |
398 | register char * string; | |
399 | register char * value; | |
400 | { | |
401 | register struct hash_entry * entry; | |
402 | register char * retval; | |
403 | ||
404 | entry = hash_ask(handle,string,STAT__WRITE); | |
405 | if (hash_found) | |
406 | { | |
407 | retval = entry -> hash_value; | |
408 | entry -> hash_value = value; | |
409 | } | |
410 | else | |
411 | { | |
412 | retval = NULL; | |
413 | } | |
414 | ; | |
415 | return (retval); | |
416 | } | |
417 | \f | |
418 | /* | |
419 | * h a s h _ i n s e r t ( ) | |
420 | * | |
421 | * Insert a (symbol-string, value) into the hash table. | |
422 | * Return an error string, "" means OK. | |
423 | * It is an 'error' to insert an existing symbol. | |
424 | */ | |
425 | ||
426 | char * /* return error string */ | |
427 | hash_insert(handle,string,value) | |
428 | register struct hash_control * handle; | |
429 | register char * string; | |
430 | register char * value; | |
431 | { | |
432 | register struct hash_entry * entry; | |
433 | register char * retval; | |
434 | ||
435 | retval = ""; | |
436 | if (handle->hash_stat[STAT_USED] > handle->hash_full) | |
437 | { | |
438 | retval = hash_grow(handle); | |
439 | } | |
440 | if ( ! * retval) | |
441 | { | |
442 | entry = hash_ask(handle,string,STAT__WRITE); | |
443 | if (hash_found) | |
444 | { | |
445 | retval = "exists"; | |
446 | } | |
447 | else | |
448 | { | |
449 | entry -> hash_value = value; | |
450 | entry -> hash_string = string; | |
451 | handle-> hash_stat[STAT_USED] += 1; | |
452 | } | |
453 | } | |
454 | return(retval); | |
455 | } | |
456 | \f | |
457 | /* | |
458 | * h a s h _ j a m ( ) | |
459 | * | |
460 | * Regardless of what was in the symbol table before, after hash_jam() | |
461 | * the named symbol has the given value. The symbol is either inserted or | |
462 | * (its value is) relpaced. | |
463 | * An error message string is returned, "" means OK. | |
464 | * | |
465 | * WARNING: this may decide to grow the hashed symbol table. | |
466 | * To do this, we call hash_grow(), WHICH WILL recursively CALL US. | |
467 | * | |
468 | * We report status internally: hash_found is TRUE if we replaced, but | |
469 | * false if we inserted. | |
470 | */ | |
471 | char * | |
472 | hash_jam(handle,string,value) | |
473 | register struct hash_control * handle; | |
474 | register char * string; | |
475 | register char * value; | |
476 | { | |
477 | register char * retval; | |
478 | register struct hash_entry * entry; | |
479 | ||
480 | retval = ""; | |
481 | if (handle->hash_stat[STAT_USED] > handle->hash_full) | |
482 | { | |
483 | retval = hash_grow(handle); | |
484 | } | |
485 | if (! * retval) | |
486 | { | |
487 | entry = hash_ask(handle,string,STAT__WRITE); | |
488 | if ( ! hash_found) | |
489 | { | |
490 | entry -> hash_string = string; | |
491 | handle->hash_stat[STAT_USED] += 1; | |
492 | } | |
493 | entry -> hash_value = value; | |
494 | } | |
495 | return(retval); | |
496 | } | |
497 | ||
498 | /* | |
499 | * h a s h _ g r o w ( ) | |
500 | * | |
501 | * Grow a new (bigger) hash table from the old one. | |
502 | * We choose to double the hash table's size. | |
503 | * Return a human-scrutible error string: "" if OK. | |
504 | * Warning! This uses hash_jam(), which had better not recurse | |
505 | * back here! Hash_jam() conditionally calls us, but we ALWAYS | |
506 | * call hash_jam()! | |
507 | * Internal. | |
508 | */ | |
509 | static char * | |
510 | hash_grow(handle) /* make a hash table grow */ | |
511 | struct hash_control * handle; | |
512 | { | |
513 | register struct hash_entry * newwall; | |
514 | register struct hash_entry * newwhere; | |
515 | struct hash_entry * newtrack; | |
516 | register struct hash_entry * oldtrack; | |
517 | register struct hash_entry * oldwhere; | |
518 | register struct hash_entry * oldwall; | |
519 | register int temp; | |
520 | int newsize; | |
521 | char * string; | |
522 | char * retval; | |
523 | #ifdef SUSPECT | |
524 | int oldused; | |
525 | #endif | |
526 | ||
527 | /* | |
528 | * capture info about old hash table | |
529 | */ | |
530 | oldwhere = handle -> hash_where; | |
531 | oldwall = handle -> hash_wall; | |
532 | #ifdef SUSPECT | |
533 | oldused = handle -> hash_stat[STAT_USED]; | |
534 | #endif | |
535 | /* | |
536 | * attempt to get enough room for a hash table twice as big | |
537 | */ | |
538 | temp = handle->hash_stat[STAT_SIZE]; | |
539 | if (( newwhere = (struct hash_entry *) | |
540 | xmalloc((long)((temp+temp+1)*sizeof(struct hash_entry)))) != NULL) | |
541 | /* +1 for wall slot */ | |
542 | { | |
543 | retval = ""; /* assume success until proven otherwise */ | |
544 | /* | |
545 | * have enough room: now we do all the work. | |
546 | * double the size of everything in handle, | |
547 | * note: hash_mask frob works for 1's & for 2's complement machines | |
548 | */ | |
549 | handle->hash_mask = handle->hash_mask + handle->hash_mask + 1; | |
550 | handle->hash_stat[STAT_SIZE] <<= 1; | |
551 | newsize = handle->hash_stat[STAT_SIZE]; | |
552 | handle->hash_where = newwhere; | |
553 | handle->hash_full <<= 1; | |
554 | handle->hash_sizelog += 1; | |
555 | handle->hash_stat[STAT_USED] = 0; | |
556 | handle->hash_wall = | |
557 | newwall = newwhere + newsize; | |
558 | /* | |
559 | * set all those pesky new slots to vacant. | |
560 | */ | |
561 | for (newtrack=newwhere; newtrack <= newwall; newtrack++) | |
562 | { | |
563 | newtrack -> hash_string = NULL; | |
564 | } | |
565 | /* | |
566 | * we will do a scan of the old table, the hard way, using the | |
567 | * new control block to re-insert the data into new hash table. | |
568 | */ | |
569 | handle -> hash_stat[STAT_USED] = 0; /* inserts will bump it up to correct */ | |
570 | for (oldtrack=oldwhere; oldtrack < oldwall; oldtrack++) | |
571 | { | |
572 | if ( ((string=oldtrack->hash_string) != NULL) && string!=DELETED ) | |
573 | { | |
574 | if ( * (retval = hash_jam(handle,string,oldtrack->hash_value) ) ) | |
575 | { | |
576 | break; | |
577 | } | |
578 | } | |
579 | } | |
580 | #ifdef SUSPECT | |
581 | if ( !*retval && handle->hash_stat[STAT_USED] != oldused) | |
582 | { | |
583 | retval = "hash_used"; | |
584 | } | |
585 | #endif | |
586 | if (!*retval) | |
587 | { | |
588 | /* | |
589 | * we have a completely faked up control block. | |
590 | * return the old hash table. | |
591 | */ | |
592 | free((char *)oldwhere); | |
593 | /* | |
594 | * Here with success. retval is already "". | |
595 | */ | |
596 | } | |
597 | } | |
598 | else | |
599 | { | |
600 | retval = "no room"; | |
601 | } | |
602 | return(retval); | |
603 | } | |
604 | \f | |
605 | /* | |
606 | * h a s h _ a p p l y ( ) | |
607 | * | |
608 | * Use this to scan each entry in symbol table. | |
609 | * For each symbol, this calls (applys) a nominated function supplying the | |
610 | * symbol's value (and the symbol's name). | |
611 | * The idea is you use this to destroy whatever is associted with | |
612 | * any values in the table BEFORE you destroy the table with hash_die. | |
613 | * Of course, you can use it for other jobs; whenever you need to | |
614 | * visit all extant symbols in the table. | |
615 | * | |
616 | * We choose to have a call-you-back idea for two reasons: | |
617 | * asthetic: it is a neater idea to use apply than an explicit loop | |
618 | * sensible: if we ever had to grow the symbol table (due to insertions) | |
619 | * then we would lose our place in the table when we re-hashed | |
620 | * symbols into the new table in a different order. | |
621 | * | |
622 | * The order symbols are visited depends entirely on the hashing function. | |
623 | * Whenever you insert a (symbol, value) you risk expanding the table. If | |
624 | * you do expand the table, then the hashing function WILL change, so you | |
625 | * MIGHT get a different order of symbols visited. In other words, if you | |
626 | * want the same order of visiting symbols as the last time you used | |
627 | * hash_apply() then you better not have done any hash_insert()s or | |
628 | * hash_jam()s since the last time you used hash_apply(). | |
629 | * | |
630 | * In future we may use the value returned by your nominated function. | |
631 | * One idea is to abort the scan if, after applying the function to a | |
632 | * certain node, the function returns a certain code. | |
633 | * To be safe, please make your functions of type char *. If you always | |
634 | * return NULL, then the scan will complete, visiting every symbol in | |
635 | * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet! | |
636 | * Caveat Actor! | |
637 | * | |
638 | * The function you supply should be of the form: | |
639 | * char * myfunct(string,value) | |
640 | * char * string; |* the symbol's name *| | |
641 | * char * value; |* the symbol's value *| | |
642 | * { | |
643 | * |* ... *| | |
644 | * return(NULL); | |
645 | * } | |
646 | * | |
647 | * The returned value of hash_apply() is (char*)NULL. In future it may return | |
648 | * other values. NULL means "completed scan OK". Other values have no meaning | |
649 | * yet. (The function has no graceful failures.) | |
650 | */ | |
651 | char * | |
652 | hash_apply(handle,function) | |
653 | struct hash_control * handle; | |
654 | char* (*function)(); | |
655 | { | |
656 | register struct hash_entry * entry; | |
657 | register struct hash_entry * wall; | |
658 | ||
659 | wall = handle->hash_wall; | |
660 | for (entry = handle->hash_where; entry < wall; entry++) | |
661 | { | |
662 | if (islive(entry)) /* silly code: tests entry->string twice! */ | |
663 | { | |
664 | (*function)(entry->hash_string,entry->hash_value); | |
665 | } | |
666 | } | |
667 | return (NULL); | |
668 | } | |
669 | \f | |
670 | /* | |
671 | * h a s h _ f i n d ( ) | |
672 | * | |
673 | * Given symbol string, find value (if any). | |
674 | * Return found value or NULL. | |
675 | */ | |
676 | char * | |
677 | hash_find(handle,string) /* return char* or NULL */ | |
678 | struct hash_control * handle; | |
679 | char * string; | |
680 | { | |
681 | register struct hash_entry * entry; | |
682 | register char * retval; | |
683 | ||
684 | entry = hash_ask(handle,string,STAT__READ); | |
685 | if (hash_found) | |
686 | { | |
687 | retval = entry->hash_value; | |
688 | } | |
689 | else | |
690 | { | |
691 | retval = NULL; | |
692 | } | |
693 | return(retval); | |
694 | } | |
695 | \f | |
696 | /* | |
697 | * h a s h _ a s k ( ) | |
698 | * | |
699 | * Searches for given symbol string. | |
700 | * Return the slot where it OUGHT to live. It may be there. | |
701 | * Return hash_found: TRUE only if symbol is in that slot. | |
702 | * Access argument is to help keep statistics in control block. | |
703 | * Internal. | |
704 | */ | |
705 | static struct hash_entry * /* string slot, may be empty or deleted */ | |
706 | hash_ask(handle,string,access) | |
707 | struct hash_control * handle; | |
708 | char * string; | |
709 | int access; /* access type */ | |
710 | { | |
711 | register char *string1; /* JF avoid strcmp calls */ | |
712 | register char * s; | |
713 | register int c; | |
714 | register struct hash_entry * slot; | |
715 | register int collision; /* count collisions */ | |
716 | ||
717 | slot = handle->hash_where + hash_code(handle,string); /* start looking here */ | |
718 | handle->hash_stat[STAT_ACCESS+access] += 1; | |
719 | collision = 0; | |
720 | hash_found = FALSE; | |
721 | while ( ((s = slot->hash_string) != NULL) && s!=DELETED ) | |
722 | { | |
723 | for(string1=string;;) { | |
724 | if((c= *s++) == 0) { | |
725 | if(!*string1) | |
726 | hash_found = TRUE; | |
727 | break; | |
728 | } | |
729 | if(*string1++!=c) | |
730 | break; | |
731 | } | |
732 | if(hash_found) | |
733 | break; | |
734 | collision++; | |
735 | slot++; | |
736 | } | |
737 | /* | |
738 | * slot: return: | |
739 | * in use: we found string slot | |
740 | * at empty: | |
741 | * at wall: we fell off: wrap round ???? | |
742 | * in table: dig here slot | |
743 | * at DELETED: dig here slot | |
744 | */ | |
745 | if (slot==handle->hash_wall) | |
746 | { | |
747 | slot = handle->hash_where; /* now look again */ | |
748 | while( ((s = slot->hash_string) != NULL) && s!=DELETED ) | |
749 | { | |
750 | for(string1=string;*s;string1++,s++) { | |
751 | if(*string1!=*s) | |
752 | break; | |
753 | } | |
754 | if(*s==*string1) { | |
755 | hash_found = TRUE; | |
756 | break; | |
757 | } | |
758 | collision++; | |
759 | slot++; | |
760 | } | |
761 | /* | |
762 | * slot: return: | |
763 | * in use: we found it slot | |
764 | * empty: wall: ERROR IMPOSSIBLE !!!! | |
765 | * in table: dig here slot | |
766 | * DELETED:dig here slot | |
767 | */ | |
768 | } | |
769 | /* fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,string),collision); */ | |
770 | handle -> hash_stat[STAT_COLLIDE+access] += collision; | |
771 | return(slot); /* also return hash_found */ | |
772 | } | |
773 | \f | |
774 | /* | |
775 | * h a s h _ c o d e | |
776 | * | |
777 | * Does hashing of symbol string to hash number. | |
778 | * Internal. | |
779 | */ | |
780 | static int | |
781 | hash_code(handle,string) | |
782 | struct hash_control * handle; | |
783 | register char * string; | |
784 | { | |
785 | register long h; /* hash code built here */ | |
786 | register long c; /* each character lands here */ | |
787 | register int n; /* Amount to shift h by */ | |
788 | ||
789 | n = (handle->hash_sizelog - 3); | |
790 | h = 0; | |
791 | while ((c = *string++) != 0) | |
792 | { | |
793 | h += c; | |
794 | h = (h<<3) + (h>>n) + c; | |
795 | } | |
796 | return (h & handle->hash_mask); | |
797 | } | |
798 | \f | |
799 | /* | |
800 | * Here is a test program to exercise above. | |
801 | */ | |
802 | #ifdef TEST | |
803 | ||
804 | #define TABLES (6) /* number of hash tables to maintain */ | |
805 | /* (at once) in any testing */ | |
806 | #define STATBUFSIZE (12) /* we can have 12 statistics */ | |
807 | ||
808 | int statbuf[STATBUFSIZE]; /* display statistics here */ | |
809 | char answer[100]; /* human farts here */ | |
810 | char * hashtable[TABLES]; /* we test many hash tables at once */ | |
811 | char * h; /* points to curent hash_control */ | |
812 | char ** pp; | |
813 | char * p; | |
814 | char * name; | |
815 | char * value; | |
816 | int size; | |
817 | int used; | |
818 | char command; | |
819 | int number; /* number 0:TABLES-1 of current hashed */ | |
820 | /* symbol table */ | |
821 | ||
822 | main() | |
823 | { | |
824 | char (*applicatee()); | |
825 | char * hash_find(); | |
826 | char * destroy(); | |
827 | char * what(); | |
828 | struct hash_control * hash_new(); | |
829 | char * hash_replace(); | |
830 | int * ip; | |
831 | ||
832 | number = 0; | |
833 | h = 0; | |
834 | printf("type h <RETURN> for help\n"); | |
835 | for(;;) | |
836 | { | |
837 | printf("hash_test command: "); | |
838 | gets(answer); | |
839 | command = answer[0]; | |
840 | if (isupper(command)) command = tolower(command); /* ecch! */ | |
841 | switch (command) | |
842 | { | |
843 | case '#': | |
844 | printf("old hash table #=%d.\n",number); | |
845 | whattable(); | |
846 | break; | |
847 | case '?': | |
848 | for (pp=hashtable; pp<hashtable+TABLES; pp++) | |
849 | { | |
850 | printf("address of hash table #%d control block is %xx\n" | |
851 | ,pp-hashtable,*pp); | |
852 | } | |
853 | break; | |
854 | case 'a': | |
855 | hash_apply(h,applicatee); | |
856 | break; | |
857 | case 'd': | |
858 | hash_apply(h,destroy); | |
859 | hash_die(h); | |
860 | break; | |
861 | case 'f': | |
862 | p = hash_find(h,name=what("symbol")); | |
863 | printf("value of \"%s\" is \"%s\"\n",name,p?p:"NOT-PRESENT"); | |
864 | break; | |
865 | case 'h': | |
866 | printf("# show old, select new default hash table number\n"); | |
867 | printf("? display all hashtable control block addresses\n"); | |
868 | printf("a apply a simple display-er to each symbol in table\n"); | |
869 | printf("d die: destroy hashtable\n"); | |
870 | printf("f find value of nominated symbol\n"); | |
871 | printf("h this help\n"); | |
872 | printf("i insert value into symbol\n"); | |
873 | printf("j jam value into symbol\n"); | |
874 | printf("n new hashtable\n"); | |
875 | printf("r replace a value with another\n"); | |
876 | printf("s say what %% of table is used\n"); | |
877 | printf("q exit this program\n"); | |
878 | printf("x delete a symbol from table, report its value\n"); | |
879 | break; | |
880 | case 'i': | |
881 | p = hash_insert(h,name=what("symbol"),value=what("value")); | |
882 | if (*p) | |
883 | { | |
884 | printf("symbol=\"%s\" value=\"%s\" error=%s\n",name,value,p); | |
885 | } | |
886 | break; | |
887 | case 'j': | |
888 | p = hash_jam(h,name=what("symbol"),value=what("value")); | |
889 | if (*p) | |
890 | { | |
891 | printf("symbol=\"%s\" value=\"%s\" error=%s\n",name,value,p); | |
892 | } | |
893 | break; | |
894 | case 'n': | |
895 | h = hashtable[number] = (char *) hash_new(); | |
896 | break; | |
897 | case 'q': | |
898 | exit(); | |
899 | case 'r': | |
900 | p = hash_replace(h,name=what("symbol"),value=what("value")); | |
901 | printf("old value was \"%s\"\n",p?p:"{}"); | |
902 | break; | |
903 | case 's': | |
904 | hash_say(h,statbuf,STATBUFSIZE); | |
905 | for (ip=statbuf; ip<statbuf+STATBUFSIZE; ip++) | |
906 | { | |
907 | printf("%d ",*ip); | |
908 | } | |
909 | printf("\n"); | |
910 | break; | |
911 | case 'x': | |
912 | p = hash_delete(h,name=what("symbol")); | |
913 | printf("old value was \"%s\"\n",p?p:"{}"); | |
914 | break; | |
915 | default: | |
916 | printf("I can't understand command \"%c\"\n",command); | |
917 | break; | |
918 | } | |
919 | } | |
920 | } | |
921 | ||
922 | char * | |
923 | what(description) | |
924 | char * description; | |
925 | { | |
926 | char * retval; | |
927 | char * malloc(); | |
928 | ||
929 | printf(" %s : ",description); | |
930 | gets(answer); | |
931 | /* will one day clean up answer here */ | |
932 | retval = malloc(strlen(answer)+1); | |
933 | if (!retval) | |
934 | { | |
935 | error("room"); | |
936 | } | |
937 | (void)strcpy(retval,answer); | |
938 | return(retval); | |
939 | } | |
940 | ||
941 | char * | |
942 | destroy(string,value) | |
943 | char * string; | |
944 | char * value; | |
945 | { | |
946 | free(string); | |
947 | free(value); | |
948 | return(NULL); | |
949 | } | |
950 | ||
951 | ||
952 | char * | |
953 | applicatee(string,value) | |
954 | char * string; | |
955 | char * value; | |
956 | { | |
957 | printf("%.20s-%.20s\n",string,value); | |
958 | return(NULL); | |
959 | } | |
960 | ||
961 | whattable() /* determine number: what hash table to use */ | |
962 | /* also determine h: points to hash_control */ | |
963 | { | |
964 | ||
965 | for (;;) | |
966 | { | |
967 | printf(" what hash table (%d:%d) ? ",0,TABLES-1); | |
968 | gets(answer); | |
969 | sscanf(answer,"%d",&number); | |
970 | if (number>=0 && number<TABLES) | |
971 | { | |
972 | h = hashtable[number]; | |
973 | if (!h) | |
974 | { | |
975 | printf("warning: current hash-table-#%d. has no hash-control\n",number); | |
976 | } | |
977 | return; | |
978 | } | |
979 | else | |
980 | { | |
981 | printf("invalid hash table number: %d\n",number); | |
982 | } | |
983 | } | |
984 | } | |
985 | ||
986 | ||
987 | ||
988 | #endif /* #ifdef TEST */ | |
989 | ||
990 | /* end: hash.c */ |