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