Attached Document below
Purpose: To go over: · Compiler optimizations · Program profiling (timing) · Header files · Linking and object file layout Computing Please ssh into one of the following: · cdmlsrvprd01.dpu.depaul.edu or use your own Linux machine. Please submit a .zip file (not .7z or any other non-standard compression!) file of your header file, .c files, and and a .txt/.pdf/.doc/.odt file containing your answer to the questions. 1. Please copy-and-paste the following files (0 Points): wordCounter.c /*-------------------------------------------------------------------------* *------* *---wordCounter.c---* *------* *--- This file defines a program that counts the words in a file---* *---using 2 different data-structures.---* *------* *--------------------------------------* *------* *---Version 1.0Joseph Phillips---* *------* *-------------------------------------------------------------------------*/ #include"wordCounterHeader.h" // PURPOSE: To hold the size of the buffer to read. inttextLen; // PURPOSE: To remove the '\n' character in the string pointed to by '\n', //if it exists. No return value. void removeNewline(char*cPtr ) { cPtr= strchr(cPtr,'\n'); if (cPtr != NULL) *cPtr = '\0'; } // PURPOSE: To return '1' if a word is found at address '*positionHandle', //and to place a lowercased version of the word into 'word', advance //'*positionHandle' past the word, and return '1' if such a word exists. //Returns '0' if no more words are found between the starting address of //'*positionHandle' and the ending '\n' or '\0' character. intdidGetWord(char**positionHandle, char*word ) { while ( (**positionHandle != '\n') && (**positionHandle != '\n') && !isalnum(**positionHandle) ) (*positionHandle)++; if ( (**positionHandle == '\n') || (**positionHandle == '\0') ) return(0); do { *word= tolower(**positionHandle); word++; (*positionHandle)++; } while ( isalnum(**positionHandle) ); *word= '\0'; return(1); } intmain(intargc, char*argv[] ) { charfilename[SMALL_TEXT_LEN]; FILE*filePtr; intchoice; intlength= 1024; textLen= 4 * length; printf("File name to read: "); fgets(filename,SMALL_TEXT_LEN,stdin); removeNewline(filename); filePtr= fopen(filename,"r"); if (filePtr == NULL) { fprintf(stderr,"Could not open %s\n",filename); exit(EXIT_FAILURE); } do { charchoiceText[SMALL_TEXT_LEN]; printf ("Which algorithm would you like to run:\n" "(1) Count words with tree\n" "(2) Count words with linked-list\n" "\n" "Your choice? " ); fgets(choiceText,SMALL_TEXT_LEN,stdin); choice = atoi(choiceText); } while ( (choice < 1)="" ||="" (choice=""> 2) ); printf("\n\n"); switch (choice) { case 1 : { struct TreeNode*rootPtr= buildTree(filePtr); printTree(rootPtr); freeTree (rootPtr); } break; case 2 : { struct ListNode*firstPtr= buildList(filePtr); printList(firstPtr); freeList (firstPtr); } break; } fclose(filePtr); return(EXIT_SUCCESS); } tree.c /*-------------------------------------------------------------------------* *------* *---tree.c---* *------* *--- This file defines functions that build, print and free a---* *---tree of struct TreeNode instances for the wordCounter program.---* *------* *--------------------------------------* *------* *---Version 1.0Joseph Phillips---* *------* *-------------------------------------------------------------------------*/ #include"wordCounterHeader.h" // PURPOSE: To build and return a tree of struct TreeNode instances telling //the counts of the words found in file '*filePtr'. struct TreeNode* buildTree(FILE*filePtr ) { struct TreeNode*rootPtr= NULL; struct TreeNode*listPrev; struct TreeNode*listRun; struct TreeNode*newPtr; intcompResult; char*line= (char*)malloc(textLen); charword[SMALL_TEXT_LEN]; while ( fgets(line,textLen,filePtr) != NULL ) { char*lineRun= line; while ( didGetWord(&lineRun,word) ) { listPrev= NULL; for (listRun = rootPtr; listRun != NULL; ) { if ( (compResult = strcmp(listRun->wordCPtr_,word)) == 0) break; listPrev = listRun; if (compResult > 0) listRun = listRun->leftPtr_; else listRun = listRun->rightPtr_; } if (listRun == NULL) { newPtr= (struct TreeNode*)malloc(sizeof(struct TreeNode)); newPtr->wordCPtr_ = strdup(word); newPtr->count_ = 1; newPtr->leftPtr_ = NULL; newPtr->rightPtr_ = NULL; if (rootPtr == NULL) rootPtr = newPtr; else if (compResult > 0) listPrev->leftPtr_ = newPtr; else listPrev->rightPtr_ = newPtr; } else (listRun->count_)++; } } free(line); return(rootPtr); } // PURPOSE: To print the subtree rooted at '*nodePtr'. No return value. voidprintTree(struct TreeNode*nodePtr ) { if (nodePtr == NULL) return; printTree(nodePtr->leftPtr_); printf("%s\t%d\n",nodePtr->wordCPtr_,nodePtr->count_); printTree(nodePtr->rightPtr_); } // PURPOSE: To free the subtree rooted at '*nodePtr'. No return value. voidfreeTree(struct TreeNode*nodePtr ) { if (nodePtr == NULL) return; freeTree(nodePtr->leftPtr_); freeTree(nodePtr->rightPtr_); free(nodePtr->wordCPtr_); free(nodePtr); } list.c /*-------------------------------------------------------------------------* *------* *---list.c---* *------* *--- This file defines functions that build, print and free a---* *---list of struct ListNode instances for the wordCounter program.---* *------* *--------------------------------------* *------* *---Version 1.0Joseph Phillips---* *------* *-------------------------------------------------------------------------*/ #include"wordCounterHeader.h" // PURPOSE: To build and return a list of struct ListNode instances telling //the counts of the words found in file '*filePtr'. struct ListNode* buildList(FILE*filePtr ) { struct ListNode*firstPtr= NULL; struct ListNode*lastPtr= NULL; struct ListNode*listRun; struct ListNode*newPtr; char*line= (char*)malloc(textLen); charword[SMALL_TEXT_LEN]; while ( fgets(line,textLen,filePtr) != NULL ) { char*lineRun= line; while ( didGetWord(&lineRun,word) ) { for (listRun = firstPtr; listRun != NULL; listRun = listRun->nextPtr_) if (strcmp(listRun->wordCPtr_,word) == 0) break; if (listRun == NULL) { newPtr = (struct ListNode*)malloc(sizeof(struct ListNode)); newPtr->wordCPtr_ = strdup(word); newPtr->count_ = 1; newPtr->nextPtr_ = NULL; if (firstPtr == NULL) firstPtr = newPtr; else lastPtr->nextPtr_ = newPtr; lastPtr= newPtr; } else (listRun->count_)++; } } free(line); return(firstPtr); } // PURPOSE: To print the list pointed to by '*firstPtr'. No return value. voidprintList(struct ListNode*firstPtr ) { struct ListNode*listRun; for (listRun = firstPtr; listRun != NULL; listRun = listRun->nextPtr_) printf("%s\t%d\n",listRun->wordCPtr_,listRun->count_); } // PURPOSE: To free the list pointed to by '*firstPtr'. No return value. voidfreeList(struct ListNode*firstPtr ) { struct ListNode*listRun; struct ListNode*nextPtr; for (listRun = firstPtr; listRun != NULL; listRun = nextPtr) { nextPtr= listRun->nextPtr_; free(listRun->wordCPtr_); free(listRun); } } 2. Header files (20 Points): Hey! Ain't something missing!?! Yeah, that is right. There is no wordCounterHeader.h. Please write one so that you can compile the program! Please be sure to declare only what is needed in common. Please add to this incomplete one: /*-------------------------------------------------------------------------* *------* *---wordCounterHeader.h---* *------* *--- This file includes common header files and declares structs---* *---needed by .c files of the wordCounter program.---* *------* *--------------------------------------* *------* *---Version 1.0Joseph Phillips---* *------* *-------------------------------------------------------------------------*/ //--- Common inclusions:---// #include
#include #include #include //--- Common constants:---// #defineSMALL_TEXT_LEN256 //--- Common types:---// structTreeNode { char*wordCPtr_; intcount_; struct TreeNode*leftPtr_; struct TreeNode*rightPtr_; }; structListNode { char*wordCPtr_; intcount_; struct ListNode*nextPtr_; }; //--- Declarations of global functions:---// // YOUR CODE HERE! 3. Timing: Part 1 (20 Points): Compile and run the program without any extra optimizations, but with profiling for timing: gcc -c -pg -O0 wordCounter.c gcc -c -pg -O0 tree.c gcc -c -pg -O0 list.c gcc wordCounter.o tree.o list.o -pg -O0 -o wordCounterO0 Run the program twice timing it both times, and answer the following: a. $ ./wordCounterO0 b. File name to read: /public/jphill13/originOfSpecies_4x.txt c. Which algorithm would you like to run: d. (1) Count words with tree e. (2) Count words with linked-list f. g. Your choice? 1 buildTree() self seconds _____________ h. $ ./wordCounterO0 i. File name to read: /public/jphill13/originOfSpecies_4x.txt j. Which algorithm would you like to run: k. (1) Count words with tree l. (2) Count words with linked-list m. n. Your choice? 2 buildList() self seconds _____________ 4. Timing: Part 2 (20 Points): Compile and run the program with optimization, but with profiling for timing: gcc -c -pg -O2 wordCounter.c gcc -c -pg -O2 tree.c gcc -c -pg -O2 list.c gcc wordCounter.o tree.o list.o -pg -O2 -o wordCounterO2 Run the program twice timing it both times, and answer the following: a. $ ./wordCounterO2 b. File name to read: /public/jphill13/originOfSpecies_4x.txt c. Which algorithm would you like to run: d. (1) Count words with tree e. (2) Count words with linked-list f. g. Your choice? 1 buildTree() self seconds _____________ h. $ ./wordCounterO2 i. File name to read: /public/jphill13/originOfSpecies_4x.txt j. Which algorithm would you like to run: k. (1) Count words with tree l. (2) Count words with linked-list m. n. Your choice? 2 buildList() self seconds _____________ 5. Algorithm choice vs. Compiler optimization (Points 10): Which is faster? . A bad algorithm and data-structure optimized with -O2 . A good algorithm and data-structure optimized with -O0 · Parts of an executable (Points 20): Please find the following inside of wordCounterO0 by using objdump to show it (if it exists in the executable) or by using objdump to disassemble the code and showing where the code manipulates the heap or stack. Show a disassembly or objdump. You do not have to show all of the objdump result if it is too long, but (1) please show the relevant output, and (2) please show the objdump command that you used to generate it. f. The string "File name to read: " in main()