0001: /**
0002: * JDBM LICENSE v1.00
0003: *
0004: * Redistribution and use of this software and associated documentation
0005: * ("Software"), with or without modification, are permitted provided
0006: * that the following conditions are met:
0007: *
0008: * 1. Redistributions of source code must retain copyright
0009: * statements and notices. Redistributions must also contain a
0010: * copy of this document.
0011: *
0012: * 2. Redistributions in binary form must reproduce the
0013: * above copyright notice, this list of conditions and the
0014: * following disclaimer in the documentation and/or other
0015: * materials provided with the distribution.
0016: *
0017: * 3. The name "JDBM" must not be used to endorse or promote
0018: * products derived from this Software without prior written
0019: * permission of Cees de Groot. For written permission,
0020: * please contact cg@cdegroot.com.
0021: *
0022: * 4. Products derived from this Software may not be called "JDBM"
0023: * nor may "JDBM" appear in their names without prior written
0024: * permission of Cees de Groot.
0025: *
0026: * 5. Due credit should be given to the JDBM Project
0027: * (http://jdbm.sourceforge.net/).
0028: *
0029: * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
0030: * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
0031: * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
0032: * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
0033: * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
0034: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
0035: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
0036: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
0037: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
0038: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0039: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
0040: * OF THE POSSIBILITY OF SUCH DAMAGE.
0041: *
0042: * Copyright 2001 (C) Alex Boisvert. All Rights Reserved.
0043: * Contributions are Copyright (C) 2001 by their associated contributors.
0044: *
0045: */package jdbm.btree;
0046:
0047: import jdbm.helper.Serializer;
0048: import jdbm.helper.Tuple;
0049: import jdbm.helper.TupleBrowser;
0050:
0051: import java.io.IOException;
0052: import java.io.ByteArrayOutputStream;
0053: import java.io.ByteArrayInputStream;
0054: import java.io.ObjectInput;
0055: import java.io.ObjectOutput;
0056: import java.io.ObjectInputStream;
0057: import java.io.ObjectOutputStream;
0058:
0059: /**
0060: * Page of a Btree.
0061: * <p>
0062: * The page contains a number of key-value pairs. Keys are ordered to allow
0063: * dichotomic search.
0064: * <p>
0065: * If the page is a leaf page, the keys and values are user-defined and
0066: * represent entries inserted by the user.
0067: * <p>
0068: * If the page is non-leaf, each key represents the greatest key in the
0069: * underlying BPages and the values are recids pointing to the children BPages.
0070: * The only exception is the rightmost BPage, which is considered to have an
0071: * "infinite" key value, meaning that any insert will be to the left of this
0072: * pseudo-key
0073: *
0074: * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
0075: * @version $Id: BPage.java,v 1.6 2003/09/21 15:46:59 boisvert Exp $
0076: */
0077: public final class BPage implements Serializer {
0078:
0079: private static final boolean DEBUG = false;
0080:
0081: /**
0082: * Version id for serialization.
0083: */
0084: final static long serialVersionUID = 1L;
0085:
0086: /**
0087: * Parent B+Tree.
0088: */
0089: transient BTree _btree;
0090:
0091: /**
0092: * This BPage's record ID in the PageManager.
0093: */
0094: protected transient long _recid;
0095:
0096: /**
0097: * Flag indicating if this is a leaf BPage.
0098: */
0099: protected boolean _isLeaf;
0100:
0101: /**
0102: * Keys of children nodes
0103: */
0104: protected Object[] _keys;
0105:
0106: /**
0107: * Values associated with keys. (Only valid if leaf BPage)
0108: */
0109: protected Object[] _values;
0110:
0111: /**
0112: * Children pages (recids) associated with keys. (Only valid if non-leaf BPage)
0113: */
0114: protected long[] _children;
0115:
0116: /**
0117: * Index of first used item at the page
0118: */
0119: protected int _first;
0120:
0121: /**
0122: * Previous leaf BPage (only if this BPage is a leaf)
0123: */
0124: protected long _previous;
0125:
0126: /**
0127: * Next leaf BPage (only if this BPage is a leaf)
0128: */
0129: protected long _next;
0130:
0131: /**
0132: * No-argument constructor used by serialization.
0133: */
0134: public BPage() {
0135: // empty
0136: }
0137:
0138: /**
0139: * Root page overflow constructor
0140: */
0141: BPage(BTree btree, BPage root, BPage overflow) throws IOException {
0142: _btree = btree;
0143:
0144: _isLeaf = false;
0145:
0146: _first = _btree._pageSize - 2;
0147:
0148: _keys = new Object[_btree._pageSize];
0149: _keys[_btree._pageSize - 2] = overflow.getLargestKey();
0150: _keys[_btree._pageSize - 1] = root.getLargestKey();
0151:
0152: _children = new long[_btree._pageSize];
0153: _children[_btree._pageSize - 2] = overflow._recid;
0154: _children[_btree._pageSize - 1] = root._recid;
0155:
0156: _recid = _btree._recman.insert(this , this );
0157: }
0158:
0159: /**
0160: * Root page (first insert) constructor.
0161: */
0162: BPage(BTree btree, Object key, Object value) throws IOException {
0163: _btree = btree;
0164:
0165: _isLeaf = true;
0166:
0167: _first = btree._pageSize - 2;
0168:
0169: _keys = new Object[_btree._pageSize];
0170: _keys[_btree._pageSize - 2] = key;
0171: _keys[_btree._pageSize - 1] = null; // I am the root BPage for now
0172:
0173: _values = new Object[_btree._pageSize];
0174: _values[_btree._pageSize - 2] = value;
0175: _values[_btree._pageSize - 1] = null; // I am the root BPage for now
0176:
0177: _recid = _btree._recman.insert(this , this );
0178: }
0179:
0180: /**
0181: * Overflow page constructor. Creates an empty BPage.
0182: */
0183: BPage(BTree btree, boolean isLeaf) throws IOException {
0184: _btree = btree;
0185:
0186: _isLeaf = isLeaf;
0187:
0188: // page will initially be half-full
0189: _first = _btree._pageSize / 2;
0190:
0191: _keys = new Object[_btree._pageSize];
0192: if (isLeaf) {
0193: _values = new Object[_btree._pageSize];
0194: } else {
0195: _children = new long[_btree._pageSize];
0196: }
0197:
0198: _recid = _btree._recman.insert(this , this );
0199: }
0200:
0201: /**
0202: * Get largest key under this BPage. Null is considered to be the
0203: * greatest possible key.
0204: */
0205: Object getLargestKey() {
0206: return _keys[_btree._pageSize - 1];
0207: }
0208:
0209: /**
0210: * Return true if BPage is empty.
0211: */
0212: boolean isEmpty() {
0213: if (_isLeaf) {
0214: return (_first == _values.length - 1);
0215: } else {
0216: return (_first == _children.length - 1);
0217: }
0218: }
0219:
0220: /**
0221: * Return true if BPage is full.
0222: */
0223: boolean isFull() {
0224: return (_first == 0);
0225: }
0226:
0227: /**
0228: * Find the object associated with the given key.
0229: *
0230: * @param height Height of the current BPage (zero is leaf page)
0231: * @param key The key
0232: * @return TupleBrowser positionned just before the given key, or before
0233: * next greater key if key isn't found.
0234: */
0235: TupleBrowser find(int height, Object key) throws IOException {
0236: int index = findChildren(key);
0237:
0238: /*
0239: if ( DEBUG ) {
0240: System.out.println( "BPage.find() current: " + this
0241: + " height: " + height);
0242: }
0243: */
0244:
0245: height -= 1;
0246:
0247: if (height == 0) {
0248: // leaf BPage
0249: return new Browser(this , index);
0250: } else {
0251: // non-leaf BPage
0252: BPage child = childBPage(index);
0253: return child.find(height, key);
0254: }
0255: }
0256:
0257: /**
0258: * Find first entry and return a browser positioned before it.
0259: *
0260: * @return TupleBrowser positionned just before the first entry.
0261: */
0262: TupleBrowser findFirst() throws IOException {
0263: if (_isLeaf) {
0264: return new Browser(this , _first);
0265: } else {
0266: BPage child = childBPage(_first);
0267: return child.findFirst();
0268: }
0269: }
0270:
0271: /**
0272: * Insert the given key and value.
0273: * <p>
0274: * Since the Btree does not support duplicate entries, the caller must
0275: * specify whether to replace the existing value.
0276: *
0277: * @param height Height of the current BPage (zero is leaf page)
0278: * @param key Insert key
0279: * @param value Insert value
0280: * @param replace Set to true to replace the existing value, if one exists.
0281: * @return Insertion result containing existing value OR a BPage if the key
0282: * was inserted and provoked a BPage overflow.
0283: */
0284: InsertResult insert(int height, Object key, Object value,
0285: boolean replace) throws IOException {
0286: InsertResult result;
0287: long overflow;
0288:
0289: int index = findChildren(key);
0290:
0291: height -= 1;
0292: if (height == 0) {
0293:
0294: result = new InsertResult();
0295:
0296: // inserting on a leaf BPage
0297: overflow = -1;
0298: if (DEBUG) {
0299: System.out
0300: .println("Bpage.insert() Insert on leaf Bpage key="
0301: + key
0302: + " value="
0303: + value
0304: + " index="
0305: + index);
0306: }
0307: if (compare(key, _keys[index]) == 0) {
0308: // key already exists
0309: if (DEBUG) {
0310: System.out
0311: .println("Bpage.insert() Key already exists.");
0312: }
0313: result._existing = _values[index];
0314: if (replace) {
0315: _values[index] = value;
0316: _btree._recman.update(_recid, this , this );
0317: }
0318: // return the existing key
0319: return result;
0320: }
0321: } else {
0322: // non-leaf BPage
0323: BPage child = childBPage(index);
0324: result = child.insert(height, key, value, replace);
0325:
0326: if (result._existing != null) {
0327: // return existing key, if any.
0328: return result;
0329: }
0330:
0331: if (result._overflow == null) {
0332: // no overflow means we're done with insertion
0333: return result;
0334: }
0335:
0336: // there was an overflow, we need to insert the overflow page
0337: // on this BPage
0338: if (DEBUG) {
0339: System.out.println("BPage.insert() Overflow page: "
0340: + result._overflow._recid);
0341: }
0342: key = result._overflow.getLargestKey();
0343: overflow = result._overflow._recid;
0344:
0345: // update child's largest key
0346: _keys[index] = child.getLargestKey();
0347:
0348: // clean result so we can reuse it
0349: result._overflow = null;
0350: }
0351:
0352: // if we get here, we need to insert a new entry on the BPage
0353: // before _children[ index ]
0354: if (!isFull()) {
0355: if (height == 0) {
0356: insertEntry(this , index - 1, key, value);
0357: } else {
0358: insertChild(this , index - 1, key, overflow);
0359: }
0360: _btree._recman.update(_recid, this , this );
0361: return result;
0362: }
0363:
0364: // page is full, we must divide the page
0365: int half = _btree._pageSize >> 1;
0366: BPage newPage = new BPage(_btree, _isLeaf);
0367: if (index < half) {
0368: // move lower-half of entries to overflow BPage,
0369: // including new entry
0370: if (DEBUG) {
0371: System.out
0372: .println("Bpage.insert() move lower-half of entries to overflow BPage, including new entry.");
0373: }
0374: if (height == 0) {
0375: copyEntries(this , 0, newPage, half, index);
0376: setEntry(newPage, half + index, key, value);
0377: copyEntries(this , index, newPage, half + index + 1,
0378: half - index - 1);
0379: } else {
0380: copyChildren(this , 0, newPage, half, index);
0381: setChild(newPage, half + index, key, overflow);
0382: copyChildren(this , index, newPage, half + index + 1,
0383: half - index - 1);
0384: }
0385: } else {
0386: // move lower-half of entries to overflow BPage,
0387: // new entry stays on this BPage
0388: if (DEBUG) {
0389: System.out
0390: .println("Bpage.insert() move lower-half of entries to overflow BPage. New entry stays");
0391: }
0392: if (height == 0) {
0393: copyEntries(this , 0, newPage, half, half);
0394: copyEntries(this , half, this , half - 1, index - half);
0395: setEntry(this , index - 1, key, value);
0396: } else {
0397: copyChildren(this , 0, newPage, half, half);
0398: copyChildren(this , half, this , half - 1, index - half);
0399: setChild(this , index - 1, key, overflow);
0400: }
0401: }
0402:
0403: _first = half - 1;
0404:
0405: // nullify lower half of entries
0406: for (int i = 0; i < _first; i++) {
0407: if (height == 0) {
0408: setEntry(this , i, null, null);
0409: } else {
0410: setChild(this , i, null, -1);
0411: }
0412: }
0413:
0414: if (_isLeaf) {
0415: // link newly created BPage
0416: newPage._previous = _previous;
0417: newPage._next = _recid;
0418: if (_previous != 0) {
0419: BPage previous = loadBPage(_previous);
0420: previous._next = newPage._recid;
0421: _btree._recman.update(_previous, previous, this );
0422: }
0423: _previous = newPage._recid;
0424: }
0425:
0426: _btree._recman.update(_recid, this , this );
0427: _btree._recman.update(newPage._recid, newPage, this );
0428:
0429: result._overflow = newPage;
0430: return result;
0431: }
0432:
0433: /**
0434: * Remove the entry associated with the given key.
0435: *
0436: * @param height Height of the current BPage (zero is leaf page)
0437: * @param key Removal key
0438: * @return Remove result object
0439: */
0440: RemoveResult remove(int height, Object key) throws IOException {
0441: RemoveResult result;
0442:
0443: int half = _btree._pageSize / 2;
0444: int index = findChildren(key);
0445:
0446: height -= 1;
0447: if (height == 0) {
0448: // remove leaf entry
0449: if (compare(_keys[index], key) != 0) {
0450: throw new IllegalArgumentException("Key not found: "
0451: + key);
0452: }
0453: result = new RemoveResult();
0454: result._value = _values[index];
0455: removeEntry(this , index);
0456:
0457: // update this BPage
0458: _btree._recman.update(_recid, this , this );
0459:
0460: } else {
0461: // recurse into Btree to remove entry on a children page
0462: BPage child = childBPage(index);
0463: result = child.remove(height, key);
0464:
0465: // update children
0466: _keys[index] = child.getLargestKey();
0467: _btree._recman.update(_recid, this , this );
0468:
0469: if (result._underflow) {
0470: // underflow occured
0471: if (child._first != half + 1) {
0472: throw new IllegalStateException(
0473: "Error during underflow [1]");
0474: }
0475: if (index < _children.length - 1) {
0476: // exists greater brother page
0477: BPage brother = childBPage(index + 1);
0478: int bfirst = brother._first;
0479: if (bfirst < half) {
0480: // steal entries from "brother" page
0481: int steal = (half - bfirst + 1) / 2;
0482: brother._first += steal;
0483: child._first -= steal;
0484: if (child._isLeaf) {
0485: copyEntries(child, half + 1, child, half
0486: + 1 - steal, half - 1);
0487: copyEntries(brother, bfirst, child, 2
0488: * half - steal, steal);
0489: } else {
0490: copyChildren(child, half + 1, child, half
0491: + 1 - steal, half - 1);
0492: copyChildren(brother, bfirst, child, 2
0493: * half - steal, steal);
0494: }
0495:
0496: for (int i = bfirst; i < bfirst + steal; i++) {
0497: if (brother._isLeaf) {
0498: setEntry(brother, i, null, null);
0499: } else {
0500: setChild(brother, i, null, -1);
0501: }
0502: }
0503:
0504: // update child's largest key
0505: _keys[index] = child.getLargestKey();
0506:
0507: // no change in previous/next BPage
0508:
0509: // update BPages
0510: _btree._recman.update(_recid, this , this );
0511: _btree._recman.update(brother._recid, brother,
0512: this );
0513: _btree._recman
0514: .update(child._recid, child, this );
0515:
0516: } else {
0517: // move all entries from page "child" to "brother"
0518: if (brother._first != half) {
0519: throw new IllegalStateException(
0520: "Error during underflow [2]");
0521: }
0522:
0523: brother._first = 1;
0524: if (child._isLeaf) {
0525: copyEntries(child, half + 1, brother, 1,
0526: half - 1);
0527: } else {
0528: copyChildren(child, half + 1, brother, 1,
0529: half - 1);
0530: }
0531: _btree._recman.update(brother._recid, brother,
0532: this );
0533:
0534: // remove "child" from current BPage
0535: if (_isLeaf) {
0536: copyEntries(this , _first, this , _first + 1,
0537: index - _first);
0538: setEntry(this , _first, null, null);
0539: } else {
0540: copyChildren(this , _first, this ,
0541: _first + 1, index - _first);
0542: setChild(this , _first, null, -1);
0543: }
0544: _first += 1;
0545: _btree._recman.update(_recid, this , this );
0546:
0547: // re-link previous and next BPages
0548: if (child._previous != 0) {
0549: BPage prev = loadBPage(child._previous);
0550: prev._next = child._next;
0551: _btree._recman.update(prev._recid, prev,
0552: this );
0553: }
0554: if (child._next != 0) {
0555: BPage next = loadBPage(child._next);
0556: next._previous = child._previous;
0557: _btree._recman.update(next._recid, next,
0558: this );
0559: }
0560:
0561: // delete "child" BPage
0562: _btree._recman.delete(child._recid);
0563: }
0564: } else {
0565: // page "brother" is before "child"
0566: BPage brother = childBPage(index - 1);
0567: int bfirst = brother._first;
0568: if (bfirst < half) {
0569: // steal entries from "brother" page
0570: int steal = (half - bfirst + 1) / 2;
0571: brother._first += steal;
0572: child._first -= steal;
0573: if (child._isLeaf) {
0574: copyEntries(brother, 2 * half - steal,
0575: child, half + 1 - steal, steal);
0576: copyEntries(brother, bfirst, brother,
0577: bfirst + steal, 2 * half - bfirst
0578: - steal);
0579: } else {
0580: copyChildren(brother, 2 * half - steal,
0581: child, half + 1 - steal, steal);
0582: copyChildren(brother, bfirst, brother,
0583: bfirst + steal, 2 * half - bfirst
0584: - steal);
0585: }
0586:
0587: for (int i = bfirst; i < bfirst + steal; i++) {
0588: if (brother._isLeaf) {
0589: setEntry(brother, i, null, null);
0590: } else {
0591: setChild(brother, i, null, -1);
0592: }
0593: }
0594:
0595: // update brother's largest key
0596: _keys[index - 1] = brother.getLargestKey();
0597:
0598: // no change in previous/next BPage
0599:
0600: // update BPages
0601: _btree._recman.update(_recid, this , this );
0602: _btree._recman.update(brother._recid, brother,
0603: this );
0604: _btree._recman
0605: .update(child._recid, child, this );
0606:
0607: } else {
0608: // move all entries from page "brother" to "child"
0609: if (brother._first != half) {
0610: throw new IllegalStateException(
0611: "Error during underflow [3]");
0612: }
0613:
0614: child._first = 1;
0615: if (child._isLeaf) {
0616: copyEntries(brother, half, child, 1, half);
0617: } else {
0618: copyChildren(brother, half, child, 1, half);
0619: }
0620: _btree._recman
0621: .update(child._recid, child, this );
0622:
0623: // remove "brother" from current BPage
0624: if (_isLeaf) {
0625: copyEntries(this , _first, this , _first + 1,
0626: index - 1 - _first);
0627: setEntry(this , _first, null, null);
0628: } else {
0629: copyChildren(this , _first, this ,
0630: _first + 1, index - 1 - _first);
0631: setChild(this , _first, null, -1);
0632: }
0633: _first += 1;
0634: _btree._recman.update(_recid, this , this );
0635:
0636: // re-link previous and next BPages
0637: if (brother._previous != 0) {
0638: BPage prev = loadBPage(brother._previous);
0639: prev._next = brother._next;
0640: _btree._recman.update(prev._recid, prev,
0641: this );
0642: }
0643: if (brother._next != 0) {
0644: BPage next = loadBPage(brother._next);
0645: next._previous = brother._previous;
0646: _btree._recman.update(next._recid, next,
0647: this );
0648: }
0649:
0650: // delete "brother" BPage
0651: _btree._recman.delete(brother._recid);
0652: }
0653: }
0654: }
0655: }
0656:
0657: // underflow if page is more than half-empty
0658: result._underflow = _first > half;
0659:
0660: return result;
0661: }
0662:
0663: /**
0664: * Find the first children node with a key equal or greater than the given
0665: * key.
0666: *
0667: * @return index of first children with equal or greater key.
0668: */
0669: private int findChildren(Object key) {
0670: int left = _first;
0671: int right = _btree._pageSize - 1;
0672:
0673: // binary search
0674: while (left < right) {
0675: int middle = (left + right) / 2;
0676: if (compare(_keys[middle], key) < 0) {
0677: left = middle + 1;
0678: } else {
0679: right = middle;
0680: }
0681: }
0682: return right;
0683: }
0684:
0685: /**
0686: * Insert entry at given position.
0687: */
0688: private static void insertEntry(BPage page, int index, Object key,
0689: Object value) {
0690: Object[] keys = page._keys;
0691: Object[] values = page._values;
0692: int start = page._first;
0693: int count = index - page._first + 1;
0694:
0695: // shift entries to the left
0696: System.arraycopy(keys, start, keys, start - 1, count);
0697: System.arraycopy(values, start, values, start - 1, count);
0698: page._first -= 1;
0699: keys[index] = key;
0700: values[index] = value;
0701: }
0702:
0703: /**
0704: * Insert child at given position.
0705: */
0706: private static void insertChild(BPage page, int index, Object key,
0707: long child) {
0708: Object[] keys = page._keys;
0709: long[] children = page._children;
0710: int start = page._first;
0711: int count = index - page._first + 1;
0712:
0713: // shift entries to the left
0714: System.arraycopy(keys, start, keys, start - 1, count);
0715: System.arraycopy(children, start, children, start - 1, count);
0716: page._first -= 1;
0717: keys[index] = key;
0718: children[index] = child;
0719: }
0720:
0721: /**
0722: * Remove entry at given position.
0723: */
0724: private static void removeEntry(BPage page, int index) {
0725: Object[] keys = page._keys;
0726: Object[] values = page._values;
0727: int start = page._first;
0728: int count = index - page._first;
0729:
0730: System.arraycopy(keys, start, keys, start + 1, count);
0731: keys[start] = null;
0732: System.arraycopy(values, start, values, start + 1, count);
0733: values[start] = null;
0734: page._first++;
0735: }
0736:
0737: /**
0738: * Remove child at given position.
0739: */
0740: /*
0741: private static void removeChild( BPage page, int index )
0742: {
0743: Object[] keys = page._keys;
0744: long[] children = page._children;
0745: int start = page._first;
0746: int count = index-page._first;
0747:
0748: System.arraycopy( keys, start, keys, start+1, count );
0749: keys[ start ] = null;
0750: System.arraycopy( children, start, children, start+1, count );
0751: children[ start ] = (long) -1;
0752: page._first++;
0753: }
0754: */
0755:
0756: /**
0757: * Set the entry at the given index.
0758: */
0759: private static void setEntry(BPage page, int index, Object key,
0760: Object value) {
0761: page._keys[index] = key;
0762: page._values[index] = value;
0763: }
0764:
0765: /**
0766: * Set the child BPage recid at the given index.
0767: */
0768: private static void setChild(BPage page, int index, Object key,
0769: long recid) {
0770: page._keys[index] = key;
0771: page._children[index] = recid;
0772: }
0773:
0774: /**
0775: * Copy entries between two BPages
0776: */
0777: private static void copyEntries(BPage source, int indexSource,
0778: BPage dest, int indexDest, int count) {
0779: System.arraycopy(source._keys, indexSource, dest._keys,
0780: indexDest, count);
0781: System.arraycopy(source._values, indexSource, dest._values,
0782: indexDest, count);
0783: }
0784:
0785: /**
0786: * Copy child BPage recids between two BPages
0787: */
0788: private static void copyChildren(BPage source, int indexSource,
0789: BPage dest, int indexDest, int count) {
0790: System.arraycopy(source._keys, indexSource, dest._keys,
0791: indexDest, count);
0792: System.arraycopy(source._children, indexSource, dest._children,
0793: indexDest, count);
0794: }
0795:
0796: /**
0797: * Return the child BPage at given index.
0798: */
0799: BPage childBPage(int index) throws IOException {
0800: return loadBPage(_children[index]);
0801: }
0802:
0803: /**
0804: * Load the BPage at the given recid.
0805: */
0806: private BPage loadBPage(long recid) throws IOException {
0807: BPage child = (BPage) _btree._recman.fetch(recid, this );
0808: child._recid = recid;
0809: child._btree = _btree;
0810: return child;
0811: }
0812:
0813: private final int compare(Object value1, Object value2) {
0814: if (value1 == null) {
0815: return 1;
0816: }
0817: if (value2 == null) {
0818: return -1;
0819: }
0820: return _btree._comparator.compare(value1, value2);
0821: }
0822:
0823: static byte[] readByteArray(ObjectInput in) throws IOException {
0824: int len = in.readInt();
0825: if (len < 0) {
0826: return null;
0827: }
0828: byte[] buf = new byte[len];
0829: in.readFully(buf);
0830: return buf;
0831: }
0832:
0833: static void writeByteArray(ObjectOutput out, byte[] buf)
0834: throws IOException {
0835: if (buf == null) {
0836: out.writeInt(-1);
0837: } else {
0838: out.writeInt(buf.length);
0839: out.write(buf);
0840: }
0841: }
0842:
0843: /**
0844: * Dump the structure of the tree on the screen. This is used for debugging
0845: * purposes only.
0846: */
0847: private void dump(int height) {
0848: String prefix = "";
0849: for (int i = 0; i < height; i++) {
0850: prefix += " ";
0851: }
0852: System.out.println(prefix
0853: + "-------------------------------------- BPage recid="
0854: + _recid);
0855: System.out.println(prefix + "first=" + _first);
0856: for (int i = 0; i < _btree._pageSize; i++) {
0857: if (_isLeaf) {
0858: System.out.println(prefix + "BPage [" + i + "] "
0859: + _keys[i] + " " + _values[i]);
0860: } else {
0861: System.out.println(prefix + "BPage [" + i + "] "
0862: + _keys[i] + " " + _children[i]);
0863: }
0864: }
0865: System.out.println(prefix
0866: + "--------------------------------------");
0867: }
0868:
0869: /**
0870: * Recursively dump the state of the BTree on screen. This is used for
0871: * debugging purposes only.
0872: */
0873: void dumpRecursive(int height, int level) throws IOException {
0874: height -= 1;
0875: level += 1;
0876: if (height > 0) {
0877: for (int i = _first; i < _btree._pageSize; i++) {
0878: if (_keys[i] == null)
0879: break;
0880: BPage child = childBPage(i);
0881: child.dump(level);
0882: child.dumpRecursive(height, level);
0883: }
0884: }
0885: }
0886:
0887: /**
0888: * Assert the ordering of the keys on the BPage. This is used for testing
0889: * purposes only.
0890: */
0891: private void assertConsistency() {
0892: for (int i = _first; i < _btree._pageSize - 1; i++) {
0893: if (compare((byte[]) _keys[i], (byte[]) _keys[i + 1]) >= 0) {
0894: dump(0);
0895: throw new Error("BPage not ordered");
0896: }
0897: }
0898: }
0899:
0900: /**
0901: * Recursively assert the ordering of the BPage entries on this page
0902: * and sub-pages. This is used for testing purposes only.
0903: */
0904: void assertConsistencyRecursive(int height) throws IOException {
0905: assertConsistency();
0906: if (--height > 0) {
0907: for (int i = _first; i < _btree._pageSize; i++) {
0908: if (_keys[i] == null)
0909: break;
0910: BPage child = childBPage(i);
0911: if (compare((byte[]) _keys[i], child.getLargestKey()) != 0) {
0912: dump(0);
0913: child.dump(0);
0914: throw new Error("Invalid child subordinate key");
0915: }
0916: child.assertConsistencyRecursive(height);
0917: }
0918: }
0919: }
0920:
0921: /**
0922: * Deserialize the content of an object from a byte array.
0923: *
0924: * @param serialized Byte array representation of the object
0925: * @return deserialized object
0926: *
0927: */
0928: public Object deserialize(byte[] serialized) throws IOException {
0929: ByteArrayInputStream bais;
0930: ObjectInputStream ois;
0931: BPage bpage;
0932:
0933: bpage = new BPage();
0934: bais = new ByteArrayInputStream(serialized);
0935: ois = new ObjectInputStream(bais);
0936:
0937: bpage._isLeaf = ois.readBoolean();
0938: if (bpage._isLeaf) {
0939: bpage._previous = ois.readLong();
0940: bpage._next = ois.readLong();
0941: }
0942:
0943: bpage._first = ois.readInt();
0944:
0945: bpage._keys = new Object[_btree._pageSize];
0946: try {
0947: for (int i = bpage._first; i < _btree._pageSize; i++) {
0948: if (_btree._keySerializer == null) {
0949: bpage._keys[i] = ois.readObject();
0950: } else {
0951: serialized = readByteArray(ois);
0952: if (serialized != null) {
0953: bpage._keys[i] = _btree._keySerializer
0954: .deserialize(serialized);
0955: }
0956: }
0957: }
0958: } catch (ClassNotFoundException except) {
0959: throw new IOException(except.getMessage());
0960: }
0961:
0962: if (bpage._isLeaf) {
0963: bpage._values = new Object[_btree._pageSize];
0964: try {
0965: for (int i = bpage._first; i < _btree._pageSize; i++) {
0966: if (_btree._valueSerializer == null) {
0967: bpage._values[i] = ois.readObject();
0968: } else {
0969: serialized = readByteArray(ois);
0970: if (serialized != null) {
0971: bpage._values[i] = _btree._valueSerializer
0972: .deserialize(serialized);
0973: }
0974: }
0975: }
0976: } catch (ClassNotFoundException except) {
0977: throw new IOException(except.getMessage());
0978: }
0979: } else {
0980: bpage._children = new long[_btree._pageSize];
0981: for (int i = bpage._first; i < _btree._pageSize; i++) {
0982: bpage._children[i] = ois.readLong();
0983: }
0984: }
0985: ois.close();
0986: bais.close();
0987:
0988: return bpage;
0989: }
0990:
0991: /**
0992: * Serialize the content of an object into a byte array.
0993: *
0994: * @param obj Object to serialize
0995: * @return a byte array representing the object's state
0996: *
0997: */
0998: public byte[] serialize(Object obj) throws IOException {
0999: byte[] serialized;
1000: ByteArrayOutputStream baos;
1001: ObjectOutputStream oos;
1002: BPage bpage;
1003: byte[] data;
1004:
1005: // note: It is assumed that BPage instance doing the serialization is the parent
1006: // of the BPage object being serialized.
1007:
1008: bpage = (BPage) obj;
1009: baos = new ByteArrayOutputStream();
1010: oos = new ObjectOutputStream(baos);
1011:
1012: oos.writeBoolean(bpage._isLeaf);
1013: if (bpage._isLeaf) {
1014: oos.writeLong(bpage._previous);
1015: oos.writeLong(bpage._next);
1016: }
1017:
1018: oos.writeInt(bpage._first);
1019:
1020: for (int i = bpage._first; i < _btree._pageSize; i++) {
1021: if (_btree._keySerializer == null) {
1022: oos.writeObject(bpage._keys[i]);
1023: } else {
1024: if (bpage._keys[i] != null) {
1025: serialized = _btree._keySerializer
1026: .serialize(bpage._keys[i]);
1027: writeByteArray(oos, serialized);
1028: } else {
1029: writeByteArray(oos, null);
1030: }
1031: }
1032: }
1033:
1034: if (bpage._isLeaf) {
1035: for (int i = bpage._first; i < _btree._pageSize; i++) {
1036: if (_btree._valueSerializer == null) {
1037: oos.writeObject(bpage._values[i]);
1038: } else {
1039: if (bpage._values[i] != null) {
1040: serialized = _btree._valueSerializer
1041: .serialize(bpage._values[i]);
1042: writeByteArray(oos, serialized);
1043: } else {
1044: writeByteArray(oos, null);
1045: }
1046: }
1047: }
1048: } else {
1049: for (int i = bpage._first; i < _btree._pageSize; i++) {
1050: oos.writeLong(bpage._children[i]);
1051: }
1052: }
1053:
1054: oos.flush();
1055: data = baos.toByteArray();
1056: oos.close();
1057: baos.close();
1058: return data;
1059: }
1060:
1061: /** STATIC INNER CLASS
1062: * Result from insert() method call
1063: */
1064: static class InsertResult {
1065:
1066: /**
1067: * Overflow page.
1068: */
1069: BPage _overflow;
1070:
1071: /**
1072: * Existing value for the insertion key.
1073: */
1074: Object _existing;
1075:
1076: }
1077:
1078: /** STATIC INNER CLASS
1079: * Result from remove() method call
1080: */
1081: static class RemoveResult {
1082:
1083: /**
1084: * Set to true if underlying pages underflowed
1085: */
1086: boolean _underflow;
1087:
1088: /**
1089: * Removed entry value
1090: */
1091: Object _value;
1092: }
1093:
1094: /** PRIVATE INNER CLASS
1095: * Browser to traverse leaf BPages.
1096: */
1097: static class Browser extends TupleBrowser {
1098:
1099: /**
1100: * Current page.
1101: */
1102: private BPage _page;
1103:
1104: /**
1105: * Current index in the page. The index positionned on the next
1106: * tuple to return.
1107: */
1108: private int _index;
1109:
1110: /**
1111: * Create a browser.
1112: *
1113: * @param page Current page
1114: * @param index Position of the next tuple to return.
1115: */
1116: Browser(BPage page, int index) {
1117: _page = page;
1118: _index = index;
1119: }
1120:
1121: public boolean getNext(Tuple tuple) throws IOException {
1122: if (_index < _page._btree._pageSize) {
1123: if (_page._keys[_index] == null) {
1124: // reached end of the tree.
1125: return false;
1126: }
1127: } else if (_page._next != 0) {
1128: // move to next page
1129: _page = _page.loadBPage(_page._next);
1130: _index = _page._first;
1131: }
1132: tuple.setKey(_page._keys[_index]);
1133: tuple.setValue(_page._values[_index]);
1134: _index++;
1135: return true;
1136: }
1137:
1138: public boolean getPrevious(Tuple tuple) throws IOException {
1139: if (_index == _page._first) {
1140:
1141: if (_page._previous != 0) {
1142: _page = _page.loadBPage(_page._previous);
1143: _index = _page._btree._pageSize;
1144: } else {
1145: // reached beginning of the tree
1146: return false;
1147: }
1148: }
1149: _index--;
1150: tuple.setKey(_page._keys[_index]);
1151: tuple.setValue(_page._values[_index]);
1152: return true;
1153:
1154: }
1155: }
1156:
1157: }
|