summaryrefslogtreecommitdiff
AgeCommit message (Collapse)AuthorFilesLines
2013-02-06Dense B+ tree: Remove root / one level if possible.feature/bplustreeJan Holesovsky1-0/+9
Change-Id: Icf76e6c711f43daa021baae47cb54cc2e4e5b0d4
2013-02-06Dense B+ tree: Joining during Delete() partially works.Jan Holesovsky1-13/+82
More work & testing still needed to make it really good, though. Change-Id: Ia2f0c24fd1a71a58a5fea948afaa41adcc9ac66a
2013-02-06Dense B+ tree: Get the order as a template parameter.Jan Holesovsky2-75/+67
For testing, we need some small order (6 or so) so that the structure is very tree-ish. For real use, we want something like 50, so that it is a bit more flat. Change-Id: If1a24d57bcb29b6381f7a5b1114a29dcf15533aa
2013-02-05Dense B+ tree: Move m_pNext handling to a more suitable place.Jan Holesovsky1-7/+6
Change-Id: I0fcf63c7c3559b0ee61cfb0a84d79e90399cf857
2013-02-04Dense B+ tree: Implement Remove().Jan Holesovsky2-3/+123
So far this is missing the implementation of joining nodes that are not enough filled (contain less than sMinFill values or children). Change-Id: I0cb855dc7b1fcbcc3d0145e7612a04956df8298e
2013-02-03Dense B+ tree: Fix serious off-by-one problem.Jan Holesovsky1-1/+1
Change-Id: I04fd003e01e7e781badce9b61c47b1281a6924ea
2013-01-31Dense B+ tree: Don't initilize NodeWithIndex in the default constructor.Jan Holesovsky1-1/+1
It is not necessary, and valgrind suggests it takes us some time. Indeed: BigPtrArray - append: 45 msec BigPtrArray - insert at front: 6580 msec BigPtrArray - insert in the middle: 3081 msec DenseBPlusTree - append: 47 msec DenseBPlusTree - insert at front: 167 msec DenseBPlusTree - insert in the middle: 87 msec I am happy now, I do not think I can do it any better. Change-Id: If7c6882daf712af37db4b43c13ab6aedb0086da0
2013-01-31Dense B+ tree: Use binary search when searching in the Keys inside nodes.Jan Holesovsky2-5/+34
Also started measuring one more case - inserting in the middle. Before this change, it took about 100 msec. BigPtrArray - append: 45 msec BigPtrArray - insert at front: 6510 msec BigPtrArray - insert in the middle: 3043 msec DenseBPlusTree - append: 48 msec DenseBPlusTree - insert at front: 167 msec DenseBPlusTree - insert in the middle: 90 msec Change-Id: I2cc0a151b26931d90c8915a6ba879cf0e386b3b2
2013-01-31Dense B+ tree: Avoid some unnecessary (and actually wrong) memcpy's.Jan Holesovsky2-12/+17
No performance impact - too rare operation. Change-Id: I0b7095b7b369753ed54c3a72f52f8d9cf95f26e7
2013-01-31Dense B+ tree: Produce more packed trees with append()s.Jan Holesovsky2-17/+25
Normally we split the nodes half/half; but in the append() case, it is much more probable that the next operation will be an append() too, so let most of the data (children pointers or values) in the original node, and transfer just 2 to the newly created one (so that there is still space for appends in the middle without having to grow the tree). BigPtrArray - append: 46 msec BigPtrArray - insert at front: 6661 msec DenseBPlusTree - append: 50 msec DenseBPlusTree - insert at front: 169 msec Change-Id: I7e492abad8238d40e79607e354b0bdee9bd386a4
2013-01-31Dense B+ tree: A small optimization of appends.Jan Holesovsky2-2/+14
Append (ie. Insert() at Count()) is supposedly a critical operation, so let's optimize for that a bit - cache the last leaf. And this gets us where we want to be (1000000 of operations): BigPtrArray - append: 45 msec BigPtrArray - insert at front: 6541 msec DenseBPlusTree - append: 59 msec DenseBPlusTree - insert at front: 169 msec Change-Id: Id66ad6f37b8a08416a874af6397e113aecfd6b0e
2013-01-31Dense B+ tree: Get rid of std::stack usage, adds terrible overhead.Jan Holesovsky2-39/+51
The results look pretty good so far - on 1000000 inserts, the DBP tree is a bit slower on append, but many times faster when inserting at the beginning: BigPtrArray - append: 46 msec BigPtrArray - insert at front: 6602 msec DenseBPlusTree - append: 200 msec DenseBPlusTree - insert at front: 165 msec Change-Id: I3fbd00d90705928f57bcaa8a1ff4dfc38fd065ed
2013-01-31Dense B+ tree: Splitting of nodes seems to work now, ie. Insert() functional.Jan Holesovsky1-72/+91
Of course, more testing still needed. Change-Id: I7e3bef1d5096e4d332f3a00d11fa13b59a4a03bf
2013-01-31Dense B+ tree: Implemented Insert(), and can start testing.Jan Holesovsky5-30/+315
The trivial case works now, but splitting nodes does not do yet. Change-Id: Ife452fc164ab786ac9e1dc9cabe9ea1a2e78231a
2013-01-31Dense B+ tree: Data structure update from the B+ tree.Jan Holesovsky2-55/+119
It turns out that the 'classic' B+ tree is not exactly what we need for the BipPtrArray replacement; but when we do a small change, it fits perfectly. The problem with B+ tree is that it is designed for non-sequential keys, not for a sequence of keys (ints) without holes. Even worse - the insert() on B+ tree does not shift the rest of the values 'to the right' which is what we need here. But if we modify the nodes so that instead of absolute key values we use relative ones, and to count the exact index we de-facto sum the indexes of the nodes that lead to the node, we get exactly what we want - insert that shifts the rest of the values to the right is possible in O(log_order(n)). Due to the lack of name for this B+ tree modification, I name it 'dense B+ tree' - maybe there already is an existing name for this structure, but I do not recall one. Change-Id: If1cd769760aa7a2a6b027b9fa54d883540d875ad
2013-01-30Dense B+ tree: Rename the files, classic B+ tree is not enough.Jan Holesovsky3-1/+0
Change-Id: If078d961e69eb79088a680cbec02036d75f064c7
2013-01-28B+ tree: Implement search.Jan Holesovsky2-7/+134
So far it only compiles, needs testing. Change-Id: Ia5633bfa6bc975067b15741df557ca0b70da56f9
2013-01-28B+ tree: Experimenting with replacement of BigPtrArray.Jan Holesovsky3-0/+90
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
2013-01-27Remove more STRINGPARAM macros form dbaccessMarcos Paulo de Souza14-126/+95
Change-Id: I283ccd03dc811dda2f10963f400cd517f42ea7b3 Reviewed-on: https://gerrit.libreoffice.org/1878 Reviewed-by: Olivier Hallot <olivier.hallot@alta.org.br> Tested-by: Olivier Hallot <olivier.hallot@alta.org.br>
2013-01-27move accessibility options .ui to right place and adapt codeCaolán McNamara8-329/+112
getting rid a pile of custom widget moving code Change-Id: I68879f9ebaf28629c4759315b318b390a985a544
2013-01-27Updated coreCaolán McNamara1-0/+0
Project: help 803567e90d6cc046b9253e6171feebab4a43778f
2013-01-27move SetAccessibleRelationLabeledBy relations into .ui and out of codeCaolán McNamara7-54/+107
Change-Id: Ieb43e08519b72d4baebd5d004e4c9fd60daa40d4
2013-01-27MacOSXSpell needs boost_headersTor Lillqvist1-0/+1
Change-Id: I4af00e2925df393523ad3d00bd3b95459ff77f9c
2013-01-27move SetAccessibleRelationLabeledBy relations into .ui and out of codeCaolán McNamara24-137/+76
Change-Id: Iaf1a4a5ed813f48f9241f9e3ae7a732c22b7b9e5
2013-01-27move entermasterpassword.ui to right place and adapt codeCaolán McNamara9-142/+41
Change-Id: Ia0308990eaf1b87de1c7fd673a2a25a45fcfb366
2013-01-27Updated coreCaolán McNamara1-0/+0
Project: help c409b0f4447cd04b2c88253aecab3dceedc251df
2013-01-27we need to parse the cell address after import, fdo#59843Markus Mohrhard1-4/+2
Otherwise we may have problems with sheet names from sheets that are not yet imported. Change-Id: I99a6507567b7d1018b790a90019cd563fa7323a0
2013-01-27prevent some unnecessary cycles for large cond format rangesMarkus Mohrhard1-2/+14
Change-Id: I48f03a897d1ca876bba0d0becf6b51a300970346
2013-01-27we need to use SCROW for row numbers, fdo#59894Markus Mohrhard1-1/+1
This caused an overflow and resulted in adding endless number of values until a bad_alloc was thrown. Change-Id: I954acd801eb18e2c2fe6a449048856cb95d0d8b0
2013-01-27remove some parametersMarkus Mohrhard2-16/+6
Change-Id: Ib812d7092c0f375f253a3db2929b2ea6b63806fa
2013-01-27remove unneeded variableMarkus Mohrhard2-11/+6
Change-Id: Ic422a31252d60ddbafdfc05104b704ff9ffc4274
2013-01-27use isEmpty instead of getLengthMarkus Mohrhard2-4/+4
Change-Id: I9e5ce12776fcb31577a735296ab10b2c98c238f8
2013-01-27still not enough boost_headerMichael Stahl2-0/+3
Change-Id: Ic0ee933fbee7368f0af2573ea33a5ce33f4043c4
2013-01-27need more boost_headersMichael Stahl2-1/+6
Change-Id: Ic58e334acb9d9c89e5466638286c0f42dc36df43
2013-01-27fix omissions in a53586f4efe26b8875107d04001f4ecec760c343Michael Stahl3-1/+5
Change-Id: I65e3fc3e34416b74365490a1cd7cba178ef7eb55
2013-01-26add mnemonic widgets to caption options dialogCaolán McNamara1-25/+30
and recover the original short-cuts Change-Id: I2d934cfb3b1ca0ab07489b23dde27fee073a5706
2013-01-26Updated coreCaolán McNamara1-0/+0
Project: help c72e13bc83d8adf973470eda98c3885ba64389cc
2013-01-26gbuild: fix silly "expandtabs" in makefile VIM modelinesMichael Stahl178-178/+178
Change-Id: I54d8923ad315e8041fd3904da3a29f1a7a8c8b16
2013-01-26gbuild: remove various pointless calls that don't add anythingMichael Stahl65-262/+0
Change-Id: I7eccac4fa8890c2873c6bbd7f8f5bf5b0dd006d2
2013-01-26gbuild: do not copy boost headers aroundMichael Stahl374-98/+730
- do not use gb_UnpackedTarball_copy_header_files for boost - adapt the optimization in concat-deps.c for new path - use boost_headers in all LinkTargets that require it - add explicit include paths to mysqlc, mysqlcppconn, libvisio, liborcus Change-Id: I0c43e73ed43cc9d2e6bce8faf55e992d655a0bb9
2013-01-26crashrep: fix conditionals: it used to be built in non-pro tooMichael Stahl1-4/+4
Change-Id: Icf3901024aed39f3b8e280a4fed8244a2b83e80e
2013-01-26CppunitTest_sw_filters_test: use externalMichael Stahl1-4/+2
Change-Id: I915d22fb2d6937a276a35b67bac0eb8b925596f1
2013-01-26idlc: silence annoying test spew on successMichael Stahl1-2/+2
Change-Id: I7c9ff31a8f4578afdb9056d6d204bd688c3c3473
2013-01-26add mnemonic widgets to document info pageCaolán McNamara1-10/+11
Change-Id: I286847cb0f07a416b1810450eb2c873ca19c2932
2013-01-26add mnemonic widgets to description info pageCaolán McNamara1-0/+4
Change-Id: Ic9b5a0d39d91ee3546ab49e5c586b16b70298045
2013-01-26add mnemonic widgets to statistics info pageCaolán McNamara2-2/+21
Change-Id: Ife142f262f3f78f25ba3b8b3eaa1a515b21b3da5
2013-01-26Updated coreCaolán McNamara1-0/+0
Project: help d6a4e01ee6738f6a30401605ce2ee019fa94b649
2013-01-26sfx2/source/control/templateview.src is localizableAndras Timar1-4/+1
Change-Id: Ic21abffa3a889b96e2ce03c9ad997b3924133e66
2013-01-26Some cppcheck cleaningJulien Nabet2-1/+2
Change-Id: Iab4ff990f71321b75f69bc61a5cda728956ca85c
2013-01-26Fix Member variable m_pView is not initialized in the constructorJulien Nabet1-0/+1
Change-Id: I0b18698f23f7c2c446e60069d0efcb6d89b1e5d3