Be a Pointer Expert

Question 1

Multi-Dimensional Arrays

Answer 1

• Remember, a 2-dimensional array is just an array of arrays.
• Like this one. It’s a 6-element array of 3-element arrays of shorts.
  short palette[][ 3 ] = {
  { 1000, 0, 0 },
  { 750, 1000, 500 },
  { 250, 750, 0 },
  { 1000, 0, 750 },
  { 500, 500, 500 },
  { 0, 750, 1000 }
  };
• The important part:
  – With each row the same length, the compiler knows where to find each element based on its indices.

Question 2

Taking Multi-Dimensional Arrays Apart

Answer 2

• There are lots of different ways to access the
  contents of this array.
• Just a plain old value: palette[1][2]
• Address of a value: &(palette[3][1])
  short palette[][ 3 ] = {
  { 1000, 0, 0 },
  { 750, 1000, 500 },
  { 250, 750, 0 },
  { 1000, 0, 750 },
  { 500, 500, 500 },
  { 0, 750, 1000 }
  };
• Each row is a 3-element array.
• So, an expression like: palette[i]
  – Should evaluate to row i, an array of
  shorts
  – And it does …
  – Like any other array, it evaluates to the
  address of the row’s first element.
  – So, palette[ 1 ] has type “pointer to short”
• We can use palette[ 1 ] like any
  other pointer to short.
  – Copy it to a pointer variable.
  – Pass it to a function.
  – Do pointer arithmetic with it
  short palette[][ 3 ] = {
  …;
  };
  short *p = palette[ 2 ];
  short *q = palette[ 3 ] + 1;
  *q = 50;
• So, syntax like palette[ i ] lets us work
  with rows
  – via pointers to a row’s first element.
• What about syntax like: palette
  – This must be a pointer that lets us get to
  the whole 2D array.
  – i.e., a pointer to its first element
  (the whole first row)

Question 3

Comparison Pointers

Answer 3

• What’s the difference?
  – These pointers point to the same location.
  – But they have different types (they point to different-sized things)
  palette[0] and palette
  Type Matters
• Since they point to different sized things.
  – They behave differently under pointer arithmetic.
  (Look at the google doc)

Question 4

Type Matters

Answer 4

When using palette and I just say palette, that’s a reference to the first row and it moves rows when I do pointer arihtmetic. When passing it to a function: I can do void f( short pal[][3] )
{
. . .;
} which will evaluate pal to pointer
What if I want to dynamically
allocate this array?
We’ll need to be able to declare a pointer with this type.

Question 5

