0undefined / btree Goto Github PK

In regards to #2, it should be considered to occasionally tidy up the nodes location in memory after some insertions/deletions.
Question is: should we have root node in the

• head
• or middle

of the memory block.

Create some benchmarks:

• Compare against arrays.
• make sure that no major performance problems arise when adding features or modifying the implementation.

It would be nice to convert the project to use CMake instead of a plain ol' makefile.
This would make it integrate easier into other projects that also use CMake.

Write documentation!

Examples aren't enough.

Implementation details, such as the value inserted is copied, not the pointer to the variable, is very important to know when using this library.

See branch example-iter.

Failure with

btree-test: malloc.c:2539: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.

Happens when we need to allocate a new node, post-iteration.

Recursion shouldn't really be a problem, as the tree shouldn't be able to grow that tall.
It could be neat to compare performance of a recursion free implementation, possibly taking inspiration from the iteration implementation that uses a struct?

Make a single allocated memory block for the whole tree.

Pros:

• More performant memory layout in regards to memory prefetching
• This means (probably) faster linear iteration of the tree
• Fewer memory allocations on insertions
• Allows for the possibility of creating a tree from a known/static dataset

Cons:

• More difficult memory management
• Increases unused memory (can possibly be mitigated if we allow an argument for how many items are expected to be in the tree)

Strategies

1. Place everything in a blob pointing to a sequence of {node, elem [2*t]}
2. Have seperate arrays for nodes and elements respectively

1 seems bothersome but easy, however 2 might be easier to implement with the current state of things. Also 2 is probably nicer to work with.

Write some tests to make sure shit don't break.

Couple of basic tests to implement:

• Smoke test: does it run at all without crashing and burning?
• Validity test: does it still present a valid B-Tree after a long series of operations?
• Pedantic: does it behave exactly like described in CLRS?

Remove the memcpy spam in btree.c#L338.

It should be fine to simply do

i = n - 1;
while (i > 0 && cmp(elem, items+(i*size)) < 0) i--;
memmove(...);
memcpy(...);
...