Advanced Pointers

Dynamic Memory Allocation

Allocation Functions

There are a number of valuable functions for dynamically allocating memory ( from the heap ) as programs run. These functions all require #include <stdlib.h>

• void *malloc(size_t size);
  • Allocates size bytes of memory, does not clear it, and returns a void pointer to the address where the memory is located.
  • Void pointers are generic pointers that can point to anything. They must normally be type cast to a real pointer type, either explicitly or implicitly, before they can be used.
  • malloc returns a NULL pointer if the dynamic memory request cannot be granted. The return value should always be checked before itis used.
• void *calloc(size_t nmemb, size_t size);
  • Similar to malloc, calloc allocates enough memory for an array of nmemb elements,where each element is size bytes big. Calloc DOES zero out the memory before returning.
• void *realloc(void *ptr, size_t size);
  • Realloc reallocates memory previously allocated with malloc or calloc. Existing data is unchanged, up to the smaller of the old size or the new size.

Deallocation

When the memory is no longer needed, it should be returned to the memory heap.

• void free(void *ptr);
  • Frees up ( gives back ) the memory pointed to by ptr, which must have previously been allocated with one of the dynamic memory allocation methods described above.
  • FREE DOES NOT CHANGE THE VALUE OF THE PTR VARIABLE.
  • ALWAYS RESET THE POINTER VARIABLE TO NULL AFTER RETURNING MEMORY !

Common Mistakes with Dynamic Memory Allocation

There are a number of errors that occur commonly when using dynamic memory:

1. Dangling Pointers:
   • If dynamic memory is freed up using free, but the pointer variable is not reset back to NULL, then the pointer still contains the address of where the dynamic memory used to be. Using ( following ) this pointer later can have a wide variety of consequences, depending on what if anything is done with that block of memory in the meantime.
   • The problem can be especially difficult to find if multiple pointers point to the same place. Even though one of the pointers may have been reset to NULL, the other pointers could be left dangling.
2. Memory Leaks:
   • If dynamic memory is continuously allocated without ever being freed back up again, the system will eventually run out of memory, which will result in either a stack overflow error or a failure of the dynamic memory allocation calls.
   • This type of error occurs most commonly when dynamic memory is allocated in a loop.
   • Always make sure to free up dynamic memory when it is no longer being used.
   • Always check the return value of malloc, calloc, or realloc to verify that it did not return NULL.
   • Memory leaks can be extremely hard to find, because they often don't result in program failures until the program runs for a sufficiently long time, so unless the program tests run long enough, the problems won't be detected.
3. Double deallocation
   • If an attempt is made to deallocate memory pointed to by a dangling pointer, it can cause all sorts of problems, particularly if that memory has since been reallocated for other purposes.
4. Use of uninitialized pointers
   • As covered earlier, any variable that is not initialized starts out with a random unknown value, which will generally be different from one run of the program to another. If the variable in question is a pointer, then the problem can be especially difficult when the uninitialized pointer is used later on in the program.
     • In a best case, the pointer will point to inaccessable memory, and a "segmentation fault" will occur, stopping the program.
     • If the bad pointer points to a valid location within your data or worse your code, then any number of problems can occur, possibly at some later time in the program.

Dynamically Allocating Strings

Dynamically Allocating Arrays

Linked Lists

Abstract Data Types

Operations Performed on a ( Linked ) List Data Type:

Define a list node

Create an empty list

Create a list node.

Insert a new data item ( node )

• Beginning of the list - easiest
• Maintaining an ordered list - harder.

Remove a data item ( node )

Find a data item ( node )

Determine the length of a list

Destroy a list

More Complex Data Structures, e.g. Advanced Linked Lists, Trees, etc.

• Circularly Linked Lists
  • Normally the last node on a linked list has the "next" field set to NULL.
  • If it points instead to the first node on the list, then the list is circular.
  • Circular linked lists have some advantages, but are also more complicated to maintain and use.
• Doubly Linked Lists
  • Suppose we add a second pointer to each node of a linked list, pointing back to the previous node in the list.
  • Now we can traverse the list back and forth in either direction, but adding and removing nodes is more complicated.
  • Doubly linked lists can also be circular.
• Cross Linked Lists
  • Suppose we have two ( or more ) links in each node, which connect the list based on different criteria:
    • For example, one set of links may connect the nodes in the order by size,and the other by age.
    • Alternatively one set of links could connect all the students in a class, while another set links all the classes a student is taking.
• Binary ( Search ) Trees
  • Each node has two pointers, pointing to two "children"
  • Typically the first points to nodes having a "smaller" value than the current node,and the other to nodes having "larger" values.
  • Greatly speeds up finding data, at the cost of increasing complexity.
    • ( Requires rebalancing the tree occasionally for best performance. )
