Chapter P4. Advanced C and programming techniques

This short chapter introduce algorithms and standard techniques to realize projects.

However, we also will cover here memory allocation and copy that is a fundamental preliminary step to getting start with this "advanced programming techniques".

Of course, we suppose that a normal or elementary programming techniques are well-know. For example we suppose that the reader may write algorithms for

• How to engine your car and go to the work.
• How to call home for a public phone.
• How to play a music CD on the local Linux system
• ... and other similar simple process that involves decisions (conditional).

 

Memory management

The computer works with memory. Actually it is also possible to work on PC with 512 MB or up to 2 GB RAM or more.

The Linux Operating System, using C may allocate structures to handle for example our Phone Database, or programs will allocate RAM to launch the Office program, etc ... memory is used everywhere.

The C Language on UNIX system is very stable and offer a better memory management from the first days.
 

The "malloc" and "calloc"

Note for example a malloc use in XFree.

   d = (DpyRec *) malloc(sizeof(DpyRec));
   if (d == NULL) return NULL;

XFree 4.2, also uses the calloc:

static int
tree_set(unsigned int **map, unsigned int i, unsigned int j)
{
    int s, c;

    if(i >= FONTENC_INVERSE_CODES)
        return FALSE;

    s = i / FONTENC_SEGMENT_SIZE;
    c = i % FONTENC_SEGMENT_SIZE;

    if(map[s] == NULL) {
        map[s] = calloc(FONTENC_SEGMENT_SIZE, sizeof(int));
        if(map[s] == NULL)
            return FALSE;
  }

    map[s][c] = j;
    return TRUE;
}
 

The calloc is more convenient because setup all the memory zone with zeros. The malloc instead does not apply this.

May be, that a library includes it own calloc function, like Xcalloc.

  if ((agentList = (AgentIdList)
       Xcalloc(*nAgents, (unsigned) sizeof(Agent))) == NULL)
    goto failed;

Both functions will use free to release the allocated memory. A wrong or superflous free may cause a bus error or other similar mistakes.

Now we will introduce an example about memory allocation, and when will be necessary.

To start the example, we will recover a previous example: structures.c

[root@ftosx1 Chap4]# more structures.c

typedef struct _student {
        char name[20];
        char address [50];
        int  id;
        int  age;
        char sex;
} student;
 

main ()
{
        student john;

        strcpy(john.name, "John Smith");
        strcpy(john.address, "1620 26th Street - Santa Monica");
        john.id = 42571;
        john.age = 18;
        john.sex = 'M';

        printf ("The data request is the following:\n\t%s\n\t%s\n\t%d\n\t%d\n\t%c\n", john.name, john.address, john.id, john.age, john.sex);

}
[root@ftosx1 Chap4]#

In this example, we declare a structure using a typeded struct and fill them with data. The program then print the structure values and exit.

In this case is not necessary to allocate memory because we are waiting with one element.

Instead, if we need to write or read the data from a file, will be necessary to allocate a memory structure for each Database record.

Of course we need to fix a maximum number of lines or records.

Therefore we modify the previous program to complete this task.

Because we will start reading an existent file, we will allocate a structure for each record. Therefore, we will have an array of structures.

The declaration for this array will be:

static student *db[MAX_DB];

Is convenient to have a separator for record components.

[root@ftosx1 Chap4]# more students.txt
John Smith     :1620 26th Street - Santa Monica:4257:18:M
Albert Einstein:6824 Genius Ave. - Princeton   :   2:78:M
Pamela Anderson:3412 Sepulveda Ave.            :   4:38:F
[root@ftosx1 Chap4]#

Now the code to allocate a structure for each record, read and print the content will be the following:

[root@ftosx1 Chap4]# more structures2.c

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

typedef struct _student {
        char name[20];
        char address [50];
        int  id;
        int  age;
        char sex;
} student;

// We fix a maximum number of records.
#define MAX_DB 100

static student *db[MAX_DB];

