Main Page | Class Hierarchy | Compound List | File List | Compound Members | File Members

hash_services Class Reference

This class provides low level support functions (e.g., hash value calculation) for the hash table element classes. More...

#include <hash_serv.h>

Inheritance diagram for hash_services:

Inheritance graph
[legend]
List of all members.

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).


Detailed Description

This class provides low level support functions (e.g., hash value calculation) for the hash table element classes.

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.


Constructor & Destructor Documentation

hash_services::hash_services  )  [inline]
 

Definition at line 31 of file hash_serv.h.

00031 {};

hash_services::~hash_services  )  [inline]
 

Definition at line 32 of file hash_serv.h.

00032 {};


Member Function Documentation

unsigned int hash_services::hash_value const char *  name  ) 
 

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

unsigned int hash_services::str_to_uint const char *  s  ) 
 

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


The documentation for this class was generated from the following files:
Generated on Wed Mar 31 21:16:06 2004 for Data Structures for a VHDL Compiler by doxygen 1.3.3