[Libreoffice-commits] Changes to 'feature/bplustree'

[Libreoffice Gerrit user]

New branch 'feature/bplustree' available with the following commits:
commit bfd8ba2869dacd0d6881332e7ab2e9d2f4597af6
Author: Jan Holesovsky <kendy at 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