Pointers and Arrays

Pointers

A pointer is an expression that contains an object’s address in memory and a scale factor equal to `sizeof(`object`)`.

The expression `sizeof(`object`)` returns an integer equal to the number of bytes spanned by object, including internal slack bytes, plus the number of trailing slack bytes reserved to force alignment of a potential consecutive object of the same type.

An lvalue is an expression that refers to an object, and therefore, it may occupy the left side of an assignment statement in order to modify the object’s value.

The `&` operator is called the address operator.  The expression `&b` returns a pointer to type of `b`, where `b` is an lvalue.  The resulting pointer is never an lvalue, as the address of an object cannot be changed.

The `*` operator is called the indirection or the dereferencing operator.  When pointer variable `pb` contains the value `&b`, the expression `*pb` provides indirect access to `b` through the reference in `pb`.

The operators `*` and `&` cancel each other.  The expression `*&b` returns an object of the type and value of `b`.

```    int b = 3;                                      /* b == 3   */
int *pb;                                        /* pointer to int: pb   */

*&b = 4;                                        /* b == 4   */

pb = &b;
*pb = 5;                                        /* b == 5   */
```

Pointer Arithmetic

In addition or subtraction of an integer to a pointer, the integer is first multiplied by the pointer’s scale factor, the size of the dereferenced pointer.

For pointer `ptr` and integer `i`, the expression `ptr + i` or `ptr - i` returns a pointer to type of `*ptr`, containing the value in `ptr` incremented or decremented by an amount equal to the value of `i` multiplied by `sizeof(*ptr)`.  The prefix and postfix increment operators may be applied to a pointer with similar result.

There is no direct means of adjusting a pointer’s value by an arbitrary amount.  Only multiples of the size of the dereferenced pointer may be added or subtracted.

An array is a block of consecutive elements in memory.  The elements are objects of the same type that are assigned sequential index numbers beginning with 0.

The `[]` operator is called the array operator.  The expression `a[i]` returns the element of array `a` with index number `i`.  Since an integer is scaled before it is added to a pointer’s value:

```    &a[i] + j == &a[i+j]    in general

&a + i == &a[i]      in particular
```

An array name alone, such as `a`, returns a `const` pointer to the first element.  This implies that the array operator is a dereferencing operator:

```    a == &a,  a + i == &a + i == &a[i]

a == *a,  a[i] == *(a + i)
```

Note that the expression `&a` returns a pointer to array `a` with scale factor of `sizeof(`the entire array`)`.

The application of the indirection and array operators to either an array name or a pointer variable is equivalent.  For pointer variable `ptr`, the expression `ptr[i]` returns the object of the type of `*ptr` located at address returned by `ptr + i`.  In general:

```    ptr == *ptr,  ptr[i] == *(ptr + i)
```

The expression `a[i]` is compiled as `*(a + i)`.  The expression `*(ptr + i)` is compiled as such, but may be coded `ptr[i]`.

An expression consisting of the subtraction of 2 pointers to elements of the same array returns an integer equal to the difference of the subscript numbers of the elements.

C guarantees that an expression that returns a pointer to the memory location just beyond the last element of an array is a valid term in a comparison expression, even though the pointer itself may not be dereferenced since it references an undefined area.

Note that `[]` has higher precedence than the operators: `++`, `--`, `*`, and `&` which have equal precedence and associate right-to-left.

```    char a, *pa, *pa1 = &a, *pa2 = &a;
long b, *pb;
int diff, n = 2;

/* Subtract pointers to the same array                               */

diff = &a - a;                                   /* diff == 10   */
diff = pa1 - a;                                      /* diff == 6    */
diff = &a - &a;                                /* diff == 2    */
diff = pa1 - pa2;                                    /* diff == 2    */
diff = pa1 + n - pa2 + 1;                            /* diff == 5    */
/*   ((ptr + int) - ptr) + int == (ptr - ptr) + int                  */
/*                             == int + int == int                   */

/* Set pointer value                                                 */

pa = a;                                              /* pa == &a  */
pa = a + 3;                                          /* pa == &a  */
--pa;                                                /* pa == &a  */
pa += 7;                                             /* pa == &a  */
pa = &a - 2;                                      /* pa == &a  */
pa = pa1 - 2;                                        /* pa == &a  */
pa = pa1 - n;                                        /* pa == &a  */

/* Synchronize pb to pa by element number                            */

pb = b + (pa - a);                                   /* pb == &b  */
*pb = 6;                                             /* b == 6    */

/* Combine dereferencing and increment operators                     */

*++pb = 7;                                           /* b == 7    */
++*pb;                                               /* b == 8    */
(*pb)++;                                             /* b == 9    */
*pb++ = 10;                                          /* b == 10   */

*pb = 11;                                            /* b == 11   */
```

