📄 btreepage.java
字号:
if (comparePrefix(key, pg, i) > 0) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
if (height == 0) {
while (l < n) {
if (comparePrefix(key, pg, l) < 0) {
return false;
}
oid = getKeyStrOid(pg, l);
result.add(db.lookupObject(oid, null));
l += 1;
}
} else {
do {
if (!prefixSearch(db, getKeyStrOid(pg, l), key, height, result)) {
return false;
}
if (l == n) {
return true;
}
} while (comparePrefix(key, pg, l++) >= 0);
return false;
}
} finally {
db.pool.unfix(pg);
}
return true;
}
static int allocate(StorageImpl db, int root, int type, BtreeKey ins)
{
int pageId = db.allocatePage();
Page pg = db.putPage(pageId);
setnItems(pg, 1);
if (type == ClassDescriptor.tpString) {
char[] sval = (char[])ins.key.oval;
int len = sval.length;
setSize(pg, len*2);
setKeyStrOffs(pg, 0, keySpace - len*2);
setKeyStrSize(pg, 0, len);
setKeyStrOid(pg, 0, ins.oid);
setKeyStrOid(pg, 1, root);
setKeyStrChars(pg, keySpace - len*2, sval);
} else if (type == ClassDescriptor.tpArrayOfByte) {
byte[] bval = (byte[])ins.key.oval;
int len = bval.length;
setSize(pg, len);
setKeyStrOffs(pg, 0, keySpace - len);
setKeyStrSize(pg, 0, len);
setKeyStrOid(pg, 0, ins.oid);
setKeyStrOid(pg, 1, root);
setKeyBytes(pg, keySpace - len, bval);
} else {
ins.pack(pg, 0);
setReference(pg, maxItems-2, root);
}
db.pool.unfix(pg);
return pageId;
}
static void memcpy(Page dst_pg, int dst_idx, Page src_pg, int src_idx,
int len, int itemSize)
{
System.arraycopy(src_pg.data, firstKeyOffs + src_idx*itemSize,
dst_pg.data, firstKeyOffs + dst_idx*itemSize,
len*itemSize);
}
static int insert(StorageImpl db, int pageId, Btree tree, BtreeKey ins, int height,
boolean unique, boolean overwrite)
{
Page pg = db.getPage(pageId);
int result;
int l = 0, n = getnItems(pg), r = n;
int ahead = unique ? 1 : 0;
try {
if (tree.type == ClassDescriptor.tpString) {
while (l < r) {
int i = (l+r) >> 1;
if (compareStr(ins.key, pg, i) >= ahead) {
l = i+1;
} else {
r = i;
}
}
Assert.that(l == r);
if (--height != 0) {
result = insert(db, getKeyStrOid(pg, r), tree, ins, height, unique, overwrite);
Assert.that(result != Btree.op_not_found);
if (result != Btree.op_overflow) {
return result;
}
} else if (r < n && compareStr(ins.key, pg, r) == 0) {
if (overwrite) {
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
ins.oldOid = getKeyStrOid(pg, r);
setKeyStrOid(pg, r, ins.oid);
return Btree.op_overwrite;
} else if (unique) {
return Btree.op_duplicate;
}
}
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
return insertStrKey(db, pg, r, ins, height);
} else if (tree.type == ClassDescriptor.tpArrayOfByte) {
while (l < r) {
int i = (l+r) >> 1;
if (tree.compareByteArrays(ins.key, pg, i) >= ahead) {
l = i+1;
} else {
r = i;
}
}
Assert.that(l == r);
if (--height != 0) {
result = insert(db, getKeyStrOid(pg, r), tree, ins, height, unique, overwrite);
Assert.that(result != Btree.op_not_found);
if (result != Btree.op_overflow) {
return result;
}
} else if (r < n && tree.compareByteArrays(ins.key, pg, r) == 0) {
if (overwrite) {
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
ins.oldOid = getKeyStrOid(pg, r);
setKeyStrOid(pg, r, ins.oid);
return Btree.op_overwrite;
} else if (unique) {
return Btree.op_duplicate;
}
}
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
return insertByteArrayKey(db, pg, r, ins, height);
} else {
while (l < r) {
int i = (l+r) >> 1;
if (compare(ins.key, pg, i) >= ahead) l = i+1; else r = i;
}
Assert.that(l == r);
/* insert before e[r] */
if (--height != 0) {
result = insert(db, getReference(pg, maxItems-r-1), tree, ins, height, unique, overwrite);
Assert.that(result != Btree.op_not_found);
if (result != Btree.op_overflow) {
return result;
}
n += 1;
} else if (r < n && compare(ins.key, pg, r) == 0) {
if (overwrite) {
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
ins.oldOid = getReference(pg, maxItems-r-1);
setReference(pg, maxItems-r-1, ins.oid);
return Btree.op_overwrite;
} else if (unique) {
return Btree.op_duplicate;
}
}
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
int itemSize = ClassDescriptor.sizeof[tree.type];
int max = keySpace / (4 + itemSize);
if (n < max) {
memcpy(pg, r+1, pg, r, n - r, itemSize);
memcpy(pg, maxItems-n-1, pg, maxItems-n, n-r, 4);
ins.pack(pg, r);
setnItems(pg, getnItems(pg)+1);
return Btree.op_done;
} else { /* page is full then divide page */
pageId = db.allocatePage();
Page b = db.putPage(pageId);
Assert.that(n == max);
int m = max/2;
if (r < m) {
memcpy(b, 0, pg, 0, r, itemSize);
memcpy(b, r+1, pg, r, m-r-1, itemSize);
memcpy(pg, 0, pg, m-1, max-m+1, itemSize);
memcpy(b, maxItems-r, pg, maxItems-r, r, 4);
ins.pack(b, r);
memcpy(b, maxItems-m, pg, maxItems-m+1, m-r-1, 4);
memcpy(pg, maxItems-max+m-1, pg, maxItems-max, max-m+1, 4);
} else {
memcpy(b, 0, pg, 0, m, itemSize);
memcpy(pg, 0, pg, m, r-m, itemSize);
memcpy(pg, r-m+1, pg, r, max-r, itemSize);
memcpy(b, maxItems-m, pg, maxItems-m, m, 4);
memcpy(pg, maxItems-r+m, pg, maxItems-r, r-m, 4);
ins.pack(pg, r-m);
memcpy(pg, maxItems-max+m-1, pg, maxItems-max, max-r, 4);
}
ins.oid = pageId;
ins.extract(b, firstKeyOffs + (m-1)*itemSize, tree.type);
if (height == 0) {
setnItems(pg, max - m + 1);
setnItems(b, m);
} else {
setnItems(pg, max - m);
setnItems(b, m - 1);
}
db.pool.unfix(b);
return Btree.op_overflow;
}
}
} finally {
if (pg != null) {
db.pool.unfix(pg);
}
}
}
static int insertStrKey(StorageImpl db, Page pg, int r, BtreeKey ins, int height)
{
int nItems = getnItems(pg);
int size = getSize(pg);
int n = (height != 0) ? nItems + 1 : nItems;
// insert before e[r]
char[] sval = (char[])ins.key.oval;
int len = sval.length;
if (size + len*2 + (n+1)*strKeySize <= keySpace) {
memcpy(pg, r+1, pg, r, n-r, strKeySize);
size += len*2;
setKeyStrOffs(pg, r, keySpace - size);
setKeyStrSize(pg, r, len);
setKeyStrOid(pg, r, ins.oid);
setKeyStrChars(pg, keySpace - size, sval);
nItems += 1;
} else { // page is full then divide page
int pageId = db.allocatePage();
Page b = db.putPage(pageId);
int moved = 0;
int inserted = len*2 + strKeySize;
int prevDelta = (1 << 31) + 1;
for (int bn = 0, i = 0; ; bn += 1) {
int addSize, subSize;
int j = nItems - i - 1;
int keyLen = getKeyStrSize(pg, i);
if (bn == r) {
keyLen = len;
inserted = 0;
addSize = len;
if (height == 0) {
subSize = 0;
j += 1;
} else {
subSize = getKeyStrSize(pg, i);
}
} else {
addSize = subSize = keyLen;
if (height != 0) {
if (i + 1 != r) {
subSize += getKeyStrSize(pg, i+1);
j -= 1;
} else {
inserted = 0;
}
}
}
int delta = (moved + addSize*2 + (bn+1)*strKeySize)
- (j*strKeySize + size - subSize*2 + inserted);
if (delta >= -prevDelta) {
if (height == 0) {
ins.getStr(b, bn-1);
} else {
Assert.that("String fits in the B-Tree page",
moved + (bn+1)*strKeySize <= keySpace);
if (bn != r) {
ins.getStr(pg, i);
setKeyStrOid(b, bn, getKeyStrOid(pg, i));
size -= keyLen*2;
i += 1;
} else {
setKeyStrOid(b, bn, ins.oid);
}
}
nItems = compactifyStrings(pg, i);
if (bn < r || (bn == r && height == 0)) {
memcpy(pg, r-i+1, pg, r-i, n - r, strKeySize);
size += len*2;
nItems += 1;
Assert.that("String fits in the B-Tree page",
size + (n-i+1)*strKeySize <= keySpace);
setKeyStrOffs(pg, r-i, keySpace - size);
setKeyStrSize(pg, r-i, len);
setKeyStrOid(pg, r-i, ins.oid);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -