0001: package com.quadcap.sql.index;
0002:
0003: /* Copyright 1997 - 2003 Quadcap Software. All rights reserved.
0004: *
0005: * This software is distributed under the Quadcap Free Software License.
0006: * This software may be used or modified for any purpose, personal or
0007: * commercial. Open Source redistributions are permitted. Commercial
0008: * redistribution of larger works derived from, or works which bundle
0009: * this software requires a "Commercial Redistribution License"; see
0010: * http://www.quadcap.com/purchase.
0011: *
0012: * Redistributions qualify as "Open Source" under one of the following terms:
0013: *
0014: * Redistributions are made at no charge beyond the reasonable cost of
0015: * materials and delivery.
0016: *
0017: * Redistributions are accompanied by a copy of the Source Code or by an
0018: * irrevocable offer to provide a copy of the Source Code for up to three
0019: * years at the cost of materials and delivery. Such redistributions
0020: * must allow further use, modification, and redistribution of the Source
0021: * Code under substantially the same terms as this license.
0022: *
0023: * Redistributions of source code must retain the copyright notices as they
0024: * appear in each source code file, these license terms, and the
0025: * disclaimer/limitation of liability set forth as paragraph 6 below.
0026: *
0027: * Redistributions in binary form must reproduce this Copyright Notice,
0028: * these license terms, and the disclaimer/limitation of liability set
0029: * forth as paragraph 6 below, in the documentation and/or other materials
0030: * provided with the distribution.
0031: *
0032: * The Software is provided on an "AS IS" basis. No warranty is
0033: * provided that the Software is free of defects, or fit for a
0034: * particular purpose.
0035: *
0036: * Limitation of Liability. Quadcap Software shall not be liable
0037: * for any damages suffered by the Licensee or any third party resulting
0038: * from use of the Software.
0039: */
0040:
0041: import java.io.IOException;
0042: import java.io.PrintStream;
0043:
0044: import com.quadcap.sql.file.Block;
0045: import com.quadcap.sql.file.BlockFile;
0046: import com.quadcap.sql.file.ByteUtil;
0047: import com.quadcap.sql.file.SubPageManager;
0048:
0049: import com.quadcap.util.Debug;
0050: import com.quadcap.util.Util;
0051:
0052: /**
0053: * This class represents a node in the btree.
0054: * <p>
0055: *
0056: * <b>Things to think about:</b>
0057: * <p>
0058: * <UL>
0059: * <LI>Key Compression using dictionary? With a large enough node, say
0060: * 4 or 8 k, you could perform a block compression
0061: * <LI>Key Endianness (X.500 keys are LSB, most others are MSB)
0062: * <LI>Large data stored in overflow areas (blockstream)
0063: * <LI>Thread-safeness
0064: * <LI>Improve block garbage collection (it appears that some deleted
0065: * keys aren't properly counted as garbage!)
0066: * </UL>
0067: *
0068: * @author Stan Bailes
0069: */
0070:
0071: // struct node {
0072: // int count; /* number of items in this node */
0073: // int dataBottom; /* data area -- grows downward */
0074: // int flags; /* isRoot, */
0075: // int[] keyIndex; /* keyrefs, grows up */
0076: // byte[] empty; /* ... empty in the middle ... */
0077: // byte[] data; /* key + data, grows down */
0078: // }
0079: public class Bnode {
0080: //#ifdef DEBUG
0081: static final boolean paranoid = false;
0082: //#endif
0083:
0084: Btree tree;
0085: BlockFile file;
0086: long blockRef;
0087:
0088: /** The number of octets in the representation of a reference to
0089: * a byte offset in the data area of this block. Currently,
0090: * bnode blocks can't be larger than 65536 because of the
0091: * two byte ref size.
0092: */
0093: public static final int REF_SIZE = 2;
0094:
0095: /** Number of key/data pairs in this node. */
0096: static final int fCount = 0;
0097:
0098: /** Bottom of data area -- grows downward. */
0099: static final int fDataBOS = 4;
0100:
0101: /** Flags */
0102: static final int fFlags = 8;
0103: static final int IS_LEAF = 0x0001;
0104: static final int BNODE_MAGICF = 0xff00;
0105: static final int BNODE_MAGICV = 0xbd00;
0106:
0107: /**
0108: * Amount of space that could be reclaimed by repacking the
0109: * node. When keys are deleted, we don't immediately remove
0110: * the key/data pair in the data area. Instead, we remove the
0111: * pointer the pair from the key index list, and record (here)
0112: * the size of the key/data pair. Later, when the block becomes
0113: * full, we reclaim this space by repacking the data area to
0114: * eliminate the holes.
0115: */
0116: static final int fGarbage = 12;
0117:
0118: static final int fParent = 16;
0119:
0120: /** Start of key indices. */
0121: static final int fIndices = 24;
0122:
0123: /**
0124: * Construct a node from a buffer.
0125: * @param tree the Btree containing this node
0126: * @param blockRef the block number in <b>file</b> of this node.
0127: */
0128: public Bnode(Btree tree, long blockRef) {
0129: //#ifdef DEBUG
0130: if (Trace.bit(2)) {
0131: Debug.println("Bnode(" + blockRef + ")");
0132: }
0133: //#endif
0134: this .tree = tree;
0135: this .file = tree.file;
0136: this .blockRef = blockRef;
0137: }
0138:
0139: /** <hr><font size =+1>Index Interface</font> <!----------------------!> */
0140:
0141: /**
0142: * Return the number of keys in this subtree. This implicitly only
0143: * counts entries in the leaf nodes.
0144: */
0145: public int size() throws IOException {
0146: Block b = getBlock();
0147: try {
0148: return size(b);
0149: } finally {
0150: b.decrRefCount();
0151: }
0152: }
0153:
0154: public int size(Block b) throws IOException {
0155: int tot = 0;
0156: for (int i = 0; i < getCount(b); i++) {
0157: Block c = getBlock(blockRef(b, i));
0158: try {
0159: if (isLeaf(c)) {
0160: tot += getCount(c);
0161: } else {
0162: tot += size(c);
0163: }
0164: } finally {
0165: c.decrRefCount();
0166: }
0167: }
0168: return tot;
0169: }
0170:
0171: /**
0172: * Implement the get operation.
0173: * @param key the search key
0174: * @return if the get succeeds, the data is returned as a byte array;
0175: * if the get fails, <b>null</b> is returned.
0176: */
0177: public final byte[] get(byte[] key, int klen) throws IOException {
0178: //#ifdef DEBUG
0179: if (Trace.bit(2)) {
0180: Debug.println("Bnode[" + blockRef + "] get("
0181: + Util.hexBytes(key) + ")");
0182: }
0183: //#endif
0184: Block b = getBlock();
0185: byte[] ret = null;
0186: try {
0187: ret = get(b, key, klen);
0188: } finally {
0189: b.decrRefCount();
0190: }
0191: return ret;
0192: }
0193:
0194: // /**
0195: // * Leaf level get operation
0196: // */
0197: // public final int get(byte[] key, int koff,
0198: // byte[] data, int off, int len) throws IOException {
0199: // Block b = getBlock();
0200: // try {
0201: // return get(b, key, koff, data, off, len);
0202: // } finally {
0203: // b.decrRefCount();
0204: // }
0205: // }
0206:
0207: /**
0208: * Implement the set operation.
0209: * @param key the key
0210: * @param data the data
0211: */
0212: public final boolean set(byte[] key, int klen, byte[] data,
0213: int doff, int dlen, boolean insOk, boolean updOk)
0214: throws IOException {
0215: //#ifdef DEBUG
0216: if (Trace.bit(2)) {
0217: Debug.println("[" + blockRef + "] set("
0218: + Util.hexBytes(key) + ", " + Util.hexBytes(data)
0219: + ")");
0220: }
0221: //#endif
0222: Block b = getBlock();
0223: try {
0224: return set(b, key, klen, data, doff, dlen, insOk, updOk);
0225: } finally {
0226: b.decrRefCount();
0227: }
0228: }
0229:
0230: /**
0231: * Implement the delete operation.
0232: * @param key the key
0233: */
0234: public final boolean delete(byte[] key) throws IOException {
0235: Block b = getBlock();
0236: try {
0237: return delete(b, key);
0238: } finally {
0239: b.decrRefCount();
0240: }
0241: }
0242:
0243: /**
0244: * A helper function to perform a single-level of the recursive search.
0245: * @param b the block to be searched.
0246: * @param key the search key
0247: * @return if found, the data, else null
0248: */
0249: final byte[] get(Block b, byte[] key, int klen) throws IOException {
0250: byte[] ret = null;
0251: int bs = bsearch(b, key, klen);
0252: if (!isLeaf(b)) {
0253: Block c = getSearchBlock(b, bs);
0254: try {
0255: ret = get(c, key, klen);
0256: } finally {
0257: c.decrRefCount();
0258: }
0259: } else if (bs >= 0) {
0260: ret = dataAtPos(b, bs);
0261: }
0262: //#ifdef DEBUG
0263: if (paranoid) {
0264: checkBlock(b);
0265: }
0266: //#endif
0267: return ret;
0268: }
0269:
0270: final Block getSearchBlock(Block b, int bs) throws IOException {
0271: int index = bs < 0 ? (-1 - bs) : bs;
0272: if (bs < 0) {
0273: index = index - 1;
0274: if (index < 0) {
0275: index = 0;
0276: }
0277: }
0278: Block c = getBlock(blockRef(b, index));
0279: return c;
0280: }
0281:
0282: // final int get(Block b, byte[] key, int koff,
0283: // byte[] data, int off, int len)
0284: // throws IOException
0285: // {
0286: // int ret = -1;
0287: // int bs = bsearch(b, tree.compare, key, 0, getCount(b)-1);
0288: // if (!isLeaf(b)) {
0289: // Block c = getSearchBlock(b, bs);
0290: // try {
0291: // ret = get(c, key, koff, data, off, len);
0292: // } finally {
0293: // c.decrRefCount();
0294: // }
0295: // } else {
0296: // if (bs >= 0) {
0297: // ret = dataAtPos(b, bs, koff, data, off, len);
0298: // } else {
0299: // ret = -1;
0300: // }
0301: // }
0302: // return ret;
0303: // }
0304:
0305: /**
0306: * Initialize an empty <b>BNode</b>.
0307: * <p><b>PRECONDITION:</b>Hold lock on <code>b</code>.
0308: * @param b the block to be initialized.
0309: */
0310: final void init(Block b, boolean isLeaf) throws IOException {
0311: setCount(b, 0);
0312: setFlags(b, (isLeaf ? IS_LEAF : 0) | BNODE_MAGICV);
0313: setBos(b, file.getPageSize());
0314: setGarbage(b, 0);
0315: setParent(b, 0);
0316: }
0317:
0318: final void init(boolean f) throws IOException {
0319: Block b = getBlock();
0320: try {
0321: init(b, f);
0322: } finally {
0323: b.decrRefCount();
0324: }
0325: }
0326:
0327: final void checkMagic() throws IOException {
0328: Block b = getBlock();
0329: try {
0330: if ((getFlags(b) & BNODE_MAGICF) != BNODE_MAGICV) {
0331: throw new IOException("Not a valid index node: "
0332: + SubPageManager.toString(b.getPageNum()));
0333: }
0334: } finally {
0335: b.decrRefCount();
0336: }
0337: }
0338:
0339: /**
0340: * Free the resources associated with this block. If the block is a
0341: * non-leaf node, free the entire subtree.
0342: */
0343: public final void free() throws IOException {
0344: free(blockRef);
0345: }
0346:
0347: /**
0348: * Free the resources associated with the specified block. If the block is a
0349: * non-leaf node, free the entire subtree.
0350: */
0351: private final void free(long blockNum) throws IOException {
0352: //#ifdef DEBUG
0353: if (blockNum == 0) {
0354: Debug
0355: .println("************************** Trying to free block 0!");
0356: return;
0357: }
0358: //#endif
0359: Block b = getBlock(blockNum);
0360: //#ifdef DEBUG
0361: if (Trace.bit(2)) {
0362: Debug.println("free(" + blockNum + ")");
0363: display(b, Debug.debugStream, false);
0364: }
0365: //#endif
0366: try {
0367: if (!isLeaf(b)) {
0368: for (int i = 0; i < getCount(b); i++) {
0369: free(blockRef(b, i));
0370: }
0371: }
0372: file.freePage(b.getPageNum());
0373: } finally {
0374: b.decrRefCount();
0375: }
0376: }
0377:
0378: /**
0379: * Perform a binary search of the keys in the specified block, searching
0380: * for the given key. If the key is found in the block, return the
0381: * index of the matching key. If the key isn't
0382: * found, return < 0, and for the key index which is the smallest
0383: * existing key greater than the given key, return
0384: * <code>0 - (index+1)</code>.
0385: * @param b the block to be searched.
0386: * @param key the search key
0387: * @param lo index of smallest element in search region
0388: * @param hi index of largest element in search region
0389: * @return if found, the index of the matching key/data pair. If not
0390: * found, return the index where the data would be found
0391: * as an expression of the form:<p>
0392: * <code>0 - (index + 1)</code>
0393: */
0394: final static int bsearch(Block b, Comparator c, byte[] key,
0395: int klen, int lo, int hi) throws IOException {
0396: while (hi >= lo) {
0397: int mid = (hi + lo) / 2;
0398: int ret = keyCompareAtPos(c, key, klen, b, mid);
0399: if (ret < 0)
0400: hi = mid - 1;
0401: else if (ret > 0)
0402: lo = mid + 1;
0403: else
0404: return mid;
0405: }
0406: return 0 - (hi + 2);
0407: }
0408:
0409: /**
0410: * Perform a binary search of the keys in the specified block, searching
0411: * for the given key. If the key is found in the block, return the
0412: * index of the matching key. If the key isn't
0413: * found, return < 0, and for the key index which is the smallest
0414: * existing key greater than the given key, return
0415: * <code>0 - (index+1)</code>.
0416: * @param b the block to be searched.
0417: * @param key the search key
0418: * @return if found, the index of the matching key/data pair. If not
0419: * found, return the index where the data would be found
0420: * as an expression of the form:<p>
0421: * <code>0 - (index + 1)</code>
0422: */
0423: final int bsearch(Block b, byte[] key, int klen) throws IOException {
0424: return bsearch(b, tree.compare, key, klen, 0, getCount(b) - 1);
0425: }
0426:
0427: /**
0428: * Return the data for a specified key as an integer
0429: */
0430: final static long blockRef(Block b, int index) throws IOException {
0431: return longDataAtPos(b, index);
0432: }
0433:
0434: /**
0435: * Recursive implementation of <code>set(key, data)</code>.<p>
0436: * <b>Precondition</b>: The caller must already have a write-lock on
0437: * <code>b</code>.
0438: * @param b the block to be searched
0439: * @param key the search key
0440: * @param data the data associated with the key
0441: * @return true if the key already existed before the set, false otherwise.
0442: */
0443: final boolean set(Block b, byte[] key, int klen, byte[] data,
0444: int doff, int dlen, boolean insOk, boolean updOk)
0445: throws IOException {
0446: //#ifdef DEBUG
0447: byte[] save = null;
0448: if (paranoid) {
0449: byte[] d = (byte[]) b.getData();
0450: save = new byte[d.length];
0451: System.arraycopy(d, 0, save, 0, d.length);
0452: }
0453: //#endif
0454: int bs = bsearch(b, key, klen);
0455: if (bs < 0 && !insOk) {
0456: throw new IOException("Key not found");
0457: } else if (bs >= 0 && !updOk) {
0458: throw new IOException("Key not unique");
0459: }
0460: int index = bs < 0 ? (-1 - bs) : bs;
0461: boolean ret = false;
0462: if (isLeaf(b)) {
0463: boolean replace = (bs >= 0);
0464: setKey(b, index, key, klen, data, doff, dlen, replace);
0465: ret = replace;
0466: } else {
0467: if (bs < 0) {
0468: index = index - 1;
0469: if (index < 0)
0470: index = 0;
0471: }
0472: Block c = getBlock(blockRef(b, index));
0473: try {
0474: ret = set(c, key, klen, data, doff, dlen, insOk, updOk);
0475: } finally {
0476: c.decrRefCount();
0477: }
0478: }
0479: //#ifdef DEBUG
0480: if (paranoid) {
0481: try {
0482: checkBlock(b);
0483: } catch (RuntimeException e) {
0484: b.setData(save);
0485: Debug.println("bs = " + bs);
0486: Debug.println("index = " + index);
0487: Debug.println("isLeaf() = " + isLeaf(b));
0488: Debug.println("key = " + Util.hexBytes(key));
0489: Debug.println("data = " + Util.hexBytes(data));
0490: Debug
0491: .println("checkSpace = "
0492: + debugcheckSpace(b, index, klen, dlen,
0493: bs >= 0));
0494: Debug.println("old block:");
0495: display(b, Debug.debugStream, false);
0496: }
0497: }
0498: //#endif
0499: return ret;
0500: }
0501:
0502: /**
0503: * Recursive implementation of <code>delete(key)</code>.
0504: * @param b the block to be searched
0505: * @param key the search key
0506: * @return true if the key already existed before the delete,
0507: * false otherwise.
0508: */
0509: final boolean delete(Block b, byte[] key) throws IOException {
0510: boolean ret = false;
0511: boolean del = false;
0512: int bs = bsearch(b, key, key.length);
0513: int index = bs < 0 ? (-1 - bs) : bs;
0514: // Debug.println(2, "delete([" + b.getPageNum() + "] " +
0515: // keybytes(key) +
0516: // "): bs = " + bs + ", index = " + index);
0517: if (isLeaf(b)) {
0518: if (bs >= 0) {
0519: del = deleteKeyAtPos(b, index, false);
0520: ret = true;
0521: }
0522: } else {
0523: if (bs < 0) {
0524: index = index - 1;
0525: if (index < 0)
0526: index = 0;
0527: }
0528: Block c = getBlock(blockRef(b, index));
0529: try {
0530: ret = delete(c, key);
0531: } finally {
0532: c.decrRefCount();
0533: }
0534: }
0535: //#ifdef DEBUG
0536: if (paranoid && !del)
0537: checkBlock(b);
0538: //#endif
0539: return ret;
0540: }
0541:
0542: //#ifdef DEBUG
0543: final void checkBlock(Block b) throws IOException {
0544: int g1 = getGarbage(b);
0545: int tk = 0;
0546: for (int i = 0; i < getCount(b); i++) {
0547: tk += existingKeyLength(b, i);
0548: if (i > 0) {
0549: byte[] k1 = keyAtPos(b, i - 1);
0550: byte[] k2 = keyAtPos(b, i);
0551: try {
0552: if (tree.compare.compare(k1, 0, k1.length, k2, 0,
0553: k2.length) >= 0) {
0554: try {
0555: display(b, System.out, false);
0556: } catch (Exception e) {
0557: }
0558: throw new RuntimeException("Bad key ordering");
0559: }
0560: } catch (RuntimeException e) {
0561: try {
0562: display(b, System.out, false);
0563: } catch (Exception ee) {
0564: }
0565: throw e;
0566: }
0567: }
0568: }
0569: int sk = file.getPageSize() - getBos(b);
0570: if (tk + g1 != sk) {
0571: try {
0572: display(b, System.out, false);
0573: } catch (Exception e) {
0574: }
0575: throw new RuntimeException("checkBlock: failure, "
0576: + (tk + g1) + " != " + sk);
0577: }
0578:
0579: }
0580:
0581: //#endif
0582:
0583: /**
0584: * Given a block and a key index, return the data for that index as a new
0585: * byte array.
0586: * @param b the block on which to operate.
0587: * @param index the index of the item for which the data is to be retrieved
0588: * @return the data for the key at the specified position in the node.
0589: */
0590: final static byte[] dataAtPos(Block b, int index) {
0591: int keyIndex = getKeyIndex(b, index);
0592:
0593: int[] start = new int[1];
0594: int keylen = getKeyLen(b, keyIndex, start);
0595: int keystart = start[0];
0596:
0597: int datastart = keystart + keylen;
0598: int datalen = getKeyLen(b, datastart, start);
0599: datastart = start[0];
0600: byte[] data = new byte[datalen];
0601: b.read(datastart, data, 0, data.length);
0602: return data;
0603: }
0604:
0605: final static int dataAtPos(Block b, int index, int koff,
0606: byte[] data, int off, int len) {
0607: int keyIndex = getKeyIndex(b, index);
0608:
0609: int[] start = new int[1];
0610: int keylen = getKeyLen(b, keyIndex, start);
0611: int keystart = start[0];
0612:
0613: int datastart = keystart + keylen;
0614: datastart = start[0];
0615:
0616: return b.read(datastart + koff, data, off, len);
0617: }
0618:
0619: /**
0620: * Given a block and a key index, return the data for that index as
0621: * a long.
0622: * @param b the block on which to operate.
0623: * @param index the index of the item for which the data is to be retrieved
0624: * @return the data for the key at the specified position in the node.
0625: */
0626: final static long longDataAtPos(Block b, int index) {
0627: int keyIndex = getKeyIndex(b, index);
0628:
0629: keyIndex = getKeyEnd(b, keyIndex); // skip to data
0630: if (b.readByte(keyIndex) != 8) {
0631: throw new RuntimeException("not a long: " + keyIndex + ": "
0632: + b.readByte(keyIndex));
0633: }
0634: return b.readLong(keyIndex + 1);
0635: }
0636:
0637: /**
0638: * Compute the total length of an existing key data pair, including
0639: * both key and data length fields.
0640: * @param b the block on which to operate.
0641: * @param index the index of the item for which the data is to be retrieved
0642: * @return the total number of data area bytes consumed by this item.
0643: */
0644: final static int existingKeyLength(Block b, int index) {
0645: int keyIndex = getKeyIndex(b, index);
0646:
0647: int[] start = new int[1];
0648: int keylen = getKeyLen(b, keyIndex, start);
0649: int keystart = start[0];
0650:
0651: int datastart = keystart + keylen;
0652: int datalen = getKeyLen(b, datastart, start);
0653: datastart = start[0];
0654: int end = datastart + datalen;
0655: return end - keyIndex;
0656: }
0657:
0658: /**
0659: * Given a block and a key index, return the key for that index as a new
0660: * byte array.
0661: * @param b the block on which to operate.
0662: * @param index the index of the item for which the key is to be retrieved
0663: */
0664: final static byte[] keyAtPos(Block b, int index) {
0665: int keyIndex = getKeyIndex(b, index);
0666:
0667: int[] start = new int[1];
0668: int keylen = getKeyLen(b, keyIndex, start);
0669: int keystart = start[0];
0670:
0671: byte[] key = new byte[keylen];
0672: b.read(keystart, key, 0, key.length);
0673: return key;
0674: }
0675:
0676: final static int getBytes(Block b, int pos, byte[] buf, int[] lenret) {
0677: int len = b.readByte(pos++) & 0xff;
0678: if ((len & 0x80) != 0) {
0679: int cnt = len & 0x7f;
0680: len = 0;
0681: while (cnt-- > 0) {
0682: len <<= 8;
0683: len += (b.readByte(pos++) & 0xff);
0684: }
0685: }
0686: lenret[0] = len;
0687: if (len > buf.length)
0688: return 0 - len;
0689: b.read(pos, buf, 0, len);
0690: return pos + len;
0691: }
0692:
0693: /**
0694: * Given a block and a key index, return the key for that index as a new
0695: * byte array.
0696: * @param b the block on which to operate.
0697: * @param index the index of the item for which the key is to be retrieved
0698: * @param buf the buffer into which the key bytes should be places
0699: * @param off the offset into the buffer
0700: * @param len the maximum number of bytes to write to the buffer
0701: *
0702: * @return the number of bytes returned, if sucessful. If the buffer
0703: * isn't big enough, we return a negative number '0 - k', where
0704: * 'k' is the actual key length.
0705: */
0706: public final static boolean getKeyAndData(Block b, int index,
0707: byte[] k, byte[] d, int[] lengths) {
0708: int pos = getKeyIndex(b, index);
0709: pos = getBytes(b, pos, k, lengths);
0710: int savelen = lengths[0];
0711: if (pos < 0)
0712: return false;
0713: pos = getBytes(b, pos, d, lengths);
0714: lengths[1] = lengths[0];
0715: lengths[0] = savelen;
0716: if (pos < 0)
0717: return false;
0718: return true;
0719: }
0720:
0721: /**
0722: * Perform a key comparison with the specified key in the block.
0723: * @param c the compare function
0724: * @param key the compare key
0725: * @param b the block to be compared
0726: * @param index the position of the key to be compared to the compare key
0727: *
0728: * @return the integer compare value (usu: -1, 0, 1)
0729: */
0730: static final int keyCompareAtPos(Comparator c, byte[] key,
0731: int klen, Block b, int index) throws IOException {
0732: int keypos = getKeyIndex(b, index);
0733: int r = getKeyLen(b, keypos);
0734: int start = (r >> 16) & 0xffff;
0735: int len = r & 0xffff;
0736: byte[] buf = (byte[]) b.getData();
0737: int ret = c.compare(key, 0, klen, buf, start, len);
0738: return ret;
0739: }
0740:
0741: /**
0742: * Find the length of the specified key, as well as the byte offset
0743: * to the start of the key.
0744: *
0745: * @param b the B-node
0746: * @param keypos the buffer offset where the key/data pair starts.
0747: * @param keystart an <b>out</b> parameter, used to return the buffer
0748: * offset where the actual key begins.
0749: */
0750: static final int getKeyLen(Block b, int keypos, int[] keystart) {
0751: int len = b.readByte(keypos++) & 0xff;
0752: if ((len & 0x80) != 0) {
0753: int cnt = len & 0x7f;
0754: len = 0;
0755: while (cnt-- > 0) {
0756: len <<= 8;
0757: len += (b.readByte(keypos++) & 0xff);
0758: }
0759: }
0760: keystart[0] = keypos;
0761: return len;
0762: }
0763:
0764: /**
0765: * Find the length of the specified key, as well as the byte offset
0766: * to the start of the key.
0767: *
0768: * @param b the B-node
0769: * @param keypos the buffer offset where the key/data pair starts.
0770: * @return the key length
0771: */
0772: final static int getKeyLen(Block b, int keypos) {
0773: int len = b.readByte(keypos++) & 0xff;
0774: if ((len & 0x80) != 0) {
0775: int cnt = len & 0x7f;
0776: len = 0;
0777: while (cnt-- > 0) {
0778: len <<= 8;
0779: len += (b.readByte(keypos++) & 0xff);
0780: }
0781: }
0782: return ((keypos & 0xffff) << 16) | (len & 0xffff);
0783: }
0784:
0785: /**
0786: * Find the length of the specified key, as well as the byte offset
0787: * to the start of the key.
0788: *
0789: * @param b the B-node
0790: * @param keypos the buffer offset where the key/data pair starts.
0791: * @return two 16-bit integers {start, len} encoded in a 32 bit int.
0792: */
0793: static final int getKeyEnd(Block b, int keypos) {
0794: int len = b.readByte(keypos++) & 0xff;
0795: if ((len & 0x80) != 0) {
0796: int cnt = len & 0x7f;
0797: len = 0;
0798: while (cnt-- > 0) {
0799: len <<= 8;
0800: len += (b.readByte(keypos++) & 0xff);
0801: }
0802: }
0803: return keypos + len;
0804: }
0805:
0806: /**
0807: * Compute the total number of bytes that will be required to store
0808: * the byte array 'b' plus its length code.
0809: * @param b the byte array
0810: * @return the length of the byte array plus the length of the length
0811: * code.
0812: */
0813: final static int totalLength(int len) {
0814: int lenlen = 1;
0815: if (len > 0x7f) {
0816: lenlen++;
0817: if (len > 0xff) {
0818: lenlen++;
0819: if (len > 0xffff) {
0820: lenlen++;
0821: if (len > 0xffffff) {
0822: lenlen++;
0823: }
0824: }
0825: }
0826: }
0827: return len + lenlen;
0828: }
0829:
0830: /**
0831: * Insert a key/data pair at the bottom of the data area and
0832: * return its offset. This method does <b>NOT</b> check the
0833: * capacity of the buffer -- it is assumed that the caller has
0834: * already ensured that enough space is available.
0835: * @param b the block to operate on
0836: * @param key the search key
0837: * @param data the data associated with the key
0838: */
0839: final static int insertKeyData(Block b, byte[] key, int klen,
0840: byte[] data, int doff, int dlen) {
0841: // ---- insert the key/data pair at the bottom of the data area
0842: int bos = getBos(b) - dlen;
0843: b.write(bos, data, doff, dlen);
0844: bos = writeLenLen(b, bos, dlen) - klen;
0845: b.write(bos, key, 0, klen);
0846: bos = writeLenLen(b, bos, klen);
0847: setBos(b, bos); // record the new data BOS.
0848: return bos;
0849: }
0850:
0851: /**
0852: * Insert or replace a key in the specified block, which may or may
0853: * not be a leaf block. Handle split operations: if a split is required,
0854: * determine which post-split block this key should be added to.
0855: * Also, if the new key happens to be key zero (i.e., the lowest valued
0856: * key in this block), then adjust the parent's reference to this block
0857: * accordingly. Although, maybe that can't happen?
0858: *
0859: * <p><b>PRECONDITION:</b> Lock/ref on block <code>b</code>
0860: * <p><b>POSTCONDITION:</b> Lock/ref on block <code>b</code>
0861: *
0862: * @return the block into which the key was actually stored. This
0863: * will be different from <code>b</code> if a split was
0864: * necessary.
0865: */
0866: final Block setKey(Block b, int index, byte[] key, int klen,
0867: byte[] data, int doff, int dlen, boolean replace)
0868: throws IOException {
0869: Block r = b;
0870: if (index < 0) {
0871: index = bsearch(b, key, klen);
0872: if (index < 0) {
0873: replace = false;
0874: index = -1 - index;
0875: }
0876: }
0877: // if it looks like we're inserting a key lower than the current
0878: // low key, remember the old low key, we'll have to update the parent
0879: // node.
0880: byte[] okey = (index == 0 && getCount(b) > 0) ? keyAtPos(b, 0)
0881: : null;
0882:
0883: if (!setKeyAtPos(b, index, key, klen, data, doff, dlen, replace)) {
0884: if (replace) {
0885: if (deleteKeyAtPos(b, index, true)) {
0886: //#ifdef DEBUG
0887: Debug.println("Just lost b!");
0888: //#endif
0889: }
0890: }
0891: Block[] ba = new Block[2];
0892: ba[0] = b;
0893: split(ba);
0894: b = ba[0];
0895: Block nb = ba[1];
0896:
0897: try {
0898: // After split, the key we were trying to add goes
0899: // into one of the two split blocks.
0900: int cv = keyCompareAtPos(tree.compare, key, klen, b, 0);
0901: r = cv < 0 ? nb : b;
0902:
0903: try {
0904: int ret = bsearch(r, key, klen);
0905: if (ret >= 0) {
0906: //#ifdef DEBUG
0907: Debug
0908: .println("After a split operation, the key was "
0909: + "found to be already present in the "
0910: + "target block at position "
0911: + ret);
0912: Debug.println("The key: " + Util.hexBytes(key));
0913: Debug.println("cv = " + cv);
0914: Debug.println("split L: ");
0915: display(ba[0], Debug.debugStream, false);
0916: Debug.println("split R: ");
0917: display(ba[1], Debug.debugStream, false);
0918: //#endif
0919: throw new RuntimeException(
0920: "internal error in setKey: dup, key = "
0921: + Util.strBytes(key));
0922: }
0923: ret = -1 - ret;
0924: if (!setKeyAtPos(r, ret, key, klen, data, doff,
0925: dlen, false)) {
0926: throw new RuntimeException(
0927: "com.quadcap.sql.index.Bnode: "
0928: + "internal error in setKey: no room. "
0929: + "key length = " + key.length
0930: + ", data.length = "
0931: + data.length);
0932: }
0933: if (ret == 0 && getCount(r) > 1) {
0934: newLow(r, keyAtPos(r, 1));
0935: }
0936: } finally {
0937: }
0938: } finally {
0939: nb.decrRefCount();
0940: }
0941: } else {
0942: if (okey != null && index == 0) {
0943: /* && (!replace || getCount(b) > 1)) */
0944: newLow(b, okey);
0945: }
0946: }
0947: return r;
0948: }
0949:
0950: /**
0951: * Split this block, by creaing a new block and moving half of this
0952: * block's keys into the new block. Then, add a new key to the parent
0953: * block to reflect the new block, and adjust the parent's old reference
0954: * to this block to reflect the new key distribution.
0955: *
0956: * <p><b>PRECONDITION:</b> We have a ref/lock on <code>ba[0]</code>
0957: * <p><b>POSTCONDITION:</b> We have a ref on <code>ba[1]</code>
0958: *
0959: * @param ba a two-element array, with <code>ba[0]</code> being
0960: * the pre-split block, and <code>ba[1]</code> the new block
0961: */
0962: final void split(Block[] ba) throws IOException {
0963: Block b = ba[0];
0964: long nbno = file.newPage();
0965: //#ifdef DEBUG
0966: if (Trace.bit(5)) {
0967: Debug.println(0, "split: new block = " + nbno);
0968: }
0969: //#endif
0970: Bnode node = this .tree.getNode(nbno);
0971: node.init(isLeaf(b));
0972: Block nb = null;
0973: boolean gotException = true;
0974: try {
0975: nb = node.getBlock();
0976: ba[1] = nb;
0977: splitHelp(ba, nbno);
0978: gotException = false;
0979: } finally {
0980: if (gotException) {
0981: if (nb != null) {
0982: nb.decrRefCount();
0983: ba[1] = null;
0984: }
0985: file.freePage(nbno);
0986: }
0987: }
0988: }
0989:
0990: /**
0991: * Split helper:
0992: * <p><b>PRECONDITION</b>: Ref/lock on both <code>ba[0], ba[1]</code>
0993: */
0994: final void splitHelp(Block[] ba, long nbno) throws IOException {
0995: Block b = ba[0];
0996: Block nb = ba[1];
0997: setParent(nb, getParent(b));
0998:
0999: //#ifdef DEBUG
1000: if (Trace.bit(5)) {
1001: Debug.println("BEFORE SPLIT: b");
1002: display(b, Debug.debugStream, false);
1003: Debug.println("BEFORE SPLIT: nb");
1004: display(nb, Debug.debugStream, false);
1005: }
1006: //#endif
1007:
1008: int more = capacity(b);
1009: int ncnt = 0;
1010: for (int i = 0; capacity(nb) > more + getGarbage(b); i++) {
1011: byte[] key = keyAtPos(b, i);
1012: byte[] data = dataAtPos(b, i);
1013: setKeyAtPos(nb, i, key, key.length, data, 0, data.length,
1014: false);
1015: if (!isLeaf(nb)) {
1016: Bnode child = this .tree.getNode(Util.integer(data));
1017: Block cb = child.getBlock();
1018: try {
1019: Bnode.setParent(cb, nbno);
1020: } finally {
1021: cb.decrRefCount();
1022: }
1023: }
1024: forgetKeyAtPos(b, i);
1025: more += REF_SIZE;
1026: ncnt++;
1027: }
1028: int cnt = getCount(b);
1029: int len = cnt - ncnt;
1030: moveKeys(b, ncnt, 0, len);
1031: setCount(b, len);
1032: gc(b);
1033: //#ifdef DEBUG
1034: if (paranoid)
1035: try {
1036: checkBlock(b);
1037: } catch (RuntimeException e) {
1038: Debug.print(e);
1039: }
1040: //#endif
1041:
1042: propogateSplit(ba);
1043: }
1044:
1045: /**
1046: * After the split operation, propagate information up the tree to
1047: * the parent block about the newly created block and the new key
1048: * distribution.
1049: *
1050: * @param ba a two-element array, with <code>ba[0]</code> being
1051: * the pre-split block, and <code>ba[1]</code> the new block
1052: */
1053: final void propogateSplit(Block[] ba) throws IOException {
1054: Block b = ba[0];
1055: Block nb = ba[1];
1056: long b_blk = b.getPageNum();
1057: long parentBlock = getParent(b);
1058: Bnode pnode = null;
1059: if (parentBlock == 0) {
1060: // ---- We're splitting the root block.
1061: // ---- We'd like for block 'b', which is currently the parent,
1062: // ---- to remain so. So we'll move the data in 'b' to 'b2',
1063: // ---- then rename 'b' to 'parent', and 'b2' to 'b'.
1064: // ---- I think.
1065: long b2 = file.newPage();
1066: Block b2b = getBlock(b2);
1067:
1068: // ---- no need to synchronize here, since we already hold the
1069: // ---- lock on the parent node, and nobody else knows about
1070: // ---- b2 yet.
1071: try {
1072: b2b.takeData(b);
1073: parentBlock = b.getPageNum();
1074: setParent(b2b, parentBlock);
1075: pnode = this .tree.getNode(parentBlock);
1076: pnode.init(false);
1077: ba[0] = b = b2b;
1078: if (!isLeaf(b2b))
1079: for (int i = 0; i < getCount(b2b); i++) {
1080: long cref = blockRef(b2b, i);
1081: Block c = getBlock(cref);
1082: try {
1083: setParent(c, b2);
1084: } finally {
1085: c.decrRefCount();
1086: }
1087: }
1088: b_blk = b2;
1089: } finally {
1090: b2b.decrRefCount();
1091: }
1092:
1093: } else {
1094: pnode = this .tree.getNode(parentBlock);
1095: }
1096:
1097: Block pb = pnode.getBlock();
1098: try {
1099: // ---- the parent currently has an entry for the old block,
1100: // ---- but with the key that is now associated with the new
1101: // ---- block. So we replace the old key, with the new block
1102: // ---- value, and we add a new key, with the old block value.
1103:
1104: // ---- replace the old key
1105: byte[] okey = keyAtPos(nb, 0);
1106: byte[] odat = Util.bytes(nb.getPageNum());
1107: Block r = setKey(pb, -1, okey, okey.length, odat, 0,
1108: odat.length, true);
1109: try {
1110: setParent(nb, r.getPageNum());
1111:
1112: // ---- add the new key
1113: byte[] nkey = keyAtPos(b, 0);
1114: byte[] ndat = Util.bytes(b.getPageNum());
1115:
1116: if (r != pb) {
1117: // if the parent block was split as a result of
1118: // the previous setKey, then it is possible that
1119: // 'b' and 'nb' were on the boundary of that
1120: // split, and will now have different parent
1121: // blocks. So we need to figure out which parent
1122: // 'b' should get...
1123:
1124: throw new RuntimeException("internal error");
1125: }
1126: r = setKey(r, -1, nkey, nkey.length, ndat, 0,
1127: ndat.length, false);
1128: setParent(b, r.getPageNum());
1129: } finally {
1130: }
1131:
1132: } finally {
1133: pb.decrRefCount();
1134: }
1135:
1136: }
1137:
1138: /**
1139: * Reclaim the data space occupied by deleted keys.
1140: */
1141: final void gc(Block b) throws IOException {
1142: //#ifdef DEBUG
1143: byte[] saved = null;
1144: if (paranoid) {
1145: saved = new byte[file.getPageSize()];
1146: System.arraycopy((byte[]) b.getData(), 0, saved, 0,
1147: saved.length);
1148: }
1149: //#endif
1150:
1151: int initcap = capacity(b);
1152: int amt = getGarbage(b);
1153: int cnt = getCount(b);
1154: if (amt > 0) {
1155: int size = 0;
1156: Object[][] pairs = new Object[2][cnt];
1157: for (int i = 0; i < cnt; i++) {
1158: size += existingKeyLength(b, i);
1159: pairs[0][i] = keyAtPos(b, i);
1160: pairs[1][i] = dataAtPos(b, i);
1161: }
1162: setBos(b, file.getPageSize());
1163: for (int i = 0; i < cnt; i++) {
1164: byte[] key = (byte[]) pairs[0][i];
1165: byte[] data = (byte[]) pairs[1][i];
1166: int pos = insertKeyData(b, key, key.length, data, 0,
1167: data.length);
1168: setKeyIndex(b, i, pos);
1169: }
1170: }
1171: setGarbage(b, 0);
1172: }
1173:
1174: /**
1175: * When an operation results in a change in the smallest key in a block,
1176: * it is necessary to inform the parent block of the change, since the
1177: * parent block key for this block is required to be the key of the
1178: * smallest item in this block.
1179: *
1180: * @param b the block containing the new lowest key
1181: * @param prevLow the key which was previously the lowest key.
1182: *
1183: * @return true if block <code>b</code> is now empty, and has been
1184: * freed and unlinked from the tree. Don't touch this block
1185: * any more!
1186: */
1187: final boolean newLow(Block b, byte[] prevLow) throws IOException {
1188: boolean ret = false;
1189: long parentBlock = getParent(b);
1190: if (parentBlock != 0) {
1191: Bnode parent = tree.getNode(parentBlock);
1192: Block pb = parent.getBlock();
1193: try {
1194: int pos = bsearch(pb, prevLow, prevLow.length);
1195: if (pos < 0) {
1196: //#ifdef DEBUG
1197: System.out.print("b = ");
1198: display(b, System.out, false);
1199: System.out.print("pb = ");
1200: display(pb, System.out, false);
1201: Debug.println(0, "prevLow = " + keybytes(prevLow));
1202: //#endif
1203: throw new RuntimeException(
1204: "deleteKeyAtPos: deleting "
1205: + " previous low key, not found!");
1206: }
1207: if (getCount(b) == 0) {
1208: if (deleteKeyAtPos(pb, pos, false)) {
1209: //#ifdef DEBUG
1210: //Debug.println("Just deleted pb!");
1211: //#endif
1212: }
1213: file.freePage(b.getPageNum());
1214: ret = true;
1215: } else {
1216: byte[] k = keyAtPos(b, 0);
1217: byte[] d = Util.bytes(b.getPageNum());
1218: setKey(pb, pos, k, k.length, d, 0, d.length, true);
1219: //#ifdef DEBUG
1220: if (paranoid)
1221: checkBlock(b);
1222: //#endif
1223: }
1224: } finally {
1225: pb.decrRefCount();
1226: }
1227: }
1228: return ret;
1229: }
1230:
1231: /**
1232: * Helper function to move key indices around when adding or deleting
1233: * keys.
1234: */
1235: final static void moveKeys(Block b, int from, int to, int length) {
1236: if (length > 0) {
1237: byte[] buf = (byte[]) b.getData();
1238: length *= REF_SIZE;
1239: int f = index(from);
1240: int t = index(to);
1241: if (f < t) {
1242: b.setDirty(true);
1243: for (int i = length - 1; i >= 0; i--) {
1244: buf[t + i] = buf[f + i];
1245: }
1246: } else if (f > t) {
1247: b.setDirty(true);
1248: for (int i = 0; i < length; i++) {
1249: buf[t + i] = buf[f + i];
1250: }
1251: }
1252: }
1253: }
1254:
1255: /**
1256: * Determine if there is room in the block for a new key/data pair.
1257: * @param b the block to operate on
1258: * @param index the index of the key that is being replaced,
1259: * if <code>replace</code> is <b>true</b>.
1260: * @param klen the search key length
1261: * @param dlen the length of the data associated with the key
1262: * @param replace <b>true</b> if an existing key/data pair is to
1263: * be replaced by the new key, <b>false</b> otherwise.
1264: *
1265: * @return negative number if there is no room for the new data.<p>
1266: * zero if there is room for the new data.<p>
1267: * positive number if there would be room after a garbage
1268: * collection. Included in this calculation is the deletion
1269: * of the key being replaced, if <code>replace</code> is true.<p>
1270: */
1271: final int checkSpace(Block b, int index, int klen, int dlen,
1272: boolean replace) {
1273: int need = REF_SIZE + totalLength(klen) + totalLength(dlen);
1274: int total = capacity(b) + getGarbage(b);
1275: if (replace)
1276: total += REF_SIZE + existingKeyLength(b, index);
1277: int ret = 0; // fits
1278: if (need > total) {
1279: ret = -1; // doesn't fit
1280: } else if (need > capacity(b)) {
1281: ret = 1; // will fit if gc
1282: }
1283: return ret;
1284: }
1285:
1286: //#ifdef DEBUG
1287: final int debugcheckSpace(Block b, int index, int klen, int dlen,
1288: boolean replace) {
1289: int need = REF_SIZE + totalLength(klen) + totalLength(dlen);
1290: Debug.println(0, "keylen = " + totalLength(klen));
1291: Debug.println(0, "datalen = " + totalLength(dlen));
1292: Debug.println(0, "need = " + need);
1293: int total = capacity(b) + getGarbage(b);
1294: Debug.println(0, "capacity = " + capacity(b));
1295: Debug.println(0, "garbage = " + getGarbage(b));
1296: Debug.println(0, "total = " + total);
1297: if (replace)
1298: total += REF_SIZE + existingKeyLength(b, index);
1299: int ret = 0; // fits
1300: if (need > total) {
1301: ret = -1; // doesn't fit
1302: } else if (need > capacity(b)) {
1303: ret = 1; // will fit if gc
1304: }
1305: return ret;
1306: }
1307:
1308: //#endif
1309:
1310: /**
1311: * This function is scary. It accounts for the fact that we're about
1312: * to delete a key, by including the size of the key/data in the
1313: * node's <code>garbage</code> field, but it doesn't actually delete
1314: * the key. Be careful.
1315: */
1316: final void forgetKeyAtPos(Block b, int index) {
1317: setGarbage(b, getGarbage(b) + existingKeyLength(b, index));
1318: }
1319:
1320: /**
1321: * Delete the specified key.
1322: *
1323: * @return true if the block is now empty, has been freed, and we
1324: * should avoid touching it...
1325: */
1326: final boolean deleteKeyAtPos(Block b, int index, boolean skipNewLow)
1327: throws IOException {
1328: boolean ret = false;
1329: int cnt = getCount(b);
1330: byte[] prevLow = index == 0 ? keyAtPos(b, 0) : null;
1331: forgetKeyAtPos(b, index);
1332: if (index < cnt - 1) {
1333: moveKeys(b, index + 1, index, cnt - index - 1);
1334: }
1335: setCount(b, cnt - 1);
1336: if (!skipNewLow && getCount(b) == 0 && getParent(b) == 0) {
1337: setLeaf(b, true);
1338: } else if (!skipNewLow && index == 0) {
1339: ret = newLow(b, prevLow);
1340: }
1341: return ret;
1342: }
1343:
1344: /**
1345: * Given a block and a key position, insert a new key/data pair
1346: * immediately at the specified position, returning true if the
1347: * key/data fit in the block. If the incoming data won't fit,
1348: * don't modify the block and return false.
1349: * @param b the block to be modified.
1350: * @param index the position in the key array
1351: * @param key the key
1352: * @param data the data
1353: * @return true if the insert was performed successfully, false
1354: * if not because of, e.g., "wont fit".
1355: */
1356: final boolean setKeyAtPos(Block b, int index, byte[] key, int klen,
1357: byte[] data, int doff, int dlen, boolean replace)
1358: throws IOException {
1359: int ret = checkSpace(b, index, klen, dlen, replace);
1360: if (ret < 0)
1361: return false;
1362: if (ret > 0) {
1363: // ---- will fit if we gc first.
1364: if (replace) {
1365: deleteKeyAtPos(b, index, true);
1366: replace = false;
1367: }
1368: gc(b);
1369: }
1370: if (replace)
1371: forgetKeyAtPos(b, index);
1372:
1373: // ---- paranoia
1374: //#ifdef DEBUG
1375: if (paranoid && checkSpace(b, index, klen, dlen, replace) != 0) {
1376: display(b, System.err, false);
1377: throw new RuntimeException(
1378: "setKeyAtPos: no room, even after gc");
1379: }
1380: //#endif
1381:
1382: // ---- insert the key/data pair at the bottom of the data area
1383: int pos = insertKeyData(b, key, klen, data, doff, dlen);
1384: if (!replace) {
1385: // ---- move the larger keys over one, then insert this one
1386: int cnt = getCount(b); // how many existing keys?
1387: // ---- move 'cnt' keys to the right
1388: if (cnt > 0) {
1389: moveKeys(b, index, index + 1, cnt - index);
1390: }
1391: setCount(b, cnt + 1); // increment the count
1392: }
1393: setKeyIndex(b, index, pos); // insert this one
1394: return true;
1395: }
1396:
1397: /**
1398: * Write a length code for the specified length, working backwards in
1399: * the data area, and returning the new bottom of the data area.
1400: */
1401: final static int writeLenLen(Block b, int bos, int len) {
1402: if (len <= 0x7f) {
1403: b.writeByte(--bos, (byte) len);
1404: } else {
1405: int lenlen = 0;
1406: while (len > 0) {
1407: b.writeByte(--bos, (byte) (len & 0xff));
1408: len >>= 8;
1409: lenlen++;
1410: }
1411: b.writeByte(--bos, (byte) (0x80 | lenlen));
1412: }
1413: return bos;
1414: }
1415:
1416: /**
1417: * Return the number of available bytes in the buffer, not including
1418: * space that could be made available by performing a garbage collection.
1419: */
1420: final static int capacity(Block b) {
1421: return getBos(b) - (fIndices + (getCount(b) * REF_SIZE));
1422: }
1423:
1424: final Block getBlock(long blockNum) throws IOException {
1425: Block b = file.getBlock(blockNum);
1426: return b;
1427: }
1428:
1429: final Block getBlock() throws IOException {
1430: return getBlock(this .blockRef);
1431: }
1432:
1433: /**
1434: * Return the byte offset of the specified key/data pair.
1435: *
1436: * @param b the Bnode containing the key
1437: * @param index the index of the specified key/data pair.
1438: */
1439: final static int getKeyIndex(Block b, int index) {
1440: return b.readShort(index(index));
1441: }
1442:
1443: /**
1444: * Set the byte offset for the specified key/data pair.
1445: *
1446: * @param b the Bnode containing the key
1447: * @param index the index of the specified key/data pair.
1448: * @param val the byte offset of the specified key/data pair.
1449: */
1450: final static void setKeyIndex(Block b, int index, int val) {
1451: b.writeShort(index(index), (short) val);
1452: }
1453:
1454: final static int index(int pos) {
1455: return pos * REF_SIZE + fIndices;
1456: }
1457:
1458: /**
1459: * Return the value of the <b>count</b> field.
1460: */
1461: final static int getBos(Block b) {
1462: return b.readInt(fDataBOS);
1463: }
1464:
1465: /**
1466: * Set the value of the <b>bos</b> field.
1467: */
1468: public final static void setBos(Block b, int bos) {
1469: b.writeInt(fDataBOS, bos);
1470: }
1471:
1472: /**
1473: * Return the value of the <b>bos</b> field.
1474: */
1475: public final static int getCount(Block b) {
1476: return b.readInt(fCount);
1477: }
1478:
1479: /**
1480: * Set the value of the <b>count</b> field.
1481: */
1482: public final static void setCount(Block b, int count) {
1483: b.writeInt(fCount, count);
1484: }
1485:
1486: /**
1487: * Return the value of the <b>flags</b> field.
1488: */
1489: public final static int getFlags(Block b) {
1490: return b.readInt(fFlags);
1491: }
1492:
1493: /**
1494: * Set the value of the <b>flags</b> field.
1495: */
1496: public final static void setFlags(Block b, int flags) {
1497: b.writeInt(fFlags, flags);
1498: }
1499:
1500: /**
1501: * Return the boolean value of a specified flag.
1502: */
1503: public final static boolean getFlag(Block b, int mask) {
1504: return (getFlags(b) & mask) != 0;
1505: }
1506:
1507: /**
1508: * Set a specified boolean flag.
1509: */
1510: public final static void setFlag(Block b, int mask, boolean val) {
1511: setFlags(b, val ? getFlags(b) | mask : getFlags(b) & ~mask);
1512: }
1513:
1514: /**
1515: * Return the value of the <b>IS_LEAF</b> flag.
1516: */
1517: public final static boolean isLeaf(Block b) {
1518: return getFlag(b, IS_LEAF);
1519: }
1520:
1521: /**
1522: * Set the value of the <b>IS_LEAF</b> flag.
1523: */
1524: public final static void setLeaf(Block b, boolean v) {
1525: setFlag(b, IS_LEAF, v);
1526: }
1527:
1528: /**
1529: * Return the value of the <b>garbage</b> field.
1530: */
1531: public final static int getGarbage(Block b) {
1532: return b.readInt(fGarbage);
1533: }
1534:
1535: /**
1536: * Set the value of the <b>garbage</b> field.
1537: */
1538: public final static void setGarbage(Block b, int g) {
1539: b.writeInt(fGarbage, g);
1540: }
1541:
1542: /**
1543: * Return the value of the <b>parent</b> field.
1544: */
1545: public final static long getParent(Block b) {
1546: return b.readLong(fParent);
1547: }
1548:
1549: /**
1550: * Set the value of the <b>parent</b> field.
1551: */
1552: public final static void setParent(Block b, long g) {
1553: b.writeLong(fParent, g);
1554: }
1555:
1556: //#ifdef DEBUG
1557: /**
1558: * For debugging purposes, write a human readable version of this
1559: * <code>Bnode</code> to the specified stream.
1560: */
1561: final void display(PrintStream os, boolean recursive)
1562: throws IOException {
1563: display(os, os, recursive);
1564: }
1565:
1566: final void display(PrintStream os, PrintStream er, boolean recursive)
1567: throws IOException {
1568: Block b = getBlock();
1569: try {
1570: display(b, os, er, recursive);
1571: } finally {
1572: b.decrRefCount();
1573: }
1574: }
1575:
1576: final void display(Block b, PrintStream os, boolean recursive)
1577: throws IOException {
1578: display(b, os, os, recursive);
1579: }
1580:
1581: /**
1582: * Since this is used for displaying the key, we attempt to return the
1583: * string itself, as long as it is composed only of printable characters.
1584: * If it contains any "non-printable" characters, it is instead formatted
1585: * in hex/ascii dump form.
1586: *
1587: * @param b the bytes form of the key
1588: * @return a displayable representation of the key.
1589: */
1590: final static String keybytes(byte[] key) {
1591: boolean printable = true;
1592: for (int i = 0; printable && i < key.length; i++) {
1593: if (key[i] < 0x20 || key[i] >= 0x7f)
1594: printable = false;
1595: }
1596: if (printable) {
1597: return new String(key);
1598: } else {
1599: return Util.hexBytes(key)
1600: + " "
1601: + com.quadcap.sql.Key.toStringHelper(key, 0,
1602: key.length);
1603:
1604: }
1605: }
1606:
1607: final static String keybytes(byte[] key, int off, int len) {
1608: return Util.hexBytes(key, off, len) + " "
1609: + com.quadcap.sql.Key.toStringHelper(key, off, len);
1610: }
1611:
1612: /**
1613: * Represent strings as having a length other than 4, while representing
1614: * integers as only of length 4 bytes.
1615: *
1616: * @param b the string of bytes to convert
1617: * @return A string containing either a 4-byte integer conversion or a
1618: * string 'keybytes' filter.
1619: */
1620: public final static String databytes(byte[] b) {
1621: String s = Util.hexBytes(b);
1622: if (b.length == 8) {
1623: s += " (" + SubPageManager.toString(ByteUtil.getLong(b, 0))
1624: + ")";
1625: }
1626: return s;
1627: }
1628:
1629: final void display(Block b, PrintStream os, PrintStream er,
1630: boolean recursive) throws IOException {
1631: boolean leaf = isLeaf(b);
1632: int saveLevel = Debug.printLevel;
1633: Debug.printLevel = 0;
1634: int count = getCount(b);
1635: os.println("Block " + b.getPageNum() + "{" + b.getRefCount()
1636: + "}" + ", parent = " + getParent(b) + ", capacity = "
1637: + capacity(b) + ", count = " + count + ", bos = "
1638: + getBos(b) + ", garbage = " + getGarbage(b));
1639:
1640: long[] children = new long[count];
1641: for (int i = 0; i < count; i++) {
1642: int index = getKeyIndex(b, i);
1643: byte[] key = keyAtPos(b, i);
1644: byte[] data = dataAtPos(b, i);
1645: if (leaf) {
1646: os.println("[" + i + " @ " + index + "]: "
1647: + tree.compare.toString(key, 0, key.length)
1648: + " = " + Bnode.databytes(data));
1649: } else {
1650: children[i] = ByteUtil.getLong(data, 0);
1651: os.println("[" + i + " @ " + index + "]: "
1652: + tree.compare.toString(key, 0, key.length)
1653: + SubPageManager.toString(children[i]));
1654: }
1655: }
1656: if (!leaf && recursive) {
1657: for (int i = 0; i < children.length; i++) {
1658: Block c = getBlock(children[i]);
1659: try {
1660: long p = getParent(c);
1661: if (0 != tree.compare.compare(keyAtPos(b, i),
1662: keyAtPos(c, 0))) {
1663: Debug.println(0, "ERROR: parent {"
1664: + b.getPageNum()
1665: + "} doesn't point to smallest key in "
1666: + " child {" + c.getPageNum() + "}");
1667: }
1668: if (p != b.getPageNum()) {
1669: Debug.println(0,
1670: "ERROR: BROKEN PARENT LINK: Block "
1671: + children[i]
1672: + " has parent link of " + p
1673: + ", but is child of "
1674: + b.getPageNum());
1675: }
1676: display(c, os, er, recursive);
1677: } finally {
1678: c.decrRefCount();
1679: }
1680: }
1681: }
1682: Debug.printLevel = saveLevel;
1683: }
1684: //#endif
1685: }
|