练习 18：函数指针

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

/** Our old friend die from ex17. */
void die(const char *message)
{
    if(errno) {
        perror(message);
    } else {
        printf("ERROR: %s\n", message);
    }

    exit(1);
}

// a typedef creates a fake type, in this
// case for a function pointer
typedef int (*compare_cb)(int a, int b);

/**
 * A classic bubble sort function that uses the
 * compare_cb to do the sorting.
 */
int *bubble_sort(int *numbers, int count, compare_cb cmp)
{
    int temp = 0;
    int i = 0;
    int j = 0;
    int *target = malloc(count * sizeof(int));

    if(!target) die("Memory error.");

    memcpy(target, numbers, count * sizeof(int));

    for(i = 0; i < count; i++) {
        for(j = 0; j < count - 1; j++) {
            if(cmp(target[j], target[j+1]) > 0) {
                temp = target[j+1];
                target[j+1] = target[j];
                target[j] = temp;
            }
        }
    }

    return target;
}

int sorted_order(int a, int b)
{
    return a - b;
}

int reverse_order(int a, int b)
{
    return b - a;
}

int strange_order(int a, int b)
{
    if(a == 0 || b == 0) {
        return 0;
    } else {
        return a % b;
    }
}

/**
 * Used to test that we are sorting things correctly
 * by doing the sort and printing it out.
 */
void test_sorting(int *numbers, int count, compare_cb cmp)
{
    int i = 0;
    int *sorted = bubble_sort(numbers, count, cmp);

    if(!sorted) die("Failed to sort as requested.");

    for(i = 0; i < count; i++) {
        printf("%d ", sorted[i]);
    }
    printf("\n");

    free(sorted);
}


int main(int argc, char *argv[])
{
    if(argc < 2) die("USAGE: ex18 4 3 1 5 6");

    int count = argc - 1;
    int i = 0;
    char **inputs = argv + 1;

    int *numbers = malloc(count * sizeof(int));
    if(!numbers) die("Memory error.");

    for(i = 0; i < count; i++) {
        numbers[i] = atoi(inputs[i]);
    }

    test_sorting(numbers, count, sorted_order);
    test_sorting(numbers, count, reverse_order);
    test_sorting(numbers, count, strange_order);

    free(numbers);

    return 0;
}

附加题 1

用十六进制编辑器打开ex18，接着找到函数起始处的十六进制代码序列，看看是否能在原始程序中找到函数。

附加题 2

在你的十六进制编辑器中找到更多随机出现的东西并修改它们。重新运行你的程序看看发生了什么。字符串是你最容易修改的东西。

⮞ ./ex18
bash: ./ex18: cannot execute binary file: Exec format error

附加题 3

将错误的函数传给compare_cb，并看看C编辑器会报告什么错误。

⮞ make ex18
cc -Wall -g -c ex18.c -o ex18.o
ex18.c: In function ‘main’:
ex18.c:120:34: warning: passing argument 3 of ‘test_sorting’ from incompatible pointer type [-Wincompatible-pointer-types]
  120 |     test_sorting(numbers, count, nothing);
      |                                  ^~~~~~~
      |                                  |
      |                                  void (*)(int,  int)
ex18.c:78:55: note: expected ‘compare_cb’ {aka ‘int (*)(int,  int)’} but argument is of type ‘void (*)(int,  int)’
   78 | void test_sorting(int *numbers, int count, compare_cb cmp)
      |                                            ~~~~~~~~~~~^~~
cc  -o ex18 ex18.o
⮞ ./ex18 9 7 3 8 0 4 5
0 3 4 5 7 8 9
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:8b:45:fc:2b:45:f8:5d:c3:f3:0f:1e:
9 8 7 5 4 3 0
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:8b:45:f8:2b:45:fc:5d:c3:f3:0f:1e:
8 9 7 3 0 5 4
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:83:7d:fc:00:74:06:83:7d:f8:00:75:
0 7 3 8 4 5 9
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:90:5d:c3:f3:0f:1e:fa:55:48:89:e5:

附加题 4

将NULL传给它，看看程序中会发生什么。然后运行Valgrind来看看它会报告什么。

⮞ make ex18
cc -Wall -g -c ex18.c -o ex18.o
cc  -o ex18 ex18.o
⮞ ./ex18 9 7 3 8 0 4 5
0 3 4 5 7 8 9
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:8b:45:fc:2b:45:f8:5d:c3:f3:0f:1e:
9 8 7 5 4 3 0
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:8b:45:f8:2b:45:fc:5d:c3:f3:0f:1e:
8 9 7 3 0 5 4
f3:0f:1e:fa:55:48:89:e5:89:7d:fc:89:75:f8:83:7d:fc:00:74:06:83:7d:f8:00:75:
Segmentation fault

附加题 5

编写另一个排序算法，修改test_sorting使它接收任意的排序函数和排序函数的比较回调。并使用它来测试两种排序算法。

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

/** Our old friend die from ex17. */
void die(const char *message)
{
    if (errno)
    {
        perror(message);
    }
    else
    {
        printf("ERROR: %s\n", message);
    }

    exit(1);
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// a typedef creates a fake type, in this
// case for a function pointer
typedef int (*compare_cb)(int a, int b);
typedef int *(*sort_method)(int *numbers, int count, compare_cb cmp);
/**
 * A classic bubble sort function that uses the
 * compare_cb to do the sorting.
 */
int *bubble_sort(int *numbers, int count, compare_cb cmp)
{
    int i = 0;
    int j = 0;
    int *target = malloc(count * sizeof(int));

    if (!target)
        die("Memory error.");

    memcpy(target, numbers, count * sizeof(int));

    for (i = 0; i < count; i++)
    {
        for (j = 0; j < count - 1; j++)
        {
            if (cmp(target[j], target[j + 1]) > 0)
            {
                swap(&target[j], &target[j + 1]);
            }
        }
    }

    return target;
}

int *selection_sort(int *numbers, int count, compare_cb cmp)
{
    int i = 0;
    int j = 0;
    int *target = malloc(count * sizeof(int));

    if (!target)
        die("Memory error.");

    memcpy(target, numbers, count * sizeof(int));

    for (i = 0; i < count - 1; i++)
    {
        int M = i;
        for (j = i + 1; j < count; j++)
        {
            if (cmp(target[M], target[j]) > 0)
            {
                M = j;
            }
        }
        swap(&target[M], &target[i]);
    }

    return target;
}

int sorted_order(int a, int b)
{
    return a - b;
}

int reverse_order(int a, int b)
{
    return b - a;
}

int strange_order(int a, int b)
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    else
    {
        return a % b;
    }
}

void nothing(int a, int b)
{
}

/**
 * Used to test that we are sorting things correctly
 * by doing the sort and printing it out.
 */
void test_sorting(int *numbers, int count, compare_cb cmp, sort_method sort)
{
    int i = 0;
    int *sorted = sort(numbers, count, cmp);

    if (!sorted)
        die("Failed to sort as requested.");

    for (i = 0; i < count; i++)
    {
        printf("%d ", sorted[i]);
    }
    printf("\n");

    free(sorted);
}

int main(int argc, char *argv[])
{
    if (argc < 2)
        die("USAGE: ex18 4 3 1 5 6");

    int count = argc - 1;
    int i = 0;
    char **inputs = argv + 1;

    int *numbers = malloc(count * sizeof(int));
    if (!numbers)
        die("Memory error.");

    for (i = 0; i < count; i++)
    {
        numbers[i] = atoi(inputs[i]);
    }

    printf("Bubble sort:\n");
    test_sorting(numbers, count, sorted_order, bubble_sort);
    test_sorting(numbers, count, reverse_order, bubble_sort);
    test_sorting(numbers, count, strange_order, bubble_sort);

    printf("Quick sort:\n");
    test_sorting(numbers, count, sorted_order, selection_sort);
    test_sorting(numbers, count, reverse_order, selection_sort);
    test_sorting(numbers, count, strange_order, selection_sort);

    free(numbers);

    return 0;
}

⮞ ./ex18_1 5 4 1 2 3
Bubble sort:
1 2 3 4 5
5 4 3 2 1
4 5 2 3 1
Quick sort:
1 2 3 4 5
5 4 3 2 1
3 5 4 2 1

strange_sort 失效。