Crossings Minimization  1.0
hash.c
Go to the documentation of this file.
1 /**
2  * @file hash.c
3  * @brief Implementation of access functions for hash table.
4  * @author Matthias Stallmann
5  * @date 2008/12/21
6  * $Id: hash.c 2 2011-06-07 19:50:41Z mfms $
7  *
8  * Uses a polynomial hash function.
9  */
10 
11 #include"defs.h"
12 #include"hash.h"
13 #include<stdlib.h>
14 #include<stdio.h>
15 #include<string.h>
16 
17 #define LOAD_FACTOR 0.75
18 #define POLYNOMIAL_VALUE 37
19 #define MIN_TABLE_SIZE 8
20 
21 /**
22  * 2^k - 1 where k is chosen to give the right table size; this is also a the
23  * table size.
24  */
25 static unsigned int modulus;
26 
27 static Nodeptr * hash_table = NULL;
28 
29 // for statistics
30 static int number_of_probes = 0;
31 static int number_of_accesses = 0;
32 
33 /**
34  * Computes a suitable table size (modulus) based on a given desired number
35  * of entries. The choice used here is a power of two minus one.
36  */
37 static unsigned int getTableSize( int entries );
38 
39 /**
40  * Compute the reverse of a string
41  * @param reversed a buffer to hold the reversed version (destination)
42  * @param original the original string
43  */
44 static void reverse( char * reversed, const char * original );
45 
46 /**
47  * Calculates the hash value of a given node name. Overflow doesn't
48  * matter because this is supposed to be 'random' anyway.
49  * The name is reversed because most node names have common prefixes.
50  */
51 static unsigned int hashValue( const char * name );
52 
53 /**
54  * Computes an index into the table from the name.
55  */
56 static unsigned int hashIndex( const char * name );
57 
58 /**
59  * @param name The name of a node
60  * @return the index of the position in the hash table where the node has
61  * been found or of the first empty position after the hash value of the name.
62  */
63 static unsigned int getIndex( const char * name );
64 
65 #ifdef DEBUG
66 static void printHashTable();
67 #endif
68 
69 void initHashTable( int number_of_items )
70 {
71  modulus = getTableSize( number_of_items );
72  hash_table = (Nodeptr *) calloc( modulus, sizeof(Nodeptr) );
73  // the following is not really necessary since calloc fills the allocated
74  // memory with 0's, but it doesn't hurt to be careful
75  int i = 0;
76  for( ; i < modulus; i++ ) hash_table[i] = NULL;
77  number_of_probes = 0;
79 }
80 
81 void insertInHashTable( const char * name, Nodeptr node )
82 {
83  unsigned int index = getIndex( name );
84  if( hash_table[index] != NULL )
85  {
86  fprintf( stderr, "insertInHashTable: Entry for '%s' already exists\n",
87  name );
88  abort();
89  }
90  hash_table[index] = node;
91 #ifdef DEBUG
92  printf("*** insert: name='%s' node->name='%s' position=%u"
93  " index=%u value=%u\n",
94  name, node->name, hashIndex(name), index, hashValue(name) );
95  printHashTable();
96  printf("***\n");
97 #endif
98 }
99 
100 Nodeptr getFromHashTable( const char * name )
101 {
102  unsigned int index = getIndex( name );
103  return hash_table[index];
104 }
105 
107 {
108  free(hash_table);
109 }
110 
112 {
113  return ((double) number_of_probes) / number_of_accesses;
114 }
115 
116 #ifdef DEBUG
117 static void printHashTable()
118 {
119  printf("--\n hash_table, size = %u\n", modulus);
120  int i = 0;
121  for( ; i < modulus; i++ )
122  {
123  if( hash_table[i] == NULL ) printf(" 0\n");
124  else printf(" %4d: '%s' position=%u index=%u value=%u\n",
125  i, hash_table[i]->name,
126  hashIndex( hash_table[i]->name ),
127  getIndex( hash_table[i]->name ),
128  hashValue( hash_table[i]->name )
129  );
130  }
131  printf("--\n");
132 }
133 #endif
134 
135 static unsigned int getTableSize( int entries )
136 {
137  int target_value = (int) (entries / LOAD_FACTOR);
138  unsigned int table_size = MIN_TABLE_SIZE;
139  for( ; table_size < target_value; table_size *= 2 );
140  return table_size - 1;
141 }
142 
143 static void reverse( char * reversed, const char * original )
144 {
145  char * rev_ptr = reversed;
146  const char * org_ptr = original + strlen(original) - 1;
147  // store the reverse of the string in buffer
148  for( ; org_ptr >= original; org_ptr-- )
149  {
150  * rev_ptr++ = * org_ptr;
151  }
152  * rev_ptr = '\0';
153 }
154 
155 static unsigned int hashValue( const char * name )
156 {
157  char rev_buf[MAX_NAME_LENGTH];
158  reverse( rev_buf, name );
159  char * rev_ptr = rev_buf;
160  unsigned int value = 0;
161  for( ; * rev_ptr != '\0'; rev_ptr++ )
162  {
163  value = (value + POLYNOMIAL_VALUE * value + * rev_ptr);
164  }
165  return value;
166 }
167 
168 static unsigned int hashIndex( const char * name )
169 {
170  return hashValue( name ) % modulus;
171 }
172 
173 static unsigned int getIndex( const char * name )
174 {
176  unsigned int index = hashIndex( name );
178  while( hash_table[ index ] != NULL
179  && strcmp( name, hash_table[ index ]->name ) != 0 )
180  {
181  index = (index + 1) % modulus;
183  }
184  return index;
185 }
186 
187 #ifdef TEST
188 int main()
189 {
190  initHashTable( 7 );
191  char name[MAX_NAME_LENGTH];
192  fgets( name, MAX_NAME_LENGTH, stdin );
193  name[ strlen(name) - 1 ] = '\0';
194  Nodeptr new_node = (Nodeptr) malloc( sizeof(struct node_struct));
195  new_node->name = (char *) malloc( strlen(name) + 1 );
196  strcpy( new_node->name, name );
197  insertInHashTable( name, new_node );
198  return 0;
199 }
200 #endif
201 
202 /* [Last modified: 2008 12 29 at 16:35:13 GMT] */
static void reverse(char *reversed, const char *original)
Definition: hash.c:143
#define LOAD_FACTOR
Definition: hash.c:17
static int number_of_probes
Definition: hash.c:30
char * name
Definition: graph.h:63
static unsigned int hashValue(const char *name)
Definition: hash.c:155
A simple map based on a hash table, maps names to node pointers.
Definitions common to all edge crossing heuristic source files.
static Nodeptr * hash_table
Definition: hash.c:27
#define MIN_TABLE_SIZE
Definition: hash.c:19
struct node_struct * Nodeptr
Definition: graph.h:57
#define POLYNOMIAL_VALUE
Definition: hash.c:18
static unsigned int hashIndex(const char *name)
Definition: hash.c:168
void insertInHashTable(const char *name, Nodeptr node)
Definition: hash.c:81
static unsigned int modulus
Definition: hash.c:25
static int number_of_accesses
Definition: hash.c:31
void initHashTable(int number_of_items)
Definition: hash.c:69
static unsigned int getTableSize(int entries)
Definition: hash.c:135
Nodeptr getFromHashTable(const char *name)
Definition: hash.c:100
#define MAX_NAME_LENGTH
Definition: defs.h:32
static unsigned int getIndex(const char *name)
Definition: hash.c:173
void removeHashTable()
Definition: hash.c:106
double getAverageNumberOfProbes()
Definition: hash.c:111
int main(int argc, char *argv[])
Definition: add_edges.c:185