20171016:Practical:C:Pointers

Introduction/Assignments

This week tutorial will focus on pointers and pointers arithmetics.

• S3: It is due on Monday, October 23, 2017 at 2pm
• S3#: It is due on Friday, March 30, 2018 at 2pm (this session spans across two weeks).

The tutorial directory (in your GIT) will have the following form:

• 20171016_pointers/
  • arrays/
  • strings/

See the corresponding section for inner content. The first exercises section is a warm-up: it's only training for you but some functions maybe useful in later sections.

This session is long, on purpose.

Warm-up

This section lists a series of small basic exercise on pointers and pointers arithmetics, they are not part of the assignments but will help you grasp the idea of using pointers arithmetics for array manipulation.

Basic Pointers

swap

Implement the following function:

/* swap(a, b) exchange pointed content between a and b
void swap(int *a, int *b);

You can test your code with following program:

# include <stdio.h>
# include <stdlib.h>
 
int main(void)
{
  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;
}

Summing and counting

Implement the following function:

/* sum_of_divisors(x, count) returns the sum of divisors of x  *
 * including 1 but not x.                                      *
 * When returning, *count must contains the number of divisors */
int sum_of_divisors(int x, size_t *count);

This function computes the sum of divisors in the half-open range [1, x) (1 included, x excluded.)

It also use the pointer counter, that should points to a size_t variable (unsigned long int), to returns the number of divisors encountered.

A possible call for this function look like this:

  int x = 28;   // just an example of value
  size_t count; // you'll probably initialize it in your function
  int res;
  res = sum_of_divisors(x, &count);
  printf("res = %d\n", res);
  printf("count = %zu\n", count);

Pointer arithmetics

REAL PROGRAMMERS use pointer arithmetics, brackets are for the weak !

Everything is in the subtitle, let's play with arrays without arrays …

In all the following functions the parameters begin is a pointer to the beginning of the array and end is pointing just after the array.

Some hints:

• the size of the array: end - begin
• accessing the element at index i: *(begin + i)
• first element of the array: *begin
• last element of the array: *(end - 1)
• pointer to the mid-point in the array: begin + (end - begin) / 2
• moving begin to the next cell: ++begin

Of course, when iterating over the array, you won't use an index variable, only pointers, like in the following example (put 0 in all cells:

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

In order to test your functions, you can use static arrays:

int array[10] = {1,2,3,4,5,6,7,8,9,10}; // an example of array of size 10
int *begin = array;
int *end = begin + 10; // 10 is the size of array, of course

Sum of cells

Implement the following function:

/* array_sum(begin, end) returns the sum of integer between begin and end */
int array_sum(int *begin, int *end);

Array reverse

Implement the following function:

/* array_reverse(begin, end) reverse the array in place */
void array_reverse(int *begin, int *end);

Array copy

Implement the following function:

/* array_copy(dst, begin, end): non overlapping copy */
void array_copy(int *dst, int *begin, int *end);

dst is a pointer to an area with at least as much space as the array between begin and end. The two arrays won't overlap.

You can test your code like this:

int array[] = {1,2,3,4,5,6,7,8,9,10};
int *begin = array;
int *end = begin + 10;
int copy[10] = {0,}; // an array full of 0
array_copy(copy, begin, end);

Array right shift

Implement the following function:

/* array_rshift(begin, end) shift content to [begin+1, end+1) */
/* real array size must be at least end - begin + 1           */
/* *end must be valid, *begin is unchanged                    */
void array_rshift(int *begin, int *end);

Shift (moves array content) by one cell to the right. As the comment state, you're supposed to have at least one integer available after the end of the array (that is end must be a valid pointer). When shifting, the first cell won't change.

Array before shift:

index	0	1	2	3	4
content	1	2	3	4

Array after shift:

index	0	1	2	3	4
content	1	1	2	3	4

Arrays

 This section must be in the directory: 20171016_pointers/arrays

Provided code

helper.h: describes some useful functions, see next section for implementation.

/* helper.h: helper functions */
 
# ifndef EPITA_IP_ARRAY_HELPER_H_
# define EPITA_IP_ARRAY_HELPER_H_
 
# define _XOPEN_SOURCE 500
 
# include <stdlib.h>
# include <time.h>
 
/* swap(a,b): swap memory location content */
void swap(int *a, int *b);
 
/* array_print(begin, end) print integer array */
/* with a fixed padding of 4 chars             */
void array_print(int *begin, int *end);
 
/* array_is_sorted(begin, end): test if array is sorted */
int array_is_sorted(int *begin, int *end);
 
/* array_random_fill(begin, end) */
void array_random_fill(int *begin, int *end);
 
/* inlined code, all is ok */
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 /* EPITA_IP_ARRAY_HELPER_H_ */

Makefile: in order to build your code, note that the files for the exercises code must exist (even if empty.)

# Makefile
 
