VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
hash.c File Reference
#include <stdlib.h>
#include <string.h>
#include "hash.h"
#include "util.h"
+ Include dependency graph for hash.c:

Go to the source code of this file.

Functions

struct s_hash ** alloc_hash_table (void)
 
void free_hash_table (struct s_hash **hash_table)
 
struct s_hash_iterator start_hash_table_iterator (void)
 
struct s_hashget_next_hash (struct s_hash **hash_table, struct s_hash_iterator *hash_iterator)
 
struct s_hashinsert_in_hash_table (struct s_hash **hash_table, char *name, int next_free_index)
 
struct s_hashget_hash_entry (struct s_hash **hash_table, char *name)
 
int hash_value (char *name)
 
void get_hash_stats (struct s_hash **hash_table, char *hash_table_name)
 

Function Documentation

struct s_hash** alloc_hash_table ( void  )

Definition at line 7 of file hash.c.

7  {
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 }
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
#define HASHSIZE
Definition: hash.h:1
Definition: hash.h:3

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void free_hash_table ( struct s_hash **  hash_table)

Definition at line 18 of file hash.c.

18  {
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 }
char * name
Definition: hash.h:4
#define HASHSIZE
Definition: hash.h:1
struct s_hash * next
Definition: hash.h:7
Definition: hash.h:3

+ Here is the caller graph for this function:

struct s_hash* get_hash_entry ( struct s_hash **  hash_table,
char *  name 
)

Definition at line 119 of file hash.c.

119  {
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 }
int hash_value(char *name)
Definition: hash.c:140
char * name
Definition: hash.h:4
struct s_hash * next
Definition: hash.h:7
Definition: hash.h:3

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void get_hash_stats ( struct s_hash **  hash_table,
char *  hash_table_name 
)

Definition at line 160 of file hash.c.

160  {
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 }
#define HASHSIZE
Definition: hash.h:1
struct s_hash * next
Definition: hash.h:7
messagelogger vpr_printf
Definition: util.c:17
Definition: hash.h:3

+ Here is the caller graph for this function:

struct s_hash* get_next_hash ( struct s_hash **  hash_table,
struct s_hash_iterator hash_iterator 
)

Definition at line 51 of file hash.c.

51  {
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 }
#define HASHSIZE
Definition: hash.h:1
struct s_hash * next
Definition: hash.h:7
Definition: hash.h:3
struct s_hash * h_ptr
Definition: hash.h:21

+ Here is the caller graph for this function:

int hash_value ( char *  name)

Definition at line 140 of file hash.c.

140  {
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 }
char * name
Definition: hash.h:4
#define HASHSIZE
Definition: hash.h:1

+ Here is the caller graph for this function:

struct s_hash* insert_in_hash_table ( struct s_hash **  hash_table,
char *  name,
int  next_free_index 
)

Definition at line 76 of file hash.c.

77  {
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 }
int count
Definition: hash.h:6
int index
Definition: hash.h:5
int hash_value(char *name)
Definition: hash.c:140
char * name
Definition: hash.h:4
static void * my_malloc(int ibytes)
Definition: graphics.c:499
struct s_hash * next
Definition: hash.h:7
Definition: hash.h:3

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

struct s_hash_iterator start_hash_table_iterator ( void  )

Definition at line 38 of file hash.c.

38  {
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 }

+ Here is the caller graph for this function: