DOCSEARCHbyAlgolia
Submit Docs

bgen B-tree Generator

repository·main·Indexed 41 days ago

https://github.com/tidwall/bgen

A high-performance, single-file B-tree generator for C that uses the preprocessor to create type-safe, customized in-memory collections. It can be used to implement maps, sets, priority queues, stacks, deques, and vectors. Features include Copy-on-Write (COW) support, custom allocators, binary and linear search options, and counted B-trees for O(log n) random access.

Tokens
5.1K
Snippets
13
Records
27
Agent score
100%

What's inside bgen

  1. Define comparators with BTREE_LESS and BTREE_COMPARE

    main

    Every B-tree requires a comparator to order items. The comparator code fragment has access to three variables: a (the first item), b (the second item), and udata (optional user data).

    • BTREE_LESS: A boolean expression. It should return true or false. This is generally recommended for numeric comparisons.
    • BTREE_COMPARE: A three-way comparison. It should return -1 (if a < b), 0 (if a == b), or 1 (if a > b). This is often better suited for strings or complex keys.
    #define BTREE_LESS    return a < b;               /* return true or false */
#define BTREE_COMPARE return a < b ? -1 : a > b;  /* return -1, 0, 1 */

  2. Optimize linear searches with BTREE_MAYBELESSEQUAL

    main

    The BTREE_MAYBELESSEQUAL option provides an optimization for linear searches, particularly useful for composite keys where the leading field is numeric and subsequent fields are indirect (e.g., pointers to strings).

    When provided, the btree performs a quick linear search on the primary field and only falls back to the full BTREE_COMPARE function when necessary.

    Note: This option is only for linear searches and cannot be used in combination with BTREE_BSEARCH.

    struct status_user {
    int status;
    char *name;
    char *desc;
};

int user_compare(struct status_user a, struct status_user b) {
    return a.status < b.status ? -1 : a.status > b.status ? 1 : 
           strcmp(a.name, b.name);
}

#define BTREE_NAME            status_users
#define BTREE_TYPE            struct status_user
#define BTREE_COMPARE         return user_compare(a, b);
#define BTREE_MAYBELESSEQUAL  return a.status <= b.status;
#include "btree.h"

  3. Choose between Binary and Linear search

    main

    By default, btree.h uses linear searching within nodes. This is highly cache-efficient and performs excellently for small nodes (low fanout).

    If you have large nodes or if the comparison operation is computationally expensive, you can enable binary searching by defining the BTREE_BSEARCH macro.

  4. How btree.h namespaces work

    main

    The BTREE_NAME macro determines the prefix for all generated types and functions. This allows you to generate multiple distinct B-tree types within the same source file without name collisions.

    For example, if you define #define BTREE_NAME users, the generator will produce:

    • struct users (the tree structure)
    • users_get(...)
    • users_insert(...)
    • users_delete(...)
    #define BTREE_NAME users
#define BTREE_TYPE struct user
#define BTREE_LESS return a.id < b.id;
#include "btree.h"

#define BTREE_NAME orders
#define BTREE_TYPE struct order
#define BTREE_LESS return a.id < b.id;
#include "btree.h"

  5. Common collection patterns using btree.h

    main

    The btree.h B-tree generator can be used to implement several different data structures by varying how keys and values are handled. Common patterns include:

    • Map: A collection of unique key-value pairs, sorted by keys.
    • Set: A collection of unique keys.
    • Queue: A FIFO (First-In-First-Out) data structure.
    • Stack: A LIFO (Last-In-First-Out) data structure.
    • Deque: A double-ended queue.
    • Priority Queue: A queue where elements are retrieved based on priority.
    • Vector: A dynamic array implemented via a B-tree (unsorted).

  6. Use the udata parameter for user-defined context

    main
    All btree functions accept an optional udata parameter. This pointer is passed through to all operations, callbacks, and code fragments (like BTREE_COMPARE and BTREE_LESS), allowing you to provide custom context to your comparison logic or iteration callbacks.

  7. Use Mutable Read Operations with COW

    main
    If the BTREE_COW (Copy-on-Write) option is enabled, you can use _mut variants of read operations. These allow for mutable access during the read process, which is essential for certain COW-based workflows.

  8. Enable Path Hints for search optimization

    main
    Providing the BTREE_PATHHINT option enables an automatic search optimization. The btree tracks the search path of every operation and uses it as a hint for the next operation. This improves performance for access patterns where subsequent operations target items near each other in the tree. This feature uses a thread-local variable and requires no additional setup beyond the flag.

  9. Enable Copy-on-Write (COW) support

    main

    By providing the BTREE_COW option, you enable support for instant $O(1)$ copies using bt_clone(). The implementation uses atomic reference counters to monitor shared state and performs just-in-time copies during mutable operations like bt_insert() and bt_delete().

    • Disable Atomics: Use BTREE_NOATOMIC to use normal integers instead of atomic counters. This is recommended for single-threaded programs, embedded environments, or WebAssembly.
    • Immutable vs Mutable: While mutable operations perform COW internally, immutable operations like bt_get() do not. To force COW for immutable operations, use their _mut() alternatives (e.g., bt_get_mut() or bt_iter_init_mut()).

  10. Create a Counted B-tree for random access

    main

    By adding the BTREE_COUNTED option, you enable a counted b-tree which allows for random access and modifications with $O(\log n)$ complexity. This enables functions like bt_insert_at(), bt_delete_at(), and bt_get_at().

    Constraint: Items inserted at specific positions must still follow the order defined by your comparator, otherwise bt_OUTOFORDER will be returned.

  11. Configure B-tree names and types

    main

    The btree.h generator uses configurable placeholders for the B-tree namespace and the item type. You can customize these using the BTREE_NAME and BTREE_TYPE macros. By default, the namespace is bt and the item type is bitem.

    #define BTREE_NAME bt
#define BTREE_TYPE bitem
    #define BTREE_NAME bt
#define BTREE_TYPE bitem

  12. Iterate through the B-tree

    main

    Iteration is available in two modes:

    1. Callback Iteration

    Uses a callback function for each item. Use bt_scan() or bt_seek().

    // Example callback
bool user_iter(struct user user, void *udata) {
    printf("%s %s (age=%d)\n", user.first, user.last, user.age);
    return true;
}

// Usage
bt_scan(&tree, user_iter, 0);

    2. Loop-based Iteration

    Provides more control and allows the iterator to stay within the current function scope.

    struct users_iter *iter;
users_iter_init(&users, &iter, 0);
users_iter_scan(iter);
while (users_iter_valid(iter)) {
    struct user user;
    users_iter_item(iter, &user);
    // ... process user ...
    users_iter_next(iter);
}
users_iter_release(iter);

    Warning: It is generally unsafe to modify the btree while iterating. If you must modify the tree (e.g., deleting an item), use users_iter_seek() to reset the iterator after the modification.

    struct users_iter *iter;
users_iter_init(&users, &iter, 0);
users_iter_scan(iter);
while (users_iter_valid(iter)) {
    users_iter_item(iter, &user);
    if (user.age >= 30 && user.age < 40) {
        users_delete(&users, user, 0, 0);
        users_iter_seek(iter, user);
        continue;
    } 
    users_iter_next(iter);
}
users_iter_release(iter);