• N-ary Trees
  • Extend the tree concept to nodes with more than 2 children.
  • For example, a node in a dictionary tree could have 26 children, one for each legal value for the next character in the word.
• Graphs ( Networks )
  • Nodes connected by arbitrary arcs
  • Consider a bus map, with routes connecting different bus stops.
  • Arcs may be directed or undirected.
  • Cycles may or may not be allowed.
• Complex combinations of different struct types.
  • Structs can contain pointers to different kinds of structs
  • The possibilities are endless !

Pointers to Pointers ( to Pointers to . . . )

• Pointer variables can hold the address of any kind of data, including the address of where to find other pointer variables.
• With multiple levels of indirection, pointer variables are declared according to the basic type one eventually gets to if you follow the daisy-chain of pointers long enough. For example:

  int i, *iptr = &i, **iptrptr = &iptr, ***iptr3 = &iptrptr;

• In this example:
  • i is an int.
  • iptr is a pointer to an int, holding the address of an int.
  • iptrptr is a pointer to a pointer to an int, holding the address of an int pointer.
  • iptr is a pointer to ( a pointer to a pointer to an int ), holding the address of an int **
• When using indirection with these types of pointers, just keep asking "what kind of data is this" until you get to a basic type. So for example:
  • i is an int.
  • iptr is an int *, so *iptr is an int.
  • iptrptr is an int **, so *iptrptr is an int *, and **iptrptr is an int.
  • iptr3 is an int ***,so *iptr3 is an int **, **iptr3 is an int *, and ***iptr3 is an int.
• Pointers to pointers allows us to pass pointer variables to functions via the pointer/address passing mechanism, so the function can change the pointer located back in main:

	  void movePointerToNextNode( struct node ** pointer ) {
    
    	 node *p = *pointer;
        p = p->next;
        *pointer = p;
        return;
     }

• And then in main:

	   node *current = NULL;
      
      // code omitted that makes current point into a list
      
      movePointerToNextNode( &current ); // Pointer variable passed by address

• Note that because of the interchangability of pointers and arrays, arrays of pointers can often be considered equivalent to double indirection.
  • For example, the following two function prototypes are equivalent:
    • int main( int argc,char * argv[ ] );
    • int main( int argc, char **argv );

Function Pointers ( Pointers to Functions )

• Pointer variables can hold the address of any kind of data, including the address of where to find functions.
• Pointers to functions are declared according to the argument type and return type of the function that they point to.
• For example:
  • int i; // i is an int
  • int *iptr; // iptr is a pointer to an int
  • int ifcn( double ); // ifcn is a function that returns an int ( and takes a double. )
  • int *iptrfcn( char ); // iptrfcn is a function that returns a pointer to an int ( and takes a char )
  • int (*ifcnptr) ( double ); // ifcnptr is a pointer to ( a function that returns an int and takes a double )
  • int *(*iptrfcnptr) ( node * ); // iptrfcnptr is a pointer to ( a function that returns an int * and takes a node * )
• In order to get the address of a function for assignment to a function pointer variable, simply use the name of the function without ( parentheses ):
  • ifcnptr = ifcn; // The ifcnptr pointer variable now holds the address of the ifcn function.
  • Note carefully that the types of the function pointer and the types of the function it points to must agree.
• In use, the function pointers can be used identically to the functions they point to:
  • int answer = ifcnptr( 3.14159 ); // same as answer = ifcn( 3.14159 );
• In practice, function pointers are often used to allow one function to call any of a number of different functions, without specifying ahead of time which function(s) will be called, provided they all have the correct argument types.
  • For example, the following is a prototype for a function that will find the value of X that yields the largest value of f( X ) over the range from start to end. The function to be optimized is passed in as the first argument:

        double findMax( double ( *fptr ) ( double ), double start, double end );

  • To call this function we can use any function that takes a double and returns a double, so given:

        double sinePlusCosine( double x );
        double sineMinusCosine( double x );

  • Then we can find the maximum value of ( sine( x ) + cosine( x ) ) and ( sine( x ) - cosine( x ) ) over the range from 0 to 2 pi by passing the address of the function as the function name without ( parentheses ).:

        double xMaxPlus = findMax( sinePlusCosine, 0.0, 2.0 * 3.14159 );
        double xMaxMinus = findMax( sineMinusCosine, 0.0, 2.0 * 3.14159 );

  • And then report the results as:

          printf( "The maximum value of sin( x ) + cos( x ) over the range 0 to 2 pi is "
          		" %f, at an X value of %f\n", sinePlusCosine( xMaxPlus ), xMaxPlus );