AAJMB1y1

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 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 bucket including its head
17typedef struct bucket{
18    Pair ** pair; //pointer to data that is in pair
19}Bucket;
20
21//creating struct for hashTable including pointer to row
22typedef struct hashTable{
23    Bucket ** bucket; //double pointer to the beginning of the row
24}HashTable;
25
26//initializes hashTable and allocates requested space from hashSpace
27HashTable *  createHashTable_S(){
28
29    //allocating space for hashTable which is just 1 item
30    HashTable * hashTable = calloc(1,sizeof(hashTable));
31
32    //allocating space for number of rows, which are equal to the predefined hashSpace
33    hashTable->bucket= calloc(HASH_SPACE, sizeof(Bucket));
34
35    return hashTable; //returns created hash Table(pointer)
36}
37
38int insertPair(HashTable * hashTable,const char * key, const char * value);
39int hashFunction_S(const char * keyIn);
40int deletePair(HashTable * hashTable, const char * key);
41int saveHashTableAs(HashTable * hashTable,const char * fileName);
42int loadHashTableTo(const char *fileName,HashTable * hashTable);
43
44int main() {
45
46    HashTable *hashTableInstance = createHashTable_S(); //since the function returns a pointer we create a pointer variable
47
48    /*printf("Do you wish to load a hashtable?\n Enter Y for yes and any other char for no\n ");
49    char ans;
50    scanf("%s", &ans);
51    if (ans == 'y' || 'Y') {
52
53        printf("Enter file name to open:\n");
54        char filename;
55        scanf("%s", &filename);
56
57        loadHashTableTo(filename, hashTableInstance);
58    } else { */
59
60
61        const char *key[MAX_INPUT] = { // creation and initialization of the array to store the key
62                "randy",
63                "alison",
64                "laken",
65                "brian",
66                "lara",
67                "daniel",
68                "jake",
69                "emma",
70                "kyle",
71                "nicole"
72        };
73
74        const char *value[MAX_INPUT] = { //creation and initialization of the array to store the value
75                "Marsaskala",
76                "Senglea",
77                "Marsaskala",
78                "Bormla",
79                "Valletta",
80                "Zebbug",
81                "Zababr",
82                "Birkirkara",
83                "Mosta",
84                "Floriana"
85        };
86
87
88        for (int i = 0; i < MAX_INPUT; i++) { //loop used to insert each value/key in the hashtable
89
90            insertPair(hashTableInstance, key[i], value[i]); //the method to insert into hashtable is called with the
91            // respective key and value and the hashtable pointer in the parameters
92        }
93        for (int i = 0; i < MAX_INPUT; i++) {
94            printf("\n%d.%s", i, key[i]);
95        }
96        printf("\n");
97
98        int c;
99        printf("Enter key number to delete: ");
100        scanf("%d", &c);
101
102    int stop = 0;
103
104    do{
105
106        if(c>0 && c<MAX_INPUT){
107            deletePair(hashTableInstance, key[c]);
108            stop = 1;
109        }else{
110            printf("Error");
111        }
112
113    }while(stop!=1);
114
115
116
117    printf("saving hash table to file..\n");
118    saveHashTableAs(hashTableInstance,FILETOSAVE);
119
120}
121
122//method that inserts pair into created hashTable
123int insertPair(HashTable * hashTable,const char * key, const char * value){
124
125    int hashValue = hashFunction_S(key); //calculate hashValue
126
127    if(hashTable->bucket[hashValue]==NULL){//if bucket doesnt exist
128
129        hashTable->bucket[hashValue] = malloc(sizeof(Bucket)); //allocate mem for new bucket
130
131        if (hashTable->bucket[hashValue] == NULL) { //error check
132            printf("Failed to allocate memory for new bucket at hashValue: %d.",hashValue);
133            return 1;//fail
134        }
135
136        hashTable->bucket[hashValue]->pair = calloc(MAX_COLL, sizeof(Pair)); //allocate mem for three pairs in bucket
137
138        if (hashTable->bucket[hashValue]->pair == NULL) { //error check
139            printf("Failed to allocate memory for array of pairs at hashValue: %d.",hashValue);
140            return 1;//fail
141        }
142
143        hashTable->bucket[hashValue]->pair[0] = malloc(sizeof(Pair)); //allocate mem for first pair
144        hashTable->bucket[hashValue]->pair[0]->key = key; //set key of first pair
145        hashTable->bucket[hashValue]->pair[0]->value = value; //set value of first pair
146
147    }else if(hashTable->bucket[hashValue]!=NULL){ //if bucket exists
148
149        int c=0; //collision counter to count amount of collisions in bucket when inserting
150
151        while(hashTable->bucket[hashValue]->pair[c]!=NULL){ //while pair exists
152            c++; //increment collision counter
153        }
154
155        if(c<MAX_COLL){ //if c is less than max initial collisions
156            hashTable->bucket[hashValue]->pair[c] = malloc(sizeof(Pair)); //allocate mem for pair
157            hashTable->bucket[hashValue]->pair[c]->key = key; //set key after last collision
158            hashTable->bucket[hashValue]->pair[c]->value = value; //set value after last collision
159
160        }else{ //if c is equal to the ax collisions, no space for new pair, produce error
161            printf("Error: Max_Collisions %d exceeded.",MAX_COLL);
162            return 1;
163        }
164
165    }
166
167    printf("Pair of key: \"%s\" and value: \"%s\" was successfully inserted into the hashTable, hashValue: %d.\n",key,value,hashValue);
168
169}
170
171 //method for hashFunction_S, accepts key and value as arguments
172int hashFunction_S(const char * keyIn){
173
174    int charSumKey = 0; //sum of the ASCII code of characters in key
175    int x; //variable to be returned
176
177    //accumulates sum of ASCII code of each character
178    for(int i=0;i<strlen(keyIn);i++) {
179        charSumKey += keyIn[i];
180    }
181
182    x = charSumKey % HASH_SPACE; //invented formula for hash function
183    return x;
184}
185
186//method that deletes pair in hashTable
187int deletePair(HashTable * hashTable, const char * key){
188
189    int hashValue = hashFunction_S(key); //get hashValue
190
191
192
193    int c = 0; //counter for collision index
194    int stop = 0; //to break from loop from if statement
195    Bucket *scan = hashTable->bucket[hashValue];
196
197    while(scan!=NULL && stop!=1){ //scans through list until match to delete is found
198
199        if(strcmp(hashTable->bucket[hashValue]->pair[0]->key,key)==0){ //if match found at head
200
201            if(hashTable->bucket[hashValue]->pair[1]==NULL){ //if head to delete is the only node in the bucket delete head then bucket
202
203                hashTable->bucket[hashValue]->pair[0]->key=NULL;
204                hashTable->bucket[hashValue]->pair[0]->value=NULL;
205                free(hashTable->bucket[hashValue]->pair[0]);
206                free(hashTable->bucket[hashValue]->pair);
207                free(hashTable->bucket[hashValue]);
208
209            }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
210
211                while(scan->pair[c]!=NULL) { //while current node exists
212
213                    if (scan->pair[c + 1] != NULL) { //if next node exists
214
215                        scan->pair[c]->key = scan->pair[c + 1]->key; //copy, from next node to key
216                        scan->pair[c]->value = scan->pair[c + 1]->value; //copy, from next node to value
217
218                    }else{ //if next node doesn't exist (at end of list)
219
220                        hashTable->bucket[hashValue]->pair[c]->key=NULL;
221                        hashTable->bucket[hashValue]->pair[c]->value=NULL;
222                        free(scan->pair[c]); //delete last element
223
224                    }
225
226                    c++; //increment counter
227
228                }
229            }
230
231            printf("Deletion of key: \"%s\" was successful at head.\n",key);
232            stop=1; //stop scanning for match
233
234        }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
235
236            while(scan->pair[c]!=NULL) { //while current node exists
237
238                if (scan->pair[c + 1] != NULL) { //if next node exists
239
240                    scan->pair[c]->key = scan->pair[c + 1]->key; //copy, from next node to key
241                    scan->pair[c]->value = scan->pair[c + 1]->value; //copy, from next node to value
242
243                }else{ //if next node doesn't exist (at end of list)
244
245                    hashTable->bucket[hashValue]->pair[c]->key=NULL;
246                    hashTable->bucket[hashValue]->pair[c]->value=NULL;
247                    free(scan->pair[c]); //delete last element
248
249                }
250
251                c++; //increment counter
252
253            }
254
255            printf("Deletion of key: \"%s\" was successful in middle.\n",key);
256            stop=1; //stop scanning for match
257
258        }else if(strcmp(scan->pair[c]->key,key)==0 && scan->pair[c+1]==NULL){//if match found at end
259
260            hashTable->bucket[hashValue]->pair[c]->key=NULL;
261            hashTable->bucket[hashValue]->pair[c]->value=NULL;
262            free(scan->pair[c]); //delete last element
263
264            printf("Deletion of key: \"%s\" was successful.\n",key);
265            stop=1; //stop scanning for match
266
267        }else { //if match not found
268            c++; //increment c
269        }
270
271    }
272
273
274
275
276}
277
278//method that saves hashTable to structured text file
279int saveHashTableAs(HashTable * hashTable,const char * fileName){
280
281    FILE *f;
282    f = fopen(fileName,"w"); //opens new file to write to
283    if(f!=NULL) {
284
285        //loop by row
286        for (int i = 0; i < HASH_SPACE; i++) {
287
288            if(hashTable->bucket[i]!=NULL) { //if bucket exists
289
290                Bucket *scan = hashTable->bucket[i];
291                int c=0; //collision counter index initialised
292
293                //navigate to the end of the bucket (can be the head)
294                while (scan->pair[c]!=NULL) {
295
296                    fprintf(f, "%s,%s", scan->pair[c]->key, scan->pair[c]->value);
297                    fprintf(f, "\t"); //new column
298
299                    c++; //increment c
300                }
301            }
302
303            fprintf(f,"\n"); //new row
304        }
305
306
307        printf("Hash table saved successfully to \"%s\"\n", fileName);
308    }
309}
310
311//method that loads hashTable setting it to the current hashTable
312int loadHashTableTo(const char *fileName,HashTable * hashTable){
313
314    char ch; //temporarily stores character from file
315    char string[1000]=""; //initialized string to temporarily hold text for scanning to max 1000 characters
316
317    char word[30] = {'\0'};
318
319    char key[30] = {'\0'}; //initialized to temporarily store key, max characters set to 30
320    char value[30] = {'\0'}; //initialized to temporarily store key, max characters set to 30
321
322    int i=0; //counts characters for string
323    int j = 0; //counts characters for word
324
325    FILE *f;
326    f = fopen(fileName,"r"); //opens new file to write to
327
328    //Reading input text file using file pointer and methods from <string.h>
329    if(f != NULL)
330    {
331        //while read character isn't at the end of file, loop
332        //scanning every character until the end of file
333        while((ch = (char)fgetc(f)) != EOF) {
334            string[i]=ch;
335            i++;
336        }
337    }
338    else //exception of retrieval failure
339    {
340        printf("Error: %s was not found.\n", fileName);
341        return 1;
342    }
343
344    fclose(f); //fclose(f) to avoid memory leak
345
346    i=0; //refreshing counter to be re-used in another while loop
347
348    //scans string for words till the end, which are then sorted into keys and values
349    while(i<strlen(string)){
350
351        //nested while loop builds up word
352        while(string[i]!=','&&string[i]!='\t'&&string[i]!='\n'){
353            word[j]=string[i];
354            j++; //increment char counter for word
355            i++; //increment char counter for string
356        }
357
358        if(string[i]==','){
359            for(int n=0;n<strlen(word);n++)
360                key[n]=word[n];
361
362        }else if(string[i]=='\t'){ //when after TAB it goes to next column or row
363            //printf("value:%s",word);
364            //printf("\tcolumn:%d\n",c);
365            for(int n=0;n<strlen(word);n++)
366                value[n]=word[n];
367
368            if(strcmp(key,"(null)")!=0 && strcmp(value,"(null)")!=0) //only inserts when not null
369                insertPair(hashTable,key,value);
370
371            memset(key,0,strlen(key)); //refresh current key for next key
372            memset(value,0,strlen(value)); //refresh current value for next value
373
374        }
375
376        memset(word,0,strlen(word)); //refresh current word for next word
377        j = 0; //refresh char counter for word
378        i++; //increment char counter for string
379    }
380
381    printf("\"%s\" loaded successfully to the current hashTable\n",fileName);
382
383}