在C语言中实现泛型编程

0x00 泛型编程概述

  • 泛型编程是一个非常常见的编程方式。主要目的是实现静态联编,使得函数可以接受不同类型的参数,并且在编译的时候确定正确的类型。
  • 很多语言都对泛型编程提供了支持,比如在C++中可以使用函数模版和类模版来实现泛型编程;在Java、Objective-C或者C#等单根继承的语言中,也可以使用类似java.lang.Object、NSObject等类型进行编程。在具有类型推断功能(比如Swift)的编程语言中,更是可以直接使用泛型编程。
  • 不过C语言是高级语言编程的基础语言,那如何在C语言中实现泛型编程,确实是一个问题。首先C语言不支持函数重载,不支持模版类型,所以实现起来确实比较困难。

0x01 泛型指针(void *)简介

  • void *是C语言中的一种类型,大家都知道在大多数编程语言中,void类型都代表所谓的空类型,比如一个函数的返回一个空类型void ,这是很常见的用法。
注意:返回值为void 并不是没有返回值,而是代表返回空类型,这就是你仍然可以在这些函数中使用return语句的原因。只有一些语言的构造函数和析构函数才没有返回值,在这些函数中,不可以使用return语句,他们是有显著的不同的,Objective-C是一门独特的语言,它的类的初始化方法是一个普通方法,返回值是instancetype(当前类的指针类型)类型。
  • void *可能就稍微鲜为人知一些,void *在C语言中可以表示人任意类型的指针。毕竟对于内存单元的地址而言,所谓它存储的数据类型,只是每次取出的字节数不同而已,这些内存单元的地址本身并没有什么不同。下面会更好的体现这句话的含义。
  • void *的大小和普通类型的指针一样,总是一个字,具体的大小因机器的字长而异,例如对于32位机器是4个字节,对于64位机器是8个字节。
我没有考证过16位的8086机器上指针的大小,因为8086的地址是20位的,这个有兴趣的话可以回去试一试。

个人认为指针的大小仍然是16位,因为20位是物理地址,而物理地址是由段地址和偏移地址计算出的,在汇编之后C语言的指针可能只是变成相对于段地址的偏移地址,毕竟对于8086而言数据一般总是在DS段中,而代码一般总是在CS段中。(斜体字代表尚未考证的说法)

  • 在C语言中,其他普通类型的指针可以自动转换为void *类型,而void *类型一般只能强制转换为其他普通类型的指针,否则会出现警告或错误。
  • 有一个特别大的坑就是关于所谓void *指向数组的情况,这里直接上代码解释了。
void Swap(void *array, int x, int y, int mallocsize) {
    void *temp = malloc(mallocsize);
    memcpy(temp, array+mallocsize*x, mallocsize);
    memcpy(array+mallocsize*x, array+mallocsize*y, mallocsize);
    memcpy(array+mallocsize*y, temp, mallocsize);
    free(temp);
}
  • 这是一个比较经典的交换函数,借助的是临时变量temp,但是这个函数是泛型的,对于memcpy的使用稍后会介绍。需要注意的是,array指向一个数组的话,不能直接用&array[x]或者array+x获得指向第x个元素的地址,因为void *类型默认的指针偏移量是1,和char *是相同的,这对于绝大多数类型来说都会出现错误。所以在使用的时候必须知道该泛型类型原来所占的长度,我们需要一个名为mallocsizeint类型形参来告诉我们这个值,在计算指针偏移的时候乘以它。这就相当于C++编程中的模版类型定义或者Java中的泛型参数了。
  • 同时要注意对于void *类型的指针,任何时候都不可以对其进行解引用运算(或者在课堂上老师习惯叫做“取内容”?),原因是显然的:void类型的变量并不合法。所以如果想进行解引用运算,必须先将其转换为普通类型的指针。用于数组的时候还需要注意解引用运算符的优先级是高于加法的,所以要加括号,比如这样:
int a = *(array + mallocsize * x);
  • 这句代码完美的体现了C语言编程的丑陋。

0x02 sizeof运算符简介

  • sizeof运算符相信学过C语言的朋友都不会陌生,但是sizeof是一个运算符估计就没多少人知道了,返回的类型是size_t类型。sizeof运算符返回某个类型所占用的空间大小。这里只说一点就是,如果对一个指针类型或者数组名(实际上数组名就是指针常量嘛)求sizeof的话,返回结果总是一个字(见上面所述)。而对一个结构体类型求sizeof,并不是简单的将结构体中各个类型的sizeof求和得到,而是要涉及到内存对齐问题,这里不多做介绍了,详细了解可以访问:如何理解 struct 的内存对齐? - 知乎

0x03 memcpy函数简介

  • memcpy是一个经常和void *配合使用的函数,其函数原型为:
void * memcpy(void *, const void *, size_t);
  • 所属的头文件为string.h,大家也看出来了,这个函数本身就是以void *类型作为参数和返回值,其实也很好理解,就是一个赋值的过程,进行内存拷贝。把第二形参指向的内存拷贝到第一形参,拷贝的字节数由第三形参指定。当然了第三个参数一般通过sizeof运算符求出,这里就不举例子了。返回值我没有研究过,也没用过,如果有知道的朋友可以评论区交流。

