· 8 years ago · Mar 22, 2018, 04:46 AM
1#include <stdlib.h>
2#include <stdio.h>
3#include <string.h>
4#include <math.h>
5
6/* constants */
7#define BUFFER_SIZE 1024
8#define FILENAME_SIZE 20
9#define blockCount 19
10#define columnCount 5
11#define MOD_AMT 5
12
13/* decoding CSV data */
14typedef struct CSVLinkedList {
15 char *operation;
16 int data;
17 struct CSVLinkedList *next;
18}CSVData;
19
20/* to store directory information */
21typedef struct Node {
22 int indexKey;
23 int startBlock;
24 int endBlock;
25} Node_index;
26
27// function prototypes
28void processCSV(CSVData *data);
29void clearCache();
30void readAtIndex(int indexRead);
31
32/* MEMORY STRUCTURE */
33int memoryStructure[blockCount][columnCount];
34Node_index *directoryStructure[5] = { NULL, NULL, NULL, NULL, NULL };
35
36// counting number of entries in the memoryStructure
37int fileCount = 0;
38int allocationType = 0, i, j;
39
40int main() {
41 /* recording overall size of */
42
43 /*INITIALIZE MEMORY BLOCK*/
44 int row = sizeof(memoryStructure) / sizeof(memoryStructure[0]);
45 int column = sizeof(memoryStructure[0]) / sizeof(memoryStructure[0][0]);
46 for (i = 0; i < row; i++) {
47 for (j = 0; j < column; j++) {
48 memoryStructure[i][j] = 0;
49 }
50 }
51 // First block is occupied by directory structure
52 //memoryStructure[0][0] = -1;
53
54 // giving user choice of memory allocation type
55 while (1) {
56 printf("Welcome to ICT1007 Assignment\n");
57 printf("Please choose the memory allocation type.\n1. Contiguous\n2. Linked\n3. Indexed\nEnter your choice: ");
58 scanf_s("%d", &allocationType);
59 if (allocationType == 1) {
60 printf("You have selected <Contiguous> memory allocation.\n\n");
61 break;
62 }
63 else if (allocationType == 2) {
64 printf("You have selected <Linked> memory allocation.\n\n");
65 break;
66 }
67 else if (allocationType == 3) {
68 printf("You have selected <Indexed> memory allocation.\n\n");
69 break;
70 }
71 else
72 printf("You have selected an invalid option. Please try again.\n");
73 }
74
75 // print main menu
76 int userChoice = -1;
77 while (userChoice != 4) {
78 printf("Main Menu\n");
79 printf("1. Import CSV file\n2. View directory structure\n3. View data structure\n4. Search node\n5. Exit\nEnter your choice: ");
80 scanf_s("%d", &userChoice);
81
82 /* to clear input buffer from scanf */
83 clearCache();
84
85 if (userChoice == 1) {
86 /* to read the CSV file*/
87 char fileName[FILENAME_SIZE];
88 printf("Enter name of CSV file to import into system: ");
89 fgets(fileName, FILENAME_SIZE, stdin);
90
91 //to remove trailing \n
92 fileName[strcspn(fileName, "\n")] = 0;
93 FILE *file;
94
95 char buf[BUFFER_SIZE];
96 int validFile = 1;
97 file = fopen(fileName, "r");
98 if (file == NULL) {
99 fprintf(stderr, "File not found.\n");
100 validFile = 0;
101 }
102 if (validFile == 1) {
103 // To check number of records in the file
104 CSVData *newEntry;
105 // to read buf
106 while (fgets(buf, sizeof(buf), file) != NULL) {
107 newEntry = malloc(sizeof(CSVData));
108 newEntry->next = NULL;
109 newEntry->data = NULL;
110
111 // this strtok will return the operation type of the line
112 char *operationType = strtok(buf, ",");
113 // recording file details
114 newEntry->operation = operationType;
115
116 // this strtok will return the file identifier
117 char *tokenPtr = "";
118 while (tokenPtr != NULL)
119 {
120 tokenPtr = strtok(NULL, ",");
121 if (newEntry->data == NULL) {
122 // recording file details
123 newEntry->data = tokenPtr;
124 }
125 else {
126 if (tokenPtr != NULL) {
127 // checking if there is a newline character in the token
128 if (strchr(tokenPtr, '\n') != NULL) {
129 //to remove trailing \n
130 tokenPtr[strcspn(tokenPtr, "\n")] = 0;
131 if (strcmp(tokenPtr, "") == 0) {
132 processCSV(newEntry);
133 break;
134 }
135 }
136
137 CSVData *subsequentEntry = malloc(sizeof(CSVData));
138 subsequentEntry->next = NULL;
139 subsequentEntry->operation = operationType;
140 subsequentEntry->data = tokenPtr;
141 // iterate through head of the node to find the next node to append the newly created node to
142 CSVData *temp = newEntry;
143 while (temp->next != NULL) {
144 temp = temp->next;
145 }
146 temp->next = subsequentEntry;
147 }
148 }
149 }
150 if (tokenPtr == NULL) {
151 processCSV(newEntry);
152 }
153 }
154 if (feof(file))
155 {
156 // print completed message?
157 printf("CSV File loaded.\n\n");
158 }
159 else
160 {
161 // some other error interrupted the read
162 fprintf(stderr, "Error reading file\n");
163 }
164 }
165 }
166 else if (userChoice == 2) {
167 /*PRINTING OF NODE LINKED LIST*/
168 printf("\nPRINTING INFORMATION OF NODES\n");
169 for (i = 0; i < MOD_AMT; i++) {
170 printf("Node %d: ", i);
171 if (directoryStructure[i] != NULL)
172 printf("FileID: %d, Start block: %d, End block: %d", directoryStructure[i]->indexKey, directoryStructure[i]->startBlock, directoryStructure[i]->endBlock);
173 else
174 printf("No information found.");
175
176 printf("\n");
177 }
178 printf("\n");
179 }
180 else if (userChoice == 3) {
181 // view entire memory structure
182
183 printf("\nPRINTING ENTIRE MEMORY STRUCTURE");
184
185 // printing directory structure
186 printf("\nBlock Number: 0\n");
187 for (i = 0; i < MOD_AMT; i++) {
188 printf("Index Number %d: ", i);
189 if (directoryStructure[i] != NULL)
190 printf("FileID - %d, Starting block - %d, Ending block - %d\n", directoryStructure[i]->indexKey, directoryStructure[i]->startBlock, directoryStructure[i]->endBlock);
191 else
192 printf("No information found.\n");
193 }
194
195 // printing memory structure
196 for (i = 0; i < blockCount; i++) {
197 printf("\nBlock Number: %d\n", i);
198 for (j = 0; j < columnCount; j++) {
199 printf("Index Number %d: %d\n", j, memoryStructure[i][j]);
200 }
201 }
202
203 // printing record information
204 printf("Total number of files: %d\n\n", fileCount);
205 printf("Total records: %d\n\n", getRecordCount());
206 }
207 else if (userChoice == 4) {
208 // TO DO - search node
209 }
210 else if (userChoice == 5) {
211 printf("Thank you for using the system.\nPress any key to continue.");
212 getch();
213 return 0;
214 }
215 else {
216 printf("Invalid choice selected, please try again.\n\n");
217 }
218 }
219}
220
221/**
222FIND EMPTY MEMORY SPACE
223- parameter memory[blockCount][columnCount]: Gets the current memory structure
224*/
225int findEmptySpace(int memory[blockCount][columnCount]) {
226 // TO DO - implement free space management
227 if (allocationType == 1) {
228 for (i = 2; i <= blockCount; i++) {
229 for (int j = 0; j < columnCount; j++) {
230 if (memory[i][j] == 0) {
231 return i;
232 }
233 }
234 }
235 return -1;
236 }
237 if (allocationType == 2) {
238 for (i = 0; i <= blockCount; i++) {
239 if (memory[i][0] == 0) {
240 return i;
241 }
242 }
243 return -1;
244 }
245 if (allocationType == 3) {
246 for (i = 0; i <= blockCount; i++) {
247 if (memory[i][0] == 0) {
248 return i;
249 }
250 }
251 return -1;
252 }
253
254}
255
256// this function returns the end block number after successfully committing all information into the memory structure
257int updateMemory(CSVData *currentNode, int blockNum) {
258 /* for linked disk block allocation method */
259 if (allocationType == 3) {
260 int endBlock = blockNum;
261 // for indexed memory allocation method:
262 // first block is burned to contain the pointers to all the blocks occupied by a file
263
264 // initialise all indexes to -1 when block is found
265 for (int x = 0; x < 5; x++) {
266 memoryStructure[blockNum][x] = -1;
267 }
268 // find new block to store file information
269 int newBlock = findEmptySpace(memoryStructure);
270 // assign the block number to the index table
271 int j = 0;
272 memoryStructure[blockNum][j] = newBlock;
273 //memoryStructure[blockNum][4] = -1;
274
275 CSVData *temp = currentNode;
276 int count = 0;
277 while (temp != NULL) {
278 // find new block to store file information when space of block has been used up
279 if (count > 4) {
280 newBlock = findEmptySpace(memoryStructure);
281 count = 0;
282 j++;
283 // the last index of the block is linked to another block to store new block pointer
284 if (j % 4 == 0) {
285 endBlock = findEmptySpace(memoryStructure);
286 memoryStructure[blockNum][j] = endBlock;
287 for (int y = 0; y < 5; y++) {
288 memoryStructure[endBlock][y] = -1;
289 }
290 memoryStructure[endBlock][count] = newBlock;
291 }
292 memoryStructure[blockNum][j] = newBlock;
293 // find new block to when space has been used up for index table
294 }
295 // append file info into block index
296 if (memoryStructure[newBlock][count] == 0) {
297 int fileInfo;
298 sscanf(temp->data, "%d", &fileInfo);
299 memoryStructure[newBlock][count] = fileInfo;
300 }
301 temp = temp->next;
302 count++;
303 }
304 }
305 if (allocationType == 2) {
306 int counter = 0;
307 while (currentNode != NULL) {
308 if (counter != 4) {
309 // getting the file data
310 int fileInfo;
311 sscanf(currentNode->data, "%d", &fileInfo);
312
313 // update the memory structure
314 memoryStructure[blockNum][counter] = fileInfo;
315
316 // to update the counter so the system will update next index of the block
317 counter++;
318 currentNode = currentNode->next;
319 }
320 else {
321 // reset counter and increment blockNum
322 int newBlockNum = findEmptySpace(memoryStructure);
323 if (blockNum == -1) {
324 // to do - error check
325 }
326 else {
327 // ptr to next block
328 printf(", %d", newBlockNum);
329 memoryStructure[blockNum][counter] = newBlockNum;
330 counter = 0;
331 blockNum = newBlockNum;
332 }
333 }
334 }
335 return blockNum;
336 }
337}
338
339/* returns which index the new data will reside in directoryStructure (0 to 4), returns -1 if unable to add */
340int insertAtIndex(int indexKey, int startBlock) {
341 int currentFreeIndex = findEmptySpace(memoryStructure);
342 /* TERMINATE PROGRAM IF MORE THAN 20 BLOCKS USED (not enough space) */
343 if (currentFreeIndex == -1) {
344 printf("YOU HAVE DO NOT HAVE ANY MORE MEMORY TO ALLOCATE\n");
345 //exit(0);
346 }
347 else {
348 /* MALLOC new node only if there are less than 5 files created */
349 if (fileCount > 4) {
350 return -1;
351 }
352 else {
353 Node_index *mallocNode = (Node_index *)malloc(sizeof(Node_index));
354
355 /*SWITCH CASE*/
356 Node_index *tempHead = NULL;
357 int hashValue = (indexKey / 100) % MOD_AMT;
358
359 if (directoryStructure[hashValue] == NULL) {
360 // able to insert the new file into the directoryStructure in index hashValue
361 mallocNode->indexKey = indexKey;
362 mallocNode->startBlock = startBlock;
363
364 directoryStructure[hashValue] = mallocNode;
365 return hashValue;
366 }
367 else {
368 // linear probing - TO DO maybe change to quadratic probing?
369 for (i = 0; i < MOD_AMT - 1; i++) {
370 // try only MOD_AMT - 1 more times
371 hashValue += 1;
372 if (hashValue > 4)
373 hashValue = 0;
374 if (directoryStructure[hashValue] == NULL) {
375 // found an empty entry
376
377 // able to insert the new file into the directoryStructure in index hashValue
378 mallocNode->indexKey = indexKey;
379 mallocNode->startBlock = startBlock;
380
381 directoryStructure[hashValue] = mallocNode;
382 return hashValue;
383 }
384 }
385 }
386 }
387 }
388}
389
390void updateEndBlock(int indexKey, int endBlock) {
391 for (i = 0; i < MOD_AMT; i++) {
392 if (directoryStructure[i] != NULL) {
393 if (directoryStructure[i]->indexKey == indexKey) {
394 directoryStructure[i]->endBlock = endBlock;
395 break;
396 }
397 }
398 }
399}
400
401/**
402DELETES HASHMAP AT INDEX, REMOVES FROM MEMORY BLOCK TOO
403- parameter indexKey: To delete the index of the file, e.g. 100, 200, 300.
404*/
405void deleteAtIndex(int indexKey) {
406 if (allocationType == 3) {
407 int ifExists = getDirIndex(indexKey);
408 if (ifExists != -1) {
409 // print out the blocks that are deleted
410 printf("Deleting File ID %d at block(s) %d", indexKey, directoryStructure[ifExists]->startBlock);
411
412 // delete from memory structure
413 int block = directoryStructure[ifExists]->startBlock;
414 for (int i = 0; i < blockCount; i++) {
415 if (memoryStructure[block][i] != -1) {
416 int blockPointer = memoryStructure[block][i];
417 if (blockPointer != -1) {
418 for (int j = 0; j < blockCount; j++) {
419 memoryStructure[blockPointer][j] = 0;
420 }
421 }
422 }
423 else {
424 break;
425 }
426 }
427 // reset block pointer
428 for (int i = 0; i < blockCount; i++) {
429 memoryStructure[block][i] = 0;
430 }
431 // delete from directory structure
432 directoryStructure[ifExists] = NULL;
433 // print delete information
434 printf(".\nSuccessfully deleted file ID %d.\n\n", indexKey);
435 fileCount--;
436 }
437 else {
438 printf("File ID %d does not exist!\n\n", indexKey);
439 }
440 }
441 else {
442 /* checking if the indexKey exists */
443 int ifExists = getDirIndex(indexKey);
444 if (ifExists != -1) {
445 // print out the blocks that are deleted
446 printf("Deleting File ID %d at block(s) %d", indexKey, directoryStructure[ifExists]->startBlock);
447
448 // to delete the entries from memory structure
449 int xCoordinate = directoryStructure[ifExists]->startBlock;
450 int yCoordinate = 0;
451 while (yCoordinate != 5) {
452 // changing the xCoordinate to the pointer if the compiler has reached the index of the pointer
453 if (yCoordinate == 4 && memoryStructure[xCoordinate][yCoordinate] != 0) {
454 int updatedXCoordinate = memoryStructure[xCoordinate][yCoordinate];
455 memoryStructure[xCoordinate][yCoordinate] = 0;
456 yCoordinate = 0;
457 xCoordinate = updatedXCoordinate;
458 // print out the blocks that are deleted
459 printf(", %d", xCoordinate);
460 }
461 else {
462 // delete whole block worth of data
463 memoryStructure[xCoordinate][yCoordinate] = 0;
464 yCoordinate += 1;
465 }
466 }
467
468 printf(".\nSuccessfully deleted file ID %d.\n\n", indexKey);
469 fileCount--;
470
471 directoryStructure[ifExists] = NULL;
472 }
473 else {
474 printf("File ID %d does not exist!\n\n", indexKey);
475 }
476 }
477}
478
479
480/* returns index of the indexKey searched in directory structure. If found return 1, else, return -1 */
481int getDirIndex(int indexKey) {
482 for (i = 0; i < MOD_AMT; i++) {
483 if (directoryStructure[i] != NULL) {
484 if (directoryStructure[i]->indexKey == indexKey) {
485 return i;
486 }
487 }
488 }
489 return -1;
490}
491
492/* this method will check if a specified index exists in the memory structure. Returns the block number, 0 if does not exist. */
493int valueExists(int indexKey) {
494 // check if the searched index exists
495 for (int i = 0; i < blockCount; i++) {
496 for (int j = 0; j < columnCount; j++) {
497 if (memoryStructure[i][j] == indexKey)
498 return i;
499 }
500 }
501 return -1;
502}
503
504/* this method gets rid of old values from scanf after the user input checks that the user has entered invalid values */
505void clearCache() {
506 char a;
507 while ((a = getchar()) != '\n' && a != EOF);
508}
509
510void readAtIndex(int indexRead) {
511 /* for linked memory allocation */
512 if (allocationType == 2) {
513 // getting the file ID of the specified index
514 int fileID = floor(indexRead / 100) * 100;
515
516 // finding out which hashmap the file is stored in
517 int mod = fileID % MOD_AMT;
518
519 // getting the file ID
520 int ifExists = getDirIndex(fileID);
521 if (ifExists != -1) {
522 int blockPtr = directoryStructure[ifExists]->startBlock;
523 // print results
524 printf("Reading file ID %d containing specified value %d from block %d.\n", fileID, indexRead, blockPtr);
525
526 // stepping through the memory structure
527 for (int i = 0; i < columnCount; i++) {
528 if (memoryStructure[blockPtr][i] == indexRead) {
529 // found
530 printf("Found! Specified value %d is located in block %d index %d.\n\n", indexRead, blockPtr, i);
531 // to break out of for loop
532 i = 4;
533 }
534 else if (i == 4) {
535 printf("Block %d does not contain the specified value %d. ", blockPtr, indexRead);
536 // change the pointer value
537 blockPtr = memoryStructure[blockPtr][i];
538 // restart the iteration through memory structure in the new block
539 i = -1;
540 printf("Proceeding to search in block %d.\n", blockPtr);
541 }
542 }
543 }
544
545 }
546 if (allocationType == 3) {
547 // getting the filed id
548 int fileId = floor(indexRead / 100) * 100;
549 int modValue = fileId % MOD_AMT;
550 int ifExists = getDirIndex(fileId);
551 if (ifExists != -1) {
552 int block = directoryStructure[ifExists]->startBlock;
553 // print results
554 printf("Reading file ID %d containing specified value %d from block %d.\n", fileId, indexRead, block);
555
556 //step through the memory structure
557
558 int blockPointer;
559 for (int i = 0; i < columnCount; i++) {
560 if (memoryStructure[block][i] != -1) {
561 blockPointer = memoryStructure[block][i];
562 if (blockPointer != -1) {
563 for (int j = 0; j < columnCount; j++) {
564 if (memoryStructure[blockPointer][j] == indexRead) {
565 // found
566 printf("Found! Specified value %d is located in block %d index %d.\n\n", indexRead, blockPointer, j);
567 break;
568 }
569 }
570 }
571 }
572 }
573 }
574
575 }
576}
577
578void processCSV(CSVData *data) {
579 int blockNum = 0;
580 CSVData *temp = data;
581 if (temp != NULL) {
582 /* converting the data into an integer type */
583 int indexKey;
584 sscanf(temp->data, "%d", &indexKey);
585 // see which operation the file has specified the program to do
586 if (strcmp(temp->operation, "add") == 0) {
587 // add function here
588
589 // first, create the entry in the hashmap
590 int startBlock = 0;
591 int endBlock = 0;
592
593 // checking if the file ID already exists in the data structure / hashmap
594 int ifExists = getDirIndex(indexKey);
595 if (ifExists != -1) {
596 printf("Unable to insert data with file ID %d as it already exists.\n\n", indexKey);
597 }
598 else {
599 // finding empty index to insert
600 startBlock = findEmptySpace(memoryStructure);
601
602 /* calculating the end block
603 float blocksReq = entryCount * 1.0 / 4;
604 endBlock = ceil(blocksReq);
605 endBlock += startBlock - 1;*/
606
607 //this will creates the file details at the hashmap
608 int ifInserted = insertAtIndex(indexKey, startBlock);
609
610 // successfully inserted
611 if (ifInserted != -1) {
612 printf("Adding file ID %d at block(s) %d", indexKey, startBlock);
613 // proceeding to adding file information
614 temp = temp->next;
615 int finalEndBlock = startBlock;
616 if (temp != NULL) {
617 // then, iterate through the given data to populate the memory structure
618 finalEndBlock = updateMemory(temp, startBlock);
619 }
620 // update the end message of block numbers
621 updateEndBlock(indexKey, finalEndBlock);
622 printf("\nSuccessfully added file ID %d\n\n", indexKey);
623 fileCount++;
624 }
625 else {
626 printf("Adding file ID %d failed.\n", indexKey);
627 printf("Unable to create more than 5 files.\n\n");
628 }
629 }
630 }
631 else if (strcmp(temp->operation, "read") == 0) {
632 // checking if specified index exists.
633 int ifExists;
634 ifExists = valueExists(indexKey);
635 /* printing error if does not exist */
636 if (ifExists == -1) {
637 printf("Error reading file content %d. Records not found.\n\n", indexKey);
638 }
639 /* proceed with reading if exist */
640 else {
641 readAtIndex(indexKey);
642 }
643 }
644 else if (strcmp(temp->operation, "delete") == 0) {
645 deleteAtIndex(indexKey);
646 }
647 else {
648 printf("Error! Unknown operation found.\n");
649 }
650
651 // free the memory that allocated.
652 free(data);
653 }
654 else {
655
656 }
657}
658
659int getRecordCount() {
660 int recordCount = 0;
661
662 /* counting directory structure entries */
663 for (i = 0; i < MOD_AMT; i++) {
664 if (directoryStructure[i] != NULL)
665 recordCount++;
666 }
667
668 /* counting memory structure entries */
669 for (i = 0; i < blockCount; i++) {
670 /* for linked disk block allocation method - cant count pointer to next block as record */
671 if (allocationType == 2) {
672 for (int j = 0; j < columnCount - 1; j++) {
673 if (memoryStructure[i][j] != 0) {
674 recordCount++;
675 }
676 }
677 }
678 // TO DO
679 else {
680 for (int j = 0; j < columnCount; j++) {
681 if (memoryStructure[i][j] != 0) {
682 recordCount++;
683 }
684 }
685 }
686 }
687 return recordCount;
688}