klib
1.0.0
Klib เป็นไลบรารี C แบบสแตนด์อโลนและมีน้ำหนักเบาเผยแพร่ภายใต้ลิขสิทธิ์ MIT/X11 ส่วนประกอบส่วนใหญ่ไม่ขึ้นอยู่กับไลบรารีภายนอก ยกเว้นไลบรารี C มาตรฐาน และเป็นอิสระจากกัน หากต้องการใช้ส่วนประกอบของไลบรารีนี้ คุณจะต้องคัดลอกไฟล์สองสามไฟล์ไปยังแผนผังซอร์สโค้ดของคุณโดยไม่ต้องกังวลเกี่ยวกับการขึ้นต่อกันของไลบรารี
Klib มุ่งมั่นเพื่อประสิทธิภาพและขนาดหน่วยความจำขนาดเล็ก ส่วนประกอบบางอย่าง เช่น khash.h, kbtree.h, ksort.h และ kvec.h เป็นหนึ่งในการใช้งานที่มีประสิทธิภาพมากที่สุดของอัลกอริธึมหรือโครงสร้างข้อมูลที่คล้ายกันในภาษาการเขียนโปรแกรมทั้งหมด ทั้งในแง่ของความเร็วและการใช้หน่วยความจำ
มีเอกสารประกอบใหม่อยู่ที่นี่ ซึ่งรวมถึงข้อมูลส่วนใหญ่ในไฟล์ README นี้
สำหรับการใช้งานคอนเทนเนอร์ทั่วไป 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.hkhash.h และ kbtree.h รวมถึงการใช้งานอื่นๆ อีกมากมาย เกณฑ์มาตรฐานเวอร์ชันเก่าก็มีให้ใช้งานเช่นกัน
