Statement Expression – Statements and Declarations in Expressions

在 linux kernel 或是一些 open source 專案中,經常看到許多高深莫測的 macro 用法,其中 Linux Kernel 中最經典的 macro 之一就是 container_of ,它看起來很奇怪,因為他使用了 { 和 } 包起來,看起來像是一個 function ,但這個 function 並沒有回傳任何值。

看完之後,你可能仍然不知道這個 macro 是在做什麼,想要真正理解這個 macro,你必須先了解什麼是「Statement Expression 」。

閱讀全文〈Statement Expression – Statements and Declarations in Expressions〉

設計一個 hash table – 陪你刷題

Leetcode 第 705 和 706 題要求你設計一個 hash set 和 hash map,在 C++ 中可以使用 unordered_set 和 unordered_map,或者在輸入資料範圍不大的情況下,可以直接用陣列當作 hash table。但這題不是要求你直接使用現成的資料結構,而是讓你思考如何設計一個 hash table,這促使我想寫下這篇文章,來探討如何設計 Hash Table。

閱讀全文〈設計一個 hash table – 陪你刷題〉

前置引用 forward reference 和前置宣告 forward declaration

Forware reference

C 語言有一個傳統,所有的 identifier 都要先宣告才能使用,這是因為早期電腦的記憶體資源並不充裕,所以 c 是採取每個 source code 只編譯一次 (one-pass compiler) 的方式,宣告是為了給 compiler 看的,讓他知道該 identifier 的型別,以便做語法檢查。

在 C 語言中,有三個例外可以不用先宣告後引用,這樣的行為稱為 forward reference 。

  1. Implicit declaration : C99/C11/C++ 標準已禁止
  2. goto 所接的 identifier
  3. Incomplete type :在被定義完整之前就用於某些特定用途

C 語言中除了 object type 和 function type ,還有 incomplete type ,常見的 incomplete type 有:

  • void
  • An array type of unknown size : int a[]
  • A structure or union type of known content

前面兩點很常見,關於第三點,看以下例子:

struct LIST_NODE {
    struct LIST_NODE *next;
    int data;
};

struct LIST_NODE 完成宣告之前,就直接在宣告內又定義了 struct LIST_NODE 型別的 pointer ,這樣是不會有編譯錯誤的。

再來看以下這段程式碼:

struct LIST_NODE {
    struct LIST_NODE *next;
    struct LIST_NODE node;
    int data;
};

編譯器卻會給出錯誤訊息:

Error: field ‘node’ has incomplete type

要理解這個錯誤,必須先了解一個事實,當我們對 identifier 做 forward reference 時,一般只關注 identifier 的型別 (data type),不在乎其大小或值。換句話說,當對一個 incomplete type 做 forward reference 時,只能使用該 identifer 的型別,其他的屬性像數值、成員、大小等,是不能使用的。

再回到前面的例子中, struct LIST_NODE *next; 單純只用了型別,指針本身不論是什麼型別,大小都是固定的,因此 compiler 也不會報出錯誤訊息;但當 compiler 看到 struct LIST_NODE node; ,需要考慮變數 node 的大小,但是 struct LIST_NODE 根本還沒定義完成,compiler 只好報出錯誤。

Forward declaration

struct animal;

struct dog {
    struct animal *t;
    int height;
    int weight;
}

struct dog 內使用 struct animal 定義一個 pointer ,為了讓 compiler 知道這個 pointer 的 data type ,在程式碼前面就必須先宣告 struct animal

這樣子的用法在 linux kernel 中的 header file 常常可見,以前在 trace code 時候常常不懂為什麼會突然宣告這個變數,其實它的用圖就是為了規避 compiler 的檢查。

當然可能會有人覺得為什麼不把整個 data type 定義出來或是直接 include 該變數定義所在的 header file? 但如果該 header file 有更動的話,會導致 include 該 header file 的 source code 也需要重新編譯,這將造成更長的編譯時間,在龐大的 Linux kernel 裡就是大量採用 forward decalartion 技巧。
未來在面對這類情況下,更好的方法應該是透過 forware declaration 來取代 inculde header file 這個動作。

Reference

  1. When can I use a forward declaration? - stackoverflow

Updated on 2022-12-01 23:34:09 星期四