c_cpp/lib/klib/README.md

   1 # Klib: a Generic Library in C
   2
   3 ## <a name="overview"></a>Overview
   4
   5 Klib is a standalone and lightweight C library distributed under [MIT/X11
   6 license][1]. Most components are independent of external libraries, except the
   7 standard C library, and independent of each other. To use a component of this
   8 library, you only need to copy a couple of files to your source code tree
   9 without worrying about library dependencies.
  10
  11 Klib strives for efficiency and a small memory footprint. Some components, such
  12 as khash.h, kbtree.h, ksort.h and kvec.h, are among the most efficient
  13 implementations of similar algorithms or data structures in all programming
  14 languages, in terms of both speed and memory use.
  15
  16 A new documentation is available [here](http://attractivechaos.github.io/klib/)
  17 which includes most information in this README file.
  18
  19 #### Common components
  20
  21 * [khash.h][khash]: generic [hash table][2] with open addressing.
  22 * [kbtree.h][kbtree]: generic search tree based on [B-tree][3].
  23 * [kavl.h][kavl]: generic intrusive [AVL tree][wiki-avl].
  24 * [ksort.h][ksort]: generic sort, including [introsort][4], [merge sort][5], [heap sort][6], [comb sort][7], [Knuth shuffle][8] and the [k-small][9] algorithm.
  25 * [kseq.h][kseq]: generic stream buffer and a [FASTA][10]/[FASTQ][11] format parser.
  26 * kvec.h: generic dynamic array.
  27 * klist.h: generic single-linked list and [memory pool][12].
  28 * kstring.{h,c}: basic string library.
  29 * kmath.{h,c}: numerical routines including [MT19937-64][13] [pseudorandom generator][14], basic [nonlinear programming][15] and a few special math functions.
  30 * [ketopt.h][ketopt]: portable command-line argument parser with getopt\_long-like API.
  31
  32 #### Components for more specific use cases
  33
  34 * ksa.c: constructing [suffix arrays][16] for strings with multiple sentinels, based on a revised [SAIS algorithm][17].
  35 * knetfile.{h,c}: random access to remote files on HTTP or FTP.
  36 * kopen.c: smart stream opening.
  37 * khmm.{h,c}: basic [HMM][18] library.
  38 * ksw.(h,c}: Striped [Smith-Waterman algorithm][19].
  39 * knhx.{h,c}: [Newick tree format][20] parser.
  40
  41
  42 ## <a name="methodology"></a>Methodology
  43
  44 For the implementation of generic [containers][21], klib extensively uses C
  45 macros. To use these data structures, we usually need to instantiate methods by
  46 expanding a long macro. This makes the source code look unusual or even ugly
  47 and adds difficulty to debugging. Unfortunately, for efficient generic
  48 programming in C that lacks [template][22], using macros is the only
  49 solution. Only with macros, we can write a generic container which, once
  50 instantiated, compete with a type-specific container in efficiency. Some
  51 generic libraries in C, such as [Glib][23], use the `void*` type to implement
  52 containers. These implementations are usually slower and use more memory than
  53 klib (see [this benchmark][31]).
  54
  55 To effectively use klib, it is important to understand how it achieves generic
  56 programming. We will use the hash table library as an example:
  57
  58     #include "khash.h"
  59     KHASH_MAP_INIT_INT(m32, char)        // instantiate structs and methods
  60     int main() {
  61         int ret, is_missing;
  62         khint_t k;
  63         khash_t(m32) *h = kh_init(m32);  // allocate a hash table
  64         k = kh_put(m32, h, 5, &ret);     // insert a key to the hash table
  65         if (!ret) kh_del(m32, h, k);
  66         kh_value(h, k) = 10;             // set the value
  67         k = kh_get(m32, h, 10);          // query the hash table
  68         is_missing = (k == kh_end(h));   // test if the key is present
  69         k = kh_get(m32, h, 5);
  70         kh_del(m32, h, k);               // remove a key-value pair
  71         for (k = kh_begin(h); k != kh_end(h); ++k)  // traverse
  72             if (kh_exist(h, k))          // test if a bucket contains data
  73                         kh_value(h, k) = 1;
  74         kh_destroy(m32, h);              // deallocate the hash table
  75         return 0;
  76     }
  77
  78 In this example, the second line instantiates a hash table with `unsigned` as
  79 the key type and `char` as the value type. `m32` names such a type of hash table.
  80 All types and functions associated with this name are macros, which will be
  81 explained later. Macro `kh_init()` initiates a hash table and `kh_destroy()`
  82 frees it. `kh_put()` inserts a key and returns the iterator (or the position)
  83 in the hash table. `kh_get()` and `kh_del()` get a key and delete an element,
  84 respectively. Macro `kh_exist()` tests if an iterator (or a position) is filled
  85 with data.
  86
  87 An immediate question is this piece of code does not look like a valid C
  88 program (e.g. lacking semicolon, assignment to an _apparent_ function call and
  89 _apparent_ undefined `m32` 'variable'). To understand why the code is correct,
  90 let's go a bit further into the source code of `khash.h`, whose skeleton looks
  91 like:
  92
  93     #define KHASH_INIT(name, SCOPE, key_t, val_t, is_map, _hashf, _hasheq) \
  94       typedef struct { \
  95         int n_buckets, size, n_occupied, upper_bound; \
  96         unsigned *flags; \
  97         key_t *keys; \
  98         val_t *vals; \
  99       } kh_##name##_t; \
 100       SCOPE inline kh_##name##_t *init_##name() { \
 101         return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t)); \
 102       } \
 103       SCOPE inline int get_##name(kh_##name##_t *h, key_t k) \
 104       ... \
 105       SCOPE inline void destroy_##name(kh_##name##_t *h) { \
 106         if (h) { \
 107           free(h->keys); free(h->flags); free(h->vals); free(h); \
 108         } \
 109       }
 110
 111     #define _int_hf(key) (unsigned)(key)
 112     #define _int_heq(a, b) (a == b)
 113     #define khash_t(name) kh_##name##_t
 114     #define kh_value(h, k) ((h)->vals[k])
 115     #define kh_begin(h, k) 0
 116     #define kh_end(h) ((h)->n_buckets)
 117     #define kh_init(name) init_##name()
 118     #define kh_get(name, h, k) get_##name(h, k)
 119     #define kh_destroy(name, h) destroy_##name(h)
 120     ...
 121     #define KHASH_MAP_INIT_INT(name, val_t) \
 122         KHASH_INIT(name, static, unsigned, val_t, is_map, _int_hf, _int_heq)
 123
 124 `KHASH_INIT()` is a huge macro defining all the structs and methods. When this
 125 macro is called, all the code inside it will be inserted by the [C
 126 preprocess][37] to the place where it is called. If the macro is called
 127 multiple times, multiple copies of the code will be inserted. To avoid naming
 128 conflict of hash tables with different key-value types, the library uses [token
 129 concatenation][36], which is a preprocessor feature whereby we can substitute
 130 part of a symbol based on the parameter of the macro. In the end, the C
 131 preprocessor will generate the following code and feed it to the compiler
 132 (macro `kh_exist(h,k)` is a little complex and not expanded for simplicity):
 133
 134     typedef struct {
 135       int n_buckets, size, n_occupied, upper_bound;
 136       unsigned *flags;
 137       unsigned *keys;
 138       char *vals;
 139     } kh_m32_t;
 140     static inline kh_m32_t *init_m32() {
 141       return (kh_m32_t*)calloc(1, sizeof(kh_m32_t));
 142     }
 143     static inline int get_m32(kh_m32_t *h, unsigned k)
 144     ...
 145     static inline void destroy_m32(kh_m32_t *h) {
 146       if (h) {
 147         free(h->keys); free(h->flags); free(h->vals); free(h);
 148       }
 149     }
 150
 151         int main() {
 152                 int ret, is_missing;
 153                 khint_t k;
 154                 kh_m32_t *h = init_m32();
 155                 k = put_m32(h, 5, &ret);
 156                 if (!ret) del_m32(h, k);
 157                 h->vals[k] = 10;
 158                 k = get_m32(h, 10);
 159                 is_missing = (k == h->n_buckets);
 160                 k = get_m32(h, 5);
 161                 del_m32(h, k);
 162                 for (k = 0; k != h->n_buckets; ++k)
 163                         if (kh_exist(h, k)) h->vals[k] = 1;
 164                 destroy_m32(h);
 165                 return 0;
 166         }
 167
 168 This is the C program we know.
 169
 170 From this example, we can see that macros and the C preprocessor plays a key
 171 role in klib. Klib is fast partly because the compiler knows the key-value
 172 type at the compile time and is able to optimize the code to the same level
 173 as type-specific code. A generic library written with `void*` will not get such
 174 performance boost.
 175
 176 Massively inserting code upon instantiation may remind us of C++'s slow
 177 compiling speed and huge binary size when STL/boost is in use. Klib is much
 178 better in this respect due to its small code size and component independency.
 179 Inserting several hundreds lines of code won't make compiling obviously slower.
 180
 181 ## <a name="resources"></a>Resources
 182
 183 * Library documentation, if present, is available in the header files. Examples
 184 can be found in the [test/][24] directory.
 185 * **Obsolete** documentation of the hash table library can be found at
 186 [SourceForge][25]. This README is partly adapted from the old documentation.
 187 * [Blog post][26] describing the hash table library.
 188 * [Blog post][27] on why using `void*` for generic programming may be inefficient.
 189 * [Blog post][28] on the generic stream buffer.
 190 * [Blog post][29] evaluating the performance of `kvec.h`.
 191 * [Blog post][30] arguing B-tree may be a better data structure than a binary search tree.
 192 * [Blog post][31] evaluating the performance of `khash.h` and `kbtree.h` among many other implementations.
 193 [An older version][33] of the benchmark is also available.
 194 * [Blog post][34] benchmarking internal sorting algorithms and implementations.
 195 * [Blog post][32] on the k-small algorithm.
 196 * [Blog post][35] on the Hooke-Jeeve's algorithm for nonlinear programming.
 197
 198 [1]: http://en.wikipedia.org/wiki/MIT_License
 199 [2]: https://en.wikipedia.org/wiki/Hash_table
 200 [3]: http://en.wikipedia.org/wiki/B-tree
 201 [4]: http://en.wikipedia.org/wiki/Introsort
 202 [5]: http://en.wikipedia.org/wiki/Merge_sort
 203 [6]: http://en.wikipedia.org/wiki/Heapsort
 204 [7]: http://en.wikipedia.org/wiki/Comb_sort
 205 [8]: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
 206 [9]: http://en.wikipedia.org/wiki/Selection_algorithm
 207 [10]: http://en.wikipedia.org/wiki/FASTA_format
 208 [11]: http://en.wikipedia.org/wiki/FASTQ_format
 209 [12]: http://en.wikipedia.org/wiki/Memory_pool
 210 [13]: http://en.wikipedia.org/wiki/Mersenne_twister
 211 [14]: http://en.wikipedia.org/wiki/Pseudorandom_generator
 212 [15]: http://en.wikipedia.org/wiki/Nonlinear_programming
 213 [16]: http://en.wikipedia.org/wiki/Suffix_array
 214 [17]: https://sites.google.com/site/yuta256/sais
 215 [18]: http://en.wikipedia.org/wiki/Hidden_Markov_model
 216 [19]: http://en.wikipedia.org/wiki/Smith-Waterman_algorithm
 217 [20]: http://en.wikipedia.org/wiki/Newick_format
 218 [21]: http://en.wikipedia.org/wiki/Container_(abstract_data_type)
 219 [22]: http://en.wikipedia.org/wiki/Template_(C%2B%2B)
 220 [23]: http://en.wikipedia.org/wiki/GLib
 221 [24]: https://github.com/attractivechaos/klib/tree/master/test
 222 [25]: http://klib.sourceforge.net/
 223 [26]: http://attractivechaos.wordpress.com/2008/09/02/implementing-generic-hash-library-in-c/
 224 [27]: http://attractivechaos.wordpress.com/2008/10/02/using-void-in-generic-c-programming-may-be-inefficient/
 225 [28]: http://attractivechaos.wordpress.com/2008/10/11/a-generic-buffered-stream-wrapper/
 226 [29]: http://attractivechaos.wordpress.com/2008/09/19/c-array-vs-c-vector/
 227 [30]: http://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-binary-search-tree/
 228 [31]: http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/
 229 [32]: http://attractivechaos.wordpress.com/2008/09/13/calculating-median/
 230 [33]: http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/
 231 [34]: http://attractivechaos.wordpress.com/2008/08/28/comparison-of-internal-sorting-algorithms/
 232 [35]: http://attractivechaos.wordpress.com/2008/08/24/derivative-free-optimization-dfo/
 233 [36]: http://en.wikipedia.org/wiki/C_preprocessor#Token_concatenation
 234 [37]: http://en.wikipedia.org/wiki/C_preprocessor
 235
 236 [wiki-avl]: https://en.wikipedia.org/wiki/AVL_tree
 237
 238 [kbtree]: http://attractivechaos.github.io/klib/#KBtree%3A%20generic%20ordered%20map:%5B%5BKBtree%3A%20generic%20ordered%20map%5D%5D
 239 [khash]: http://attractivechaos.github.io/klib/#Khash%3A%20generic%20hash%20table:%5B%5BKhash%3A%20generic%20hash%20table%5D%5D
 240 [kseq]: http://attractivechaos.github.io/klib/#Kseq%3A%20stream%20buffer%20and%20FASTA%2FQ%20parser:%5B%5BKseq%3A%20stream%20buffer%20and%20FASTA%2FQ%20parser%5D%5D
 241 [ksort]: http://attractivechaos.github.io/klib/#Ksort%3A%20sorting%2C%20shuffling%2C%20heap%20and%20k-small:%5B%5BKsort%3A%20sorting%2C%20shuffling%2C%20heap%20and%20k-small%5D%5D
 242 [kavl]: http://attractivechaos.github.io/klib/#KAVL%3A%20generic%20intrusive%20AVL%20tree
 243 [ketopt]: http://attractivechaos.github.io/klib/#Ketopt%3A%20parsing%20command-line%20arguments