# 第二章 動態鏈接和泛函數
> 來源：http://blog.csdn.net/besidemyself/article/details/6387915
> 譯者：[besidemyself](http://my.csdn.net/besidemyself)
## 2.1 構造器和析構器
讓我們來實現一個簡單的字符串數據類型，這個數據類型將在接下來的集合中用到。對于新的字符串，我們分配一個動態緩存來保存字文本。當這個字符串被刪除時，我們將回收其所占用的內存緩沖。
`new()` 負責創建一個對象，`delete()` 必須回收這個對象所占用的資源。 `new()` 預先知道它所創建的資源的類型，因為它的第一個參數將傳遞對這個對象的描述。基于這個參數，我們可以使用一系列的判斷語句`if` 來處理單個不同的要創建的對象。這樣做的缺點是 `new()` 得完全包含對每個支持的對象要處理的代碼。
現在 `new()` 擁有一個更大的問題。它負責創建對象并且返回對象的指針，這個指針被傳遞到`delete()` ，也就是說，`new()` 必須在每個對象中安裝特定的析構器信息。最明顯的應用是使用一個指針，指向特定的析構器，這個析構器是類型描述符的一部分，被傳進 `new()` 。到目前為止，我們需要像如下的聲明:
```c
struct type{
size_t size; /*size of an object*/
void (*dtor)(void*); /*destructor*/
};
struct String{
char *text; /*dynamic string*/
const void* destroy; /*locate destructor*/
};
struct Set{
...information...
const void * destroy; /*locate destructor*/
};
```
似乎我們又有另外一個問題：在新的對象中，有人需要把析構器指針 `dtor`從類型描述中拷貝到 `destroy` 中。而且這樣的拷貝在不同的對象的類中會放到不同的位置。
初始化工作是 `new()` 的一部分，不同的類型會要求`new()` 干不同的工作——`new()` 可能需要不同的參數來處理不同的類型：
```c
new(Set); /*make a set*/
new(String,"text"); /*make a string*/
```
對于初始化我們使用另外一個指定類型的功能函數，這個函數我們稱它為構造器。因為構造器和析構器都是類型指定的，不需要改變，我們把他們當成類型描述的一部分傳遞給 `new()` 函數。
注意，對于一個對象自身來說構造器和析構器并不是用來擔當獲取和釋放內存的責任——這是`new()` 和 `delete()` 的工作。構造器被 `new()` 調用僅僅用來初始化 `new()` 所分配的內存。對于一個字符串，這需要涉及需要另外一塊內存存儲文本，但是對于`struct String` 自身的內存卻是使用 `new()` 來分配的。這個空間接下來會被`delete(`) 所釋放。然而 `delete()`首先 會調用析構器，析構器是對構造器所做的初始化進行反向操作。這步完成后才調用`delete()` 釋放`new()` 所分配的內存。
## 2.2 方法，消息，類和對象
`delete()` 必須能夠在不知道對象類型的情況下定位析構器。因此修正了2.1 部分的聲明，我們必須堅持指針被用來定位析構器，這個指針必須放到所有對象的開始處傳進`delete()` 中，而不管他們的類型是什么。
這個指針應該指向什么呢 ？如果所有我們所擁有的是一個對象的地址，那么對于一個對象來說，指針給了我們訪問指定類型的對象信息，就像對象的析構函數一樣。似乎很可能我們將要創造一個類型指定的功能如一個函數用來顯示對象，或者一個對象的比較函數`differ()` ，或一個函數`clone()` 去創建一個對象的完全拷貝。因此我們將使用一個指針指向函數指針表。
仔細看，我們會意識到這個表必須是類型描述的一部分，被傳進 `new()` , 顯然的解決問題的答案就是讓對象指向一個類型的完全描述：
```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*/
...
};
```
每個對象將以一個指針開始，這個指針向對象的類型描述表，通過這個類型描述表，我們就可以定位一個對象的類型指定信息：`.size` 是`new()` 所分配的對象所占用內存的大小；`.dtor` 指向被`delete()`（`delete` 用來銷毀對象） 所調用的析構器；而 `.differ` 指向一個函數，這個函數用于比較對象。
繼續往下看，我們會注意到，每個功能都是以對象而存在的，通過對象來選擇這些功能。只有構造函數要處理部分初始化內存區域工作。我們都叫這些功能為一個對象的方法。調用一個對象的方法就是處理一則消息，我們使用參數`self` 來標記消息接收的對象。因為我們使用基本的Ｃ函數功能，`self` 是不需要作為第一個參數而傳進的。
多個對象共享相同的類型描述符，也就是說，他們需要相同數量大小的內存空間，可用于相同的方法。我們稱所有擁有相同的類型描述符的對象為一類；單獨的對象被稱為類的實例。到目前為止，一個類，一個抽象數據類型，可能的值與操作結合的集合，即，一個數據類型，這些是極其相似的。
一個對象是一個類的實例，也就是說，它擁有一個描述，這個描述被`new()` 所分配的內存所指示，并且這個描述被類的方法操作。普遍來說，一個對象是特殊數據類型的值。
## 2.3 選擇器，動態鏈接，多態
誰來郵遞消息呢？ 構造器被 `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;
}
```
在一個對象的起始地方，`struct Class` 指針的存在是極其重要的。這也是我們在 `new()` 中初始化它的原因：
如上圖右邊的類型描述 `class` 在編譯的時候已經被初始化。對象是在運行時被創建的，接下來圖中的虛線關聯才被插入。在語句：
```c
* (const struct Class **) p = class;
```
中，`p`指向對象的內存區域的起始位置。我們對`p`進行了強制類型轉換，`p`把對象的起始位置當成一個指針，指向`struct Class`，即把參數`class` 設置為這個指針的值。
接下來，若構造器是類型描述的一部分，我們調用它，并把其返回值做為 `new()` 的結果，即作為一個新的對象返回。2.6 部分列出一個很聰明的構造器，由于它聰明，所以能夠對它自己的內存管理作出決策。
注意啦，只有明確的可見函數如 new() 能擁有可變的參數列表。參數列表被 `va_list` 的變量 `ap` 所訪問，`ap` 被一個宏 `va_start()` 初始化，這個宏在`stdarg.h` 頭文件。`new()`僅僅能夠把整個參數列表傳進構造器中；因此，`.ctor` 也被聲明成擁有 `va_list` 的參數，而不是它私有的參數列表。由于我們接下來要在好多函數中共享源參數列表，因此我們只傳遞 `ap`的地址到構造器中——當它返回時，`ap` 指向參數列表的第一個參數，而參數列表本身不會被改變。
`delete()` 假設每個對象，也就是說，每個非空指針，指向一個類型描述。如果類型描述的析構器存在，則調用它。這里，`self` 扮演前面 `p` 的角色。我們使用局部變量`cp` 來進行強制類型轉換，并從`self` 中獲得我們所需要的信息。
```c
void delete (void * self)
{
const struct Class ** cp = self;
if (self && * cp && (* cp) -> dtor){
self = (* cp) -> dtor(self);
}
free(self);
}
```
析構器，在上述`delete()`中，也會獲得一次把他的返回值傳進`free()` 的機會，如果構造器試著去欺騙，則析構器會有更改的機會，參看2.6部分。如果一個對象在調用`delete()` 的時候不想被刪除，則可在他的析構器中返回一個空指針。
所有其他的方法都存儲在類型描述中，并以相似的方式被調用。在每個例子中，我們有一個單獨的接收對象`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` ，而這個`*self` 會隱藏在任意的指針`self`下面。此時此刻，至少，我們會對空指針很警惕。在每個類型描述的起始，我們將存放一個“魔法數字”，或甚至把地址或所有已知類型的地址范圍與 `*self` 相比較，但是，在第八章會看到，我們將做更嚴格的檢查。
不管怎么說，`differ()` 列舉出了函數調用技術怎么被動態鏈接或后期鏈接調用的原因：即只要我們能夠在一開始擁有一個正確的類型描述指針，那么我們就可以對任意的對象使用`differ()` 調用。這個函數實際上被調用的時機是盡可能的晚的——即僅僅在實際執行期間調用，而不是之前調用。
我們可以稱`differ()` 為一個選擇器。它是多態功能的一個例子，也就是說，一個函數能夠接受不同的參數類型，且表現不同，并且這種現象是基于他們的參數類型。一旦我們實現了更多的類時，這些類在他們的描述符中都包含 `.differ` ，則可稱 `differ()` 為一個泛函數，且在這些類中能夠被應用于任何對象。
我們可以把這個選擇器當成方法，方法自己本身不會動態鏈接，但仍然能夠像多態函數一樣的表現，因為它能讓動態的連接的函數做他們真實的事情。
多態機制實際已經嵌入到很多編程語言中，例如：如在Pascal（一種編程語言）中，`write()` 函數會根據參數類型不同進行不同的處理。在C++中，操作符 + 如果被不同的類型值如整型，指針，浮點指針調用，將產生不同的結果。這個現象被稱作重載，即：參數類型和操作符名結合起來決定操作結果。相同的操作符與不同的參數類型結合將產生不同的響應。
這里并沒有明顯的差異。因為動態連接，`differ()` 的表現更像一個重載函數，而且C的編譯器也能夠使得 + 看起來像多態函數——至少對于內嵌的數據類型來說。然而，C編譯器能夠根據對 + 操作符的不同使用而產生不同的返回類型，但是函數`differ()` 依靠它的參數類型只能返回相同的類型。
很多方法在不需要動態連接的情況下能夠實現多態。例如，函數 `sizeOf()` 返回任意類型的對象的大小。
```c
size_t sizeOf (const void * self)
{
const struct Class * const * cp = self;
assert(self && * cp);
return (* cp) -> size;
}
```
所有的對象都攜帶它們的描述符，我們可以使用描述符來獲得對象的大小。注意如下的不同之處：
```c
void* s=new(string, "text");
assert(sizeof s!=sizeOf(s));
```
`sizeof` 是C語言的操作符，用于在運行時以字節的個數返回參數的大小。而 `sizeOf()` 是我們實現的多態函數，它的參數指向一個對象，返回在運行時對象所占用的字節大小。
## 2.4 應用
然而我們還沒有實現一個字符串類，我們仍然做好了一個簡單的測試程序的準備。`String.h` 定義了抽象數據類型：
```c
extern const void * String;
```
對于所有的對象，我們的方法都是相似的。我們向內存管理頭文件`new.h` 中增加在1.4 部分介紹的聲明：
```c
void * (* clone) (const void * self);
int (* differ) (const void * self, const void * b);
size_t sizeOf(const void* self);
```
前兩個源型聲明稱為選擇器，它們在相關的`struct Class` 中聲明。下面是其應用：
```c
int main ()
{
void * a = new(String, "a"), * aa = clone(a);
void * b = new(String, "b");
printf("sizeOf(a) == %lu/n", (unsigned long)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;
}
```
我們創建了兩個字符串，并且拷貝了其中一份。我們打印出`String` 對象所占用的大小——并不是對象的控制文本所占用的大小。最終，檢查拷貝的對象與對象本身相等，但并不相同，最后再次刪除字符串對象。如果所有的程序均以實現，程序的運行結果如下：
```c
sizeOf(a)==8
ok
```
## 2.5 實現——`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;
}
```
在構造器中，我們緊緊需要初始化 .text 因為 new() 已經建立了 .class 。
析構器釋放被字符串控制的動態內存。由于 delete() 只在 self 為非空的情況下調用 析構器，所以我們不需要做其他參數檢查，代碼如下：
```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` 如果我們比較同一個字符串對象，則返回假，若果我們比較兩個不同的字符串對象，返回真，如果我們想比較字符串文本的差異可試著使用`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);
}
```
類型描述符是獨一無二的——這里我們要確定一個因素，即：我們的第二個參數是否為字符串文本。
所有這些方法都應該使用關鍵字`static` 來修飾。因為這些方法只能通過 `new()` 和`delete()` ，或者選擇器調用。對于通過類型描述符的方式指定的選擇器都是可用的方法。
```c
#include “new.r”
static const struct Class _String = {
sizeof(struct String),
String_ctor, String_dtor,
String_clone, String_differ
};
const void * String = & _String;
```
在String.h 中聲明String.c 中包含的公有方法，new.h 中聲明new.c中包含的公有方法。以便于正確的初始化類型描述符，這里也包含了一個私有的頭文件 new.r ，此文件中包含了2.2 部分定義的 struct Class 類型描述。
## 2.6 另一種實現——原子
為了列舉我們通過構造器和析構器到底能夠做什么，我們實現了原子，所謂原子就是一個唯一的字符竄對象；如果兩個原子包含相同的字符竄，則他們是相等的。原子是很容易比較的：如果兩個參數的指針不同，則 `differ()` 返回真。原子的構造和銷毀要付出一定的代價；我們為所有的原子維持了一個循環鏈表，并計數原子被克隆的次數，如下：
```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;
}
```
所有的原子的循環鏈表被`ring` 所標記，通過它的成員 `.next` 來擴展，并使用構造器和析構器來維持。在構造器保存文本之前，首先會遍歷鏈表是否有相同的文本已經存在，如下的代碼插入到`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;
```
如果我們找到了相同文本的原子，則增加它的引用計數`count`值，釋放新的對象`self` 返回當前找的的原子指針`p` 。否則我們向循環鏈表中插入一個新字符串對象并設置其引用計數為`count` 為1。
析構器防止刪除引用計數為非零的原子。如下的代碼被插入到`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;
}
```
如果對引用計數的減1操作計數扔為正數，則返回一個空指針，以便于 `delete()` 手下留情。否則如果我們的字符串對象是最后一個對象我們清除循環鏈表標記符，否則從鏈表中刪除我們的字符串。
把上述的實現加入到 2.4 的程序中，注意，對一個字符串對象的克隆此時為源字符串對象本身，運行結果如下：
```c
sizeOf(a)==16
ok
clone?
```
##2.7 總結
給一個指針指定一個對象，動態連接使我們找到了類型指定的函數功能：每個對象都會以一個描述符開始，這個描述符包含了指針，指向對象的可用函數指針表。尤其是，一個描述符包含一個指向構造器的指針，這個構造器用來初始化對象所關聯的內存區域，另外這個指針還指向一個析構器，析構器會在刪除對象之前回收對象所擁有的資源。
我們稱所有的對象所共享的描述符為一個類。而對象是類的實例，對于對象指定類型的功能被稱作對象的方法，而消息被這些功能函數所調用。對于一個對象，我們使用選擇器功能去定位和調用動態連接的方法。
通過選擇器和動態連接使得相同函數名對于不同的類而產生不同的結果。這樣的函數被稱為是多態的。
多態功能是非常有用的。他們提供了一種概念上的抽象：`differ()` 可比較任何兩個對象——我們不需要銘記`differ()` 針對具體的情形是否可用。一個很容易并非常方便的調試工具就是多態函數 `store()` ，可在一個文件描述符上顯示任何對象。
## 2.8 練習
了解了多態的功能后，我們需要使用動態連接來實現`Object` 和 `Set`。這對于 `Set` 來說是比較困難的。我們不再記錄一個元素屬于哪個集合。
對于字符串來說，似乎有更多的方法去實現。我們需要知道字符串的長度，我們更想為一個對象從新設置它的字符串文本，我們應該能打印字符串文本。如果我們樂意去處理子串，將會更加有趣味。
原子是如此有效的，我們可使用一個哈希表來跟蹤它，那么一個原子的值能否被改變呢？
`String_clone()` 呈現出一個微妙的問題：在這個函數中，`String` 的值似乎應該與`self->class` 相同。我們向 `new()` 中傳遞的參數會有任何變化嗎？
