📄 btreepage.java
字号:
package org.garret.perst.impl;
import org.garret.perst.*;
class BtreePage {
static final int firstKeyOffs = 4;
static final int keySpace = Page.pageSize - firstKeyOffs;
static final int strKeySize = 8;
static final int maxItems = keySpace / 4;
static int getnItems(Page pg) {
return Bytes.unpack2(pg.data, 0);
}
static int getSize(Page pg) {
return Bytes.unpack2(pg.data, 2);
}
static int getKeyStrOid(Page pg, int index) {
return Bytes.unpack4(pg.data, firstKeyOffs + index*8);
}
static int getKeyStrSize(Page pg, int index) {
return Bytes.unpack2(pg.data, firstKeyOffs + index*8+4);
}
static int getKeyStrOffs(Page pg, int index) {
return Bytes.unpack2(pg.data, firstKeyOffs + index*8+6);
}
static int getReference(Page pg, int index) {
return Bytes.unpack4(pg.data, firstKeyOffs + index*4);
}
static void setnItems(Page pg, int nItems) {
Bytes.pack2(pg.data, 0, (short)nItems);
}
static void setSize(Page pg, int size) {
Bytes.pack2(pg.data, 2, (short)size);
}
static void setKeyStrOid(Page pg, int index, int oid) {
Bytes.pack4(pg.data, firstKeyOffs + index*8, oid);
}
static void setKeyStrSize(Page pg, int index, int size) {
Bytes.pack2(pg.data, firstKeyOffs + index*8+4, (short)size);
}
static void setKeyStrOffs(Page pg, int index, int offs) {
Bytes.pack2(pg.data, firstKeyOffs + index*8+6, (short)offs);
}
static void setKeyStrChars(Page pg, int offs, char[] str) {
int len = str.length;
for (int i = 0; i < len; i++) {
Bytes.pack2(pg.data, firstKeyOffs + offs, (short)str[i]);
offs += 2;
}
}
static void setKeyBytes(Page pg, int offs, byte[] bytes) {
System.arraycopy(bytes, 0, pg.data, firstKeyOffs + offs, bytes.length);
}
static void setReference(Page pg, int index, int oid) {
Bytes.pack4(pg.data, firstKeyOffs + index*4, oid);
}
final static int compare(Key key, Page pg, int i) {
long i8;
int i4;
float r4;
double r8;
switch (key.type) {
case Types.Boolean:
case Types.Byte:
return (byte)key.ival - pg.data[BtreePage.firstKeyOffs + i];
case Types.Short:
return (short)key.ival - Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i*2);
case Types.Char:
return (char)key.ival - (char)Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i*2);
case Types.Object:
case Types.Int:
i4 = Bytes.unpack4(pg.data, BtreePage.firstKeyOffs + i*4);
return key.ival < i4 ? -1 : key.ival == i4 ? 0 : 1;
case Types.Long:
case Types.Date:
i8 = Bytes.unpack8(pg.data, BtreePage.firstKeyOffs + i*8);
return key.lval < i8 ? -1 : key.lval == i8 ? 0 : 1;
case Types.Float:
r4 = Float.intBitsToFloat(Bytes.unpack4(pg.data,
BtreePage.firstKeyOffs + i*4));
return key.dval < r4 ? -1 : key.dval == r4 ? 0 : 1;
case Types.Double:
r8 = Double.longBitsToDouble(Bytes.unpack8(pg.data,
BtreePage.firstKeyOffs + i*8));
return key.dval < r8 ? -1 : key.dval == r8 ? 0 : 1;
}
Assert.failed("Invalid type");
return 0;
}
final static int compareStr(Key key, Page pg, int i) {
char[] chars = (char[])key.oval;
int alen = chars.length;
int blen = BtreePage.getKeyStrSize(pg, i);
int minlen = alen < blen ? alen : blen;
int offs = BtreePage.getKeyStrOffs(pg, i) + BtreePage.firstKeyOffs;
byte[] b = pg.data;
for (int j = 0; j < minlen; j++) {
int diff = chars[j] - (char)Bytes.unpack2(b, offs);
if (diff != 0) {
return diff;
}
offs += 2;
}
return alen - blen;
}
final static int comparePrefix(char[] key, Page pg, int i) {
int alen = key.length;
int blen = BtreePage.getKeyStrSize(pg, i);
int minlen = alen < blen ? alen : blen;
int offs = BtreePage.getKeyStrOffs(pg, i) + BtreePage.firstKeyOffs;
byte[] b = pg.data;
for (int j = 0; j < minlen; j++) {
int diff = key[j] - (char)Bytes.unpack2(b, offs);
if (diff != 0) {
return diff;
}
offs += 2;
}
return minlen - blen;
}
static boolean find(StorageImpl db, int pageId, Key firstKey, Key lastKey,
Btree tree, int height, ArrayList result)
{
Page pg = db.getPage(pageId);
int l = 0, n = getnItems(pg), r = n;
int oid;
height -= 1;
try {
if (tree.type == Types.String) {
if (firstKey != null) {
while (l < r) {
int i = (l+r) >> 1;
if (compareStr(firstKey, pg, i) >= firstKey.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
}
if (lastKey != null) {
if (height == 0) {
while (l < n) {
if (-compareStr(lastKey, pg, l) >= lastKey.inclusion) {
return false;
}
oid = getKeyStrOid(pg, l);
result.add(db.lookupObject(oid));
l += 1;
}
} else {
do {
if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
return false;
}
if (l == n) {
return true;
}
} while (compareStr(lastKey, pg, l++) >= 0);
return false;
}
} else {
if (height == 0) {
while (l < n) {
oid = getKeyStrOid(pg, l);
result.add(db.lookupObject(oid));
l += 1;
}
} else {
do {
if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
return false;
}
} while (++l <= n);
}
}
} else if (tree.type == Types.ArrayOfByte) {
if (firstKey != null) {
while (l < r) {
int i = (l+r) >> 1;
if (tree.compareByteArrays(firstKey, pg, i) >= firstKey.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
}
if (lastKey != null) {
if (height == 0) {
while (l < n) {
if (-tree.compareByteArrays(lastKey, pg, l) >= lastKey.inclusion) {
return false;
}
oid = getKeyStrOid(pg, l);
result.add(db.lookupObject(oid));
l += 1;
}
} else {
do {
if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
return false;
}
if (l == n) {
return true;
}
} while (tree.compareByteArrays(lastKey, pg, l++) >= 0);
return false;
}
} else {
if (height == 0) {
while (l < n) {
oid = getKeyStrOid(pg, l);
result.add(db.lookupObject(oid));
l += 1;
}
} else {
do {
if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
return false;
}
} while (++l <= n);
}
}
} else {
if (firstKey != null) {
while (l < r) {
int i = (l+r) >> 1;
if (compare(firstKey, pg, i) >= firstKey.inclusion) {
l = i+1;
} else {
r = i;
}
}
Assert.that(r == l);
}
if (lastKey != null) {
if (height == 0) {
while (l < n) {
if (-compare(lastKey, pg, l) >= lastKey.inclusion) {
return false;
}
oid = getReference(pg, maxItems-1-l);
result.add(db.lookupObject(oid));
l += 1;
}
return true;
} else {
do {
if (!find(db, getReference(pg, maxItems-1-l), firstKey, lastKey, tree, height, result)) {
return false;
}
if (l == n) {
return true;
}
} while (compare(lastKey, pg, l++) >= 0);
return false;
}
}
if (height == 0) {
while (l < n) {
oid = getReference(pg, maxItems-1-l);
result.add(db.lookupObject(oid));
l += 1;
}
} else {
do {
if (!find(db, getReference(pg, maxItems-1-l), firstKey, lastKey, tree, height, result)) {
return false;
}
} while (++l <= n);
}
}
} finally {
db.pool.unfix(pg);
}
return true;
}
static boolean prefixSearch(StorageImpl db, int pageId, char[] key,
int height, ArrayList result)
{
Page pg = db.getPage(pageId);
int l = 0, n = getnItems(pg), r = n;
int oid;
height -= 1;
try {
while (l < r) {
int i = (l+r) >> 1;
if (comparePrefix(key, pg, i) > 0) {
l = i + 1;
} else {
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -