1 What is the pointer

1.1 Arrays and pointers

If you know the size of the arrays at initialization (i.e. when the program is first run), you can usually get away with the use of fixed size arrays for which C will automatically manage memory for you.
```
#define len 3
int main(){

double xs[len];
for (int i=0; i<len; i++)   xs[i] = 0.0;

double ys[] = {1, 2, 3};
return 0;
}
```

1.2 Pointers and dynamic memory management

Otherwise, we have to manage memory ourselves using pointers. Bascially, memory in C can be auotmatic, static or dynamic.
- Variables in automatic memory are managed by the computer on the stack, when it goes out of scope, the varible disappears.
- Static variables essentially live forever.
- Dynamic memory is allocated in the heap, and its lifetime is managed by users.
Mini-glossary:
- scope: Where a variable is visible - basically C variables have block scope
  - variables either live within a pair of curly braces (inlucdes variables in parentheses just before block such as function arguments and the counter in a for loop),
  - or they are visible thorughout the file.
- stack: Computer memory is divided into a stack (small) and a heap (big).
  - Automatic varianbles are put on the stack;
  - dynamcic variables are put in the heap.
  - Hence if you have a very large array, you would use dynamic memory allocation even if you knwe its size at initialization.
- More details above stack and heap can be found in Memory management in C
Any variable in memory has an address represented as a 64-bit integer in most operating systems.
- A pointer is basically an integer containing the address of a block of memory.
- This is what is returned by functions such as malloc.
- In C, a pointer is dentoed by *.
- However, the * notation is confusing because its interpreation depends on whehter you are using it in a declaraiton or not.
- In a declaration
```
int *p = malloc(sizeof(int)); // p is a pointer to an integer
*p = 5; // *p is an integer
```

To get the actual address value, we can use the & address opertor.

This is often used so that a function can alter the value of an argument passed in (e.g. see address.c below).

#include <stdio.h>
int main(){
int i = 2;
int j = 3;
int *p;
int *q;
*p = i;
q = &j;
printf("p  = %p\n", p);
printf("*p = %d\n", *p);
printf("&p = %p\n", &p);
printf("q  = %p\n", q);
printf("*q = %d\n", *q);
printf("&q = %p\n", &q);
}

1.3 Passing by value and passing by reference

Illustrate the difference by tow examples

#include <stdio.h>
void change_arg(int p) {
p *= 2;
}
int main()
{
int x = 5;
change_arg(x);
printf("%d\n", x);
}

#include <stdio.h>

void change_arg(int *p) {
*p *= 2;
}
int main(){
int x = 5;
change_arg(&x);
printf("%d\n", x);
}

1.4 Pointers to pointers to pointers

Must remember that a pointer is simply a name for an integer that represents an address;
since it is an integer, it also has an address

#include <stdio.h>
int main(int argc, char* argv[]) {
int x = 2;
int *p = &x;
int **q = &p;
int ***r = &q;

printf("%d, %p, %p, %p, %p, %p, %p, %d", x, &x, p, &p, q, &q, r, ***r);
return 0;
}

If we want to store a whole sequence of ints, we can do so by simply allocating more memory

An example

int *ps = malloc(5 * sizeof(int)); // ps is a pointer to an integer
for (int i=0; i<5; i++) {
ps[i] = i;
}

The computer will find enough space in the heap to store 5 consecutive integers in a contiguour way.

Since C arrays are all the same type, this allows us to do pointer arithmetic
i.e. the pointer ps is the same as $&ps[0]$ and ps + 2 is the same as $&ps[2]$.
An example at this point is helpful.

#include <stdio.h>
#include <stdlib.h>

int main(){
int *ps = malloc(5 * sizeof(int));
for (int i =0; i < 5; i++) {
ps[i] = i + 10;
}

printf("%d, %d\n", *ps, ps[0]); // remmeber that *ptr is just a regular variable outside of a declaration, in this case, an int
printf("%d, %d\n", *(ps+2), ps[2]);
printf("%d, %d\n", *(ps+4), *(&ps[4])); // * and & are inverses

free(ps); // avoid memory leak
}

1.4 Pointers and arrays

An array name is actualy just a constant pointer to the address of the beginning of the array.
Hence, we can derferecne an array name just like a pointer. We can also do pointer arithmetic with array names
this leads to the following legal but weird syntax:

arr[i] = *(arr + i) = i[arr]

#include <stdio.h>

int main(){
int arr[] = {1, 2, 3};
printf("%d\t%d\t%d\t%d\t%d\t%d\n", *arr, arr[0], 0[arr], *(arr + 2), arr[2], 2[arr]);
}

1.4 Allocating memory for 2D arrays

An example

#include <stdio.h>
#include <stdlib.h>

int main(){
int r = 3, c = 4;

// first allocate space for the pointers to all rows
int **arr = malloc(r * sizeof(int *));
// then allocate space for the number of columns in each row
for (int i=0; i<r; i++) {
arr[i] = malloc(c * sizeof(int));
}

// fill array with integer values
for (int i = 0; i <  r; i++) {
   for (int j = 0; j < c; j++) {
      arr[i][j] =i*r+j;
   }
}

for (int i = 0; i <  r; i++) {
   for (int j = 0; j < c; j++) {
      printf("%d ", arr[i][j]);
   }
}

// every malloc should have a free to avoid memory leaks
for (int i=0; i<r; i++)  free(arr[i]);
free(arr);
}

1.5 More on pointers

Differnt kinds of nothing:
- There is a special null pointer indicated by the keyword NULL that points to nothing.
- It is typically used for pointer comparisons, since NULL pointers are guaranteed to compare as not equal to any other pointer (including another NULL).
- In paticular, it is often used as a sentinel value to mark the end of a list.
- In contrast a void pointer (void * ) points to a memory location whose type is not decalred.
- It is used in C for generic operations - for example, malloc returns a void pointer.
- To totally confuse the beginning C student, there is also the NUL keyword, which refers to the ‘\0’ character used to terminate C strings.
- NUL and NULL are totally different beasts.

Deciphering pointer idioms: A common C idiom that you should get used to is *q++ = *p++ where p and q are both pointers. In English, this says

*q = *p (copy the variable pointed to by p into the variable pointed to by q)
- increment q
- increment p
An example

#include <stdio.h>
#include <stdlib.h>

int main(){
// example 1
typedef char* string;
char *s[] = {"mary ", "had ", "a ", "little ", "lamb", NULL};
for (char **sp = s; *sp != NULL; sp++) {
printf("%s", *sp);
}
printf("\n");

// example 2
char *src = "abcde";
char *dest = malloc(5); 

char *p = src + 4;
char *q = dest;
while ((*q++ = *p--)); 

for (int i = 0; i < 5; i++)
   printf("i = %d, src[i] = %c, dest[i] = %c\n", i, src[i], dest[i]);

}

1.5 Function pointers

How to make a nice function pointer:
- Start with a regular function declaration func,
- for example, here func is a function that takes a pair of ints and returns an int
```
int func(int, int);
```
To turn it to a function pointer, just add a * and wrap the funtion name in parenthesis like so

int (*func)(int, int);

Now func is a pointer to a funciton that takes a pair of ints and returns an int. Finally, add a typedef so that we can use func as a new type

typedef int (*func)(int, int);

which allows us to create arrays of function pointers, higher order functions etc as shown in the following example.

#include <stdio.h>
#include <math.h>

// Create a function pointer type that takes a double and returns a double
typedef double (*func)(double x);

// A higher order function that takes just such a function pointer
double apply(func f, double x)
{
return f(x);
}

double square(double x)
{
return x * x;
}

double cube(double x)
{
return pow(x, 3);
}

int main(){
double a = 3;
func fs[] = {square, cube, NULL};

for (func *f=fs; *f; f++) {
printf("%.1f\n", apply(*f, a));
}
}

2 Examples

2.1 Pointer version of Pell’s equation

The previous version by using arry can be found in recursion

2.1.1 Iterate by using while

C codes

//run on VS 2010
#include <stdio.h>

void pf2_pointer_arry(int *a1, int *b1, int *Lab, int N){
    int i,La,ta,tb,ta1,tb1,*a,*b,n=1;
    a1[0]=3;
    b1[0]=2;
    Lab[0]=Lab[1]=1;
    
    while(n<N){
        ta=tb=0;
        a=a1;
        b=b1;   
        La=Lab[0];
        for(i=0;i<La;i++){
            ta1=(*a)*3+(*b)*4+ta;   
            tb1=(*a)*2+(*b)*3+tb;
            *a=ta1%10;  
            *b=tb1%10;  
            ta=ta1/10;  
            tb=tb1/10;  
            a++;
            b++;
        }
        Lab[0]=La;
        Lab[1]=La;
        if(ta){
          *a+=ta;
          Lab[0]++;
          }
        if(tb){
          *b+=tb;
          Lab[1]++;
          }
        n++;
    }       
}


