tarantool / tarantool / 5223368825

88%

push

github

salad: make rope_erase erase more than a single element

We are going to use rope for representation of string field on tuple
update. It will help to handle multiple updates of the same string field
in the single update operation.

Currently rope erase operation can only remove single element at a time
which make erase complexity S*log2(N). Here S is number or deleted
elements and N is number of nodes in the rope. This patch changes rope
API to delete given number of elements at a time. Now complexity is
K*log2(N) when K is number of nodes where deleted elements resides.

Note that implementation is still suboptimal for the case when deleted
elements reside in more than a single node. First the implementation
searches every next node from the root of the tree. Second the balancing
rotations are performed on every node deletion.

As for the first issue it can be fixed merely by traversing to the next
node instead. Unfortunately the traversing code works with single level
of indirection while erasion works with two levels of indirection. We
can duplicate the code/use macros/copy to handle the difference but all
the possibilities are rather ugly so traversal on erasion is not done.
Anyway looks like sane update usage will erase from a single node every
time.

Part of #8226

NO_DOC=internal
NO_CHANGELOG=internal

63133 of 115680 branches covered (54.58%)

35 of 35 new or added lines in 2 files covered. (100.0%)

94768 of 110370 relevant lines covered (85.86%)

2862265.43 hits per line