| /* |
| * Copyright 2000-2014 JetBrains s.r.o. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package com.intellij.util.io; |
| |
| import com.intellij.openapi.util.io.FileUtil; |
| import gnu.trove.TIntIntHashMap; |
| import org.jetbrains.annotations.NotNull; |
| |
| import java.io.File; |
| import java.io.IOException; |
| import java.nio.ByteBuffer; |
| import java.util.Arrays; |
| |
| /** |
| * Created by IntelliJ IDEA. |
| * User: maximmossienko |
| * Date: 7/12/11 |
| * Time: 1:34 PM |
| */ |
| public class IntToIntBtree { |
| public static int version() { |
| return 4 + (IOUtil.ourByteBuffersUseNativeByteOrder ? 0xFF : 0); |
| } |
| |
| private static final int HAS_ZERO_KEY_MASK = 0xFF000000; |
| static final boolean doSanityCheck = false; |
| static final boolean doDump = false; |
| |
| final int pageSize; |
| private final short maxInteriorNodes; |
| private final short maxLeafNodes; |
| private final short maxLeafNodesInHash; |
| final BtreeIndexNodeView root; |
| private int height; |
| private int maxStepsSearchedInHash; |
| private int totalHashStepsSearched; |
| private int hashSearchRequests; |
| private int pagesCount; |
| private int hashedPagesCount; |
| private int count; |
| private int movedMembersCount; |
| private boolean hasZeroKey; |
| private int zeroKeyValue; |
| |
| private final boolean isLarge = true; |
| private final ResizeableMappedFile storage; |
| private final boolean offloadToSiblingsBeforeSplit = false; |
| private final boolean indexNodeIsHashTable = true; |
| final int metaDataLeafPageLength; |
| final int hashPageCapacity; |
| |
| private static final boolean hasCachedMappings = false; |
| private TIntIntHashMap myCachedMappings; |
| private final int myCachedMappingsSize; |
| |
| public IntToIntBtree(int pageSize, @NotNull File file, @NotNull PagedFileStorage.StorageLockContext storageLockContext, boolean initial) throws IOException { |
| this.pageSize = pageSize; |
| |
| if (initial) { |
| FileUtil.delete(file); |
| } |
| |
| storage = new ResizeableMappedFile(file, pageSize, storageLockContext, 1024 * 1024, true, IOUtil.ourByteBuffersUseNativeByteOrder); |
| root = new BtreeIndexNodeView(this); |
| |
| if (initial) { |
| nextPage(); // allocate root |
| root.setAddress(0); |
| root.setIndexLeaf(true); |
| } |
| |
| int i = (this.pageSize - BtreePage.RESERVED_META_PAGE_LEN) / BtreeIndexNodeView.INTERIOR_SIZE - 1; |
| assert i < Short.MAX_VALUE && i % 2 == 0; |
| maxInteriorNodes = (short)i; |
| maxLeafNodes = (short)i; |
| |
| int metaPageLen; |
| if (indexNodeIsHashTable) { |
| ++i; |
| while(!isPrime(i)) i -= 2; |
| |
| hashPageCapacity = i; |
| metaPageLen = BtreePage.RESERVED_META_PAGE_LEN; |
| i = (int)(hashPageCapacity * 0.9); |
| if ((i & 1) == 1) ++i; |
| } |
| else { |
| hashPageCapacity = -1; |
| metaPageLen = BtreePage.RESERVED_META_PAGE_LEN; |
| } |
| |
| metaDataLeafPageLength = metaPageLen; |
| |
| assert i > 0 && i % 2 == 0; |
| maxLeafNodesInHash = (short) i; |
| |
| if (hasCachedMappings) { |
| myCachedMappings = new TIntIntHashMap(myCachedMappingsSize = 4 * maxLeafNodes); |
| } |
| else { |
| myCachedMappings = null; |
| myCachedMappingsSize = -1; |
| } |
| } |
| |
| // return total number of bytes needed for storing information |
| public int persistVars(@NotNull BtreeDataStorage storage, boolean toDisk) { |
| int i = storage.persistInt(0, height | (hasZeroKey ? HAS_ZERO_KEY_MASK :0), toDisk); |
| hasZeroKey = (i & HAS_ZERO_KEY_MASK) != 0; |
| height = i & ~HAS_ZERO_KEY_MASK; |
| |
| pagesCount = storage.persistInt(4, pagesCount, toDisk); |
| movedMembersCount = storage.persistInt(8, movedMembersCount, toDisk); |
| maxStepsSearchedInHash = storage.persistInt(12, maxStepsSearchedInHash, toDisk); |
| count = storage.persistInt(16, count, toDisk); |
| hashSearchRequests = storage.persistInt(20, hashSearchRequests, toDisk); |
| totalHashStepsSearched = storage.persistInt(24, totalHashStepsSearched, toDisk); |
| hashedPagesCount = storage.persistInt(28, hashedPagesCount, toDisk); |
| root.setAddress(storage.persistInt(32, root.address, toDisk)); |
| zeroKeyValue = storage.persistInt(36, zeroKeyValue, toDisk); |
| return 40; |
| } |
| |
| public interface BtreeDataStorage { |
| int persistInt(int offset, int value, boolean toDisk); |
| } |
| |
| private static boolean isPrime(int val) { |
| if (val % 2 == 0) return false; |
| int maxDivisor = (int)Math.sqrt(val); |
| for(int i = 3; i <= maxDivisor; i+=2) { |
| if (val % i == 0) return false; |
| } |
| return true; |
| } |
| |
| private int nextPage() { |
| int pageStart = (int)storage.length(); |
| storage.putInt(pageStart + pageSize - 4, 0); |
| ++pagesCount; |
| return pageStart; |
| } |
| |
| private BtreeIndexNodeView myAccessNodeView; |
| private int myLastGetKey; |
| private int myOptimizedInserts; |
| private boolean myCanUseLastKey; |
| |
| public boolean get(int key, @NotNull int[] result) { |
| if (key == 0) { |
| if (hasZeroKey) { |
| result[0] = zeroKeyValue; |
| return true; |
| } |
| return false; |
| } |
| |
| if (hasCachedMappings) { |
| if (myCachedMappings.containsKey(key)) { |
| result[0] = myCachedMappings.get(key); |
| return true; |
| } |
| } |
| |
| if (myAccessNodeView == null) myAccessNodeView = new BtreeIndexNodeView(this); |
| myAccessNodeView.initTraversal(root.address); |
| int index = myAccessNodeView.locate(key, false); |
| |
| if (index < 0) { |
| myCanUseLastKey = true; |
| myLastGetKey = key; |
| return false; |
| } else { |
| myCanUseLastKey = false; |
| } |
| result[0] = myAccessNodeView.addressAt(index); |
| return true; |
| } |
| |
| public void put(int key, int value) { |
| if (key == 0) { |
| hasZeroKey = true; |
| zeroKeyValue = value; |
| return; |
| } |
| |
| if (hasCachedMappings) { |
| myCachedMappings.put(key, value); |
| if (myCachedMappings.size() == myCachedMappingsSize) flushCachedMappings(); |
| } |
| else { |
| boolean canUseLastKey = myCanUseLastKey; |
| if (canUseLastKey) { |
| myCanUseLastKey = false; |
| if (key == myLastGetKey && !myAccessNodeView.myHasFullPagesAlongPath && myAccessNodeView.isValid()) { |
| ++myOptimizedInserts; |
| ++count; |
| myAccessNodeView.insert(key, value); |
| return; |
| } |
| } |
| doPut(key, value); |
| } |
| } |
| |
| private void doPut(int key, int value) { |
| if (myAccessNodeView == null) myAccessNodeView = new BtreeIndexNodeView(this); |
| myAccessNodeView.initTraversal(root.address); |
| int index = myAccessNodeView.locate(key, true); |
| |
| if (index < 0) { |
| ++count; |
| myAccessNodeView.insert(key, value); |
| } else { |
| myAccessNodeView.setAddressAt(index, value); |
| if (!myAccessNodeView.myIsDirty) myAccessNodeView.markDirty(); |
| } |
| } |
| |
| void dumpStatistics() { |
| int leafPages = height == 3 ? pagesCount - (1 + root.getChildrenCount() + 1):height == 2 ? pagesCount - 1:1; |
| long leafNodesCapacity = hashedPagesCount * maxLeafNodesInHash + (leafPages - hashedPagesCount)* maxLeafNodes; |
| long leafNodesCapacity2 = leafPages * maxLeafNodes; |
| int usedPercent = (int)((count * 100L) / leafNodesCapacity); |
| int usedPercent2 = (int)((count * 100L) / leafNodesCapacity2); |
| IOStatistics.dump("pagecount:" + pagesCount + |
| ", height:" + height + |
| ", movedMembers:"+movedMembersCount + |
| ", optimized inserts:"+myOptimizedInserts + |
| ", hash steps:" + maxStepsSearchedInHash + |
| ", avg search in hash:" + (hashSearchRequests != 0 ? totalHashStepsSearched / hashSearchRequests:0) + |
| ", leaf pages used:" + usedPercent + |
| "%, leaf pages used if sorted: " + |
| usedPercent2 + "%, size:"+storage.length() |
| ); |
| } |
| |
| private void flushCachedMappings() { |
| if (hasCachedMappings) { |
| int[] keys = myCachedMappings.keys(); |
| Arrays.sort(keys); |
| for(int key:keys) doPut(key, myCachedMappings.get(key)); |
| myCachedMappings.clear(); |
| myCanUseLastKey = false; |
| } |
| } |
| |
| public void doClose() throws IOException { |
| myCachedMappings = null; |
| storage.close(); |
| } |
| |
| public void doFlush() { |
| flushCachedMappings(); |
| storage.force(); |
| } |
| |
| static void myAssert(boolean b) { |
| if (!b) { |
| myAssert("breakpoint place" != "do not remove"); |
| } |
| assert b; |
| } |
| |
| static class BtreePage { |
| static final int RESERVED_META_PAGE_LEN = 8; |
| static final int FLAGS_SHIFT = 24; |
| static final int LENGTH_SHIFT = 8; |
| static final int LENGTH_MASK = 0xFFFF; |
| |
| protected final IntToIntBtree btree; |
| protected int address = -1; |
| private short myChildrenCount; |
| protected int myAddressInBuffer; |
| protected ByteBuffer myBuffer; |
| protected ByteBufferWrapper myBufferWrapper; |
| protected boolean myHasFullPagesAlongPath; |
| protected boolean myIsDirty; |
| |
| public BtreePage(IntToIntBtree btree) { |
| this.btree = btree; |
| myChildrenCount = -1; |
| } |
| |
| void setAddress(int _address) { |
| if (doSanityCheck) myAssert(_address % btree.pageSize == 0); |
| address = _address; |
| |
| syncWithStore(); |
| } |
| |
| protected void syncWithStore() { |
| PagedFileStorage pagedFileStorage = btree.storage.getPagedFileStorage(); |
| myAddressInBuffer = pagedFileStorage.getOffsetInPage(address); |
| myBufferWrapper = pagedFileStorage.getByteBuffer(address, false); |
| myBuffer = myBufferWrapper.getCachedBuffer(); |
| myIsDirty = false; // we will mark dirty on child count change, attrs change or existing key put |
| doInitFlags(myBuffer.getInt(myAddressInBuffer)); |
| } |
| |
| protected void doInitFlags(int anInt) { |
| myChildrenCount = (short)((anInt >>> LENGTH_SHIFT) & LENGTH_MASK); |
| } |
| |
| protected final void setFlag(int mask, boolean flag) { |
| mask <<= FLAGS_SHIFT; |
| int anInt = myBuffer.getInt(myAddressInBuffer); |
| |
| if (flag) anInt |= mask; |
| else anInt &= ~ mask; |
| myBuffer.putInt(myAddressInBuffer, anInt); |
| if (!myIsDirty) markDirty(); |
| } |
| |
| void markDirty() { |
| btree.storage.getPagedFileStorage().getByteBuffer(address, true); |
| myIsDirty = true; |
| } |
| |
| protected final short getChildrenCount() { |
| return myChildrenCount; |
| } |
| |
| protected final void setChildrenCount(short value) { |
| myChildrenCount = value; |
| int myValue = myBuffer.getInt(myAddressInBuffer); |
| myValue &= ~LENGTH_MASK << LENGTH_SHIFT; |
| myValue |= value << LENGTH_SHIFT; |
| myBuffer.putInt(myAddressInBuffer, myValue); |
| if (!myIsDirty) markDirty(); |
| } |
| |
| protected final void setNextPage(int nextPage) { |
| putInt(4, nextPage); |
| } |
| |
| protected final int getNextPage() { |
| return getInt(4); |
| } |
| |
| protected final int getInt(int address) { |
| return myBuffer.getInt(myAddressInBuffer + address); |
| } |
| |
| protected final void putInt(int offset, int value) { |
| myBuffer.putInt(myAddressInBuffer + offset, value); |
| } |
| |
| protected final ByteBuffer getBytes(int address, int length) { |
| ByteBuffer duplicate = myBuffer.duplicate(); |
| duplicate.order(myBuffer.order()); |
| |
| int newPosition = address + myAddressInBuffer; |
| duplicate.position(newPosition); |
| duplicate.limit(newPosition + length); |
| return duplicate; |
| } |
| |
| protected final void putBytes(int address, ByteBuffer buffer) { |
| myBuffer.position(address + myAddressInBuffer); |
| myBuffer.put(buffer); |
| } |
| } |
| |
| // Leaf index node |
| // (value_address {<0 if address in duplicates segment}, hash key) {getChildrenCount()} |
| // (|next_node {<0} , hash key|) {getChildrenCount()} , next_node {<0} |
| // next_node[i] is pointer to all less than hash_key[i] except for the last |
| private static class BtreeIndexNodeView extends BtreePage { |
| static final int INTERIOR_SIZE = 8; |
| static final int KEY_OFFSET = 4; |
| static final int MIN_ITEMS_TO_SHARE = 20; |
| |
| private boolean isIndexLeaf; |
| private boolean isHashedLeaf; |
| private static final int LARGE_MOVE_THRESHOLD = 5; |
| |
| BtreeIndexNodeView(IntToIntBtree btree) { |
| super(btree); |
| } |
| |
| private static final int HASH_FREE = 0; |
| |
| private int search(int value) { |
| if (isIndexLeaf() && isHashedLeaf()) { |
| return hashIndex(value); |
| } |
| else { |
| int hi = getChildrenCount() - 1; |
| int lo = 0; |
| |
| while(lo <= hi) { |
| int mid = lo + (hi - lo) / 2; |
| int keyAtMid = keyAt(mid); |
| |
| if (value > keyAtMid) { |
| lo = mid + 1; |
| } else if (value < keyAtMid) { |
| hi = mid - 1; |
| } else { |
| return mid; |
| } |
| } |
| return -(lo + 1); |
| } |
| } |
| |
| final int addressAt(int i) { |
| if (doSanityCheck) { |
| short childrenCount = getChildrenCount(); |
| if (isHashedLeaf()) myAssert(i < btree.hashPageCapacity); |
| else myAssert(i < childrenCount || (!isIndexLeaf() && i == childrenCount)); |
| } |
| return getInt(indexToOffset(i)); |
| } |
| |
| private void setAddressAt(int i, int value) { |
| int offset = indexToOffset(i); |
| if (doSanityCheck) { |
| short childrenCount = getChildrenCount(); |
| final int metaPageLen; |
| |
| if (isHashedLeaf()) { |
| myAssert(i < btree.hashPageCapacity); |
| metaPageLen = btree.metaDataLeafPageLength; |
| } |
| else { |
| myAssert(i < childrenCount || (!isIndexLeaf() && i == childrenCount)); |
| metaPageLen = RESERVED_META_PAGE_LEN; |
| } |
| myAssert(offset + 4 <= btree.pageSize); |
| myAssert(offset >= metaPageLen); |
| } |
| putInt(offset, value); |
| } |
| |
| private int indexToOffset(int i) { |
| return i * INTERIOR_SIZE + (isHashedLeaf() ? btree.metaDataLeafPageLength:RESERVED_META_PAGE_LEN); |
| } |
| |
| private int keyAt(int i) { |
| if (doSanityCheck) { |
| if (isHashedLeaf()) myAssert(i < btree.hashPageCapacity); |
| else myAssert(i < getChildrenCount()); |
| } |
| return getInt(indexToOffset(i) + KEY_OFFSET); |
| } |
| |
| private void setKeyAt(int i, int value) { |
| final int offset = indexToOffset(i) + KEY_OFFSET; |
| if (doSanityCheck) { |
| final int metaPageLen; |
| if (isHashedLeaf()) { |
| myAssert(i < btree.hashPageCapacity); |
| metaPageLen = btree.metaDataLeafPageLength; |
| } |
| else { |
| myAssert(i < getChildrenCount()); |
| metaPageLen = RESERVED_META_PAGE_LEN; |
| } |
| myAssert(offset + 4 <= btree.pageSize); |
| myAssert(offset >= metaPageLen); |
| } |
| putInt(offset, value); |
| } |
| |
| static final int INDEX_LEAF_MASK = 0x1; |
| static final int HASHED_LEAF_MASK = 0x2; |
| |
| final boolean isIndexLeaf() { |
| return isIndexLeaf; |
| } |
| |
| @Override |
| protected void doInitFlags(int flags) { |
| super.doInitFlags(flags); |
| flags = (flags >> FLAGS_SHIFT) & 0xFF; |
| isHashedLeaf = (flags & HASHED_LEAF_MASK) == HASHED_LEAF_MASK; |
| isIndexLeaf = (flags & INDEX_LEAF_MASK) == INDEX_LEAF_MASK; |
| } |
| |
| void setIndexLeaf(boolean value) { |
| isIndexLeaf = value; |
| setFlag(INDEX_LEAF_MASK, value); |
| } |
| |
| private boolean isHashedLeaf() { |
| return isHashedLeaf; |
| } |
| |
| void setHashedLeaf(boolean value) { |
| isHashedLeaf = value; |
| setFlag(HASHED_LEAF_MASK, value); |
| } |
| |
| final short getMaxChildrenCount() { |
| return isIndexLeaf() ? isHashedLeaf() ? btree.maxLeafNodesInHash:btree.maxLeafNodes:btree.maxInteriorNodes; |
| } |
| |
| final boolean isFull() { |
| short childrenCount = getChildrenCount(); |
| if (!isIndexLeaf()) { |
| ++childrenCount; |
| } |
| return childrenCount == getMaxChildrenCount(); |
| } |
| |
| boolean processMappings(KeyValueProcessor processor) throws IOException { |
| assert isIndexLeaf(); |
| |
| if (isHashedLeaf()) { |
| int offset = myAddressInBuffer + indexToOffset(0); |
| |
| for(int i = 0; i < btree.hashPageCapacity; ++i) { |
| int key = myBuffer.getInt(offset + KEY_OFFSET); |
| if (key != HASH_FREE) { |
| if(!processor.process(key, myBuffer.getInt(offset))) return false; |
| } |
| offset += INTERIOR_SIZE; |
| } |
| } else { |
| final int childrenCount = getChildrenCount(); |
| for(int i = 0; i < childrenCount; ++i) { |
| if (!processor.process(keyAt(i), addressAt(i))) return false; |
| } |
| } |
| return true; |
| } |
| |
| public void initTraversal(int address) { |
| myHasFullPagesAlongPath = false; |
| setAddress(address); |
| } |
| |
| public boolean isValid() { |
| return myBufferWrapper.getCachedBuffer() == myBuffer; |
| } |
| |
| private static class HashLeafData { |
| final BtreeIndexNodeView nodeView; |
| final int[] keys; |
| final TIntIntHashMap values; |
| |
| HashLeafData(BtreeIndexNodeView _nodeView, int recordCount) { |
| nodeView = _nodeView; |
| |
| final IntToIntBtree btree = _nodeView.btree; |
| |
| int offset = nodeView.myAddressInBuffer + nodeView.indexToOffset(0); |
| final ByteBuffer buffer = nodeView.myBuffer; |
| |
| keys = new int[recordCount]; |
| values = new TIntIntHashMap(recordCount); |
| int keyNumber = 0; |
| |
| for(int i = 0; i < btree.hashPageCapacity; ++i) { |
| int key = buffer.getInt(offset + KEY_OFFSET); |
| if (key != HASH_FREE) { |
| int value = buffer.getInt(offset); |
| |
| if (keyNumber == keys.length) throw new IllegalStateException("Index corrupted"); |
| keys[keyNumber++] = key; |
| values.put(key, value); |
| } |
| offset += INTERIOR_SIZE; |
| } |
| |
| Arrays.sort(keys); |
| } |
| |
| private void clean() { |
| final IntToIntBtree btree = nodeView.btree; |
| for(int i = 0; i < btree.hashPageCapacity; ++i) { |
| nodeView.setKeyAt(i, HASH_FREE); |
| } |
| } |
| } |
| |
| private int splitNode(int parentAddress) { |
| final boolean indexLeaf = isIndexLeaf(); |
| |
| if (doSanityCheck) { |
| myAssert(isFull()); |
| dump("before split:"+indexLeaf); |
| } |
| |
| final boolean hashedLeaf = isHashedLeaf(); |
| final short recordCount = getChildrenCount(); |
| BtreeIndexNodeView parent = null; |
| HashLeafData hashLeafData = null; |
| |
| if (parentAddress != 0) { |
| parent = new BtreeIndexNodeView(btree); |
| parent.setAddress(parentAddress); |
| |
| if (btree.offloadToSiblingsBeforeSplit) { |
| if (hashedLeaf) { |
| hashLeafData = new HashLeafData(this, recordCount); |
| if (doOffloadToSiblingsWhenHashed(parent, hashLeafData)) return parentAddress; |
| } |
| else { |
| if (doOffloadToSiblingsSorted(parent)) return parentAddress; |
| } |
| } |
| } |
| |
| short maxIndex = (short)(getMaxChildrenCount() / 2); |
| |
| BtreeIndexNodeView newIndexNode = new BtreeIndexNodeView(btree); |
| newIndexNode.setAddress(btree.nextPage()); |
| syncWithStore(); // next page can cause ByteBuffer to be invalidated! |
| if (parent != null) parent.syncWithStore(); |
| btree.root.syncWithStore(); |
| |
| newIndexNode.setIndexLeaf(indexLeaf); // newIndexNode becomes dirty |
| |
| int nextPage = getNextPage(); |
| setNextPage(newIndexNode.address); |
| newIndexNode.setNextPage(nextPage); |
| |
| int medianKey = -1; |
| |
| if (indexLeaf && hashedLeaf) { |
| if (hashLeafData == null) hashLeafData = new HashLeafData(this, recordCount); |
| final int[] keys = hashLeafData.keys; |
| |
| boolean defaultSplit = true; |
| |
| //if (keys[keys.length - 1] < newValue && btree.height <= 3) { // optimization for adding element to last block |
| // btree.root.syncWithStore(); |
| // if (btree.height == 2 && btree.root.search(keys[0]) == btree.root.getChildrenCount() - 1) { |
| // defaultSplit = false; |
| // } else if (btree.height == 3 && |
| // btree.root.search(keys[0]) == -btree.root.getChildrenCount() - 1 && |
| // parent.search(keys[0]) == parent.getChildrenCount() - 1 |
| // ) { |
| // defaultSplit = false; |
| // } |
| // |
| // if (!defaultSplit) { |
| // newIndexNode.setChildrenCount((short)0); |
| // newIndexNode.insert(newValue, 0); |
| // ++btree.count; |
| // medianKey = newValue; |
| // } |
| //} |
| |
| if (defaultSplit) { |
| hashLeafData.clean(); |
| |
| final TIntIntHashMap map = hashLeafData.values; |
| |
| final int avg = keys.length / 2; |
| medianKey = keys[avg]; |
| --btree.hashedPagesCount; |
| setChildrenCount((short)0); // this node becomes dirty |
| newIndexNode.setChildrenCount((short)0); |
| |
| for(int i = 0; i < avg; ++i) { |
| int key = keys[i]; |
| insert(key, map.get(key)); |
| key = keys[avg + i]; |
| newIndexNode.insert(key, map.get(key)); |
| } |
| |
| /*setHashedLeaf(false); |
| setChildrenCount((short)keys.length); |
| |
| --btree.hashedPagesCount; |
| btree.movedMembersCount += keys.length; |
| |
| for(int i = 0; i < keys.length; ++i) { |
| int key = keys[i]; |
| setKeyAt(i, key); |
| setAddressAt(i, map.get(key)); |
| } |
| return parentAddress;*/ |
| } |
| } else { |
| short recordCountInNewNode = (short)(recordCount - maxIndex); |
| newIndexNode.setChildrenCount(recordCountInNewNode); // newIndexNode node becomes dirty |
| |
| if (btree.isLarge) { |
| ByteBuffer buffer = getBytes(indexToOffset(maxIndex), recordCountInNewNode * INTERIOR_SIZE); |
| newIndexNode.putBytes(newIndexNode.indexToOffset(0), buffer); |
| } else { |
| for(int i = 0; i < recordCountInNewNode; ++i) { |
| newIndexNode.setAddressAt(i, addressAt(i + maxIndex)); |
| newIndexNode.setKeyAt(i, keyAt(i + maxIndex)); |
| } |
| } |
| if (indexLeaf) { |
| medianKey = newIndexNode.keyAt(0); |
| } else { |
| newIndexNode.setAddressAt(recordCountInNewNode, addressAt(recordCount)); |
| --maxIndex; |
| medianKey = keyAt(maxIndex); // key count is odd (since children count is even) and middle key goes to parent |
| } |
| setChildrenCount(maxIndex); // "this" node becomes dirty |
| } |
| |
| if (parent != null) { |
| if (doSanityCheck) { |
| int medianKeyInParent = parent.search(medianKey); |
| int ourKey = keyAt(0); |
| int ourKeyInParent = parent.search(ourKey); |
| parent.dump("About to insert "+medianKey + "," + newIndexNode.address+"," + medianKeyInParent + " our key " + ourKey + ", " + ourKeyInParent); |
| |
| myAssert(medianKeyInParent < 0); |
| myAssert(!parent.isFull()); |
| } |
| |
| parent.insert(medianKey, -newIndexNode.address); |
| |
| if (doSanityCheck) { |
| parent.dump("After modifying parent"); |
| int search = parent.search(medianKey); |
| myAssert(search >= 0); |
| myAssert(parent.addressAt(search + 1) == -newIndexNode.address); |
| |
| dump("old node after split:"); |
| newIndexNode.dump("new node after split:"); |
| } |
| } else { |
| if (doSanityCheck) { |
| btree.root.dump("Splitting root:"+medianKey); |
| } |
| |
| int newRootAddress = btree.nextPage(); |
| newIndexNode.syncWithStore(); |
| syncWithStore(); |
| |
| if (doSanityCheck) { |
| System.out.println("Pages:"+btree.pagesCount+", elements:"+btree.count + ", average:" + (btree.height + 1)); |
| } |
| btree.root.setAddress(newRootAddress); |
| parentAddress = newRootAddress; |
| |
| btree.root.setChildrenCount((short)1); // btree.root becomes dirty |
| btree.root.setKeyAt(0, medianKey); |
| btree.root.setAddressAt(0, -address); |
| btree.root.setAddressAt(1, -newIndexNode.address); |
| |
| if (doSanityCheck) { |
| btree.root.dump("New root"); |
| dump("First child"); |
| newIndexNode.dump("Second child"); |
| } |
| } |
| |
| return parentAddress; |
| } |
| |
| private boolean doOffloadToSiblingsWhenHashed(BtreeIndexNodeView parent, final HashLeafData hashLeafData) { |
| int indexInParent = parent.search(hashLeafData.keys[0]); |
| |
| if (indexInParent >= 0) { |
| BtreeIndexNodeView sibling = new BtreeIndexNodeView(btree); |
| sibling.setAddress(-parent.addressAt(indexInParent)); |
| |
| int numberOfKeysToMove = (sibling.getMaxChildrenCount() - sibling.getChildrenCount()) / 2; |
| |
| if (!sibling.isFull() && numberOfKeysToMove > MIN_ITEMS_TO_SHARE) { |
| if (doSanityCheck) { |
| sibling.dump("Offloading to left sibling"); |
| parent.dump("parent before"); |
| } |
| |
| final int childrenCount = getChildrenCount(); |
| final int[] keys = hashLeafData.keys; |
| final TIntIntHashMap map = hashLeafData.values; |
| |
| for(int i = 0; i < numberOfKeysToMove; ++i) { |
| final int key = keys[i]; |
| sibling.insert(key, map.get(key)); |
| } |
| |
| if (doSanityCheck) { |
| sibling.dump("Left sibling after"); |
| } |
| |
| parent.setKeyAt(indexInParent, keys[numberOfKeysToMove]); |
| if (!parent.myIsDirty) parent.markDirty(); |
| |
| setChildrenCount((short)0); // "this" node becomes dirty |
| --btree.hashedPagesCount; |
| hashLeafData.clean(); |
| |
| for(int i = numberOfKeysToMove; i < childrenCount; ++i) { |
| final int key = keys[i]; |
| insert(key, map.get(key)); |
| } |
| } else if (indexInParent + 1 < parent.getChildrenCount()) { |
| insertToRightSiblingWhenHashed(parent, hashLeafData, indexInParent, sibling); |
| } |
| } else if (indexInParent == -1) { |
| insertToRightSiblingWhenHashed(parent, hashLeafData, 0, new BtreeIndexNodeView(btree)); |
| } |
| |
| if (!isFull()) { |
| if (doSanityCheck) { |
| dump("old node after split:"); |
| parent.dump("Parent node after split"); |
| } |
| return true; |
| } |
| |
| return false; |
| } |
| |
| private void insertToRightSiblingWhenHashed(BtreeIndexNodeView parent, |
| HashLeafData hashLeafData, |
| int indexInParent, |
| BtreeIndexNodeView sibling) { |
| sibling.setAddress(-parent.addressAt(indexInParent + 1)); |
| int numberOfKeysToMove = (sibling.getMaxChildrenCount() - sibling.getChildrenCount()) / 2; |
| |
| if (!sibling.isFull() && numberOfKeysToMove > MIN_ITEMS_TO_SHARE) { |
| if (doSanityCheck) { |
| sibling.dump("Offloading to right sibling"); |
| parent.dump("parent before"); |
| } |
| |
| final int[] keys = hashLeafData.keys; |
| final TIntIntHashMap map = hashLeafData.values; |
| |
| final int childrenCount = getChildrenCount(); |
| final int lastChildIndex = childrenCount - numberOfKeysToMove; |
| for(int i = lastChildIndex; i < childrenCount; ++i) { |
| final int key = keys[i]; |
| sibling.insert(key, map.get(key)); // sibling will be dirty |
| } |
| |
| if (doSanityCheck) { |
| sibling.dump("Right sibling after"); |
| } |
| parent.setKeyAt(indexInParent, keys[lastChildIndex]); |
| if (!parent.myIsDirty) parent.markDirty(); |
| |
| setChildrenCount((short)0); // "this" node becomes dirty |
| --btree.hashedPagesCount; |
| hashLeafData.clean(); |
| |
| for(int i = 0; i < lastChildIndex; ++i) { |
| final int key = keys[i]; |
| insert(key, map.get(key)); |
| } |
| } |
| } |
| |
| private boolean doOffloadToSiblingsSorted(BtreeIndexNodeView parent) { |
| if (!isIndexLeaf()) return false; // TODO |
| |
| int indexInParent = parent.search(keyAt(0)); |
| |
| if (indexInParent >= 0) { |
| if (doSanityCheck) { |
| myAssert(parent.keyAt(indexInParent) == keyAt(0)); |
| myAssert(parent.addressAt(indexInParent + 1) == -address); |
| } |
| |
| BtreeIndexNodeView sibling = new BtreeIndexNodeView(btree); |
| sibling.setAddress(-parent.addressAt(indexInParent)); |
| |
| final int toMove = (sibling.getMaxChildrenCount() - sibling.getChildrenCount()) / 2; |
| |
| if (toMove > 0) { |
| if (doSanityCheck) { |
| sibling.dump("Offloading to left sibling"); |
| parent.dump("parent before"); |
| } |
| |
| for(int i = 0; i < toMove; ++i) sibling.insert(keyAt(i), addressAt(i)); |
| if (doSanityCheck) { |
| sibling.dump("Left sibling after"); |
| } |
| |
| parent.setKeyAt(indexInParent, keyAt(toMove)); |
| if (!parent.myIsDirty) parent.markDirty(); |
| |
| int indexOfLastChildToMove = (int)getChildrenCount() - toMove; |
| btree.movedMembersCount += indexOfLastChildToMove; |
| |
| if (btree.isLarge) { |
| ByteBuffer buffer = getBytes(indexToOffset(toMove), indexOfLastChildToMove * INTERIOR_SIZE); |
| putBytes(indexToOffset(0), buffer); |
| } |
| else { |
| for (int i = 0; i < indexOfLastChildToMove; ++i) { |
| setAddressAt(i, addressAt(i + toMove)); |
| setKeyAt(i, keyAt(i + toMove)); |
| } |
| } |
| |
| setChildrenCount((short)indexOfLastChildToMove); // "this" node becomes dirty |
| } |
| else if (indexInParent + 1 < parent.getChildrenCount()) { |
| insertToRightSiblingWhenSorted(parent, indexInParent + 1, sibling); |
| } |
| } else if (indexInParent == -1) { |
| insertToRightSiblingWhenSorted(parent, 0, new BtreeIndexNodeView(btree)); |
| } |
| |
| if (!isFull()) { |
| if (doSanityCheck) { |
| dump("old node after split:"); |
| parent.dump("Parent node after split"); |
| } |
| return true; |
| } |
| return false; |
| } |
| |
| private void insertToRightSiblingWhenSorted(BtreeIndexNodeView parent, int indexInParent, BtreeIndexNodeView sibling) { |
| sibling.setAddress(-parent.addressAt(indexInParent + 1)); |
| int toMove = (sibling.getMaxChildrenCount() - sibling.getChildrenCount()) / 2; |
| |
| if (toMove > 0) { |
| if (doSanityCheck) { |
| sibling.dump("Offloading to right sibling"); |
| parent.dump("parent before"); |
| } |
| |
| int childrenCount = getChildrenCount(); |
| int lastChildIndex = childrenCount - toMove; |
| for(int i = lastChildIndex; i < childrenCount; ++i) sibling.insert(keyAt(i), addressAt(i)); // sibling will be dirty |
| if (doSanityCheck) { |
| sibling.dump("Right sibling after"); |
| } |
| parent.setKeyAt(indexInParent, keyAt(lastChildIndex)); |
| if (!parent.myIsDirty) parent.markDirty(); |
| setChildrenCount((short)lastChildIndex); // "this" node becomes dirty |
| } |
| } |
| |
| private void dump(String s) { |
| if (doDump) { |
| immediateDump(s); |
| } |
| } |
| |
| private void immediateDump(String s) { |
| short maxIndex = getChildrenCount(); |
| System.out.println(s + " @" + address); |
| for (int i = 0; i < maxIndex; ++i) { |
| System.out.print(addressAt(i) + " " + keyAt(i) + " "); |
| } |
| |
| if (!isIndexLeaf()) { |
| System.out.println(addressAt(maxIndex)); |
| } |
| else { |
| System.out.println(); |
| } |
| } |
| |
| private int locate(int valueHC, boolean split) { |
| int searched = 0; |
| int parentAddress = 0; |
| final int maxHeight = btree.height + 1; |
| |
| while(true) { |
| if (isFull()) { |
| if (split) { |
| parentAddress = splitNode(parentAddress); |
| if (parentAddress != 0) setAddress(parentAddress); |
| --searched; |
| } else { |
| myHasFullPagesAlongPath = true; |
| } |
| } |
| |
| int i = search(valueHC); |
| |
| ++searched; |
| if (searched > maxHeight) throw new IllegalStateException(); |
| |
| if (isIndexLeaf()) { |
| btree.height = Math.max(btree.height, searched); |
| return i; |
| } |
| |
| int address = i < 0 ? addressAt(-i - 1):addressAt(i + 1); |
| parentAddress = this.address; |
| setAddress(-address); |
| } |
| } |
| |
| private void insert(int valueHC, int newValueId) { |
| if (doSanityCheck) myAssert(!isFull()); |
| short recordCount = getChildrenCount(); |
| if (doSanityCheck) myAssert(recordCount < getMaxChildrenCount()); |
| |
| final boolean indexLeaf = isIndexLeaf(); |
| |
| if (indexLeaf) { |
| if (recordCount == 0 && btree.indexNodeIsHashTable) { |
| setHashedLeaf(true); |
| ++btree.hashedPagesCount; |
| } |
| |
| if (isHashedLeaf()) { |
| int index = hashIndex(valueHC); |
| |
| if (index < 0) { |
| index = -index - 1; |
| } |
| |
| setKeyAt(index, valueHC); |
| setAddressAt(index, newValueId); |
| setChildrenCount((short)(recordCount + 1)); // "this" node becomes dirty |
| return; |
| } |
| } |
| |
| int medianKeyInParent = search(valueHC); |
| if (doSanityCheck) myAssert(medianKeyInParent < 0); |
| int index = -medianKeyInParent - 1; |
| setChildrenCount((short)(recordCount + 1)); // "this" node becomes dirty |
| |
| final int itemsToMove = recordCount - index; |
| btree.movedMembersCount += itemsToMove; |
| |
| if (indexLeaf) { |
| if (btree.isLarge && itemsToMove > LARGE_MOVE_THRESHOLD) { |
| ByteBuffer buffer = getBytes(indexToOffset(index), itemsToMove * INTERIOR_SIZE); |
| putBytes(indexToOffset(index + 1), buffer); |
| } else { |
| for(int i = recordCount - 1; i >= index; --i) { |
| setKeyAt(i + 1, keyAt(i)); |
| setAddressAt(i + 1, addressAt(i)); |
| } |
| } |
| setKeyAt(index, valueHC); |
| setAddressAt(index, newValueId); |
| } else { |
| // <address> (<key><address>) {record_count - 1} |
| // |
| setAddressAt(recordCount + 1, addressAt(recordCount)); |
| if (btree.isLarge && itemsToMove > LARGE_MOVE_THRESHOLD) { |
| int elementsAfterIndex = recordCount - index - 1; |
| if (elementsAfterIndex > 0) { |
| ByteBuffer buffer = getBytes(indexToOffset(index + 1), elementsAfterIndex * INTERIOR_SIZE); |
| putBytes(indexToOffset(index + 2), buffer); |
| } |
| } else { |
| for(int i = recordCount - 1; i > index; --i) { |
| setKeyAt(i + 1, keyAt(i)); |
| setAddressAt(i + 1, addressAt(i)); |
| } |
| } |
| |
| if (index < recordCount) setKeyAt(index + 1, keyAt(index)); |
| |
| setKeyAt(index, valueHC); |
| setAddressAt(index + 1, newValueId); |
| } |
| |
| if (doSanityCheck) { |
| if (index > 0) myAssert(keyAt(index - 1) < keyAt(index)); |
| if (index < recordCount) myAssert(keyAt(index) < keyAt(index + 1)); |
| } |
| } |
| |
| private static final boolean useDoubleHash = true; |
| private int hashIndex(int value) { |
| final int length = btree.hashPageCapacity; |
| int hash = value & 0x7fffffff; |
| int index = hash % length; |
| int keyAtIndex = keyAt(index); |
| |
| btree.hashSearchRequests++; |
| |
| int total = 0; |
| if (useDoubleHash) { |
| if (keyAtIndex != value && keyAtIndex != HASH_FREE) { |
| // see Knuth, p. 529 |
| final int probe = 1 + (hash % (length - 2)); |
| |
| do { |
| index -= probe; |
| if (index < 0) index += length; |
| |
| keyAtIndex = keyAt(index); |
| ++total; |
| if (total > length) { |
| throw new IllegalStateException("Index corrupted"); // violation of Euler's theorem |
| } |
| } |
| while (keyAtIndex != value && keyAtIndex != HASH_FREE); |
| } |
| } else { |
| while(keyAtIndex != value && keyAtIndex != HASH_FREE) { |
| if (index == 0) index = length; |
| --index; |
| keyAtIndex = keyAt(index); |
| ++total; |
| |
| if (total > length) throw new IllegalStateException("Index corrupted"); // violation of Euler's theorem |
| } |
| } |
| |
| btree.maxStepsSearchedInHash = Math.max(btree.maxStepsSearchedInHash, total); |
| btree.totalHashStepsSearched += total; |
| |
| return keyAtIndex == HASH_FREE ? -index - 1 : index; |
| } |
| } |
| |
| public abstract static class KeyValueProcessor { |
| public abstract boolean process(int key, int value) throws IOException; |
| } |
| |
| public boolean processMappings(@NotNull KeyValueProcessor processor) throws IOException { |
| doFlush(); |
| root.syncWithStore(); |
| |
| if (hasZeroKey) { |
| if(!processor.process(0, zeroKeyValue)) return false; |
| } |
| return processLeafPages(root, processor); |
| } |
| |
| private boolean processLeafPages(@NotNull BtreeIndexNodeView node, @NotNull KeyValueProcessor processor) throws IOException { |
| if (node.isIndexLeaf()) { |
| return node.processMappings(processor); |
| } |
| |
| // Copy children addresses first to avoid node's ByteBuffer invalidation |
| final int[] childrenAddresses = new int[node.getChildrenCount() + 1]; |
| |
| for(int i = 0; i < childrenAddresses.length; ++i) { |
| childrenAddresses[i] = -node.addressAt(i); |
| } |
| |
| if (childrenAddresses.length > 0) { |
| BtreeIndexNodeView child = new BtreeIndexNodeView(this); |
| |
| for (int childrenAddress : childrenAddresses) { |
| child.setAddress(childrenAddress); |
| if (!processLeafPages(child, processor)) return false; |
| } |
| } |
| return true; |
| } |
| |
| public void withStorageLock(@NotNull Runnable runnable) { |
| storage.getPagedFileStorage().lock(); |
| try { |
| runnable.run(); |
| } |
| finally { |
| storage.getPagedFileStorage().unlock(); |
| } |
| } |
| } |