0001: package org.garret.perst.impl;
0002:
0003: import org.garret.perst.*;
0004: import java.util.ArrayList;
0005:
0006: class BtreePage {
0007: static final int firstKeyOffs = 4;
0008: static final int keySpace = Page.pageSize - firstKeyOffs;
0009: static final int strKeySize = 8;
0010: static final int maxItems = keySpace / 4;
0011:
0012: static int getnItems(Page pg) {
0013: return Bytes.unpack2(pg.data, 0);
0014: }
0015:
0016: static int getSize(Page pg) {
0017: return Bytes.unpack2(pg.data, 2);
0018: }
0019:
0020: static int getKeyStrOid(Page pg, int index) {
0021: return Bytes.unpack4(pg.data, firstKeyOffs + index * 8);
0022: }
0023:
0024: static int getKeyStrSize(Page pg, int index) {
0025: return Bytes.unpack2(pg.data, firstKeyOffs + index * 8 + 4);
0026: }
0027:
0028: static int getKeyStrOffs(Page pg, int index) {
0029: return Bytes.unpack2(pg.data, firstKeyOffs + index * 8 + 6);
0030: }
0031:
0032: static int getReference(Page pg, int index) {
0033: return Bytes.unpack4(pg.data, firstKeyOffs + index * 4);
0034: }
0035:
0036: static void setnItems(Page pg, int nItems) {
0037: Bytes.pack2(pg.data, 0, (short) nItems);
0038: }
0039:
0040: static void setSize(Page pg, int size) {
0041: Bytes.pack2(pg.data, 2, (short) size);
0042: }
0043:
0044: static void setKeyStrOid(Page pg, int index, int oid) {
0045: Bytes.pack4(pg.data, firstKeyOffs + index * 8, oid);
0046: }
0047:
0048: static void setKeyStrSize(Page pg, int index, int size) {
0049: Bytes
0050: .pack2(pg.data, firstKeyOffs + index * 8 + 4,
0051: (short) size);
0052: }
0053:
0054: static void setKeyStrOffs(Page pg, int index, int offs) {
0055: Bytes
0056: .pack2(pg.data, firstKeyOffs + index * 8 + 6,
0057: (short) offs);
0058: }
0059:
0060: static void setKeyStrChars(Page pg, int offs, char[] str) {
0061: int len = str.length;
0062: for (int i = 0; i < len; i++) {
0063: Bytes.pack2(pg.data, firstKeyOffs + offs, (short) str[i]);
0064: offs += 2;
0065: }
0066: }
0067:
0068: static void setKeyBytes(Page pg, int offs, byte[] bytes) {
0069: System.arraycopy(bytes, 0, pg.data, firstKeyOffs + offs,
0070: bytes.length);
0071: }
0072:
0073: static void setReference(Page pg, int index, int oid) {
0074: Bytes.pack4(pg.data, firstKeyOffs + index * 4, oid);
0075: }
0076:
0077: final static int compare(Key key, Page pg, int i) {
0078: long i8;
0079: int i4;
0080: float r4;
0081: double r8;
0082: switch (key.type) {
0083: case ClassDescriptor.tpBoolean:
0084: case ClassDescriptor.tpByte:
0085: return (byte) key.ival
0086: - pg.data[BtreePage.firstKeyOffs + i];
0087: case ClassDescriptor.tpShort:
0088: return (short) key.ival
0089: - Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i
0090: * 2);
0091: case ClassDescriptor.tpChar:
0092: return (char) key.ival
0093: - (char) Bytes.unpack2(pg.data,
0094: BtreePage.firstKeyOffs + i * 2);
0095: case ClassDescriptor.tpObject:
0096: case ClassDescriptor.tpInt:
0097: case ClassDescriptor.tpEnum:
0098: i4 = Bytes.unpack4(pg.data, BtreePage.firstKeyOffs + i * 4);
0099: return key.ival < i4 ? -1 : key.ival == i4 ? 0 : 1;
0100: case ClassDescriptor.tpLong:
0101: case ClassDescriptor.tpDate:
0102: i8 = Bytes.unpack8(pg.data, BtreePage.firstKeyOffs + i * 8);
0103: return key.lval < i8 ? -1 : key.lval == i8 ? 0 : 1;
0104: case ClassDescriptor.tpFloat:
0105: r4 = Float.intBitsToFloat(Bytes.unpack4(pg.data,
0106: BtreePage.firstKeyOffs + i * 4));
0107: return key.dval < r4 ? -1 : key.dval == r4 ? 0 : 1;
0108: case ClassDescriptor.tpDouble:
0109: r8 = Double.longBitsToDouble(Bytes.unpack8(pg.data,
0110: BtreePage.firstKeyOffs + i * 8));
0111: return key.dval < r8 ? -1 : key.dval == r8 ? 0 : 1;
0112: }
0113: Assert.failed("Invalid type");
0114: return 0;
0115: }
0116:
0117: final static int compareStr(Key key, Page pg, int i) {
0118: char[] chars = (char[]) key.oval;
0119: int alen = chars.length;
0120: int blen = BtreePage.getKeyStrSize(pg, i);
0121: int minlen = alen < blen ? alen : blen;
0122: int offs = BtreePage.getKeyStrOffs(pg, i)
0123: + BtreePage.firstKeyOffs;
0124: byte[] b = pg.data;
0125: for (int j = 0; j < minlen; j++) {
0126: int diff = chars[j] - (char) Bytes.unpack2(b, offs);
0127: if (diff != 0) {
0128: return diff;
0129: }
0130: offs += 2;
0131: }
0132: return alen - blen;
0133: }
0134:
0135: final static int comparePrefix(char[] key, Page pg, int i) {
0136: int alen = key.length;
0137: int blen = BtreePage.getKeyStrSize(pg, i);
0138: int minlen = alen < blen ? alen : blen;
0139: int offs = BtreePage.getKeyStrOffs(pg, i)
0140: + BtreePage.firstKeyOffs;
0141: byte[] b = pg.data;
0142: for (int j = 0; j < minlen; j++) {
0143: int diff = key[j] - (char) Bytes.unpack2(b, offs);
0144: if (diff != 0) {
0145: return diff;
0146: }
0147: offs += 2;
0148: }
0149: return minlen - blen;
0150: }
0151:
0152: static boolean find(StorageImpl db, int pageId, Key firstKey,
0153: Key lastKey, Btree tree, int height, ArrayList result) {
0154: Page pg = db.getPage(pageId);
0155: int l = 0, n = getnItems(pg), r = n;
0156: int oid;
0157: height -= 1;
0158: try {
0159: if (tree.type == ClassDescriptor.tpString) {
0160: if (firstKey != null) {
0161: while (l < r) {
0162: int i = (l + r) >> 1;
0163: if (compareStr(firstKey, pg, i) >= firstKey.inclusion) {
0164: l = i + 1;
0165: } else {
0166: r = i;
0167: }
0168: }
0169: Assert.that(r == l);
0170: }
0171: if (lastKey != null) {
0172: if (height == 0) {
0173: while (l < n) {
0174: if (-compareStr(lastKey, pg, l) >= lastKey.inclusion) {
0175: return false;
0176: }
0177: oid = getKeyStrOid(pg, l);
0178: result.add(db.lookupObject(oid, null));
0179: l += 1;
0180: }
0181: } else {
0182: do {
0183: if (!find(db, getKeyStrOid(pg, l),
0184: firstKey, lastKey, tree, height,
0185: result)) {
0186: return false;
0187: }
0188: if (l == n) {
0189: return true;
0190: }
0191: } while (compareStr(lastKey, pg, l++) >= 0);
0192: return false;
0193: }
0194: } else {
0195: if (height == 0) {
0196: while (l < n) {
0197: oid = getKeyStrOid(pg, l);
0198: result.add(db.lookupObject(oid, null));
0199: l += 1;
0200: }
0201: } else {
0202: do {
0203: if (!find(db, getKeyStrOid(pg, l),
0204: firstKey, lastKey, tree, height,
0205: result)) {
0206: return false;
0207: }
0208: } while (++l <= n);
0209: }
0210: }
0211: } else if (tree.type == ClassDescriptor.tpArrayOfByte) {
0212: if (firstKey != null) {
0213: while (l < r) {
0214: int i = (l + r) >> 1;
0215: if (tree.compareByteArrays(firstKey, pg, i) >= firstKey.inclusion) {
0216: l = i + 1;
0217: } else {
0218: r = i;
0219: }
0220: }
0221: Assert.that(r == l);
0222: }
0223: if (lastKey != null) {
0224: if (height == 0) {
0225: while (l < n) {
0226: if (-tree.compareByteArrays(lastKey, pg, l) >= lastKey.inclusion) {
0227: return false;
0228: }
0229: oid = getKeyStrOid(pg, l);
0230: result.add(db.lookupObject(oid, null));
0231: l += 1;
0232: }
0233: } else {
0234: do {
0235: if (!find(db, getKeyStrOid(pg, l),
0236: firstKey, lastKey, tree, height,
0237: result)) {
0238: return false;
0239: }
0240: if (l == n) {
0241: return true;
0242: }
0243: } while (tree.compareByteArrays(lastKey, pg,
0244: l++) >= 0);
0245: return false;
0246: }
0247: } else {
0248: if (height == 0) {
0249: while (l < n) {
0250: oid = getKeyStrOid(pg, l);
0251: result.add(db.lookupObject(oid, null));
0252: l += 1;
0253: }
0254: } else {
0255: do {
0256: if (!find(db, getKeyStrOid(pg, l),
0257: firstKey, lastKey, tree, height,
0258: result)) {
0259: return false;
0260: }
0261: } while (++l <= n);
0262: }
0263: }
0264: } else {
0265: if (firstKey != null) {
0266: while (l < r) {
0267: int i = (l + r) >> 1;
0268: if (compare(firstKey, pg, i) >= firstKey.inclusion) {
0269: l = i + 1;
0270: } else {
0271: r = i;
0272: }
0273: }
0274: Assert.that(r == l);
0275: }
0276: if (lastKey != null) {
0277: if (height == 0) {
0278: while (l < n) {
0279: if (-compare(lastKey, pg, l) >= lastKey.inclusion) {
0280: return false;
0281: }
0282: oid = getReference(pg, maxItems - 1 - l);
0283: result.add(db.lookupObject(oid, null));
0284: l += 1;
0285: }
0286: return true;
0287: } else {
0288: do {
0289: if (!find(db, getReference(pg, maxItems - 1
0290: - l), firstKey, lastKey, tree,
0291: height, result)) {
0292: return false;
0293: }
0294: if (l == n) {
0295: return true;
0296: }
0297: } while (compare(lastKey, pg, l++) >= 0);
0298: return false;
0299: }
0300: }
0301: if (height == 0) {
0302: while (l < n) {
0303: oid = getReference(pg, maxItems - 1 - l);
0304: result.add(db.lookupObject(oid, null));
0305: l += 1;
0306: }
0307: } else {
0308: do {
0309: if (!find(db,
0310: getReference(pg, maxItems - 1 - l),
0311: firstKey, lastKey, tree, height, result)) {
0312: return false;
0313: }
0314: } while (++l <= n);
0315: }
0316: }
0317: } finally {
0318: db.pool.unfix(pg);
0319: }
0320: return true;
0321: }
0322:
0323: static boolean prefixSearch(StorageImpl db, int pageId, char[] key,
0324: int height, ArrayList result) {
0325: Page pg = db.getPage(pageId);
0326: int l = 0, n = getnItems(pg), r = n;
0327: int oid;
0328: height -= 1;
0329: try {
0330: while (l < r) {
0331: int i = (l + r) >> 1;
0332: if (comparePrefix(key, pg, i) > 0) {
0333: l = i + 1;
0334: } else {
0335: r = i;
0336: }
0337: }
0338: Assert.that(r == l);
0339: if (height == 0) {
0340: while (l < n) {
0341: if (comparePrefix(key, pg, l) < 0) {
0342: return false;
0343: }
0344: oid = getKeyStrOid(pg, l);
0345: result.add(db.lookupObject(oid, null));
0346: l += 1;
0347: }
0348: } else {
0349: do {
0350: if (!prefixSearch(db, getKeyStrOid(pg, l), key,
0351: height, result)) {
0352: return false;
0353: }
0354: if (l == n) {
0355: return true;
0356: }
0357: } while (comparePrefix(key, pg, l++) >= 0);
0358: return false;
0359: }
0360: } finally {
0361: db.pool.unfix(pg);
0362: }
0363: return true;
0364: }
0365:
0366: static int allocate(StorageImpl db, int root, int type, BtreeKey ins) {
0367: int pageId = db.allocatePage();
0368: Page pg = db.putPage(pageId);
0369: setnItems(pg, 1);
0370: if (type == ClassDescriptor.tpString) {
0371: char[] sval = (char[]) ins.key.oval;
0372: int len = sval.length;
0373: setSize(pg, len * 2);
0374: setKeyStrOffs(pg, 0, keySpace - len * 2);
0375: setKeyStrSize(pg, 0, len);
0376: setKeyStrOid(pg, 0, ins.oid);
0377: setKeyStrOid(pg, 1, root);
0378: setKeyStrChars(pg, keySpace - len * 2, sval);
0379: } else if (type == ClassDescriptor.tpArrayOfByte) {
0380: byte[] bval = (byte[]) ins.key.oval;
0381: int len = bval.length;
0382: setSize(pg, len);
0383: setKeyStrOffs(pg, 0, keySpace - len);
0384: setKeyStrSize(pg, 0, len);
0385: setKeyStrOid(pg, 0, ins.oid);
0386: setKeyStrOid(pg, 1, root);
0387: setKeyBytes(pg, keySpace - len, bval);
0388: } else {
0389: ins.pack(pg, 0);
0390: setReference(pg, maxItems - 2, root);
0391: }
0392: db.pool.unfix(pg);
0393: return pageId;
0394: }
0395:
0396: static void memcpy(Page dst_pg, int dst_idx, Page src_pg,
0397: int src_idx, int len, int itemSize) {
0398: System.arraycopy(src_pg.data,
0399: firstKeyOffs + src_idx * itemSize, dst_pg.data,
0400: firstKeyOffs + dst_idx * itemSize, len * itemSize);
0401: }
0402:
0403: static int insert(StorageImpl db, int pageId, Btree tree,
0404: BtreeKey ins, int height, boolean unique, boolean overwrite) {
0405: Page pg = db.getPage(pageId);
0406: int result;
0407: int l = 0, n = getnItems(pg), r = n;
0408: int ahead = unique ? 1 : 0;
0409: try {
0410: if (tree.type == ClassDescriptor.tpString) {
0411: while (l < r) {
0412: int i = (l + r) >> 1;
0413: if (compareStr(ins.key, pg, i) >= ahead) {
0414: l = i + 1;
0415: } else {
0416: r = i;
0417: }
0418: }
0419: Assert.that(l == r);
0420: if (--height != 0) {
0421: result = insert(db, getKeyStrOid(pg, r), tree, ins,
0422: height, unique, overwrite);
0423: Assert.that(result != Btree.op_not_found);
0424: if (result != Btree.op_overflow) {
0425: return result;
0426: }
0427: } else if (r < n && compareStr(ins.key, pg, r) == 0) {
0428: if (overwrite) {
0429: db.pool.unfix(pg);
0430: pg = null;
0431: pg = db.putPage(pageId);
0432: ins.oldOid = getKeyStrOid(pg, r);
0433: setKeyStrOid(pg, r, ins.oid);
0434: return Btree.op_overwrite;
0435: } else if (unique) {
0436: return Btree.op_duplicate;
0437: }
0438: }
0439: db.pool.unfix(pg);
0440: pg = null;
0441: pg = db.putPage(pageId);
0442: return insertStrKey(db, pg, r, ins, height);
0443: } else if (tree.type == ClassDescriptor.tpArrayOfByte) {
0444: while (l < r) {
0445: int i = (l + r) >> 1;
0446: if (tree.compareByteArrays(ins.key, pg, i) >= ahead) {
0447: l = i + 1;
0448: } else {
0449: r = i;
0450: }
0451: }
0452: Assert.that(l == r);
0453: if (--height != 0) {
0454: result = insert(db, getKeyStrOid(pg, r), tree, ins,
0455: height, unique, overwrite);
0456: Assert.that(result != Btree.op_not_found);
0457: if (result != Btree.op_overflow) {
0458: return result;
0459: }
0460: } else if (r < n
0461: && tree.compareByteArrays(ins.key, pg, r) == 0) {
0462: if (overwrite) {
0463: db.pool.unfix(pg);
0464: pg = null;
0465: pg = db.putPage(pageId);
0466: ins.oldOid = getKeyStrOid(pg, r);
0467: setKeyStrOid(pg, r, ins.oid);
0468: return Btree.op_overwrite;
0469: } else if (unique) {
0470: return Btree.op_duplicate;
0471: }
0472: }
0473: db.pool.unfix(pg);
0474: pg = null;
0475: pg = db.putPage(pageId);
0476: return insertByteArrayKey(db, pg, r, ins, height);
0477: } else {
0478: while (l < r) {
0479: int i = (l + r) >> 1;
0480: if (compare(ins.key, pg, i) >= ahead)
0481: l = i + 1;
0482: else
0483: r = i;
0484: }
0485: Assert.that(l == r);
0486: /* insert before e[r] */
0487: if (--height != 0) {
0488: result = insert(db, getReference(pg, maxItems - r
0489: - 1), tree, ins, height, unique, overwrite);
0490: Assert.that(result != Btree.op_not_found);
0491: if (result != Btree.op_overflow) {
0492: return result;
0493: }
0494: n += 1;
0495: } else if (r < n && compare(ins.key, pg, r) == 0) {
0496: if (overwrite) {
0497: db.pool.unfix(pg);
0498: pg = null;
0499: pg = db.putPage(pageId);
0500: ins.oldOid = getReference(pg, maxItems - r - 1);
0501: setReference(pg, maxItems - r - 1, ins.oid);
0502: return Btree.op_overwrite;
0503: } else if (unique) {
0504: return Btree.op_duplicate;
0505: }
0506: }
0507: db.pool.unfix(pg);
0508: pg = null;
0509: pg = db.putPage(pageId);
0510: int itemSize = ClassDescriptor.sizeof[tree.type];
0511: int max = keySpace / (4 + itemSize);
0512: if (n < max) {
0513: memcpy(pg, r + 1, pg, r, n - r, itemSize);
0514: memcpy(pg, maxItems - n - 1, pg, maxItems - n, n
0515: - r, 4);
0516: ins.pack(pg, r);
0517: setnItems(pg, getnItems(pg) + 1);
0518: return Btree.op_done;
0519: } else { /* page is full then divide page */
0520: pageId = db.allocatePage();
0521: Page b = db.putPage(pageId);
0522: Assert.that(n == max);
0523: int m = max / 2;
0524: if (r < m) {
0525: memcpy(b, 0, pg, 0, r, itemSize);
0526: memcpy(b, r + 1, pg, r, m - r - 1, itemSize);
0527: memcpy(pg, 0, pg, m - 1, max - m + 1, itemSize);
0528: memcpy(b, maxItems - r, pg, maxItems - r, r, 4);
0529: ins.pack(b, r);
0530: memcpy(b, maxItems - m, pg, maxItems - m + 1, m
0531: - r - 1, 4);
0532: memcpy(pg, maxItems - max + m - 1, pg, maxItems
0533: - max, max - m + 1, 4);
0534: } else {
0535: memcpy(b, 0, pg, 0, m, itemSize);
0536: memcpy(pg, 0, pg, m, r - m, itemSize);
0537: memcpy(pg, r - m + 1, pg, r, max - r, itemSize);
0538: memcpy(b, maxItems - m, pg, maxItems - m, m, 4);
0539: memcpy(pg, maxItems - r + m, pg, maxItems - r,
0540: r - m, 4);
0541: ins.pack(pg, r - m);
0542: memcpy(pg, maxItems - max + m - 1, pg, maxItems
0543: - max, max - r, 4);
0544: }
0545: ins.oid = pageId;
0546: ins.extract(b, firstKeyOffs + (m - 1) * itemSize,
0547: tree.type);
0548: if (height == 0) {
0549: setnItems(pg, max - m + 1);
0550: setnItems(b, m);
0551: } else {
0552: setnItems(pg, max - m);
0553: setnItems(b, m - 1);
0554: }
0555: db.pool.unfix(b);
0556: return Btree.op_overflow;
0557: }
0558: }
0559: } finally {
0560: if (pg != null) {
0561: db.pool.unfix(pg);
0562: }
0563: }
0564: }
0565:
0566: static int insertStrKey(StorageImpl db, Page pg, int r,
0567: BtreeKey ins, int height) {
0568: int nItems = getnItems(pg);
0569: int size = getSize(pg);
0570: int n = (height != 0) ? nItems + 1 : nItems;
0571: // insert before e[r]
0572: char[] sval = (char[]) ins.key.oval;
0573: int len = sval.length;
0574: if (size + len * 2 + (n + 1) * strKeySize <= keySpace) {
0575: memcpy(pg, r + 1, pg, r, n - r, strKeySize);
0576: size += len * 2;
0577: setKeyStrOffs(pg, r, keySpace - size);
0578: setKeyStrSize(pg, r, len);
0579: setKeyStrOid(pg, r, ins.oid);
0580: setKeyStrChars(pg, keySpace - size, sval);
0581: nItems += 1;
0582: } else { // page is full then divide page
0583: int pageId = db.allocatePage();
0584: Page b = db.putPage(pageId);
0585: int moved = 0;
0586: int inserted = len * 2 + strKeySize;
0587: int prevDelta = (1 << 31) + 1;
0588:
0589: for (int bn = 0, i = 0;; bn += 1) {
0590: int addSize, subSize;
0591: int j = nItems - i - 1;
0592: int keyLen = getKeyStrSize(pg, i);
0593: if (bn == r) {
0594: keyLen = len;
0595: inserted = 0;
0596: addSize = len;
0597: if (height == 0) {
0598: subSize = 0;
0599: j += 1;
0600: } else {
0601: subSize = getKeyStrSize(pg, i);
0602: }
0603: } else {
0604: addSize = subSize = keyLen;
0605: if (height != 0) {
0606: if (i + 1 != r) {
0607: subSize += getKeyStrSize(pg, i + 1);
0608: j -= 1;
0609: } else {
0610: inserted = 0;
0611: }
0612: }
0613: }
0614: int delta = (moved + addSize * 2 + (bn + 1)
0615: * strKeySize)
0616: - (j * strKeySize + size - subSize * 2 + inserted);
0617: if (delta >= -prevDelta) {
0618: if (height == 0) {
0619: ins.getStr(b, bn - 1);
0620: } else {
0621: Assert
0622: .that(
0623: "String fits in the B-Tree page",
0624: moved + (bn + 1) * strKeySize <= keySpace);
0625: if (bn != r) {
0626: ins.getStr(pg, i);
0627: setKeyStrOid(b, bn, getKeyStrOid(pg, i));
0628: size -= keyLen * 2;
0629: i += 1;
0630: } else {
0631: setKeyStrOid(b, bn, ins.oid);
0632: }
0633: }
0634: nItems = compactifyStrings(pg, i);
0635: if (bn < r || (bn == r && height == 0)) {
0636: memcpy(pg, r - i + 1, pg, r - i, n - r,
0637: strKeySize);
0638: size += len * 2;
0639: nItems += 1;
0640: Assert
0641: .that(
0642: "String fits in the B-Tree page",
0643: size + (n - i + 1) * strKeySize <= keySpace);
0644: setKeyStrOffs(pg, r - i, keySpace - size);
0645: setKeyStrSize(pg, r - i, len);
0646: setKeyStrOid(pg, r - i, ins.oid);
0647: setKeyStrChars(pg, keySpace - size, sval);
0648: }
0649: setnItems(b, bn);
0650: setSize(b, moved);
0651: setSize(pg, size);
0652: setnItems(pg, nItems);
0653: ins.oid = pageId;
0654: db.pool.unfix(b);
0655: return Btree.op_overflow;
0656: }
0657: moved += keyLen * 2;
0658: prevDelta = delta;
0659: Assert.that("String fits in the B-Tree page", moved
0660: + (bn + 1) * strKeySize <= keySpace);
0661: setKeyStrSize(b, bn, keyLen);
0662: setKeyStrOffs(b, bn, keySpace - moved);
0663: if (bn == r) {
0664: setKeyStrOid(b, bn, ins.oid);
0665: setKeyStrChars(b, keySpace - moved, sval);
0666: } else {
0667: setKeyStrOid(b, bn, getKeyStrOid(pg, i));
0668: memcpy(b, keySpace - moved, pg,
0669: getKeyStrOffs(pg, i), keyLen * 2, 1);
0670: size -= keyLen * 2;
0671: i += 1;
0672: }
0673: }
0674: }
0675: setnItems(pg, nItems);
0676: setSize(pg, size);
0677: return size + strKeySize * (nItems + 1) < keySpace / 2 ? Btree.op_underflow
0678: : Btree.op_done;
0679: }
0680:
0681: static int insertByteArrayKey(StorageImpl db, Page pg, int r,
0682: BtreeKey ins, int height) {
0683: int nItems = getnItems(pg);
0684: int size = getSize(pg);
0685: int n = (height != 0) ? nItems + 1 : nItems;
0686: byte[] bval = (byte[]) ins.key.oval;
0687: // insert before e[r]
0688: int len = bval.length;
0689: if (size + len + (n + 1) * strKeySize <= keySpace) {
0690: memcpy(pg, r + 1, pg, r, n - r, strKeySize);
0691: size += len;
0692: setKeyStrOffs(pg, r, keySpace - size);
0693: setKeyStrSize(pg, r, len);
0694: setKeyStrOid(pg, r, ins.oid);
0695: setKeyBytes(pg, keySpace - size, bval);
0696: nItems += 1;
0697: } else { // page is full then divide page
0698: int pageId = db.allocatePage();
0699: Page b = db.putPage(pageId);
0700: int moved = 0;
0701: int inserted = len + strKeySize;
0702: int prevDelta = (1 << 31) + 1;
0703:
0704: for (int bn = 0, i = 0;; bn += 1) {
0705: int addSize, subSize;
0706: int j = nItems - i - 1;
0707: int keyLen = getKeyStrSize(pg, i);
0708: if (bn == r) {
0709: keyLen = len;
0710: inserted = 0;
0711: addSize = len;
0712: if (height == 0) {
0713: subSize = 0;
0714: j += 1;
0715: } else {
0716: subSize = getKeyStrSize(pg, i);
0717: }
0718: } else {
0719: addSize = subSize = keyLen;
0720: if (height != 0) {
0721: if (i + 1 != r) {
0722: subSize += getKeyStrSize(pg, i + 1);
0723: j -= 1;
0724: } else {
0725: inserted = 0;
0726: }
0727: }
0728: }
0729: int delta = (moved + addSize + (bn + 1) * strKeySize)
0730: - (j * strKeySize + size - subSize + inserted);
0731: if (delta >= -prevDelta) {
0732: if (height == 0) {
0733: ins.getByteArray(b, bn - 1);
0734: } else {
0735: Assert
0736: .that(
0737: "String fits in the B-Tree page",
0738: moved + (bn + 1) * strKeySize <= keySpace);
0739: if (bn != r) {
0740: ins.getByteArray(pg, i);
0741: setKeyStrOid(b, bn, getKeyStrOid(pg, i));
0742: size -= keyLen;
0743: i += 1;
0744: } else {
0745: setKeyStrOid(b, bn, ins.oid);
0746: }
0747: }
0748: nItems = compactifyByteArrays(pg, i);
0749: if (bn < r || (bn == r && height == 0)) {
0750: memcpy(pg, r - i + 1, pg, r - i, n - r,
0751: strKeySize);
0752: size += len;
0753: nItems += 1;
0754: Assert
0755: .that(
0756: "String fits in the B-Tree page",
0757: size + (n - i + 1) * strKeySize <= keySpace);
0758: setKeyStrOffs(pg, r - i, keySpace - size);
0759: setKeyStrSize(pg, r - i, len);
0760: setKeyStrOid(pg, r - i, ins.oid);
0761: setKeyBytes(pg, keySpace - size, bval);
0762: }
0763: setnItems(b, bn);
0764: setSize(b, moved);
0765: setSize(pg, size);
0766: setnItems(pg, nItems);
0767: ins.oid = pageId;
0768: db.pool.unfix(b);
0769: return Btree.op_overflow;
0770: }
0771: moved += keyLen;
0772: prevDelta = delta;
0773: Assert.that("String fits in the B-Tree page", moved
0774: + (bn + 1) * strKeySize <= keySpace);
0775: setKeyStrSize(b, bn, keyLen);
0776: setKeyStrOffs(b, bn, keySpace - moved);
0777: if (bn == r) {
0778: setKeyStrOid(b, bn, ins.oid);
0779: setKeyBytes(b, keySpace - moved, bval);
0780: } else {
0781: setKeyStrOid(b, bn, getKeyStrOid(pg, i));
0782: memcpy(b, keySpace - moved, pg,
0783: getKeyStrOffs(pg, i), keyLen, 1);
0784: size -= keyLen;
0785: i += 1;
0786: }
0787: }
0788: }
0789: setnItems(pg, nItems);
0790: setSize(pg, size);
0791: return size + strKeySize * (nItems + 1) < keySpace / 2 ? Btree.op_underflow
0792: : Btree.op_done;
0793: }
0794:
0795: static int compactifyStrings(Page pg, int m) {
0796: int i, j, offs, len, n = getnItems(pg);
0797: int[] size = new int[keySpace / 2 + 1];
0798: int[] index = new int[keySpace / 2 + 1];
0799: if (m == 0) {
0800: return n;
0801: }
0802: int nZeroLengthStrings = 0;
0803: if (m < 0) {
0804: m = -m;
0805: for (i = 0; i < n - m; i++) {
0806: len = getKeyStrSize(pg, i);
0807: if (len != 0) {
0808: offs = getKeyStrOffs(pg, i) >>> 1;
0809: size[offs + len] = len;
0810: index[offs + len] = i;
0811: } else {
0812: nZeroLengthStrings += 1;
0813: }
0814: }
0815: for (; i < n; i++) {
0816: len = getKeyStrSize(pg, i);
0817: if (len != 0) {
0818: offs = getKeyStrOffs(pg, i) >>> 1;
0819: size[offs + len] = len;
0820: index[offs + len] = -1;
0821: }
0822: }
0823: } else {
0824: for (i = 0; i < m; i++) {
0825: len = getKeyStrSize(pg, i);
0826: if (len != 0) {
0827: offs = getKeyStrOffs(pg, i) >>> 1;
0828: size[offs + len] = len;
0829: index[offs + len] = -1;
0830: }
0831: }
0832: for (; i < n; i++) {
0833: len = getKeyStrSize(pg, i);
0834: if (len != 0) {
0835: offs = getKeyStrOffs(pg, i) >>> 1;
0836: size[offs + len] = len;
0837: index[offs + len] = i - m;
0838: } else {
0839: nZeroLengthStrings += 1;
0840: }
0841: setKeyStrOid(pg, i - m, getKeyStrOid(pg, i));
0842: setKeyStrSize(pg, i - m, len);
0843: }
0844: setKeyStrOid(pg, i - m, getKeyStrOid(pg, i));
0845: }
0846: int nItems = n -= m;
0847: n -= nZeroLengthStrings;
0848: for (offs = keySpace / 2, i = offs; n != 0; i -= len) {
0849: len = size[i];
0850: j = index[i];
0851: if (j >= 0) {
0852: offs -= len;
0853: n -= 1;
0854: setKeyStrOffs(pg, j, offs * 2);
0855: if (offs != i - len) {
0856: memcpy(pg, offs, pg, i - len, len, 2);
0857: }
0858: }
0859: }
0860: return nItems;
0861: }
0862:
0863: static int compactifyByteArrays(Page pg, int m) {
0864: int i, j, offs, len, n = getnItems(pg);
0865: int[] size = new int[keySpace + 1];
0866: int[] index = new int[keySpace + 1];
0867: if (m == 0) {
0868: return n;
0869: }
0870: int nZeroLengthArrays = 0;
0871: if (m < 0) {
0872: m = -m;
0873: for (i = 0; i < n - m; i++) {
0874: len = getKeyStrSize(pg, i);
0875: if (len != 0) {
0876: offs = getKeyStrOffs(pg, i);
0877: size[offs + len] = len;
0878: index[offs + len] = i;
0879: } else {
0880: nZeroLengthArrays += 1;
0881: }
0882: }
0883: for (; i < n; i++) {
0884: len = getKeyStrSize(pg, i);
0885: if (len != 0) {
0886: offs = getKeyStrOffs(pg, i);
0887: size[offs + len] = len;
0888: index[offs + len] = -1;
0889: }
0890: }
0891: } else {
0892: for (i = 0; i < m; i++) {
0893: len = getKeyStrSize(pg, i);
0894: if (len != 0) {
0895: offs = getKeyStrOffs(pg, i);
0896: size[offs + len] = len;
0897: index[offs + len] = -1;
0898: }
0899: }
0900: for (; i < n; i++) {
0901: len = getKeyStrSize(pg, i);
0902: if (len != 0) {
0903: offs = getKeyStrOffs(pg, i);
0904: size[offs + len] = len;
0905: index[offs + len] = i - m;
0906: } else {
0907: nZeroLengthArrays += 1;
0908: }
0909: setKeyStrOid(pg, i - m, getKeyStrOid(pg, i));
0910: setKeyStrSize(pg, i - m, len);
0911: }
0912: setKeyStrOid(pg, i - m, getKeyStrOid(pg, i));
0913: }
0914: int nItems = n -= m;
0915: n -= nZeroLengthArrays;
0916: for (offs = keySpace, i = offs; n != 0; i -= len) {
0917: len = size[i];
0918: j = index[i];
0919: if (j >= 0) {
0920: offs -= len;
0921: n -= 1;
0922: setKeyStrOffs(pg, j, offs);
0923: if (offs != i - len) {
0924: memcpy(pg, offs, pg, i - len, len, 1);
0925: }
0926: }
0927: }
0928: return nItems;
0929: }
0930:
0931: static int removeStrKey(Page pg, int r) {
0932: int len = getKeyStrSize(pg, r) * 2;
0933: int offs = getKeyStrOffs(pg, r);
0934: int size = getSize(pg);
0935: int nItems = getnItems(pg);
0936: if ((nItems + 1) * strKeySize >= keySpace) {
0937: memcpy(pg, r, pg, r + 1, nItems - r - 1, strKeySize);
0938: } else {
0939: memcpy(pg, r, pg, r + 1, nItems - r, strKeySize);
0940: }
0941: if (len != 0) {
0942: memcpy(pg, keySpace - size + len, pg, keySpace - size, size
0943: - keySpace + offs, 1);
0944: for (int i = nItems; --i >= 0;) {
0945: if (getKeyStrOffs(pg, i) < offs) {
0946: setKeyStrOffs(pg, i, getKeyStrOffs(pg, i) + len);
0947: }
0948: }
0949: setSize(pg, size -= len);
0950: }
0951: setnItems(pg, nItems - 1);
0952: return size + strKeySize * nItems < keySpace / 2 ? Btree.op_underflow
0953: : Btree.op_done;
0954: }
0955:
0956: static int removeByteArrayKey(Page pg, int r) {
0957: int len = getKeyStrSize(pg, r);
0958: int offs = getKeyStrOffs(pg, r);
0959: int size = getSize(pg);
0960: int nItems = getnItems(pg);
0961: if ((nItems + 1) * strKeySize >= keySpace) {
0962: memcpy(pg, r, pg, r + 1, nItems - r - 1, strKeySize);
0963: } else {
0964: memcpy(pg, r, pg, r + 1, nItems - r, strKeySize);
0965: }
0966: if (len != 0) {
0967: memcpy(pg, keySpace - size + len, pg, keySpace - size, size
0968: - keySpace + offs, 1);
0969: for (int i = nItems; --i >= 0;) {
0970: if (getKeyStrOffs(pg, i) < offs) {
0971: setKeyStrOffs(pg, i, getKeyStrOffs(pg, i) + len);
0972: }
0973: }
0974: setSize(pg, size -= len);
0975: }
0976: setnItems(pg, nItems - 1);
0977: return size + strKeySize * nItems < keySpace / 2 ? Btree.op_underflow
0978: : Btree.op_done;
0979: }
0980:
0981: static int replaceStrKey(StorageImpl db, Page pg, int r,
0982: BtreeKey ins, int height) {
0983: ins.oid = getKeyStrOid(pg, r);
0984: removeStrKey(pg, r);
0985: return insertStrKey(db, pg, r, ins, height);
0986: }
0987:
0988: static int replaceByteArrayKey(StorageImpl db, Page pg, int r,
0989: BtreeKey ins, int height) {
0990: ins.oid = getKeyStrOid(pg, r);
0991: removeByteArrayKey(pg, r);
0992: return insertByteArrayKey(db, pg, r, ins, height);
0993: }
0994:
0995: static int handlePageUnderflow(StorageImpl db, Page pg, int r,
0996: int type, BtreeKey rem, int height) {
0997: int nItems = getnItems(pg);
0998: if (type == ClassDescriptor.tpString) {
0999: Page a = db.putPage(getKeyStrOid(pg, r));
1000: int an = getnItems(a);
1001: if (r < nItems) { // exists greater page
1002: Page b = db.getPage(getKeyStrOid(pg, r + 1));
1003: int bn = getnItems(b);
1004: int merged_size = (an + bn) * strKeySize + getSize(a)
1005: + getSize(b);
1006: if (height != 1) {
1007: merged_size += getKeyStrSize(pg, r) * 2
1008: + strKeySize * 2;
1009: }
1010: if (merged_size > keySpace) {
1011: // reallocation of nodes between pages a and b
1012: int i, j, k;
1013: db.pool.unfix(b);
1014: b = db.putPage(getKeyStrOid(pg, r + 1));
1015: int size_a = getSize(a);
1016: int size_b = getSize(b);
1017: int addSize, subSize;
1018: if (height != 1) {
1019: addSize = getKeyStrSize(pg, r);
1020: subSize = getKeyStrSize(b, 0);
1021: } else {
1022: addSize = subSize = getKeyStrSize(b, 0);
1023: }
1024: i = 0;
1025: int prevDelta = (an * strKeySize + size_a)
1026: - (bn * strKeySize + size_b);
1027: while (true) {
1028: i += 1;
1029: int delta = ((an + i) * strKeySize + size_a + addSize * 2)
1030: - ((bn - i) * strKeySize + size_b - subSize * 2);
1031: if (delta >= 0) {
1032: if (delta >= -prevDelta) {
1033: i -= 1;
1034: }
1035: break;
1036: }
1037: size_a += addSize * 2;
1038: size_b -= subSize * 2;
1039: prevDelta = delta;
1040: if (height != 1) {
1041: addSize = subSize;
1042: subSize = getKeyStrSize(b, i);
1043: } else {
1044: addSize = subSize = getKeyStrSize(b, i);
1045: }
1046: }
1047: int result = Btree.op_done;
1048: if (i > 0) {
1049: k = i;
1050: if (height != 1) {
1051: int len = getKeyStrSize(pg, r);
1052: setSize(a, getSize(a) + len * 2);
1053: setKeyStrOffs(a, an, keySpace - getSize(a));
1054: setKeyStrSize(a, an, len);
1055: memcpy(a, getKeyStrOffs(a, an), pg,
1056: getKeyStrOffs(pg, r), len * 2, 1);
1057: k -= 1;
1058: an += 1;
1059: setKeyStrOid(a, an + k, getKeyStrOid(b, k));
1060: setSize(b, getSize(b) - getKeyStrSize(b, k)
1061: * 2);
1062: }
1063: for (j = 0; j < k; j++) {
1064: int len = getKeyStrSize(b, j);
1065: setSize(a, getSize(a) + len * 2);
1066: setSize(b, getSize(b) - len * 2);
1067: setKeyStrOffs(a, an, keySpace - getSize(a));
1068: setKeyStrSize(a, an, len);
1069: setKeyStrOid(a, an, getKeyStrOid(b, j));
1070: memcpy(a, getKeyStrOffs(a, an), b,
1071: getKeyStrOffs(b, j), len * 2, 1);
1072: an += 1;
1073: }
1074: rem.getStr(b, i - 1);
1075: result = replaceStrKey(db, pg, r, rem, height);
1076: setnItems(a, an);
1077: setnItems(b, compactifyStrings(b, i));
1078: }
1079: db.pool.unfix(a);
1080: db.pool.unfix(b);
1081: return result;
1082: } else { // merge page b to a
1083: if (height != 1) {
1084: int r_len = getKeyStrSize(pg, r);
1085: setKeyStrSize(a, an, r_len);
1086: setSize(a, getSize(a) + r_len * 2);
1087: setKeyStrOffs(a, an, keySpace - getSize(a));
1088: memcpy(a, getKeyStrOffs(a, an), pg,
1089: getKeyStrOffs(pg, r), r_len * 2, 1);
1090: an += 1;
1091: setKeyStrOid(a, an + bn, getKeyStrOid(b, bn));
1092: }
1093: for (int i = 0; i < bn; i++, an++) {
1094: setKeyStrSize(a, an, getKeyStrSize(b, i));
1095: setKeyStrOffs(a, an, getKeyStrOffs(b, i)
1096: - getSize(a));
1097: setKeyStrOid(a, an, getKeyStrOid(b, i));
1098: }
1099: setSize(a, getSize(a) + getSize(b));
1100: setnItems(a, an);
1101: memcpy(a, keySpace - getSize(a), b, keySpace
1102: - getSize(b), getSize(b), 1);
1103: db.pool.unfix(a);
1104: db.pool.unfix(b);
1105: db.freePage(getKeyStrOid(pg, r + 1));
1106: setKeyStrOid(pg, r + 1, getKeyStrOid(pg, r));
1107: return removeStrKey(pg, r);
1108: }
1109: } else { // page b is before a
1110: Page b = db.getPage(getKeyStrOid(pg, r - 1));
1111: int bn = getnItems(b);
1112: int merged_size = (an + bn) * strKeySize + getSize(a)
1113: + getSize(b);
1114: if (height != 1) {
1115: merged_size += getKeyStrSize(pg, r - 1) * 2
1116: + strKeySize * 2;
1117: }
1118: if (merged_size > keySpace) {
1119: // reallocation of nodes between pages a and b
1120: int i, j, k, len;
1121: db.pool.unfix(b);
1122: b = db.putPage(getKeyStrOid(pg, r - 1));
1123: int size_a = getSize(a);
1124: int size_b = getSize(b);
1125: int addSize, subSize;
1126: if (height != 1) {
1127: addSize = getKeyStrSize(pg, r - 1);
1128: subSize = getKeyStrSize(b, bn - 1);
1129: } else {
1130: addSize = subSize = getKeyStrSize(b, bn - 1);
1131: }
1132: i = 0;
1133: int prevDelta = (an * strKeySize + size_a)
1134: - (bn * strKeySize + size_b);
1135: while (true) {
1136: i += 1;
1137: int delta = ((an + i) * strKeySize + size_a + addSize * 2)
1138: - ((bn - i) * strKeySize + size_b - subSize * 2);
1139: if (delta >= 0) {
1140: if (delta >= -prevDelta) {
1141: i -= 1;
1142: }
1143: break;
1144: }
1145: prevDelta = delta;
1146: size_a += addSize * 2;
1147: size_b -= subSize * 2;
1148: if (height != 1) {
1149: addSize = subSize;
1150: subSize = getKeyStrSize(b, bn - i - 1);
1151: } else {
1152: addSize = subSize = getKeyStrSize(b, bn - i
1153: - 1);
1154: }
1155: }
1156: int result = Btree.op_done;
1157: if (i > 0) {
1158: k = i;
1159: Assert.that(i < bn);
1160: if (height != 1) {
1161: setSize(b, getSize(b)
1162: - getKeyStrSize(b, bn - k) * 2);
1163: memcpy(a, i, a, 0, an + 1, strKeySize);
1164: k -= 1;
1165: setKeyStrOid(a, k, getKeyStrOid(b, bn));
1166: len = getKeyStrSize(pg, r - 1);
1167: setKeyStrSize(a, k, len);
1168: setSize(a, getSize(a) + len * 2);
1169: setKeyStrOffs(a, k, keySpace - getSize(a));
1170: memcpy(a, getKeyStrOffs(a, k), pg,
1171: getKeyStrOffs(pg, r - 1), len * 2,
1172: 1);
1173: } else {
1174: memcpy(a, i, a, 0, an, strKeySize);
1175: }
1176: for (j = 0; j < k; j++) {
1177: len = getKeyStrSize(b, bn - k + j);
1178: setSize(a, getSize(a) + len * 2);
1179: setSize(b, getSize(b) - len * 2);
1180: setKeyStrOffs(a, j, keySpace - getSize(a));
1181: setKeyStrSize(a, j, len);
1182: setKeyStrOid(a, j, getKeyStrOid(b, bn - k
1183: + j));
1184: memcpy(a, getKeyStrOffs(a, j), b,
1185: getKeyStrOffs(b, bn - k + j),
1186: len * 2, 1);
1187: }
1188: an += i;
1189: setnItems(a, an);
1190: rem.getStr(b, bn - k - 1);
1191: result = replaceStrKey(db, pg, r - 1, rem,
1192: height);
1193: setnItems(b, compactifyStrings(b, -i));
1194: }
1195: db.pool.unfix(a);
1196: db.pool.unfix(b);
1197: return result;
1198: } else { // merge page b to a
1199: if (height != 1) {
1200: memcpy(a, bn + 1, a, 0, an + 1, strKeySize);
1201: int len = getKeyStrSize(pg, r - 1);
1202: setKeyStrSize(a, bn, len);
1203: setSize(a, getSize(a) + len * 2);
1204: setKeyStrOffs(a, bn, keySpace - getSize(a));
1205: setKeyStrOid(a, bn, getKeyStrOid(b, bn));
1206: memcpy(a, getKeyStrOffs(a, bn), pg,
1207: getKeyStrOffs(pg, r - 1), len * 2, 1);
1208: an += 1;
1209: } else {
1210: memcpy(a, bn, a, 0, an, strKeySize);
1211: }
1212: for (int i = 0; i < bn; i++) {
1213: setKeyStrOid(a, i, getKeyStrOid(b, i));
1214: setKeyStrSize(a, i, getKeyStrSize(b, i));
1215: setKeyStrOffs(a, i, getKeyStrOffs(b, i)
1216: - getSize(a));
1217: }
1218: an += bn;
1219: setnItems(a, an);
1220: setSize(a, getSize(a) + getSize(b));
1221: memcpy(a, keySpace - getSize(a), b, keySpace
1222: - getSize(b), getSize(b), 1);
1223: db.pool.unfix(a);
1224: db.pool.unfix(b);
1225: db.freePage(getKeyStrOid(pg, r - 1));
1226: return removeStrKey(pg, r - 1);
1227: }
1228: }
1229: } else if (type == ClassDescriptor.tpArrayOfByte) {
1230: Page a = db.putPage(getKeyStrOid(pg, r));
1231: int an = getnItems(a);
1232: if (r < nItems) { // exists greater page
1233: Page b = db.getPage(getKeyStrOid(pg, r + 1));
1234: int bn = getnItems(b);
1235: int merged_size = (an + bn) * strKeySize + getSize(a)
1236: + getSize(b);
1237: if (height != 1) {
1238: merged_size += getKeyStrSize(pg, r) + strKeySize
1239: * 2;
1240: }
1241: if (merged_size > keySpace) {
1242: // reallocation of nodes between pages a and b
1243: int i, j, k;
1244: db.pool.unfix(b);
1245: b = db.putPage(getKeyStrOid(pg, r + 1));
1246: int size_a = getSize(a);
1247: int size_b = getSize(b);
1248: int addSize, subSize;
1249: if (height != 1) {
1250: addSize = getKeyStrSize(pg, r);
1251: subSize = getKeyStrSize(b, 0);
1252: } else {
1253: addSize = subSize = getKeyStrSize(b, 0);
1254: }
1255: i = 0;
1256: int prevDelta = (an * strKeySize + size_a)
1257: - (bn * strKeySize + size_b);
1258: while (true) {
1259: i += 1;
1260: int delta = ((an + i) * strKeySize + size_a + addSize)
1261: - ((bn - i) * strKeySize + size_b - subSize);
1262: if (delta >= 0) {
1263: if (delta >= -prevDelta) {
1264: i -= 1;
1265: }
1266: break;
1267: }
1268: size_a += addSize;
1269: size_b -= subSize;
1270: prevDelta = delta;
1271: if (height != 1) {
1272: addSize = subSize;
1273: subSize = getKeyStrSize(b, i);
1274: } else {
1275: addSize = subSize = getKeyStrSize(b, i);
1276: }
1277: }
1278: int result = Btree.op_done;
1279: if (i > 0) {
1280: k = i;
1281: if (height != 1) {
1282: int len = getKeyStrSize(pg, r);
1283: setSize(a, getSize(a) + len);
1284: setKeyStrOffs(a, an, keySpace - getSize(a));
1285: setKeyStrSize(a, an, len);
1286: memcpy(a, getKeyStrOffs(a, an), pg,
1287: getKeyStrOffs(pg, r), len, 1);
1288: k -= 1;
1289: an += 1;
1290: setKeyStrOid(a, an + k, getKeyStrOid(b, k));
1291: setSize(b, getSize(b) - getKeyStrSize(b, k));
1292: }
1293: for (j = 0; j < k; j++) {
1294: int len = getKeyStrSize(b, j);
1295: setSize(a, getSize(a) + len);
1296: setSize(b, getSize(b) - len);
1297: setKeyStrOffs(a, an, keySpace - getSize(a));
1298: setKeyStrSize(a, an, len);
1299: setKeyStrOid(a, an, getKeyStrOid(b, j));
1300: memcpy(a, getKeyStrOffs(a, an), b,
1301: getKeyStrOffs(b, j), len, 1);
1302: an += 1;
1303: }
1304: rem.getByteArray(b, i - 1);
1305: result = replaceByteArrayKey(db, pg, r, rem,
1306: height);
1307: setnItems(a, an);
1308: setnItems(b, compactifyByteArrays(b, i));
1309: }
1310: db.pool.unfix(a);
1311: db.pool.unfix(b);
1312: return result;
1313: } else { // merge page b to a
1314: if (height != 1) {
1315: int r_len = getKeyStrSize(pg, r);
1316: setKeyStrSize(a, an, r_len);
1317: setSize(a, getSize(a) + r_len);
1318: setKeyStrOffs(a, an, keySpace - getSize(a));
1319: memcpy(a, getKeyStrOffs(a, an), pg,
1320: getKeyStrOffs(pg, r), r_len, 1);
1321: an += 1;
1322: setKeyStrOid(a, an + bn, getKeyStrOid(b, bn));
1323: }
1324: for (int i = 0; i < bn; i++, an++) {
1325: setKeyStrSize(a, an, getKeyStrSize(b, i));
1326: setKeyStrOffs(a, an, getKeyStrOffs(b, i)
1327: - getSize(a));
1328: setKeyStrOid(a, an, getKeyStrOid(b, i));
1329: }
1330: setSize(a, getSize(a) + getSize(b));
1331: setnItems(a, an);
1332: memcpy(a, keySpace - getSize(a), b, keySpace
1333: - getSize(b), getSize(b), 1);
1334: db.pool.unfix(a);
1335: db.pool.unfix(b);
1336: db.freePage(getKeyStrOid(pg, r + 1));
1337: setKeyStrOid(pg, r + 1, getKeyStrOid(pg, r));
1338: return removeByteArrayKey(pg, r);
1339: }
1340: } else { // page b is before a
1341: Page b = db.getPage(getKeyStrOid(pg, r - 1));
1342: int bn = getnItems(b);
1343: int merged_size = (an + bn) * strKeySize + getSize(a)
1344: + getSize(b);
1345: if (height != 1) {
1346: merged_size += getKeyStrSize(pg, r - 1)
1347: + strKeySize * 2;
1348: }
1349: if (merged_size > keySpace) {
1350: // reallocation of nodes between pages a and b
1351: int i, j, k, len;
1352: db.pool.unfix(b);
1353: b = db.putPage(getKeyStrOid(pg, r - 1));
1354: int size_a = getSize(a);
1355: int size_b = getSize(b);
1356: int addSize, subSize;
1357: if (height != 1) {
1358: addSize = getKeyStrSize(pg, r - 1);
1359: subSize = getKeyStrSize(b, bn - 1);
1360: } else {
1361: addSize = subSize = getKeyStrSize(b, bn - 1);
1362: }
1363: i = 0;
1364: int prevDelta = (an * strKeySize + size_a)
1365: - (bn * strKeySize + size_b);
1366: while (true) {
1367: i += 1;
1368: int delta = ((an + i) * strKeySize + size_a + addSize)
1369: - ((bn - i) * strKeySize + size_b - subSize);
1370: if (delta >= 0) {
1371: if (delta >= -prevDelta) {
1372: i -= 1;
1373: }
1374: break;
1375: }
1376: prevDelta = delta;
1377: size_a += addSize;
1378: size_b -= subSize;
1379: if (height != 1) {
1380: addSize = subSize;
1381: subSize = getKeyStrSize(b, bn - i - 1);
1382: } else {
1383: addSize = subSize = getKeyStrSize(b, bn - i
1384: - 1);
1385: }
1386: }
1387: int result = Btree.op_done;
1388: if (i > 0) {
1389: k = i;
1390: Assert.that(i < bn);
1391: if (height != 1) {
1392: setSize(b, getSize(b)
1393: - getKeyStrSize(b, bn - k));
1394: memcpy(a, i, a, 0, an + 1, strKeySize);
1395: k -= 1;
1396: setKeyStrOid(a, k, getKeyStrOid(b, bn));
1397: len = getKeyStrSize(pg, r - 1);
1398: setKeyStrSize(a, k, len);
1399: setSize(a, getSize(a) + len);
1400: setKeyStrOffs(a, k, keySpace - getSize(a));
1401: memcpy(a, getKeyStrOffs(a, k), pg,
1402: getKeyStrOffs(pg, r - 1), len, 1);
1403: } else {
1404: memcpy(a, i, a, 0, an, strKeySize);
1405: }
1406: for (j = 0; j < k; j++) {
1407: len = getKeyStrSize(b, bn - k + j);
1408: setSize(a, getSize(a) + len);
1409: setSize(b, getSize(b) - len);
1410: setKeyStrOffs(a, j, keySpace - getSize(a));
1411: setKeyStrSize(a, j, len);
1412: setKeyStrOid(a, j, getKeyStrOid(b, bn - k
1413: + j));
1414: memcpy(a, getKeyStrOffs(a, j), b,
1415: getKeyStrOffs(b, bn - k + j), len,
1416: 1);
1417: }
1418: an += i;
1419: setnItems(a, an);
1420: rem.getByteArray(b, bn - k - 1);
1421: result = replaceByteArrayKey(db, pg, r - 1,
1422: rem, height);
1423: setnItems(b, compactifyByteArrays(b, -i));
1424: }
1425: db.pool.unfix(a);
1426: db.pool.unfix(b);
1427: return result;
1428: } else { // merge page b to a
1429: if (height != 1) {
1430: memcpy(a, bn + 1, a, 0, an + 1, strKeySize);
1431: int len = getKeyStrSize(pg, r - 1);
1432: setKeyStrSize(a, bn, len);
1433: setSize(a, getSize(a) + len);
1434: setKeyStrOffs(a, bn, keySpace - getSize(a));
1435: setKeyStrOid(a, bn, getKeyStrOid(b, bn));
1436: memcpy(a, getKeyStrOffs(a, bn), pg,
1437: getKeyStrOffs(pg, r - 1), len, 1);
1438: an += 1;
1439: } else {
1440: memcpy(a, bn, a, 0, an, strKeySize);
1441: }
1442: for (int i = 0; i < bn; i++) {
1443: setKeyStrOid(a, i, getKeyStrOid(b, i));
1444: setKeyStrSize(a, i, getKeyStrSize(b, i));
1445: setKeyStrOffs(a, i, getKeyStrOffs(b, i)
1446: - getSize(a));
1447: }
1448: an += bn;
1449: setnItems(a, an);
1450: setSize(a, getSize(a) + getSize(b));
1451: memcpy(a, keySpace - getSize(a), b, keySpace
1452: - getSize(b), getSize(b), 1);
1453: db.pool.unfix(a);
1454: db.pool.unfix(b);
1455: db.freePage(getKeyStrOid(pg, r - 1));
1456: return removeByteArrayKey(pg, r - 1);
1457: }
1458: }
1459: } else { // scalar types
1460: Page a = db.putPage(getReference(pg, maxItems - r - 1));
1461: int an = getnItems(a);
1462: int itemSize = ClassDescriptor.sizeof[type];
1463: if (r < nItems) { // exists greater page
1464: Page b = db.getPage(getReference(pg, maxItems - r - 2));
1465: int bn = getnItems(b);
1466: Assert.that(bn >= an);
1467: if (height != 1) {
1468: memcpy(a, an, pg, r, 1, itemSize);
1469: an += 1;
1470: bn += 1;
1471: }
1472: int merged_size = (an + bn) * (4 + itemSize);
1473: if (merged_size > keySpace) {
1474: // reallocation of nodes between pages a and b
1475: int i = bn - ((an + bn) >> 1);
1476: db.pool.unfix(b);
1477: b = db.putPage(getReference(pg, maxItems - r - 2));
1478: memcpy(a, an, b, 0, i, itemSize);
1479: memcpy(b, 0, b, i, bn - i, itemSize);
1480: memcpy(a, maxItems - an - i, b, maxItems - i, i, 4);
1481: memcpy(b, maxItems - bn + i, b, maxItems - bn, bn
1482: - i, 4);
1483: memcpy(pg, r, a, an + i - 1, 1, itemSize);
1484: setnItems(b, getnItems(b) - i);
1485: setnItems(a, getnItems(a) + i);
1486: db.pool.unfix(a);
1487: db.pool.unfix(b);
1488: return Btree.op_done;
1489: } else { // merge page b to a
1490: memcpy(a, an, b, 0, bn, itemSize);
1491: memcpy(a, maxItems - an - bn, b, maxItems - bn, bn,
1492: 4);
1493: db.freePage(getReference(pg, maxItems - r - 2));
1494: memcpy(pg, maxItems - nItems, pg, maxItems - nItems
1495: - 1, nItems - r - 1, 4);
1496: memcpy(pg, r, pg, r + 1, nItems - r - 1, itemSize);
1497: setnItems(a, getnItems(a) + bn);
1498: setnItems(pg, nItems - 1);
1499: db.pool.unfix(a);
1500: db.pool.unfix(b);
1501: return nItems * (itemSize + 4) < keySpace / 2 ? Btree.op_underflow
1502: : Btree.op_done;
1503: }
1504: } else { // page b is before a
1505: Page b = db.getPage(getReference(pg, maxItems - r));
1506: int bn = getnItems(b);
1507: Assert.that(bn >= an);
1508: if (height != 1) {
1509: an += 1;
1510: bn += 1;
1511: }
1512: int merged_size = (an + bn) * (4 + itemSize);
1513: if (merged_size > keySpace) {
1514: // reallocation of nodes between pages a and b
1515: int i = bn - ((an + bn) >> 1);
1516: db.pool.unfix(b);
1517: b = db.putPage(getReference(pg, maxItems - r));
1518: memcpy(a, i, a, 0, an, itemSize);
1519: memcpy(a, 0, b, bn - i, i, itemSize);
1520: memcpy(a, maxItems - an - i, a, maxItems - an, an,
1521: 4);
1522: memcpy(a, maxItems - i, b, maxItems - bn, i, 4);
1523: if (height != 1) {
1524: memcpy(a, i - 1, pg, r - 1, 1, itemSize);
1525: }
1526: memcpy(pg, r - 1, b, bn - i - 1, 1, itemSize);
1527: setnItems(b, getnItems(b) - i);
1528: setnItems(a, getnItems(a) + i);
1529: db.pool.unfix(a);
1530: db.pool.unfix(b);
1531: return Btree.op_done;
1532: } else { // merge page b to a
1533: memcpy(a, bn, a, 0, an, itemSize);
1534: memcpy(a, 0, b, 0, bn, itemSize);
1535: memcpy(a, maxItems - an - bn, a, maxItems - an, an,
1536: 4);
1537: memcpy(a, maxItems - bn, b, maxItems - bn, bn, 4);
1538: if (height != 1) {
1539: memcpy(a, bn - 1, pg, r - 1, 1, itemSize);
1540: }
1541: db.freePage(getReference(pg, maxItems - r));
1542: setReference(pg, maxItems - r, getReference(pg,
1543: maxItems - r - 1));
1544: setnItems(a, getnItems(a) + bn);
1545: setnItems(pg, nItems - 1);
1546: db.pool.unfix(a);
1547: db.pool.unfix(b);
1548: return nItems * (itemSize + 4) < keySpace / 2 ? Btree.op_underflow
1549: : Btree.op_done;
1550: }
1551: }
1552: }
1553: }
1554:
1555: static int remove(StorageImpl db, int pageId, Btree tree,
1556: BtreeKey rem, int height) {
1557: Page pg = db.getPage(pageId);
1558: try {
1559: int i, n = getnItems(pg), l = 0, r = n;
1560:
1561: if (tree.type == ClassDescriptor.tpString) {
1562: while (l < r) {
1563: i = (l + r) >> 1;
1564: if (compareStr(rem.key, pg, i) > 0) {
1565: l = i + 1;
1566: } else {
1567: r = i;
1568: }
1569: }
1570: if (--height != 0) {
1571: do {
1572: switch (remove(db, getKeyStrOid(pg, r), tree,
1573: rem, height)) {
1574: case Btree.op_underflow:
1575: db.pool.unfix(pg);
1576: pg = null;
1577: pg = db.putPage(pageId);
1578: return handlePageUnderflow(db, pg, r,
1579: tree.type, rem, height);
1580: case Btree.op_done:
1581: return Btree.op_done;
1582: case Btree.op_overflow:
1583: db.pool.unfix(pg);
1584: pg = null;
1585: pg = db.putPage(pageId);
1586: return insertStrKey(db, pg, r, rem, height);
1587: }
1588: } while (++r <= n);
1589: } else {
1590: while (r < n) {
1591: if (compareStr(rem.key, pg, r) == 0) {
1592: int oid = getKeyStrOid(pg, r);
1593: if (oid == rem.oid || rem.oid == 0) {
1594: rem.oldOid = oid;
1595: db.pool.unfix(pg);
1596: pg = null;
1597: pg = db.putPage(pageId);
1598: return removeStrKey(pg, r);
1599: }
1600: } else {
1601: break;
1602: }
1603: r += 1;
1604: }
1605: }
1606: } else if (tree.type == ClassDescriptor.tpArrayOfByte) {
1607: while (l < r) {
1608: i = (l + r) >> 1;
1609: if (tree.compareByteArrays(rem.key, pg, i) > 0) {
1610: l = i + 1;
1611: } else {
1612: r = i;
1613: }
1614: }
1615: if (--height != 0) {
1616: do {
1617: switch (remove(db, getKeyStrOid(pg, r), tree,
1618: rem, height)) {
1619: case Btree.op_underflow:
1620: db.pool.unfix(pg);
1621: pg = null;
1622: pg = db.putPage(pageId);
1623: return handlePageUnderflow(db, pg, r,
1624: tree.type, rem, height);
1625: case Btree.op_done:
1626: return Btree.op_done;
1627: case Btree.op_overflow:
1628: db.pool.unfix(pg);
1629: pg = null;
1630: pg = db.putPage(pageId);
1631: return insertByteArrayKey(db, pg, r, rem,
1632: height);
1633: }
1634: } while (++r <= n);
1635: } else {
1636: while (r < n) {
1637: if (tree.compareByteArrays(rem.key, pg, r) == 0) {
1638: int oid = getKeyStrOid(pg, r);
1639: if (oid == rem.oid || rem.oid == 0) {
1640: rem.oldOid = oid;
1641: db.pool.unfix(pg);
1642: pg = null;
1643: pg = db.putPage(pageId);
1644: return removeByteArrayKey(pg, r);
1645: }
1646: } else {
1647: break;
1648: }
1649: r += 1;
1650: }
1651: }
1652: } else { // scalar types
1653: int itemSize = ClassDescriptor.sizeof[tree.type];
1654: while (l < r) {
1655: i = (l + r) >> 1;
1656: if (compare(rem.key, pg, i) > 0) {
1657: l = i + 1;
1658: } else {
1659: r = i;
1660: }
1661: }
1662: if (--height == 0) {
1663: int oid = rem.oid;
1664: while (r < n) {
1665: if (compare(rem.key, pg, r) == 0) {
1666: if (getReference(pg, maxItems - r - 1) == oid
1667: || oid == 0) {
1668: rem.oldOid = getReference(pg, maxItems
1669: - r - 1);
1670: db.pool.unfix(pg);
1671: pg = null;
1672: pg = db.putPage(pageId);
1673: memcpy(pg, r, pg, r + 1, n - r - 1,
1674: itemSize);
1675: memcpy(pg, maxItems - n + 1, pg,
1676: maxItems - n, n - r - 1, 4);
1677: setnItems(pg, --n);
1678: return n * (itemSize + 4) < keySpace / 2 ? Btree.op_underflow
1679: : Btree.op_done;
1680: }
1681: } else {
1682: break;
1683: }
1684: r += 1;
1685: }
1686: return Btree.op_not_found;
1687: }
1688: do {
1689: switch (remove(db, getReference(pg, maxItems - r
1690: - 1), tree, rem, height)) {
1691: case Btree.op_underflow:
1692: db.pool.unfix(pg);
1693: pg = null;
1694: pg = db.putPage(pageId);
1695: return handlePageUnderflow(db, pg, r,
1696: tree.type, rem, height);
1697: case Btree.op_done:
1698: return Btree.op_done;
1699: }
1700: } while (++r <= n);
1701: }
1702: return Btree.op_not_found;
1703: } finally {
1704: if (pg != null) {
1705: db.pool.unfix(pg);
1706: }
1707: }
1708: }
1709:
1710: static void purge(StorageImpl db, int pageId, int type, int height) {
1711: if (--height != 0) {
1712: Page pg = db.getPage(pageId);
1713: int n = getnItems(pg) + 1;
1714: if (type == ClassDescriptor.tpString
1715: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1716: while (--n >= 0) {
1717: purge(db, getKeyStrOid(pg, n), type, height);
1718: }
1719: } else {
1720: while (--n >= 0) {
1721: purge(db, getReference(pg, maxItems - n - 1), type,
1722: height);
1723: }
1724: }
1725: db.pool.unfix(pg);
1726: }
1727: db.freePage(pageId);
1728: }
1729:
1730: static int traverseForward(StorageImpl db, int pageId, int type,
1731: int height, IPersistent[] result, int pos) {
1732: Page pg = db.getPage(pageId);
1733: int oid;
1734: try {
1735: int i, n = getnItems(pg);
1736: if (--height != 0) {
1737: if (type == ClassDescriptor.tpString
1738: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1739: for (i = 0; i <= n; i++) {
1740: pos = traverseForward(db, getKeyStrOid(pg, i),
1741: type, height, result, pos);
1742: }
1743: } else {
1744: for (i = 0; i <= n; i++) {
1745: pos = traverseForward(db, getReference(pg,
1746: maxItems - i - 1), type, height,
1747: result, pos);
1748: }
1749: }
1750: } else {
1751: if (type == ClassDescriptor.tpString
1752: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1753: for (i = 0; i < n; i++) {
1754: oid = getKeyStrOid(pg, i);
1755: result[pos++] = db.lookupObject(oid, null);
1756: }
1757: } else { // page of scalars
1758: for (i = 0; i < n; i++) {
1759: oid = getReference(pg, maxItems - 1 - i);
1760: result[pos++] = db.lookupObject(oid, null);
1761: }
1762: }
1763: }
1764: return pos;
1765: } finally {
1766: db.pool.unfix(pg);
1767: }
1768: }
1769:
1770: static int markPage(StorageImpl db, int pageId, int type, int height) {
1771: int nPages = 1;
1772: Page pg = db.getGCPage(pageId);
1773: try {
1774: int i, n = getnItems(pg);
1775: if (--height != 0) {
1776: if (type == ClassDescriptor.tpString
1777: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1778: for (i = 0; i <= n; i++) {
1779: nPages += markPage(db, getKeyStrOid(pg, i),
1780: type, height);
1781: }
1782: } else {
1783: for (i = 0; i <= n; i++) {
1784: nPages += markPage(db, getReference(pg,
1785: maxItems - i - 1), type, height);
1786: }
1787: }
1788: } else {
1789: if (type == ClassDescriptor.tpString
1790: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1791: for (i = 0; i < n; i++) {
1792: db.markOid(getKeyStrOid(pg, i));
1793: }
1794: } else { // page of scalars
1795: for (i = 0; i < n; i++) {
1796: db.markOid(getReference(pg, maxItems - 1 - i));
1797: }
1798: }
1799: }
1800: } finally {
1801: db.pool.unfix(pg);
1802: }
1803: return nPages;
1804: }
1805:
1806: static void exportPage(StorageImpl db, XMLExporter exporter,
1807: int pageId, int type, int height)
1808: throws java.io.IOException {
1809: Page pg = db.getPage(pageId);
1810: try {
1811: int i, n = getnItems(pg);
1812: if (--height != 0) {
1813: if (type == ClassDescriptor.tpString
1814: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1815: for (i = 0; i <= n; i++) {
1816: exportPage(db, exporter, getKeyStrOid(pg, i),
1817: type, height);
1818: }
1819: } else {
1820: for (i = 0; i <= n; i++) {
1821: exportPage(db, exporter, getReference(pg,
1822: maxItems - i - 1), type, height);
1823: }
1824: }
1825: } else {
1826: if (type == ClassDescriptor.tpString
1827: || type == ClassDescriptor.tpArrayOfByte) { // page of strings
1828: for (i = 0; i < n; i++) {
1829: exporter.exportAssoc(getKeyStrOid(pg, i),
1830: pg.data, BtreePage.firstKeyOffs
1831: + BtreePage
1832: .getKeyStrOffs(pg, i),
1833: BtreePage.getKeyStrSize(pg, i), type);
1834: }
1835: } else {
1836: for (i = 0; i < n; i++) {
1837: exporter.exportAssoc(getReference(pg, maxItems
1838: - 1 - i), pg.data,
1839: BtreePage.firstKeyOffs + i
1840: * ClassDescriptor.sizeof[type],
1841: ClassDescriptor.sizeof[type], type);
1842:
1843: }
1844: }
1845: }
1846: } finally {
1847: db.pool.unfix(pg);
1848: }
1849: }
1850: }
|