Bugfix Release of STX B+ Tree 0.8.1
Posted on 2008-01-25 15:48 by Timo Bingmann at Permlink with 1 Comments. Tags: #c++ #stx-btree
Released a bugfix version 0.8.1 of the STX B+ Tree C++ Template Classes package. The bug fixed is a possibly illegal memory access during find() function.
I received a new test case via email in which valgrind detected an uninitialized memory access. By tracing it, I soon found that it happens during any find(key) call with a key that is larger than any item contained in the tree. During the find() function find_lower() is called on a leaf node and returns the slot number with the smallest or equal key. However if the queried key is larger than all keys in a leaf node or in the whole tree, find_lower() returns a slot number past the last valid key slot. Comparison of this invalid slot with the queried key then yields an uninitialized memory error in valgrind.
The updated source code package including the wxBTreeDemo source is available for download from this webpage.
Some compiled binaries of wxBTreeDemo for Win32 and Linux are available on the demo download page.
As before, the updated main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.
Great library!
One thing I'm really missing is random access on the tree by index and not just access by key value. You keep track of the number of elements per node anyway, ain't you?
Another thing I like with B trees is its potential for hardware acceleration. Someone might image a shifting memory where memory contents can be shifted upwards or downwards in a single clock cycle.