To traverse an array, it is more efficient to use a dereferenced pointer than a subscript for referencing the elements.  The first `for` statement below uses a subscript to initialize all elements of array `a`.  The second `for` statement represents the way the compiler processes the first.

The second `for` statement requires three operations to address each element of `a`.  The expression `i++` increments `i` by 1, and the expression `a + i` multiplies `i` by `sizeof(int)`, and then adds the product to `&a`.

The third `for` statement requires just one operation to address each element of `a`.  The expression `ptr++` increases the value in `ptr` by `sizeof(*ptr)`, in this case `sizeof(int)`.  This saves one addition and one multiplication.

```    int i, a, *ptr, *end = &a;

for (i=0; i<10; i++)
a[i] = 0;

for (i=0; i<10; i++)
*(a + i) = 0;

for (ptr = a; ptr < end; ptr++)
*ptr = 0;
```

Multi-dimensional Arrays

C has no true multi-dimensional arrays.  Instead, C permits elements of an array to be defined as arrays themselves.  A compound array of nested one-dimensional arrays simulates a multi-dimensional array.

The array `int a` is defined as array of array of array of `int`.  The array operator `[]` associates left to right.

Threfore, `a` is an array of 2 elements `a[i]` which are arrays of 3 elements `a[i][j]` which are arrays of 4 elements `a[i][j][k]` which are integers.

C stores the elements of an array in row major order, meaning that all columns in the same row are placed beside each other in memory.  To traverse all elements of an array of multiple subscripts in order of memory address, the rightmost subscript must vary through its entire range once for each time that the next-rightmost subscript changes value, etc.

A compound array of arbitrary dimensions such as `type a[rows][cols][dim3]` is so arranged in memory that the address of an arbitrary element may be expressed as:

```    &a[i][j][k] == &a + sizeof(type) x ((((i x cols) + j) x dim3) + k)
```

The internal displacement of element `a` is:

```    `sizeof(int)` x ((((1 x 3) + 2) x 4) + 1) = 21 x `sizeof(int)`
```

The elements of `a` are arranged in memory as shown below.

`*`
 `a` `a` `a`
 `a` `a` `a`
`a``a`

Array `a` can be expressed in terms of pointers rather than subscripts, since the expressions `a`, `a[i]`, and `a[i][j]` are array names that return pointers.

```    &a                       pointer to array of array of array of int
a       == &a         pointer to array of array of int
a[i]    == &a[i]      pointer to array of int
a[i][j] == &a[i][j]   pointer to int

a[i] == *(&a + i) == *(a + i)

a[i][j] == *(&a[i] + j) == *(a[i] + j)
== *(*(a + i) + j)

a[i][j][k] == *(&a[i][j] + k) == *(a[i][j] + k)
== *(*(*(a + i) + j) + k)
```

The last relation is derived in a direct, though less conceptual manner, by successive application of the array operator `[]` which associates left to right:

```    a[i][j][k] == ((a[i])[j])[k]
== ((*(a + i))[j])[k]
== (*(*(a + i) + j))[k]
== *(*(*(a + i) + j) + k)
```

Finally, note that the expressions `&a`, `a`, `a`, `a`, and `&a`, all return pointers containing the address of the first `int` in the compound array, but the scale factor of each pointer is different.

Casts and Pointers

An explicit cast is required to assign or compare a pointer of one type to a pointer of another type.  The cast adjusts the scale of the pointer expression.  For the above example the following is true:

```    (int*)&a == (int*)a == (int*)a == a == &a
```

Note that the cast is not needed in the rightmost terms.

By use of a cast, data in memory of one type can be corrupted by overlaid data of another type.