int main(int argc,char* arg[]){
    int i;
    
    int a[100], b[100], Lab[2];
    for (i = 0; i < 100; i++) a[i]=b[i]=0;
    
    pf2(a,b,Lab,50);
    
    printf("p=");
    for(i=Lab[0]-1;i>=0;i--)
      printf("%d",a[i]);
    printf("   q=");
    for(i=Lab[1]-1;i>=0;i--)
      printf("%d",b[i]);
    printf("\n");

    getchar();
    return 0;
}

2.1.2 Iterate by using recursion

#include <stdio.h>

void pf2(int *a1, int *b1, int *Lab, int N){
    int i,La,ta,tb,ta1,tb1,*a,*b;
    if(N<=1) {
        a1[0]=3;
        b1[0]=2;
        Lab[0]=Lab[1]=1;
    }
    else{
        pf2(a1, b1, Lab, N-1);
        ta=tb=0;
        a=a1;
        b=b1;   
        La=Lab[0];
        for(i=0;i<La;i++){
            ta1=(*a)*3+(*b)*4+ta;   
            tb1=(*a)*2+(*b)*3+tb;
            *a=ta1%10;
            *b=tb1%10;  
            ta=ta1/10;
            tb=tb1/10;  
            a++;
            b++;
        }
        Lab[0]=La;Lab[1]=La;
        if(ta){
          *a+=ta;
          Lab[0]++;
          }
        if(tb){
          *b+=tb;
          Lab[1]++;
          }
    }       
}

int main(int argc,char* arg[]){
    int i;
    
    int a[100], b[100], Lab[2];
    for (i = 0; i < 100; i++) a[i]=b[i]=0;
    
    pf2(a,b,Lab,50);
    
    printf("p=");
    for(i=Lab[0]-1;i>=0;i--)
      printf("%d",a[i]);
    printf("   q=");
    for(i=Lab[1]-1;i>=0;i--)
      printf("%d",b[i]);printf("\n");

    getchar();
    return 0;
}

2.2 Pointer version of Matrix Product

The previous version by using arry can be found in matrixproduct
C codes

#include <stdio.h>

void MatrixByMatrix(double *outVector, double *A, double *v, int n, int p, int q)
{
    int i, j, k;
    double s, *pa,*pv;
    for (i = 0; i<n; i++){
        for (k = 0; k<q; k++){
            s = 0; 
            pa=A+i*p; 
            pv=v+k*p;
            for (j = 0; j < p; j++) 
              s += (*pa++) * (*pv++);
            outVector[i*n + k] = s;
        }
    }
}

