≡ Practical Programming David Bouchet
Practical Work #5

Pointers

Submission

Due Date

By Friday 30 November 2018 23:42

Directory Hierarchy

Create your git repository (replace john.smith by your own login). 

$ git clone git@git.cri.epita.net:p/2022-spe-tp/tp05-john.smith

It must contain the following files and directories:

The AUTHORS file must contain the following information.

AUTHORS
First Name
Family Name
Login
Email Address

The last character of your AUTHORS file must be a newline character.

For instance:

AUTHORS
$ cat AUTHORS
John
Smith
john.smith
john.smith@epita.fr
$ # Command prompt ready for the next command...

Be careful, if you do not follow all the given instructions, no point will be given to your answers.

Warm-up Exercices

Introduction

In this part, you will complete some source files (with the .c extension). Each of them must be compiled with the instruction below (replace source.c by the name of your source file). 

$ gcc -Wall -Wextra source.c

No makefile is required.

Basic Pointers

Swapping Variables

Write a function that swaps the contents of two variables. To do so, complete the following file.

swap.c
# include <stdio.h>

void swap(int *a, int *b)
{
    // TODO
}

int main()
{
    int a = 1;
    int b = 2;

    printf("a = %d\n", a);
    printf("b = %d\n", b);

    swap(&a, &b);

    printf("a = %d\n", a);
    printf("b = %d\n", b);

    return 0;
}

Then, compile it and run it. The expected result is as follows: 

$ gcc -Wall -Wextra swap.c
$ ./a.out
a = 1
b = 2
a = 2
b = 1

Sum of Divisors

Write the following function: 

unsigned long sum_of_divisors(unsigned long n, size_t *count);

To do so, complete the following file.

sum_of_divisors.c
# include <stdio.h>

unsigned long sum_of_divisors(unsigned long n, size_t *count)
{
    // TODO
}

int main()
{
    unsigned long x;
    unsigned long sum;
    size_t count;

    x = 28;
    sum = sum_of_divisors(x, &count);
    printf("x = %lu\n", x);
    printf("sum   = %lu\n", sum);
    printf("count = %zu\n\n", count);

    x = 100;
    sum = sum_of_divisors(x, &count);
    printf("x = %lu\n", x);
    printf("sum   = %lu\n", sum);
    printf("count = %zu\n", count);
}

Then, compile it and run it. The expected result is as follows: 

$ gcc -Wall -Wextra sum_of_divisors.c
$ ./a.out
x = 28
sum   = 28
count = 5

x = 100
sum   = 117
count = 8

Pointer Arithmetic

For all the functions in this section, the begin variable points to the beginning of an array and the end variable points just after the array.

Some hints:

Of course, when iterating over arrays, do not use index variables. Use pointers only. For instance: 

for (p = begin; p < end; p++)
  *p = 0;

Complete the following file.

arithmetic.c
# include <stdio.h>

int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int *begin = arr;
int *end = arr + 10;
int copy[10] = { 0, };

#define PRINT(a) \
for (size_t i = 0; i < size; i++)\
    if (i != size - 1)\
        printf("%2i, ", *(a + i));\
    else\
        printf("%2i]\n", *(a + i))\

// Swap the contents of two variables.
void swap(int* a, int* b)
{
    // TODO
    // (Just copy your code from the previous section.)
}

// Return the sum of the array from 'begin' to 'end'.
int array_sum(int *begin, int *end)
{
    // TODO
}

// Reverse the array from 'begin' to 'end'.
void array_reverse(int *begin, int *end)
{
    // TODO
}

// Copy the array from 'begin' to 'end' into 'dst'.
// The dst array must be large enough.
// The two arrays do not overlap.
void array_copy(int *dst, int *begin, int *end)
{
    // TODO
}

// Shift the array from 'begin' to 'end' by one position to the right.
// The leftmost value will not change.
// The rightmost value will be lost.
// For instance:
// - Before: 1 2 3 4 5
// - After:  1 1 2 3 4
void array_rshift(int *begin, int *end)
{
    // TODO
}

int main()
{
    size_t size = end - begin;

    printf("Initial arr  = [");
    PRINT(arr);

    int sum = array_sum(begin, end);
    printf("sum          = %2i\n", sum);

    array_reverse(begin, end);
    printf("Reversed arr = [");
    PRINT(arr);

    array_copy(copy, begin, end);
    printf("Copy         = [");
    PRINT(copy);

    array_rshift(begin, end);
    array_rshift(begin, end);
    array_rshift(begin, end);
    printf("Shifted arr  = [");
    PRINT(arr);
}