```    int i = 513;                /* i == 0x00000201                       */
/* since Intel memory is little-endian:  */
/* byte 0 == 0x01, byte 1 == 0x02        */

*((char*)&i + 1) = 'a';     /* overlay byte 1 of i with 0x61         */
/* i == 0x00006101 == 24833              */

i = 513;                   /* same as above                         */
((char*)&i) = 'a';      /* parens are needed since [] has        */
/* higher precedence than & or cast      */
```

Array of Pointers

The declaration `char *a` defines an array of pointers to `char`.  If the first pointer `a` holds the address of `char c`, then the array name `a` is a pointer to the first pointer to `char`.

```    char *a;              /* array of 5 pointers to char              */
char c = 'b';

a = &c;               /* 3rd element holds pointer to variable c  */
```

Array Literals

An array literal is used to initialize an array.  Elements are initilized in the order specified in the literal.  If the literal contains fewer entries than the array’s dimension, the final elements will remain uninitialized.

A string literal is compiled as an array of `char` with an extra final element equal to `'\0'`.  A string literal, as well as an array literal of `char`, may be the initializer of an array of `char`.  However, a string literal is the only literal that may be the initializer of a pointer to `char`.

In the declaration of an array with an initializer, the first dimension is implied and it may be omitted by coding empty brackets `[]`.  This does not apply to higher dimensions.

```    int a = {0, 1, 2, 3};

int aa = { {00, 01, 02, 03}, {10, 11, 12, 13}, {20, 21, 22, 23} };

int aaa = {
{ {000, 001, 002, 003}, {010, 011, 012, 013}, {020, 021, 022, 023} },
{ {100, 101, 102, 103}, {110, 111, 112, 113}, {120, 121, 122, 123} }
};

int b = {1, 2};                 /* Last 2 elements uninitialized  */

char ca = "string";             /* Implied final \0               */

char *pc = "string";

/* char *pc = {'s', 't', 'r', 'i ', 'n', 'g', '\0'};                    */
/*                                                                      */
/* Note: This doesn't work.  Only a true string literal does.           */

/* Array of pointers to strings                                         */
char *apc = {"snap", "crackle", "pop"};

/* Implied first dimension                                              */
char aD1[] = "arr1";
char aD2[] = {"arr1", "arr2", "arr3"};
char aD3[] = { {"arr1", "arr2", "arr3"}, {"arr4", "arr5", "arr6"} };
```

Pointer to Pointer

The declaration `char **ppc` defines a single variable `ppc` that is a pointer to pointer to `char`.  The object that `ppc` points to, `*ppc`, is a pointer to `char`.  The object that `*ppc` points to, `*(*ppc)` or `**ppc`, is a `char`.

Access to memory through a single pointer is called a single level of indirection or single indirection.  Access to memory through multiple pointers is called multiple levels of indirection or multiple indirection.  Multiple levels of pointers to pointers form a pointer chain that ends in an object variable.  The fully dereferenced value of any pointer in the chain references the object at the end.

```    char c = 'a';             /* char                                    */
char *pc = &c;            /* pointer to char                         */
/* *pc == c the object pc points to        */
char **ppc = &pc;         /* pointer to pointer to char              */
/* *ppc == pc the object ppc points to     */
/* **ppc == *pc == c                       */
/* char **ppc = &&c                                                     */
/*                                                                      */
/* Note: This doesn't work.  The & operator applies only to an lvalue.  */
/*       &&c == &(&c) and &c is not an lvalue.                          */

char c2 = 'b';            /* another char                            */
char *pc2 = &c2;          /* another pointer to char                 */

ppc = &pc2;               /* *ppc == pc2 the object ppc points to    */
*ppc = pc;                /* *ppc == pc2 = pc                        */
**ppc = c2;               /* **ppc == *pc2 == *pc == c = c2          */
```

Such a pointer is often used for traversing an array of pointers and referencing the objects that they address, which are usually strings of varying length.

