Lecture – Advanced Pointers

Table of Contents

• Lecture – Advanced Pointers
  • Table of Contents
  • References
  • Don't Use Pointers Until Properly Initialized
  • Pointers to Pointers
  • Pointers to struct
  • Pointer in a struct
  • Self-referencing struct
  • Dynamic Memory
  • Dynamic Memory Functions
  • void * and size_t
  • Generic Pointers
  • malloc for arrays
  • calloc for arrays
  • realloc
  • Testing a returned pointer
  • assert
  • free
  • Dynamic Memory for structs
  • Dynamic Teammates
  • Doubly-Linked (Non-Circular) Teammates
  • Doubly-, Circularly-Linked Teammates
  • Returning Dynamic Arrays Using Pointers
  • Dynamic Multi-Dimensional Arrays
  • Linked List Insert and Delete

References

Based from Advanced Pointers http://www.csee.umbc.edu/courses/undergraduate/313/spring12/Lectures/CPointersAdvanced.ppt

Don't Use Pointers Until Properly Initialized

• You should not dereference a pointer until it points to something

• Just declaring a variable to be a pointer is not enough

  char *name;    /* pointer declaration */ 
  
  strcpy(name, "bobby"); 
  scanf( "%s", name); 
  printf( "%s\n", name);
  

Pointers to Pointers

• Since a pointer is a variable type, a pointer may point to another pointer.

• Consider the following declarations

  int age = 42;         
  int *pAge = &age;     
  int **ppAge = &pAge;     

• an int
• a pointer to an int
• a pointer to a pointer to an int

• Draw a memory diagram of these variable and their relationships

• What type and what value do each of the following represent?

  • age, pAge, ppAge, *pAge, *ppAge, **ppAge, *(*ppAge)

Exercise:

int main ( ) {

double gpa = 3.25, *pGpa, **ppGpa; 

pGpa = &gpa; 
ppGpa = &pGpa; 

printf( "%0.2f, %0.2f, %0.2f", gpa, *pGpa, **ppGpa); 
return 0; 
} 

 
 
• double, pointer to double, and
   pointer to a pointer to a double
• pgpa --> gpa
• ppGpa--> pGpa --> gpa
  
• Output? 

Pointers to struct

typedef struct student {  
  char name[50];  
  char major [20]; 
  double gpa; 
} STUDENT_t; 

STUDENT_t bob = {"Bob Smith", "Math", 3.77}; 
STUDENT_t sally = {"Sally", "CSEE", 4.0}; 
STUDENT_t *pStudent;   
pStudent = &bob;                      

printf ("Bob's name: %s\n", pStudent->name); 
printf ("Bob's gpa : %f\n", pStudent->gpa); 

pStudent = &sally; 
printf ("Sally's name: %s\n", pStudent->name); 
printf ("Sally's gpa: %f\n", pStudent->gpa); 

• struct for student data
 
 
 
  
 
 
 
• "pointer to struct student"
  • pStudent --> bob
 
• use -> to access the members
• a->b result is same as (*a).b
  
• pStudent --> sally

Pointer in a struct

The data member of a struct can be any data type, including pointer. The struct person has a pointer to a struct name.

#define FNSIZE 50 
#define LNSIZE 40 

typedef struct name 
{
  char first[ FNSIZE + 1 ]; 
  char last [ LNSIZE + 1 ]; 
} NAME_t; 

typedef struct person {  
  NAME_t *pName;    
  int age; 
  double gpa; 
} PERSON_t;

 
 
 
 
  
 
 
 
 
 
• pointer to NAME struct 
 
 
  
  

Given the code below, how do we access bob's name, last name, and first name?
Draw a diagram of memory represented by these declarations

NAME bobsName = {"Bob", "Smith"}; 
PERSON bob; 
bob.age = 42; 
bob.gpa = 3.4; 
bob.pName = &bobsName;  

How might code access to the 3rd letter of Bob's first name?

Self-referencing struct