int main(int argc,char* argv[]){
  int i, j;
    double b[100], c[100], out[16];
    srand(1);
    for (i = 0; i < 100; i++)   
      b[i] = (rand() % 100) / 100.0;
    srand(1000);
    for (i = 0; i < 100; i++)   
      c[i] = (rand() % 100) / 100.0;

    MatrixByMatrix(out, b, c, 4, 25, 4);
    printf("Matrix out:\n");
    for (i = 0; i<4; i++){
        for (j = 0; j<4; j++)   
          printf("%lf ", out[i*4+j);
        printf("\n");
    }

    fflush(stdin);
    getchar();
    return 0;
}

3 compile C programs by Make

Details of this part can be found http://people.duke.edu/~ccc14/sta-663/CrashCourseInC.html
The processs of C program compilation can be quite messy, with all sorts of different compiler and linker flags to specify, libraries to add and so on.
For this reason, most C programs are compiled using the make build tool that you are already familiar with.
Here is a simple generic makefile that you can customize to compile your own programs adapted from the book 21st Centur C by Ben Kelmens (O’Reilly Media).
- TARGET: Typically the name of the execuatble
- OBJECTS: The intemediate object files - typically there is one file.o for every file.c
- CFLAGS: Compiler flags, e.g. -Wall (show all warnings), -g (add debug information), -O3 (use level 3 optimization). Also used to indicate paths to headers in non-standard locations, e.g. -I/opt/include
- LDFLAGS: Linker flags, e.g. -lm (link agains the libmath library). Alos used to indicate pahts to libaries in non-standard locations, e.g. -L/opt/lib
- CC: Compiler, e.g. gcc or clang or icc
In addition, there are traiditonal dummy flags
- all: Builds all targets (for example, you may also have html and pdf targets that are optional)
- clean: Remove intermediate and final products generated by the makefile
```
TARGET =
OBJECTS =
CFLAGS = -g -Wall -O3
LDLIBS =
CC = c99

all: TARGET

clean:
rm $(TARGET) $(OBJECTS)

$(TARGET): $(OBJECTS)
```

Just fill in the blanks with whatever is appropriate for your program.

Here is a simple example where the main file test_main.c uses a function from stuff.c with declarations in stuff.h and also depends on the libm C math library.

%%file stuff.h
#include <stdio.h>
#include <math.h>

void do_stuff();

%%file stuff.c
#include "stuff.h"

void do_stuff() {
printf("The square root of 2 is %.2f\n", sqrt(2));
}

%%file test_make.c
#include "stuff.h"

int main(){
do_stuff();
}

%%file makefile
TARGET = test_make
OBJECTS = stuff.o
CFLAGS = -g -Wall -O3
LDLIBS = -lm
CC = clang

all: $(TARGET)

clean:
rm $(TARGET) $(OBJECTS)

$(TARGET): $(OBJECTS)

! make

! ./test_make

# Make is clever enough to recompile only what has been changed since the last time it was called
! make

! make clean

! make

Try to fix the following buggy program

%%file buggy.c

# Create a function pointer type that takes a double and returns a double
double *func(double x);

# A higher order function that takes just such a function pointer
double apply(func f, double x){
return f(x);
}

double square(double x){
return x * x;
}

double cube(double x){
return pow(3, x);
}

double mystery(double x){
double y = 10;
if (x < 10)
x = square(x);
else
x += y;
x = cube(x);
return x;
}

int main(){
double a = 3;
func fs[] = {square, cube, mystery, NULL}

for (func *f=fs, f != NULL, f++) {
printf("%d\n", apply(f, a));
}
}

! clang -g -Wall buggy.c -o buggy

What other language has an annual Obfuscated Code Contest http://www.ioccc.org/?
In particular, the following features of C are very conducive to writing unreadable code:
- lax rules for identifiers (e.g. _o, _0, _O, O are all valide identifiers)
- chars are bytes and pointers are integers
- pointer arithmetic means that array[index] is the same as *(array+index) whihc is the same as index[array]!
- lax formatting rules especially with respect to whitespace (or lack of it)
- Use of the comma operator to combine multiple expressions together with the ?: operator -Recursive function calls - e.g. main calling main repeatedly is legal C
Here is one winning entry from the 2013 IOCCC entry that should warm the heart of statisticians - it displays sparklines (invented by Tufte).

main(a,b)char**b;{int c=1,d=c,e=a-d;for(;e;e--)_(e)<_(c)?c=e:_(e)>_(d)?d=e:7;
while(++e<a)printf("\xe2\x96%c",129+(**b=8*(_(e)-_(c))/(_(d)-_(c))));}

%%file sparkl.c
main(a,b)char**b;{int c=1,d=c,e=a-d;for(;e;e--)_(e)<_(c)?c=e:_(e)>_(d)?d=e:7;
while(++e<a)printf("\xe2\x96%c",129+(**b=8*(_(e)-_(c))/(_(d)-_(c))));}

! gcc -Wno-implicit-int -include stdio.h -include stdlib.h -D'_(x)=strtof(b[x],0)' sparkl.c -o sparkl

import numpy as np
np.set_printoptions(linewidth=np.infty)
print ' '.join(map(str, (100*np.sin(np.linspace(0, 8*np.pi, 30))).astype('int')))

%%bash

./sparkl 0 76 98 51 -31 -92 -88 -21 60 99 68 -10 -82 -96 -41 41 96 82 10 -68 -99 -60 21 88 92 31 -51 -98 -76 0

If you have too much time on your hands and really want to know how not to write C code (unless you are crafting an entry for the IOCCC), I recommend this tutorial http://www.dreamincode.net/forums/topic/38102-obfuscated-code-a-simple-introduction/

4 References

Bronson, G. J., (2006). “A First Book of ANSI C”, 4nd, McGraw-Hill, Inc.
Kernighan, B. W. and Ritchie, D., (1988). “C Programming Language”, 2nd, Prentice Hall.
Cheng, H. H., (1996). “C for Engineers and Scientists :An interpretive approach”, Pearson.
Bryant, R. E. and O’Hallaron D, R., (2003). “Computer systems: a programmer’s perspective”, 3nd, Prentice Hall Upper Saddle River
Computational Statistics in Python

Pointers

Xu Liu