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 من بين العديد من التطبيقات الأخرى. يتوفر أيضًا إصدار أقدم من المعيار.
