HelenOS-historic – /kernel/trunk/generic/src/adt/btree.c

Rev 1140 – Change B+-tree from 2-3-4 tree to 2-3-4-5 tree by adding ...

jermar — Thu, 30 Mar 2006 20:39:21 +0200

jermar – 2 file(s) modified
Change B+-tree from 2-3-4 tree to 2-3-4-5 tree by adding space for the fourth key.
This should make key removal easier.

~ /kernel/trunk/generic/include/adt/btree.h
~ /kernel/trunk/generic/src/adt/btree.c

Rev 1136 – Try to avoid splitting full B+-tree nodes by trying left ...

jermar — Sun, 26 Mar 2006 21:06:53 +0200

jermar – 1 file(s) modified
Try to avoid splitting full B+-tree nodes by trying left or right rotation first.
(This improved memory consumption of this algorithm by some 40% - meassured on 101-item set).

~ /kernel/trunk/generic/src/adt/btree.c

Rev 1134 – Change B+-tree to: - store lesser keys in a key's ...

jermar — Sat, 25 Mar 2006 16:51:02 +0100

jermar – 1 file(s) modified
Change B+-tree to:
- store lesser keys in a key's left subtree
- propagate the bigger of medians (if there are two medians) when splitting a node

~ /kernel/trunk/generic/src/adt/btree.c

Rev 1121 – Small textual changes.

jermar — Thu, 23 Mar 2006 22:18:58 +0100

jermar – 8 file(s) modified
Small textual changes.

~ /kernel/trunk/arch/amd64/include/atomic.h
~ /kernel/trunk/arch/amd64/src/amd64.c
~ /kernel/trunk/arch/amd64/src/asm_utils.S
~ /kernel/trunk/arch/ia32/src/ia32.c
~ /kernel/trunk/arch/ia32/src/userspace.c
~ /kernel/trunk/arch/ia64/src/ia64.c
~ /kernel/trunk/arch/mips32/src/mips32.c
~ /kernel/trunk/generic/src/adt/btree.c

Rev 1101 – B+-tree implementation. Currently supports only inserting and searching.

jermar — Mon, 20 Mar 2006 21:37:17 +0100

jermar – 9 file(s) modified
B+-tree implementation.
Currently supports only inserting and searching.

+ /kernel/trunk/generic/include/adt/btree.h
~ /kernel/trunk/generic/include/typedefs.h
+ /kernel/trunk/generic/src/adt/btree.c
~ /kernel/trunk/generic/src/main/main.c
~ /kernel/trunk/kernel.config
~ /kernel/trunk/Makefile
+ /kernel/trunk/test/btree
+ /kernel/trunk/test/btree/btree1
+ /kernel/trunk/test/btree/btree1/test.c