diskodev

DESIGN & DEVELOPMENT AGENCY

Filtering by Tag: C

Pointers 101 - Part 2

(This is a second post of a three part series giving an introduction to pointers in C/C++. The first post can be found here)

Pointers and Arrays
There is a strong relationship between pointers and arrays in C/C++. They are usually discussed together due to this. All arrays make use of pointers internally. So anything done through arrays can also be done using pointers. Using pointers makes your program run faster than normally using arrays. The declaration

       int i_arr[5];

defines a integer array i_arr of size 5. The array in memory would be represented as

image 001.png

You access the i-th element in the array using the notation i_arr[i]. The first element in the array is numbered 0 (i_arr[0]). Hence the last element is one less than the size of the array (i_arr[n-1]).

Now let us define a integer pointer that points to the first element in the array, shown below

        int *ptr_i_arr = &i_arr[0];

Now, ptr_i_arr has the address of the first element in the array i_arr. We can then manipulate the first element using the pointer. So to increment the value by 5, we could give as

        *ptr_i_arr += 5;

Here is the important part. Arrays are always stored in continuous memory locations (At-least abstracted that way). So using a pointer we can move along the array just by incrementing/decrementing it. Now ptr_i_arr is pointing to the first element in the array. So ptr_i_arr+1 or ptr_i_arr++ operations makes the pointer to point to the next element. ptr_i_arr+i makes it point to i-th element after i and ptr_i_arr-i makes it to point to i-th element before i. This is regardless the size of the data type pointed to. incrementing by i, points to the i-th element forward and decrementing by i, points to the i-th element backward.

If ptr_i_arr points to i_arr[0], then *(ptr_i_arr + 1) points to i_arr[1]. ptr_i_arr + i is the address of i_arr[i] and *(ptr_i_arr + i) is the value at i_arr[i]. Note: we do need to enclose ptr_i_arr + 1 in brackets ,before getting its value, because otherwise the prefix * takes precedence and you would be incrementing the value pointed by the pointer.

Pointers and arrays can be better visualized as,

image002.png

Moreover, since the name of the array returns the base address, we can get the pointer to point to the array by giving the expression

        int *ptr_i_arr = i_arr;

and following from above, we can also get the element i_arr[i] using the expression *(i_arr + i). As seen above, this is similar to how we index an element using pointers.

There is one thing to keep in mind with regards to the differences between pointers and arrays. An array name is not a variable. Hence expressions like i_arr = some_value and i_arr++ is not valid where as these expressions are valid using pointers.

When present as function parameters, char str[] and char *str are similar. Both can be manipulated as pointers inside the function. Check out the below code snippet to get a understanding of how pointers work with arrays.        

Multidimensional Arrays and Pointers
Consider the following 2-d array definition

int i_2d_arr[3][5] = { {4, 2, 7, 8, 1},
                                         {12, 19, 15, 16, 11},
                                         {23, 28, 22, 29, 28} };
Here, each row of the 2-d array can be thought of as a 1-d array. So we have 1-d array of 3 elements, each of which is a 1-d array of 5 elements. As in 1-d arrays, we can get the first element as i_2d_arr[0], the next as i_2d_arr[1] etc. More specifically, since the 0-th element is a 1-d array, i_2d_arr[0] gives the base address of the first 1-d array (this is nothing but the base address of the array {4, 2, 7, 8, 1}). Following from the same i_2d_arr[1] gives the base address of the second 1-d array ({12, 19, 15, 16, 11}).

Although the array is represented in a columnar format, the way it is actually stored is actually different. Array elements are stored in continuous memory locations. So if a pointer points to the base memory, we can move along the array just by incrementing/decrementing it. The above 2-d array would be represented in memory as

image003.png

Now going into the expressions to print the contents, (i_2d_arr + 0) gives us the address of the 0-th element in the 2-d array. similarly, *(i_2d_arr + 0) should give us 0-th element. But we need to remember that the 0-th element in the 2-d array is again a 1-d array. Hence the expression, *(i_2d_array + 0) gives the base address of the 0-th 1-d array. *(i_2d_arr + 0) is nothing is but i_2d_arry[0]. To access the first element in the 2-d array, we need to give i_2d_arr[0][0]. The equivalent pointer expression for this would be *(*(i_2d_arr + 0) + 0). Hence the different ways to access the first element are,  i_2d_arr[0][0] & *(i_2d_arr[0] + 0) & *(*(i_2d_arr + 0) + 0). Below code snippet shows you how to loop and print a 2-d array using pointer expressions.

