CSCI 159 Bonus Lab

CSCI 159 Bonus lab exercises

The bonus lab is an independent exercise (we won't be specifically covering it in the labs), and is due by 8pm Friday Dec. 6th

There are as usual two halves: a warm-up exercise working with pointers in general along with pointers to structs (warm-up exercise done in basic.cpp), then an exercise in dynamic memory allocation/deallocation (done in bonus.cpp). There is no design exercise for the bonus lab.

The pointers exercise (basic.cpp) is worth 9 marks.
The memory allocation/deallocation exercise (bonus.cpp) is worth 9 marks.
Both parts are due by 8pm on Friday Dec. 6th

Here is the collection of new C++ syntax elements we'll be using for the bonus lab.

Follow our usual setup process

Log in, open a browser, go to the bonus lab page, open a terminal window:
(see lab 2 if you need a refresher on any of the steps)
get the bonus lab:
make -f make159 csci159/bonus
Go into your bonus directory and begin the edit/compile/test/submit routine:
- to edit basic.cpp: pluma basic.cpp &
- to compile basic.cpp: make basicx
- to test basicx: ./basicx
- to submit: make submit
  once we get to the second half of today's lab:
- to edit bonus.cpp: pluma bonus.cpp &
- to compile bonus.cpp to create bonusx: make bonusx
- to test bonusx: ./bonusx
- to submit: make submit
As with previous labs, you'll see that the two .cpp files are nearly empty to start with.

First half: pointers and pointers to structs (to be done in basic.cpp)

Libraries, constants, and a struct

We'll use our usual iostream and string libraries.

We'll define a SomeGlobal constant (globally) for use with our later pointer/memory address experiments, and define a (struct) datatype to represent fractions.

// datatype to represent a fraction as a numerator and denominator
struct Fraction {
   int numerator;
   int denominator;
};

const double SomeGlobal = 12;

Prototypes

We'll be creating and calling three functions to illustrate the basic functionality of pointers: getVals, displayStruct, and displayInt.

// get two ints from the user
//    and store in integers referenced by the pointer parameters
// (shows use of pointers to achieve pass-by-ref effect)
void getVals(int* ptr1, int* ptr2);

// display various memory addresses and values associated with the parameters
void displayStruct(Fraction* fptr);
void displayInt(int* iptr, int* jptr);

Experimentation in main: part I

We'll start off by having main declare a bunch of int and Fraction variables and a bunch of int* and Fraction* pointer variables.

We'll then experiment with using & to take the addresses of different variables, and use cout to print out the various addresses and the contents of memory at those addresses.

int main()
{
   cout << endl << "===Inside main===" << endl;

   // declare a mix of local variables: ints, pointers to ints, structs, pointers to structs
   int a = 10;
   int b = 20;
   Fraction F = { 1, 2 };
   Fraction G = { 5, 7 };
   int* ptrForInts = &a;        // points at a
   Fraction* ptrForFracs = &F;  // points at F

   // show addresses and contents of local variables and global constant
   cout << "Addresses (in hexadecimal), sizes (bytes), and values of locals are:" << endl;
   cout << "   a: " << (&a) << ", size: " << sizeof(int) << ", value: " << a << endl;
   cout << "   b: " << (&b) << ", size: " << sizeof(int) << ", value: " << b << endl;
   cout << "   F: " << (&F) << ", size: " << sizeof(Fraction) << ", numer: " << F.numerator
        << ", denom: " << F.denominator << endl;
   cout << "   G: " << (&G) << ", size: " << sizeof(double) << ", numer: " << G.numerator
        << ", denom: " << G.denominator << endl;
   cout << "And for the pointer variables:" << endl;
   cout << "    ptrForInts: " << (&ptrForInts) << ", size: " << sizeof(int*) << ", value: "
        << ptrForInts << " (should match a's addr)" << endl;
   cout << "   ptrForFracs: " << (&ptrForFracs) << ", size: " << sizeof(Fraction*)
        << ", value: " << ptrForFracs << " (should match F's addr)" << endl;
   cout << "And for global constant SomeGlobal:" << endl;
   cout << "addr: " << (&SomeGlobal) << ", size: " << sizeof(double) << ", value: "
        << SomeGlobal << endl;
}

Experimentation in main: part II

Next, inside main after the couts above, we'll try using the displayInt and displayStruct functions to show what a function can see when we pass it a pointer to something.

   // use displayInt on the pointer to a and the address of b
   displayInt(ptrForInts, &b);

   // similarly with displayStruct
   displayStruct(ptrForFracs);
   displayStruct(&G);

Experimentation in main: part III

Finally, in main (after the displayStruct calls) we'll try using getVals to change the values of our variables through a pointer to a and through the address of b.

Similarly, we'll try to use it to change the values of F's fields through the addresses of the fields.

   // use getVals to alter the values of a (through the pointer) and b, show the new contents
   getVals(ptrForInts, &b);
   cout << "===Back in main===" << endl;
   cout << "Revised a: " << a << ", revised b: " << b << endl;

   // similarly for the fields of F (numerator through the pointer)
   getVals(&(ptrForFracs->numerator), &(F.denominator));
   cout << "===Back in main===" << endl;
   cout << "Revised fraction numerator: " << F.numerator;
   cout << ", denominator: " << F.denominator << endl << endl;

}