CC=gcc -fsanitize=address
CPPFLAGS= -MMD -D_XOPEN_SOURCE=500
CFLAGS= -Wall -Wextra -std=c99 -O2
LDFLAGS=
LDLIBS=
 
# you should at least create empty file insert_sort.c and quick_sort.c in
# order to compile
 
SRC= insert_sort.c helper.c quick_sort.c main_tests.c
OBJ= ${SRC:.c=.o}
DEP= ${SRC:.c=.d}
 
all:
 
-include ${DEP}
 
main_tests: ${OBJ}
 
clean:
	rm -f ${OBJ} ${DEP} main_tests
 
# END

main_tests.c: a template file for testing, you'll fill it with test code for the next exercises.

/* main_tests.c: testing your code */
 
# define _XOPEN_SOURCE 500
 
# 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"
# include "quick_sort.h"
 
 
int main(int argc, char *argv[])
{
  srandom(time(NULL));
  // default to length = 16
  size_t len = 16;
  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;
 
  // a sorted array for basic tests
  for (int *cur = begin + 1; cur < end; ++cur)
    *cur = *(cur - 1) + 1;
 
  /* use bench_sort to test and bench sort algorithms on presorted array */
 
  // random fill the array
  // copy in order to test sorting algorithm on the same array
  array_random_fill(begin, end);
  memcpy(copy, begin, len * sizeof (int));
 
  /* use bench_sort to test and bench sort algorithms on random array */
 
  // free memory
  free(array);
  free(copy);
  return 0;
}

Helper functions

Here is the file helper.c some of the functions have been stripped, fix them !

/* helper's functions */
 
# define _XOPEN_SOURCE 500
 
# include <assert.h>
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
 
# include "helper.h"
 
/* swap(a,b): swap memory location content */
void swap(int *a, int *b)
{
  // FIX ME
}
 
/* array_print(begin, end) print integer array */
/* with a fixed padding of 4 chars             */
void array_print(int *begin, int *end)
{
  int line = 0;
  for (; begin != end; ++begin) {
    if (line > 72) {
      printf("|`|\n");
      line = 0;
    }
    line += printf("| %4d ", *begin);
  }
  printf("|\n");
}
 
/* array_is_sorted(begin, end): test if array is sorted */
int array_is_sorted(int *begin, int *end)
{
  // FIX ME
}
 
/* array_sorted_fill(begin, end) */
void array_sorted_fill(int *begin, int *end)
{
  for (int i = 0; begin != end; ++begin, ++i)
    *begin = i;
}
 
/* array_random_fill(begin, end) */
void array_random_fill(int *begin, int *end)
{
  for (; begin != end; ++begin)
    *begin = random() % 10000;
}
 
 
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));
}

Insert Sort

The purpose here is to implement an insertion sort. The algorithm is pretty simple, you first implement an insert function that insert an element at its 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])

