22 May 2009

Arrays and Pointer to arrays : One Dimension

In this snippet we will look at manipulating pointers to single-dimensional arrays with ease. For this we first need to review one-dimensional arrays.Subsequent snippet will cover multidimensional arrays.


***************************
Manipulating simple arrays
***************************

Suppose we have the following two declarations

int array[10];

and

int * parray[10];

Diagrammatically, the difference between the two arrays  is as shown below
two figures.

Figure-1:

              +——————————+
array [0]      |   int    |
              +——————————+
array [1]      |   int    |
              +——————————+
array [2]      |   int    |
              +——————————+
array [3]      |   int    |
              +——————————+
array [4]      |   int    |
              +——————————+
array [5]      |   int    |
              +——————————+
array [6]      |   int    |
              +——————————+
array [7]      |   int    |
              +——————————+
array [8]      |   int    |
              +——————————+
array [9]      |   int    |
              +——————————+




Figure-2:


             +——————————+         +——————————+
parray[0]     |  int *   |  ——————>|   int    | *parray[0]
             +——————————+         +——————————+
+——————————+
parray[1]     |  int *   |  ——————————————————————————————
———>  |   int
| *parray[1]
             +——————————+           +——————————+
+——————————+
parray[2]     |  int *   |  ————————>|   int    | *parray[2]
             +——————————+           +——————————+              +——————————+
parray[3]     |  int *   |  ——————————————————————————————
———> |   int    |
*parray[3]
             +——————————+          +——————————+               +——————————+
parray[4]     |  int *   |  ——————> |   int    | *parray[4]
             +——————————+          +——————————+
+——————————+
parray[5]     |  int *   |  ——————————————————————————————
—————>|   int
| *parray[5]
             +——————————+           +——————————+
+——————————+
parray[6]     |  int *   |  ————————>|   int    | *parray[6]
             +——————————+           +——————————+              +——————————+
parray[7]     |  int *   |  ——————————————————————————————
———> |   int    |
*parray[7]
             +——————————+          +——————————+               +——————————+
parray[8]     |  int *   |  ——————> |   int    | *parray[8]
             +——————————+          +——————————+
+——————————+
parray[9]     |  int *   |  ——————————————————————————————
———>  |   int
| *parray[9]
             +——————————+
+——————————+


           int * implies int pointer



In the first declaration we access the ith int in the array by performing array[i]. In the second declaration, we access the ith integer (though this int is not part of the array) by performing     *parray[i]., In the second declaration, the ith int pointer (which are elements of the array parray) can be accessed by performing  parray[i] 


***************************
Dual Nature of array names:
***************************

Array names have dual nature. Sometimes it signifies the whole array. That
is why, given

TYPE  array_name[M];

We can find the size of the array by printing out  sizeof (array_name). For
example:

Given

long     array_of_long[100] ;