Then, compile it and run it. The expected result is as follows: 

$ gcc -Wall -Wextra arithmetic.c
$ ./a.out
Initial arr  = [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10]
sum          = 55
Reversed arr = [10,  9,  8,  7,  6,  5,  4,  3,  2,  1]
Copy         = [10,  9,  8,  7,  6,  5,  4,  3,  2,  1]
Shifted arr  = [10, 10, 10, 10,  9,  8,  7,  6,  5,  4]

Arrays

Provided Files

The Makefile

Be careful, some source files must exist even if empty.

Makefile
# Makefile

CC=gcc -fsanitize=address
CPPFLAGS= -MMD -D_XOPEN_SOURCE=500
CFLAGS= -Wall -Wextra -std=c99 -O2
LDFLAGS=
LDLIBS=

# You should at least create the "insert_sort.c"
# and "insert_sort.h" files in order to compile.
# (These files can be empty.)

SRC= insert_sort.c helper.c main.c
OBJ= ${SRC:.c=.o}
DEP= ${SRC:.c=.d}

all: main

-include ${DEP}

main: ${OBJ}

clean:
	rm -f ${OBJ} ${DEP} main

# END

The helper.h File

helper.h
# ifndef _HELPER_H
# define _HELPER_H

# include <stdlib.h>
# include <time.h>

void swap(int *a, int *b);
void array_print(int *begin, int *end);
int array_is_sorted(int *begin, int *end);
void array_sorted_fill(int *begin, int *end);
void array_random_fill(int *begin, int *end);

static inline
double time_gdiff(struct timespec t0, struct timespec t1)
{
  double s = t1.tv_sec - t0.tv_sec;
  return s + (t1.tv_nsec - t0.tv_nsec) * 1e-9;
}

typedef void (*sort_fun)(int*, int*);

void bench_sort(int *begin, int *end, sort_fun sort, const char *msg);

# endif

The insert_sort.h File

insert_sort.h
# ifndef _INSERT_SORT_H_
# define _INSERT_SORT_H_

# include <stdlib.h>
# include <string.h>

# include "helper.h"

void array_insert_sort(int *begin, int *end);
void array_insert_sort_bin(int *begin, int *end);

# endif

The Main File

You can use the following main file (you do not have to) in order to test your code. You can pass the size of the array as a parameter (the default size is 16). Also, try larger sizes (e.g. 32,768 or 65,536) and observe the differences in performance.

Uncomment some lines of this file according to the functions you want to test. (Do not print an array if it is too large.)

main.c
#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "helper.h"
#include "insert_sort.h"

#define DEFAULT_SIZE 16

int main(int argc, char *argv[])
{
    size_t len = DEFAULT_SIZE;

    srandom(time(NULL));
    if (argc > 1)
        len = strtoul(argv[1], NULL, 10);

    int *array = calloc(len, sizeof (int));
    int *copy = calloc(len, sizeof (int));
    int *begin = array, *end = array + len;

    // Fill the array with sorted values.
    array_sorted_fill(begin, end);

    // Test the algorithms on a presorted array.
    // -----------------------------------------------------------------------
    array_print(begin, end);
    bench_sort(begin, end, array_insert_sort, "insert_sort (sorted)");
    array_print(begin, end);
    bench_sort(begin, end, array_insert_sort_bin, "insert_sort_bin (sorted)");
    array_print(begin, end);

    // Fill the array with random values
    // and copy it in order to test the algorithms on the same array.
    // -----------------------------------------------------------------------
    array_random_fill(begin, end);
    memcpy(copy, begin, len * sizeof (int));

    // Test the algorithms on a random array.
    // -----------------------------------------------------------------------
    array_print(begin, end);
    bench_sort(begin, end, array_insert_sort, "insert_sort (random)");
    array_print(begin, end);
    memcpy(begin, copy, len * sizeof (int));
    array_print(begin, end);
    bench_sort(begin, end, array_insert_sort_bin, "insert_sort_bin (random)");
    array_print(begin, end);

    // free memory
    free(array);
    free(copy);

    return 0;
}

