20151012:C:Pointers

Introduction

This week subject is about pointers, arrays, matrix, strings and multiple files compilation.

The global layout of session should be:

• 20151012_tutorial/
  • AUTHORS
  • arrays/
  • strings/
  • matrix/

Arrays used as pointers

In this section we'll write some more operations on arrays, but this time we want to use pointers arithmetic (t + i) rather than array bracket notations (t[i]), **i.e.** for the next exercises you must not use brackets.

We also use this exercise to introduce multi-files program. Your program will be split in 3 files and a Makefile. Here is a description of the mini-program source directory:

• Makefile: building the code
• arrays.c: where you'll write your code
• arrays.h: header description
• ptr_arrays.c: main program file.

The Makefile, the header file and the main file are provided:

# Makefile
 
# Compilers and options
 
# Setup compiler
# Add runtime aggressive memory check
CC=clang -fsanitize=address
# Prefer gcc without sanitizer for production
# CC=gcc
 
# CPPFLAGS with dependencies files (.d)
CPPFLAGS= -MMD -MP
 
# Standard options, added pedantic
CFLAGS= -Wall -Wextra -pedantic -std=c99 -O2
 
# libs options
LDFLAGS=
LDLIBS=
 
# source files
SRC= arrays.c ptr_arrays.c
# object files (produced from source files list)
OBJ= ${SRC:.c=.o}
 
# dependencies files (produced from source files list)
DEP= ${SRC:.c=.d}
 
# include dependencies files
-include ${DEP}
 
# default rule
all: ptr_arrays
 
# ptr_arrays depends on object files
ptr_arrays: ${OBJ}
 
# setup cleaning rules as phony: always run
.PHONY: clean
 
# Cleaning rule
clean:
	rm -f *.o *~
	rm -f ${DEP}
	rm -f ptr_arrays
 
# END

Some remarks about this Makefile:

• we use a variable (SRC) to list the source files
• we indicate that the target program depends on .o files
• the compiler produces files containing dependencies that will be used by make
• we use clang with the flag -fsanitize=address that activate runtime checks for memory

/* file: arrays.h */
/* Headers of functions on arrays */
 
# ifndef _20151012_ARRAYS_H_
# define _20151012_ARRAYS_H_
 
/* print_array(begin, end) prints the ints stored between begin and end */
void print_array(int *begin, int *end);
 
/* binsearch(x, begin, end) returns the pointer to the position of x,
 * the array between begin and end is supposed to be sorted.
 * binsearch returns the expected place of x: the pointer to the first cell
 * containing a value not smaller than x. If all cells contains smaller value,
 * the function returns end. */
int* binsearch(int x, int *begin, int *end);
 
/* sorted_insert(x, begin, end) insert x at its place between begin and end,
 * the stored values are supposed to sorted in increasing order.
 * The function returns true (!= 0) if x wasn't in the array and false (0)
 * otherwise.
 * We assume that there is enough memory for an insertion. */
int sorted_insert(int x, int *begin, int *end);
 
/* quick_sort(begin, end) sort the array between begin and end using the quick
 * sort algorithm. */
void quick_sort(int *begin, int *end);
 
# endif /* _20151012_ARRAYS_H_ */

/* file: ptr_arrays.c */
/* Using pointers as array */
 
# define _XOPEN_SOURCE 600
 
# include <assert.h>
# include <stdio.h>
# include <stdlib.h>
 
# include "arrays.h"
 
static inline
int is_sorted(int *begin, int *end) {
  for (; begin < end - 1 && *begin <= *(begin + 1); begin++) {}
  return begin == end - 1;
}
 
static
void test_sorted_insert(int *arr, size_t len) {
  printf("Sorted fill:\n");
  int *begin = arr, *end = arr;
  while (end - begin < (ssize_t)len) {
    int x = random() % 1000;
    printf("\tInserting %3d: ", x);
    if (sorted_insert(x, begin, end)) {
      printf("OK\n");
      end++;
    } else {
      printf("already inside\n");
    }
  }
  print_array(begin, end);
  printf("Array is sorted: ");
  if (is_sorted(begin, end))
    printf("OK\n");
  else {
    printf("KO\n");
    assert(0);
  }
}
 
