Assignment #1 Solution

Purpose:
To go over:
    • Compiler optimizations
    • Program profiling (timing)
    • Header files
    • Linking and object file layout
Computing
Please ssh into one of the following:
    • 140.192.36.184
    • 140.192.36.185
    • 140.192.36.186
    • 140.192.36.187
or use your own Linux machine.
Please submit a .zip file (not .7z or any other non-standard compression!) file of your header file and a .txt/.pdf/.doc/.odt file containing your answer to the questions.
                a. 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             2018 September 9        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*          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.
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(stderr,"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);
    }
    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.0             2018 September 9        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*          filePtr
                                )
{
  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)
          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.
void            printTree       (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.
void            freeTree        (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.0             2018 September 9        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*          filePtr
                                )
{
  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)
          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.
void            printList       (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.
void            freeList        (struct ListNode*       firstPtr
                                )
{
  struct ListNode*      listRun;
  struct ListNode*      nextPtr;

  for  (listRun = firstPtr;  listRun != NULL;  listRun = nextPtr)
  {
    nextPtr     = listRun->nextPtr_;

    free(listRun->wordCPtr_);
    free(listRun);
  }

}
          
                b. Header files (10 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             2018 September 9        Joseph Phillips ---*
 *---                                                                   ---*
 *-------------------------------------------------------------------------*/

//---                       Common inclusions:                  ---//
#include        <stdlib.h>
#include        <stdio.h>
#include        <string.h>


//---                       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!
        
                c. 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:
        b. $ ./wordCounterO0
File name to read: originOfSpecies.txt
Which algorithm would you like to run:
(1) Count words with tree
(2) Count words with linked-list

Your choice? 1
buildTree() self seconds
_____________
        c. $ ./wordCounterO0 
File name to read: originOfSpecies.txt
Which algorithm would you like to run:
(1) Count words with tree
(2) Count words with linked-list

Your choice? 2
buildList() self seconds
_____________
                a. 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:
        d. $ ./wordCounterO2
File name to read: originOfSpecies.txt
Which algorithm would you like to run:
(1) Count words with tree
(2) Count words with linked-list

Your choice? 1
buildTree() self seconds
_____________
        e. $ ./wordCounterO2 
File name to read: originOfSpecies.txt
Which algorithm would you like to run:
(1) Count words with tree
(2) Count words with linked-list

Your choice? 2
buildList() self seconds
_____________
                a. 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()
        g. The local variable rootPtr in buildTree()
        h. The code for printList()
        i. The global variable textLen
Question
Command
Result
(A)
______________________





________________________________ 
(B)
______________________





________________________________ 
(C)
______________________





________________________________ 
(D)
______________________





________________________________ 
                a. Compiler optimizations (Points 30):
Find and show at least 2 examples (total) of the following optimizations in either wordCounterO0 or wordCounterO2.
        j. usage of registers to hold vars (as opposed to the stack)
        k. code motion
        l. reduction in strength
For both:
        m. Tell if it exists in either wordCounterO0, wordCounterO2, or both, and
        n. Show these optimizations in the disassembly of the function that has it