Getting pass-by-ref behaviour through pointers

Because a pointer tells us where in memory something is stored, a function can take that address and alter the memory at that location, giving us behaviour comperable to that of pass-by-reference.

Our getVals function thus modifies the two ints whose addresses main passed to getVals.

void getVals(int* ptr1, int* ptr2)
{
   cout << endl << "===Inside getVals===" << endl;
   cout << "Enter two integers: ";
   cin >> (*ptr1);
   cin >> (*ptr2);
}

Accessing basic content through pointers

The displayInt function simply takes any two pointers to ints as parameters and displays both the addresses provided by those pointers and the values stored in memory at those addresses.

void displayInt(int* iptr, int* jptr)
{
   cout << endl << "===Inside displayInt===" << endl;
   // show addresses and contents of parameters and the ints they 'point at'
   cout << "Addr stored in iptr param: " << iptr << ", value stored there: " << (*iptr) << endl;
   cout << "Addr stored in jptr param: " << jptr << ", value stored there: " << (*jptr) << endl;
}

Accessing struct content

Our displayStruct function gets passed a pointer to a Fraction struct, and inside the function we want to access the various fields of the struct.

The 'normal' notation would be to use * to de-reference the pointer, i.e. *fptr, then the . to access a field, e.g.
cout << (*fptr).numerator;

The streamlined notation replaces this with the -> notation, e.g.
cout << fptr->numerator;

Examples of both formats are used in the displayStruct function below.

