Assignment #1 Solution

Description

5/5 – (2 votes)

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.

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);
  }

}

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!

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:

1. ```
$ ./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

_____________

1. ```
$ ./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

_____________

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:

1. ```
$ ./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

_____________

1. ```
$ ./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

_____________

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.

1. The string "File name to read: " in main()
2. The local variable rootPtr in buildTree()
3. The code for printList()
4. The global variable textLen

Question	Command	Result
(A)	______________________	________________________________
(B)	______________________	________________________________
(C)	______________________	________________________________
(D)	______________________	________________________________

Compiler optimizations (Points 30):

Find and show at least 2 examples (total) of the following optimizations in either wordCounterO0 or wordCounterO2.

1. usage of registers to hold vars (as opposed to the stack)
2. code motion
3. reduction in strength

For both:

1. Tell if it exists in either wordCounterO0, wordCounterO2, or both, and
2. Show these optimizations in the disassembly of the function that has it

Share this:

Share this:

Description

Purpose:

Computing

Please copy-and-paste the following files (0 Points):

wordCounter.c

tree.c

list.c

Header files (10 Points):

Timing: Part 1 (20 Points):

Timing: Part 2 (20 Points):

Parts of an executable (Points 20):

Compiler optimizations (Points 30):

Share this:

Related products

Lab 6: Uniform Matrices Solution

Task 5 Process Synchronization Solution

Assignment-2 Solution

Assignment-2 Solution

One of the philosophies behind Unix is the motto – Assignment 1 Solution