```    char c, **ppc, *ap = {"alpha", "bravo", "charlie"};

ppc = ap;                 /* ppc = &ap                            */

c = **ppc;                /* c == 'a'                                */
c = *ppc;              /*   All reference the 1st char            */
c = ppc;            /*   of the 1st string                     */

c = *(*(ppc + 2) + 1);    /* c == 'h'                                */
c = *(ppc + 1);        /*   All reference the 2nd char            */
c = (*(ppc + 2));      /*   of the 3rd string                     */
c = ppc;            /*                                         */

c = ap;                                           /* c == 'a'  */
c = **ppc;                                              /* c == 'a'  */

c = ap;                                           /* c == 'b'  */
c = (*++ppc);                                        /* c == 'b'  */
ppc--;          /* Decrement ppc  */
c = *(++ppc);                                        /* c == 'b'  */

c = ap;                                           /* c == 'c'  */
c = **++ppc;                                            /* c == 'c'  */

c = ap;                                           /* c == 'h'  */
c = *++*ppc;    /* This alters the value of ap */    /* c == 'h'  */
--*ppc;         /* Restore ap  */
c = *++ppc;  /* This alters the value of ap */    /* c == 'h'  */
```

Pointer to Array

The declaration `char (*pa)` defines a single variable `pa` that is a pointer to array of 5 `char`.  The object that `pa` points to, `*pa`, is an array of 5 `char` whose third element is `(*pa)`.  Pointer `pa` is scaled by `sizeof(`array of 5 `char)`.

```    char (*pa);         /* pointer to array of char                */

char a;             /* array of char                           */

char aaa;     /* array of array of array of char   */
/* 12 consecutive array of char in memory  */

pa = &a;               /* pa = pointer to entire array a             */

a = 't';            /* change 2nd char in a to 't'                */
(*pa) = 'p';        /* change the same char to 'p'                */

pa = aaa;           /* pa = &aaa  assign pointer to         */
/* 9th consecutive array of char in memory */

aaa = 't';    /* change 2nd char in 9th array to 't'     */
(*pa) = 'p';        /* change the same char to 'p'                */

/* Change 2nd char in 5th thru 8th consecutive array to 'Z'           */

for (pa = aaa; pa < &aaa; pa++)
(*pa) = 'Z';
```

Here is a comprehensive example:

```    char **ppc;
/* Array of pointers to strings of unequal length */
char *apc = { "hello, " };                  /* Initialize apc  */
char *pc = "world\n";

char aD1f = "charlie\n";                      /* Implied final \0 */
char aD1s = {'b', 'i', 'n', 'g', ' ', '\0'};
char aD2 = { "bang ", {'b', 'o', 'o', 'm', '\n', '\0'} };
char aD3 = {
{ {' ', 'e', 'n', 'd'}, {' ', 'o',   'f', ' '} },
{ {'s', 't', 'o', 'r'}, {'y', '\n', '\0', ' '} }
};

apc = pc;                           /* Print:                     */
apc = "goodbye, ";                  /*   hello, world             */
apc = aD1f;                         /*   goodbye, charlie         */
apc = aD1s;                         /*   bing bang boom           */
apc = aD2;                       /*   end of story             */

apc = aD3 + 1;                /* apc == &aD3    */

ppc = apc;                             /* Use the char** in loop     */

while (ppc < &apc)
printf("%s", *ppc++);              /* Dereference ppc only once  */
/* to get char* for printf    */
```

Generic Pointer

A pointer is preserved unchanged when first, it is assigned to another pointer to an object type whose storage alignment requirements are less or equally strict, and then, assigned back from there.  Storage alignment is implemention-dependent, but the type `char` has the least strict requirement for alignment.  Under pre-ANSI C, the pointer to `char` was used for the generic pointer in type conversions.

ANSI C introduced the pointer to `void` which requires no explicit cast for assignment or comparison to any other pointer, which occur with no loss of information.  Neither dereferencing nor pointer arithmetic applies to a pointer to `void`, as it has no scale.  When a function defined with a parameter that is a pointer to any type is called with a corresponding argument that is a pointer to `void`, the type conversion is performed as in an assignment.

Continuing the above example:

```    void *pv;
void printout(char*);

apc = (char *) aD3;                 /* apc == &aD3    */
printf("%s", ++apc);                /* Print: end of story        */

pv = apc;                           /* Assign char* to void*      */
apc = pv;                           /* and back                   */
apc = '\n';
apc = '\0';
printf("%s", apc);                  /* Print: goodbye             */

pv = "so long\n";                      /* Assign char* to void*      */
printout(pv);                          /* Print: so long             */

void printout(char *a) { printf("%s", a); }
```

Null Pointer

