Bgen

Bgen is a B-tree generator for C. It's small & fast and includes a variety of options for creating custom in-memory btree based collections.

Features

Compile-time generation using preprocessor templates
Type-safe generic data structure
Single-file header with no dependencies
Namespaces
Support for custom allocators
Callback and loop-based iteration
Copy-on-write with O(1) cloning.
Loads of useful toggles and options
Enable specialized btrees
Supports most C compilers (C99+). Clang, gcc, tcc, etc
Webassembly support with Emscripten (emcc)
Exhaustively tested with 100% coverage
Very fast 🚀

Goals

Give C programs high performance in-memory btrees
Provide a template system for optimized code generation
Allow for sane customizations and options
Make it possible to use one btree library for a variety of collection types, such as maps, sets, stacks, queues, lists, vectors, and spatial indexes. See the examples.

It's a non-goal for bgen to provide disk-based functionality or a B+tree implementation.

Using

Just drop the "bgen.h" into your project and create your btree using the C preprocessor.

Example 1 (Insert items)

Insert items into a simple btree that only stores ints.

#include <stdio.h>

#define BGEN_NAME bt            // The namespace for the btree structure.
#define BGEN_TYPE int           // The data type for all items in the btree
#define BGEN_LESS return a < b; // A code fragment for comparing items
#include "../bgen.h"            // Include "bgen.h" to generate the btree

int main() {
    // Create an empty btree instance.
    struct bt *tree = 0;

    // Insert some items into the btree
    bt_insert(&tree, 3, 0, 0);
    bt_insert(&tree, 8, 0, 0);
    bt_insert(&tree, 2, 0, 0);
    bt_insert(&tree, 5, 0, 0);

    // Print items in tree
    struct bt_iter *iter;
    bt_iter_init(&tree, &iter, 0);
    for (bt_iter_scan(iter); bt_iter_valid(iter); bt_iter_next(iter)) {
        int item;
        bt_iter_item(iter, &item);
        printf("%d ", item);
    } 
    printf("\n");

    // Delete an item
    bt_delete(&tree, 3, 0, 0);

    // Print again
    for (bt_iter_scan(iter); bt_iter_valid(iter); bt_iter_next(iter)) {
        int item;
        bt_iter_item(iter, &item);
        printf("%d ", item);
    } 
    printf("\n");

    bt_iter_release(iter);
    bt_clear(&tree, 0);
    return 0;
}
// Output:
// 2 3 5 8
// 2 5 8

Example 2 (Key-value map)

Create a key-value map where the key is a string and value is an int.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>

struct pair {
    const char *key;
    int value;
};

#define BGEN_NAME map
#define BGEN_TYPE struct pair
#define BGEN_COMPARE return strcmp(a.key, b.key);
#include "../bgen.h"

void print_map(const char *comment, struct map **map) {
    printf("%s", comment);
    struct map_iter *iter;
    map_iter_init(map, &iter, 0);
    for (map_iter_scan(iter); map_iter_valid(iter); map_iter_next(iter)) {
        struct pair pair;
        map_iter_item(iter, &pair);
        printf("[%s] = %d; ", pair.key, pair.value);
    }
    map_iter_release(iter);
    printf("\n");
}

int main() {
    // Create a map of three (string, int) pairs
    struct map *map = 0;
    map_insert(&map, (struct pair){"GPU", 15}, 0, 0);
    map_insert(&map, (struct pair){"RAM", 20}, 0, 0);
    map_insert(&map, (struct pair){"CPU", 10}, 0, 0);
    print_map("1) Initial map:  ", &map);

    // Get an existing item
    struct pair item;
    assert(map_get(&map, (struct pair){"GPU"}, &item, 0) == map_FOUND);
    printf("2) Get item:     [%s] = %d;\n", item.key, item.value);

    // Update an existing item
    assert(map_insert(&map, (struct pair){"CPU", 25}, 0, 0) == map_REPLACED);
    // Insert a new item
    assert(map_insert(&map, (struct pair){"SSD", 30}, 0, 0) == map_INSERTED); 
    print_map("3) Updated map:  ", &map);
    assert(map_insert(&map, (struct pair){"UPS"}, 0, 0) == map_INSERTED); 
    print_map("4) Updated map:  ", &map);

    assert(map_delete(&map, (struct pair){.key="GPU"}, 0, 0) == map_DELETED);
    print_map("5) After delete: ", &map);

    return 0;
}

// Output:
// 1) Initial map:  [CPU] = 10; [GPU] = 15; [RAM] = 20;
// 2) Get item:     [GPU] = 15;
// 3) Updated map:  [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;
// 4) Updated map:  [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30; [UPS] = 0;
// 5) After delete: [CPU] = 25; [RAM] = 20; [SSD] = 30; [UPS] = 0;

Example 3 (Priority queue)

Create two priority queues. One ordered by the maximum value and the other by the minimum value.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>

#define BGEN_NAME max_priority_queue
#define BGEN_TYPE int
#define BGEN_LESS return a < b;
#include "../bgen.h"

#define BGEN_NAME min_priority_queue
#define BGEN_TYPE int
#define BGEN_LESS return b < a;
#include "../bgen.h"

int main() {
    int data[] = { 1, 8, 5, 6, 3, 4, 0, 9, 7, 2 };
    int n = sizeof(data)/sizeof(int);
    printf("data: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");

    struct max_priority_queue *max_priority_queue = 0;

    // Fill the priority queue.
    for (int i = 0; i < n; i++) {
        max_priority_queue_insert(&max_priority_queue, data[i], 0, 0);
    }

    printf("max_priority_queue: ");
    while (max_priority_queue_count(&max_priority_queue, 0) > 0) {
        int val;
        max_priority_queue_pop_front(&max_priority_queue, &val, 0);
        printf("%d ", val);
    }
    printf("\n");

    struct min_priority_queue *min_priority_queue = 0;

    // Fill the priority queue.
    for (int i = 0; i < n; i++) {
        min_priority_queue_insert(&min_priority_queue, data[i], 0, 0);
    }

    printf("min_priority_queue: ");
    while (min_priority_queue_count(&min_priority_queue, 0) > 0) {
        int val;
        min_priority_queue_pop_front(&min_priority_queue, &val, 0);
        printf("%d ", val);
    }
    printf("\n");


    return 0;
}

// Output:
// data: 1 8 5 6 3 4 0 9 7 2
// max_priority_queue: 0 1 2 3 4 5 6 7 8 9
// min_priority_queue: 9 8 7 6 5 4 3 2 1 0

Check out the examples directory for more examples, and the API reference for the full list of operations.

Options

Bgen provides a bunch of options for customizing your btree. All options are set using the C preprocessor.

Namespaces

Each bgen btree will have its own namespace using the BGEN_NAME define.

For example, the following will create a btree using the users namespace.

#define BGEN_NAME users
#define BGEN_TYPE struct user
#define BGEN_LESS return a.id < b.id;
#include "bgen.h"

This will generate all the functions and types using the users prefix, such as:

struct users; // The btree type
int users_get(struct users **root, struct user key, struct user *item, void *udata);
int users_insert(struct users **root, struct user item, struct user *old, void *udata);
int users_delete(struct users **root, struct user key, struct user *old, void *udata);

Many more functions will also be generated, see the API for a complete list.

It's also possible to generate multiple btrees in the

Bgen

Install / Use

README

Bgen

Features

Goals

Using

Example 1 (Insert items)

Example 2 (Key-value map)

Example 3 (Priority queue)

Options

Namespaces