• Powerful data structures can be created when a data member of a struct is a pointer to a struct of the same kind.
• The simple example on the next slide illustrates the technique.

typedef struct player 
{ 
  char name[20]; 
  struct player *teammate;  
} TEAMMATE; 
TEAMMATE *team, bob, harry, john; 
team = &bob;
strncpy(bob.name, "bob", 20); 
bob.teammate = &harry;
strncpy(harry.name, "harry", 20); 
harry.teammate = &john; 
strncpy(john.name, "bill", 20); 
john.teammate = NULL: 

• tag "player"
 
 
• can't use TEAMMATE yet, use tag
 
 
• first player
 
• next teammate
 
• next teammate
 
• last teammate

Typical code to print a (linked) list, follow the teammate pointers until NULL is encountered:

 
TEAMMATE *t = team;

while (t != NULL) {
  printf("%s\n", t->name); // (*t).name 

  t = t->teammate;     //t=(*t).teammate; 
}

• start with the first player
• t=&bob
 
• while there are more players...
• print player name
 
• advance to next player 

Dynamic Memory

• C allows us to allocate memory in which to store data during program execution.

• Dynamic memory has two primary applications

  1. Dynamically allocating an array
     • based on some user input or file data
     • Better than guessing and PRE-defining the array size in our code since it can't be changed
  2. Dynamically allocating structs to hold data in some predetermined arrangement (a data structure)
     • Allows an "infinite" amount of data to be stored

Dynamic Memory Functions

These functions are used to allocate and free dynamically allocated heap memory and are part of the standard C library.

• To use these functions, include <stdlib.h> .

  #include <stdlib.h>
  

• void *malloc( size_t nrBytes ); 
  

  • Returns a pointer to dynamically allocated memory on the heap of size nrBytes, or NULL if the request cannot be satisfied. The memory is uninitialized.

• void *calloc( int nrElements, size_t nrBytes ); 
  

  • Same as malloc( ), but the memory is initialized to zero
  • Note that the parameter list is different

• void *realloc( void *p, size_t nrBytes); 
  

  • Changes the size of the memory pointed to by p to nrBytes. The contents will be unchanged up to the minimum of the old and new size. Function copies data to new location as needed. If the new size is larger, the new space is uninitialized. If successful, it returns a pointer to the new memory and care should be taken to not use the old pointer. Upon failure, it returns NULL if request cannot be satisfied in which case p still points to a valid block.

• void free( void *p ) 
  

  • Deallocates the memory pointed to by p which must point to memory previously allocated by calling one of the functions above. Does nothing if p is NULL.

void * and size_t

• The void* type is C's generic pointer. It may point to any kind of variable, but may not be dereferenced. Any other pointer type may be converted to void* and back again without loss of information. void* is often used as parameter types to, and return types from, library functions.

• size_t is an unsigned integral type that should be used (rather than int) when expressing "the size of something" (e.g. an int, array, string, or struct). It too is often used as a parameter to, or return type from, library functions. By definition, size_t is the type that is returned from the sizeof( ) operator.

Generic Pointers

Pointers of type (void *) can be useful to use one pointer variable to point to different data types at different times
(void *) is also the type returned by the dynamic memory allocation function malloc

Example:

void PrintGenericArray(void * ptr, char type, int numElements){ 
    char * c = (char *) ptr; 
    int * i= (int  *) ptr; 
    float * f= (float *) ptr; 
    int j=0; 
    switch (type) { 
        case 'c': for(;j<numElements; j++) printf("%c\n",*(c+j)); break; 
        case 'i': for(;j<numElements; j++) printf("%d\n",*(i+j)); break; 
        case 'f': for(;j<numElements; j++) printf("%f\n",*(f+j)); break; 
    } 
}

malloc for arrays

• malloc( ) returns a void pointer to uninitialized memory.

• Good programming practice is to immediately cast the void* to the appropriate pointer type.

• Note the use of sizeof( ) for portable code.

