EXAM #3 REVIEW:

Consider the following struct definition:
struct Foo {
  int x;
  double y;
};

-Declare a struct named `foo` that is of type `struct Foo`. Do not initialize it.

// struct Foo foo;

-Using only one statement, declare a struct named `bar` that is of type `struct Foo`, 
 and initialize `x` to be 5 and `y` to be 2.5.

// struct Foo bar = { 5, 2.5 };

-Given only these two code snippets:
1: int main() { /* OMITTED */ }
2: int main( int argc, char** argv ) { /* OMITTED */ }

What can the second snippet do that the first cannot?

// It can use command line arguments.  The first can take command line arguments, 
// but they will be ignored.

-Consider the following complete program:
#include <stdio.h>
int main( int argc, char** argv ) {
  int x;
  for ( x = 0; x < argc; x++ ) {
    printf( "%s\n", argv[ x ] );
  }
  return 0;
}

This program is compiled using make and gcc, forming an executable named `prog`.
Show what the output of `prog` would be for the following invocations:

./prog

// ./prog

./prog 1 2 3

// ./prog
// 1
// 2
// 3

./prog foo bar

// ./prog
// foo
// bar

-Define a type of struct called `MyStruct` that contains a member named `one` of 
 type `unsigned char`, and another member named `two` that points to an integer.

// struct MyStruct {
//   unsigned char one;
//   int* two;
// };

-In your own words, explain why the following code will not compile:

struct OddStruct {
  int x;
  struct OddStruct odd;
};

// The struct definition is infinitely recursive; there is no base case.

-Recursive functions need to consider two general cases.  What are the names for 
 these cases?

// 1 - base case
// 2 - recursive case

-What would happen if a recursive function had been defined without any base cases 
 but with recursive cases?

// It would never terminate.

-What would happen if a recursive function had been defined without any recursive 
 cases but with bases cases?

// In general, it would fail to process all the input.

-Consider the following recursive mathematical definition of the factorial function(!):
0! = 1
n! = n * (n - 1)!, for n != 0

Write a recursive function definition for a function named `factorial` that models 
this mathematical definition.  Assume that the function will only be given 
non-negative integers as input.  For full credit, you must not use any 
global variables.

// int factorial( int n ) {
//   if ( n == 0 ) {
//     return 1;
//   } else {
//     return n * factorial( n - 1 );
//   }
// }

-Consider the following recursive code:

struct IntList {
  int item;
  struct IntList* next;
};

int sumIntList( struct IntList* list ) {
  return list->item + sumIntList( list->next );
}

`next` in `IntList` can either point to another `struct IntList`, or hold NULL.
`sumIntList` will get the sum of a chain of `struct IntList` structs.  
With this in mind, what is missing from the current definition of 
`sumIntList` that is needed to make this code work correctly?  
Write in this code.

// `sumIntList` is missing a base case.  The correct version of `sumIntList`:

// int sumIntList( struct IntList* list ) {
//   if ( list == NULL ) {
//     return 0;
//   } else {
//     return list->item + sumIntList( list->next );
//   }
// }

-Consider the following struct definition:

struct SomeStruct {
  int number;
  char* string;
};
  
Write a function definition for a function named `initStruct` that will take:
-A pointer to a `struct SomeStruct` named `p`
-A `int` named `n`
-A pointer to a string named `s`

The function should set the `number` field of the struct pointed to by `p` to `n`, 
and it should set the `string` field of the struct pointed to by `p` to `s`. 
It should not return anything.

// void initStruct( struct SomeStruct* p, int n, char* s ) {
//   p->number = n;
//   p->string = s;
// }

-Consider again your code for `initStruct`. Write an entire program that 
 will do the following:
-Declare a struct SomeStruct.
-Determine the number of characters in the first command line argument. 
 (Hint: use`strlen`)
-Initialize this struct using the previously defined `initStruct` function. Set the 
 `number` field to the number of characters in the argument, and the `string` field 
 to the argument itself.

For example, if the executable's name is `prog2`, then for the following invocation:
./prog2 moo

…the `number` field should be set to 3, and the `string` field should point to a 
string holding "moo".

Make sure to include any libraries needed by this code, and write in a function 
prototype for `initStruct`.  Assume that `initStruct` is defined somewhere valid 
in your code elsewhere.

