📄 btree.java
字号:
if (r == 0) {
sp += 1;
gotoNextItem(pg, r);
} else {
posStack[sp++] = r-1;
db.pool.unfix(pg);
}
}
if (sp != 0 && from != null) {
Page pg = db.getPage(pageStack[sp-1]);
if (BtreePage.compareStr(from, pg, posStack[sp-1]) >= from.inclusion) {
sp = 0;
}
db.pool.unfix(pg);
}
}
} else if (type == ClassDescriptor.tpArrayOfByte) {
if (order == ASCENT_ORDER) {
if (from == null) {
while (--h >= 0) {
posStack[sp] = 0;
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
pageId = BtreePage.getKeyStrOid(pg, 0);
end = BtreePage.getnItems(pg);
db.pool.unfix(pg);
sp += 1;
}
} else {
while (--h > 0) {
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (compareByteArrays(from, pg, i) >= from.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
posStack[sp] = r;
pageId = BtreePage.getKeyStrOid(pg, r);
db.pool.unfix(pg);
sp += 1;
}
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
end = r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (compareByteArrays(from, pg, i) >= from.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
if (r == end) {
sp += 1;
gotoNextItem(pg, r-1);
} else {
posStack[sp++] = r;
db.pool.unfix(pg);
}
}
if (sp != 0 && till != null) {
Page pg = db.getPage(pageStack[sp-1]);
if (-compareByteArrays(till, pg, posStack[sp-1]) >= till.inclusion) {
sp = 0;
}
db.pool.unfix(pg);
}
} else { // descent order
if (till == null) {
while (--h > 0) {
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
posStack[sp] = BtreePage.getnItems(pg);
pageId = BtreePage.getKeyStrOid(pg, posStack[sp]);
db.pool.unfix(pg);
sp += 1;
}
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
posStack[sp++] = BtreePage.getnItems(pg)-1;
db.pool.unfix(pg);
} else {
while (--h > 0) {
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (compareByteArrays(till, pg, i) >= 1-till.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
posStack[sp] = r;
pageId = BtreePage.getKeyStrOid(pg, r);
db.pool.unfix(pg);
sp += 1;
}
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (compareByteArrays(till, pg, i) >= 1-till.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
if (r == 0) {
sp += 1;
gotoNextItem(pg, r);
} else {
posStack[sp++] = r-1;
db.pool.unfix(pg);
}
}
if (sp != 0 && from != null) {
Page pg = db.getPage(pageStack[sp-1]);
if (compareByteArrays(from, pg, posStack[sp-1]) >= from.inclusion) {
sp = 0;
}
db.pool.unfix(pg);
}
}
} else { // scalar type
if (order == ASCENT_ORDER) {
if (from == null) {
while (--h >= 0) {
posStack[sp] = 0;
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
pageId = BtreePage.getReference(pg, BtreePage.maxItems-1);
end = BtreePage.getnItems(pg);
db.pool.unfix(pg);
sp += 1;
}
} else {
while (--h > 0) {
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (BtreePage.compare(from, pg, i) >= from.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
posStack[sp] = r;
pageId = BtreePage.getReference(pg, BtreePage.maxItems-1-r);
db.pool.unfix(pg);
sp += 1;
}
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = end = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (BtreePage.compare(from, pg, i) >= from.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
if (r == end) {
sp += 1;
gotoNextItem(pg, r-1);
} else {
posStack[sp++] = r;
db.pool.unfix(pg);
}
}
if (sp != 0 && till != null) {
Page pg = db.getPage(pageStack[sp-1]);
if (-BtreePage.compare(till, pg, posStack[sp-1]) >= till.inclusion) {
sp = 0;
}
db.pool.unfix(pg);
}
} else { // descent order
if (till == null) {
while (--h > 0) {
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
posStack[sp] = BtreePage.getnItems(pg);
pageId = BtreePage.getReference(pg, BtreePage.maxItems-1-posStack[sp]);
db.pool.unfix(pg);
sp += 1;
}
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
posStack[sp++] = BtreePage.getnItems(pg)-1;
db.pool.unfix(pg);
} else {
while (--h > 0) {
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (BtreePage.compare(till, pg, i) >= 1-till.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
posStack[sp] = r;
pageId = BtreePage.getReference(pg, BtreePage.maxItems-1-r);
db.pool.unfix(pg);
sp += 1;
}
pageStack[sp] = pageId;
Page pg = db.getPage(pageId);
l = 0;
r = BtreePage.getnItems(pg);
while (l < r) {
i = (l+r) >> 1;
if (BtreePage.compare(till, pg, i) >= 1-till.inclusion) {
l = i + 1;
} else {
r = i;
}
}
Assert.that(r == l);
if (r == 0) {
sp += 1;
gotoNextItem(pg, r);
} else {
posStack[sp++] = r-1;
db.pool.unfix(pg);
}
}
if (sp != 0 && from != null) {
Page pg = db.getPage(pageStack[sp-1]);
if (BtreePage.compare(from, pg, posStack[sp-1]) >= from.inclusion) {
sp = 0;
}
db.pool.unfix(pg);
}
}
}
}
public boolean hasNext() {
if (counter != updateCounter) {
if (((StorageImpl)getStorage()).concurrentIterator) {
refresh();
} else {
throw new ConcurrentModificationException();
}
}
return sp != 0;
}
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
StorageImpl db = (StorageImpl)getStorage();
int pos = posStack[sp-1];
currPos = pos;
currPage = pageStack[sp-1];
Page pg = db.getPage(currPage);
E curr = (E)getCurrent(pg, pos);
if (db.concurrentIterator) {
currKey = getCurrentKey(pg, pos);
}
gotoNextItem(pg, pos);
return curr;
}
public int nextOid() {
if (!hasNext()) {
throw new NoSuchElementException();
}
StorageImpl db = (StorageImpl)getStorage();
int pos = posStack[sp-1];
currPos = pos;
currPage = pageStack[sp-1];
Page pg = db.getPage(currPage);
int oid = getReference(pg, pos);
if (db.concurrentIterator) {
currKey = getCurrentKey(pg, pos);
}
gotoNextItem(pg, pos);
return oid;
}
private int getReference(Page pg, int pos) {
return (type == ClassDescriptor.tpString || type == ClassDescriptor.tpArrayOfByte)
? BtreePage.getKeyStrOid(pg, pos)
: BtreePage.getReference(pg, BtreePage.maxItems-1-pos);
}
protected Object getCurrent(Page pg, int pos) {
StorageImpl db = (StorageImpl)getStorage();
return db.lookupObject(getReference(pg, pos), null);
}
protected final void gotoNextItem(Page pg, int pos)
{
StorageImpl db = (StorageImpl)getStorage();
if (type == ClassDescriptor.tpString) {
if (order == ASCENT_ORDER) {
if (++pos == end) {
while (--sp != 0) {
db.pool.unfix(pg);
pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -