Experiments in lightweight C templates

btree.inl

// Here is btree.inl, which is the thing you would write yourself.

// Unlike C++ templates, the granularity of these lightweight templates is at the
// module level rather than the function or class level. You can think of it like
// ML functors (parameterized modules) except that there isn't any static checking
// of signatures (in that respect, it's like C++ templates). In my view, this style
// of parameterized generative modules is generally the better conceptual framework.

// This is a completely valid C file even prior to preprocessing, so during library
// development you can just include this file directly. That is a big win for testing
// and debugging, and it also means you don't need to run template.py when you're
// iterating rapidly on the library's implementation. It also makes it easy to start
// developing a library as a specialized, non-generic module and then turn it into
// a generic template later with minimal refactoring once the code has stabilized.

// The #ifndef/#error idiom is used to signal errors for required template parameters.
// The #ifndef/#define idiom is used for optional template parameters with defaults.
// The JOIN macro is a variadic token concatenator provided for your convenience.
// The TEMPLATE comment tells the template.py preprocessor to perform parameterized
// prefix replacement for C identifiers in the subsequent parts of the file.

// In this example I intentionally went overboard with name configurability, but
// I wanted to illustrate how you can have optional parameters (BTREE_NAME) with
// defaults defined in terms of optional parameters (BTREE_KEY_NAME, BTREE_VALUE_NAME)
// with defaults defined in terms of required parameters (BTREE_KEY, BTREE_VALUE).

// Jeff Roberts used a similar approach in some internal libraries at RAD Game Tools.
// The big difference from what I recall is that in Jeff's approach you had to 
// write the kind of code that's in btree.out.inl as opposed to btree.inl. Between that
// and the fact that his wrapper macros were really verbose, writing code in
// that form didn't feel very natural or look too great. But I did appreciate the approach
// and its advantages over C++ templates, particularly with lots of optional parameters
// that drive a decision tree of different implementation choices. This is what the C++
// world calls policy-based template design, but in Jeff's form it leads to very straightforward
// code since you don't have to use obscurantist metaprogramming techniques and can instead
// use simple #if/#elif/#else decision trees. This is similar to why 'static if' in D is great.

#ifndef BTREE_KEY
#error "BTREE_KEY must be #defined to a type."
#endif

#ifndef BTREE_VALUE
#error "BTREE_VALUE must be #defined to a type."
#endif

#ifndef BTREE_KEY_NAME
#define BTREE_KEY_NAME BTREE_KEY
#endif

#ifndef BTREE_VALUE_NAME
#define BTREE_VALUE_NAME BTREE_VALUE
#endif

#ifndef BTREE_NAME
#define BTREE_NAME JOIN(BTree_, BTREE_KEY_NAME, _, BTREE_VALUE_NAME)
#endif

#ifndef BTREE_PREFIX
#define BTREE_PREFIX JOIN(BTREE_NAME, _)
#endif

#ifndef BTREE_FANOUT
#define BTREE_FANOUT 32
#endif

#define BTree BTREE_NAME

/// TEMPLATE(BTree_, BTREE_PREFIX)

typedef BTREE_KEY BTree_Key;
typedef BTREE_VALUE BTree_Value;

struct BTree_Leaf {
    BTree_Key keys[BTREE_FANOUT];
    BTree_Value values[BTREE_FANOUT];
};

struct BTree_Node {
    BTree_Key keys[BTREE_FANOUT];
    BTree_Node *children[BTREE_FANOUT];
};

struct BTree {
    BTree_Node *root;
    int height;
};

BTree_Value *BTree_Get(BTree *tree, BTree_Key key);

#ifdef BTREE_IMPLEMENTATION

BTree_Value *BTree_Get(BTree *tree, BTree_Key key) {
    // ...
}

#endif

#undef BTree
#undef BTREE_KEY
#undef BTREE_VALUE
#undef BTREE_KEY_NAME
#undef BTREE_VALUE_NAME
#undef BTREE_NAME
#undef BTREE_PREFIX
#undef BTREE_FANOUT
#undef BTREE_IMPLEMENTATION

// Next is btree.out.inl, which is the generated counterpart of btree.inl.
// Lines match up perfectly one to one. This lets us use the #line directive
// to redirect the compiler and debugger to the original file. Also note that
// template-prefixed names only have two characters added to parenthesize them,
// and hence they still look almost identical and read naturally.

#line 1 "btree.inl"
#ifndef BTREE_KEY
#error "BTREE_KEY must be #defined to a type."
#endif

#ifndef BTREE_VALUE
#error "BTREE_VALUE must be #defined to a type."
#endif

#ifndef BTREE_KEY_NAME
#define BTREE_KEY_NAME BTREE_KEY
#endif

#ifndef BTREE_VALUE_NAME
#define BTREE_VALUE_NAME BTREE_VALUE
#endif

#ifndef BTREE_NAME
#define BTREE_NAME JOIN(BTree_, BTREE_KEY_NAME, _, BTREE_VALUE_NAME)
#endif

#ifndef BTREE_PREFIX
#define BTREE_PREFIX JOIN(BTREE_NAME, _)
#endif

#ifndef BTREE_FANOUT
#define BTREE_FANOUT 32
#endif

#define BTree BTREE_NAME

/// TEMPLATE(BTree_, BTREE_PREFIX)

typedef BTREE_KEY BTree_(Key);
typedef BTREE_VALUE BTree_(Value);

struct BTree_(Leaf) {
    BTree_(Key) keys[BTREE_FANOUT];
    BTree_(Value) values[BTREE_FANOUT];
};

struct BTree_(Node) {
    BTree_(Key) keys[BTREE_FANOUT];
    BTree_(Node) *children[BTREE_FANOUT];
};

struct BTree {
    BTree_(Node) *root;
    int height;
};

BTree_(Value) *BTree_(Get)(BTree *tree, BTree_(Key) key);

#ifdef BTREE_IMPLEMENTATION

BTree_(Value) *BTree_(Get)(BTree *tree, BTree_(Key) key) {
    // ...
}

#endif

#undef BTree
#undef BTREE_KEY
#undef BTREE_VALUE
#undef BTREE_KEY_NAME
#undef BTREE_VALUE_NAME
#undef BTREE_NAME
#undef BTREE_PREFIX
#undef BTREE_FANOUT
#undef BTREE_IMPLEMENTATION

// Next is btree.h, which your library users will include.

#pragma push_macro("JOIN_HELPER")
#undef JOIN_HELPER
#define JOIN_HELPER(a, b) a##b

#pragma push_macro("JOIN2")
#undef JOIN2
#define JOIN2(a, b) JOIN_HELPER(a, b)

#pragma push_macro("JOIN3")
#undef JOIN3
#define JOIN3(a, b, c) JOIN2(JOIN2(a, b), c)

#pragma push_macro("JOIN4")
#undef JOIN4
#define JOIN4(a, b, c, d, ...) JOIN2(JOIN2(JOIN2(a, b), c), d)

#pragma push_macro("JOIN")
#undef JOIN
#define JOIN(...) JOIN4(__VA_ARGS__, , , ,)

#pragma push_macro("BTree_")
#undef BTree_
#define BTree_(name) JOIN2(BTREE_PREFIX, name)

#include "btree.out.inl"

#pragma pop_macro("JOIN_HELPER")
#pragma pop_macro("JOIN2")
#pragma pop_macro("JOIN3")
#pragma pop_macro("JOIN4")
#pragma pop_macro("JOIN")
#pragma pop_macro("BTree_")

// Finally, here is an example of using btree.h.

#define BTREE_KEY char
#define BTREE_VALUE uint8_t
#include "btree.h"
// We didn't specify BTREE_NAME, so this will define the type BTree_char_uint8_t. 

#define BTREE_KEY uint32_t
#define BTREE_VALUE void *
#define BTREE_NAME CursorTree
#include "btree.h"
// We set BTREE_NAME this time so we get the type CursorTree.

#define BTREE_KEY uint32_t
#define BTREE_VALUE void *
#define BTREE_VALUE_NAME voidptr_t
#include "btree.h"
// We set BTREE_VALUE_NAME since 'void *' isn't a valid identifier, and get BTree_uint32_t_voidptr_t.