// #include <string.h>
// void initStruct( struct SomeStruct*, int, char* );
// int main( int argc, char** argv ) {
//   struct SomeStruct s;
//   initStruct( &s, strlen( argv[ 1 ] ), argv[ 1 ] );
//   return 0;
// }

-In your own words, what is allocated on the stack?

// Local variables.  In other words, variables specific to blocks.

-In your own words, what is allocated on the heap?

// Anything with malloc / calloc / realloc.

-When a function is called, do its parameters go on the stack or the heap?

// stack (these are local variables)

-When a _recursive_ function is called, do its parameters go on the stack or the heap?

// stack (these are still local variables)

-What is wrong with the following code:

char string[] = "moo";
char string2[] = "cow";

string = string2;

// You cannot reassign arrays in C.

-Consider the above definitions of `string` and `string2`.  Say I want `string`'s 
contents to be that of `string2`, and `string2`'s contents to be that of `string`.  
Write some code that will swap the content of these strings. (Hints: you will 
need some temporary space to perform the swap, along with the `strcpy` function.)

// char temp[ 4 ];
// strcpy( temp, string );
// strcpy( string, string2 );
// strcpy( string2, temp );

-Consider the following struct definition:

struct Point {
  int x;
  int y;
};

-Define a `struct Square` that has the following members:
-A `struct Point` named `topLeft`.
-An `int` named `width`.

// struct Square {
//   struct Point topLeft;
//   int width;
// };

-In as few words as possible (as few as three gets full credit), what is the 
 value of a pointer?

// A memory address

-For the subsequent questions, consider the following code:

int sumBetween1( int start, int end ) {
  if ( start > end ) {
    return 0;
  } else {
    return start + sumBetween1( start + 1, end );
  }
}

int sumBetween2( int start, int end ) {
  int retval = 0;
  while( start <= end ) {
    retval += start;
    start++;
  }
  return retval;
}

-Is sumBetween1 recursive?  Why or why not?

// Yes.  It calls itself.

-Is sumBetween2 recursive?  Why or why not?

// No.  It doesn't call itself.

-Write a definition for a function named `filterPositive` that takes the following parameters:
-An integer array named `src`
-An integer array named `dest`
-An integer named `length`

The function will copy over positive integers from `src` into `dest`.  Each array is
guaranteed to be of length `length`.  The function should return the number of 
positive integers copied over.

For example, if given the array `src` is:
{ -1, -3, 2, -6, 4 }

…then `dest` should look like:
{ 2, 4, <<undefined>>, <<undefined>>, <<undefined>> }


// int filterPositive( int* src, int* dest, int length ) {
//   int srcPos;
//   int destPos = 0;
// 
//   for( srcPos = 0; srcPos < length; srcPos++ ) {
//     if ( src[ srcPos ] > 0 ) {
//       dest[ destPos ] = src[ srcPos ];
//       destPos++;
//     }
//   }
//   return destPos;
// }

-Consider the following code:

int whoKnows( int* array, int n, int a ) {
  if ( n == 0 ) {
    return a;
  } else if ( array[ 0 ] > a ) {
    return whoKnows( array + 1, n - 1, array[ 0 ] );
  } else {
    return whoKnows( array + 1, n - 1, a );
  }
}

int callWhoKnows() {
  int array[] = { -1, -2, 4, 2, 3, 7, 11, 5 };
  return whoKnows( array + 1, 7, array[ 0 ] );
}

Determine what the `whoKnows` function computes.  Name it more appropriately, 
given the following candidate names: average, countEven, countMax, countMin, 
countNeg, countOdd, countPos, countSevens, indexFirstEven, indexFirstOdd, 
indexOfMax, indexOfMin, isSorted, maxValue, minValue, noDups, sum, sumEven, 
sumNeg, sumOdd, sumPos.

// maxValue

-Consider the following code:

struct Point {
  int x;
  int y;
};

struct Circle {
  struct Point center;
  int radius;
};

struct ConcentricCircle {
  struct Circle* circles;
  int numCircles;
}

struct Point point;
struct Circle circle;
struct ConcentricCircle concCircle;

// OMITTED INITIALIZATION CODE

With respect to the above code, determine the type of each of the following 
expressions, writing ERROR if there is a type error:

point // struct Point
&point // struct Point*
*(&point) // struct Point

circle.center // struct Point
circle.radius // int

concCircle->numCircles // ERROR
concCircle.circles // struct Circle*
concCircle.circles[ 0 ] // struct Circle

-Consider the following code:

unsigned char arr[] = { 1, 2, 3 };
unsigned char* p = arr;

Write a memory diagram illustrating how this looks in memory.  Note where 
variables are in memory and where things are pointing using arrows.

// A diagram showing { 1, 2, 3 } in memory, and p pointing to the start of { 1, 2, 3 }.  
// `p` should itself be in memory, holding the address of wherever the `1` is.  
// Note that `arr` is a constant, and is not directly in memory as a result.)

-Assume that the variable `numInts` is an integer holding some positive value. 
 Write an expression that will allocate `numInts` number of integers on the heap.

// malloc( sizeof( int ) * numInts )

-Consider the following code:
int* m = malloc( sizeof( int ) * 5 );
int* c = calloc( sizeof( int ), 5 );

Give what the value of each of the following expressions is, or say UNDEF 
if the value is undefined, or ERROR if the code would not compile:

m[ -1 ] // UNDEF
c[ -1 ] // UNDEF
m[ 5 ] // UNDEF
c[ 5 ] // UNDEF
m[ 0 ] // UNDEF
c[ 0 ] // 0
m[ 4 ] // UNDEF
c[ 4 ] // 0

-In your own words, what is a void*?

// A pointer without context.  I.e. it holds some memory address, but without any 
// other information we don't know how to interpret what is at that memory address.

-In your own words, why does malloc return a void*?

// malloc allocates some block of memory, and how we use that memory is up to the
// programmer. The same function is used to allocate integers, characters, structs, 
// and so on, so by returning a void* it remains generic (we don't need a separate 
// malloc for ints, chars, etc.).

-What is wrong with the following code?

void foo( int numInts ) {
  int arr[ numInts ];
  int x;
  for( x = 0; x < numInts; x++ ) {
    arr[ x ] = x;
  }
}

// The number of array elements declared for an array must be a constant.
// `numInts` is a variable here.

-Consider the function prototype for realloc:

void* realloc( void*, size_t size );

What happens when NULL is passed to realloc, as with:
realloc( NULL, sizeof( int ) )

// realloc behaves like malloc

-Write a definition of a function named `intsBetween` that will return all integers 
 between `start` and `end`, which are two integer inputs.  The integers should be in
 order, and the function is inclusive.  If start > end, then it should return NULL.  
 For example:

intsBetween( 2, 4 ) == { 2, 3, 4 }
intsBetween( 3, 3 ) == { 3 }
intsBetween( 4, 2 ) == NULL

Write your function below:

// int* intsBetween( int start, int end ) {
//   if ( start > end ) {
//     return NULL;
//   } else {
//     int length = end - start + 1;
//     int* retval = malloc( sizeof( int ) * length );
//     int pos;
//     for( pos = 0; pos < length; pos++ ) {
//       retval[ pos ] = pos + start;
//     }
//     return retval;
//   }
// }

-What is wrong with the following code:

int* foo() {
  int x = 10;
  return &x;
}

void bar() {
  int* p = foo();
  *p = 20;
}

// `x` is allocated on the stack, and once `foo` returns `x` is no longer alive
// (its memory is no longer available to be used).

-Is there anything wrong in the following code snippets?  If there is something 
 wrong, use the specific name of the error.

void one() {
  malloc( sizeof( int ) );
}

// ^^ Memory leak ^^

void two() {
  int* p = malloc( sizeof( int ) );
  free( p );
}

// ^^ nothing wrong ^^

void three() {
  int* p = malloc( sizeof( int ) );
  free( p );
  free( p );
}

// ^^ double free ^^

int* four() {
  int* p = malloc( sizeof( int ) );
  free( p );
  return p;
}

// ^^ dangling pointer ^^

-List one reason why a programmer may prefer passing a pointer to a struct to a 
 function instead of a struct directly.  (i.e. prefer `void foo1( struct Foo* foo )` 
 to `void foo2( struct Foo foo )`)

// If we pass a struct as opposed to a pointer to a struct, a copy of the struct 
// will be made.  Depending on the context, this can be wasteful.

-List one reason why a programmer may prefer passing a struct to a function 
 directly as opposed to a pointer to a struct. (i.e. prefer 
 `void foo2( struct Foo foo )` to `void foo1( struct Foo* foo )`)

// The function needs to manipulate a copy of the struct as opposed to the 
// original struct. Such manipulation will require modifying the struct.

