KKiGdCu6

1#include <string.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5#define HASH_SPACE 15                           //pre fixed hash space
6#define MAX_COLL 5                              //pre fixed number of maximum collisions
7#define MAX_INPUT 10                            //pre fixed size of the key and value arrays
8#define FILETOSAVE "hashSave.txt"               //declaring file name to save/load in
9
10//creating a struct Pair to store HashTable's values and keys
11typedef struct pair{
12    const char * key; //the key to be inputted
13    const char * value; //the value to be inputted
14}Pair;
15
16//creating struct for pointers
17typedef struct pointer{
18    Pair ** pair; //pointer to data that is in pair
19}Pointer;
20
21//creating struct for hashTable including pointer
22typedef struct hashTable{
23    Pointer ** pointer; //double pointer to the 1st value
24}HashTable;
25
26//initializes hashTable and allocates requested space from hashSpace
27HashTable *  createAHashTable(){
28
29    //allocating space for hashTable
30    HashTable * hashTable = malloc(sizeof(hashTable));
31
32    //allocating space for number of rows, which are equal to the predefined hashSpace
33    hashTable->pointer= calloc(HASH_SPACE, sizeof(Pointer));
34
35    return hashTable; //returns created hash Table(pointer)
36}
37
38int insert(HashTable * hashTable,const char * key, const char * value);
39int getHashFunction(const char * keyIn);
40int delete(HashTable * hashTable, const char * key);
41int saveHashTable(HashTable * hashTable,const char * fileName);
42int loadHashTable(const char *fileName,HashTable * hashTable);
43
44int main() { //main method
45
46    HashTable *hashTablePointer = createAHashTable(); //since the function returns a pointer we create a pointer variable
47
48    loadHashTable(FILETOSAVE,hashTablePointer); //loading any hash table already saved to the file.
49
50
51        const char *key[MAX_INPUT] = { // creation and initialization of the array to store the key
52                "randy",
53                "alison",
54                "laken",
55                "brian",
56                "lara",
57                "daniel",
58                "jake",
59                "emma",
60                "kyle",
61                "nicole"
62        };
63
64        const char *value[MAX_INPUT] = { //creation and initialization of the array to store the value
65                "Marsaskala",
66                "Senglea",
67                "Marsaskala",
68                "Bormla",
69                "Valletta",
70                "Zebbug",
71                "Zababr",
72                "Birkirkara",
73                "Mosta",
74                "Floriana"
75        };
76
77
78        for (int i = 0; i < MAX_INPUT; i++) { //loop used to insert each value/key in the hashtable
79
80            insert(hashTablePointer, key[i], value[i]); //the method to insert into hashtable is called with the
81            // respective key and value and the hash table pointer in the parameters
82        }
83        for (int i = 0; i < MAX_INPUT; i++) { //loop used to print all the keys and their respective number
84            printf("\n%d.%s", i, key[i]);
85        }
86        printf("\n"); //new line
87
88    int stop,c =0; //initialising variables
89    do{
90        printf("Enter key number to delete: \n"); //asking the user to input a key number to be deleted
91        scanf("%d", &c);
92
93        if(c>=0 && c<MAX_INPUT){ //checking that the key number is between its valid range so it exists
94            delete(hashTablePointer, key[c]); //calling the delete method and passing the key with its corresponding values in the parameter
95            stop = 1; //condition to stop looping
96        }else{
97            printf("Error, Enter a number from 0-9"); //when expression is false
98        }
99
100    }while(stop!=1); //condition to loop until the right number is entered
101
102    printf("saving hash table to file..\n");
103    saveHashTable(hashTablePointer,FILETOSAVE); //saving the array in the respective file
104
105}
106
107//method that inserts pair into created hashTable
108int insert(HashTable * hashTable,const char * key, const char * value){
109
110    int hashValue = getHashFunction(key); //calculating the hashValue for a particular key
111
112    if(hashTable->pointer[hashValue]==NULL){ //if the pointer doesnt exist
113
114        hashTable->pointer[hashValue] = malloc(sizeof(Pointer)); //allocate memory for the pointer
115
116        if (hashTable->pointer[hashValue] == NULL) { //error check
117            printf("ERROR: Could not allocate memory to hashValue: %d.",hashValue);
118            return 1;//fail
119        }
120
121        hashTable->pointer[hashValue]->pair = calloc(MAX_COLL, sizeof(Pair)); //allocate memory for 5 Max pairs in the pointer
122
123        if (hashTable->pointer[hashValue]->pair == NULL) { //error check
124            printf("ERROR: Could not allocate memory for the pairs at hashValue: %d.",hashValue);
125            return 1;//fail
126        }
127
128        hashTable->pointer[hashValue]->pair[0] = calloc(1,sizeof(Pair)); //allocate mem for first pair
129        hashTable->pointer[hashValue]->pair[0]->key = key; //set key of first pair
130        hashTable->pointer[hashValue]->pair[0]->value = value; //set value of first pair
131
132    }else if(hashTable->pointer[hashValue]!=NULL){ //if the pointer already exists and we have a collision
133
134        int c=0; //collision counter initialised to 0;
135
136        while(hashTable->pointer[hashValue]->pair[c]!=NULL){ //while a collision is found
137            c++; //increment collision counter to store to the next free space
138        }
139
140        if(c<MAX_COLL){ //if c is less than the max collisions
141
142            hashTable->pointer[hashValue]->pair[c] = calloc(1,sizeof(Pair)); //allocate memory for 1 pair
143            hashTable->pointer[hashValue]->pair[c]->key = key; //set key(pair pointer) to the next collision space
144            hashTable->pointer[hashValue]->pair[c]->value = value; //set value(pair pointer) to the next collision space
145
146        }else{ //  if collisions have equaled the max collisions
147            printf("ERROR: Max Collision: %d has been exceeded.",MAX_COLL); //there is no more space to left
148            return 1;
149        }
150    }
151    //telling user the insertion was successful
152    printf("Key: %s and value: %s were successfully inserted into the hashTable with a hashValue: %d.\n",key,value,hashValue);
153    return 0;
154}
155
156 //method for getHashFunction, accepts key and value as arguments
157int getHashFunction(const char * keyIn){
158
159    int size = 0; //sum of the ASCII code of characters in key
160    int x; //variable to be returned
161
162    //accumulates size of the string
163    for(int i=0;i<sizeof(keyIn);i++) {
164        size = size + keyIn[i]; //adding the size each time
165    }
166
167    x = size % HASH_SPACE; //formula for hash function
168    return x;
169}
170
171//method that deletes pair in hashTable
172int delete(HashTable * hashTable, const char * key){
173
174    int hashValue = getHashFunction(key); //get hashValue
175
176    int c = 0; //counter for collision index
177    int stop = 0; //initial condition to break from if statement
178    Pointer *search = hashTable->pointer[hashValue]; //new pointer to search for respective hash value
179
180    while(search!=NULL && stop!=1){ //scans through list until the match is found
181
182        if(strcmp(hashTable->pointer[hashValue]->pair[0]->key,key)==0){ //if match found at head //comparing the pointer to the key
183
184            if(hashTable->pointer[hashValue]->pair[1]==NULL){ //if head to delete is the only node in the pointer delete head then pointer
185
186                hashTable->pointer[hashValue]->pair[0]->key=NULL; //the first position key is deleted
187                hashTable->pointer[hashValue]->pair[0]->value=NULL; //the first position value is deleted
188
189
190                free(hashTable->pointer[hashValue]->pair[0]); //freeing hash table and all values inside it since memory was allocated to it
191                free(hashTable->pointer[hashValue]->pair);
192                free(hashTable->pointer[hashValue]);
193
194            }else if(hashTable->pointer[hashValue]->pair[1]!=NULL){ //if there is a collision we shift everything to left then delete last
195
196                while(search->pair[c]!=NULL) { //while current node exists
197
198                    if (search->pair[c + 1] != NULL) { //if next node exists
199
200                        search->pair[c]->key = search->pair[c + 1]->key; //copy, from next node to key
201                        search->pair[c]->value = search->pair[c + 1]->value; //copy, from next node to value
202
203                    }else{ //if next node does not exist
204
205                        hashTable->pointer[hashValue]->pair[c]->key=NULL;
206                        hashTable->pointer[hashValue]->pair[c]->value=NULL;
207                        free(search->pair[c]); //delete last element
208
209                    }
210
211                    c++; //increment collision check counter
212
213                }
214            }
215
216            printf(" key: %s was successfully deleted.\n",key);
217            stop=1; //stops the loop
218
219        }else if(strcmp(search->pair[c]->key,key)==0 && search->pair[c+1]!=NULL) {//if match found in middle, shift everything after it to the left
220
221            while (search->pair[c] != NULL) { //while current node exists
222
223                if (search->pair[c + 1] != NULL) { //if next node exists
224
225                    search->pair[c]->key = search->pair[c + 1]->key; //copy, from next node to key
226                    search->pair[c]->value = search->pair[c + 1]->value; //copy, from next node to value
227
228                } else { //if next node doesn't exist (at end of list)
229
230                    hashTable->pointer[hashValue]->pair[c]->key = NULL;
231                    hashTable->pointer[hashValue]->pair[c]->value = NULL;
232                    free(search->pair[c]); //delete last element
233
234                }
235
236                c++; //increment counter
237
238            }
239
240            printf("Deletion of key: \"%s\" was successful in middle.\n", key);
241            stop = 1; //stop scanning for match
242
243        }else if(strcmp(search->pair[c]->key,key)==0 && search->pair[c+1]==NULL){//if match found at end
244
245            hashTable->pointer[hashValue]->pair[c]->key=NULL;
246            hashTable->pointer[hashValue]->pair[c]->value=NULL;
247            free(search->pair[c]); //delete last element
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    return 0;
259}
260
261//method that saves hashTable to structured text file
262int saveHashTable(HashTable * hashTable,const char * fileName){
263
264    FILE *fp;
265    fp = fopen(fileName,"w"); //opens new file to write to
266    if(fp!=NULL) { //while file exists
267
268        //loop by row
269        for (int i = 0; i < HASH_SPACE; i++) {
270
271            if(hashTable->pointer[i]!=NULL) { //if pointer alreadt exists
272
273                Pointer *scan = hashTable->pointer[i];
274                int c=0; //collision counter index initialised
275
276                //navigate to the end of the pointer (can be the head)
277                while (scan->pair[c]!=NULL) {
278
279                    fprintf(fp, "%s,%s", scan->pair[c]->key, scan->pair[c]->value);
280                    fprintf(fp, "\t"); //new column
281
282                    c++; //increment c
283                }
284            }
285
286            fprintf(fp,"\n"); //new row
287        }
288
289
290        printf("Hash table saved successfully to \"%s\"\n", fileName);
291    }
292    return 0;
293}
294
295//method that loads hashTable setting it to the current hashTable
296int loadHashTable(const char *fileName,HashTable * hashTable){
297
298    char ch; //temporarily stores character from file
299    char string[2000]=""; //initialized string to temporarily hold text for scanning to max 1000 characters
300
301    char word[50] = {'\0'};
302
303    char key[50] = {'\0'}; //initialized to temporarily store key, max characters set to 30
304    char value[50] = {'\0'}; //initialized to temporarily store key, max characters set to 30
305
306    int i=0; //counts characters for string
307    int j = 0; //counts characters for word
308
309    FILE *fp;
310    fp = fopen(fileName,"r"); //opens new file to write to
311
312    //Reading input text file using file pointer and methods from <string.h>
313    if(fp != NULL)
314    {
315        //while read character isn't at the end of file, loop
316        //scanning every character until the end of file
317        while((ch = (char)fgetc(fp)) != EOF) {
318            string[i]=ch;
319            i++;
320        }
321    }
322    else //exception of retrieval failure
323    {
324        printf("Error: %s was not found.\n", fileName);
325        printf("This file will now be created in the end of this program.\n");
326        return 1;
327    }
328
329    fclose(fp); //fclose(f) to avoid memory leak
330
331    i=0; //refreshing counter to be re-used in another while loop
332
333    //scans string for words till the end, which are then sorted into keys and values
334    while(i<strlen(string)){
335
336        //nested while loop builds up word
337        while(string[i]!=','&&string[i]!='\t'&&string[i]!='\n'){
338            word[j]=string[i];
339            j++; //increment char counter for word
340            i++; //increment char counter for string
341        }
342
343        if(string[i]==','){
344            for(int n=0;n<strlen(word);n++)
345                key[n]=word[n];
346
347        }else if(string[i]=='\t'){ //when after TAB it goes to next column or row
348            //printf("value:%s",word);
349            //printf("\tcolumn:%d\n",c);
350            for(int n=0;n<strlen(word);n++)
351                value[n]=word[n];
352
353            if(strcmp(key,"(null)")!=0 && strcmp(value,"(null)")!=0) //only inserts when not null
354                insert(hashTable,key,value);
355
356            memset(key,0,strlen(key)); //refresh current key for next key
357            memset(value,0,strlen(value)); //refresh current value for next value
358
359        }
360
361        memset(word,0,strlen(word)); //refresh current word for next word
362        j = 0; //refresh char counter for word
363        i++; //increment char counter for string
364    }
365
366    printf("\"%s\" loaded successfully to the current hashTable\n",fileName);
367
368    return 0;
369}