C++泛型与多态（3）：类模板特化

C++的类没有重载，所以类只能依靠特化来实现多态。

例子：斐波那契数列

斐波那契数列（Fibonacci Number）是一个经典的数学问题。解决这类问题，是FP的强项。下面是一个Haskell的实现。

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

从其实现可以看出，函数式编程解决这类问题的两种武器：

模式匹配
递归

而类模板特化，也是同样的思路：

template <U64 N> 
struct Fib
{
  static const U64 value = Fib<N-1>::value + Fib<N-2>::value; 
}; 

template <>
struct Fib <1> 
{ 
  static const U64 value = 1; 
};
 
template <> 
struct Fib <0> 
{ 
  static const U64 value = 0; 
};

例子：数列求和

我们再看另外一个例子：对任意一个整数数列求和。在不使用fold的情况下，Haskell的实现方式如下：

sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + (add xs)

其中，整数数列的长度不确定。如果用C++的模版来实现，则需要使用C++11的变参模版：

template <int... T_ELEMS> 
struct SUM;

template <int T_HEAD, int... T_TAIL>
struct SUM <T_HEAD, T_TAIL...>
{
   static const int value = T_HEAD + SUM<T_TAIL...>::value;
};

template <>
struct SUM <>
{
   static const int value = 0;
};

从这两个例子可以看出，C++模版解决问题的思路和FP是完全一样。正是因为模板具备了这样的能力，所以它是图灵完备的。

因而，我们也可以清晰的看出，模版的特化像模式匹配一样，是一种ad-hoc多态。

给出这两个例子，仅仅是为了展示模版特化的本质。在实际应用中，肯定不是为了例子中的计算数值。而是通过编译时和运行时的结合，为程序员提供强大的武器。

动静结合：mockcpp

mockcpp支持对于自由函数的mock。其中一种实现技术称之为 Api Hook: 为了能够mock一个自由函数，就需要对自由函数的调用进行拦截，并将控制权转交给mock框架。

而拦截技术的关键，就是将被mock自由函数的地址替换为mockcpp为之生成的hook。而每个被mock的自由函数都有一个对应的hook。

这种一一映射关系，就可以通过模板特化的技术来解决。我们先定义一个特化模板ApiHookFunctor。其中，我们仅仅列出了针对两参数函数的特化模板。针对带有其它参数个数函数的特化模板的算法完全一样，这里就不再列出。

// 基础模板
template <typename F, unsigned int SEQ> 
struct ApiHookFunctor
{
};

// 2 个参数函数的特化
template <typename R, typename T1, typename T2, unsigned int SEQ> 
struct ApiHookFunctor<R (T1, T2), SEQ>
{
private: 
  typedef R FUNC (T1, T2); 
  
  // 2 个参数的 hook
  static R hook(T1 p1, T2 p2) 
  {
    // 控制权转交给 mockcpp 框架
    return GlobalMockObject::instance.invoke<R>(apiAddress)(p1, p2); 
  }
  
public:
  static void* getApiHook(FUNC* api) 
  {
    if(not appliedBy(api)) return 0; 
    ++refCount;
    return getHook(); 
  }
  
  static void* applyApiHook(FUNC* api) 
  {
    if(apiAddress != 0) return 0;
    apiAddress = reinterpret_cast<void*>(api);
    refCount = 1;
    return getHook();
  } 

  static bool freeApiHook(void* hook) 
  {
    if(getHook() != hook) return false; 
    freeHook();
    return true;
  }
   
private:
  static bool appliedBy(FUNC* api)
  { 
    return apiAddress == reinterpret_cast<void*>(api); 
  } 

  static void* getHook()
  { 
    return reinterpret_cast<void*>(hook); 
  }
   
  static void freeHook()
  {
    if(--refCount == 0) apiAddress = 0; 
  } 

private:
  static void* apiAddress; // 原函数地址
  static unsigned int refCount; // 引用计数 
};
// ...

如果两个函数如果有相同的函数原型，比如:

// 这两个函数具有相同的类型
int f(int, double);
int g(int, double);

虽然f和 g是两个不同的函数，但它们的类型是相同的。但之前我们已经介绍过，Api Hook设计的关键在于，要为每一个需要mock 的自由函数都应该生成一个hook。所以，上述模板必须能够为同一类型的函数预先分配多个hook，以供多个同一类型的不同函数进行动态分配。

而模板参数SEQ正是为了区分同一类型函数的多个hook。每一个经过实例化之后的模板类都是一个可动态分配的资源，因为一个这样的模板类对应了一个hook。

而每个模板的静态数据apiAddress用来纪录当前模板类被分配给了哪个函数, 其内容为函数的原始地址。当一个自由函数被多次mock 时，refCount用来纪录mock的次数。当其值为0时,此模板类将会被释放，以供后续的分配。

