CS 214 / Objects and pointers
=============================

recap
-----

an object is a contiguous region of memory that is used to store data

to use an object, we need to know (1) its location and (2) its type

we can divide objects into three categories based on lifetime
	static, stack, and heap
	static and stack objects are managed by the run-time system
		-> associated with variables
		-> static
	heap objects are managed by explicit function calls
		-> dynamic
		
		
arrays
------

an array is a sequence of elements of the same type
-> individual elements can be accessed by index

	a[n]  <- expression representing index n in array a
	
array objects are contiguous sequences of element objects (of some type)
-> no other data is stored (that is, no boundaries, length indicators, etc.)

array variables will be automatically associated with an array object


	int a[20];
		<- a names an array of 20 ints
	

	int b[5], c[10];  // declaring multiple array variables
					  // note that the dimension is given for each variable

	
arrays can be of any type

	double d[2];
	
arrays of arrays

	double m[10][10];
		m is an array (length 10) of arrays (each length 10) of doubles
		
	double voxel[10][10][10];
	

array indexing works as <array reference>[<index>]

	a[3]  - is an int
	
	m[i][j]  - is a double
	m[i]     - is an array of doubles
	
	m[i][j]  ==== (m[i])[j]
	
	voxel[x][y][z]  
	
just like any other data, arrays are not initialized by default

	int a[10];   // contents are uninitialized
	
before reading the contents of a, we should write to it

	for (int i = 0; i < 10; i++) a[i] = 0;
	memset(a, 0, 10 * sizeof(int));
	
we can also explicitly initialize array variables

	int b[]  = { 1, 2, 3, 4 };  // implicit dimension
	int c[4] = { 1, 2, 3, 4 };  // explicit dimension
	
	int d[10] = { 1, 2, 3, 4 }; // explicit partial initialization
	
	int m[2][2] = { { 1, 0 }, { 0, 1 } };
		// modern style
		
	int m[2][2] = { 1, 0, 0, 1 };
		// "traditional" style (bad)
		

	int a, b;
	scanf("%d %d", &a, &b);
	
	int m[2] = { a, b };
	
	
we can pass arrays to functions

	int
	sum (int values[], int length)
	{
		int total = 0;
		int i;
		
		for (i = 0; i < length; i++) total += values[i];
		
		return total;
	}
	

	void
	clear (int values[], int length)
	{
		int i;
		for (i = 0; i < length; i++) values[i] = 0;
	}

	
arrays are passed by reference
	-> the address of the array, not its contents
	
	{
		int n[15];
		clear(n, 15);   // sets all the elements of n to 0
		
		int m[30];
		clear(m, 15);  // sets the first 15 elements (0..14) to 0
		
		clear(m + 15, 15); // ????
	
	}
	

strings
-------

C does not have a string type

by convention, sequences of characters ending with a terminator are strings

	strings are data
	strings are stored in char arrays
	
	
	char s[10];
	
	strcpy(s, "hello");  // copies the string into s (5 letters + terminator)
	
the terminator is a specific char value equal to 0
	0, '\0'
do not confuse with '0' (== 48)

	char t[10] = {'h', 'e', 'l', 'l', 'o', '\0'};
	
	char u[10] = "hello";
	char v[10] = "hello";
	
	char w[10] = "";
	
popular string functions

	#include <string.h>
	
	strlen() - counts the characters before the terminator in the provided array
		strlen(w) == 0
	
		strnlen()  - "safe" variant of strlen
	
	strcpy() - copies a string from one location to another
		strcpy(destination, source);
		
		it is your responsibility to ensure the destination is large enough
		
		strcpy(u, v);
		
		strnpy(dest, src, maxlen);
	
	strcmp(x, y) - performs a lexicographic comparison
		returns an integer n
		
		n == 0  if x and y are equal
		n < 0   if x comes before y
		n > 0   if x comes after y



pointers
--------

recall: all data is stored in objects, and all objects have locations

	a pointer is a data value that represents a location (an address)
	
we can use pointers to indirectly refer to objects
	-> only way to refer to heap objects

we can store pointers in pointer variables

	int *p;  // p stores the address of an object
			 // the type of p (int *) indicates the type of the object (int)
			 
			 
	equivalently: int* p; int * p; int*p;
	
	be careful with * placement:
		int* p, q;
			the * only affects the variable immediately after it
			p is int *, but q is just int
	
we can use the unary & operator to get the addresses of objects
	(any expression that can occur to the left of = )

	int n;
	int *p;
	
	p = &n;   // p now has the address of n
	
	int a[10];
	p = &a[1];  // p now has the address of a[1]
		
we can use the unary * operator to dereference a pointer
	(that is, talk about the data it points to)

	int *p;
	p = &n;
	
	
		p   // pointer value (int *)
		*p  // int value (int); same as writing n
		
				*p = 5;  same as n = 5
				
		&p  // pointer to p (int **)
		
		
				int **q;
				q = &p;
				
					*q is the same as p
					**q is the same as n
					
					
		&*p  this is just p again
		*&p  also just p again


what about arrays?

	to index into an array, we need to know
		(1) the location of the array (a pointer)
		(2) the desired index
		(3) the element length (implied by the element type)
		
-> array names are essentially just pointers to the array

	int a[10];
	int *p;
	
	p = a;
	
the bracket syntax works with any pointer, not just array names

	p[1] is the same as a[1]
	
	p = &a[5];
	
	now, p[0] is the same as a[5]
		p[1] is the same as a[6]
		p[-1] is the same as a[4]
		p[-5] is a[0]
		p[-6] is undefined (just like a[-1])
	

pointer arithmetic

	if i have a pointer p and an integer i

	p + i     is the same as   &p[i]
	*(p + i)  is the same as   p[i]
	
fun fact: addition is commutative, so p + 4 is the same as 4 + p

	p[4] === *(p + 4) === *(4 + p) === 4[p]
	

note that pointer arithmetic depends on the type of the pointer

	the actual displacement in bytes depends on the size of the object
	
	int *p = a;
	
	p + 1
	
Special pointers

	NULL  - a distinct pointer value that does not point to any object
	
		-> cannot be dereferenced
	
		-> considered false (all other pointers are "true")

NULL has a special type: void *

"void pointers" give a location, but have no type information
	pure addresses
	
by default, all we can do with void pointers is compare for equality

by themselves, void pointers are not very useful
    but we can use them to write generic functions
	
memcpy(void *dest, void *src, size_t length);