Helper Functions

Complete the helper.c file.

helper.c
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "helper.h"

// Swap the contents of two variables.
void swap(int *a, int *b)
{
    // TODO
    // (Just copy your code from the previous section.)
}

// Print an array.
void array_print(int *begin, int *end)
{
    for (int line = 0; begin != end; ++begin)
    {
        if (line > 72)
        {
            printf("|`|\n");
            line = 0;
        }

        line += printf("| %4d ", *begin);
    }

    printf("|\n");
}

// Test if an array is sorted.
// If the array is sorted, return true (1).
// Otherwise, return false (0).
int array_is_sorted(int *begin, int *end)
{
    // TODO
}

// Fill an array with sorted values.
void array_sorted_fill(int *begin, int *end)
{
    for (int i = 0; begin != end; ++begin, ++i)
        *begin = i;
}

// Fill an array with random values.
void array_random_fill(int *begin, int *end)
{
    for (; begin != end; ++begin)
        *begin = random() % 10000;
}

// Benchmark an algorithm.
void bench_sort(int *begin, int *end, sort_fun sort, const char *msg)
{
    struct timespec t0, t1;

    clock_gettime(CLOCK_MONOTONIC, &t0);
    sort(begin, end);
    clock_gettime(CLOCK_MONOTONIC, &t1);

    printf("%s:    \t%g\n", msg, time_gdiff(t0, t1));
    assert(array_is_sorted(begin, end));
}

Insertion Sort

You will write an insertion sort. The algorithm is pretty simple. First, you write an insert() function that inserts an element at its right place in a sorted array. Then, you take each element one by one and insert it in the first part of the array. 

insert_sort(array):
    for i in range(len(array)):
        insert(array[:i], array[i])

Inserting is also a pretty straightforward algorithm. Find where to insert the value, shift the right side of the array by one cell to the right and write the value. Here is a plain version of the algorithm (note that your array must have an extra cell). 

insert(array, x):
    i = len(array)
    array.append(None)
    while i > 0 && x < array[i - 1]:
        array[i] = array[i - 1]
        i = i - 1
  array[i] = x

You can also use a faster algorithm by using the binary search. 

insert_bin(x, array):
    i = binary_search(x, array)
    j = len(array)
    array.append(None)
    while j > i:
        array[j] = array[j - 1]
        j = j - 1
    array[i] = x

Remember, we always return the position where the element should be located. For shifting we can also use the memmove() function.

Create an insert_sort.c file with the required headers and write the two following functions: 

// Insertion using the plain algorithm.
void array_insert(int *begin, int *end, int x);

// Insertion using the binary-search algorithm.
void array_insert_bin(int *begin, int *end, int x);

Try and test these two functions on your own. When this is done, you can implement the insertion sort (two versions again). 

// Insertion sort using plain method.
void array_insert_sort(int *begin, int *end);

// Insertion sort using binary search.
void array_insert_sort_bin(int *begin, int *end);

Finally, you can either test the functions on your own or use the provided main file (see above).

Strings

Introduction

In this section, you will manipulate strings by using pointers only. To do so, you will write some commonly used functions.

Obviously, you will not use the array notation with index variables when iterating over arrays. You must use the pointer notation only.

In the C language, a string is no more than an array of characters. The end of a string is denoted by a special character, which is called the NULL character. The ASCII code of the NULL character is zero.

The following code prints the numerical values (e.g. the ASCII codes) of some characters. 

# include <stdio.h>

int main()
{
    char s[] = "abcdefghijklmnopqrstuvwxyz";

    for (size_t i = 0; i < sizeof(s); i++)
        printf("s[%2zu] = 0x%02x - '%c'\n", i, s[i], s[i]);

    return 0;
}

Its output is as follows: 