ApiHookFunctor用来生成单个资源，而下面的模板：ApiHookGenerator则用来生成和管理所有资源。这是一个动态和静态相结合，进行资源分配和释放的典型处理手法。其中,编译时（静态）生成所有可使用的资源，以及相关的算法代码；而运行时（动态）则根据静态生成的算法，动态的管理静态生成的资源。如下：

template <typename F, unsigned int SEQ>
struct ApiHookGenerator 
{ 
  static void* findApiHook(F* api) 
  {
    void* hook;
    
    (hook = ApiHookFunctor<F, SEQ>::getApiHook(api))   
    || (hook = ApiHookGenerator<F, SEQ-1>::findApiHook(api)); 
    
    return hook;
  } 

  static void* applyApiHook(F* api) 
  { 
    void* hook;
    
    (hook = ApiHookFunctor<F, SEQ>::applyApiHook(api)) 
    || (hook = ApiHookGenerator<F, SEQ-1>::applyApiHook(api));
    return hook; 
  }
   
  static bool freeApiHook(void* hook) 
  {
    return (ApiHookFunctor<F, SEQ>::freeApiHook(hook)) 
    || (ApiHookGenerator<F, SEQ-1>::freeApiHook(hook)); 
  }
}; 

template <typename F>
struct ApiHookGenerator<F, 0> 
{
  static void* findApiHook(F* api) { return 0; }
  static void* applyApiHook(F* api) { return 0; }
  static bool freeApiHook(void* hook) { return true; } 
};

有了ApiHookGenerator这个资源管理器之后，用户就可以通过如下方式来使用：

template <typename F>
struct ParameterizedApiHookHolder 
  : public ApiHookHolder
{ 
  const static unsigned int MAX_RESOURCES = 10; 
  
  ParameterizedApiHookHolder(F* api)
  {
    (m_hook = ApiHookGenerator<F, MAX_RESOURCES>::findApiHook(api)) 
    || (m_hook = ApiHookGenerator<F, MAX_RESOURCES>::appyApiHook(api));
  } 

  void * getApiHook() const { return m_hook; }
  
  ~ParameterizedApiHookHolder()
  {
    ApiHookGenerator<F, MAX_RESOURCES>::freeApiHook(m_hook);
  }
private:
  void* m_hook; 
};

最后，为了有助于进一步理解上述代码，我们来总结一下解决问题的整个思路:

每个被mock函数，都要有一个自己的hook函数；
每个hook函数，必须和原函数的原型完全一样;
由于函数原型存在无穷个种类，所以我们必须借助模板，按需在编译时生成hook资源；
不同函数可能属于同一类型,所以需要给同一类型的的函数预留多份 hook资源;
有了多份资源，就需要按照一定的算法进行管理。于是为资源模板引入SEQ参数；资源的生成和管理算法，都是以SEQ来区分同一类型函数的多份hook 资源。
由于每个函数的运行时地址都是唯一的，所以，使用“函数地址”作为key值，在运行时，按照静态生成的算法，动态地分配编译时按需生成的hook资源。

动静结合：组合

Transaction DSL中可以这样描述一个序列：

__sequential
  ( __asyn(Action1)
  , __asyn(Action2)
  , __sync(Action3))

__sequantial里包含的Action完全由用户根据自己的需要填写，因而数量不确定。

而__sequential这个宏背后直接对应的就是变参模版:

#define __sequential(...)      \
       SEQUENTIAL__< __VA_ARGS__ >

而模版SEQUENTIAL__的实现如下：

template <typename... T_ACTIONS> 
struct GenericSequential;

template <typename T_HEAD, typename... T_TAIL>
struct GenericSequential<T_HEAD, T_TAIL...> : GenericSequential<T_TAIL...>
{
protected:
  void init()
  {
    GenericSequential<T_TAIL...>::pushBackAction(action);
    GenericSequential<T_TAIL...>::init();
  }
   
private:
  details::LINKED__< T_HEAD > action;
};

template <>
struct GenericSequential<> : SchedSequentialAction
{
protected:
  void init() {}
};

template <typename... T_ACTIONS>
struct SEQUENTIAL__ : GenericSequential<T_ACTIONS...>
{
  SEQUENTIAL__()
  {
    GenericSequential<T_ACTIONS...>::init();
  }
};

这里例子展示的是，对于不确定数量的被组合元素，通过变参模版在编译时完成对于类型的静态组合。然后运行时，让模版类里的函数完成动态组合。

小结

本文介绍了类模版特化的语义，并通过几个例子介绍了通过它解决问题的方式。

从中我们可以看出，类模版特化要表达的语义为：

函数选择优先级

在随后的文章中，会继续介绍与泛型有关的其它多态。

C++泛型与多态（3）：类模板特化

C++泛型与多态（3）：类模板特化

例子：斐波那契数列

例子：数列求和

动静结合：mockcpp

动静结合：组合

小结

相关链接

推荐阅读更多精彩内容