| /* |
| * Copyright 2009-2010 by The Regents of the University of California |
| * 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 from |
| * |
| * 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 edu.uci.ics.hyracks.dataflow.std.sort; |
| |
| import java.nio.ByteBuffer; |
| |
| import edu.uci.ics.hyracks.api.context.IHyracksTaskContext; |
| import edu.uci.ics.hyracks.api.exceptions.HyracksDataException; |
| import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor; |
| import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender; |
| |
| /** |
| * @author pouria Implements Memory Manager based on creating Binary Search Tree |
| * (BST) while Free slot size is the key for the BST nodes. Each node in |
| * BST shows a class of free slots, while all the free slots within a |
| * class have same lengths. Slots in a class are stored as a LinkedList, |
| * whose head is the BST node, corresponding to that class. BST is not |
| * stored as a separate data structure, but the free slots in the memory |
| * are used to hold BST nodes. Each BST node has the logical structure, |
| * defined in the BSTNodeUtil class. |
| */ |
| public class BSTMemMgr implements IMemoryManager { |
| |
| private final IHyracksTaskContext ctx; |
| public static int frameSize; |
| |
| private ByteBuffer[] frames; |
| private ByteBuffer convertBuffer; |
| private Slot root; |
| private Slot result; // A reusable object to hold one node returned as |
| // method result |
| private Slot insertSlot; // A reusable object to hold one node within insert |
| // process |
| private Slot lastLeftParent; // A reusable object for the search process |
| private Slot lastLeft; // A reusable object for the search process |
| private Slot parent; // A reusable object for the search process |
| |
| private Slot[] parentRes; |
| private int lastFrame; |
| |
| public BSTMemMgr(IHyracksTaskContext ctx, int memSize) { |
| this.ctx = ctx; |
| frameSize = ctx.getFrameSize(); |
| convertBuffer = ByteBuffer.allocate(4); |
| frames = new ByteBuffer[memSize]; |
| lastFrame = -1; |
| root = new Slot(); |
| insertSlot = new Slot(); |
| result = new Slot(); |
| lastLeftParent = new Slot(); |
| lastLeft = new Slot(); |
| parent = new Slot(); |
| parentRes = new Slot[] { new Slot(), new Slot() }; |
| } |
| |
| /** |
| * result is the container sent by the caller to hold the results |
| */ |
| @Override |
| public void allocate(int length, Slot result) throws HyracksDataException { |
| search(length, parentRes); |
| if (parentRes[1].isNull()) { |
| addFrame(parentRes); |
| if (parentRes[1].isNull()) { |
| return; |
| } |
| } |
| |
| int sl = BSTNodeUtil.getLength(parentRes[1], frames, convertBuffer); |
| int acLen = BSTNodeUtil.getActualLength(length); |
| if (shouldSplit(sl, acLen)) { |
| int[] s = split(parentRes[1], parentRes[0], acLen); |
| int insertLen = BSTNodeUtil.getLength(s[2], s[3], frames, convertBuffer); |
| insert(s[2], s[3], insertLen); // inserting second half of the split |
| // slot |
| BSTNodeUtil.setHeaderFooter(s[0], s[1], length, false, frames); |
| result.set(s[0], s[1]); |
| return; |
| } |
| allocate(parentRes[1], parentRes[0], length, result); |
| } |
| |
| @Override |
| public int unallocate(Slot s) throws HyracksDataException { |
| int usedLen = BSTNodeUtil.getLength(s, frames, convertBuffer); |
| int actualLen = BSTNodeUtil.getActualLength(usedLen); |
| int fix = s.getFrameIx(); |
| int off = s.getOffset(); |
| |
| int prevMemSlotFooterOffset = ((off - BSTNodeUtil.HEADER_SIZE) >= 0 ? (off - BSTNodeUtil.HEADER_SIZE) |
| : BSTNodeUtil.INVALID_INDEX); |
| int t = off + 2 * BSTNodeUtil.HEADER_SIZE + actualLen; |
| int nextMemSlotHeaderOffset = (t < frameSize ? t : BSTNodeUtil.INVALID_INDEX); |
| // Remember: next and prev memory slots have the same frame index as the |
| // unallocated slot |
| if (!isNodeNull(fix, prevMemSlotFooterOffset) && BSTNodeUtil.isFree(fix, prevMemSlotFooterOffset, frames)) { |
| int leftLength = BSTNodeUtil.getLength(fix, prevMemSlotFooterOffset, frames, convertBuffer); |
| removeFromList(fix, prevMemSlotFooterOffset - leftLength - BSTNodeUtil.HEADER_SIZE); |
| int concatLength = actualLen + leftLength + 2 * BSTNodeUtil.HEADER_SIZE; |
| if (!isNodeNull(fix, nextMemSlotHeaderOffset) && BSTNodeUtil.isFree(fix, nextMemSlotHeaderOffset, frames)) { |
| removeFromList(fix, nextMemSlotHeaderOffset); |
| concatLength += BSTNodeUtil.getLength(fix, nextMemSlotHeaderOffset, frames, convertBuffer) + 2 |
| * BSTNodeUtil.HEADER_SIZE; |
| } |
| insert(fix, prevMemSlotFooterOffset - leftLength - BSTNodeUtil.HEADER_SIZE, concatLength); // newly |
| // (merged) |
| // slot |
| // starts |
| // at |
| // the |
| // prev |
| // slot |
| // offset |
| return concatLength; |
| |
| } else if (!isNodeNull(fix, nextMemSlotHeaderOffset) |
| && BSTNodeUtil.isFree(fix, nextMemSlotHeaderOffset, frames)) { |
| removeFromList(fix, nextMemSlotHeaderOffset); |
| int concatLength = actualLen + BSTNodeUtil.getLength(fix, nextMemSlotHeaderOffset, frames, convertBuffer) |
| + 2 * BSTNodeUtil.HEADER_SIZE; |
| insert(fix, off, concatLength); // newly (merged) slot starts at the |
| // unallocated slot offset |
| return concatLength; |
| } |
| // unallocated slot is not merging with any neighbor |
| insert(fix, off, actualLen); |
| return actualLen; |
| } |
| |
| @Override |
| public boolean readTuple(int frameIx, int offset, FrameTupleAppender dest) { |
| int offToRead = offset + BSTNodeUtil.HEADER_SIZE; |
| int length = BSTNodeUtil.getLength(frameIx, offset, frames, convertBuffer); |
| return dest.append(frames[frameIx].array(), offToRead, length); |
| } |
| |
| @Override |
| public boolean writeTuple(int frameIx, int offset, FrameTupleAccessor src, int tIndex) { |
| int offToCopy = offset + BSTNodeUtil.HEADER_SIZE; |
| int tStartOffset = src.getTupleStartOffset(tIndex); |
| int tEndOffset = src.getTupleEndOffset(tIndex); |
| int tupleLength = tEndOffset - tStartOffset; |
| ByteBuffer srcBuffer = src.getBuffer(); |
| System.arraycopy(srcBuffer.array(), tStartOffset, frames[frameIx].array(), offToCopy, tupleLength); |
| return true; |
| } |
| |
| @Override |
| public ByteBuffer getFrame(int frameIndex) { |
| return frames[frameIndex]; |
| } |
| |
| @Override |
| public void close() { |
| //clean up all frames |
| for (int i = 0; i < frames.length; i++) |
| frames[i] = null; |
| } |
| |
| /** |
| * @param parentResult |
| * is the container passed by the caller to contain the results |
| * @throws HyracksDataException |
| */ |
| private void addFrame(Slot[] parentResult) throws HyracksDataException { |
| clear(parentResult); |
| if ((lastFrame + 1) >= frames.length) { |
| return; |
| } |
| frames[++lastFrame] = allocateFrame(); |
| int l = frameSize - 2 * BSTNodeUtil.HEADER_SIZE; |
| BSTNodeUtil.setHeaderFooter(lastFrame, 0, l, true, frames); |
| initNewNode(lastFrame, 0); |
| |
| parentResult[1].copy(root); |
| if (parentResult[1].isNull()) { // root is null |
| root.set(lastFrame, 0); |
| initNewNode(root.getFrameIx(), root.getOffset()); |
| parentResult[1].copy(root); |
| return; |
| } |
| |
| while (!parentResult[1].isNull()) { |
| if (BSTNodeUtil.getLength(parentResult[1], frames, convertBuffer) == l) { |
| append(parentResult[1].getFrameIx(), parentResult[1].getOffset(), lastFrame, 0); |
| parentResult[1].set(lastFrame, 0); |
| return; |
| } |
| if (l < BSTNodeUtil.getLength(parentResult[1], frames, convertBuffer)) { |
| if (isNodeNull(BSTNodeUtil.getLeftChildFrameIx(parentResult[1], frames, convertBuffer), |
| BSTNodeUtil.getLeftChildOffset(parentResult[1], frames, convertBuffer))) { |
| BSTNodeUtil.setLeftChild(parentResult[1].getFrameIx(), parentResult[1].getOffset(), lastFrame, 0, |
| frames); |
| parentResult[0].copy(parentResult[1]); |
| parentResult[1].set(lastFrame, 0); |
| return; |
| } else { |
| parentResult[0].copy(parentResult[1]); |
| parentResult[1].set(BSTNodeUtil.getLeftChildFrameIx(parentResult[1], frames, convertBuffer), |
| BSTNodeUtil.getLeftChildOffset(parentResult[1], frames, convertBuffer)); |
| } |
| } else { |
| if (isNodeNull(BSTNodeUtil.getRightChildFrameIx(parentResult[1], frames, convertBuffer), |
| BSTNodeUtil.getRightChildOffset(parentResult[1], frames, convertBuffer))) { |
| BSTNodeUtil.setRightChild(parentResult[1].getFrameIx(), parentResult[1].getOffset(), lastFrame, 0, |
| frames); |
| parentResult[0].copy(parentResult[1]); |
| parentResult[1].set(lastFrame, 0); |
| return; |
| } else { |
| parentResult[0].copy(parentResult[1]); |
| parentResult[1].set(BSTNodeUtil.getRightChildFrameIx(parentResult[1], frames, convertBuffer), |
| BSTNodeUtil.getRightChildOffset(parentResult[1], frames, convertBuffer)); |
| } |
| } |
| } |
| throw new HyracksDataException("New Frame could not be added to BSTMemMgr"); |
| } |
| |
| private void insert(int fix, int off, int length) throws HyracksDataException { |
| BSTNodeUtil.setHeaderFooter(fix, off, length, true, frames); |
| initNewNode(fix, off); |
| |
| if (root.isNull()) { |
| root.set(fix, off); |
| return; |
| } |
| |
| insertSlot.clear(); |
| insertSlot.copy(root); |
| while (!insertSlot.isNull()) { |
| int curSlotLen = BSTNodeUtil.getLength(insertSlot, frames, convertBuffer); |
| if (curSlotLen == length) { |
| append(insertSlot.getFrameIx(), insertSlot.getOffset(), fix, off); |
| return; |
| } |
| if (length < curSlotLen) { |
| int leftChildFIx = BSTNodeUtil.getLeftChildFrameIx(insertSlot, frames, convertBuffer); |
| int leftChildOffset = BSTNodeUtil.getLeftChildOffset(insertSlot, frames, convertBuffer); |
| if (isNodeNull(leftChildFIx, leftChildOffset)) { |
| initNewNode(fix, off); |
| BSTNodeUtil.setLeftChild(insertSlot.getFrameIx(), insertSlot.getOffset(), fix, off, frames); |
| return; |
| } else { |
| insertSlot.set(leftChildFIx, leftChildOffset); |
| } |
| } else { |
| int rightChildFIx = BSTNodeUtil.getRightChildFrameIx(insertSlot, frames, convertBuffer); |
| int rightChildOffset = BSTNodeUtil.getRightChildOffset(insertSlot, frames, convertBuffer); |
| if (isNodeNull(rightChildFIx, rightChildOffset)) { |
| initNewNode(fix, off); |
| BSTNodeUtil.setRightChild(insertSlot.getFrameIx(), insertSlot.getOffset(), fix, off, frames); |
| return; |
| } else { |
| insertSlot.set(rightChildFIx, rightChildOffset); |
| } |
| } |
| } |
| throw new HyracksDataException("Failure in node insertion into BST in BSTMemMgr"); |
| } |
| |
| /** |
| * @param length |
| * @param target |
| * is the container sent by the caller to hold the results |
| */ |
| private void search(int length, Slot[] target) { |
| clear(target); |
| result.clear(); |
| |
| if (root.isNull()) { |
| return; |
| } |
| |
| lastLeftParent.clear(); |
| lastLeft.clear(); |
| parent.clear(); |
| result.copy(root); |
| |
| while (!result.isNull()) { |
| if (BSTNodeUtil.getLength(result, frames, convertBuffer) == length) { |
| target[0].copy(parent); |
| target[1].copy(result); |
| return; |
| } |
| if (length < BSTNodeUtil.getLength(result, frames, convertBuffer)) { |
| lastLeftParent.copy(parent); |
| lastLeft.copy(result); |
| parent.copy(result); |
| int fix = BSTNodeUtil.getLeftChildFrameIx(result, frames, convertBuffer); |
| int off = BSTNodeUtil.getLeftChildOffset(result, frames, convertBuffer); |
| result.set(fix, off); |
| } else { |
| parent.copy(result); |
| int fix = BSTNodeUtil.getRightChildFrameIx(result, frames, convertBuffer); |
| int off = BSTNodeUtil.getRightChildOffset(result, frames, convertBuffer); |
| result.set(fix, off); |
| } |
| } |
| |
| target[0].copy(lastLeftParent); |
| target[1].copy(lastLeft); |
| |
| } |
| |
| private void append(int headFix, int headOff, int nodeFix, int nodeOff) { |
| initNewNode(nodeFix, nodeOff); |
| |
| int fix = BSTNodeUtil.getNextFrameIx(headFix, headOff, frames, convertBuffer); // frameIx |
| // for |
| // the |
| // current |
| // next |
| // of |
| // head |
| int off = BSTNodeUtil.getNextOffset(headFix, headOff, frames, convertBuffer); // offset |
| // for |
| // the |
| // current |
| // next |
| // of |
| // head |
| BSTNodeUtil.setNext(nodeFix, nodeOff, fix, off, frames); |
| |
| if (!isNodeNull(fix, off)) { |
| BSTNodeUtil.setPrev(fix, off, nodeFix, nodeOff, frames); |
| } |
| BSTNodeUtil.setPrev(nodeFix, nodeOff, headFix, headOff, frames); |
| BSTNodeUtil.setNext(headFix, headOff, nodeFix, nodeOff, frames); |
| } |
| |
| private int[] split(Slot listHead, Slot parent, int length) { |
| int l2 = BSTNodeUtil.getLength(listHead, frames, convertBuffer) - length - 2 * BSTNodeUtil.HEADER_SIZE; |
| // We split the node after slots-list head |
| if (!isNodeNull(BSTNodeUtil.getNextFrameIx(listHead, frames, convertBuffer), |
| BSTNodeUtil.getNextOffset(listHead, frames, convertBuffer))) { |
| int afterHeadFix = BSTNodeUtil.getNextFrameIx(listHead, frames, convertBuffer); |
| int afterHeadOff = BSTNodeUtil.getNextOffset(listHead, frames, convertBuffer); |
| int afHNextFix = BSTNodeUtil.getNextFrameIx(afterHeadFix, afterHeadOff, frames, convertBuffer); |
| int afHNextOff = BSTNodeUtil.getNextOffset(afterHeadFix, afterHeadOff, frames, convertBuffer); |
| BSTNodeUtil.setNext(listHead.getFrameIx(), listHead.getOffset(), afHNextFix, afHNextOff, frames); |
| if (!isNodeNull(afHNextFix, afHNextOff)) { |
| BSTNodeUtil.setPrev(afHNextFix, afHNextOff, listHead.getFrameIx(), listHead.getOffset(), frames); |
| } |
| int secondOffset = afterHeadOff + length + 2 * BSTNodeUtil.HEADER_SIZE; |
| BSTNodeUtil.setHeaderFooter(afterHeadFix, afterHeadOff, length, true, frames); |
| BSTNodeUtil.setHeaderFooter(afterHeadFix, secondOffset, l2, true, frames); |
| |
| return new int[] { afterHeadFix, afterHeadOff, afterHeadFix, secondOffset }; |
| } |
| // We split the head |
| int secondOffset = listHead.getOffset() + length + 2 * BSTNodeUtil.HEADER_SIZE; |
| BSTNodeUtil.setHeaderFooter(listHead.getFrameIx(), listHead.getOffset(), length, true, frames); |
| BSTNodeUtil.setHeaderFooter(listHead.getFrameIx(), secondOffset, l2, true, frames); |
| |
| fixTreePtrs(listHead.getFrameIx(), listHead.getOffset(), parent.getFrameIx(), parent.getOffset()); |
| return new int[] { listHead.getFrameIx(), listHead.getOffset(), listHead.getFrameIx(), secondOffset }; |
| } |
| |
| private void fixTreePtrs(int nodeFrameIx, int nodeOffset, int parentFrameIx, int parentOffset) { |
| int nodeLeftChildFrameIx = BSTNodeUtil.getLeftChildFrameIx(nodeFrameIx, nodeOffset, frames, convertBuffer); |
| int nodeLeftChildOffset = BSTNodeUtil.getLeftChildOffset(nodeFrameIx, nodeOffset, frames, convertBuffer); |
| int nodeRightChildFrameIx = BSTNodeUtil.getRightChildFrameIx(nodeFrameIx, nodeOffset, frames, convertBuffer); |
| int nodeRightChildOffset = BSTNodeUtil.getRightChildOffset(nodeFrameIx, nodeOffset, frames, convertBuffer); |
| |
| int status = -1; // (status==0 if node is left child of parent) |
| // (status==1 if node is right child of parent) |
| if (!isNodeNull(parentFrameIx, parentOffset)) { |
| int nlen = BSTNodeUtil.getActualLength(BSTNodeUtil |
| .getLength(nodeFrameIx, nodeOffset, frames, convertBuffer)); |
| int plen = BSTNodeUtil.getActualLength(BSTNodeUtil.getLength(parentFrameIx, parentOffset, frames, |
| convertBuffer)); |
| status = ((nlen < plen) ? 0 : 1); |
| } |
| |
| if (!isNodeNull(nodeLeftChildFrameIx, nodeLeftChildOffset) |
| && !isNodeNull(nodeRightChildFrameIx, nodeRightChildOffset)) { // Node |
| // has |
| // two |
| // children |
| int pMinFIx = nodeFrameIx; |
| int pMinOff = nodeOffset; |
| int minFIx = nodeRightChildFrameIx; |
| int minOff = nodeRightChildOffset; |
| int nextLeftFIx = BSTNodeUtil.getLeftChildFrameIx(minFIx, minOff, frames, convertBuffer); |
| int nextLeftOff = BSTNodeUtil.getLeftChildOffset(minFIx, minOff, frames, convertBuffer); |
| |
| while (!isNodeNull(nextLeftFIx, nextLeftOff)) { |
| pMinFIx = minFIx; |
| pMinOff = minOff; |
| minFIx = nextLeftFIx; |
| minOff = nextLeftOff; |
| nextLeftFIx = BSTNodeUtil.getLeftChildFrameIx(minFIx, minOff, frames, convertBuffer); // min |
| // is |
| // now |
| // pointing |
| // to |
| // current |
| // (old) |
| // next |
| // left |
| nextLeftOff = BSTNodeUtil.getLeftChildOffset(minFIx, minOff, frames, convertBuffer); // min |
| // is |
| // now |
| // pointing |
| // to |
| // current |
| // (old) |
| // next |
| // left |
| } |
| |
| if ((nodeRightChildFrameIx == minFIx) && (nodeRightChildOffset == minOff)) { // nrc |
| // is |
| // the |
| // same as min |
| BSTNodeUtil.setLeftChild(nodeRightChildFrameIx, nodeRightChildOffset, nodeLeftChildFrameIx, |
| nodeLeftChildOffset, frames); |
| } else { // min is different from nrc |
| int minRightFIx = BSTNodeUtil.getRightChildFrameIx(minFIx, minOff, frames, convertBuffer); |
| int minRightOffset = BSTNodeUtil.getRightChildOffset(minFIx, minOff, frames, convertBuffer); |
| BSTNodeUtil.setRightChild(minFIx, minOff, nodeRightChildFrameIx, nodeRightChildOffset, frames); |
| BSTNodeUtil.setLeftChild(minFIx, minOff, nodeLeftChildFrameIx, nodeLeftChildOffset, frames); |
| BSTNodeUtil.setLeftChild(pMinFIx, pMinOff, minRightFIx, minRightOffset, frames); |
| } |
| |
| // Now dealing with the parent |
| if (!isNodeNull(parentFrameIx, parentOffset)) { |
| if (status == 0) { |
| BSTNodeUtil.setLeftChild(parentFrameIx, parentOffset, minFIx, minOff, frames); |
| } else if (status == 1) { |
| BSTNodeUtil.setRightChild(parentFrameIx, parentOffset, minFIx, minOff, frames); |
| } |
| } else { // No parent (node was the root) |
| root.set(minFIx, minOff); |
| } |
| return; |
| } |
| |
| else if (!isNodeNull(nodeLeftChildFrameIx, nodeLeftChildOffset)) { // Node |
| // has |
| // only |
| // left |
| // child |
| if (status == 0) { |
| BSTNodeUtil |
| .setLeftChild(parentFrameIx, parentOffset, nodeLeftChildFrameIx, nodeLeftChildOffset, frames); |
| } else if (status == 1) { |
| BSTNodeUtil.setRightChild(parentFrameIx, parentOffset, nodeLeftChildFrameIx, nodeLeftChildOffset, |
| frames); |
| } else if (status == -1) { // No parent, so node is root |
| root.set(nodeLeftChildFrameIx, nodeLeftChildOffset); |
| } |
| return; |
| } |
| |
| else if (!isNodeNull(nodeRightChildFrameIx, nodeRightChildOffset)) { // Node |
| // has |
| // only |
| // right |
| // child |
| if (status == 0) { |
| BSTNodeUtil.setLeftChild(parentFrameIx, parentOffset, nodeRightChildFrameIx, nodeRightChildOffset, |
| frames); |
| } else if (status == 1) { |
| BSTNodeUtil.setRightChild(parentFrameIx, parentOffset, nodeRightChildFrameIx, nodeRightChildOffset, |
| frames); |
| } else if (status == -1) { // No parent, so node is root |
| root.set(nodeRightChildFrameIx, nodeRightChildOffset); |
| } |
| return; |
| } |
| |
| else { // Node is leaf (no children) |
| if (status == 0) { |
| BSTNodeUtil.setLeftChild(parentFrameIx, parentOffset, BSTNodeUtil.INVALID_INDEX, |
| BSTNodeUtil.INVALID_INDEX, frames); |
| } else if (status == 1) { |
| BSTNodeUtil.setRightChild(parentFrameIx, parentOffset, BSTNodeUtil.INVALID_INDEX, |
| BSTNodeUtil.INVALID_INDEX, frames); |
| } else { // node was the only node in the tree |
| root.clear(); |
| } |
| return; |
| } |
| } |
| |
| /** |
| * Allocation with no splitting but padding |
| * |
| * @param node |
| * @param parent |
| * @param result |
| * is the container sent by the caller to hold the results |
| */ |
| private void allocate(Slot node, Slot parent, int length, Slot result) { |
| int nextFix = BSTNodeUtil.getNextFrameIx(node, frames, convertBuffer); |
| int nextOff = BSTNodeUtil.getNextOffset(node, frames, convertBuffer); |
| if (!isNodeNull(nextFix, nextOff)) { |
| int nextOfNextFIx = BSTNodeUtil.getNextFrameIx(nextFix, nextOff, frames, convertBuffer); |
| int nextOfNextOffset = BSTNodeUtil.getNextOffset(nextFix, nextOff, frames, convertBuffer); |
| BSTNodeUtil.setNext(node.getFrameIx(), node.getOffset(), nextOfNextFIx, nextOfNextOffset, frames); |
| if (!isNodeNull(nextOfNextFIx, nextOfNextOffset)) { |
| BSTNodeUtil.setPrev(nextOfNextFIx, nextOfNextOffset, node.getFrameIx(), node.getOffset(), frames); |
| } |
| BSTNodeUtil.setHeaderFooter(nextFix, nextOff, length, false, frames); |
| result.set(nextFix, nextOff); |
| return; |
| } |
| |
| fixTreePtrs(node.getFrameIx(), node.getOffset(), parent.getFrameIx(), parent.getOffset()); |
| BSTNodeUtil.setHeaderFooter(node.getFrameIx(), node.getOffset(), length, false, frames); |
| result.copy(node); |
| } |
| |
| private void removeFromList(int fix, int off) { |
| int nextFIx = BSTNodeUtil.getNextFrameIx(fix, off, frames, convertBuffer); |
| int nextOffset = BSTNodeUtil.getNextOffset(fix, off, frames, convertBuffer); |
| int prevFIx = BSTNodeUtil.getPrevFrameIx(fix, off, frames, convertBuffer); |
| int prevOffset = BSTNodeUtil.getPrevOffset(fix, off, frames, convertBuffer); |
| if (!isNodeNull(prevFIx, prevOffset) && !isNodeNull(nextFIx, nextOffset)) { |
| BSTNodeUtil.setNext(prevFIx, prevOffset, nextFIx, nextOffset, frames); |
| BSTNodeUtil.setPrev(nextFIx, nextOffset, prevFIx, prevOffset, frames); |
| BSTNodeUtil.setNext(fix, off, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| BSTNodeUtil.setPrev(fix, off, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| return; |
| } |
| if (!isNodeNull(prevFIx, prevOffset)) { |
| BSTNodeUtil.setNext(prevFIx, prevOffset, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| BSTNodeUtil.setPrev(fix, off, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| return; |
| } |
| |
| // We need to find the parent, so we can fix the tree |
| int parentFIx = BSTNodeUtil.INVALID_INDEX; |
| int parentOffset = BSTNodeUtil.INVALID_INDEX; |
| int length = BSTNodeUtil.getActualLength(BSTNodeUtil.getLength(fix, off, frames, convertBuffer)); |
| fix = root.getFrameIx(); |
| off = root.getOffset(); |
| int curLen = BSTNodeUtil.getLength(fix, off, frames, convertBuffer); |
| while (length != curLen) { |
| parentFIx = fix; |
| parentOffset = off; |
| if (length < curLen) { |
| fix = BSTNodeUtil.getLeftChildFrameIx(parentFIx, parentOffset, frames, convertBuffer); // parentFIx |
| // is |
| // now |
| // the |
| // old(current) |
| // fix |
| off = BSTNodeUtil.getLeftChildOffset(parentFIx, parentOffset, frames, convertBuffer); // parentOffset |
| // is |
| // now |
| // the |
| // old(current) |
| // off |
| } else { |
| fix = BSTNodeUtil.getRightChildFrameIx(parentFIx, parentOffset, frames, convertBuffer); // parentFIx |
| // is |
| // now |
| // the |
| // old(current) |
| // fix |
| off = BSTNodeUtil.getRightChildOffset(parentFIx, parentOffset, frames, convertBuffer); // parentOffset |
| // is |
| // now |
| // the |
| // old(current) |
| // off |
| } |
| curLen = BSTNodeUtil.getLength(fix, off, frames, convertBuffer); |
| } |
| |
| if (!isNodeNull(nextFIx, nextOffset)) { // it is head of the list (in |
| // the |
| // tree) |
| BSTNodeUtil.setPrev(nextFIx, nextOffset, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| int nodeLeftChildFIx = BSTNodeUtil.getLeftChildFrameIx(fix, off, frames, convertBuffer); |
| int nodeLeftChildOffset = BSTNodeUtil.getLeftChildOffset(fix, off, frames, convertBuffer); |
| int nodeRightChildFix = BSTNodeUtil.getRightChildFrameIx(fix, off, frames, convertBuffer); |
| int nodeRightChildOffset = BSTNodeUtil.getRightChildOffset(fix, off, frames, convertBuffer); |
| BSTNodeUtil.setLeftChild(nextFIx, nextOffset, nodeLeftChildFIx, nodeLeftChildOffset, frames); |
| BSTNodeUtil.setRightChild(nextFIx, nextOffset, nodeRightChildFix, nodeRightChildOffset, frames); |
| if (!isNodeNull(parentFIx, parentOffset)) { |
| int parentLength = BSTNodeUtil.getLength(parentFIx, parentOffset, frames, convertBuffer); |
| if (length < parentLength) { |
| BSTNodeUtil.setLeftChild(parentFIx, parentOffset, nextFIx, nextOffset, frames); |
| } else { |
| BSTNodeUtil.setRightChild(parentFIx, parentOffset, nextFIx, nextOffset, frames); |
| } |
| } |
| |
| if ((root.getFrameIx() == fix) && (root.getOffset() == off)) { |
| root.set(nextFIx, nextOffset); |
| } |
| |
| return; |
| } |
| |
| fixTreePtrs(fix, off, parentFIx, parentOffset); |
| } |
| |
| private void clear(Slot[] s) { |
| s[0].clear(); |
| s[1].clear(); |
| } |
| |
| private boolean isNodeNull(int frameIx, int offset) { |
| return ((frameIx == BSTNodeUtil.INVALID_INDEX) || (offset == BSTNodeUtil.INVALID_INDEX) || (frames[frameIx] == null)); |
| } |
| |
| private boolean shouldSplit(int slotLength, int reqLength) { |
| return ((slotLength - reqLength) >= BSTNodeUtil.MINIMUM_FREE_SLOT_SIZE); |
| } |
| |
| private void initNewNode(int frameIx, int offset) { |
| BSTNodeUtil.setLeftChild(frameIx, offset, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| BSTNodeUtil.setRightChild(frameIx, offset, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| BSTNodeUtil.setNext(frameIx, offset, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| BSTNodeUtil.setPrev(frameIx, offset, BSTNodeUtil.INVALID_INDEX, BSTNodeUtil.INVALID_INDEX, frames); |
| } |
| |
| private ByteBuffer allocateFrame() { |
| return ctx.allocateFrame(); |
| } |
| |
| public String debugPrintMemory() { |
| Slot s = new Slot(0, 0); |
| if (s.isNull()) { |
| return "memory:\tNull"; |
| } |
| |
| String m = "memory:\n" + debugPrintSlot(0, 0) + "\n"; |
| int length = BSTNodeUtil.getActualLength(BSTNodeUtil.getLength(0, 0, frames, convertBuffer)); |
| int noff = (length + 2 * BSTNodeUtil.HEADER_SIZE >= frameSize ? BSTNodeUtil.INVALID_INDEX : length + 2 |
| * BSTNodeUtil.HEADER_SIZE); |
| int nfix = (noff == BSTNodeUtil.INVALID_INDEX ? ((frames.length == 1) ? BSTNodeUtil.INVALID_INDEX : 1) : 0); |
| if (noff == BSTNodeUtil.INVALID_INDEX && nfix != BSTNodeUtil.INVALID_INDEX) { |
| noff = 0; |
| } |
| s.set(nfix, noff); |
| while (!isNodeNull(s.getFrameIx(), s.getOffset())) { |
| m += debugPrintSlot(s.getFrameIx(), s.getOffset()) + "\n"; |
| length = BSTNodeUtil.getActualLength(BSTNodeUtil.getLength(s.getFrameIx(), s.getOffset(), frames, |
| convertBuffer)); |
| noff = (s.getOffset() + length + 2 * BSTNodeUtil.HEADER_SIZE >= frameSize ? BSTNodeUtil.INVALID_INDEX : s |
| .getOffset() + length + 2 * BSTNodeUtil.HEADER_SIZE); |
| nfix = (noff == BSTNodeUtil.INVALID_INDEX ? ((frames.length - 1 == s.getFrameIx()) ? BSTNodeUtil.INVALID_INDEX |
| : s.getFrameIx() + 1) |
| : s.getFrameIx()); |
| if (noff == BSTNodeUtil.INVALID_INDEX && nfix != BSTNodeUtil.INVALID_INDEX) { |
| noff = 0; |
| } |
| s.set(nfix, noff); |
| } |
| return m; |
| } |
| |
| public String debugPrintTree() { |
| Slot node = new Slot(); |
| node.copy(root); |
| if (!node.isNull()) { |
| return debugPrintSubTree(node); |
| } |
| return "Null"; |
| } |
| |
| private String debugPrintSubTree(Slot r) { |
| Slot node = new Slot(); |
| node.copy(r); |
| int fix = node.getFrameIx(); |
| int off = node.getOffset(); |
| int lfix = BSTNodeUtil.getLeftChildFrameIx(node, frames, convertBuffer); |
| int loff = BSTNodeUtil.getLeftChildOffset(node, frames, convertBuffer); |
| int rfix = BSTNodeUtil.getRightChildFrameIx(node, frames, convertBuffer); |
| int roff = BSTNodeUtil.getRightChildOffset(node, frames, convertBuffer); |
| int nfix = BSTNodeUtil.getNextFrameIx(node, frames, convertBuffer); |
| int noff = BSTNodeUtil.getNextOffset(node, frames, convertBuffer); |
| int pfix = BSTNodeUtil.getPrevFrameIx(node, frames, convertBuffer); |
| int poff = BSTNodeUtil.getPrevOffset(node, frames, convertBuffer); |
| |
| String s = "{" + r.getFrameIx() + ", " + r.getOffset() + " (Len: " |
| + BSTNodeUtil.getLength(fix, off, frames, convertBuffer) + ") - " + "(LC: " |
| + debugPrintSlot(lfix, loff) + ") - " + "(RC: " + debugPrintSlot(rfix, roff) + ") - " + "(NX: " |
| + debugPrintSlot(nfix, noff) + ") - " + "(PR: " + debugPrintSlot(pfix, poff) + ") }\n"; |
| if (!isNodeNull(lfix, loff)) { |
| s += debugPrintSubTree(new Slot(lfix, loff)) + "\n"; |
| } |
| if (!isNodeNull(rfix, roff)) { |
| s += debugPrintSubTree(new Slot(rfix, roff)) + "\n"; |
| } |
| |
| return s; |
| } |
| |
| private String debugPrintSlot(int fix, int off) { |
| if (isNodeNull(fix, off)) { |
| return BSTNodeUtil.INVALID_INDEX + ", " + BSTNodeUtil.INVALID_INDEX; |
| } |
| int l = BSTNodeUtil.getLength(fix, off, frames, convertBuffer); |
| int al = BSTNodeUtil.getActualLength(l); |
| boolean f = BSTNodeUtil.isFree(fix, off, frames); |
| return fix + ", " + off + " (free: " + f + ") (Len: " + l + ") (actual len: " + al + ") "; |
| } |
| } |
