1 /*
2 ** C implementation of a hash table ADT
3 */
4 typedef enum tagReturnCode {SUCCESS, FAIL} ReturnCode;
5
6
7 typedef struct tagEntry
8 {
9 char* key;
10 char* value;
11 } Entry;
12
13
14
15 typedef struct tagNode
16 {
17 Entry* entry;
18
19 struct tagNode* next;
20 } Node;
21
22
23 typedef struct tagHash
24 {
25 unsigned int table_size;
26
27 Node** heads;
28
29 } Hash;
30
31
hash_func(const char * str,unsigned int table_size)32 static unsigned int hash_func(const char* str, unsigned int table_size)
33 {
34 unsigned int hash_value;
35 unsigned int a = 127;
36
37 for (hash_value = 0; *str != 0; ++str)
38 hash_value = (a*hash_value + *str) % table_size;
39
40 return hash_value;
41 }
42
43
HashCreate(Hash ** hash,unsigned int table_size)44 ReturnCode HashCreate(Hash** hash, unsigned int table_size)
45 {
46 unsigned int i;
47
48 if (table_size < 1)
49 return FAIL;
50
51 //
52 // Allocate space for the Hash
53 //
54 if (((*hash) = malloc(sizeof(**hash))) == NULL)
55 return FAIL;
56
57 //
58 // Allocate space for the array of list heads
59 //
60 if (((*hash)->heads = malloc(table_size*sizeof(*((*hash)->heads)))) == NULL)
61 return FAIL;
62
63 //
64 // Initialize Hash info
65 //
66 for (i = 0; i < table_size; ++i)
67 {
68 (*hash)->heads[i] = NULL;
69 }
70
71 (*hash)->table_size = table_size;
72
73 return SUCCESS;
74 }
75
76
HashInsert(Hash * hash,const Entry * entry)77 ReturnCode HashInsert(Hash* hash, const Entry* entry)
78 {
79 unsigned int index = hash_func(entry->key, hash->table_size);
80 Node* temp = hash->heads[index];
81
82 HashRemove(hash, entry->key);
83
84 if ((hash->heads[index] = malloc(sizeof(Node))) == NULL)
85 return FAIL;
86
87 hash->heads[index]->entry = malloc(sizeof(Entry));
88 hash->heads[index]->entry->key = malloc(strlen(entry->key)+1);
89 hash->heads[index]->entry->value = malloc(strlen(entry->value)+1);
90 strcpy(hash->heads[index]->entry->key, entry->key);
91 strcpy(hash->heads[index]->entry->value, entry->value);
92
93 hash->heads[index]->next = temp;
94
95 return SUCCESS;
96 }
97
98
99
HashFind(const Hash * hash,const char * key)100 const Entry* HashFind(const Hash* hash, const char* key)
101 {
102 unsigned int index = hash_func(key, hash->table_size);
103 Node* temp = hash->heads[index];
104
105 while (temp != NULL)
106 {
107 if (!strcmp(key, temp->entry->key))
108 return temp->entry;
109
110 temp = temp->next;
111 }
112
113 return NULL;
114 }
115
116
HashRemove(Hash * hash,const char * key)117 ReturnCode HashRemove(Hash* hash, const char* key)
118 {
119 unsigned int index = hash_func(key, hash->table_size);
120 Node* temp1 = hash->heads[index];
121 Node* temp2 = temp1;
122
123 while (temp1 != NULL)
124 {
125 if (!strcmp(key, temp1->entry->key))
126 {
127 if (temp1 == hash->heads[index])
128 hash->heads[index] = hash->heads[index]->next;
129 else
130 temp2->next = temp1->next;
131
132 free(temp1->entry->key);
133 free(temp1->entry->value);
134 free(temp1->entry);
135 free(temp1);
136 temp1 = NULL;
137
138 return SUCCESS;
139 }
140
141 temp2 = temp1;
142 temp1 = temp1->next;
143 }
144
145 return FAIL;
146 }
147
148
HashPrint(Hash * hash,void (* PrintFunc)(char *,char *))149 void HashPrint(Hash* hash, void (*PrintFunc)(char*, char*))
150 {
151 unsigned int i;
152
153 if (hash == NULL || hash->heads == NULL)
154 return;
155
156 for (i = 0; i < hash->table_size; ++i)
157 {
158 Node* temp = hash->heads[i];
159
160 while (temp != NULL)
161 {
162 PrintFunc(temp->entry->key, temp->entry->value);
163 temp = temp->next;
164 }
165 }
166 }
167
168
169
HashDestroy(Hash * hash)170 void HashDestroy(Hash* hash)
171 {
172 unsigned int i;
173
174 if (hash == NULL)
175 return;
176
177 for (i = 0; i < hash->table_size; ++i)
178 {
179 Node* temp = hash->heads[i];
180
181 while (temp != NULL)
182 {
183 Node* temp2 = temp;
184
185 free(temp->entry->key);
186 free(temp->entry->value);
187 free(temp->entry);
188
189 temp = temp->next;
190
191 free(temp2);
192 }
193 }
194
195 free(hash->heads);
196 hash->heads = NULL;
197
198 free(hash);
199 }
200
201