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.BufferedReader;
0042: import java.io.InputStreamReader;
0043: import java.io.IOException;
0044:
0045: import java.util.Properties;
0046:
0047: import com.quadcap.sql.file.Block;
0048: import com.quadcap.sql.file.BlockFile;
0049: import com.quadcap.sql.file.ByteUtil;
0050: import com.quadcap.sql.file.SubPageManager;
0051:
0052: import com.quadcap.sql.lock.PooledObject;
0053: import com.quadcap.sql.lock.ObjectPool;
0054:
0055: import com.quadcap.util.Debug;
0056: import com.quadcap.util.Util;
0057:
0058: /**
0059: * A cursor for a Quadcap Btree.
0060: *
0061: * @author Stan Bailes
0062: */
0063: public class BtreeCursor extends PooledObject implements BCursor {
0064: Object fileLock;
0065:
0066: Btree tree;
0067: Bnode root = null;
0068: Comparator compare = null;
0069:
0070: Block[] blocks = new Block[16];
0071: int[] pointers = new int[16];
0072:
0073: byte[] curKey = new byte[4096];
0074: byte[] curVal = new byte[4096];
0075: int[] lengths = new int[2];
0076:
0077: int depth = -1;
0078: long size = -1;
0079:
0080: /**
0081: * <pre>
0082: * For the position variable:
0083: * -2 unknown
0084: * -1 after last
0085: * 0 before first
0086: * >0 on key
0087: * </pre>
0088: */
0089: static final long posUNKNOWN = -2;
0090: static final long posAFTER_LAST = -1;
0091: static final long posBEFORE_FIRST = 0;
0092:
0093: long position = posUNKNOWN;
0094:
0095: /**
0096: * Constructor for cursor on a given Btree.
0097: */
0098: private BtreeCursor() {
0099: }
0100:
0101: static final boolean noPool = false;
0102: static ObjectPool pool = new ObjectPool(new BtreeCursor());
0103:
0104: static BtreeCursor get(Btree tree, boolean skipSetup)
0105: throws IOException {
0106: BtreeCursor c = null;
0107: if (noPool) {
0108: c = new BtreeCursor();
0109: } else {
0110: synchronized (tree.lock) {
0111: c = (BtreeCursor) pool.get();
0112: }
0113: }
0114: if (c != null) {
0115: c.init(tree, skipSetup);
0116: }
0117: return c;
0118: }
0119:
0120: public void release() {
0121: unsetup();
0122: synchronized (fileLock) {
0123: Btree theTree = tree;
0124: tree = null;
0125: fileLock = null;
0126: theTree.releaseCursor(this );
0127: if (!noPool) {
0128: pool.release(this );
0129: }
0130: }
0131: }
0132:
0133: /**
0134: * PooledObject factory
0135: */
0136: public PooledObject create() {
0137: return new BtreeCursor();
0138: }
0139:
0140: /**
0141: * Init for use/reuse
0142: */
0143: public void init(Btree tree, boolean skipSetup) throws IOException {
0144: this .tree = tree;
0145: this .fileLock = tree.lock;
0146: if (!skipSetup) {
0147: beforeFirst();
0148: }
0149: }
0150:
0151: /**
0152: * Called to re-establish the synchronization of this cursor in
0153: * the case where the underlying index has been modified.
0154: */
0155: protected void setup(boolean restoreKey) throws IOException {
0156: if (depth < 0) {
0157: synchronized (fileLock) {
0158: this .root = tree.getRoot();
0159: this .compare = tree.compare;
0160: if (restoreKey) {
0161: if (lengths[0] > 0) {
0162: seek(curKey, lengths[0]);
0163: } else {
0164: beforeFirst();
0165: }
0166: }
0167: }
0168: }
0169: }
0170:
0171: /**
0172: * Called (in theory) by the owning Btree when the index is modified.
0173: */
0174: public void unsetup() {
0175: for (int i = 0; i < blocks.length; i++) {
0176: setBlock(i, null);
0177: }
0178: this .root = null;
0179: this .depth = -1;
0180: this .size = -1;
0181: if (position > 0)
0182: position = posUNKNOWN;
0183: }
0184:
0185: /**
0186: * Seek: Position the cursor on or before the specified key value.
0187: * Return true if the key matches exactly.
0188: */
0189: public final boolean seek(byte[] key) throws IOException {
0190: return seek(key, key.length);
0191: }
0192:
0193: /**
0194: * Seek, but the key can be a subsequence of the given byte array.
0195: */
0196: public boolean seek(byte[] key, int len) throws IOException {
0197: synchronized (fileLock) {
0198: position = posUNKNOWN;
0199: setup(false);
0200: setBlock(0, root.getBlock());
0201: boolean ret = seek1(0, key, len);
0202: if (ret) {
0203: holdKey(0);
0204: }
0205: //#ifdef DEBUG
0206: if (Trace.bit(6)) {
0207: Debug.println(toString() + ".seek("
0208: + Util.hexBytes(key, 0, len) + ") = " + ret);
0209: }
0210: //#endif
0211: return ret;
0212: }
0213: }
0214:
0215: //#ifdef DEBUG
0216: final String id() {
0217: return tree.getFile().getName().substring(0, 1) + " "
0218: + SubPageManager.toString(tree.getRootBlock());
0219: }
0220:
0221: final String dr() {
0222: return !Trace.bit(12) ? ", val = "
0223: + (lengths[1] > 0 ? Util.hexBytes(getVal()) : "null")
0224: : "";
0225: }
0226:
0227: //#endif
0228:
0229: /**
0230: * (Private) seek recursion kernel
0231: */
0232: boolean seek1(int level, byte[] key, int len) throws IOException {
0233: Block b = blocks[level];
0234: int bs;
0235: bs = Bnode.bsearch(b, compare, key, len, 0,
0236: Bnode.getCount(b) - 1);
0237: int index = bs < 0 ? (-1 - bs) : bs;
0238: if (!Bnode.isLeaf(b)) {
0239: if (bs < 0) {
0240: index = index - 1;
0241: if (index < 0)
0242: index = 0;
0243: }
0244: pointers[level] = index;
0245: Block c = root.getBlock(Bnode.blockRef(b, index));
0246: setBlock(++level, c);
0247: return seek1(level, key, len);
0248: } else {
0249: pointers[level] = index;
0250: depth = level + 1;
0251: return bs >= 0;
0252: }
0253: }
0254:
0255: /**
0256: * Manage updates to the 'blocks' array through this function to
0257: * assuage refcount madness.
0258: */
0259: final void setBlock(int i, Block b) {
0260: if (blocks[i] != null)
0261: blocks[i].decrRefCount();
0262: blocks[i] = b;
0263: }
0264:
0265: /**
0266: * Move the cursor before the first key.
0267: */
0268: public void beforeFirst() throws IOException {
0269: synchronized (fileLock) {
0270: this .root = tree.getRoot();
0271: this .compare = tree.compare;
0272: lengths[0] = lengths[1] = 0;
0273: Block b = root.getBlock();
0274: for (int level = 0; b != null; level++) {
0275: setBlock(level, b);
0276: pointers[level] = 0;
0277: if (!Bnode.isLeaf(b)) {
0278: b = root.getBlock(Bnode.blockRef(b, 0));
0279: } else {
0280: depth = level + 1;
0281: b = null;
0282: }
0283: }
0284: position = posBEFORE_FIRST;
0285:
0286: //#ifdef DEBUG
0287: if (Trace.bit(1)) {
0288: Debug.println(toString() + ".beforeFirst()");
0289: }
0290: //#endif
0291: }
0292: }
0293:
0294: /**
0295: * Move the cursor after the last key.
0296: */
0297: public void afterLast() throws IOException {
0298: synchronized (fileLock) {
0299: setup(false);
0300: Block b = root.getBlock();
0301: for (int level = 0; b != null; level++) {
0302: setBlock(level, b);
0303: int count = Bnode.getCount(b);
0304: pointers[level] = count;
0305: if (!Bnode.isLeaf(b)) {
0306: b = root.getBlock(Bnode.blockRef(b,
0307: pointers[level] - 1));
0308: } else {
0309: b = null;
0310: }
0311: }
0312: position = posAFTER_LAST;
0313: //#ifdef DEBUG
0314: if (Trace.bit(1)) {
0315: Debug.println(toString() + ".afterLast()");
0316: }
0317: //#endif
0318: }
0319: }
0320:
0321: /**
0322: * Move the cursor to the specified absolute position
0323: */
0324: public boolean absolute(int x) throws IOException {
0325: synchronized (fileLock) {
0326: if (x > 0) {
0327: // from first
0328: beforeFirst();
0329: int cur = 1;
0330: int cnt = Bnode.getCount(blocks[depth - 1]);
0331: while (cur + cnt < x) {
0332: cur += cnt;
0333: if (!getNextBlock())
0334: return false;
0335: cnt = Bnode.getCount(blocks[depth - 1]);
0336: }
0337: int p = x - cur;
0338: if (p < 0 || p >= cnt)
0339: return false;
0340: pointers[depth - 1] = p;
0341: holdKey(0);
0342: pointers[depth - 1]++;
0343: position = x;
0344: //#ifdef DEBUG
0345: if (Trace.bit(1)) {
0346: Debug.println(toString() + ".absolute(" + x
0347: + ") = true");
0348: }
0349: //#endif
0350: return true;
0351: } else if (x < 0) {
0352: int absx = 0 - x;
0353: // from last
0354: afterLast();
0355: int cnt = Bnode.getCount(blocks[depth - 1]);
0356: while (cnt < absx) {
0357: absx -= cnt;
0358: if (!getPrevBlock())
0359: return false;
0360: cnt = Bnode.getCount(blocks[depth - 1]);
0361: }
0362: pointers[depth - 1] -= absx;
0363: holdKey(0);
0364: //#ifdef DEBUG
0365: if (Trace.bit(1)) {
0366: Debug.println(toString() + ".absolute(" + x
0367: + ") = true");
0368: }
0369: //#endif
0370: if (size > 0)
0371: position = size + x;
0372: return true;
0373: } else {
0374: throw new IOException("absolute 0");
0375: }
0376: }
0377: }
0378:
0379: /**
0380: * Move the cursor to the next row and return <b>true</b> if the
0381: * cursor is positioned on a valid row.
0382: */
0383: public boolean next() throws IOException {
0384: synchronized (fileLock) {
0385: setup(true);
0386: if (depth <= 0)
0387: return false;
0388: int p = pointers[depth - 1];
0389: int cnt = Bnode.getCount(blocks[depth - 1]);
0390: if (p >= cnt) {
0391: if (cnt == 0 || !getNextBlock()) {
0392: //#ifdef DEBUG
0393: if (Trace.bit(1)) {
0394: Debug.println(toString() + ".next() false");
0395: }
0396: //#endif
0397: return false;
0398: }
0399: p = pointers[depth - 1];
0400: cnt = Bnode.getCount(blocks[depth - 1]);
0401: if (p >= cnt) {
0402: //#ifdef DEBUG
0403: if (Trace.bit(1)) {
0404: Debug.println(toString() + ".next() false");
0405: }
0406: //#endif
0407: return false;
0408: }
0409: }
0410: holdKey(0);
0411: pointers[depth - 1]++;
0412: if (position >= 0)
0413: position++;
0414: //#ifdef DEBUG
0415: if (Trace.bit(1)) {
0416: Debug.println(toString() + ".next(): "
0417: + Util.hexBytes(getKeyBuf(), 0, getKeyLen())
0418: + " = " + dr());
0419: }
0420: //#endif
0421: return true;
0422: }
0423: }
0424:
0425: /**
0426: * Move the cursor to the next row and return <b>true</b> if the
0427: * cursor is positioned on a valid row.
0428: */
0429: public boolean prev() throws IOException {
0430: synchronized (fileLock) {
0431: setup(true);
0432: if (depth < 0)
0433: return false;
0434: int p = pointers[depth - 1] - 1;
0435: int cnt = Bnode.getCount(blocks[depth - 1]);
0436: if (p < 0 || cnt <= 0) {
0437: if (cnt <= 0 || !getPrevBlock())
0438: return false;
0439: p = pointers[depth - 1];
0440: if (p < 0 || cnt <= 0)
0441: return false;
0442: }
0443: pointers[depth - 1] = p;
0444: holdKey(0);
0445: if (position > 0) {
0446: position--;
0447: } else if (position == posAFTER_LAST) {
0448: if (size < 0) {
0449: position = posUNKNOWN;
0450: } else {
0451: position = size;
0452: }
0453: }
0454: //#ifdef DEBUG
0455: if (Trace.bit(1)) {
0456: Debug.println(toString() + ".prev() true");
0457: }
0458: //#endif
0459: return true;
0460: }
0461: }
0462:
0463: /**
0464: * Delete the current row (if the cursor is positioned on a valid
0465: * row, that is ;-)
0466: */
0467: public boolean delete() throws IOException {
0468: synchronized (fileLock) {
0469: boolean ret = false;
0470: setup(true);
0471: if (depth >= 0) {
0472: int p = pointers[depth - 1];
0473: int cnt = Bnode.getCount(blocks[depth - 1]);
0474: if (p >= 0 && p < cnt) {
0475: root.deleteKeyAtPos(blocks[depth - 1], p, false);
0476: tree.notifyUpdate(this );
0477: ret = true;
0478: }
0479: }
0480: //#ifdef DEBUG
0481: if (Trace.bit(9)) {
0482: Debug.println(toString() + ".delete() = " + ret);
0483: }
0484: //#endif
0485: return ret;
0486: }
0487: }
0488:
0489: /**
0490: * Insert a new key/data pair. We are presumably positioned just before
0491: * the spot where the new record should go, but we should check, anyway.
0492: * This will return false if the key already exists in the index.
0493: */
0494: public boolean insert(byte[] key, int klen, byte[] data, int doff,
0495: int dlen) throws IOException {
0496: synchronized (fileLock) {
0497: setup(true);
0498:
0499: int p = pointers[depth - 1];
0500: final Block b = blocks[depth - 1];
0501: final int cnt = Bnode.getCount(b);
0502:
0503: if (p < 0 || p > cnt)
0504: throw new IOException("bad tree");
0505:
0506: boolean ret = true;
0507: if (p >= 0 && p < cnt) {
0508: int r = Bnode.keyCompareAtPos(compare, key, klen, b, p);
0509: if (r != -1)
0510: ret = false;
0511: } else if (p > 0 && cnt > 0) {
0512: int r = Bnode.keyCompareAtPos(compare, key, klen, b,
0513: p - 1);
0514: if (r != 1)
0515: ret = false;
0516: }
0517: if (ret) {
0518: root.setKey(b, p, key, klen, data, doff, dlen, false);
0519: tree.notifyUpdate(this );
0520: }
0521: //#ifdef DEBUG
0522: if (Trace.bit(7)) {
0523: Debug
0524: .println(toString()
0525: + ".insert("
0526: + k(key, 0, klen)
0527: + (!Trace.bit(12) ? (", " + k(data,
0528: doff, dlen)) : "") + ") = "
0529: + ret);
0530: }
0531: //#endif
0532: return ret;
0533: }
0534: }
0535:
0536: public boolean insert(byte[] key, byte[] data) throws IOException {
0537: return insert(key, key.length, data, 0, data.length);
0538: }
0539:
0540: /**
0541: * Replace the data portion of the current item with the specified data
0542: */
0543: public boolean replace(byte[] data, int doff, int dlen)
0544: throws IOException {
0545: synchronized (fileLock) {
0546: setup(true);
0547:
0548: int p = pointers[depth - 1];
0549: final Block b = blocks[depth - 1];
0550: final int cnt = Bnode.getCount(b);
0551:
0552: if (p < 0 || p > cnt) {
0553: throw new IOException("bad tree");
0554: }
0555:
0556: root.setKey(b, p, curKey, lengths[0], data, doff, dlen,
0557: true);
0558: tree.notifyUpdate(this );
0559: //#ifdef DEBUG
0560: if (Trace.bit(8)) {
0561: Debug.println(toString() + ".replace("
0562: + k(curKey, 0, lengths[0]) + ") = true");
0563: }
0564: //#endif
0565: return true;
0566: }
0567: }
0568:
0569: public boolean replace(byte[] data) throws IOException {
0570: return replace(data, 0, data.length);
0571: }
0572:
0573: /**
0574: * Return the total number of entries in this index
0575: */
0576: public long size() throws IOException {
0577: synchronized (fileLock) {
0578: setup(true);
0579: if (size < 0) {
0580: size = subtreeSize(root, root.getBlock());
0581: }
0582: return size;
0583: }
0584: }
0585:
0586: /**
0587: * Return the current position in the index
0588: */
0589: public long position() throws IOException {
0590: synchronized (fileLock) {
0591: setup(true);
0592: if (position < 0) {
0593: long total = 0;
0594: boolean r = false;
0595: for (int d = 0; d < depth - 1; d++) {
0596: Block b = blocks[d];
0597: int p = pointers[d];
0598: int c = Bnode.getCount(b);
0599: if (d == 0)
0600: r = (c / 2) <= p;
0601: if (r)
0602: p++;
0603: else {
0604: c = p;
0605: p = 0;
0606: }
0607: if (Bnode.isLeaf(b)) {
0608: total += (c - p);
0609: } else {
0610: for (int i = p; i < c; i++) {
0611: Block s = root.getBlock(Bnode
0612: .blockRef(b, i));
0613: try {
0614: total += subtreeSize(root, s);
0615: } finally {
0616: s.decrRefCount();
0617: }
0618: }
0619: }
0620: }
0621: position = r ? size() - total : total + 1;
0622: }
0623: return position;
0624: }
0625: }
0626:
0627: /**
0628: * Close the index
0629: */
0630: public void close() {
0631: unsetup();
0632: }
0633:
0634: public int getKey(byte[] buf) {
0635: System.arraycopy(curKey, 0, buf, 0, lengths[0]);
0636: return lengths[0];
0637: }
0638:
0639: public byte[] getKeyBuf() {
0640: return curKey;
0641: }
0642:
0643: public void setKeyBuf(byte[] buf) {
0644: curKey = buf;
0645: }
0646:
0647: public int getKeyLen() {
0648: return lengths[0];
0649: }
0650:
0651: public byte[] getKey() {
0652: byte[] ret = new byte[lengths[0]];
0653: System.arraycopy(curKey, 0, ret, 0, ret.length);
0654: return ret;
0655: }
0656:
0657: public int getVal(byte[] buf) {
0658: System.arraycopy(curVal, 0, buf, 0, lengths[1]);
0659: return lengths[1];
0660: }
0661:
0662: public byte[] getValBuf() {
0663: return curVal;
0664: }
0665:
0666: public void setValBuf(byte[] buf) {
0667: curVal = buf;
0668: }
0669:
0670: public int getValLen() {
0671: return lengths[1];
0672: }
0673:
0674: public byte[] getVal() {
0675: byte[] ret = new byte[lengths[1]];
0676: System.arraycopy(curVal, 0, ret, 0, ret.length);
0677: return ret;
0678: }
0679:
0680: public long getValAsLong() {
0681: return ByteUtil.getLong(curVal, 0);
0682: }
0683:
0684: //--------------------------------- private stuff
0685:
0686: final boolean getNextBlock() throws IOException {
0687: int d = depth - 2;
0688: while (d >= 0 && pointers[d] + 1 >= Bnode.getCount(blocks[d])) {
0689: d--;
0690: }
0691:
0692: if (d < 0)
0693: return false;
0694: Block b = root.getBlock(Bnode
0695: .blockRef(blocks[d], ++pointers[d]));
0696:
0697: setBlock(d + 1, b);
0698: pointers[d + 1] = 0;
0699:
0700: for (int i = d + 2; i < depth; i++) {
0701: pointers[i] = 0;
0702: Block c = root.getBlock(Bnode.blockRef(blocks[i - 1],
0703: pointers[i - 1]));
0704: setBlock(i, c);
0705: }
0706: return true;
0707: }
0708:
0709: final boolean getPrevBlock() throws IOException {
0710: int d = depth - 2;
0711: while (d >= 0 && pointers[d] <= 0) {
0712: d--;
0713: }
0714:
0715: if (d < depth - 1) {
0716: if (d < 0) {
0717: return false;
0718: }
0719: Block b = root.getBlock(Bnode.blockRef(blocks[d],
0720: --pointers[d]));
0721: setBlock(d + 1, b);
0722: pointers[d + 1] = 0;
0723:
0724: for (int i = d + 2; i < depth; i++) {
0725: Block c = root.getBlock(Bnode.blockRef(blocks[i - 1],
0726: pointers[i - 1]));
0727: setBlock(i, c);
0728: pointers[i] = Bnode.getCount(c) - 1;
0729: }
0730: }
0731: return true;
0732: }
0733:
0734: final void holdKey(int off) {
0735: int p = pointers[depth - 1] - off;
0736: Block b = blocks[depth - 1];
0737: if (p >= 0 && p < Bnode.getCount(b)) {
0738: if (!Bnode.getKeyAndData(b, p, curKey, curVal, lengths)) {
0739: throw new RuntimeException(
0740: "holdKey: getKeyAndData failed");
0741: }
0742: } else {
0743: //msg("holdKey: p = " + p + ", pointers[depth(" + depth + ")-1]=" +
0744: // pointers[depth-1] + ", off = " + off + ", count = " +
0745: // Bnode.getCount(b));
0746: throw new RuntimeException("Hold what, mate?");
0747: }
0748: //Debug.println("holdKey: [" + k(curKey, 0, lengths[0]) +
0749: //" / " + k(curVal, 0, lengths[1]) + "]");
0750: }
0751:
0752: static long subtreeSize(Bnode root, Block b) throws IOException {
0753: int count = Bnode.getCount(b);
0754: if (Bnode.isLeaf(b))
0755: return count;
0756: else {
0757: long total = 0;
0758: for (int i = 0; i < count; i++) {
0759: Block c = root.getBlock(Bnode.blockRef(b, i));
0760: try {
0761: total += subtreeSize(root, c);
0762: } finally {
0763: c.decrRefCount();
0764: }
0765: }
0766: return total;
0767: }
0768: }
0769:
0770: //#ifdef DEBUG
0771:
0772: public String toString() {
0773: return "BtreeCursor[" + tree + "]";
0774: }
0775:
0776: String k(byte[] b, int off, int len) {
0777: return tree.compare.toString(b, off, len);
0778: }
0779:
0780: String t() {
0781: StringBuffer sb = new StringBuffer();
0782: for (int i = 0; i < depth; i++) {
0783: if (i > 0)
0784: sb.append(' ');
0785: sb.append(String.valueOf(pointers[i]));
0786: sb.append('/');
0787: sb.append(String.valueOf(Bnode.getCount(blocks[i])));
0788: }
0789: return sb.toString();
0790: }
0791:
0792: static int lastCount = -1;
0793: static StringBuffer lastBuf = new StringBuffer();
0794:
0795: private static final int countNext(BCursor c) throws IOException {
0796: int cnt = 0;
0797: while (c.next())
0798: cnt++;
0799: lastCount = cnt;
0800: return cnt;
0801: }
0802:
0803: private static final int countPrev(BCursor c) throws IOException {
0804: int cnt = 0;
0805: StringBuffer sb = lastBuf;
0806: sb.setLength(0);
0807: sb.append("{");
0808: byte[] buf = new byte[111];
0809: while (c.prev()) {
0810: cnt++;
0811: int len = c.getKey(buf);
0812: if (cnt > 0)
0813: sb.append(',');
0814: sb.append(new String(buf, 0, len));
0815: }
0816: sb.append("}");
0817: lastCount = cnt;
0818: return cnt;
0819: }
0820:
0821: final static String r(boolean b) {
0822: return b ? "{true}" : "{false}";
0823: }
0824:
0825: static void itest(BCursor bc) throws IOException {
0826: InputStreamReader ir = new InputStreamReader(System.in);
0827: BufferedReader r = new BufferedReader(ir);
0828: String ret = "";
0829: while (true) {
0830: System.out.print("BC" + ret + " (" + ((BtreeCursor) bc).t()
0831: + "): ");
0832: System.out.flush();
0833: String line = r.readLine();
0834: if (line == null)
0835: break;
0836: try {
0837: ret = doLine(bc, line);
0838: if (ret == null)
0839: break;
0840: } catch (Throwable t) {
0841: t.printStackTrace(System.out);
0842: System.out.println("-------------------------");
0843: }
0844: }
0845: }
0846:
0847: static String doLine(BCursor bc, String line) throws Exception {
0848: String ks = line.toLowerCase().substring(1).trim();
0849: byte[] k = ks.getBytes();
0850: byte[] d = ks.toUpperCase().getBytes();
0851: String ret = "";
0852: if (line.startsWith("g")) {
0853: ret = r(bc.seek(k));
0854: } else if (line.equals("<")) {
0855: bc.beforeFirst();
0856: } else if (line.equals(">")) {
0857: bc.afterLast();
0858: } else if (line.equals("n")) {
0859: ret = r(bc.next());
0860: } else if (line.equals("p")) {
0861: ret = r(bc.prev());
0862: } else if (line.equals("d")) {
0863: ret = r(bc.delete());
0864: } else if (line.startsWith("i")) {
0865: ret = r(bc.insert(k, k.length, d, 0, d.length));
0866: } else if (line.startsWith("r")) {
0867: ret = r(bc.replace(d, 0, d.length));
0868: } else if (line.equals("c")) {
0869: bc.close();
0870: } else if (line.equals("s")) {
0871: show("position = " + bc.position() + " of " + bc.size()
0872: + " records");
0873: } else if (line.equals("k")) {
0874: show("current key = "
0875: + new String(bc.getKeyBuf(), 0, bc.getKeyLen()));
0876: show("current val = "
0877: + new String(bc.getValBuf(), 0, bc.getValLen()));
0878: show("current val as long: " + bc.getValAsLong());
0879:
0880: } else if (line.equals("p")) {
0881: show("position = " + bc.position() + " of " + bc.size()
0882: + " records");
0883: } else if (line.equals("q")) {
0884: return null;
0885: } else {
0886: int row = 0;
0887: boolean bad = true;
0888: try {
0889: row = Integer.parseInt(line);
0890: bad = false;
0891: } catch (Throwable t) {
0892: }
0893: if (!bad) {
0894: ret = r(bc.absolute(row));
0895: } else {
0896: show("g <key> seek(key)");
0897: show("i <key> insert(key,KEY)");
0898: show("r <key> replace(KEY)");
0899: show("< beforeFirst()");
0900: show("> afterLast()");
0901: show("n next()");
0902: show("p prev()");
0903: show("c close()");
0904: show("d delete()");
0905: show("s position / size");
0906: }
0907: }
0908: return ret;
0909: }
0910:
0911: static void show(String s) {
0912: System.out.println(s);
0913: }
0914:
0915: static final long tick() {
0916: return System.currentTimeMillis();
0917: }
0918:
0919: static final void mkey(int i, byte[] b) {
0920: int x = b.length;
0921: while (x > 0 && i > 0) {
0922: b[--x] = (byte) ('0' + (i % 10));
0923: i /= 10;
0924: }
0925: while (x > 0)
0926: b[--x] = '0';
0927: }
0928:
0929: static void ktest(BCursor c) throws IOException {
0930: long s = tick();
0931: byte[] k = new byte[8];
0932: for (int i = 0; i < k.length; i++)
0933: k[i] = '0';
0934: for (int ki = 0; ki < 100000; ki++) {
0935: int i = (ki * 2003) % 100000;
0936: mkey(i, k);
0937: if (c.seek(k))
0938: throw new IOException("*** Error, found " + i);
0939: if (!c.insert(k, k.length, k, 0, k.length)) {
0940: throw new IOException("*** Error insert: " + i);
0941: }
0942: }
0943: long elap = tick() - s;
0944: System.out.println("insert: " + elap + " ms");
0945: kshow(c);
0946: }
0947:
0948: static void kshow(BCursor c) throws IOException {
0949: long s = tick();
0950: int count = 0;
0951: int total = 0;
0952: int etotal = 0;
0953: c.beforeFirst();
0954: while (c.next()) {
0955: etotal += count;
0956: count++;
0957: total += Integer.parseInt(new String(c.getValBuf(), 0, c
0958: .getValLen()));
0959: }
0960: long elap = tick() - s;
0961: show("seek: " + elap + " ms");
0962: show("Count: " + count + ", total/etotal = " + total + "/"
0963: + etotal);
0964: }
0965:
0966: static void ktest(Btree t) throws IOException {
0967: long s = tick();
0968: byte[] k = new byte[8];
0969: for (int i = 0; i < k.length; i++)
0970: k[i] = '0';
0971: for (int ki = 0; ki < 100000; ki++) {
0972: int i = (ki * 2003) % 100000;
0973: mkey(i, k);
0974: t.set(k, k);
0975: }
0976: long elap = tick() - s;
0977: System.out.println("insert: " + elap + " ms");
0978: kshow(t.getCursor());
0979: }
0980:
0981: /**
0982: * Main for testing
0983: */
0984: public static void main(String[] args) {
0985: try {
0986: String name = "test.db";
0987: int blocksize = 4096;
0988: int cachesize = 256;
0989: BlockFile f = new BlockFile(name, "rw", new Properties(),
0990: blocksize, cachesize);
0991: long rootBlock = f.newPage();
0992: Btree t = new Btree(f, rootBlock, true);
0993: // tree.set("abc".getBytes(), "def".getBytes());
0994: // tree.set("aabc".getBytes(), "def".getBytes());
0995: // tree.set("fabc".getBytes(), "def".getBytes());
0996:
0997: BCursor c = t.getCursor();
0998: //itest(c);
0999: //jtest(c);
1000: //ktest(t);
1001: ktest(c);
1002: } catch (Throwable t) {
1003: t.printStackTrace(System.out);
1004: }
1005: }
1006:
1007: static void jtest(BCursor c) throws Exception {
1008: c.seek("abc".getBytes());
1009: c.insert("abc".getBytes(), 3, "def".getBytes(), 0, 3);
1010: c.seek("ahc".getBytes());
1011: c.insert("ahc".getBytes(), 3, "deh".getBytes(), 0, 3);
1012: c.seek("bbc".getBytes());
1013: c.insert("bbc".getBytes(), 3, "jej".getBytes(), 0, 3);
1014:
1015: int cSize = countNext(c);
1016: if (c.size() != cSize) {
1017: System.out
1018: .println("Bad size: " + cSize + " vs " + c.size());
1019: }
1020: for (int i = 1; i <= cSize; i++) {
1021: if (i == 0)
1022: c.beforeFirst();
1023: else
1024: c.absolute(i);
1025: if (c.position() != i) {
1026: System.out.println("Bad position " + i + " vs "
1027: + c.position());
1028: }
1029: if (countNext(c) != cSize - i) {
1030: System.out.println("Bad count next: " + lastCount
1031: + " vs " + (cSize - i));
1032: }
1033: if (i == 0)
1034: c.beforeFirst();
1035: else
1036: c.absolute(i);
1037: if (c.position() != i) {
1038: System.out.println("Bad position " + i + " vs "
1039: + c.position());
1040: }
1041: if (countPrev(c) != i) {
1042: System.out.println("Bad count prev: " + i + " vs "
1043: + lastCount + " " + lastBuf);
1044: }
1045: if (i == 0)
1046: c.afterLast();
1047: else
1048: c.absolute(0 - i);
1049: if (c.position() != cSize - i) {
1050: System.out.println("Bad position " + (cSize - i)
1051: + " vs " + c.position());
1052: }
1053: if (countNext(c) != i - 1) {
1054: System.out.println("Bad count next: " + lastCount
1055: + " vs " + (i - 1));
1056: }
1057: if (i == 0)
1058: c.afterLast();
1059: else
1060: c.absolute(0 - i);
1061: if (c.position() != (cSize - i)) {
1062: System.out.println("Bad position " + (cSize - i)
1063: + " vs " + c.position());
1064: }
1065: if (countPrev(c) != cSize - i + 1) {
1066: System.out.println("Bad count prev: " + (cSize - i + 1)
1067: + " vs " + lastCount + " " + lastBuf);
1068: }
1069: }
1070:
1071: System.out.println("seek(abc) = " + c.seek("abc".getBytes())
1072: + ": " + c.position() + "/" + c.size());
1073: System.out.println("c.next() = " + c.next());
1074: System.out.println("c.next() = " + c.next());
1075:
1076: System.out.println("seek(abb) = " + c.seek("abb".getBytes()));
1077: System.out.println("c.next() = " + c.next());
1078: System.out.println("c.next() = " + c.next());
1079:
1080: System.out.println("seek(abd) = " + c.seek("abd".getBytes()));
1081: System.out.println("c.next() = " + c.next());
1082: System.out.println("c.next() = " + c.next());
1083:
1084: System.out.println("seek(zzz) = " + c.seek("zzz".getBytes()));
1085: System.out.println("c.next() = " + c.next());
1086: System.out.println("c.next() = " + c.next());
1087: }
1088: //#endif
1089: }
|