Lecture Outline for Week 5

I. Memory model
	- Memory allocation: procedure stack, heap, global variables
	- Procedure stack
		- when a procedure is called, the caller address is 
		  placed on the stack
		- address for the return value is placed on the stack
		- the value of each parameter is placed on the stack
		- space for each local variable is placed on to the stack
	- When a procedure is returned
		- the return value is copied to the proper location
		- the stack is popped to the previous procedure frame

	Ex: This is legal.
	    int main(void)
            {
                int a;

                a = getvalue();
                print a;
            }

            void getvalue()
 	    {
                int temp = 5;
                return (temp);
            }

	Ex: This is not legal
	    int main(void)
            {
                int *a;

                a = getvalue();
                print *a;
            }

            int *getvalue()
 	    {
                int temp = 5;
                return (&temp);
            }

II. Structures vs. arrays
	- the name of the array is a pointer to the array
	- the name of a structure refers to the entire structure
	- thus we can assign structures using the '=' which we can't do
	  with arrays
	- when structures are passed to and from functions, their VALUE
	  is passed, not a pointer to the structure, unlike arrays
	- NOTE: THIS IS FOR ANSI-C ONLY, NON-ANSI COMPILERS CAN TREAT
	  STRUTURES LIKE ARRAYS OR CAN TREAT FUNCTION CALLS AND RETURNS
	  AS ADDRESSES
	Ex: int A[10];
	    int B[10];
	    A = B;		/* illegal! - copies address of B to A */

	    struct point p1;
	    struct point p2:
            p1 = p2;		/* legal! - copies entire structure contents */

        Ex: int main(void)
            {
                int *array;

                array = getarray();
                print array[0];
            }

            int *getarray()
            {
                int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
                return (array);
            }

	Ex: int main(void)
            {
                struct point p1;
 
	        p1 = getpoint();
                print p1.x;
            }

            struct point getpoint()
            {
                 struct point temp = {1, 2};
                 return (point);
            }

	Ex: same as above but using pointers

	A more complicated example:
	    int main()
	    {
                int a;

                a = xchoosey();
                print a;
            }
	    
            int xchoosey()
            {
                int x, y, sum;
                getinput(&x);
                getinput(&y);
                sum = factorial(x) + factorial(y);
                return sum;
            }
            
	    void getinput(int *x)
            {
               int d;

               scanf("%d", &d);
               *x = d;
            } 
	
	    int factorial(int x)
	    {
                int a = 1;
                while (x > 0)
                    a *= (x--);
	    }

III. Multidimensional arrays vs. pointers to arrays
	- A multidimensional array is a contiguous block of memory (same as
		an array)
	- it can be accessed in two methods, as rows and columns
		Example: a[5][6]
	- or as a single dimensional array
		Example: a[5*rowsize + 6]
	- using multidimensional arrays is often more difficult than an array
	  of pointers to arrays

	int daytab[10][20];
	value = f(daytab);

	int f(int dayarg[10][20]) { ... }
	int f(int dayarg[][20]) { ... }
	int f(int (*dayarg)[20]) { ... }

	what is wrong with the following:
	int f(int *dayarg[20]) { ... }
	int f(int *dayarg[]) { ... }
	int f(int *dayarg[10]) { ... }
	int f(int **dayarg) { ... }

	- array of pointers to arrays
	int *daypointer[10];
	for (i = 0; i < 10; i++)
            daypointer[i] = &(daytab[i][0]);
	value = f(daypointer);

	int f(int **daypointer) { ... }
        int f(int *daypointer[]) { ... }
		- these are now ok

IV. Allocating and freeing memory
	- the heap is an area of memory that is separate from the stack
	- thus we can reserve a chunk of memory from the heap and retain
	  it throughout the program
	- this chunk will not be deallocated (or free'd) until we do so or
	  until the program terminates
	- THERE IS NOT GARBAGE COLLECTION IN C
		- we must explicitly free a piece of memory from the heap
		  once we are finished with it
		- the heap is finite, and if we never free memory, we risk
		  running out of it
	- malloc
		- takes size in bytes as an argument
		- returns a void pointer
		- always test the value returned by a memory allocation
		  routine
		- malloc is the most efficient and universal of the C
		  allocation routines
		- for this class, you may only use malloc() to allocate
		  memory
		ex: int *array;
		    array = (int *)malloc(ARRAYLENGTH * sizeof(int));
		    if (array == NULL) ERROR
	- free
		- takes a pointer
		ex: free((void *)array);
	- calloc
		- like malloc but it initializes the data to 0
		- may be significantly slower than malloc

	- Rules of allocation and deallocation
		- you must never free memory that is not allocated!
		- you must never access a pointer before it has memory
		   allocated to it
		- you must never access memory after it has been freed
		- until a memory location has been freed, you MUST retain
		   a pointer to it
			- memory leaks
				- one of the major errors in industrial C code
				- pointers to allocated memory are lost and
				  thus the memory is never freed
				- the longer a program runs the more resources
				  it hogs until the system runs out of space
		- when you are finished with a piece of allocated memory you
		  must free it
	- useful tip: once you free a memory address, set its pointer
		  to NULL and initialize pointers to NULL
	Ex: 
		char * readword()
		{
                    char *stringptr = NULL;
		    stringptr = (char *)malloc(ARRAYSIZE * sizeof(char));
		    if (stringptr == NULL)
			return;  (ERROR!)
		    else {
                        scanf("%s", stringptr);
			while (isdigit(*stringptr))
                            stringptr++;
                        return stringptr;
                    }
                }

IV. Abstract Data Types
	- fundamental datatypes
		- stack
		- queue
		- tree
	- all of the above can be implemented with linked lists or arrays
		- linked structure in the case of trees
	- static variables 
		- the variable is allocated as if it were a global 
		  variable, but is only active within the function call.
	- abstract data types
		- the program does not care how a particular data type is
		  implemented, just how to use it
		- so we can "hide" the implementation from the program
		- benefits:	
			- the program is easier to read without the extra code
			- we can change the implementation without having
			  to modify the rest of the code
			- it is easier to program without thinking about
			  the little details of a datastructure
	- abstracting datatypes
		- pull the implementation of the data type into a separate .c
		  file
		- place the prototypes, global variables, and constants 
		  which the world needs to know about in a .h file
		- compile with the -c flag to create the object code
		EXAMPLE: use_stack_old.c stack.c stack.h and use_stack.c
		- gcc -c -ansi -Wall -pedantic stack.c
		- gcc -c -ansi -Wall -pedantic use_stack.c
		- gcc -o use_stack use_stack.o stack.o
		EXAMPLE: stack_ll.c changes the implementations
		- gcc -c -ansi -Wall -pedantic stack_ll.c
		- gcc -o use_stack use_stack.o stack_ll.o
	- compiling in C
		- the compiler makes 2 passes
		- first it compiles source C code into object code
			- like assmenbly but includes lookup tables
		- then it links the object code with all necessary libraries
		  and produces the executable
		- with multiple C files, we must compile each down to its
		  object code, then link all of the object code files
		  together