As you can see, all the work is in insert. Inserting is also a pretty straightforward algorithm: find where to insert, shift the right side of the array by one cell to the right and put the value. The classic naive version look like this (note: 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

Since comparison is at least as expensive as assigning cells, it can be interesting to find the insertion position using a faster algorithm, and we've already done that: 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

So we got the binary search (remember, we always return the position where the element should be), for shifting we can also use memmove(3) (see the man page for details and header.)

• Create a file insert_sort.c, include required headers and implement the following functions:

// insert using the naive algo
void array_insert(int *begin, int *end, int x);
 
// insert using binary search
void array_insert_bin(int *begin, int *end, int x);

Once you got your insertion (try to test it on your own), you can implement the insertion sort (two versions again).

• Complete the file insert_sort.c with the following functions:

// insertion sort using naive method
void array_insert_sort(int *begin, int *end);
 
// insertion sort using binary search
void array_insert_sort_bin(int *begin, int *end);

Here is the header insert_sort.h file for this question:

/* insert_sort.h : implementing insert sort */
 
# ifndef EPITA_IP_INSERT_SORT_H_
# define EPITA_IP_INSERT_SORT_H_
 
# include <stdlib.h>
# include <string.h>
 
# include "helper.h"
 
/*
 * insert sort *
 */
 
void array_insert_sort(int *begin, int *end);
 
void array_insert_sort_bin(int *begin, int *end);
 
# endif /* EPITA_IP_INSERT_SORT_H_ */

Testing you code: in the file main_tests.c you have a template for testing your code. The provided code creates an array (with the corresponding begin and end for convenience). The function bench_sort can be used this way:

  bench_sort(begin, end, array_insert_sort, "insert sort");

In the second part, in order to compare sorting algorithm using the same random array each time, we should make a copy (already in the template code) of the array, then you can just restore the array after sorting it.

  bench_sort(begin, end, array_insert_sort, "insert sort");
  // restore array
  memcpy(begin, copy, len * sizeof (int));

Quick Sort

Now let's write a better sorting algorithm: quick sort !

Here is the quick sort algorithm:

partition(array, begin, end):
  pivot = begin + (end - begin) / 2
  pval = array[pivot]
  swap(array[pivot], array[end - 1])
  pivot = begin
  for i in range(begin, end):
    if array[i] < pval:
      swap(array[pivot], array[i])
      pivot += 1
  swap(array[pivot], array[end - 1])
  return pivot

quick_sort(array, begin, end):
  if end - begin > 1:
    pivot = partition(array, begin, end)
    quick_sort(array, begin, pivot)
    quick_sort(array, pivot + 1, end)

In addition to quick sort, we add a tiny optimization: hybrid_sort (bad name sorry) just check if the array is sorted before running quick sort.

• Complete the file quick_sort.c:

/* quick_sort.c : simple quick sort implementation */
 
# include <stdlib.h>
 
# include "helper.h"
# include "quick_sort.h"
 
int* partition(int *begin, int *end)
{
  // FIX ME
}
 
void quick_sort(int *begin, int *end)
{
  // FIX ME
}
 
void hybrid_sort(int *begin, int *end)
{
  if (end - begin < 2 || array_is_sorted(begin, end))
    return;
  quick_sort(begin, end);
}

And here is the corresponding header:

/* quick_sort.h : simple quick sort implementation */
 
# ifndef EPITA_IP_QUICK_SORT_H_
# define EPITA_IP_QUICK_SORT_H_
 
# include <stdlib.h>
 
void quick_sort(int *begin, int *end);
 
void hybrid_sort(int *begin, int *end);
 
# endif /* EPITA_IP_QUICK_SORT_H_ */

You can now test your code like you've done for the insertion sort. The provided code does some wall-clock benchmark, observe the variation in performances between each sorting algorithm, especially for big size (try 32768 or 65536 … )

Strings

 This section must be in the directory: 20171016_pointers/strings

As an introduction to string manipulation, you'll implement some classical functions.

First, a string in C, is just an array of characters and the end of the string is marked by a special character. This special character has the ASCII code 0 (or the character value '\0'.)

This small code let us see the content (as ASCII code) of a string:

/* print_string.c */
 
# include <stdio.h>
# include <stdlib.h>
 
int main() {
  // a simple static string
  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;
}

If we run it, we obtain:

shell> ls
Makefile  print_string.c
shell> make print_string
gcc -Wall -Wextra -pedantic -std=c99 -O2    print_string.c   -o print_string
shell> ./print_string 
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 - ''
shell>

Note: we get the length of the array of string using sizeof because s is a static local array, that doesn't work in the general case.

Computing the length of a string

In the previous example, we use sizeof to get the length of a string, but, as noted, it only works because our string was a static array, take a look at the following code:

/* string_len.c */
 
# include <stdio.h>
# include <stdlib.h>
 
int main() {
  char *s = "abcdefghijklmnopqrstuvwxyz";
  printf("sizeof(s) = %zu\n", sizeof (s));
  return 0;
}

And now run it:

shell> make string_len
gcc -Wall -Wextra -pedantic -std=c99 -O2    string_len.c   -o string_len
shell> ./string_len
sizeof(s) = 8
shell>

So, if we want the length of the string, we need to find the 0 at the end of it. That's the purpose of the function strlen(3) provided by the C standard library. This function is pretty easy to write: you just traverse the array of characters until you found the terminating 0, and then you return the its index. This function counts the number of characters without the terminating 0.

• Implement the following function:

size_t mystrlen(char *s);

Your function must have the same behavior as the standard function strlen(3) (see the man page.)

Copying strings

Another classical operation on strings is the copy. Like for strlen, the standard library provides functions for that. The most common one are strcpy(3) and strncpy(3). We'll focus on the second one.

strncpy(dst, src, len) will write exactly len bytes in dst, copying bytes from src and, if src is not long enough, fill the rest of dst with 0 ('\0'.) As for strlen(3), the end of src is defined by the terminating 0.

You can note that:

• dst must points to an area of at least len bytes
• if src contains len or more bytes, then strncpy won't put a terminating 0 in dst
• if src contains less than len bytes, then the end of dst will be filled with 0.

For further details, read the man page.

• Implement the following function:

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

The function returns dst in all cases.

In order to test your function, you can use the following code that do some copy and print the ASCII value of character in the string:

/* mystrncpy.c */
 
# include <stdio.h>
# include <stdlib.h>
 
size_t mystrlen(char *s) {
  // FIX ME
  return 0;
}
 
char *mystrncpy(char *dst, char *src, size_t len) {
  // FIX ME
  return dst;
}
 
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;
}

Once completed with the code of mystrlen and mystrncpy, you'll normally get:

shell> make mystrncpy
gcc -Wall -Wextra -pedantic -std=c99 -O2    mystrncpy.c   -o mystrncpy
shell> ./mystrncpy 
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 
shell>