exam format

  • NO CODING ON THE EXAMS
  • SOME fill in the blank/multi choice
  • lots of short answer
    • a few sentences at most
    • “name/define”
    • “contrast/compare”
  • “procedures”
    • doing algorithms on paper, ish
  • tracing, definitely
    • showing the output of good code
    • diagnosing problems with bad
  • IDEAS, NOT DETAILS.
  • EVERYBODY ALWAYS GETS “DEREFERENCE” WRONG
    • NOT: “losing the reference”
    • NOT: “freeing the memory”

why do we use malloc?

  • the stack is LINEAR
    • representing non-linear data structures is impossible on the stack
  • the stack is only maybe 8-10 MB???
    • for variables and small arrays? OK
    • for big arrays, big objects, big data structs…
    • GOTTA use the heap.
  • the lifetimes of stack variables are tied to the functions that they are declared in
    • heap memory has a CUSTOM lifetime

how does heap work???????

  • allocator KEEPS TRACK of used/free heap space
    • bitmap
      • use bits to keep track of used/free of uniformly-sized heap chunks
    • linked list
      • use linked list of exactly-sized heap blocks; each block has a header
  • when you malloc, allocator finds free space
    • first fit
      • start @ beginning, first that fits.
    • next fit
      • start @ most-recent allocation, first that fits.
    • worst fit
      • biggest (worst-fitting) block
    • best fit
      • smallest (best-fitting) block
    • quick fit
      • categorize blocks by size
      • multiple lists/sets of blocks.
    • pooling
      • preallocate space (but requires foreknowledge)
  • when you free, allocator turns used space into free space
  • malloc can recycle previously-used space.

pointersssssssssssssssss

  • a T* is a pointer to a T.
    • int* p
      • p holds an address
      • that address is the address of an int
  • to get the address of any T, we use & (“address-of”)
    • (And, Address, Add a star)
    • int var = 0xDEADBEEF; p = &var;
  • to get the VALUE that a pointer points to…
    • *p = 20; - dereference operator (“value-at”)
    • s->field = 20; - arrow (struct field)
    • a[10] = 20; - [indexing]
    • ALL of these can:
      • SEGFAULT
      • CAUSE UB
  • pointer casting changes how we LOOK at a sequence of bytes.
    • char* c = (char*)p;
    • c is the same address as p…
    • but when we access c, we’ll be looking at it as if it were an array of bytes
      • c[0] == 0xEF
  • void* is a pointer with no “meaning”
    • it’s an address…
    • but it can point to anything

constants in C

  • #define X 10
    • TEXTUAL replacement of X with 10, everywhere
  • enum { X = 10 };
    • makes a constant VALUE, but not a variable
    • MUST be int!
  • const int X = 10;
    • makes a VARIABLE (has an ADDRESS)

include guards

#ifndef _SOMETHING_H_
#define _SOMETHING_H_
// this crap ^^^ vvv prevents this header file
// from being doubly- (or triply-, etc) included
#endif

scope & lifetime

  • scope: “where a name can be seen”
    • “lexical” feature
    • part of the language rules to keep us sane
  • lifetime: “the time between allocation & deallocation of a piece of memory”
    • for local and global variables, lifetime == scope
    • BUT
    • for heap memory, there is no scope, only lifetime, and the lifetime is NONLOCAL
      • it can OUTLAST the function it was allocated in.

what pointers good for?????

  • ARRAYS
    • “arrays” in C are just pointers.
    • a[i] == *(a + i)
  • passing “by reference”
    • S some_struct = { 1, 2 };
    • some_func(&some_struct)
    • “giving away access to your stuff”
    • sometimes just better performance.
  • HEAP MEMORY!
    • can only access heap through pointers (indirectly)
void func(int* p) {
	p[0] = 20;
}

int main() {
	// giving a pointer to another function gives that
	// function *access* to your variables
	int arr[2] = { 5, 10 };
	func(arr);
	printf("%d\n", arr[0]); // prints 20.

	// single pointer: array of something
	const char* s = "hello!";

	// double pointer array of arrays of something
	// (yeah ok it isn't written char** but that's cause of
	// how this array is declared)
	const char* strings[] = {
		"hi",
		"byeeeeeeeeeeee"
	};

	print("%p\n", strings[0]); // prints ADDRESS of "hi"
	print("%c\n", strings[0][1]); // prints 'i'

}