Tags: tidwall/btree.c
Tags
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.
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.
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`.
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
PreviousNext