main ()
{
        FILE *fp;
        student john;
        char line[BUFSIZ], * tmp ;
        int i = 0;

        if (( fp = fopen ("students.txt", "r")) == NULL ) {
                printf ("Cannot open file");
                exit (1);
        }
 

    while (fgets(line, BUFSIZ, fp) != NULL) {

                if (i == MAX_DB) {
                                puts ("Maximum number of records reached");
                                break;
                }

                if ( (db[i] = (student *) malloc (sizeof(student))) == NULL) {
                                puts ("Impossible to allocate space for this record\n");
                                exit (1);
                }

           tmp = calloc (50, sizeof(char));

           tmp = (char *) strtok (line, ":");
           strcpy (db[i]->name, tmp);

           tmp = (char *) strtok (NULL, ":");
           strcpy (db[i]->address, tmp);

           tmp = (char *) strtok (NULL, ":");
           db[i]->id = atoi(tmp);

           tmp = (char *) strtok (NULL, ":");
           db[i]->age = atoi(tmp);

           tmp = (char *) strtok (NULL, ":");
           db[i]->sex = tmp[0] + '\0';

           printf ("The data readed is the following:\n\t%s\n\t%s\n\t%d\n\t%d\n\t%c\n", db[i]->name, db[i]->address, db[i]->id, db[i]->age, db[i]->sex);

          i++;
        }

        fclose (fp);

}
[root@ftosx1 Chap4]#

Compiling and executing we will have:

[root@ftosx1 Chap4]# gcc structures2.c -o structures2
[root@ftosx1 Chap4]# ./structures2
The data readed is the following:
        John Smith
        1620 26th Street - Santa Monica
        4257
        18
        M
The data readed is the following:
        Albert Einstein
        6824 Genius Ave. - Princeton
        2
        78
        M
The data readed is the following:
        Pamela Anderson
        3412 Sepulveda Ave.
        4
        38
        F
[root@ftosx1 Chap4]#

Note how the character is transformed.

Also note how we use a malloc and calloc to allocate memory.

The "memcpy"

For example, suppose that we want to save the information from the "db" array of structures to two array of structures. One for male data and one for female data.

Then, we will copy the db[i] ... for each record to a relative structure for male persons and another time for female persons.

The source is as follows:

[root@ftosx1 Chap4]# more structures3.c

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

typedef struct _student {
        char name[20];
        char address [50];
        int  id;
        int  age;
        char sex;
} student;

// We fix a maximum number of records.
#define MAX_DB 100

static student *db[MAX_DB];
static student *db_male[MAX_DB];
static student *db_female[MAX_DB];

main ()
{
        FILE *fp;
    char line[BUFSIZ], * tmp ;
        int i = 0;

        if (( fp = fopen ("students.txt", "r")) == NULL ) {
                printf ("Cannot open file");
                exit (1);
        }
 

    while (fgets(line, BUFSIZ, fp) != NULL) {

                if (i == MAX_DB) {
                                puts ("Maximum number of records reached");
                                break;
                }

                if ( (db[i] = (student *) malloc (sizeof(student))) == NULL) {
                                puts ("Impossible to allocate space for this record\n");
                                exit (1);
                }

                /* Now we allocate both temp_db to save male and female data */

                if ( (db_male[i] = (student *) malloc (sizeof(student))) == NULL) {
                                puts ("Impossible to allocate space for this record\n");
                                exit (1);
                }

                if ( (db_female[i] = (student *) malloc (sizeof(student))) == NULL) {
                                puts ("Impossible to allocate space for this record\n");
                                exit (1);
                }

           tmp = calloc (50, sizeof(char));

           tmp = (char *) strtok (line, ":");
           strcpy (db[i]->name, tmp);

           tmp = (char *) strtok (NULL, ":");
           strcpy (db[i]->address, tmp);

           tmp = (char *) strtok (NULL, ":");
           db[i]->id = atoi(tmp);

           tmp = (char *) strtok (NULL, ":");
           db[i]->age = atoi(tmp);

           tmp = (char *) strtok (NULL, ":");
           db[i]->sex = tmp[0] + '\0';

           if (db[i]->sex == 'M') { //is a male data
                memcpy (db_male[i], db[i], sizeof (student));

               puts ("This data is for a male person");

               printf ("The data readed is the following:\n\t%s\n\t%s\n\t%d\n\t%d\n\t%c\n", db_male[i]->name, db_male[i]->address, db_male[i]->id, db_male[i]->age, db_male[i]->s
ex);

           } else {
               memcpy (db_female[i], db[i], sizeof (student));
               puts ("This data is for a FEMALE person");

               printf ("The data readed is the following:\n\t%s\n\t%s\n\t%d\n\t%d\n\t%c\n", db_female[i]->name, db_female[i]->address, db_female[i]->id, db_female[i]->age, db_fe
male[i]->sex);
           }
 

           i++;
        }

        fclose (fp);
 

}

