VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
hash.c
Go to the documentation of this file.
1 #include <stdlib.h>
2 #include <string.h>
3 #include "hash.h"
4 #include "util.h"
5 
6 struct s_hash **
8 
9  /* Creates a hash table with HASHSIZE different locations (hash values). */
10 
11  struct s_hash **hash_table;
12 
13  hash_table = (struct s_hash **) my_calloc(sizeof(struct s_hash *),
14  HASHSIZE);
15  return (hash_table);
16 }
17 
18 void free_hash_table(struct s_hash **hash_table) {
19 
20  /* Frees all the storage associated with a hash table. */
21 
22  int i;
23  struct s_hash *h_ptr, *temp_ptr;
24 
25  for (i = 0; i < HASHSIZE; i++) {
26  h_ptr = hash_table[i];
27  while (h_ptr != NULL) {
28  free(h_ptr->name);
29  temp_ptr = h_ptr->next;
30  free(h_ptr);
31  h_ptr = temp_ptr;
32  }
33  }
34 
35  free(hash_table);
36 }
37 
39 
40  /* Call this routine before you start going through all the elements in *
41  * a hash table. It sets the internal indices to the start of the table. */
42 
43  struct s_hash_iterator hash_iterator;
44 
45  hash_iterator.i = -1;
46  hash_iterator.h_ptr = NULL;
47  return (hash_iterator);
48 }
49 
50 struct s_hash *
51 get_next_hash(struct s_hash **hash_table, struct s_hash_iterator *hash_iterator) {
52 
53  /* Returns the next occupied hash entry, and moves the iterator structure *
54  * forward so the next call gets the next entry. */
55 
56  int i;
57  struct s_hash *h_ptr;
58 
59  i = hash_iterator->i;
60  h_ptr = hash_iterator->h_ptr;
61 
62  while (h_ptr == NULL) {
63  i++;
64  if (i >= HASHSIZE)
65  return (NULL); /* End of table */
66 
67  h_ptr = hash_table[i];
68  }
69 
70  hash_iterator->h_ptr = h_ptr->next;
71  hash_iterator->i = i;
72  return (h_ptr);
73 }
74 
75 struct s_hash *
76 insert_in_hash_table(struct s_hash **hash_table, char *name,
77  int next_free_index) {
78 
79  /* Adds the string pointed to by name to the hash table, and returns the *
80  * hash structure created or updated. If name is already in the hash table *
81  * the count member of that hash element is incremented. Otherwise a new *
82  * hash entry with a count of zero and an index of next_free_index is *
83  * created. */
84 
85  int i;
86  struct s_hash *h_ptr, *prev_ptr;
87 
88  i = hash_value(name);
89  prev_ptr = NULL;
90  h_ptr = hash_table[i];
91 
92  while (h_ptr != NULL) {
93  if (strcmp(h_ptr->name, name) == 0) {
94  h_ptr->count++;
95  return (h_ptr);
96  }
97 
98  prev_ptr = h_ptr;
99  h_ptr = h_ptr->next;
100  }
101 
102  /* Name string wasn't in the hash table. Add it. */
103 
104  h_ptr = (struct s_hash *) my_malloc(sizeof(struct s_hash));
105  if (prev_ptr == NULL) {
106  hash_table[i] = h_ptr;
107  } else {
108  prev_ptr->next = h_ptr;
109  }
110  h_ptr->next = NULL;
111  h_ptr->index = next_free_index;
112  h_ptr->count = 1;
113  h_ptr->name = (char *) my_malloc((strlen(name) + 1) * sizeof(char));
114  strcpy(h_ptr->name, name);
115  return (h_ptr);
116 }
117 
118 struct s_hash *
119 get_hash_entry(struct s_hash **hash_table, char *name) {
120 
121  /* Returns the hash entry with this name, or NULL if there is no *
122  * corresponding entry. */
123 
124  int i;
125  struct s_hash *h_ptr;
126 
127  i = hash_value(name);
128  h_ptr = hash_table[i];
129 
130  while (h_ptr != NULL) {
131  if (strcmp(h_ptr->name, name) == 0)
132  return (h_ptr);
133 
134  h_ptr = h_ptr->next;
135  }
136 
137  return (NULL);
138 }
139 
140 int hash_value(char *name) {
141  /* Creates a hash key from a character string. The absolute value is taken *
142  * for the final val to compensate for long strlen that cause val to *
143  * overflow. */
144 
145  int i;
146  int val = 0, mult = 1;
147 
148  i = strlen(name);
149  for (i = strlen(name) - 1; i >= 0; i--) {
150  val += mult * ((int) name[i]);
151  mult *= 7;
152  }
153  val += (int) name[0];
154  val %= HASHSIZE;
155 
156  val = abs(val);
157  return (val);
158 }
159 
160 void get_hash_stats(struct s_hash **hash_table, char *hash_table_name){
161 
162  /* Checks to see how well elements are distributed within the hash table. *
163  * Will traverse through the hash_table and count the length of the linked *
164  * list. Will output the hash number, the number of array elements that are *
165  * NULL, the average number of linked lists and the maximum length of linked *
166  * lists. */
167 
168  int num_NULL = 0, total_elements = 0, max_num = 0, curr_num;
169  double avg_num = 0;
170  int i;
171  struct s_hash *h_ptr;
172 
173  for (i = 0; i<HASHSIZE; i++){
174  h_ptr = hash_table[i];
175  curr_num = 0;
176 
177  if (h_ptr == NULL)
178  num_NULL++;
179  else{
180  while (h_ptr != NULL){
181  curr_num ++;
182  h_ptr = h_ptr->next;
183  }
184  }
185 
186  if (curr_num > max_num)
187  max_num = curr_num;
188 
189  total_elements = total_elements + curr_num;
190  }
191 
192  avg_num = (float) total_elements / ((float)HASHSIZE - (float)num_NULL);
193 
194  vpr_printf(TIO_MESSAGE_INFO, "\n");
195  vpr_printf(TIO_MESSAGE_INFO, "The hash table '%s' is of size %d.\n",
196  hash_table_name, HASHSIZE);
197  vpr_printf(TIO_MESSAGE_INFO, "It has: %d keys that are never used; total of %d elements; an average linked-list length of %.1f; and a maximum linked-list length of %d.\n",
198  num_NULL, total_elements, avg_num, max_num);
199  vpr_printf(TIO_MESSAGE_INFO, "\n");
200 }
struct s_hash ** alloc_hash_table(void)
Definition: hash.c:7
struct s_hash_iterator start_hash_table_iterator(void)
Definition: hash.c:38
int count
Definition: hash.h:6
int index
Definition: hash.h:5
struct s_hash * get_hash_entry(struct s_hash **hash_table, char *name)
Definition: hash.c:119
int hash_value(char *name)
Definition: hash.c:140
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
char * name
Definition: hash.h:4
#define HASHSIZE
Definition: hash.h:1
void free_hash_table(struct s_hash **hash_table)
Definition: hash.c:18
static void * my_malloc(int ibytes)
Definition: graphics.c:499
struct s_hash * next
Definition: hash.h:7
struct s_hash * get_next_hash(struct s_hash **hash_table, struct s_hash_iterator *hash_iterator)
Definition: hash.c:51
messagelogger vpr_printf
Definition: util.c:17
struct s_hash * insert_in_hash_table(struct s_hash **hash_table, char *name, int next_free_index)
Definition: hash.c:76
Definition: hash.h:3
void get_hash_stats(struct s_hash **hash_table, char *hash_table_name)
Definition: hash.c:160
struct s_hash * h_ptr
Definition: hash.h:21