CS 214 / More pointers
======================

// Puzzle: Can you explain whether/how the function below works?

int
mystery_function (char *p)
{
    int i = 0;
    while (*p++) i++;
    return i;
}


NULL and void *
---------------

We often talk about null pointers and void pointers
these are easy to confuse - both are pointers you can't dereference

these are actually not the same sort of thing
    type vs value
    
in general, whether a pointer is null is a run-time question
    -> we can make promises or requirements that a pointer will be non-null,
        but the compiler can't/won't enforce these

whether a pointer is void is only known at compile time
    -> at run-time, nothing is typed and all pointers can be dereferenced
    -> technically, expressions can have type void *
        there are no "void pointers"

dynamic allocation
------------------

manually allocate and deallocate objects on the heap

heap: a region of memory managed by the run-time system
    run-time keeps track of which parts of the heap are allocated
    
    unrelated to the priority queue data structure also called "heaps"


interface:

    void * malloc(size_t length);
    
        attempts to allocate the requested number of bytes
        
        returns a pointer to the newly allocated object on success
        returns NULL on failure
    
    void free(void *object);
    
        given a pointer to an object allocated by malloc(), deallocates
            the object
        
        it is an error to call free() with a pointer not previously
            returned by malloc() or already freed

int *p = malloc(20 * sizeof(int));
int *q = p;

free(q);  // this is fine: the pointer needs to be the same, not the variable
free(p);  // double-free error

in general, every call to malloc() should lead to a call to free() eventually

do not:
    call free with a pointer not obtained from malloc
    call free with a pointer to the middle of an object
    call free more than once with a given pointer

compile with -fsanitize=address to detect these errors at run-time


consider:

    int *p = malloc(20 * sizeof(int));
    double *q = malloc(25 * sizeof(double));
    
how can malloc return both int* and double* ?
    it can't!
    it returns an untyped pointer (void *), and we have to indicate its
        type ourselves
        
    void *r = malloc(100);
        // okay, but not actually useful
        // all we can do with void pointers is compare for equality
        // to deference, we need a type

the compiler will automatically promote void * to other pointer types
as needed

    p = r;
    q = r;  // both okay, but suspicious to do both

you will often see code like this

    int *p = (int *) malloc(some_dimension * sizeof(int));
        // explicitly cast pointer to desired type
        // personally, I think specifying the type 3 times is redundant
        
    q = (int *) malloc(some_other_dimension * sizeof(int));
        // the cast is useful here, because the compiler will catch
        // the type error (q is double *)


note the use of sizeof()
    operator that the compiler will replace with the number of chars needed
    to store that type
    
    sizeof(int)
    sizeof(double)
    sizeof(int *)
    
we can also use sizeof() with variables or expressions

    int a[20];
    int *b = malloc(100 * sizeof(int));
    
    sizeof(a) == 20 * sizeof(int)
    sizeof(b) == sizeof(int *)
    
    sizeof(*a) == sizeof(int)
    sizeof(*b) == sizeof(int)
    
    
    sizeof(a) / sizeof(a[0]) == 20

two variants of malloc()

    void * calloc(size_t elem_length, size_t num_elems);
        calls malloc() and then sets all the bytes to 0
    
    
    void * realloc(void *object, size_t length);
        "changes" the size of an object
        - might shrink/expand object in-place
        - might allocate a new object, copy the data, and free the 
            original object

    because realloc() may move your object, you must assume that it did
    
    typical use
    int size = ...
    int *p = malloc(sizeof(int) * size);
    ...
    
    size *= 2;
    p = realloc(p, sizeof(int) * size);
        // this is a little risky, because realloc() returns NULL and does
        // not free the object if it can't find space
        
    // safer
    size *= 2;
    int *q = realloc(p, sizeof(int) * size);
    if (!q) { return error_code; }
    p = q;


function pointers
-----------------

recall: function code exists in memory
    -> functions are objects with addresses

a function name by itself is an expression that evaluates to a pointer to
    that function
    
function pointers allow us to refer to functions indirectly

to store a function pointer, we need to express its type
    -> number and type of parameters and return type

    example: fp points to a function that takes 1 int and returns int
    
    int (*fp)(int);
    
    void (*fp2)(int, int);
    
    int foo(int x) { return x + 1; }
    
    fp = foo;

    int n = fp(4);

void (*tests[])(void) = { test1, test2, test3 };

void run_test(int n)
{
    tests[n]();
}


void 
qsort(
    void *array,                        // array to be sorted
    size_t array_length,                // number of elements
    size_t elem_length,                 // size of elements
    int (*compare)(void *, void *)      // comparison function
);

int
compare_ints (void *a, void *b)
{
    int *x = a;
    int *y = b;
    return *x - *y;
}


int a[20] = { ... };
qsort(a, 20, sizeof(int), compare_ints);



void
bubble_sort(void *a, size_t nelems, size_t elem_len,
        int (*compare)(void *, void *))
{
    void *t = malloc(elem_len);
    
    for (int i = 0; i < nelems; i++) {
        for (int j = 1, j < nelems; j++) {
            void *p = (char *) a + elem_len * (j - 1);
            void *q = (char *) a + elem_len * j;
            
            if (compare(p, q) > 0) {
                // swap

                memcpy(t, p, elem_len);
                memcpy(p, q, elem_len);
                memcpy(q, t, elem_len);
            }
        }
    }
    
    free(t);
}