Taking Multi-Dimensional Arrays Apart(Pointer Syntax for 2D Array

Answer 5

• Well, if A is an array of Xs,
  A evaluates to a pointer to an X
• palette is an array of colors
  (where a color is an array of 3 shorts)
• So, palette evaluates to a pointer to a color,
  a 3-element array of short.
• How do we write this?
  – short color[3]; -> I’m an array of three shorts
  – short (cptr)[3]; -> I’m a pointer to three shorts
  short palette[][ 3 ] = {
  { 1000, 0, 0 },
  { 750, 1000, 500 },
  { 250, 750, 0 },
  { 1000, 0, 750 },
  { 500, 500, 500 },
  { 0, 750, 1000 }
  };
  short (cptr)[3]; -> need to have parenthesis so square brackets would not take precedence
  cptr = palette;
• We can use this type to pass palette to a function.
  void f( short (*p)[ 3 ] ) {
  …;
  }
  f( palette );
• We could get an offset into the palette array.
  short (*p2)[ 3 ] = palette + 2;
  p2[ 1 ][ 2 ] = 25; -> the first row of an array isthird row so this will move it down to th fourth row third element and make it 25
• Or pass that to a function.
  f( palette + 3 );

Question 6

Alternative Array Syntax for 2D Arrays and Beyond

Answer 6

• We have an alternative, simplified syntax for
  passing arrays to functions.
  void f( short p[][ 3 ] ) {
  …;
  }
  void f( short (*p)[ 3 ] ) {
  …;
  }
• And this is what it means.
• Elsewhere, we have to use the pointer syntax.
• Let’s practice.
  int a[ 5 ][ 10 ]; -> array of 5 things
  int (ap)[ 10 ] = a; -> pointer to the first one
  double b[ 10 ][ 5 ][ 3 ]; -> array of 10 things
  double (bp)[ 5 ][ 3 ] = b; -> pointer to the first one

Question 7

MultiDimensional Arrays (dynamically allocate 2D array)

Answer 7

• These pointer types are exactly what we need to dynamically allocate 2D arrays.
  short (pal)[ 3 ];
  int N = 1000;
  pal = (short ()[3])malloc(N * 3 * sizeof(short)); -> goofy the * because there is no variable name but star says if there was one it would take precedence over brackets
• Now, we can use this pointer just like
  an N X 3 array of shorts.
  pal[ 5 ][ 2 ] = 850;

Question 8

MultiDeimension Arrays(Dynamically Allocate 2D Array Full Example)

Answer 8

• C99 lets us define variable-sized arrays
• The same technique lets us allocate variablesized arrays on the heap instead of the stack.
  int R = 500;
  int C = 400;
  int (a)[ C ]; -> I’m a pointer to a
  row of C ints.
  a = (int ()[C])malloc( R * C * sizeof( int ) ); -> Now, I point to the first of R rows.
  for ( int i = 0; i < R; i++ )
  for ( int j = 0; j < C; j++ )
  a[ i ][ j ] = i * j; -> See, works just like
  a 2D array

Question 9

Freeing Memory

Answer 9

• The last two arrays are each stored in one big
  block.
• We can free them with one call to free().
  free( pal ); -> Free the N X 3 array of shorts.
  free( a ); -> Free the R X C array of ints.

Question 10

Arrays of Pointers

Answer 10

• Alternatively, you can structure your array
  Java-style, as an array of pointers to arrays.
• This takes some more work, but it offers more flexibility.
  Picture on doc
• We can figure out what types we need to
  make this work.
  First we have to create the outer array
• … then each of the inner arrays.
  int **b;
  b = (int **)malloc( R * sizeof( int * ) );
  for ( int i = 0; i < R; i++ )
  b[ i ] = (int *)malloc( C * sizeof( int ) );
  When it’s time to free the array,
  it’s going to take more work.
  for ( int i = 0; i < R; i++ )
  free( b[ i ] );
  free( b );
• There are some tradeoffs with this
  representation.
  Extra storage overhead
  Maybe less locality
  Array doesn’t need to be rectangular(rows are not same length if needed)

Question 11

Array of Strings

Answer 11

• We can use similar techniques for
  representing arrays of strings.
  A 2D Array of characters.
  char words[][ 14 ] = {
  “eggplant”,
  “nap”,
  “establishment”,
  “synergy”,
  “paleolithic”,
  “seaweed”
  };
  An array of char pointers.
  char *words[] = {
  “eggplant”,
  “nap”,
  “establishment”,
  “synergy”,
  “paleolithic”,
  “seaweed”
  };
  Here, we’re doing stack allocation instead of heap.
  sizeof() is different for these
• Here words has type: char (*ptr)[ 14 ];
• But here, it has type: char **ptr;
• for both:
  – words[3][5] is a character (g)
  – words[1] is a char pointer (nap)
  – words gets you the whole array (but the types differ)
• The second one is how argv[ ] is
  represented

Question 12

Pointers Functions

Answer 12

• There’s anther type of pointer, a pointer to a
  function.
• We can store a pointer for the starting address of a function, and call the function later via this pointer
  – If this is a function:
  int f( char str ) …
  – This is a pointer to a function:
  int (fp)( char * ); -> a pointer to a function that takes a pointer to char and returns an int
  This can hold a pointer to function f, or any function of the same type.
  We’re declaring a variable named fp.
  This looks like a function prototype, with all the parameter types.
  … and, a star and parentheses around
  the function name.

Question 13

Storing Function Pointers

Answer 13

• The name of a function evaluates to a pointer
  to that function.
• So, we can store a function pointer like this:
  int (*fp)( char *str );
  fp = myFunction;
  int myFunction( char *str ) {
  …;
  return someValue;
  }
  int x = fp( “hello world” );

Question 14

Using Function Pointers

Answer 14

int stringLength( char str )
{
char p = str;
while ( *p )
p++;
return p - str;
}
int main( int argc, char *argv[] )
{
int (f)( char * );
f = stringLength;
for ( int i = 0; i < argc; i++ ) {
int result = f( argv[ i ] );
printf( “%d\n”, result );
}
…
Print the length of each string on the
command line.
This is worth something, but it’s not how you
normally use function pointers
int applyFunction( char **strings,
int stringCount,
int (f)( char * ) )
{
int total = 0;
for ( int i = 0; i < stringCount; i++ ) {
total += f( strings[ i ] );
}
return total;
}
This is more typical.
This will apply any function f to the list of strings, returning the total.
applyFunction( argv, argc, stringLength );
applyFunction( argv, argc, countVowels );
We can get applyFunction() to use
different functions, without even knowing
the particular function it’s using.

Question 15

Reading Types

Answer 15

• Now, we have lots of building blocks for defining new
  types
  – fundamental and specialized types
  – arrays, pointers and function pointers
  – const
  – And we’re not done yet
• We have a whole syntax for defining type expressions
• But, we still just need the same rules for reading type
  – Start at the name of the thing being declared (or where its
  name would be if it had a name)
  – Work your way out, respecting precedence

Question 16

Fun With Reading Types

Answer 16

• Can you describe the types of the following?
  int (f)( int, void ()( char ) );
  void ((g)( int const *, float ))();
  int (h)( float const * const ,
  double ()( float));
  A Larger Example
• I have listOfFunctions.c as a larger example …
  let’s take a look.
  – It maintains a list of function pointers.
  – Gives us some practice reading and writing
  function pointer types
  – Demonstrates the chain of responsibility pattern.
  bool (*testList[ 10 ])( int );
  read right to left

Question 17

Function Pointers in the Standard
Library

Answer 17

• Function pointers have been around since the beginning.
• Consider atexit(). It lets you register a function to be called at normal program termination.
  int atexit( void (*function)(void) );
• There’s also qsort(). It lets you sort arrays of
  anything you want. You just have to tell it how
  to compare them.
• The pointersInLibc.c example demonstrates
  this and atexit()
  void qsort(void base, -> Start of the array
  size_t nmemb, -> Number of items
  size_t size, -> Size of each
  item
  int(compar)(const void *, const void *));-> Comparison rule, returns negative,
  zero or positive.

Question 18

Sort Examples

Answer 18

• Pretend we want to sort an array of ints.
  int list[8] = {
  250, 90,
  710, 270,
  45, 109,
  365, 33
  };
  qsort( list,
  8, sizeof( list[ 0 ] ),
  myComp -> I know how to compare two array elements(given pointers to them)
• The comparison function gets generic pointers to two elements.
  – qsort() doesn’t know
  what type of thing
  I’m sorting.
  – qsort() gives the comparison function addresses of two elements… as two void pointers.
  int myComp( void const *aptr, void const *bptr )
  {
• My comparison function knows the actual
  array type.
  – Here, it’s an array of ints.
  – I convert these void pointers
  … to int pointers.
  int myComp( void const *aptr, void const *bptr )
  {
  int const *a = aptr;
  int const *b = bptr;
  Notice, this is pointer-to-int
  (not int)
  and, array elements are const
• This is how all comparison functions will work.
  int myComp( void const *aptr, void const *bptr )
  {
  int const *a = aptr;
  int const *b = bptr;
  if ( *a < *b )
  return -1;
  if ( *a > *b )
  return 1;
  return 0;
  }
  Get two void pointers
  Convert them to pointers to array elements.
  Compare array elements using these more specific pointer types.

Question 19

Sorting Char Pointers

Answer 19

• Now, pretend it’s an array of char pointer
  char *list[8] = {
  ”red”,
  “green”,
  “blue”,
  “orange”,
  …
  };
  qsort( list,
  8, sizeof( list[ 0 ] ),
  stringComp );
  A different comparison
  function.
• Comparison function gets two void pointers.
  int stringComp( void const *aptr, void const *bptr )
  {
• It knows these are secretly pointer to array
  elements, so, pointers to char pointers.
  int stringComp( void const *aptr, void const *bptr )
  {
  char * const *a = aptr;
  char * const *b = bptr;

Question 20

Thinking About Function Pointers

Answer 20

• You should think of function pointers the
  same way you think about abstraction and
  overriding in Java
  – We can talk about something (a function) and
  store it
  – … without committing to exactly what it will dowhen we use it.
• Before C++, this was an important part of how object-oriented code was written in C.