| 681 | } |
| 682 | |
| 683 | bool BTreeDatabase::BTreeImpl::leafShift(Leaf& left, Leaf& right) { |
| 684 | if (left->count() == 0) { |
| 685 | left->shiftLeft(*right, right->count()); |
| 686 | return true; |
| 687 | } |
| 688 | |
| 689 | if (right->count() == 0) |
| 690 | return true; |
| 691 | |
| 692 | uint32_t leftSize = parent->leafSize(left); |
| 693 | uint32_t rightSize = parent->leafSize(right); |
| 694 | if (leftSize + rightSize < parent->m_blockSize) { |
| 695 | left->shiftLeft(*right, right->count()); |
| 696 | return true; |
| 697 | } |
| 698 | |
| 699 | // TODO: Shifting algorithm is bad, could potentially want to shift more |
| 700 | // than one element here. |
| 701 | uint32_t rightBeginSize = parent->m_keySize + parent->dataSize(right->elements[0].data); |
| 702 | uint32_t leftEndSize = parent->m_keySize + parent->dataSize(left->elements[left->elements.size() - 1].data); |
| 703 | if (leftSize < rightSize - rightBeginSize && leftSize + rightBeginSize < parent->m_blockSize) { |
| 704 | left->shiftLeft(*right, 1); |
| 705 | return true; |
| 706 | } else if (rightSize < leftSize - leftEndSize && rightSize + leftEndSize < parent->m_blockSize) { |
| 707 | right->shiftRight(*left, 1); |
| 708 | return true; |
| 709 | } |
| 710 | |
| 711 | return false; |
| 712 | } |
| 713 | |
| 714 | auto BTreeDatabase::BTreeImpl::leafSplit(Leaf& leaf) -> Maybe<Leaf> { |
| 715 | if (leaf->elements.size() < 2) |