Understanding Pointers - Part 1 - Basics

Pointer is variable type in C Programming language, that is used to store a memory address. Being able to store a memory address in a variable and then use it turns out be a great asset when you are doing low level programming.


Basics

A Pointer is a variable type that stores a memory address.

Note: When we say 'memory', we will assume we are talking about the RAM, where your program is loaded before execution.

On Memory and addresses.

Before going further, we need to get some minimal basic understanding of memory. This is crucial to successful understanding and use of pointers in C.

Let's say that you have a 4 GB RAM installed in your computer. There are (4 * 1000 * 1000 * 1000) bytes in your RAM. Now, each byte stores some information. To access information stored in a particular byte or to store some information in a that byte, the CPU needs to identify that particular byte somehow. And for that, we have a memory address. Each byte is assigned a unique number that is called its address, its memory address.

Normally, from a programming prespective, we just need to remember that memory addresses are a set of sequential numbers, starting at some number and ending at another. 

So, a pointer variable basically stores a number. A number representing a particular location in your computer memory.

Declaring a pointer

To declare a pointer variable in your code, you must first need to decide what kind of variable is going to be stored at that memory address.

For example, you could have an integer stored at that memory address. Or it could be a character. Or a float. etc.

So, to declare a pointer in your code, you must know what's going to be stored at that address in memory.

To start with, we will deal with integers.

Let's say I have a integer variable, var, and I have assigned it a value of 10. Like this:

int var = 10;

Now, var is stored somewhere in memory. To know the memory address where var is stored, we would declare a pointer variable that stores an address of an integer. Then we would assign the address of var to the pointer variable. Look at the code below:

int var = 10; // var declared and assigned a value of 10
int *ptr;    // a pointer variable 'ptr' declared
ptr = &var;   // Value of var's memory address stored in ptr

Let's understand, step by step, what we did here.

• First, we declared an integer variable var and we assigned it a value of 10.

• Then, we declared a pointer variable ptr using the * operator. Using this syntax tells the compiler that 'ptr' is a pointer variable, that will store memory address of an integer.

• Then, we assigned the address of var to ptr, using & operator. & operator is used to access the location of an object in C.

Here's a complete program, to print the address of var, using a pointer variable.

#include <stdio.h>
int main()
{
    int var = 10;
    int *ptr;
    
    ptr = &var;
    
    printf("0x%x",ptr);
}

Here is the output that I get when I run this program:

0x48d51dac

Try running this program on your computer and you may get a completely different memory address printed. That's ok.

The exact memory address assigned to any variable in our program, depends on a whole lot of factors and is out of scope of this lesson. As long as you were able to get some memory address printed, we are on the right track.

Note, how in the above program, I printed the ptr using a %x in printf. There's no special reason behind doing this. It's just more of a habit to represent memory addresses as hexadecimals.
We could have printed the memory address as an integer too. But, in the rest of the lesson, I shall print memory addresses in hexadecimal format as a convention.

Practicing declaring pointers

Now, remember I said that to declare a pointer we must know what kind of variable is going to be stored in the memory address represented by the pointer. To declare a pointer that stores address of an integer, we declared it like this:

int *ptr;

If we read the above statement backwards, we shall get some idea of how to declare a pointer variable. Let's read this statement backwards like this:

Address stored in ptr points to 'int' or 'integer'. Meaning, if you will go to the address stored in ptr, you will find an integer stored there.

Let's try another declaration:

int *newptr;

Reading the above declaration backwards -> Address stored in newptr points to 'integer'.

Another one:

char *ptr;

Reading this backwards -> Address stored in ptr points to a 'character'.

Now, let's declare a pointer that stores address of a float number.

float *ptr; // Address stored in ptr points to a floating point.

Let's write a program to declare different kind of pointers:

