📄 btreepage.java
字号:
size_a += addSize;
size_b -= subSize;
prevDelta = delta;
if (height != 1) {
addSize = subSize;
subSize = getKeyStrSize(b, i);
} else {
addSize = subSize = getKeyStrSize(b, i);
}
}
int result = Btree.op_done;
if (i > 0) {
k = i;
if (height != 1) {
int len = getKeyStrSize(pg, r);
setSize(a, getSize(a) + len);
setKeyStrOffs(a, an, keySpace - getSize(a));
setKeyStrSize(a, an, len);
memcpy(a, getKeyStrOffs(a, an),
pg, getKeyStrOffs(pg, r), len, 1);
k -= 1;
an += 1;
setKeyStrOid(a, an+k, getKeyStrOid(b, k));
setSize(b, getSize(b) - getKeyStrSize(b, k));
}
for (j = 0; j < k; j++) {
int len = getKeyStrSize(b, j);
setSize(a, getSize(a) + len);
setSize(b, getSize(b) - len);
setKeyStrOffs(a, an, keySpace - getSize(a));
setKeyStrSize(a, an, len);
setKeyStrOid(a, an, getKeyStrOid(b, j));
memcpy(a, getKeyStrOffs(a, an),
b, getKeyStrOffs(b, j), len, 1);
an += 1;
}
rem.getByteArray(b, i-1);
result = replaceByteArrayKey(db, pg, r, rem, height);
setnItems(a, an);
setnItems(b, compactifyByteArrays(b, i));
}
db.pool.unfix(a);
db.pool.unfix(b);
return result;
} else { // merge page b to a
if (height != 1) {
int r_len = getKeyStrSize(pg, r);
setKeyStrSize(a, an, r_len);
setSize(a, getSize(a) + r_len);
setKeyStrOffs(a, an, keySpace - getSize(a));
memcpy(a, getKeyStrOffs(a, an),
pg, getKeyStrOffs(pg, r), r_len, 1);
an += 1;
setKeyStrOid(a, an+bn, getKeyStrOid(b, bn));
}
for (int i = 0; i < bn; i++, an++) {
setKeyStrSize(a, an, getKeyStrSize(b, i));
setKeyStrOffs(a, an, getKeyStrOffs(b, i) - getSize(a));
setKeyStrOid(a, an, getKeyStrOid(b, i));
}
setSize(a, getSize(a) + getSize(b));
setnItems(a, an);
memcpy(a, keySpace - getSize(a), b, keySpace - getSize(b), getSize(b), 1);
db.pool.unfix(a);
db.pool.unfix(b);
db.freePage(getKeyStrOid(pg, r+1));
setKeyStrOid(pg, r+1, getKeyStrOid(pg, r));
return removeByteArrayKey(pg, r);
}
} else { // page b is before a
Page b = db.getPage(getKeyStrOid(pg, r-1));
int bn = getnItems(b);
int merged_size = (an+bn)*strKeySize + getSize(a) + getSize(b);
if (height != 1) {
merged_size += getKeyStrSize(pg, r-1) + strKeySize*2;
}
if (merged_size > keySpace) {
// reallocation of nodes between pages a and b
int i, j, k, len;
db.pool.unfix(b);
b = db.putPage(getKeyStrOid(pg, r-1));
int size_a = getSize(a);
int size_b = getSize(b);
int addSize, subSize;
if (height != 1) {
addSize = getKeyStrSize(pg, r-1);
subSize = getKeyStrSize(b, bn-1);
} else {
addSize = subSize = getKeyStrSize(b, bn-1);
}
i = 0;
int prevDelta = (an*strKeySize + size_a) - (bn*strKeySize + size_b);
while (true) {
i += 1;
int delta = ((an+i)*strKeySize + size_a + addSize)
- ((bn-i)*strKeySize + size_b - subSize);
if (delta >= 0) {
if (delta >= -prevDelta) {
i -= 1;
}
break;
}
prevDelta = delta;
size_a += addSize;
size_b -= subSize;
if (height != 1) {
addSize = subSize;
subSize = getKeyStrSize(b, bn-i-1);
} else {
addSize = subSize = getKeyStrSize(b, bn-i-1);
}
}
int result = Btree.op_done;
if (i > 0) {
k = i;
Assert.that(i < bn);
if (height != 1) {
setSize(b, getSize(b) - getKeyStrSize(b, bn-k));
memcpy(a, i, a, 0, an+1, strKeySize);
k -= 1;
setKeyStrOid(a, k, getKeyStrOid(b, bn));
len = getKeyStrSize(pg, r-1);
setKeyStrSize(a, k, len);
setSize(a, getSize(a) + len);
setKeyStrOffs(a, k, keySpace - getSize(a));
memcpy(a, getKeyStrOffs(a, k),
pg, getKeyStrOffs(pg, r-1), len, 1);
} else {
memcpy(a, i, a, 0, an, strKeySize);
}
for (j = 0; j < k; j++) {
len = getKeyStrSize(b, bn-k+j);
setSize(a, getSize(a) + len);
setSize(b, getSize(b) - len);
setKeyStrOffs(a, j, keySpace - getSize(a));
setKeyStrSize(a, j, len);
setKeyStrOid(a, j, getKeyStrOid(b, bn-k+j));
memcpy(a, getKeyStrOffs(a, j),
b, getKeyStrOffs(b, bn-k+j), len, 1);
}
an += i;
setnItems(a, an);
rem.getByteArray(b, bn-k-1);
result = replaceByteArrayKey(db, pg, r-1, rem, height);
setnItems(b, compactifyByteArrays(b, -i));
}
db.pool.unfix(a);
db.pool.unfix(b);
return result;
} else { // merge page b to a
if (height != 1) {
memcpy(a, bn + 1, a, 0, an+1, strKeySize);
int len = getKeyStrSize(pg, r-1);
setKeyStrSize(a, bn, len);
setSize(a, getSize(a) + len);
setKeyStrOffs(a, bn, keySpace - getSize(a));
setKeyStrOid(a, bn, getKeyStrOid(b, bn));
memcpy(a, getKeyStrOffs(a, bn),
pg, getKeyStrOffs(pg, r-1), len, 1);
an += 1;
} else {
memcpy(a, bn, a, 0, an, strKeySize);
}
for (int i = 0; i < bn; i++) {
setKeyStrOid(a, i, getKeyStrOid(b, i));
setKeyStrSize(a, i, getKeyStrSize(b, i));
setKeyStrOffs(a, i, getKeyStrOffs(b, i) - getSize(a));
}
an += bn;
setnItems(a, an);
setSize(a, getSize(a) + getSize(b));
memcpy(a, keySpace - getSize(a), b, keySpace - getSize(b), getSize(b), 1);
db.pool.unfix(a);
db.pool.unfix(b);
db.freePage(getKeyStrOid(pg, r-1));
return removeByteArrayKey(pg, r-1);
}
}
} else { // scalar types
Page a = db.putPage(getReference(pg, maxItems-r-1));
int an = getnItems(a);
int itemSize = ClassDescriptor.sizeof[type];
if (r < nItems) { // exists greater page
Page b = db.getPage(getReference(pg, maxItems-r-2));
int bn = getnItems(b);
Assert.that(bn >= an);
if (height != 1) {
memcpy(a, an, pg, r, 1, itemSize);
an += 1;
bn += 1;
}
int merged_size = (an+bn)*(4 + itemSize);
if (merged_size > keySpace) {
// reallocation of nodes between pages a and b
int i = bn - ((an + bn) >> 1);
db.pool.unfix(b);
b = db.putPage(getReference(pg, maxItems-r-2));
memcpy(a, an, b, 0, i, itemSize);
memcpy(b, 0, b, i, bn-i, itemSize);
memcpy(a, maxItems-an-i, b, maxItems-i, i, 4);
memcpy(b, maxItems-bn+i, b, maxItems-bn, bn-i, 4);
memcpy(pg, r, a, an+i-1, 1, itemSize);
setnItems(b, getnItems(b) - i);
setnItems(a, getnItems(a) + i);
db.pool.unfix(a);
db.pool.unfix(b);
return Btree.op_done;
} else { // merge page b to a
memcpy(a, an, b, 0, bn, itemSize);
memcpy(a, maxItems-an-bn, b, maxItems-bn, bn, 4);
db.freePage(getReference(pg, maxItems-r-2));
memcpy(pg, maxItems-nItems, pg, maxItems-nItems-1,
nItems - r - 1, 4);
memcpy(pg, r, pg, r+1, nItems - r - 1, itemSize);
setnItems(a, getnItems(a) + bn);
setnItems(pg, nItems - 1);
db.pool.unfix(a);
db.pool.unfix(b);
return nItems*(itemSize + 4) < keySpace/2
? Btree.op_underflow : Btree.op_done;
}
} else { // page b is before a
Page b = db.getPage(getReference(pg, maxItems-r));
int bn = getnItems(b);
Assert.that(bn >= an);
if (height != 1) {
an += 1;
bn += 1;
}
int merged_size = (an+bn)*(4 + itemSize);
if (merged_size > keySpace) {
// reallocation of nodes between pages a and b
int i = bn - ((an + bn) >> 1);
db.pool.unfix(b);
b = db.putPage(getReference(pg, maxItems-r));
memcpy(a, i, a, 0, an, itemSize);
memcpy(a, 0, b, bn-i, i, itemSize);
memcpy(a, maxItems-an-i, a, maxItems-an, an, 4);
memcpy(a, maxItems-i, b, maxItems-bn, i, 4);
if (height != 1) {
memcpy(a, i-1, pg, r-1, 1, itemSize);
}
memcpy(pg, r-1, b, bn-i-1, 1, itemSize);
setnItems(b, getnItems(b) - i);
setnItems(a, getnItems(a) + i);
db.pool.unfix(a);
db.pool.unfix(b);
return Btree.op_done;
} else { // merge page b to a
memcpy(a, bn, a, 0, an, itemSize);
memcpy(a, 0, b, 0, bn, itemSize);
memcpy(a, maxItems-an-bn, a, maxItems-an, an, 4);
memcpy(a, maxItems-bn, b, maxItems-bn, bn, 4);
if (height != 1) {
memcpy(a, bn-1, pg, r-1, 1, itemSize);
}
db.freePage(getReference(pg, maxItems-r));
setReference(pg, maxItems-r, getReference(pg, maxItems-r-1));
setnItems(a, getnItems(a) + bn);
setnItems(pg, nItems - 1);
db.pool.unfix(a);
db.pool.unfix(b);
return nItems*(itemSize + 4) < keySpace/2
? Btree.op_underflow : Btree.op_done;
}
}
}
}
static int remove(StorageImpl db, int pageId, Btree tree, BtreeKey rem, int height)
{
Page pg = db.getPage(pageId);
try {
int i, n = getnItems(pg), l = 0, r = n;
if (tree.type == ClassDescriptor.tpString) {
while (l < r) {
i = (l+r) >> 1;
if (compareStr(rem.key, pg, i) > 0) {
l = i+1;
} else {
r = i;
}
}
if (--height != 0) {
do {
switch (remove(db, getKeyStrOid(pg, r), tree, rem, height)) {
case Btree.op_underflow:
db.pool.unfix(pg);
pg = null;
pg = db.putPage(pageId);
return handlePageUnderflow(db, pg, r, tree.type, rem, height);
case Btree.op_done:
return Btree.op_done;
case Btree.op_overflow:
db.pool.unfix(pg);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -