klib

Klib: a Generic Library in C Overview Klib is a standalone and lightweight C library distributed under MIT/X11 license. Most components are independent of external libraries, except the standard C library, and independent of each other. To use a component of this library, you only need to copy a couple of files to your source code tree without worrying about library dependencies. Klib strives for efficiency and a small memory footprint. Some components, such as khash.h, kbtree.h, ksort.h and kvec.h, are among the most efficient implementations of similar algorithms or data structures in all programming languages, in terms of both speed and memory use. A new documentation is available here which includes most information in this README file. Common components khash.h: generic hash table with open addressing. kbtree.h: generic search tree based on B-tree. kavl.h: generic intrusive AVL tree. ksort.h: generic sort, including introsort, merge sort, heap sort, comb sort, Knuth shuffle and the k-small algorithm. kseq.h: generic stream buffer and a FASTA/FASTQ format parser. kvec.h: generic dynamic array. klist.h: generic single-linked list and memory pool. kstring.{h,c}: basic string library. kmath.{h,c}: numerical routines including MT19937-64 pseudorandom generator, basic nonlinear programming and a few special math functions. ketopt.h: portable command-line argument parser with getopt_long-like API. Components for more specific use cases ksa.c: constructing suffix arrays for strings with multiple sentinels, based on a revised SAIS algorithm. knetfile.{h,c}: random access to remote files on HTTP or FTP. kopen.c: smart stream opening. khmm.{h,c}: basic HMM library. ksw.(h,c}: Striped Smith-Waterman algorithm. knhx.{h,c}: Newick tree format parser. Methodology For the implementation of generic containers, klib extensively uses C macros. To use these data structures, we usually need to instantiate methods by expanding a long macro. This makes the source code look unusual or even ugly and adds difficulty to debugging. Unfortunately, for efficient generic programming in C that lacks template, using macros is the only solution. Only with macros, we can write a generic container which, once instantiated, compete with a type-specific container in efficiency. Some generic libraries in C, such as Glib, use the void* type to implement containers. These implementations are usually slower and use more memory than klib (see this benchmark). To effectively use klib, it is important to understand how it achieves generic programming. We will use the hash table library as an example: #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; } In this example, the second line instantiates a hash table with unsigned as the key type and char as the value type. m32 names such a type of hash table. All types and functions associated with this name are macros, which will be explained later. Macro kh_init() initiates a hash table and kh_destroy() frees it. kh_put() inserts a key and returns the iterator (or the position) in the hash table. kh_get() and kh_del() get a key and delete an element, respectively. Macro kh_exist() tests if an iterator (or a position) is filled with data. An immediate question is this piece of code does not look like a valid C program (e.g. lacking semicolon, assignment to an apparent function call and apparent undefined m32 'variable'). To understand why the code is correct, let's go a bit further into the source code of khash.h, whose skeleton looks like: #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() is a huge macro defining all the structs and methods. When this macro is called, all the code inside it will be inserted by the C preprocess to the place where it is called. If the macro is called multiple times, multiple copies of the code will be inserted. To avoid naming conflict of hash tables with different key-value types, the library uses token concatenation, which is a preprocessor feature whereby we can substitute part of a symbol based on the parameter of the macro. In the end, the C preprocessor will generate the following code and feed it to the compiler (macro kh_exist(h,k) is a little complex and not expanded for simplicity): typedef struct { int n_buckets, size, n_occupied,