#include <stdio.h>
int main()
{
    int a = 10;
    char b = 'A';
    float c = 3.14159;
    double d = 2.71828182;
    
    int * ptr1;        // address stored at ptr1 points to integer
    char * ptr2;       // address stored at ptr1 points to character
    float * ptr3;      // address stored at ptr1 points to float
    double * ptr4;     // address stored at ptr1 points to double
    
    ptr1 = &a;
    ptr2 = &b;
    ptr3 = &c;
    ptr4 = &d;
    
    printf("0x%x \n", ptr1);
    printf("0x%x \n", ptr2);
    printf("0x%x \n", ptr3);
    printf("0x%x \n", ptr4);

    return 0; 

}

Here is the output that I get, when I run the above program:

0x215c78f0
0x215c78ef
0x215c78f4
0x215c78f8

I would encourage you to type this program in your favorite editor and compile and run it on your machine. This will make you more comfortable with pointer notation and then we can starting looking ahead at how we use pointers in C programming.

Printing the value stored at a memory address

We have understood that a pointer stores a memory address. We can use the * operator, to print the value stored at the memory address in a pointer.

Let's see how to do this:

int * ptr;
int a = 10;
ptr = &a;

printf("%d \n", *ptr);

As we can see, the * operator is used to access the value stored at the memory address in a pointer.

Once we apply the * operator to a pointer, we get the value at that memory address and we can use it, just like we use any other value in our program. Like, assigning it to another variable.

int * ptr;
int a = 10;
ptr = &a;     // ptr now stores the address of a
int b = *ptr; // b now gets the value stored at memory address of a, which is 10

Here's the full program:

#include <stdio.h>
int main()
{
    int *ptr;
    int a,b;
    
    a = 10;
    ptr = &a;
    
    b = *ptr;
    
    printf("a=%d b=%d \n",a,b);

    return 0; 

}

Here's the output that I get for the above program:-

a=10 b=10

I would encourage you to try running each of the example programs shown in this lesson. That's it for this lesson.

In the next lesson, we shall see how pointers are used in C language to accomplish various tasks and also learn about pointer arithmatic.

String tokenization in C

Let's say you have to write a C program to tokenize a string that contains a list of tokens separated by some delimiter, say a comma.

You could figure out your own algorithm for doing that, but usually a saner approach is to find a library function that already does that.

And C Programming language library does provide a function, called strtok that does exactly that. You provide it with a string and a delimiter string, and it helps you in splitting the string based on that delimiter.

So instead of writing our own function, we shall go forward and try to use strtok for our task. In doing so, we shall learn how to use it and other such functions.


Here is the function declaration of strtok function:

char *strtok(char *str, const char *delim);

From the function declaration above, we can see that strtok takes the string as its first argument and the delimiter/separator string as its second argument.
The first call to strtok shall contain the string to be parsed and the delimiter. This shall return the text between the start of the string and the first occurance of the delimiter string. To get the next token, we only need to pass a NULL as the first argument and the delimiter as the second. strtok maintains the context and knows it has to parse the same string that you provided earlier.

The following program shows an example.

#include <stdio.h>
#include <string.h>
int main()
{
    char str[50];
    char *token;

    strcpy(str,"abc,def,ghi");
    token = strtok(str,",");
    printf("%s \n",token);
    
    token = strtok(NULL,",");
    printf("%s \n",token);
    
    token = strtok(NULL,",");
    printf("%s \n",token);
    
    return 0;
}

In the above example, we have a string "abc,def,ghi" and we parse it into tokens abc, def and ghi.
Note, how we pass str as the first argument in the first call to strtok and NULL as the first argument in the subsequent calls. Here is how the output of this program is going to look like:

abc
def
ghi

strtok() returns a NULL if it is not able to find any tokens. We can use this property when there are unknown number of tokens to be parsed. We can keep calling strtok() in a loop after the first call, until it returns NULL.

#include <stdio.h>
#include <string.h>
int main()
{
    char str[50];
    char *token;

    strcpy(str,"abc,def,ghi,jkl,mno");
    token = strtok(str,",");
    
    while ( token != NULL ) 
    {
        printf("%s \n",token);
        token = strtok(NULL,",");
    }
    
    return 0;
}

Here is the output of above program:

abc
def
ghi
jkl
mno

We can also provide multiple delimiters to strtok, as shown below.

#include <stdio.h>
#include <string.h>
int main()
{
    char str[50];
    char *token;

    strcpy(str,"abc,def:ghi;jkl,mno");
    
    token = strtok(str,",;:");
    
    while ( token != NULL ) 
    {
        printf("%s \n",token);
        token = strtok(NULL,",;:");
    }

    return 0;
}

Here we pass a delimiter string which contains a comma, semicolon and a colon. strtok function checks for each of these and identifies a token if it finds any of these characters.
Output of above program:

abc
def
ghi
jkl
mno

Another thing about strtok that we need to know is that when it encounters more than one delimiters in succession, it considers them to be a single delimiter. Program below shows this scenario:

#include <stdio.h>
#include <string.h>
int main()
{
    char str[50];
    char *token;

    strcpy(str,"abc,,,def,,,,,,ghi");
    
    token = strtok(str,",");

    while ( token != NULL ) 
    {
        printf("%s \n",token);
        token = strtok(NULL,",");
    }

    return 0;
}

Output of the above program:

abc
def
ghi 

Also, if  a delimiter is encountered at the start or end of a string, strtok() ignores them, as shown below.

#include <stdio.h>
#include <string.h>
int main()
{
    char str[50];
    char *token;

    strcpy(str,",,,abc,,,def,,,,,,,ghi,,,,,,");
    
    token = strtok(str,",");
    while ( token != NULL ) 
    {
        printf("%s \n",token);
        token = strtok(NULL,",");
    }

    return 0;
}

Output of the above program:

abc
def
ghi 

There are a few common pitfalls that we should avoid while using strtok().

Never pass a constant char pointer as the first argument of strtok. That's because strtok changes the first argument internally, so passing a constant pointer shall result in a crash ( unless you have a signal handler implemented ).

Something like below will result in a crash:

#include <stdio.h>
#include <string.h>
int main()
{
    char *str = "abc,def";
    char *token;

    token = strtok(str,",");
    printf("%s \n",token);

    return 0;
}

Also, if want to maintain the string that is to be parsed for further usage, you should avoid passing the pointer to the string directly to strtok, as it changes its first argument internally. It's advisable to copy the string into a temporary buffer and pass that to strtok to get your tokens.

Next, strtok is not thread-safe. That's because it uses a static buffer internally. So, you should take care that only one thread in your program calls strtok at a time.

If you have a multithreaded program, then you should be using strtok_r function instead of strtok. strtok_r is a reentrant version of strtok. Let's understand how we can use strtok_r.

Here is the function declaration:

char *strtok_r(char *str, const char *delim, char **saveptr);

strtok_r has an additional third argument, saveptr, a pointer to a char pointer that is provided by the caller. strtok_r uses this saveptr to maintain context between subsequent calls for the same string. The value of saveptr should remain unchanged in all calls to the strtok_r for it work correctly.


Here is an example program showing strtok_r usage

#include <stdio.h>
#include <string.h>


int main()
{
    char str[] = "apple,orange,banana";
    char *saveptr;
    char *token;

    token = strtok_r(str,",",&saveptr);

    while ( token != NULL )
    {
        printf("%s \n",token);
        token = strtok_r(NULL,",",&saveptr);
    }

    return 1;
}

Output of the above program:

apple
orange
banana

Both strtok and strtok_r change their first argument, the pointer to the string supplied to it in the first call. As a programmer, you should be aware of this, while using strtok or strtok_r in your programs.


Now, let's say that you would like to know if there was no content between successive delimiters in the input string. With strtok you wouldn't be able to get this information, because it treats successive delimiters as one. For this task, its best to use strsep() function instead of strtok/strtok_r.
Here is an example of strsep usage:

#define TESTSTRING ("abc,,,def,,,ghi")
int main()
{
    char *str; 
    char *token;

    str = (char *) malloc(sizeof(char) * (strlen(TESTSTRING)+1));

    strcpy(str,TESTSTRING);
    
    token = strsep(&str,",");

    while (token != NULL)
    {
        if ( strlen(token) == 0 )
        {
            printf("No Content\n");
        }
        else
        {
            printf("%s\n",token);
        }

        token = strsep(&str,",");
    }

    return 0;
}

Here is the output of the above program:

abc
No Content
No Content
def
No Content
No Content
ghi 

Again with strsep, we have to keep in mind that it changes the pointer whose address is passed to it as the first argument.

With both strsep and strtok/strtok_r functions, its best to copy the string to be split into a temporary buffer and then use these functions for tokenization. By doing this we don't have to worry about changing the original string pointer, as it could have been passed to you from another function and you may not really know exactly which memory the string resides in or what the caller intends to do with it after you have returned.

So, as we can see, C library does provide us functions that help us with string tokenization, but we need to take care how we use them.

Circular linked lists - Attributes, Implementation and Uses

What is a Circular Linked List

A Circular Linked List is a linked list in which the last node in the list points to the first node in the list. This property makes it circular.

This is shown in the figure below - the last node in the linked list points to the head node of the list, making it circular.

A Circular Linked list

Uses of a Circular Linked List

1. Circular linked lists are a natural option to represent something circular or a set of objects that form a loop. 
2. In a circular linked lists you can have easy access to end of the list. This gives you flexibility to add or delete elements at both ends of the list in a quick manner. This attribute comes in handy in a variety of situations.
3. Another attribute of a circular linked list is that a pointer to any node in the list gives you the ability to traverse the whole length of the list. This flexibility is not available in a normal single linked list where one needs the pointer to the head of the list to traverse the whole length of the linked list.
4. An interesting feature of a circular linked list is that one can create two circular linked list out of a single circular linked list in constant time. This can be done by simply swapping the next pointers of the two nodes that would form the tail nodes of the newly constructed circular linked lists. In a similar manner, if you swap the next pointers of a last nodes of two separate circular linked lists, you are merging the two lists into a single circular linked list in a constant time operation.
5. Circular linked lists can be normally used where a resource needs to shared among a number of users in a round robin manner. 
6. A good example of this is how an operating system can schedule CPU resources among processes in round robin manner.

          Another example is a multi-player game where the chance to play the game passes around                     the players in round robin manner.

Linux Kernel Implementation of a Circular linked list

Linux kernel code uses circular linked lists extensively and so the circular linked list implementation in the linux kernel is a good case study in implementation and usage of a circular linked list.

Linux kernel implements a doubly linked circular linked list.

The definition of the list structure in linux looks like this 

struct list_head {
 struct list_head *next, *prev;
};

The list head structure shown above represents the link of a particular node in the list. To implement a circular linked list using this, one needs to embed this structure in another structure that would hold the information associated with the node.

e.g.
Let's say, you want to build a circular linked list in which each node would store an integer as information. Let's call this list circular_int_list. Using Linux Kernel's list_head, you would declare your list structure as follows

typedef struct circular_int_list
{
        int info;
        struct list_head list;
};

This structure represents a single node in the linked list. Linux implementation provides a number of functions to manipulate and use a linked list. Let's go through them one by one and at the same time performing certain operations on our circular linked list shown above.

So, let's say you want to start off by creating the first node in the list. The steps for this are:

1. Allocate memory for the node
2. Call linux Kernel's INIT_LIST_HEAD() function, passing it the address of the list element of your node. This function initializes the circular linked list. This means that the node is now the first element in the list. Since this is a doubly circular linked list, the node is also the last element in the list and the prev and next pointer of the list structure point to the node itself.

The code for above steps is given below:

/* Step 1
 * Declare the list and allocate memory 
 * for the first node
 */
struct circular_int_list *mylist;
mylist = (struct circular_int_list *) malloc(sizeof(struct circular_int_list));

/* Step 2
 * Call the INIT_LIST_HEAD() to initalize the list 
 */
INIT_LIST_HEAD(&(mylist->list));