static inline
void random_fill(int *begin, int *end) {
  for (int *cur = begin; cur < end; cur++)
    *cur = random() % 1000;
}
 
static inline
void sorted_fill(int *begin, int *end) {
  for (int i = 0; begin < end; begin++, i++)
    *begin = i;
}
 
static inline
void rev_sorted_fill(int *begin, int *end) {
  for (int i = end - begin; begin < end; begin++, i--)
    *begin = i;
}
 
static
void subtest_qsort(int *begin, int *end) {
  printf("\tbefore sort:\n\t");
  print_array(begin, end);
  quick_sort(begin, end);
  printf("\tafter sort:\n\t");
  print_array(begin, end);
 
  printf("Array is sorted: ");
  if (is_sorted(begin, end))
    printf("OK\n");
  else {
    printf("KO\n");
    assert(0);
  }
}
 
static
void test_qsort(int *arr, size_t len) {
  int *begin = arr, *end = arr + len;
 
  printf("Sorting sorted arrays:\n");
  sorted_fill(begin, end);
  subtest_qsort(begin, end);
 
  printf("Sorting reverse sorted arrays:\n");
  rev_sorted_fill(begin, end);
  subtest_qsort(begin, end);
 
  printf("Sorting random arrays:\n");
  random_fill(begin, end);
  subtest_qsort(begin, end);
}
 
int main(int argc, char *argv[]) {
  size_t len = 8;
  if (argc > 1)
    len = strtoul(argv[1], NULL, 10);
  int *arr = malloc(len * sizeof (int));
  printf("*** Testing insertion and binary search ***\n");
  test_sorted_insert(arr, len);
 
  printf("\n*** Testing quick sort***\n");
  test_qsort(arr, len);
 
  free(arr);
  return 0;
}

All functions for this exercise will be implemented in the file arrays.c. You should add the correct includes for your code at the beginning of the file and also include (like it is done in the main file) the header arrays.h.

Printing arrays content

• Implement the following function:

/* print_array(begin, end) prints the ints stored between begin and end */
void print_array(int *begin, int *end);

This function prints the content of an array, on one line each value separated by | and some space. In the main file, we test arrays with values smaller than 1000 so you can print integer with a width of 3 so that every cells have the same length. The format for this is %3d.

Binary search

• Implement the following function:

/* binsearch(x, begin, end) returns the pointer to the position of x,
 * the array between begin and end is supposed to be sorted.
 * binsearch returns the expected place of x: the pointer to the first cell
 * containing a value not smaller than x. If all cells contains smaller value,
 * the function returns end. */
int* binsearch(int x, int *begin, int *end);

Here is a quick description of the binary search algorithm (dichotomy):

binsearch(x, arr, L, R):
  dist = R - L
  if dist < 1:
    return L
  end if
  mid = L + dist/2
  if arr[mid] < x:
    return binsearch(x, arr, mid + 1, R)
  else:
    return binsearch(x, arr, L, mid)
  endif

Note that this function returns the expected position of x even if it's not in arr. This way we can use it for an insertion algorithm (next question.)

Sorted insertion

• Implement the following function:

/* sorted_insert(x, begin, end) insert x at its place between begin and end,
 * the stored values are supposed to sorted in increasing order.
 * The function returns true (!= 0) if x wasn't in the array and false (0)
 * otherwise.
 * We assume that there is enough memory for an insertion. */
int sorted_insert(int x, int *begin, int *end);

In order to build this function we want to reuse binsearch of course, but we also want to use memmove(3) in order to shift values during the insertion. Here is a pseudo-code of the algorithm:

sorted_insert(x, arr, L, R):
  pos = binsearch(x, arr, L, R)
  if pos < R and arr[pos] == x:
    return false
  end if
  if pos < R:
    shift cells by 1 to the right from pos to R in arr
  end if
  arr[pos] = x
  return true

