klib
1.0.0
Klib 是一個獨立的輕量級 C 函式庫，在 MIT/X11 授權下分發。除標準C 庫外，大多數元件都獨立於外部庫，並且彼此獨立。要使用該庫的元件，您只需將幾個檔案複製到原始程式碼樹中，而不必擔心庫依賴性。
Klib 致力於提高效率並減少記憶體佔用。就速度和記憶體使用而言，某些元件（例如 khash.h、kbtree.h、ksort.h 和 kvec.h）是所有程式語言中類似演算法或資料結構的最有效實作。
此處提供了新文檔，其中包含此自述文件中的大部分資訊。
為了實作通用容器，klib 廣泛使用 C 巨集。為了使用這些資料結構，我們通常需要透過擴展一個長宏來實例化方法。這使得原始程式碼看起來不尋常甚至醜陋，並且增加了調試的難度。不幸的是，對於缺乏模板的 C 語言的高效泛型編程，使用巨集是唯一的解決方案。只有使用巨集，我們才能編寫一個通用容器，一旦實例化，它就可以與特定類型的容器競爭效率。 C 中的一些通用函式庫（例如 Glib）使用void*類型來實作容器。這些實作通常比 klib 更慢並且使用更多記憶體（請參閱此基準測試）。
為了有效地使用 klib，了解它如何實現泛型程式設計非常重要。我們將以哈希表庫為例：
#include "khash.h"
KHASH_MAP_INIT_INT(m32, char) // instantiate structs and methods
int main() {
int ret, is_missing;
khint_t k;
khash_t(m32) *h = kh_init(m32); // allocate a hash table
k = kh_put(m32, h, 5, &ret); // insert a key to the hash table
if (!ret) kh_del(m32, h, k);
kh_value(h, k) = 10; // set the value
k = kh_get(m32, h, 10); // query the hash table
is_missing = (k == kh_end(h)); // test if the key is present
k = kh_get(m32, h, 5);
kh_del(m32, h, k); // remove a key-value pair
for (k = kh_begin(h); k != kh_end(h); ++k) // traverse
if (kh_exist(h, k)) // test if a bucket contains data
kh_value(h, k) = 1;
kh_destroy(m32, h); // deallocate the hash table
return 0;
}
在此範例中，第二行實例化一個哈希表，其中unsigned作為鍵類型， char作為值類型。 m32命名了這種類型的雜湊表。與該名稱關聯的所有類型和函數都是宏，稍後將對此進行解釋。宏kh_init()啟動一個雜湊表，然後kh_destroy()釋放它。 kh_put()插入一個鍵並傳回哈希表中的迭代器（或位置）。 kh_get()和kh_del()分別取得一個鍵和刪除一個元素。宏kh_exist()測試迭代器（或位置）是否已填入資料。
一個迫在眉睫的問題是這段程式碼看起來不像一個有效的 C 程式（例如缺少分號、對明顯函數呼叫的賦值以及明顯未定義的m32 「變數」）。為了理解為什麼程式碼是正確的，讓我們進一步研究khash.h的原始程式碼，其框架如下：
#define KHASH_INIT(name, SCOPE, key_t, val_t, is_map, _hashf, _hasheq)
typedef struct {
int n_buckets, size, n_occupied, upper_bound;
unsigned *flags;
key_t *keys;
val_t *vals;
} kh_##name##_t;
SCOPE inline kh_##name##_t *init_##name() {
return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));
}
SCOPE inline int get_##name(kh_##name##_t *h, key_t k)
...
SCOPE inline void destroy_##name(kh_##name##_t *h) {
if (h) {
free(h->keys); free(h->flags); free(h->vals); free(h);
}
}
#define _int_hf(key) (unsigned)(key)
#define _int_heq(a, b) (a == b)
#define khash_t(name) kh_##name##_t
#define kh_value(h, k) ((h)->vals[k])
#define kh_begin(h, k) 0
#define kh_end(h) ((h)->n_buckets)
#define kh_init(name) init_##name()
#define kh_get(name, h, k) get_##name(h, k)
#define kh_destroy(name, h) destroy_##name(h)
...
#define KHASH_MAP_INIT_INT(name, val_t)
KHASH_INIT(name, static, unsigned, val_t, is_map, _int_hf, _int_heq)
KHASH_INIT()是一個巨大的宏，定義了所有的結構和方法。當這個巨集被呼叫時，它裡面的所有程式碼都會被C預處理插入到它被呼叫的地方。如果多次呼叫巨集，則會插入程式碼的多個副本。為了避免具有不同鍵值類型的雜湊表的命名衝突，該庫使用標記串聯，這是一種預處理器功能，我們可以根據巨集的參數替換部分符號。最後，C 預處理器將產生以下程式碼並將其提供給編譯器（宏kh_exist(h,k)有點複雜，為簡單起見未展開）：
typedef struct {
int n_buckets, size, n_occupied, upper_bound;
unsigned *flags;
unsigned *keys;
char *vals;
} kh_m32_t;
static inline kh_m32_t *init_m32() {
return (kh_m32_t*)calloc(1, sizeof(kh_m32_t));
}
static inline int get_m32(kh_m32_t *h, unsigned k)
...
static inline void destroy_m32(kh_m32_t *h) {
if (h) {
free(h->keys); free(h->flags); free(h->vals); free(h);
}
}
int main() {
int ret, is_missing;
khint_t k;
kh_m32_t *h = init_m32();
k = put_m32(h, 5, &ret);
if (!ret) del_m32(h, k);
h->vals[k] = 10;
k = get_m32(h, 10);
is_missing = (k == h->n_buckets);
k = get_m32(h, 5);
del_m32(h, k);
for (k = 0; k != h->n_buckets; ++k)
if (kh_exist(h, k)) h->vals[k] = 1;
destroy_m32(h);
return 0;
}
這就是我們所知道的C程式。
從這個例子中，我們可以看出巨集和C預處理器在klib中扮演關鍵角色。 Klib 速度快的部分原因是編譯器在編譯時知道鍵值類型，並且能夠將程式碼最佳化到與特定類型程式碼相同的層級。用void*編寫的通用函式庫不會獲得這樣的效能提升。
在實例化時大量插入程式碼可能會讓我們想起C++在使用STL/boost時的緩慢編譯速度和巨大的二進位大小。由於程式碼量小且元件獨立，Klib 在這方面要好得多。插入幾百行程式碼不會使編譯明顯變慢。
void*進行泛型程式設計可能效率低下的部落格文章。kvec.h效能的部落格文章。khash.h和kbtree.h在許多其他實作中的效能。也可以使用舊版本的基準測試。