• As we've seen, the pointer can be used as an array name.

  int *p = (int *)malloc( 42 * sizeof(int)); 
  for (k = 0; k < 42; k++) 
    p[ k ] = k; 
  for (k = 0; k < 42; k++) 
    printf("%d\n", p[ k ]); 
  

  Use of pointer without checking validity

Exercise: rewrite this code using p as a pointer without using [ ]

calloc for arrays

• calloc( ) returns a void pointer to memory that is initialized to zero.
• Note that the parameters to calloc( ) are different than the parameters for malloc( )

  int *p = (int *)calloc( 42,  sizeof(int)); 
  for (k = 0; k < 42; k++) 
  printf(“%d\n”, p[k]); 
  

  Use of pointer without checking validity

realloc

• realloc( ) changes the size of a dynamically allocated memory previously created by malloc( ) or calloc( ) and returns a void pointer to the new memory

• The contents will be unchanged up to the minimum of the old and new size. If the new size is larger, the new space is uninitialized.

  int *p = (int *)malloc( 42 * sizeof(int)); 
  for (k = 0; k < 42; k++)   p[ k ] = k; 
  p = (int *_)realloc( p, 99 * sizeof(int)); 
  for (k = 0; k < 42; k++)   printf( "p[ %d ] = %d\n", k, p[k]); 
  for (k = 0; k < 99; k++)   p[ k ] = k * 2; 
  for (k = 0; k < 99; k++)   printf("p[ %d ]  = %d\n", k, p[k]);
  

  Use of pointer without checking validity

Testing a returned pointer

• malloc( ), calloc( ) and realloc( ) all return NULL if unable to fulfill the requested memory allocation.

• Good programming practice (required as far as exam and projects are concerned) is that the pointer returned should be validated

  Checking pointer validity before use

  char *cp = malloc( 22 * sizeof( char ) ); 
  if (cp == NULL) { 
    fprintf( stderr, "malloc failed\n"); 
    exit( -12 ); 
  }
  

assert

• Since dynamic memory allocation shouldn't fail unless there is a serious programming mistake, such failures are often fatal.

• Rather than using if statements to check the return values from malloc( ), we can use the assert( ) function.

• To use assert( ), you must include <assert.h>

  #include <assert.h> 
  

  char *cp = malloc( 22 * sizeof( char ) ); 
  assert( cp != NULL );
  

• The parameter to assert is any Boolean expression -- assert( expression );

  • If the Boolean expression is true, nothing happens and execution continues on the next line
  • If the Boolean expression is false, a message is output to stderr and your program terminates
    • The message includes the name of the .c file and the line number of the assert( ) that failed

• assert( ) may be disabled with the preprocessor directive #define NDEBUG

• assert( ) may be used for any condition including

  • Opening files
  • Function parameter checking (preconditions)

free

• free( ) is used to return dynamically allocated memory back to the heap to be reused by later calls tomalloc( ), calloc( ) or realloc( )

• The parameter to free( ) must be a pointer previously returned by one of malloc(), calloc() or realloc( )

• Freeing a NULL pointer has no effect

• Failure to free memory is known as a "memory leak" and may lead to program crash when no more heap memory is available

  int *p = (int *)calloc(42,  sizeof(int)); 
  /* code that uses p */ 
  free( p );
  /* remaining code */
  

Dynamic Memory for structs

In C

typedef struct person{ 
    char name[ 51 ]; 
    int age; 
    double gpa; 
} PERSON; 
/* memory allocation */ 
PERSON *pbob = (PERSON *)malloc(sizeof(PERSON)); 
pbob->age = 42;             //same as (*pbob).age = 42; 
pbob->gpa = 3.5;            //same as (*pbob).gpa = 3.5; 
strcpy( pbob->name, “bob”); //same as strcpy((*pbob).name, “bob”); 
... 
/* explicitly freeing the memory */ 
free( pbob ); 

Java

In JAVA a garbage collector frees memory that no longer used/has a reference to it

