klib
1.0.0
Klib adalah perpustakaan C mandiri dan ringan yang didistribusikan di bawah lisensi MIT/X11. Sebagian besar komponen tidak bergantung pada pustaka eksternal, kecuali pustaka C standar, dan tidak bergantung satu sama lain. Untuk menggunakan komponen perpustakaan ini, Anda hanya perlu menyalin beberapa file ke pohon kode sumber tanpa mengkhawatirkan ketergantungan perpustakaan.
Klib mengupayakan efisiensi dan jejak memori yang kecil. Beberapa komponen, seperti khash.h, kbtree.h, ksort.h dan kvec.h, adalah implementasi paling efisien dari algoritma atau struktur data serupa di semua bahasa pemrograman, baik dari segi kecepatan dan penggunaan memori.
Dokumentasi baru tersedia di sini yang mencakup sebagian besar informasi dalam file README ini.
Untuk implementasi container generik, klib banyak menggunakan makro C. Untuk menggunakan struktur data ini, kita biasanya perlu membuat instance metode dengan memperluas makro yang panjang. Hal ini membuat kode sumber terlihat tidak biasa atau bahkan jelek dan menambah kesulitan dalam proses debug. Sayangnya, untuk pemrograman generik yang efisien di C yang tidak memiliki template, menggunakan makro adalah satu-satunya solusi. Hanya dengan makro, kita dapat menulis container generik yang, setelah dibuat instance-nya, bersaing dengan container tipe spesifik dalam hal efisiensi. Beberapa perpustakaan umum di C, seperti Glib, menggunakan tipe void* untuk mengimplementasikan container. Implementasi ini biasanya lebih lambat dan menggunakan lebih banyak memori daripada klib (lihat benchmark ini).
Untuk menggunakan klib secara efektif, penting untuk memahami cara klib mencapai pemrograman generik. Kami akan menggunakan perpustakaan tabel hash sebagai contoh:
#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;
}
Dalam contoh ini, baris kedua membuat instance tabel hash dengan unsigned sebagai tipe kunci dan char sebagai tipe nilai. m32 memberi nama jenis tabel hash seperti itu. Semua tipe dan fungsi yang terkait dengan nama ini adalah makro, yang akan dijelaskan nanti. Makro kh_init() memulai tabel hash dan kh_destroy() membebaskannya. kh_put() menyisipkan kunci dan mengembalikan iterator (atau posisi) di tabel hash. kh_get() dan kh_del() masing-masing mendapatkan kunci dan menghapus elemen. Makro kh_exist() menguji apakah iterator (atau posisi) diisi dengan data.
Pertanyaan langsungnya adalah potongan kode ini tidak terlihat seperti program C yang valid (misalnya tidak memiliki titik koma, penugasan ke pemanggilan fungsi yang jelas , dan 'variabel' m32 yang tidak terdefinisi ). Untuk memahami mengapa kode tersebut benar, mari kita bahas lebih jauh kode sumber khash.h , yang kerangkanya terlihat seperti:
#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() adalah makro besar yang mendefinisikan semua struct dan metode. Ketika makro ini dipanggil, semua kode di dalamnya akan dimasukkan oleh preproses C ke tempat pemanggilannya. Jika makro dipanggil beberapa kali, banyak salinan kode akan disisipkan. Untuk menghindari konflik penamaan tabel hash dengan tipe nilai kunci yang berbeda, perpustakaan menggunakan penggabungan token, yang merupakan fitur praprosesor dimana kita dapat mengganti bagian simbol berdasarkan parameter makro. Pada akhirnya, praprosesor C akan menghasilkan kode berikut dan memasukkannya ke kompiler (makro kh_exist(h,k) sedikit rumit dan tidak diperluas untuk kesederhanaan):
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;
}
Ini adalah program C yang kita tahu.
Dari contoh ini, kita dapat melihat bahwa makro dan praprosesor C memainkan peran penting dalam klib. Klib cepat sebagian karena kompiler mengetahui tipe nilai kunci pada waktu kompilasi dan mampu mengoptimalkan kode ke level yang sama dengan kode tipe spesifik. Pustaka generik yang ditulis dengan void* tidak akan mendapatkan peningkatan kinerja seperti itu.
Memasukkan kode secara besar-besaran saat instantiasi mungkin mengingatkan kita akan kecepatan kompilasi C++ yang lambat dan ukuran biner yang besar ketika STL/boost digunakan. Klib jauh lebih baik dalam hal ini karena ukuran kodenya yang kecil dan independensi komponennya. Memasukkan beberapa ratus baris kode tidak akan membuat kompilasi menjadi lebih lambat.
void* untuk pemrograman generik mungkin tidak efisien.kvec.h .khash.h dan kbtree.h di antara banyak implementasi lainnya. Benchmark versi lama juga tersedia.
