C 語言練習程式(8) -- 可應付不同型態的function(generic function)寫法 -- 指標相關程式集錦(7)

此篇為Pointers in C Programming A Modern Approach to Memory Management, Recursive Data Structures, Strings, and Arrays這本書第六章筆記其之二。

在這一章節，要說的是很有用的技巧--generic function，generic指的是這函式可應付不同型態，不用同一個功能的函式為了不同的型態要重寫好多次。這裡以is_sorted函式為例。is_sorted的目的是撿查陣列是否有排序，但陣列的型態可能是字串、整數或浮點數。所以它的函式原型應是這樣:

bool is_sorted(void const *array,
               size_t len, size_t obj_size,
               compare_function cmp)

因為不知道型態，所以都用size_t來表示。還有一個compare_function cmp是給使用者自訂的比較函式。這個函式還是要針對不同的型態去編寫。
重點來了，compare_function這個型態怎麼來的? 要寫下面這一行:

typedef int (*compare_function)(void const *, void const *);

這是一個函數指標。
is_sorted完整函式如下:

bool is_sorted(void const *array,
               size_t len, size_t obj_size,
               compare_function cmp)
{
  for (int i = 1; i < len; i++) {
    void const *a = (char *)array + (i - 1) * obj_size;
    void const *b = (char *)array + i * obj_size;
    if (cmp(a, b) > 0) {
      // a is larger than b, so the array is not sorted
      return false;
    }
  }
  return true;
}

要注意的是下面兩行:

    void const *a = (char *)array + (i - 1) * obj_size;
    void const *b = (char *)array + i * obj_size;

這是為了可以應對不同型態，乾脆就讓使用這函數的人自己去填目前要使用的型態大小。
完整程式如下:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int int_compare(void const *x, void const *y)
{
  // Get the objects, and interpret them as integers
  int const *a = x;
  int const *b = y;
  return *a - *b;
}

int string_compare(const void *x, const void *y)
{
  // Get the objects and interpet them as strings
  char * const *a = x;
  char * const *b = y;
  return strcmp(*a, *b);
}

typedef int (*compare_function)(void const *, void const *);
bool is_sorted(void const *array,
               size_t len, size_t obj_size,
               compare_function cmp)
{
  for (int i = 1; i < len; i++) {
    void const *a = (char *)array + (i - 1) * obj_size;
    void const *b = (char *)array + i * obj_size;
    if (cmp(a, b) > 0) {
      // a is larger than b, so the array is not sorted
      return false;
    }
  }
  return true;
}

int main(void)
{
  int int_array[] = { 10, 5, 30, 15, 20, 30 };
  int int_array_length =
    sizeof int_array / sizeof *int_array;

  if (is_sorted(int_array, int_array_length,
                sizeof *int_array, int_compare)) {
    printf("int_array is sorted\n");
  } else {
    printf("int_array is not sorted\n");
  }
  qsort(int_array, int_array_length,
        sizeof *int_array, int_compare);
  if (is_sorted(int_array, int_array_length,
                sizeof *int_array, int_compare)) {
    printf("int_array is sorted\n");
  } else {
    printf("int_array is not sorted\n");
  }

  char *string_array[] = { "foo", "bar", "baz" };
  int string_array_length =
    sizeof string_array / sizeof *string_array;

  if (is_sorted(string_array, string_array_length,
                sizeof *string_array, string_compare)) {
    printf("string_array is sorted\n");
  } else {
    printf("string_array is not sorted\n");
  }
  qsort(string_array, string_array_length,
        sizeof *string_array, string_compare);
  if (is_sorted(string_array, string_array_length,
                sizeof *string_array, string_compare)) {
    printf("string_array is sorted\n");
  } else {
    printf("string_array is not sorted\n");
  }

  return 0;
}

另一個應用的例子，是反向函數，希望可以把陣列內所有元素都倒著排。

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

void reverse(void *array, int n, int size)
{
  if (n <= 0) return; // avoid right underflow
  char *left = array;
  char *right = left + size * (n - 1);
  char tmp[size];

  while (left < right) {
    memcpy(&tmp, left, size);
    memcpy(left, right, size);
    memcpy(right, &tmp, size);
    left += size; right -= size;
  }
}

int main(void)
{
  int int_array[] = { 1, 2, 3, 4, 5 };
  int n = sizeof int_array / sizeof *int_array;
  reverse(int_array, n, sizeof *int_array);
  for (int i = 0; i < n; i++) {
    printf("%d ", int_array[i]);
  }
  printf("\n");

  char char_array[] = { 'f', 'o', 'o', 'b', 'a', 'r' };
  int m = sizeof char_array / sizeof *char_array;
  reverse(char_array, m, sizeof *char_array);
  for (int i = 0; i < m; i++) {
    printf("%c ", char_array[i]);
  }
  printf("\n");

  return 0;
}

可以發現，以交換函數為例，memcpy是非常好用的--只要知道元素大小，不管是字串或是數字都可用。

第三個例子是插入排序。不管是int_compare、string_compare跟

typedef int (*compare_function)(void const *, void const *);

都是跟is_sorted一樣。而插入排序核心的交換函數swap一樣要用到memcpy，完整程式碼如下:

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

int int_compare(void const *x, void const *y)
{
  // Get the objects, and interpret them as integers
  int const *a = x;
  int const *b = y;
  return *a - *b;
}

int string_compare(const void *x, const void *y)
{
  // Get the objects and interpet them as strings
  char * const *a = x;
  char * const *b = y;
  return strcmp(*a, *b);
}

typedef int (*compare_function)(void const *, void const *);

void swap(void *a, void *b, size_t obj_size)
{
  char tmp[obj_size];
  memcpy(&tmp, a, obj_size);
  memcpy(a, b, obj_size);
  memcpy(b, &tmp, obj_size);
}

void swap_down(char *start, char *current,
               size_t obj_size,
               compare_function cmp)
{

  while (current != start) {
    char *prev = current - obj_size;
    if (cmp(prev, current) <= 0) break; // done swapping
    swap(prev, current, obj_size);
    current = prev;
  }
}

void insertion_sort(void *array,
                    size_t len, size_t obj_size,
                    compare_function cmp)
{
  char *start = array;
  for (int i = 1; i < len; i++) {
    swap_down(start, start + i * obj_size, obj_size, cmp);
  }
}

int main(void)
{
  int int_array[] = { 10, 5, 30, 15, 20, 30 };
  int int_array_length =
    sizeof int_array / sizeof *int_array;

  insertion_sort(int_array, int_array_length,
        sizeof *int_array, int_compare);
  for (int i = 0; i < int_array_length; i++) {
    printf("%d ", int_array[i]);
  }
  printf("\n");

  char *string_array[] = { "foo", "bar", "baz" };
  int string_array_length =
    sizeof string_array / sizeof *string_array;

  insertion_sort(string_array, string_array_length,
        sizeof *string_array, string_compare);
  for (int i = 0; i < string_array_length; i++) {
    printf("%s ", string_array[i]);
  }
  printf("\n");

  return 0;
}