New branch 'feature/bplustree' available with the following commits:
commit bfd8ba2869dacd0d6881332e7ab2e9d2f4597af6
Author: Jan Holesovsky <ke...@suse.cz>
Date: Sun Jan 27 23:51:27 2013 +0100
B+ tree: Experimenting with replacement of BigPtrArray.
The BigPtrArray implementation does not seem to be entirely optimal from the
data structure point of view. Let's experiment with a drop-in replacement
using a B+ tree (not B-tree!) that seems to be much more fit for the
purpose -
it nicely handles holes in the indices (ie. does not eat your entire memory
if
you insert just one entry at 1000000), and allows traversing all the data in
O(n).
From reading the code, I believe these were the only requirements for
BigPtrArray. Eg. seeing that BigPtrArray::Insert() can lead to copying of
the
entire content of the BlockInfo array makes me feel a bit dizzy. Other
aspects of BigPtrArray remind of a naive B+ tree (without the actual tree)
implementation, see eg. BigPtrArray::Index2Block() and its binary search.
The other advantage is that if the B+ tree implementation works (ie.
compares
well with BigPtrArray from the performance point of view), I believe it will
allow larger update of the entire Writer core, mainly in the area of undo,
redo, and change tracking - via copy-on-write, and remembering the entire B+
trees (with most of the metadata + data shared).
This commit only copies the BigPtrArray API to a new header. The
implementation itself will reuse no code from BigPtrArray.
Change-Id: I65f97f26439a29edbbbac3f48a94aa007a8ef1ea
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
