Skip to content

Tags: tidwall/btree.c

Tags

v0.6.4

Toggle v0.6.4's commit message
Remove unneeded include

v0.6.3

Toggle v0.6.3's commit message
Copy fewer nodes on rebalance

This commit fixes a potential future memory error.

It can"t be currently tested in production because the memmove
overwrites a "spare" slot that isn"t used during the
rebalance operation. But without this fix, if at some point in
the future the spare slots are no longer located immediately
after the child nodes then a heap-buffer-overflow would have
happen.

v0.6.2

Toggle v0.6.2's commit message
Fix reference counter falling belowing zero

This commit fixes an issue where a node"s reference counter
may fall below zero when more than one tree share the same node
(rc == 1) and then the both copy the node and fetch_subtract the
rc. This is a hard to produce issue, but possible.

The rc must never fall below zero except when the node is
about to be freed by the node_free function.

This commit replaces the fetch_subtract with node_free which
correctly frees the node when the rc == -1.

v0.6.1

Toggle v0.6.1's commit message
Add custom searcher

Using the btree_set_searcher() function, it"s now possible to add
a custom search operation on node items during tree traversal.

This is an advanced operation that puts the programmer in control
of how items are searched, such as using a bsearch, sequentially
scanning items, or maybe using SIMD.

The benchmarks now use a custom searcher that sequentially scans
the items instead of a traditional bsearch. Look at the
tests/bench.c file for an example of usage. To bench using a
bsearch use `BSEARCH=1 tests/run.sh bench`.

v0.6.0

Toggle v0.6.0's commit message
Add loop-based iteration

For example:
    struct btree_iter *iter = btree_iter_new(tr);
    bool ok = btree_iter_seek(iter, key);
    while (ok) {
        item = btree_iter_item(iter);
        ok = btree_iter_next(iter);
    }
    btree_iter_free(iter);

See the README.md for an example.

v0.5.0

Toggle v0.5.0's commit message
Add BTREE_NOATOMICS option

Add the compiler define BTREE_NOATOMIC options to disable using
an atomic reference counter. Instead a normal int will be used
in its place.

This means that using btree_clone() will no longer result in a
clone that is thread-safe, but it will still a valid clone for
single threaded programs. This may be desired (or needed) for
environments where there are no atomics, or where concurrency is
coroutine-based.

Usage:
    cc -DBTREE_NOATOMICS btree.c

v0.4.2

Toggle v0.4.2's commit message
Add max_items limit and coerse signedness

v0.4.1

Toggle v0.4.1's commit message
Add inttypes.h

v0.4.0

Toggle v0.4.0's commit message
Merge branch "clone"

v0.3.1

Toggle v0.3.1's commit message
Fix warnings for -Wall -Wextra

This commit fixes all warnings when the -Wall -Wextra compiler
options are provided. Tested with Clang and GCC.