Compiling and running we will get the expected output!

[root@ftosx1 Chap4]# gcc memcpy.c -o memcpy
[root@ftosx1 Chap4]# ./memcpy
This data is for a male person
The data readed is the following:
        John Smith
        1620 26th Street - Santa Monica
        4257
        18
        M
This data is for a male person
The data readed is the following:
        Albert Einstein
        6824 Genius Ave. - Princeton
        2
        78
        M
This data is for a FEMALE person
The data readed is the following:
        Pamela Anderson
        3412 Sepulveda Ave.
        4
        38
        F
[root@ftosx1 Chap4]#

There are also another function

Programming techniques

• Sorting
• Searching
• Queue

Algorithms for Sorting

To apply this classical algorithms in C programs, we will start the explanation.

We will use an array that we can fill from the command line. We fix 100 elements as maximum. When we want to order the elements we will press (Ctrl-D = EOF).
 

Selection

We present here the algorithm.
 

[root@ftosx1 Chap4]# more sort1.c

#include <stdio.h>

#define MAX 100

mysort (int a[], int N)
{
        int i, j, min, t;

        for (i = 1; i < N; i++) {
              min = i;
              for (j = i+1; j <= N; j++)
                   if (a[j] < a[min] )
                        min = j;
              t = a[min]; a[min] = a[i]; a[i] = t;

        }

}

main ()
{
        int N, i, a[MAX+1]; // this happens because arrays start from 0.
        N = 0;
        while (scanf ("%d", &a[N+1]) != EOF)
                        N++;
        a[0] = 0;

        // Now we call the function.
        mysort (a, N);

        for (i = 1; i <= N; i++)
                        printf ("%d ", a[i]);
        printf ("\n");

        exit (1);
}

[root@ftosx1 Chap4]#

Running we will have.

[root@ftosx1 Chap4]# ./sort1
9 3 3 2 3 7 2 13 54 31 42
2 2 3 3 3 7 9 13 31 42 54
[root@ftosx1 Chap4]#

This example is quite simple. Now, we will introduce the insertion method.

Insertion

The algorithm here is the following:

insertion (int a[], int N)
{
    int i, j, v;
    for (i = 2; i < = N; i++)
    {
        v = a[i];
        j = i;
        while (a[j-1] < v) {
            a[j] = a[j-1]; j--;
        }
    }
}

The element being considered is inserted merely by moving larger elements one position to the right and then inserting the elements in vacant positions.
 

Bubble

The code is as follows:

buble (int a[], int N)
{
    int i, j, t;
    for (i= N; i >= 1; i--) {
        for (j = 2; j <= i; j++) {
             t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }
    }
}

This method moves the largest element to the top of the list exchanging elements, then the second, etc.

ShellSort

We implement this method as follows:

shellsort (int a[], int N)
{
    int i, j, h, v;
    for (h = 1; h <= N/9; h = 3*h + 1);
    for (; h > 0; h /=3)
    for (i = h + 1; i <= N; i+= 1)
    {
        v = a[i];
        j = i;
        while (j > h && a[j-h] > v) {
            a [j] = a[j-h];
            j -= h;
            a[j] = v;
        }
    }
}

Where we can get the numbers "3", etc ? These numbers become available from test and theorems about the number of permutations to gain the solution. These results are not covered in this training.

QuickSort

Here we have the implementation:

