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.0 Joseph Phillips ---*
*--- ---*
*-------------------------------------------------------------------------*
#include "wordCounterHeader.h"
PURPOSE: To hold the size of the buffer to read.
int textLen;
PURPOSE: To remove the '\n' character in the string pointed to by '\n',
if it exists. No return value.
void removeNewline (char* cPt
)
{
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.
int didGetWord (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);
}
int main (int argc,
char* argv[]
)
{
char filename[SMALL_TEXT_LEN];
FILE* filePtr;
int choice;
int length = 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(stde
,"Could not open %s\n",filename);
exit(EXIT_FAILURE);
}
do
{
char choiceText[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);
}
eak;
case 2 :
{
struct ListNode* firstPtr= buildList(filePtr);
printList(firstPtr);
freeList (firstPtr);
}
eak;
}
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.0 Joseph 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* filePt
)
{
struct TreeNode* rootPtr = NULL;
struct TreeNode* listPrev;
struct TreeNode* listRun;
struct TreeNode* newPtr;
int compResult;
char* line = (char*)malloc(textLen);
char word[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)
eak;
listPrev = listRun;
if (compResult > 0)
listRun = listRun->leftPtr_;
else
listRun = listRun-
ightPtr_;
}
if (listRun == NULL)
{
newPtr = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newPtr->wordCPtr_ = strdup(word);
newPtr->count_ = 1;
newPtr->leftPtr_ = NULL;
newPtr-
ightPtr_ = NULL;
if (rootPtr == NULL)
rootPtr = newPtr;
else
if (compResult > 0)
listPrev->leftPtr_ = newPtr;
else
listPrev-
ightPtr_ = newPtr;
}
else
(listRun->count_)++;
}
}
free(line);
return(rootPtr);
}
PURPOSE: To print the subtree rooted at '*nodePtr'. No return value.
void printTree (struct TreeNode* nodePt
)
{
if (nodePtr == NULL)
return;
printTree(nodePtr->leftPtr_);
printf("%s\t%d\n",nodePtr->wordCPtr_,nodePtr->count_);
printTree(nodePtr-
ightPtr_);
}
PURPOSE: To free the subtree rooted at '*nodePtr'. No return value.
void freeTree (struct TreeNode* nodePt
)
{
if (nodePtr == NULL)
return;
freeTree(nodePtr->leftPtr_);
freeTree(nodePtr-
ightPtr_);
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.0 Joseph 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* filePt
)
{
struct ListNode* firstPtr = NULL;
struct ListNode* lastPtr = NULL;
struct ListNode* listRun;
struct ListNode* newPtr;
char* line = (char*)malloc(textLen);
char word[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)
eak;
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.
void printList (struct ListNode* firstPt
)
{
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.
void freeList (struct ListNode* firstPt
)
{
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.0 Joseph Phillips ---*
*--- ---*
*-------------------------------------------------------------------------*
--- Common inclusions: ---
#include
#include
#include
#include
--- Common constants: ---
#define SMALL_TEXT_LEN 256
--- Common types: ---
struct TreeNode
{
char* wordCPtr_;
int count_;
struct TreeNode* leftPtr_;
struct TreeNode* rightPtr_;
};
struct ListNode
{
char* wordCPtr_;
int count_;
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
. 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
. 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()