Multidimensional Pointer Expressions
Let us look at a sample program given below.

Above, i_arr is an array of two 2-d arrays of size 2. The 2-d arrays present inside are in turn an 1-d array of 2 elements. So, the first cout prints the base address of the 3-d array. This is because the address of the 3-d, 2-d and 1-d array is the same. In the next cout, i_arr is an array of two 2-d array. So i_arr+1 gives the address of the second 2-d array. In the third expression, *i_arr+1, *i_arr gives the address of the 1st 1-d array in the 1st 2-d array. (Whew!!! I know. Stay with me). So *i_arr+1 gives the second 1-d array in the first 2-d array. Going on from above, the fourth expression **i_arr+1 gives the second element in the first 1-d array in the first 2-d array. Next, ***i_arr+1 just increments the first element in the 3-d array (1). Passing Multidimensional Arrays to a Function
There are many ways in which we can pass a multidimensional array as an argument to a function. They are explained below.

In the above snippet, three different functions are used to print out the 2-d array. In the first method (print_2d_array1), the base address of the 2-d array is passed as an argument to the function. The pointer is then used to access the elements using the formula, *([ptr_name] + i * [column_count] + j). i*[column_count] added to the base address, takes the expression to the correct 1-d array. Then this expression again added with j gives the correct element in the array.

The second method (print_2d_array2) works differently to the first. The base address of the 2-d array is passed to a pointer to a 1-d array of integers whose dimension is 5 (int (*ptr_2d_arr)[5]). During the run of the outer i loop, the expression t_ptr = ptr_2d_arr[i], assigns the address of the 0-th 1-d array, and then inside the j loop, it access the 1-d elements. During the next run, the expression assigns the address of the 1-st 1-d array and the inner j loop does the same work.

The third method (print_2d_array3) works similar to the second method. In fact, writing  int ptr_2d_arr[][5] is the same as writing int (*ptr_2d_arr)[5]. Both are pointers to an 1-d array of integers with 5 elements. We can then access the element as we would do normally in an array.

One very important point to note is, a 2-d array does not break up into a pointer to a pointer. It breaks up into a pointer to a array. See this discussion regarding the same.

We had seen how pointers work with 2-d arrays, but the above concepts can be easily extended to any dimension of arrays.

Array of Pointers
Array of pointers are nothing but a variable which holds a collection of addresses. The list of address present in the array can be address of isolated variables or addresses of array elements. Defining a array of pointers is shown below.

        static int i_arr[] = {1, 2, 3};
        static int *p_i_arr[] = {i_arr, i_arr + 1, i_arr +2};

The most frequent use of array of pointers is to store strings in the array. Consider the below definition,

        char *words[] = {“hi”, “bye”, “good”, “bad”};

these words are stored in memory in a layout shown below.

image004.png

The words are stored in some memory location and the array in turn points to those memory locations. This sort of architecture has a lot of advantages. Using an array of pointers, we can interchange elements in the array very easily. So if you want to inter-change the first and the second element in an pointer array, just changing the pointers is sufficient. It it was an normal array, you need to call strcpy to do the same work.

There are some differences between 2-d arrays and an array of pointers to note though. Look at the below definitions,

        char c_arr1[25][25];
        char *c_arr2[25];

then the expressions, c_arr1[0][1] and c_arr2[0][2] are both valid. But, c_arr1 is a 2-d array whose size is 25*25 char elements and initialized with some random values. c_arr2 allocates only 25 pointers and does not initializes them. Initialization must be done explicitly. And each entry in the array of pointers need not occupy all the 25 space. So if we have all "a" in each of the 25 locations, the total space taken up is 25*sizeof("a") char elements and not 25*25 char elements.