quicksort (int a[], int l, int r)
{
    int v, i, j, t;
    if (r > 1)
    {
        v = a[r];
        i = l - 1;
        j = r;
        for (;;) {
            while (a[++i] < v);
            while (a[--j]) > v);
            if (i >=j )
                break;
            t = a[i]; a[i] = a[j]; a[r] = t;
        }
        t = a[i]; a[i] = a[r]; a[r] = t;
        quicksort (a, l, i-1);
        quicksort (a, l+1, r);
    }
}

There are also an implementation in the C Library.

Algorithms for Searching

Here we need to get (or retrieve) information from a large ammount of data, as a Database. Is normal to think that the information is divided in records and we can search info with a key.

Read the Chapter B29. A tour on Linux DataBase  for a formal introduction about Database, rows and columns.

The goal for this chapter is to introduce the method as well an algorithm for it.

The searching algorithms we will introduce here are the following:

• Sequential Search
• List Search and
• Binary Search

Sequential Search

static struct node {
    int key;
    int info;
}
static struct node a[maxN+1];

static int N;

seqinitialize()
{
    N = 0;
}

int seqsearch (int v)
{
    int x = N + 1;
    a[0].key = v;
    a[0].info = -1;
    while (v != a[--x].key)
        ;
    return a[x].info;
}

seqinsert (int , int info)
{
    a[++N].key = v;
    a[N].info = info;
}
 

Note that we here uses an abstract data type where the integers keys (key) and info are used as the normal information. Of course, this is a normal example. For more complicated data, the structure must be changed.

Please also note that we reproduce the element if the key are wrong.

List Search

One advantage is that it becomes easy to keep list sorted:

static struct node
{
    int key, info;
    struct node *next;
}

static struct node *head, *z;

listinitialize ()
{
    head = (struct node *) malloc (sizeof *head);
    z = (structure node *) malloc (sizeof *z);
    head ->next = z;
    z->next;
    z->info = -1;
}

int listsearch (int v)
{
    struct node *t = head;
    z->key = v;
    while (v > t->key)
        t = t->next;
    if (v != t-key)
        return z->info;
    return t->info;
}

Note that also in this case we insert data.

Binary Search

The code is the following:

int binsearch (int v)
{
    int l = 1;
    int r = N;
    int x;

    while (r>=1) {
        x = (l+r)/2;
        if (v < a[x].key)
            r = x-1;
        else
            l = x +1;
    return -1;
}

To find if a given key v is in the table, first compare it with element at the middle position. If v is smaller, then it must be in first half, no otherwise. Then, apply this method recursively.

Queues

Therefore a queue is this. A list of objects with precedence. From this point of view there are different methods to handle the objects. The most two common are FIFO and LILO. FIFO stand for First-In-First-Out, and the second is LILO, Last-In-Last-Out. There are also variation following this schema.

We will list here the code to implement a queue.

#define max 100
static int queue[max+1], head, tail;

put (int v)
{
    queue[tail++] = v;
    if (tail > max)
        tail = 0;
}

int get ()
{
    int t = queue[head++];
    if (head > max)
        head = 0;
    return t;
}

queueinit ()
{
    head = 0;
    tail = 0;
}

int queueempty ()
{
    return head == tail;
}

Other more simple examples are available to implement a stack.

Exercises

1. Check how the command "cd -" back to the previous (pop) directory stack.

Test

1. What is the C function allocate memory ?
2. List three C functions to allocate memory.
3. What is the C function to free the allocated space ?
4. What is the C function to copy two structures ?
5. Is possible that some development libraries includes its own Malloc/Calloc functions ?
6. What is the "memcpy" role ?
7. What does the "bcopy" function ?
8. What is wrong in the examples for malloc and memcpy ?
9. List the most three important advanced techniques.
10. List four possible method of sorting.
11. Describe the method of sort called "selection".
12. Are there a C function for sorting data ?
13. List three method of searching.
14. Why is necessary to insert data in search algorithms ?
15. What is FIFO ? What is LILO ?

Check the Interactive Exam Cram Programming: 

Internet Resources for this Chapter.

• http://www.ibiblio.org/pub/Linux/devel/lang/c/