(As a point of interest, if you look at the output when you run the program you'll see that the address of the first field is the same as the address of the struct as a whole.)

void displayStruct(Fraction* fptr)
{
   cout << endl << "===Inside displayStruct===" << endl;
   cout << "Addr stored in fptr param: " << fptr << endl;

   cout << "Addr of numerator field is: " << (&(fptr->numerator));
   // example accessing a field (numerator) using -> notation
   cout << ", value stored there: " << fptr->numerator << endl;

   cout << "Addr of denominator field is: " << (&(fptr->denominator));
   // example accessing a field (denominator) using  *. notation
   cout << ", value stored there: " << (*fptr).denominator << endl;
}

Sample run:

Below is a sample run of the program, with the user entering 100 200 300 400 as the four requested integers. (Note the specific memory addresses you see when you run it will probably be different, but the results should otherwise match.)

===Inside main=== 
Addresses (in hexadecimal), sizes (bytes), and values of locals are: 
   a: 0x7ffe3a4e0d1c, size: 4, value: 10 
   b: 0x7ffe3a4e0d18, size: 4, value: 20 
   F: 0x7ffe3a4e0d10, size: 8, numer: 1, denom: 2 
   G: 0x7ffe3a4e0d08, size: 8, numer: 5, denom: 7 
And for the pointer variables: 
    ptrForInts: 0x7ffe3a4e0d00, size: 8, value: 0x7ffe3a4e0d1c (should match a's addr) 
   ptrForFracs: 0x7ffe3a4e0cf8, size: 8, value: 0x7ffe3a4e0d10 (should match F's addr) 
And for global constant SomeGlobal: 
addr: 0x55dcb80a94b0, size: 8, value: 12 
 
===Inside displayInt=== 
Addr stored in iptr param: 0x7ffe3a4e0d1c, value stored there: 10 
Addr stored in jptr param: 0x7ffe3a4e0d18, value stored there: 20 
 
===Inside displayStruct=== 
Addr stored in fptr param: 0x7ffe3a4e0d10 
Addr of numerator field is: 0x7ffe3a4e0d10, value stored there: 1 
Addr of denominator field is: 0x7ffe3a4e0d14, value stored there: 2 
 
===Inside displayStruct=== 
Addr stored in fptr param: 0x7ffe3a4e0d08 
Addr of numerator field is: 0x7ffe3a4e0d08, value stored there: 5 
Addr of denominator field is: 0x7ffe3a4e0d0c, value stored there: 7 
 
===Inside getVals=== 
Enter two integers: 100 200 
===Back in main=== 
Revised a: 100, revised b: 200 
 
===Inside getVals=== 
Enter two integers: 300 400 
===Back in main=== 
Revised fraction numerator: 300, denominator: 400

Looking at the output, we can see that the addresses stored inside the iptr, jptr, and fptr (twice) parameters do indeed match the addresses for the original variables (a, b, F, G).

FOR CURIOUSITY ONLY:
If we decrypt a little of the hex we can also see that many of the variables and parameters wind up side-by-side in memory.
Using the memory addresses from the run above, and looking at just the last 3 digits of the memory addresses, the following table shows the address and size of each of the variables.

variable	addr (hex)	addr (decimal)	size (bytes)
a	d1c	2396	4
b	d18	2392	4
F	d10	2384	8
G	d08	2376	8
ptrForInts	d00	2368	8
ptrForFracs	cf8	2360	8

(The global constant, on the other hand, is in a completely different section of memory.)

Second half: dynamic memory allocation/deallocation (to be done in bonus.cpp)

For this half of the lab we'll use a struct to hold both the size of an array and a pointer to the actual array content, and practice generating and freeing the actual array space as the program runs:

the user will get to pick an array size and we'll generate an array of that exact size
the user will get to pick min/max values to be stored in the array and we'll fill the array with random values from that range, then print the array content
we'll then deallocate the array, freeing up the memory it was using

The libraries, constants, and the struct for our array size and pointer:

The iostream and string libraries are our usuals, but this time we'll also make use of ctime and cstdlib as part of initializing our pseudo-random number generator, and the 'nothrow' option will be used as part of our array allocation request.

#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::nothrow;

// structure to hold an array of numbers and its size,
// using a pointer for the array since it will be dynamically allocated/deallocated
struct numArray {
   long size;
   long* data;
};

// maximum number of characters to skip on bad input
const int LineLen = 80;

The functions we'll make use of:

We'll need our usual getInteger function to get non-negative integers from the user, plus functions to allocate, fill, print, and deallocate the array.

The array information (pointer and size) are parts of a struct, so we'll be passing the struct as a parameter to the various functions (by reference in cases where the function needs to alter the struct).

// get a non-negative integer value from the user (using the prompt provided)
long getInteger(string prompt);

// attempt to allocate the array within narr, using the specified array size,
// return true if successful, false otherwise
bool allocate(numArray &narr, long sz);

// deallocate the array component of narr and set the data and size
//    fields to null and 0 to indicate it is now empty
void deallocate(numArray &narr);

// fill the given numArray with random values in the range min..max (inclusive)
void fillRand(numArray &narr, long min, long max);

// print the given numArray's content
void print(numArray narr);

The main routine:

The main routine is primarily just the central data holder and organizer for our struct and user information, it:

initializes the random number generator (using the system clock)
creates a variable of type numArray to eventually hold the array of information
gets the desired size and value range from the user
attempts to allocate the array and, if successful
- fills the array
- prints the array
- deallocates the array

int main()
{
   // initialize the random number generator
   srand(time(NULL));

   // set up the empty table and get the desired size and value range from the user
   numArray dataTable;
   int numEntries = getInteger("How many data values would you like to store?");
   int minVal = getInteger("What is the smallest allowable data value (integer)?");
   int maxVal = getInteger("What is the largest allowable data value (integer)?");

   // attempt to allocate the table, then fill, print, and deallocate it if successful
   if (allocate(dataTable, numEntries)) {
      cout << "Now filling the table with random data" << endl;
      fillRand(dataTable, minVal, maxVal);
      cout << "The resulting table content is:" << endl;
      print(dataTable);
      cout << "Now deleting the table" << endl;
      deallocate(dataTable);
   }
}

The allocation function:

The allocation routine should:

check that the requested size is valid (this is a last line of defense in case the getInteger routine earlier has missing or broken error checking),
initialize the pointer and size to null and 0 (so we have known values in case the allocation fails),
attempt the allocation of the array using new (with nothrow to prevent exception generation since we don't yet know how to handle exceptions) and storing the address new gives us,
check that it worked (i.e. narr.data isn't null any more), set the size field and return true
display appropriate error messages and return false if anything went wrong

bool allocate(numArray &narr, long sz)
{
   // check the size is valid and attempt the allocation
   if (sz > 0) {
      narr.data = nullptr;
      narr.size = 0;
      narr.data = new(nothrow) long[sz];
      if (narr.data) {
         narr.size = sz;
         return true;
      } else {
         cerr << "Error: allocation failed for array of " << sz << " longs" << endl;
      }
   } else {
      cerr << "Error: allocate needs a positive number of elements (given " << sz << ")" << endl;
   }
   return false;
}

The deallocation function:

The deallocation function should:

make it's own check of the struct's pointer and size to make sure it is being asked to delete something valid (giving an error message if not)
delete the array's storage,
update the pointer and size fields to reflect the fact that there is no longer any storage associated with the array

void deallocate(numArray &narr)
{
   if (narr.data) {
       delete [] narr.data;
       narr.data = nullptr;
       narr.size = 0;
   } else {
       cerr << "Warning: deallocate called on unallocated array" << endl;
   }
}

The fill and print functions:

Fill and print should each check that the given struct actually has appropriate size and pointer fields (a non-null pointer), then process each element of the array. Fill should also make sure that the min..max range is valid.

In each case, we're using a for loop to access each array position in turn, i.e. narr.data[p] for position p.

Fill also has to worry about generating a random number in the range min..max, which is reflected by the formula for val in the code below.

(I'm assuming everyone can implement a suitable getInteger with appropriate error checking by now.)

void fillRand(numArray &narr, long min, long max)
{
   if (narr.data == nullptr) {
      cerr << "Warning: fill called on unallocated array" << endl;
   } else if (narr.size < 1) {
      cerr << "Warning: fill called on array with 0 or negative size (";
      cerr << narr.size << ")" << endl;
   } else if (min > max) {
      cerr << "Warning: fill called with impossible data range (values > ";
      cerr << min << " but < " << max << ")" << endl;
   } else {
      for (int p = 0; p < narr.size; p++) {
          // generate a pseudo-random value in the range min..max (inclusive)
          long val = min + (rand() % (1 + max - min));
          // place in the next position in the array
          narr.data[p] = val;
      }
   }
}

void print(numArray narr)
{
   if (narr.data == nullptr) {
      cerr << "Warning: print called on unallocated array" << endl;
   } else if (narr.size < 1) {
      cerr << "Warning: print called on array with 0 or negative size (";
      cerr << narr.size << ")" << endl;
   } else {
      for (int p = 0; p < narr.size; p++) {
          // display the next array element
          cout << narr.data[p] << endl;
      }
   }
}

Sample run:

Below is a sample run of the program, with the user specifying 7 as the desired array size and 13 to 104 as the desired value range.

How many data values would you like to store? 
7 
What is the smallest allowable data value (integer)? 
13 
What is the largest allowable data value (integer)? 
104 
Now filling the table with random data 
The resulting table content is: 
42 
90 
61 
86 
13 
51 
71 
Now deleting the table