20151012:C:Pointers
Sommaire
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 |