#include <hash_serv.h>
Inheritance diagram for hash_services:
Public Member Functions | |
hash_services () | |
~hash_services () | |
unsigned int | str_to_uint (const char *s) |
This function is passed a string. | |
unsigned int | hash_value (const char *name) |
Use a shift algorithm to distribute the key (e.g., make it more pseudo-random). |
The hash table is defined by a template and the element classes are the classes that are used in instantiating the hash table. These classes must all provide certain class functions, which in turn make use of functions provided by this class.
Definition at line 29 of file hash_serv.h.
|
Definition at line 31 of file hash_serv.h.
00031 {}; |
|
Definition at line 32 of file hash_serv.h.
00032 {}; |
|
Use a shift algorithm to distribute the key (e.g., make it more pseudo-random). I actually tried several different algorithms to do this and this one worked the best. It was suggested by Brent Gregory at Synopsys, although any mistakes in translating his suggestion to code are mine. The code below is a loop, which has been in-lined for speed. Definition at line 67 of file hash_serv.C. References str_to_uint(). Referenced by symtable::enter_sym(), strtable::find_string(), and symtable::find_sym().
00068 { 00069 unsigned int val, new_val; 00070 00071 val = str_to_uint( name ); 00072 00073 new_val = val ^ (val << 1); 00074 new_val = new_val ^ (val << 2); 00075 new_val = new_val ^ (val << 3); 00076 new_val = new_val ^ (val << 4); 00077 new_val = new_val ^ (val << 5); 00078 new_val = new_val ^ (val << 6); 00079 new_val = new_val ^ (val << 7); 00080 new_val = new_val ^ (val << 8); 00081 new_val = new_val ^ (val << 9); 00082 new_val = new_val ^ (val << 10); 00083 new_val = new_val ^ (val << 11); 00084 new_val = new_val ^ (val << 12); 00085 new_val = new_val ^ (val << 13); 00086 new_val = new_val ^ (val << 14); 00087 new_val = new_val ^ (val << 15); 00088 new_val = new_val ^ (val << 16); 00089 00090 return new_val; // adjust for hash table size 00091 } // hash_value |
|
This function is passed a string. It returns a hash key formed from the string. An attempt is made to make this key as unique as possible. Definition at line 28 of file hash_serv.C. References SIZE_INT. Referenced by hash_value().
00029 { 00030 int i, byte_ix, word_cnt; 00031 char c; 00032 union { 00033 unsigned char c[ SIZE_INT ]; 00034 unsigned int u; 00035 } val; 00036 00037 val.u = 0; 00038 word_cnt = 0; 00039 for (i = 0, byte_ix = 0; i < strlen( s ); i++, byte_ix = (byte_ix + 1) % SIZE_INT) { 00040 if (i > 0 && (i % SIZE_INT) == 0) { 00041 word_cnt++; 00042 } 00043 c = s[ i ]; 00044 // Every odd word, shift the character up by one bit 00045 // It turns out that this makes a big difference in the 00046 // uniqueness of the key generated from a string 00047 if (word_cnt & 0x1) { 00048 c = c << 1; 00049 } 00050 val.c[ byte_ix ] ^= c; 00051 } 00052 00053 return val.u; 00054 } // str_to_uint |