0x04 C语言中实现泛型编程

  • 说了这么多,还没提到泛型编程。不过前面也提的差不多了,总体思想就是使用void *类型当作泛型指针,然后再辅以类似于mallocsize的参数指定所占内存大小,所占内存大小通过sizeof运算符求得,如果需要进行赋值的话,利用memcpy函数完成,下面就直接给一个例子出来,是泛型的快速排序算法,说明这些问题:
#ifndef Compare_h
#define Compare_h

#include <stdio.h>
#include "JCB.h"

int IsGreater(void *x, void *y);
int IsGreaterOrEqual(void *x, void *y);
int IsSmaller(void *x, void *y);
int IsSmallerOrEqual(void *x, void *y);

#endif /* Compare_h */
//
//  Compare.c
//  Job-Dispatcher
//
//  Created by 路伟饶 on 2017/11/16.
//  Copyright © 2017年 路伟饶. All rights reserved.
//

#include "Compare.h"

int IsGreater(void *x, void *y) {
    return *(int *)x > *(int *)y;
}
int IsGreaterOrEqual(void *x, void *y) {
    return *(int *)x >= *(int *)y;
}
int IsSmaller(void *x, void *y) {
    return *(int *)x < *(int *)y;
}
int IsSmallerOrEqual(void *x, void *y) {
    return *(int *)x <= *(int *)y;
}
//
//  QuickSort.h
//  Job-Dispatcher
//
//  Created by 路伟饶 on 2017/11/16.
//  Copyright © 2017年 路伟饶. All rights reserved.
//

#ifndef QuickSort_h
#define QuickSort_h

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Compare.h"

void QuickSort(void *array, int left, int right, int mallocsize);

#endif /* QuickSort_h */
//
//  QuickSort.c
//  Job-Dispatcher
//
//  Created by 路伟饶 on 2017/11/16.
//  Copyright © 2017年 路伟饶. All rights reserved.
//

#include "QuickSort.h"

void Swap(void *array, int x, int y, int mallocsize) {
    void *temp = malloc(mallocsize);
    memcpy(temp, array+mallocsize*x, mallocsize);
    memcpy(array+mallocsize*x, array+mallocsize*y, mallocsize);
    memcpy(array+mallocsize*y, temp, mallocsize);
    free(temp);
}

int QuickSortSelectCenter(int l, int r) {
    return (l+r)/2;
}
int QuickSortPartition(void *array, int l, int r, int mallocsize) {
    int left = l;
    int right = r;
    void *temp = malloc(mallocsize);
    memcpy(temp, array+mallocsize*right, mallocsize);
    while (left < right) {
        while ( IsSmallerOrEqual(array+mallocsize*left, temp) && left < right) {
            left ++;
        }
        if (left < right) {
            memcpy(array+mallocsize*right, array+mallocsize*left, mallocsize);
            right--;
        }
        while ( IsGreaterOrEqual(array+mallocsize*right, temp) && left < right) {
            right--;
        }
        if (left < right) {
            memcpy(array+mallocsize*left, array+mallocsize*right, mallocsize);
            left ++;
        }
    }
    memcpy(array+mallocsize*left, temp, mallocsize);
    return left;
}

void QuickSort(void *array, int left, int right, int mallocsize) {
    if (left>=right) {
        return;
    }
    int center = QuickSortSelectCenter(left, right);
    Swap(array, center, right, mallocsize);
    center = QuickSortPartition(array, left, right, mallocsize);
    QuickSort(array, left, center-1, mallocsize);
    QuickSort(array, center+1, right, mallocsize);
}
  • 这里留了一个悬念,明明可以直接比较的,为什么还要这么麻烦使用好多函数完成,也就是关于Compare.h的用处的问题,下面会揭晓答案。

0x05 泛型的协议问题

  • 刚刚那个问题就涉及到了一个泛型的协议问题,我这里是借用了Objective-C 中的一个概念去阐述。就像刚刚那个问题,既然我的快速排序是泛型的,那么怎么保证实际传入泛型参数一定是可比较的呢?举个例子,显然intfloatdouble是可以进行比较的,char使用ASCII编码方案的比较我们也理解,String类型甚至也是可以比较的。但是如果在其他语言中,对象之间如何进行比较呢?这就是个问题了。在C++中我们可以进行运算符重载,这样就仍旧可以使用比较运算符,借助运算符重载函数来完成。不过对于Java、Objective-C这种语言该怎么办?而且如果传入的泛型参数没有实现对应的运算符重载函数怎么办?这时候就要引入一个协议的概念,简单来说就是,如果某个类型想要作为排序泛型函数的泛型参数,那你必须实现可比较的协议。这个协议在Swift语言中就称为Comparable,这样的话在编译的时候,编译器才知道这个泛型参数是可以进行比较的,这样才能完成我们的操作,否则的话就会出现错误。这就是泛型中的协议问题。

0x06 总结

  • C语言的泛型编程以void *作为泛型类型,本质上是泛型指针。
  • C语言的泛型编程需要知道一个泛型类型变量所占的内存大小,这个可以通过sizeof求得并传入泛型函数。
  • C语言的泛型编程中要注意数组的偏移问题,void *的默认偏移是1,对于绝大多数类型来说都是错误的,需要自行编程转换。
  • C语言的泛型编程中使用memcpy函数进行泛型变量的拷贝和赋值。
  • C语言的泛型编程中也需要注意协议问题,但是C中就只能自行编写函数进行定义了,在其他语言中可以使用现成的接口或者协议。

相关推荐