fi66t5GZ

1// Exercise 2b. Hash Tables - Dynamic 2D Array version
2// Created by Russell Sammut-Bonnici on 23/12/2017.
3// CPS1011
4
5#include "hashTable.h"
6
7//creating a struct Pair to store HashTable's values and keys
8typedef struct pair{
9    const char * key; //the key to be inputted
10    const char * value; //the value to be inputted
11}Pair;
12
13//creating struct for linked list including its head
14typedef struct bucket{
15    Pair ** pair; //pointer to data that is in pair
16    int max_c; //max collision aka no. of columns  (grows dynamically)
17}Bucket;
18
19//creating struct for hashTable including pointer to row and hashSpace size
20typedef struct hashTable{
21    Bucket ** bucket; //double pointer to the beginning of the row
22    int hashSpace; //size of the hashTable
23}HashTable;
24
25//main method
26int main(){
27
28    //create and initialize hashTable3 with the initial hashSpace 20
29    HashTable * hashTable2 = createHashTable_D(10);
30
31    //initializing array to store string key inputs (in this case IDs)
32    char *key1[INPUT_AMOUNT]={"0426298M","0326288M","0134566M","0987654M","0234211M",
33                              "0423458M","0234288M","0134098M","0456654M","0214211M",
34                              "2345698M","0678348M","0223366M","0999954M","0121211M",
35                              "0010108M","0234018M","0014098M","0972654M","0211111M"};
36
37    //initializing array to store string value inputs (in this case Mobile No.s)
38    char *value1[INPUT_AMOUNT]={"79835334","99887766","79856342","99223344","79887766",
39                                "79567834","99333366","79111112","99113114","79000000",
40                                "79835335","79835337","79835336","99222332","79563366",
41                                "79874534","95692366","79109422","92376314","79000943"};
42
43    //inserts keys and values into hashTable demonstrating insertion
44    for(int i=0;i<INPUT_AMOUNT;i++) //loops for every pair input
45        insertPair(hashTable2,key1[i],value1[i]);
46
47    printf("\n");
48
49    //deletes a specified pair in hashTable by scanning through list demonstrating deletion
50    deletePair(hashTable2,"0972654M"); //deletes pair (which is "0972654M","92376314")
51
52    printf("\n");
53
54    //checks if key "0326288M" exists, returns 1 since it exists, demonstrating look up
55    printf("Look up of key: \"%s\". Return value: %d\n","0326288M",checkExists(hashTable2,"0326288M"));
56
57    printf("\n");
58
59    //saves hashTable to disk as fileName
60    saveHashTableAs(hashTable2,"hashTable2.dat");
61
62    printf("\n");
63
64    //loads "hashTable1" from disk by fileName and adds to hashTable
65    loadHashTableTo("hashTable1.dat",hashTable2);
66
67    printf("\n");
68
69    //frees data in hashTable
70    freeHashTable(hashTable2);
71
72
73    return 0;
74}
75
76//initializes hashTable and allocates requested space from hashSpace
77HashTable * createHashTable_D(unsigned int hashSpace){
78
79    //allocating space for hashTable which is just 1 item
80    HashTable * hashTable = calloc(1,sizeof(hashTable));
81
82    //allocating space for number of rows, which are equal to the hashSpace
83    hashTable->bucket= calloc(hashSpace, sizeof(Bucket));
84    hashTable->hashSpace = hashSpace; //store hashSpace in hashTable
85
86    return hashTable; //returns created hash Table
87}
88
89//method that inserts pair into created hashTable
90int insertPair(HashTable * hashTable,const char * key, const char * value){
91
92    int hashValue = hashFunction_D(hashTable,key); //calculate hashValue
93
94    if(hashTable->bucket[hashValue]==NULL){//if bucket doesnt exist
95
96        hashTable->bucket[hashValue] = malloc(sizeof(Bucket)); //allocate mem for new bucket
97
98        if (hashTable->bucket[hashValue] == NULL) { //error check
99            printf("Failed to allocate memory for new bucket at hashValue: %d.",hashValue);
100            return 1;//fail
101        }
102
103        hashTable->bucket[hashValue]->max_c = INITIAL_MAX_C; //max collisions set initially to 3
104        hashTable->bucket[hashValue]->pair = calloc(INITIAL_MAX_C, sizeof(Pair)); //allocate mem for three pairs in bucket
105
106        if (hashTable->bucket[hashValue]->pair == NULL) { //error check
107            printf("Failed to allocate memory for array of pairs at hashValue: %d.",hashValue);
108            return 1;//fail
109        }
110
111        hashTable->bucket[hashValue]->pair[0] = malloc(sizeof(Pair)); //allocate mem for first pair
112        hashTable->bucket[hashValue]->pair[0]->key = key; //set key of first pair
113        hashTable->bucket[hashValue]->pair[0]->value = value; //set value of first pair
114
115    }else if(hashTable->bucket[hashValue]!=NULL){ //if bucket exists
116
117        int c=0; //collision counter to count amount of collisions in bucket when inserting
118
119        while(hashTable->bucket[hashValue]->pair[c]!=NULL){ //while pair exists
120            c++; //increment collision counter
121        }
122
123        if(c<INITIAL_MAX_C){ //if c is less than max initial collisions
124            hashTable->bucket[hashValue]->pair[c] = malloc(sizeof(Pair)); //allocate mem for pair
125            hashTable->bucket[hashValue]->pair[c]->key = key; //set key after last collision
126            hashTable->bucket[hashValue]->pair[c]->value = value; //set value after last collision
127
128        }else{ //if c is equal to the initial max collisions, no space for new pair, bucket needs to dynamically grow
129
130            //reallocate to add one new column to the bucket for the new pair
131            hashTable->bucket[hashValue] = realloc(hashTable->bucket[hashValue],sizeof(Bucket)*hashTable->bucket[hashValue]->max_c+1);
132            hashTable->bucket[hashValue]->max_c++; //max collision grows by 1
133            hashTable->bucket[hashValue]->pair[c] = malloc(sizeof(Pair)); //allocate mem for pair
134            hashTable->bucket[hashValue]->pair[c]->key = key; //set key at newly added column
135            hashTable->bucket[hashValue]->pair[c]->value = value; //set value at newly added column
136        }
137
138    }
139
140    printf("Pair of key: \"%s\" and value: \"%s\" was successfully inserted into the hashTable, hashValue: %d.\n",key,value,hashValue);
141
142}
143
144//method for hashFunction_D, accepts key and value as arguments
145int hashFunction_D(HashTable * hashTable, const char * keyIn){
146
147    int charSumKey = 0; //sum of the ASCII code of characters in key
148    int x; //variable to be returned
149    int size = hashTable->hashSpace; //sets size to hashSpace of table
150
151    //accumulates sum of ASCII code of each character
152    for(int i=0;i<strlen(keyIn);i++) {
153        charSumKey += keyIn[i];
154    }
155
156    x = charSumKey % size; //invented formula for hash function
157    return x;
158}
159
160int deletePair(HashTable * hashTable, const char * key){
161
162    int hashValue = hashFunction_D(hashTable,key); //get hashValue
163
164    if(checkExists(hashTable,key)==1){ //if exists, delete pair
165
166        int c = 0; //counter for collision index
167        int stop = 0; //to break from loop from if statement
168        Bucket *scan = hashTable->bucket[hashValue];
169
170        while(scan!=NULL && stop!=1){ //scans through list until match to delete is found
171
172            if(strcmp(hashTable->bucket[hashValue]->pair[0]->key,key)==0){ //if match found at head
173
174                if(hashTable->bucket[hashValue]->pair[1]==NULL){ //if head to delete is the only node in the bucket delete head then bucket
175
176                    hashTable->bucket[hashValue]->pair[0]->key=NULL;
177                    hashTable->bucket[hashValue]->pair[0]->value=NULL;
178                    free(hashTable->bucket[hashValue]->pair[0]);
179                    free(hashTable->bucket[hashValue]->pair);
180                    free(hashTable->bucket[hashValue]);
181
182                }else if(hashTable->bucket[hashValue]->pair[1]!=NULL){ //if there is more than just one node in the list, shift rest to left then delete last
183
184                    while(scan->pair[c]!=NULL) { //while current node exists
185
186                        if (scan->pair[c + 1] != NULL) { //if next node exists
187
188                            scan->pair[c]->key = scan->pair[c + 1]->key; //copy, from next node to key
189                            scan->pair[c]->value = scan->pair[c + 1]->value; //copy, from next node to value
190
191                        }else{ //if next node doesn't exist (at end of list)
192
193                            hashTable->bucket[hashValue]->pair[c]->key=NULL;
194                            hashTable->bucket[hashValue]->pair[c]->value=NULL;
195                            free(scan->pair[c]); //delete last element
196
197                            //reallocate to shorten bucket
198                            hashTable->bucket[hashValue] = realloc(hashTable->bucket[hashValue],sizeof(Bucket)*hashTable->bucket[hashValue]->max_c-1);
199                            hashTable->bucket[hashValue]->max_c--; //max collision shrinks by 1
200
201                        }
202
203                        c++; //increment counter
204
205                    }
206                }
207
208                printf("Deletion of key: \"%s\" was successful at head.\n",key);
209                stop=1; //stop scanning for match
210
211            }else if(strcmp(scan->pair[c]->key,key)==0 && scan->pair[c+1]!=NULL){//if match found in middle, shift everything after it to the left
212
213                while(scan->pair[c]!=NULL) { //while current node exists
214
215                    if (scan->pair[c + 1] != NULL) { //if next node exists
216
217                        scan->pair[c]->key = scan->pair[c + 1]->key; //copy, from next node to key
218                        scan->pair[c]->value = scan->pair[c + 1]->value; //copy, from next node to value
219
220                    }else{ //if next node doesn't exist (at end of list)
221
222                        hashTable->bucket[hashValue]->pair[c]->key=NULL;
223                        hashTable->bucket[hashValue]->pair[c]->value=NULL;
224                        free(scan->pair[c]); //delete last element
225
226                        //reallocate to shorten bucket
227                        hashTable->bucket[hashValue] = realloc(hashTable->bucket[hashValue],sizeof(Bucket)*hashTable->bucket[hashValue]->max_c-1);
228                        hashTable->bucket[hashValue]->max_c--; //max collision shrinks by 1
229
230                    }
231
232                    c++; //increment counter
233
234                }
235
236                printf("Deletion of key: \"%s\" was successful in middle.\n",key);
237                stop=1; //stop scanning for match
238
239            }else if(strcmp(scan->pair[c]->key,key)==0 && scan->pair[c+1]==NULL){//if match found at end
240
241                hashTable->bucket[hashValue]->pair[c]->key=NULL;
242                hashTable->bucket[hashValue]->pair[c]->value=NULL;
243                free(scan->pair[c]); //delete last element
244
245                //reallocate to shorten bucket
246                hashTable->bucket[hashValue] = realloc(hashTable->bucket[hashValue],sizeof(Bucket)*hashTable->bucket[hashValue]->max_c-1);
247                hashTable->bucket[hashValue]->max_c--; //max collision shrinks by 1
248
249                printf("Deletion of key: \"%s\" was successful.\n",key);
250                stop=1; //stop scanning for match
251
252            }else { //if match not found
253                c++; //increment c
254            }
255
256        }
257
258    }
259
260
261}
262
263//method that looks up key and checks if it exists in the hashTable, returns 1 when exists
264int checkExists(HashTable * hashTable, const char * key){
265
266    int hashValue = hashFunction_D(hashTable,key); //get hashValue
267
268    if(hashTable->bucket[hashValue]==NULL){//checks if bucket of hashValue exists
269        printf("Error: the key's hashValue does not own any existing bucket.\n");
270        return 0;
271    }else{ //goes through bucket
272
273        int c = 0; //collision index counter
274        Pair *scan = hashTable->bucket[hashValue]->pair[c];
275
276        while(scan!=NULL){ //loops to last node in the bucket (which can be the first pair)
277
278            if(strcmp(scan->key,key)==0){
279
280                return 1; //exists
281
282            }
283
284            c++; //increment c
285            scan = hashTable->bucket[hashValue]->pair[c]; //goes to next column
286
287        }
288
289        //at this point it has reached the end of the bucket without finding any match
290        printf("Error: the key's hashValue does not own an existing list.\n");
291        return 0;
292
293    }
294
295}
296
297//method that saves hashTable to structured text file
298int saveHashTableAs(HashTable * hashTable,const char * fileName){
299
300    FILE *f;
301    f = fopen(fileName,"w"); //opens new file to write to
302    if(f!=NULL) {
303
304        //loop by row
305        for (int i = 0; i < hashTable->hashSpace; i++) {
306
307            if(hashTable->bucket[i]!=NULL) { //if bucket exists
308
309                Bucket *scan = hashTable->bucket[i];
310                int c=0; //collision counter index initialised
311
312                //navigate to the end of the bucket (can be the head)
313                while (scan->pair[c]!=NULL) {
314
315                    fprintf(f, "%s,%s", scan->pair[c]->key, scan->pair[c]->value);
316                    fprintf(f, "\t"); //new column
317
318                    c++; //increment c
319                }
320            }
321
322            fprintf(f,"\n"); //new row
323        }
324
325
326        printf("Hash table saved successfully to \"%s\"\n", fileName);
327    }
328}
329
330//method that loads hashTable setting it to the current hashTable
331int loadHashTableTo(const char *fileName,HashTable * hashTable){
332
333    char ch; //temporarily stores character from file
334    char string[1000]=""; //initialized string to temporarily hold text for scanning to max 1000 characters
335
336    char word[30] = {'\0'};
337
338    char key[30] = {'\0'}; //initialized to temporarily store key, max characters set to 30
339    char value[30] = {'\0'}; //initialized to temporarily store key, max characters set to 30
340
341    int i=0; //counts characters for string
342    int j = 0; //counts characters for word
343
344    FILE *f;
345    f = fopen(fileName,"r"); //opens new file to write to
346
347    //Reading input text file using file pointer and methods from <string.h>
348    if(f != NULL)
349    {
350        //while read character isn't at the end of file, loop
351        //scanning every character until the end of file
352        while((ch = (char)fgetc(f)) != EOF) {
353            string[i]=ch;
354            i++;
355        }
356    }
357    else //exception of retrieval failure
358    {
359        printf("Error: %s was not found.\n", fileName);
360        return 1;
361    }
362
363    fclose(f); //fclose(f) to avoid memory leak
364
365    i=0; //refreshing counter to be re-used in another while loop
366
367    //scans string for words till the end, which are then sorted into keys and values
368    while(i<strlen(string)){
369
370        //nested while loop builds up word
371        while(string[i]!=','&&string[i]!='\t'&&string[i]!='\n'){
372            word[j]=string[i];
373            j++; //increment char counter for word
374            i++; //increment char counter for string
375        }
376
377        if(string[i]==','){
378            for(int n=0;n<strlen(word);n++)
379                key[n]=word[n];
380
381        }else if(string[i]=='\t'){ //when after TAB it goes to next column or row
382            //printf("value:%s",word);
383            //printf("\tcolumn:%d\n",c);
384            for(int n=0;n<strlen(word);n++)
385                value[n]=word[n];
386
387            if(strcmp(key,"(null)")!=0 && strcmp(value,"(null)")!=0) //only inserts when not null
388                insertPair(hashTable,key,value);
389
390            memset(key,0,strlen(key)); //refresh current key for next key
391            memset(value,0,strlen(value)); //refresh current value for next value
392
393        }
394
395        memset(word,0,strlen(word)); //refresh current word for next word
396        j = 0; //refresh char counter for word
397        i++; //increment char counter for string
398    }
399
400    printf("\"%s\" loaded successfully to the current hashTable\n",fileName);
401
402}
403
404//method that frees the hashTable since memory was allocated to it when creating
405int freeHashTable(HashTable * hashTable){
406
407    for(int i=0;i<hashTable->hashSpace;i++) { //frees every bucket if exists
408        if(hashTable->bucket[i]!=NULL)
409            free(hashTable->bucket[i]);
410    }
411
412    free(hashTable); //finally, frees hashTable
413
414    printf("Current hashTable has been successfully freed.\n");
415
416}