public class Person         
{ 
  public int age; 
  public double gpa; 
} 
// memory allocation 
Person bob = new Person( );  
bob.age = 42; 
bob.gpa = 3.5; 
// bob is eventually freed by garbage collector 

Dynamic Teammates

typedef struct player{ 
  char name[20]; 
  struct player *teammate; 
} PLAYER; 

PLAYER *getPlayer( ){ 
  char *name = askUserForPlayerName( ); 
  PLAYER *p = (PLAYER *)malloc(sizeof(PLAYER)); 
  strncpy( p->name, name, 20 ); 
  p->teammate = NULL; 
  return p; 
}

int main ( ){ 
  int nrPlayers, count = 0; 
  PLAYER *pPlayer, *pTeam = NULL; 
  nrPlayers = askUserForNumberOfPlayers( ); 
  while (count < nrPlayers){ 
    pPlayer = getPlayer( ); 
    pPlayer->teammate = pTeam; 
    pTeam = pPlayer; 
    ++count; 
  }
   
  /* do other stuff with the PLAYERs */ 
  /* Exercise -- write code to free ALL the PLAYERs */ 
  return 0; 
}

Doubly-Linked (Non-Circular) Teammates

typedef struct player { 
  char name[20]; 
  struct player *nextteammate; 
  struct player *prevteammate; 
} TEAMMATE; 

TEAMMATE *team, bob, harry, john;
team = &bob;

strncpy(bob.name, "bob", 20); 
bob.prevteammate = NULL;       
bob.nextteammate = &harry;    

strncpy(harry.name, "harry", 20);
harry.prevteammate = &bob;    
harry.nextteammate = &john;    

strncpy(john.name, "john", 20);
john.prevteammate = &harry:
john.nextteammate = NULL;    

 
 •head is first player
 •create first player
    ‣write name
    ‣NULL prev teammate
    ‣next teammate
 •create second player
    ‣write name
    ‣prev teammate
    ‣next teammate
 •third second player
    ‣write name
    ‣prev teammate
    ‣NULL next teammate

Doubly-, Circularly-Linked Teammates

typedef struct player { 
  char name[20]; 
  struct player *nextteammate; 
  struct player *prevteammate; 
} TEAMMATE; 

TEAMMATE *team, bob, harry, john; 
team = &bob;                       
strncpy(bob.name, "bob", 20); 
bob.prevteammate = &john           
bob.nextteammate = &harry;         
strncpy(harry.name, "harry", 20);
harry.prevteammate = &bob;
harry.nextteammate = &john; 
strncpy(john.name, "john", 20);
john.prevteammate = &harry:
john.nextteammate = &bob;

 
 
 
• head --> tail
 
 
 
 
• tail --> head
 

Returning Dynamic Arrays Using Pointers

• Local arrays cannot be returned from functions since their lifetime does not extend beyond the function call
  • They typically live on the stack, in a memory area that is deallocated when the function exits
• However, pointers to dynamically allocated arrays may be returned
  • These exist in the heap

    char *getCharArray( int size ){ 
      char *cp = (char *)malloc( size * sizeof(char)); 
      assert( cp != NULL); 

      return cp; 
    }

 
•on the heap
•allocation check with  
    minimal handling
•return pointer to allocated memory

Dynamic Multi-Dimensional Arrays

• There are now three primary ways to define a 2-D array, depending on just how dynamic you want them to be.
• int board[ 8 ] [ 8 ];
  • An 8 x 8 2-d array of int... Not dynamic at all
• int *board[ 8 ];
  • An array of 8 pointers to int. Each pointer represents a row whose size may be dynamically allocated.
• int **board;
  • A pointer to a pointer of ints. Both the number of rows and the size of each row are dynamically allocated.

• Variable Length Arrays and Flexible Array Members will be covered in next lecture

Linked List Insert and Delete

http://www.csee.umbc.edu/courses/undergraduate/201/fall08/lectures/index.shtml
http://www.csee.umbc.edu/courses/undergraduate/201/fall08/lectures/linkedlist/

Cover Implementation: insert and delete