# Dynamic Linkage: Generic Functions
物件導向程式設計 (OOP) 包含了封裝，繼承與多型下三大概念。透過第一章介紹的抽象化資料，我們便能做到類似封裝的效果。這個章節將會介紹如何去設計能達到類似多型的程式。
## Polymorphism & Generic Function
多型為一種讓相同介面的函式能根據參數型態執行不同操作的函式。根據決定要執行什麼操作的時間，可以將多型分為以下兩類:
* 靜態多型: 在編譯時決定函式行為，例如函式多載 (overloading) 和模板 (template)。
* 模板為泛型函式（generic function) 主要的實現方式。
* 動態多型: 在執行時決定函式行為，例如 virtual function。
## Design of Constructors and Destructors
以下為以設計多型函式的方式設計建構子 (constructor) 與解構子 (destructor) 的例子。
首先，如果要讓 `new()` 與 `delete()` 是能被應用在各種不同資料型態上的函式，需要考慮以下狀況:
* `new()` 與 `delete()` 都需要知道要處理甚麼物件，這樣才能對以下操作做出合適的處理:
* 分配符合該物件大小的記憶體空間。
* 初始化該物件的各個成員。
* 釋放該物件的記憶體空間。
對於這樣的需求，可以透過讓做為參數傳遞的型態描述符 (type descriptor) 帶有**指向用來管理特定型態的函式 (i.e., `delete()`) 的指標**，使 `new()` 與 `delete()` 可以透過這些函式指標去管理特定型態的物件。
### Introduction of the Concepts of Class, Instance, and Method
首先，下方為作者提供的例子:
```C++=
struct Class {
size_t size;
void * (* ctor) (void * self, va_list * app);
void * (* dtor) (void * self);
void * (* clone) (const void * self);
int (* differ) (const void * self, const void * b);
};
struct String {
const void * class; /* must be first */
char * text;
};
struct Set {
const void * class; /* must be first */
...
};
```
`String` 與 `Set` 的**第一個成員都是指向型態描述符的指標**，透過這個指標能找到特定型態的資訊，並根據這些資訊進行相對應的操作。以下為型態描述符中各個成員的功能:
* `.size`: 提供 `new()` 在分配空間時需要的長度資訊。
* `.ctor`: 指向讓 `new()` 呼叫，並會接收已分配空間與其他 `new()` 原本接收的參數的建構子。
* `.dtor`: 指向讓 `delete()` 呼叫的解構子。
* `.clone()`: 指向用來複製特定物件的函式。
* `.differ()`: 指向比較特定物件的函式。
上述以型態描述符取得特定操作的方式蘊含了以下物件導向程式設計的概念:
* 類別 (*class*): 使用同型態描述符的物件屬於同類別。
* 實例 (*instance*): 同類別的各個物件被稱作實例。
* 方法 (*method*): 紀錄在型態描述符，並透過特定類別的實例呼叫的函式。
### Introduction of the Concepts of Dynamic Linkage and Polymorphisms
`new()` 在呼叫建構子方法的過程中會處理未初始化的記憶體空間，處理方式如下:
```C=
void * new (const void * _class, ...)
{ const struct Class * class = _class;
void * p = calloc(1, class —> size);
assert(p);
* (const struct Class **) p = class;
if (class —> ctor)
{ va_list ap;
va_start(ap, _class);
p = class —> ctor(p, & ap);
va_end(ap);
}
return p;
}
```
首先，由於我們假設每個物件的第一個成員必定是型態描述符，因此可以透過 `* (const struct Class **) p = class;` 直接用型態描述符的結構解讀以物件起始位址爲開頭的記憶體區段。
接下來，如果型態描述符的成員帶有建構子的資訊，則呼叫建構子並回傳其執行結果，也就是回傳初始化過的新物件。
* 可變參數列表的使用方式可以參考[此連結](https://en.cppreference.com/w/c/variadic/va_start)。
`delete()` 同樣在物件有指向型態描述符時，會呼叫型態描述符儲存的解構子。下方 `self` 與 `new()` 的 `p` 的功用相同，都是用來取得特定型態的資訊的 (這邊是用來取得特定型態的解構子)。
```C=
void delete (void * self)
{ const struct Class ** cp = self;
if (self && * cp && (* cp) —> dtor)
self = (* cp) —> dtor(self);
free(self);
}
```
其他儲存在型態描述符的方法也是用類似方式呼叫的。在任何情況下，我們都會接收一個 `self` 物件，然後透過型態描述符決定方法最終要呼叫的函式。以下為一個範例:
```C=
int differ (const void * self, const void * b)
{ const struct Class * const * cp = self;
assert(self && * cp && (* cp) —> differ);
return (* cp) —> differ(self, b);
}
```
這個方法能運作同樣是因為我們將型態描述符設為物件的第一個成員，因此能透過 `self` 找到特定型態的對應操作。
* 上述例子有防範 NULL 指標的情況，至於其他情況我們可以透過像是放置一個特殊值 (magic number) 在每個型態描述符的開頭或是判斷 `self` 指標的位址是否在包含所有已知型態描述符的記憶體範圍來避免，但在 chapter 8 我們會看到更嚴謹的檢查。
除此之外，以上這幾個方法 (i.e., `new()`, `delete()` 與 `differ()`) 展示了所謂 *dynamic linkage* 或是 *late binding* 的函式呼叫技巧。作者將這類方法稱為 *selectors*，並提到它們具有以下特點：
* 使函式以類似多型函式的方式運作。儘管函式不是動態連結的，但它會呼叫動態連結的函式做實際上的操作。
* 只要我們實作不同類別時都有實作並設置好類別型態描述符的成員，這些成員就會是一個能應用到任何物件的泛型函式。
類別方法也可以是沒使用動態連結的多型函式，像是下方回傳任意物件大小的 `sizeOf()`:
```C=
size_t sizeOf (const void * self)
{ const struct Class * const * cp = self;
assert(self && * cp);
return (* cp) —> size;
}
```
`sizeOf()` 透過物件自己帶有的型態描述符提取物件的大小資訊並回傳。
## An Application
在開始實作各個介面前，作者首先根據各個介面的功能撰寫了以下測試程式:
```C=
#include "String.h"
#include "new.h"
int main ()
{ void * a = new(String, "a"), * aa = clone(a);
void * b = new(String, "b");
printf("sizeOf(a) == %u\n", sizeOf(a));
if (differ(a, b))
puts("ok");
if (differ(a, aa))
puts("differ?");
if (a == aa)
puts("clone?");
delete(a), delete(aa), delete(b);
return 0;
}
```
以下為測試程式的執行流程:
1. 創建兩個 string 物件，並複製其中一個。
* String.h 會提供 `extern const void * String;` 宣告使我們能取得 `String` 資料型態。
2. 測試 `sizeOf()` 的功能。`sizeOf()` 會顯示 `String` 物件的大小 (不是物件儲存的字串大小，而是物件本身)。
3. 測試 `differ()` 的功能。
4. 測試 `clone()` 的功能
5. 確認複製的物件與被複製的物件並非同一個物件，只是儲存的字串相同。
當程式正確執行時，會產生以下結果:
```C
sizeOf(a) == 8
ok
```
## An Implementation — String
完整的程式碼可參考[此網址](https://github.com/shichao-an/ooc/blob/master/02/String.c)。
透過 String 的型態描述符可以讓我們清楚的知道當要實作新的資料型態時會需要實作哪些功能。
首先，String 的建構子會提取並將傳遞給 `new()` 的文字儲存到 `new()` 配置的 struct String 中，程式實作如下:
```C=
struct String {
const void * class; /* must be first */
char * text;
};
static void * String_ctor (void * _self, va_list * app)
{ struct String * self = _self;
const char * text = va_arg(* app, const char *);
self —> text = malloc(strlen(text) + 1);
assert(self —> text);
strcpy(self —> text, text);
return self;
}
```
解構子需要釋放 string 物件帶有的動態配置的記憶體，由於 `delete()` 只能在 `self` 不是 `NULL` 的時候被呼叫，因此我們不用去做額外檢查。
```C=
static void * String_dtor (void * _self)
{ struct String * self = _self;
free(self —> text), self —> text = 0;
return self;
}
```
`String_clone()` 用於複製字串。之後，原始字串與複製的字串都將被傳遞給 `delete()`，因此我們必須為字串的內容建立一個新的動態複本。這可以簡單地透過呼叫 `new()` 來完成。
```C=
static void * String_clone (const void * _self)
{ const struct String * self = _self;
return new(String, self —> text);
}
```
`String_differ()` 在比較相同的字串物件時回傳 false，比較完全不同種類的物件時回傳 true。當比較兩個不同的字串物件時，則會使用 `strcmp()` 來進行比較。
* 由於同型態的物件都會指向同一個型態描述符，因此我們透過第二個參數的型態描述符來判斷該物件是否為字串物件。
```C=
static int String_differ (const void * _self, const void * _b)
{ const struct String * self = _self;
const struct String * b = _b;
if (self == b)
return 0;
if (! b || b —> class != String)
return 1;
return strcmp(self —> text, b —> text);
}
```
為了讓以上這些方法僅能被 new()，delete() 或其它 *selector* 呼叫，因此所有的方法都使用 `static` 修飾。
`String.c` include 了 `String.h` 與 `new.h` 中的 public 宣告，並且為了正確的初始化型態描述符，`String.c` 也 include 了包含 `struct Class` 定義的 private 標頭 `new.r`。
```C=
/* String.c */
#include "new.r"
static const struct Class _String = {
sizeof(struct String),
String_ctor, String_dtor,
String_clone, String_differ
};
const void * String = & _String;
```
## Another Implementation — Atom
完整的範例程式碼可參考[此網址](https://github.com/shichao-an/ooc/blob/master/02/Atom.c)。
為了進一步展示建構子與解構子可以做的變化，作者實作了一個環形鏈結序列 *atoms*。每個 *atom* 會儲存一個唯一的字串，並透過比較指標來實現低成本的 `differ()` 實作，但建構與解構的成本較高，因為這些操作需要維護環狀串列以及一個追蹤 *atom* 被複製次數的計數器。
```C=
struct String {
const void * class; /* must be first */
char * text;
struct String * next;
unsigned count;
};
static struct String * ring; /* of all strings */
static void * String_clone (const void * _self)
{ struct String * self = (void *) _self;
++ self —> count;
return self;
}
```
建構子儲存字串前會先檢查序列中是否已儲存過相同字串。如果找到儲存同樣字串的 *atom*，則增加這個 *atom* 的計數器，釋放 self 物件並回傳找到的 *atom*。反之新增一個字串物件到環狀序列並將其計數器設為 1。以下程式碼會新增到 `String_ctor()` 的開頭:
```C=
if (ring)
{ struct String * p = ring;
do
if (strcmp(p —> text, text) == 0)
{ ++ p —> count;
free(self);
return p;
}
while ((p = p —> next) != ring);
}
else
ring = self;
self —> next = ring —> next, ring —> next = self;
self —> count = 1;
```
解構子會將傳入的 *atom* 的計數器減 1，並在計數器的值仍大於 0 的時候回傳 NULL，反之將傳入的 *atom* 從鏈結串列中移除。以下程式碼會新增到 `String_dtor()` 開頭:
```C=
if (—— self —> count > 0)
return 0;
assert(ring);
if (ring == self)
ring = self —> next;
if (ring == self)
ring = 0;
else
{ struct String * p = ring;
while (p —> next != self)
{ p=p —> next;
assert(p != ring);
}
p —> next = self —> next;
}
```
需注意到，*atoms* 的實作方式會使複製的字串物件與原本的字串物件相同，使測試程式的輸出為下:
```bash
sizeOf(a) == 16
ok
clone?
```
## Summary
這個章節介紹了如何透過指標使程式執行時根據物件的型態決定要呼叫的函式。這是透過讓每個物件的第一個成員都是指向一個型態描述符的指標實現的，而型態描述符中儲存了指向適用於該型態的方法的指標。
這種設計引入了物件導向程式設計的概念。共用相同型態描述符的物件可以視為屬於同一類別 (*class*)，這些物件稱為實例 (*instances*)，而適用於特定類別的函式則稱為方法 (*methods*)。負責根據物件型態動態決定要呼叫哪個方法的函式則被稱為 *selector*。
*Selector* 結合動態連結可以讓同名的函式根據不同類別的參數執行不同的方法，這種特性被稱為多型 (*polymorphism*)。多型函式提高了程式的抽象化程度。例如，函式 `differ()` 的用途是比較兩個物件，我們只需了解其功能而不用記住對於不同類別的物件需要使用哪個 `differ()`。
Sign in with Wallet
Connect another wallet