Constant Pointers
Pointer constants are pointers whose state you cannot change but the contents that it points to can change. If the content it points to are also constants, you cannot change it too. The following code fragment will help you understand constant pointers better.

         // Pointer is not constant
        // String pointed to is not constant
        char *ptr_str = “bat”;
        *ptr_str = ‘c’; // Operation possible
        ptr_str = “sat”; // Operation possible

        // Pointer is not constant
        // String is constant
        const char *ptr_str = “bat”;
        *ptr_str = ‘c’; // Operation not possible
        ptr_str = “sat” // Operation possible

        // Pointer is not constant
        // String is constant
        char const *ptr_str = “bat”;
        *ptr_str = ‘c’; // Operation not possible
        ptr_str = “sat”; // Operation possible

        // Pointer is constant
        // String is not constant
        char * const ptr_str = “bat”;
        *ptr_str = ‘c’ // Operation possible
        ptr_str = “sat”; // Operation not possible

        // Pointer is constant
        // String is constant
        const char * const ptr_str = “bat”;
        *ptr_str = ‘c’; // Operation not possible
        ptr_str = “sat”; // Operation not possible

That is it for part 2 of the series. Part 3 will be coming up shortly. And sorry for the long post.

If you have read this far, you should follow me on twitter.

Also feel free to follow my projects on github.

Pointers 101 - Part 1

(This is a first post of a three part series giving an introduction to pointers in C/C++)

Pointers are objects that contain the address of another object. Pointers can contain the address of any datatype in C/C++. Pointers are mainly used for dynamic memory allocation, representing dynamic structures, recursion among various others. Pointers are sometimes tricky if you do not get your head around it. You can easily shoot your foot when using pointers. Program crashes and memory overwrites are some common problems that occur with incorrect pointer usage.

In part 1, we shall be looking at the basics. Pointers to arrays and strings & pointer arrays will be covered in part 2. Advanced topics like dynamic memory allocation, data structures etc will be covered in part 3.

Please do read the comments in the code samples given in the post. Lots of explanations are contained within it.

Do we need to know about pointers?
Although no modern languages and frameworks support pointers (at least explicitly), most concepts in the architecture are represented and implemented using pointers. Memory management, Representation of File Systems, Databases, Data Structures etc are some places these concepts are used extensively. Even if you are going to work only with high level languages, it is essential to know about pointers. They help you understand the internal workings better.

Pointers and Modern Computer Architecture
First, to understand how pointers work, we need to understand how memory is represented in modern computer architecture. Memory is abstracted and represented as an array of consecutive storage locations.  Variables, created by a program, are stored in these locations and each one of them has an address associated with them. In order to access the value stored in a memory location, we need to know its base address, which is nothing but the starting address. Using the base address along with the size of the datatype we can access the value of the type.

Pointers provide a level of indirection from the actual physical representation and helps you abstract from it. It can be best explained by the following illustration:

image001.png

Here, p is a pointer which is pointing to some object o ie, the address of o is contained in p. We can use p (after indirection) wherever o is needed. During the run of the program, p can stop pointing to o and can point to some other variable. This level of indirection not only has its uses, it also brings in performance gains and gets you closer to the underlying hardware.

In C/C++, you can declare a pointer by the following synta

        datatype *pointer_name;

Here, datatype can be a built-in or a user defined type and pointer_name is the variable name you decide to give. We can make the pointer point to a variable using the & (address-of) operator.

        int index = 15;
        int *idx_ptr = &index;

We have an int variable index which has a value 15. We then create a pointer and make it point to index by taking its address. The & operator only applies to objects in memory. This is so because objects not in memory do not have an address. Hence you cannot use the & operator to constants and expressions.

Now you can use indx_ptr whever an index is needed. For example, if you want to increment index, you could giv

        *idx_ptr += 1;

Pointer Expressions
The blow code sequence shows how to declare various pointers and how to use them in programs.

When you run the above code, you should be getting a similar output as shown below (Except for the addresses)

        Address of i - 0x22ccd4
        Address of i - 0x22ccd4
        Address of i_ptr - 0x22ccd0
        Value of i - 5
        Value of i_ptr - 0x22ccd4
        Value of i - 5
        Value of i - 5

The expressions are the same for other built-in types too. Try not to make a pointer point to a different type. You might lose some information when manipulating the type through the pointer. This is called slicing. For example,

        int i = 5;
        char *c_ptr = &i;