s[ 0] = 0x61 - 'a'
s[ 1] = 0x62 - 'b'
s[ 2] = 0x63 - 'c'
s[ 3] = 0x64 - 'd'
s[ 4] = 0x65 - 'e'
s[ 5] = 0x66 - 'f'
s[ 6] = 0x67 - 'g'
s[ 7] = 0x68 - 'h'
s[ 8] = 0x69 - 'i'
s[ 9] = 0x6a - 'j'
s[10] = 0x6b - 'k'
s[11] = 0x6c - 'l'
s[12] = 0x6d - 'm'
s[13] = 0x6e - 'n'
s[14] = 0x6f - 'o'
s[15] = 0x70 - 'p'
s[16] = 0x71 - 'q'
s[17] = 0x72 - 'r'
s[18] = 0x73 - 's'
s[19] = 0x74 - 't'
s[20] = 0x75 - 'u'
s[21] = 0x76 - 'v'
s[22] = 0x77 - 'w'
s[23] = 0x78 - 'x'
s[24] = 0x79 - 'y'
s[25] = 0x7a - 'z'
s[26] = 0x00 - ''

Lengths of Strings

In the above example, we get the length of the array by using sizeof() because the array was static.

Let us execute this other example. 

# include <stdio.h>

int main()
{
    char s1[] = "abcdefghijklmnopqrstuvwxyz";   // Array notation.
    char *s2  = "abcdefghijklmnopqrstuvwxyz";   // Pointer notation.

    printf("sizeof(s1) = %zu\n", sizeof (s1));
    printf("sizeof(s2) = %zu\n", sizeof (s2));

    return 0;
}

Its output is as follows: 

sizeof(s1) = 27
sizeof(s2) = 8

When we use a pointer, the sizeof() operator returns the size of the pointer (not the size of the array). So, if we want to know the size of a string, we have to count each character up to the NULL character. That is the purpose of the strlen() function of the standard library. Note that the length of a string does not include the NULL character.

This function is easy to write. Write the following function that has the same behavior as the one of the standard library (have a look at its man page). 

size_t mystrlen(char *s);

You will test your function in the next section.

Copying Strings

Copying strings is another very common operation on strings. The standard library provides two functions for this purpose: strcpy() and strncpy(). We will focus on the second one. Read its man page and write the following function that has exactly the same behavior. 

char *mystrncpy(char *dst, const char *src, size_t len);

Complete the following code and execute it to test your functions.

mystrncpy.c
#include <stdio.h>
#include <stdlib.h>

size_t mystrlen(char *s)
{
    // TODO
}

char *mystrncpy(char *dst, char *src, size_t len)
{
    // TODO
}

void print_str_as_array(char *s, size_t len)
{
    for (size_t i = 0; i < len; i++)
        printf("0x%02x ", s[i]);

    printf("\n");
}

int main()
{
    char src[] = "abc";
    char *dst = malloc(2 * sizeof(src) * sizeof(char));

    // Fill dst with 0x7f.
    for (char *cur = dst; cur < dst + 2 * sizeof(src); cur++)
        *cur = 0x7f;

    // Print dst and src.
    printf("src = ");
    print_str_as_array(src, sizeof(src));
    printf("dst = ");
    print_str_as_array(dst, 2 * sizeof(src));

    // Copy exactly the length of src.
    mystrncpy(dst, src, mystrlen(src));
    printf("\ndst = ");
    print_str_as_array(dst, 2 * sizeof(src));

    // Fill dst with 0x7f.
    for (char *cur = dst; cur < dst + 2 * sizeof(src); cur++)
        *cur = 0x7f;

    // Copy the length of src + 1.
    mystrncpy(dst, src, mystrlen(src) + 1);
    printf("\ndst = ");
    print_str_as_array(dst, 2 * sizeof(src));

    // Fill dst with 0x7f.
    for (char *cur = dst; cur < dst + 2 * sizeof(src); cur++)
        *cur = 0x7f;

    // Copy the size of dst.
    mystrncpy(dst, src, 2 * sizeof(src));
    printf("\ndst = ");
    print_str_as_array(dst, 2 * sizeof(src));

    // Fill dst with 0x7f.
    for (char *cur = dst; cur < dst + 2 * sizeof(src); cur++)
        *cur = 0x7f;

    free(dst);
    return 0;
}

The expected result is as follows: 

$ gcc -Wall -Wextra mystrncpy.c
$ ./a.out
src = 0x61 0x62 0x63 0x00
dst = 0x7f 0x7f 0x7f 0x7f 0x7f 0x7f 0x7f 0x7f

dst = 0x61 0x62 0x63 0x7f 0x7f 0x7f 0x7f 0x7f

dst = 0x61 0x62 0x63 0x00 0x7f 0x7f 0x7f 0x7f

dst = 0x61 0x62 0x63 0x00 0x00 0x00 0x00 0x00