Then, the size of array  array_of_long  is given by  sizeof(array_of_long.
Hence the array name signifies the whole array.

At other times the array name behaves as a pointer. The C compiler creates
a  pointer whose name is again the array name itself. And this points to
the first element of the array. Thus given:

TYPE array_name[M];

Then array_name points to the first element, i.e.  array_name[ 0 ].  Note
that the elements of the array is of the type TYPE.   array_name[ 0 ] can
be anything, an int, char, struct etc.

Diagrammatically, this can be viewed as:
Figure-3:

+——————————————+         +——————————+
|  array_name  | ——————> |   TYPE   | array_name[0]
+——————————————+         +——————————+
                        |   TYPE   | array_name[1]
                        +——————————+
                        |   TYPE   | array_name[2]
                        +——————————+
                        |   TYPE   | array_name[3]
                        +——————————+
                        |   TYPE   | array_name[4]
                        +——————————+
                        |   TYPE   | array_name[5]
                        +——————————+
                             .
                             .
                             .
                             .
                        +——————————+
                        |   TYPE   | array_name[M-1]
                        +——————————+


***************
Variable names:
***************

When we declare an array as below:

TYPE array_name[M];

The compiler provides  the following variable names.

array_name[0], array_name[1],  . . . . ,  array_name[M-1].

These variable names can be manipulated  like any other variable. It should
be noted that the M number of variables are of the type TYPE.


*****************************
Incrementing the array names:
*****************************

We saw earlier that in the case of single dimensional array, the array name
(in our example this is array_name) is also a pointer to the first element,
which in our examples is  array_name[0].

We can't increment the contents of the array name, which is a constant, but
we can do, for example

p = array_name + 1;

When we do this, p points to the next element, i.e.,  array_name[1].

In general, if we do:

p = (array_name + i)

Then p points to the ith element, i.e.,   array_name[i]

This result is important, which states that:

( array_name + i )  points to element  array_name[i] .



******************************
*************************************
Relationship between index and pointer in single dimensional array:
******************************
*************************************

We know that if p points to some object, then *p is that object
Thus, it follows that- since

(array_name + i ) points to array_name[i] ,

therefore, it follows that

*(array_name + i)  =   array_ name[i]

the above relation, rewritten as below is the heart and soul of arrays and
pointers

array_name[i] =  *(array_name + i)

An important corollary happens when we put i=0,  we have

array_name[0] =  *array_name


******************************
********
Alternative declaration of array name:
******************************
********

If we have a general single dimensional array declaration

TYPE array_name[M];

Then the array name can be considered to behave as the following
declaration. Because array_name points to an element of type TYPE.

TYPE *array_name;  /* i.e., array name points to TYPE */

Thus, there are two ways we can write a prototype of a function in which
the pointer array_name is passed.

The first method is
void f( TYPE  array_name[] );

the second method is
void f( TYPE  *array_name );



******************************
**********
Pointers to arrays (single dimensional):
******************************
**********

A pointer to a single dimensional array is declared as, for example,

char  (*p)[10] ;

Here  p points to the  whole array of 10 characters, as shown in the
diagram below



+——————————————+         +——————+
|      p       | ——————> | char |  0
+——————————————+         +——————+
                        | char |  1
                        +——————+
                        | char |  2
                        +——————+
                        | char |  3
                        +——————+
                        | char |  4
                        +——————+
                        | char |  5
                        +——————+
                        | char |  6
                        +——————+
                        | char |  7
                        +——————+
                        | char |  8
                        +——————+
                        | char |  9
+——————————————+         +——————+
|    p+1       | ——————> | char |
+——————————————+         +——————+
                        | char |
                        +——————+
                            .
                            .
                            .


Since  p points to an array of  10 chars therefore (*p) is the array of 10
chars. That is, (*p) means the whole array of 10 characters. And just to
confirm that-  we can print out sizeof(*p) we get 10 bytes.

This also means, as per our earlier snippet, if we increment p by 1, the
value will change by 10 bytes.


***************
The  Technique:
***************
Let us look at a few tricks for manipulating pointers to an array.

Before coming to the tricks, The basics are that:
any single dimensional array declaration has the following declaration

TYPE     array_name[M] ;

While pointer to an array type of declaration has the syntax.

TYPE     ( *pointer_to_array )[M] ;

If we compare the two we can see that , (*pointer_to_array) is nothing but
the array name. What this means is that wherever results we had with
respect to array_name previously, if we substitute it by
(*pointer_to_array) we will get the same result. This is the basis of the
trick. We will now apply this and see a few more methods.


We will use the following examples to show the methods.

We will compare the following two declarations to explain the methods.

char   (*p)[10] ;

char    array_name[10];

In the above case     (*p) is the name of the array

Therefore:
1.    Size of the array array_name is given by sizeof(array_name).  Since
(*p) is the name of the array, therefore size of array (*p) is given by
sizeof(*p).


2.    The compiler creates the following memory variables array_name[0],
array_name[1], array_name[ 2], .... ,  array_name[M-1] where they hold a
char. Similarly, the compiler creates the following variable (*p)[0],
(*p)[1], (*p)[2]  .... ,  (*p)[M-1], where each of the variable holds a
char.


3.    Just as array_name points to array_name[0], similarly, (*p) points to
(*p)[0].

If we perform (array_name + 1) it will point to array_name[1]. Similarly,
if we do  (*p)+1 it will point to (*p)[1]. Which means that;

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

 In general we have:

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

A corollary of this is:

(*p)[0]  =  **p


4.    However the following analogy fails in the case of pointer to arrays.
We said that, if there is a declaration as below;

TYPE array_name[M];
then, if we wish to  pass array_name as a parameter in the function, then
there can be two ways of writing the prototype;

void f( TYPE  array_name[] );

or

void f( TYPE  *array_name );

The first method works for pointer to array, but the second method does not
work.

Thus, if we wish to pass a pointer to a single dimensional array in a
function, then function prototype should be

void f( TYPE  (*p)[] )


This will not work:
void f( TYPE  **p)



Of course, in all the  above examples of pointer to arrays we have assumed
that we have initialized ‘p’ correctly, may be by the pointer we get by a
malloc or some other means.

The following program will show more inputs about manipulating pointers to
arrays,


#include

main()
{
 int arrray[10] = {0,1,2,3,4,5,6,7,8,9};

 int (*p)[10];

 int i;

 p = (int (*)[10]) arrray;     /* initialize p by casting array */

  for(i=0;i<10;i++)
      printf("%d, %d, %d \n",arrray[i], (*p)[i], *((*p)+i));

}


We will see the output as:

0, 0, 0
1, 1, 1
2, 2, 2
3, 3, 3
4, 4, 4
5, 5, 5
6, 6, 6
7, 7, 7
8, 8, 8
9, 9, 9

which proves that  all the expressions in the printf statement are
identical.


This little trick works in the following case too.

Suppose we have

int (**q)[10];
If we have initialized q correctly then (**q) is the name of the array.
Therefore

1.  Size of array  is   sizeof(**q)

2.  The following variables are created (**q)[0], (**q)[1],  ....,
(**q)[9].

3.  (**q) points to (**q)[0] and in general  (**q)[i]  =  *((**q)+i)


The following code will show  what we have meant so far.

The data structure used in the following code is shown here:



+——————————————+         +——————————————+         +——————+
+——————————————+
|      q       | ——————> |       p      | ——————> | int  |  <—————— |
arry      |
+——————————————+         +——————————————+         +——————+
+——————————————+
                                                 | int  |  8
                                                 +——————+
                                                 | int  |  12
                                                 +——————+
                                                 | int  |  16
                                                 +——————+
                                                 | int  |  20
                                                 +——————+
                                                 | int  |  24
                                                 +——————+
                                                 | int  |  28
                                                 +——————+
                                                 | int  |  32
                                                 +——————+
                                                 | int  |  36
                                                 +——————+
                                                 | int  |  40  bytes
                       +——————————————+          +——————+
                       |    p+1       | ——————>  | int  |
                       +——————————————+          +——————+
                                                 | int  |
                                                 +——————+
                                                     .
                                                     .
                                                     .

sizeof(*p) = 40 bytes,  assuming 32-bit integer.




#include

main()
{
 int arry[10] = {0,1,2,3,4,5,6,7,8,9};

 int (*p)[10];

 int (**q)[10];

 int i;


 p = (int(*)[10])arry;   /* initialize p with pointer array */

 q = &p;      /* initialize q with the address of p */

  for(i=0;i<10;i++)
      printf("%d, %d, %d, %d, %d, %d \n",
        arry[i], *(arry+i), (*p)[i], *((*p)+i), (**q)[i], *((**q)+i));

}
==============================
========
Result:
0, 0, 0, 0, 0, 0
1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2, 2
3, 3, 3, 3, 3, 3
4, 4, 4, 4, 4, 4
5, 5, 5, 5, 5, 5
6, 6, 6, 6, 6, 6
7, 7, 7, 7, 7, 7
8, 8, 8, 8, 8, 8
9, 9, 9, 9, 9, 9

 As we see all the expressions in the printf statement have the same
meaning.


In the next snippet, we will discuss about pointers to two-dimensional
arrays.

11 May 2009

Preventing Precedence Errors: EqualitytInequality

A very commonly observed precedence error during usage of expressions is inadequate parenthesizing.  Here we take examples of Equality/Inequality expressions:

if(var1 & var2 == 0)

The above is incorrect because == has a higher precedence than &, therefore in the above expression  var2==0  will be computed first, which is a bool. Then that bool will be bit_AND'ed with var1.  And this was not our intention.

The correct way  is:

if((var1 & var2) == 0)


In practice, the test for equality/inequality must be the last logical operation, but it can happen otherwise, if there are operators of lower precedence than  ==  or   !=  in the expression.

If we recall our three liner:

S—U—Ari
Re—Bit—Lo—C
Assignment—Comma


The  “e”  in Re stands for equality/inequality, and when they are there in an expression with operators of lower precedence then the  ==  or !=  will get executed earlier. To change the order of evaluation we need to appropriately parenthesize these operators. These operators(with precedence lower than  ==  and   != )  are   Bit—Lo—C—Assignment—Comma.   In practice we will find bit and assignment operator mixed with  ==  and   != operators.

So when we see this mixture, i.e.,==  or  !=, &,  | ,  ^, =   in a statement,  parenthesis are to be taken care.

The following are some examples where precedence errors are very common.


a)    Test if FLAG_A is clear in message incorrect
if(message & FLAG_A == 0)

correct
if((message & FLAG_A) == 0)


b)    Test if FLAG_ A is set in message  incorrect
if(message & FLAG_A != 0)

correct
if((message & FLAG_A) != 0)



c)    Test if all flags are clear incorrect
if ( message & (FLAG_A | FLAG_B | FLAG_C) == 0)

 correct
if (( message & (FLAG_A | FLAG_B | FLAG_C)) ==0)

d)    Incorrect
if ( c = getchar() != EOF)

correct
if (( c = getchar()) != EOF)

In all the above cases, parenthesizing is to be done for operands with precedence lower than  == or !=  so that they are executed earlier.

In short, when and expression has   equality/inequality operator as the final operand and we see that there are operators in the expression whose precedence levels and are still lower than equality / inequality, then we should get the parenthesis correct. The operators with lower precedence than  “Re” are  Bit—Lo—C—Assignment—Comma