The memmove(3) functions moves bytes from a memory area to some other that may overlap, this means that you need to compute the size of block to be moved and multiply it by the size of an int.

Quick Sort

Now let's move to quick-sort. Here is a pseudo-code description of quick-sort:

// Choose the median value between arr[L], arr[R] and arr[L + (R - L)/2]
// you can probably guess how to do that by yourself.
choose_pivot(arr, L, R)

// groups all values smaller than arr[pivot] to the left and all value bigger to the right
// returns the position of the pivot value after the partition.
partition(arr, L, R, pivot):
  pval = arr[pivot]
  swap arr[pivot] and arr[R - 1]
  pivot = L
  for i = L to R - 2 do:
    if arr[i] < pval:
      swap arr[pivot] and arr[i]
      pivot = pivot + 1
    end if
  done
  swap arr[pivot] and arr[R - 1]
  return pivot

quick_sort(arr, L, R):
  if R - L > 1:
    pivot = choose_pivot(arr, L, R)
    pivot = partition(arr, L, R, pivot)
    quick_sort(arr, L, pivot)
    quick_sort(arr, pivot + 1, R)
  end if

• Implement described function:

int *choose_pivot(int *begin, int *end);
int* partition(int *begin, int *end, int *pivot);

• Implement the main function:

/* quick_sort(begin, end) sort the array between begin and end using the quick
 * sort algorithm. */
void quick_sort(int *begin, int *end);

Testing

Once you've implemented all the request functions, you can launch the tests:

shell> ls
Makefile  arrays.c  arrays.h  ptr_arrays.c
shell> make
clang -fsanitize=address -Wall -Wextra -pedantic -std=c99 -O2 -MMD -MP  -c -o ptr_arrays.o ptr_arrays.c
clang -fsanitize=address -Wall -Wextra -pedantic -std=c99 -O2 -MMD -MP  -c -o arrays.o arrays.c
clang -fsanitize=address   ptr_arrays.o arrays.o   -o ptr_arrays
shell> ./ptr_arrays 
*** Testing insertion and binary search ***
Sorted fill:
	Inserting 383: OK
	Inserting 886: OK
	Inserting 777: OK
	Inserting 915: OK
	Inserting 793: OK
	Inserting 335: OK
	Inserting 386: OK
	Inserting 492: OK
| 335 | 383 | 386 | 492 | 777 | 793 | 886 | 915 |
Array is sorted: OK

*** Testing quick sort***
Sorting sorted arrays:
	before sort:
	|   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |
	after sort:
	|   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |
Array is sorted: OK
Sorting reverse sorted arrays:
	before sort:
	|   8 |   7 |   6 |   5 |   4 |   3 |   2 |   1 |
	after sort:
	|   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |
Array is sorted: OK
Sorting random arrays:
	before sort:
	| 649 | 421 | 362 |  27 | 690 |  59 | 763 | 926 |
	after sort:
	|  27 |  59 | 362 | 421 | 649 | 690 | 763 | 926 |
Array is sorted: OK
shell>

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>

Matrix examples

The purpose of this exercise is to practice the common idiom: single dimension array used as matrix.

A matrix M of dimension m × n will be implemented as an array of size m*n and access to a cell M(i,j) will be obtained with M[i * n + j].

For your test, and as a source of inspiration, here is a printing function for matrix:

void print_matrix(int M[], size_t m, size_t n) {
  for (size_t i = 0; i < m; i++) {
    size_t line_offset = i * n;
    for (size_t j = 0; j < n; j++) {
      printf("| %3d ", M[line_offset + j]);
    }
    printf("|\n");
  }
}

• Implement the following function:

void fill_matrix(int M[], size_t m, size_t n);

This function will the matrix in row first mode, column are filled with values from 0 to the size of the matrix, for example, with a 3 × 5 matrix, the cell M(i,j) will contains j * m + i<tt>.

If we print such a matrix, we get:

|   0 |   3 |   6 |   9 |  12 |
|   1 |   4 |   7 |  10 |  13 |
|   2 |   5 |   8 |  11 |  14 |