Above, c_ptr here slices the value of i. Only the char part of i is stored in c_ptr. Rest of the value is lost in c_ptr.

Pointer to a Pointer and Function Pointers
A pointer which points to another pointer is called a pointer to a pointer. Since pointer too has an address, you could get another pointer to point to it. In memory, it would be represented a

image002.png

Above, i_ptr is the pointer which points to the variable i. i_ptr_ptr is a pointer which points to i_ptr. You can manipulate i using both i_ptr & i_ptr_ptr. Below code samples show how to use pointer to a pointers and function pointers.

The output for the code should be something similar to

        Address of i - 0x22ccd4
        Value of i - 5
        Address of first level pointer - 0x22ccd0
        Address of first level pointer - 0x22ccd0
        Address of pointer to a pointer - 0x22cccc
        Value of pointer to a pointer - 0x22ccd0
        Hello World

Function pointers are pointers that point to a function instead of a variable and when de-refrenced, they call their respective function. It can take in arguments like any other functions.

Function pointers can be assigned, placed in arrays, passed to functions, returned by functions etc. The below snippet explains the concepts behind function pointers.

Here, we are trying to use the same built-in qsort() method to sort both integers and char arrays. The way we do this is pass different comparison function for each of the type. The comparison function is passed as a function pointer to the qsort method. When qsort runs, the comparison function is called through the function pointer, for each pair of values that need to be compared. Based on the return value of the comparison function, the elements in the array are ordered accordingly.

In the above code, do not be overly concerned with understanding all of it. Concepts present here will be explained in successive posts.

Function pointers sometimes make it verbose to decode its declaration. For example,

        int *some_func()

and

        int (*some_func)()

is that the first is a function - taking no arguments and return an int pointer and the next is a pointer to a function - taking no arguments and returning an int. The point to be noted here is that * has a lower precedence than (). Hence the () are required when declaring a function pointer.

Function pointers are mainly used in function callbacks, event driven programs and selecting functions to execute dynamically based on some values.

Pointers and Function Arguments
In C/C++, you cannot alter the value of a variable in the calling function. All variables are passed by value rather than references. So when you write a swap function like this,

       void swap(int x, int y)
       {
            int temp;
            temp = x;
            x = y;
            y = temp;
        }

and call it with swap(a, b), because of call by value, swap cannot interchange the values. The values of a and b would remain the same when the call returns. If you want to forever change its values, you need to use pointers in the function. So swap should be rewritten as,

        void swap(int *x, int *y)
        {
            int temp;
            temp = *x;
            *x = *y;
            *y = temp;
        }

Now the function should be called as, swap(&a, &b). Since the & operator produces the address of a variable, &a is a pointer to a. Pointer arguments enable a function to access and change objects in the function that called it.

Another advantage in passing pointers as arguments in functions is that we could make the function return more than one value. We pass pointers as arguments to the functions, and inside the function, we write the values directly into the variable's memory using pointers. For example,

        void some_func(int *val1, int *val2, int *val3)
        {
            *val1 = 5;
            *val2 = 6;
            *val3 = 7;
        }

Here, the values of the three arguments passed into some_func will be maintained even after we exit the function.

Understanding Pointer Declarations
Pointer declarations are like every other declaration in C/C++. Methods to successfully decode declarations can be found in this post. It basically advices,

        "Start at the variable name (or innermost construct if no identifier is present. Look right without jumping over a right parenthesis; say what you see. Look left again without jumping over a parenthesis; say what you see. Jump out a level of parentheses if any. Look right; say what you see. Look left; say what you see. Continue in this manner until you say the variable type or return type."

So following from above, some example decoding would be,

        int *some_var[5]
            some_var is an array[5] of pointers to an int
        int (*some_var)[5]
            some_var is a pointer to an int array[5]
        void (*some_func)()
            some_func is a pointer to a function - taking no args and returning none
        void *some_func()
            some_func is a function which return a void pointer
        char (*(*x())[])()
            x is a function returning pointer to a array of function pointers returning chars

That is it for part 1 of the series. Part 2 will be coming up shortly.

If you have read this far, you should follow me on twitter.

Also feel free to follow my projects on github.