-Write the definition of a function named `copyString` that will take a pointer 
 to a string and return a pointer to a newly allocated string that is a copy of 
 the original one.  (Hint: you will need `strlen`, `strcpy`, and `malloc`, and you
 may assume that all relevant libraries have already been included.)

// char* copyString( char* string ) {
//   char* retval = calloc( sizeof( char ), strlen( string ) + 1 );
//   strcpy( retval, string );
//   return retval;
// }

-Consider the start †o a function definition:

void addToTable( int** table, int rows, int cols, int toAdd ) {
  // ADD CODE HERE
}

At the point ADD CODE HERE, write in code that will add `toAdd` to each 
element of the table.

// void addToTable( int** table, int rows, int cols, int toAdd ) {
//   int row;
//   for( row = 0; row < rows; row++ ) {
//     int col;
//     for( col = 0; col < cols; col++ ) {
//       table[ row ][ col ] = table[ row ][ col ] + toAdd;
//     }
//   }
// }

As the following code runs (starting at main), what are the values of the 
variables `a` and `b` at the point specified?

void doSomething( struct Foo foo ) {
  foo.x = 10;
  foo.y = 20;
}

int main() {
  int a, b;
  struct Foo foo;
  foo.x = 2;
  foo.y = 3;
  doSomething( foo );
  a = foo.x;
  b = foo.y;
  // What are a and b at this point?

  return 0;
}

// a = 2, b = 3
// doSomething is working with a copy of foo

-Consider the following struct:
struct Foo {
  int x;
  int y;
};

As the following code runs (starting at main), what are the values of the 
variables `a` and `b` at the point specified?

void doSomething( struct Foo* foo ) {
  foo->x = 10;
  foo->y = 20;
}

int main() {
  int a, b;
  struct Foo foo;
  foo.x = 2;
  foo.y = 3;
  doSomething( &foo );
  a = foo.x;
  b = foo.y;
  // What are a and b at this point?

  return 0;
}

// a = 10, b = 20
// doSomething is working directly with foo through a pointer

-Name one reason why a programmer may want to add assertions to code?

// To ensure that assumptions at a given point are true.

-Consider the following code:

#include <assert.h>
int main() {
  int x = 0;
  assert( x = 1 ); // assignment
  return 0;
}

There is a subtle potential problem with this code.  What is it?

// `x` is assigned in an assert.  If assertions are turned off, this assignment 
// to `x` will never happen.  Code should behave the same whether or not 
// assertions are turned on.

-What is printed by the following code?

int x = 1;
if ( x == 1 ) {
  int x = 2;
  printf( "%i\n", x );
}
printf( "%i\n", x );

// 2
// 1

-What is wrong with the following code?
int x = 2;
if ( x > 0 ) {
  int y = 7;
}
x = y;

// y is neither in scope nor alive in x = y;

-What does the following code print (starting execution at main)?

int x = 0;
void foo( int x ) {
  printf( "%i\n", x );
}

void bar( int x ) {
  x = x + 2;
  printf( "%i\n", x );
}

void baz( int x ) {
  if ( 1 ) {
    int x = 2;
  }
  printf( "%i\n", x );
}

int main() {
  int x = 3;
  printf( "%i\n", x );
  foo( x );
  printf( "%i\n", x );
  bar( x );
  printf( "%i\n", x );
  baz( x );
  printf( "%i\n", x );
  return 0;
}

// 3
// 3
// 3
// 5
// 3
// 3
// 3

-What does the following code print, starting execution at main?  
 (Yes, this is from the last exam, and you should expect something like it on this one!)

int x = 0;
void one( int x ) {
  printf( “one: %i\n”, x );
}

void two( int notX ) {
  x = 2;
  printf( “two: %i\n”, x );
}

void three( int notX ) {
  x = x + 3;
  printf( “three: %i\n”, x );
}

void four( int x ) {
  if ( 1 ) {
    int x = 4;
  }
  printf( “four: %i\n”, x );
}

void five( int x ) {
  if ( 1 ) {
    x = x + 5;
  }
  printf( “five: %i\n”, x );
}

int main() {
  one( x );
  if ( 1 ) {
    int x = 8;
    two( x );
    printf( “main1: %i\n”, x );
    three( x );
    printf( “main2: %i\n”, x );
  }
  four( x );
  five( x );
  printf( “main3: %i\n”, x );
  return 0;
}

// one: 0
// two: 2
// main1: 8
// three: 5
// main2: 8
// four: 5
// five: 10
// main3: 5