Pointers
--------

Reading:  Chap 10.1-10.2, 18.1-18.2

Pointers
   - a pointer is a VARIABLE
     - that contains the memory location of data but not the data itself

     e.g.
     int *p;   // creates a variable called p. its type is "pointer to int". 
               // read right to left.
 
     int x;   // creates a variable of type int
 
     x = 4;
 
   - address operator

     p = &x;  // & (address operator)
              // gets the location of x and stores it in p
 
   - dereference operator

     y = *p;  // * (dereference operator)
              // y gets the value 4 (*p can be used wherever x can be used)

                         Address X 4
          ___________
         |___________|  4000000
         |___________|  3999999
         |___________|      ...
       p |_ 300000 __|   400000
         |___________|      ...
       x |______ 4 __|   300000
         |___________|      ...
         |___________|        5
         |___________|        4
         |___________|        3
         |___________|        2
         |___________|        1
         |___________|        0
 
          ___________            ___________
       p |___________|------> x |______ 4 __|
         (pointer to int)       (int)
 
    - you can see how this can lead to making a linked list!
 

Memory Allocation and Pointers

   - int *p; does not creat an integer
     - it creates a pointer to integer

   - one way to create an integer to which p points is
     - Declare "int x"
     - Then p can be assigned to the memory location of x (p = &x)

   - another way is to create an integer dynamically
     p = new int; //  assign memory location of dynamically created int
     *p = 10;

          ___________
         |___________|  4000000
         |___________|  3999999
         |___________|      ...
       p |_ 300000 __|   400000
         |___________|      ...
       x |______ 4 __|   300000
         |___________|      ...
         |___________|        5
         |___________|        4
         |___________|        3
         |___________|        2
         |___________|        1
         |___________|        0

          ___________            ___________
       p |___________|        x |______ 4 __|
         (pointer to int)       (int)
               |
               |                 ___________
               ------------->   |_____ 10 __|
                                (int)
 
      x = *p;   // what happens?
      x = p;    // is this correct?
 
   - NULL value
     - indicates that a pointer does not point to a valid region
     - int *p = NULL;   // NULL is actually 0. memory address 0 is never used
 
   - memory deallocation
     - memory is allocated dynamically using "new p"
     - it must be deleted using

       delete p;
     
     - more below
 
  
Memory Management and Deallocation

   Types of memory

       ___________
      |           |
      |           |  stack (local variables, variable size)
      |___________|
      |     |     |
      |     V     |
      |           |   unallocated memory
      |     ^     |
      |_____|_____|
      |           |
      |           |  heap (dynamically allocated memory, variable size)
      |___________|
      |           |
      |           |  static data (global variables)
      |___________|      
      |           |
      |           |  code (read-only)
      |___________|
      
      

   Heap
    
      - allows variables to be allocated dynamically
      
      - allows arbitrary variable lifetimes

      - space allocated when "new" is called
      
        int *p = new int; // allocates an integer and returns a pointer to it
        
        - note that p is a pointer that is allocated on the stack
      
      - space must be explicitly deallocated
      
        delete p;  // deletes the object pointed to by p
        
        - every new should eventually be followed at some point with a delete
      
        int *
        alloc_func()
        {
            int i;
            int *p;
            
            p = new int;
            return p;   // okay
            
        } // i and p are deallocated. *p is not deallocated

        int *
        error_func()
        {
            int i;
            int *p;
            
            i = *p;     // initialization error
            p = &i;
            
            delete p;   // deleting stack memory error
            return &i;  // returning stack memory error
        }
        
        int *
        error2_func()
        {
            int *p = new int;
            
            p = new int;  // error: first piece of memory is lost
            delete p;
            delete p;     // error: possible corruption, NULL out pointer
        }
        
      - show figure of the memory areas in the heap

More Examples
-------------

   1)
   
      int *p;
      int **pp;
      int *p2;

      pp = &p;

      pp = p;             // type mismatch
      pp = *p;            // type mismatch
      p2 = pp;            // type mismatch
      *pp = p;            // allocation bug, unless pp = &p has been done
      **pp = *p;          // allocation bug, unless pp = &p has been done
      &p = pp;            // non lvalue in assignment
      p = new int; p2 = p; *p = 10; // what is the value of p2? - 10
      p2 = p; p = new int; *p = 10; // what is the value of p2? - undefined
      
   2) Is there a problem with this code?
    
       for (Node *p = ptr; p != NULL; p = p->next) {
           delete p;
       }
       
       If there is a problem, how would you fix it?
       
   3) Is there a problem with this code?
   
      Node *node = new Node;
      Node *n = node;
      
      delete node;
      node = NULL;
      delete n;