The code for INIT_LIST_HEAD() is simple and is shown below:

void INIT_LIST_HEAD(struct list_head *list)
{
 list->next = list;
 list->prev = list;
}

Side Note: All the linux kernel code shown here can be found online and the relevant links are provided at the end of this post.

Now let's look at functions used for adding a new node to the list:
To add an new element to the list, list_add() function is provided. It's first argument is pointer to the new node that is to be added and second argument is pointer to the node in the list after which you want to add the new node. Point to note here is that you can provide any node in the list and the new node is going to be added after that node.
If you always provide the same node to insert after, you get insertion of the new nodes in stack fashion.

e.g.

list_add(&(newnode->list), &(mylist->list));

Implementation of list_add() function is given below:

void list_add(struct list_head *new, struct list_head *head)
{
 __list_add(new, head, head->next);
}

void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
 next->prev = new;
 new->next = next;
 new->prev = prev;
 prev->next = new;
}

There is also a function list_add_tail(). This inserts the new node just behind the head. Use this function if you want to implement a queue.

For deleting a node from the list, there is list_del() function. The only argument it needs is the pointer to the node which you want to remove from the list.

list_del(&(newnode->list));

Implementation of the list_del() function is given below:

void list_del(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
 entry->next = LIST_POISON1; 
 entry->prev = LIST_POISON2;
}

void __list_del(struct list_head * prev, struct list_head * next)
{
 next->prev = prev;
 prev->next = next;
}

LIST_POISON1 and LIST_POISON2 are non null pointers that would result in page-faults in case somebody tries to access them.

Linux kernel provides many different ways in which you can iterate over a given list. Let's look here at one of them: list_for_each_entry().

If I wanted to print integer values stored as information in the list I have defined above, here is how I would use the list_for_each_entry macro to traverse the list :

struct mylist *listnode;

list_for_each_entry(listnode,&mylist, list)
{
        printf("%d \n",listnode->info);
}

As you can see, the code above is clean and elegant.

The list_for_each_entry() macro is implemented as shown below:-

#define list_for_each_entry(pos, head, member)    \
 for (pos = list_entry((head)->next, typeof(*pos), member); \
      &pos->member != (head);  \
      pos = list_entry(pos->member.next, typeof(*pos), member))

#define list_entry(ptr, type, member) \
 container_of(ptr, type, member)

#define container_of(ptr, type, member) ({   \
 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
 (type *)( (char *)__mptr - offsetof(type,member) );})

list_entry() macro used above gives back the structure that contains the element given to it as its first argument.  It internally uses the container_of() macro.

These are just some of the many different operations that linux kernel allows on its circular linked list. For those who revel in reading code, I would greatly recommend going through the entire list file.

Linux kernel implementation of circular linked list seems to have been made in such a manner that the list structure and list operations themselves remain an abstraction don't meddle with the information stored in each node.
The generic nature allows for the same list structure to be used in different types of situations without ever changing how the list operations are done.
You can embed the list_head structure in any structure and you have got a linked list, a circular one at that !

Linked lists are widely used in Linux code. You would find a single structure containing multiple list_head structures, indicating that a single node is part of multiple linked lists. This is quite good, since the information resides at only one place in memory while it is part of multiple linked lists.

e.g. The task_struct structure in linux kernel, the structure that stores all the information of a process, contains multiple linked lists inside itself. The kernel itself uses one of these lists to manage different tasks.

struct task_struct 
{
        .
        .

        /*
         * List of tasks 
         */
 struct list_head tasks;

 /*
  * children/sibling forms the list of my natural children
  */
 struct list_head children; /* list of my children */
 struct list_head sibling;  /* linkage in my parent's children list */
        .
        .
        .
};

We have looked at circular linked lists - its uses and one of its most used implementations in the software world. To those who are interested, I would strongly recommend browsing linux kernel code to discover more.

References:

1. Code : Linux Kernel Code (version 3.9.8)
2. Book : Linux Kernel Development by Robert Love
3. Linked list Wikipedia Article