For each pointer type, a single value that is distinct from all valid values is designated the null pointer.  The internal representation of the null pointer may differ by pointer type, but the null pointer of one type converts upon casting to the null pointer of any other type.  The null pointer evaluates to zero in a boolean expression.

The null pointer constant is an integral constant expression with value zero.  It assumes the value of the null pointer in expressions of initialization, assignment, or comparison involving a pointer of any type.  In order to use it for a function argument, it must be cast to the pointer type of the parameter, or to `void *`.  This is necessary to distinguish it as a pointer rather than the constant `0`.

The macro `NULL` is used by convention for the null pointer constant.
`<stio.h> ` defines `NULL` as `0`.
`<stddef.h>` defines `NULL` as `(void *) 0`.

```    #include <stddef.h>

int  i = 1,   *pi = 0;
char c = 'a', *pc = (char *) pi;      /* Converts null pointer const */

if (pi == NULL && pc == 0)            /* Compares equal to NP const  */
pi = &i;                          /* This is executed            */

if (!pc && c == 'a')                  /* (1 && 1) == 1               */
pc = &c;                          /* This is executed            */
```

Const and Pointers

The `const` type qualifier applies to pointer variables as well as object variables.  A pointer variable may be so defined that the constant property applies to: only its dereferenced value, only its own value, or both values.

An expression that returns a `const` object is not a valid lvalue.  However, a pointer to a `const` object may be assigned to a pointer to a non-`const` object with only a compiler warning.  In addition, the `const` qualifier may be overridden by a cast with no compiler warning.  This allows for the dangerous possibility of modification of a `const` object through pointer indirection.

```    int i = 10;
const int ci = 25;                    /* no direct assignment to ci  */

int *pi = &i;
const int *pci = &ci;                 /* *pci is const,  pci is not  */
int *const cpi = &i;                  /*  cpi is const, *cpi is not  */
const int *const cpci = &ci;          /* cpci and *cpci are const    */

pci = &i;                             /* *pci == i                   */
pci = &ci;                            /* *pci == ci                  */
pci = pi;                             /* *pci == *pi == i            */
pci = cpci;                           /* *pci == *cpci == ci         */

/* *pci = 5;                                error - *pci is const       */

/* cpi = &i;                                error - cpi is const        */
/* cpi = pi;                                                            */

*cpi = 9;                             /* *cpi == i = 9               */

/* cpci = &ci;                              error - cpci is const       */
/* cpci = pci;                                                          */

/* *cpci = 5;                               error - *cpci is const      */

/* warning only - dangerous    */
pi = &ci;                             /* *pi == ci                   */
pi = pci;                             /* *pi == *pci == *cpci == ci  */

/* no warning - dangerous      */
pi = (int *)&ci;                      /* *pi == ci                   */
pi = (int *)pci;                      /* *pi == *pci == *cpci == ci  */

*pi = 5;                              /* *pi == ci = 5 modify const  */
```

Passing Arrays to Functions

When an array is passed to a function, what is placed on the stack is not the entire array, but only a pointer to the array’s first element.  The function may modify the array’s elements indirectly, since it receives a pointer.  The number of elements must be passed in a separate argument.

In a function call, the argument for an array must be a pointer to the array’s first element, which may be an array expression or a pointer variable.  In fact, the argument may be a pointer to any of the array’s elements, indicating that the function is to receive a shortened array.

Note that for a multi-dimensional array, the argument must be a pointer to a first-dimension element which is an array of all the higher-dimensions.

In a function’s definition or prototype, the parameter for an array may be coded as an array, for clarity, or a pointer, for accuracy.  When the parameter is an array, the first dimension is implied and it may be indicated by empty brackets `[]`.

For multi-dimensional arrays, all higher dimensions must be specified, to maintain the correct scale.  When the parameter is an array, all higher dimensions must follow the first dimension.  When the parameter is a pointer, it must be a pointer to an array of all the higher dimensions.

```    void func1Da(char );
void func1Db(char []);
void func1Dc(char *);
void func3Da(char );
void func3Db(char []);
void func3Dc(char (*));

char aD1 = "char";

char aD3 = {
{"big", "bag"},
{"wig", "wag"},
{"zig", "zag"},
};

char *pc = aD1;

func1Da(aD1);                         /* pass "char"   print: char   */
func1Db(&aD1);                     /* pass "har"    print: har    */
func1Dc(&aD1);                     /* pass "r"      print: r      */

/* using a pointer variable:   */
func1Da(pc);                          /* pass "char"   print: char   */

func3Da(aD3);                         /* pass &aD3  print: big    */
func3Db(&aD3);                     /* pass &aD3  print: wag    */
func3Dc(&aD3);                     /* pass &aD3  print: zag    */

/* using a pointer variable:   */
func3Da(paD2);                        /* pass &aD3  print: big    */

void func1Da(char a) {printf("%s\n", a);}
void func1Db(char a[])  {printf("%s\n", a);}
void func1Dc(char *a)   {printf("%s\n", a);}

void func3Da(char a) {printf("%s\n", a);}
void func3Db(char a[])  {printf("%s\n", a);}
void func3Dc(char (*a)) {printf("%s\n", a);}
```

Pointer to Function

The declaration `char (*pfc)(char*, int)` defines variable `pfc` that is a pointer to a function which takes parameters of `char*` and `int`, and returns a `char`.  Note that, as in a function prototype, it is not necessary to declare parameter names.  When a pointer to a particular function is assigned to a function pointer variable, that function may be called indirectly through the variable.  The function and the variable must agree in number and type of parameters, and in return type.  The expression for the pointer to a given function `func(`params`)` is `func`.  The expression for an indirect function call through functon pointer variable `pfc` is `(*pfc)(`params`)`.  This syntax is similar to the array syntax, but with `()` replacing `[]` as the dereferencing operator.

Standard C introduced alternative constructions of these expressions.  The alternative expression for the pointer to function `func(`params`)` is `&func`.  The alternative expression for an indirect function call through functon pointer variable `pfc` is `pfc(`params`)`.

Unlike object pointers, there is no generic function pointer.  Under some compilers, the pointer to `void` may be large enough to hold a function pointer with no loss of information, but the standard does not guarantee this.

The elements of an array may consist of pointers to function.

```    char  func(char*, int);            /* Function of specific params    */

char (*pfc)(char*, int);           /* Function pointer, same params  */

int i = 4;                         /* Variables for params and call  */
char c, a[] = "array";

pfc = func;                        /* Assign pointer to variable     */
c = (*pfc)(a, i);                  /* Indirect call                  */

pfc = &func;                       /* Alternative syntax             */
c = pfc(a, i);
```

In its most common use, a function pointer variable passes a type-specific function to another function that is coded as a generic routine to handle objects of any type. When the generic function is called, it takes the function pointer variable as an argument, and it also takes as arguments pointers to the actual objects it handles, defined as pointer to `void`.  The function pointer variable’s parameters are also defined as pointer to `void`.

Before the generic function is called, a pointer to a function that handles objects of a specific type is assigned to the function pointer argument.  The generic function manipulates the objects through the object pointer parameters and it performs type-specific actions by calling the type-specific function indirectly through the function pointer variable parameter.  For example, the generic function would be a sort, and the function pointer variable would convey the routine to compare the objects to be sorted.

```    int *maxint(int *, int *);
void *genfunc(void *, void *, void* (*)(void*, void*));

int num1 = 1, num2 = 2, *pi;

void *arg1, *arg2;            /* Object pointer variables            */
void* (*arg3)(void*, void*);  /* Pointer function variable           */

arg1 = (void*)&num1;          /* Cast object pointers to void*       */
arg2 = (void*)&num2;

/* Cast pointer to maxint to type      */
/* of function pointer variable max    */
arg3 = (void* (*)(void*, void*))maxint;

pi = (int*)genfunc(arg1, arg2, arg3);

/* Cast all args in place              */
pi = (int*)genfunc((void*)&num1, (void*)&num2,
(void* (*)(void*, void*))maxint);

/* Return pointer to int having max value  */
int *maxint(int *int1, int *int2)
{
if (*int1 > *int2)
return int1;
else
return int2;
}

/* Return pointer chosen by indirect call to function pointer variable  */
void *genfunc(void *obj1, void *obj2, void* (*max)(void*, void*))
{
if (obj1 == NULL)
if (obj2 == NULL)
return NULL;
else
return obj2;
else
if (obj2 == NULL)
return obj1;
else
return (*max)(obj1, obj2);
}
```