📄 btree.java
字号:
if (++pos <= BtreePage.getnItems(pg)) {
posStack[sp-1] = pos;
do {
int pageId = BtreePage.getKeyStrOid(pg, pos);
db.pool.unfix(pg);
pg = db.getPage(pageId);
end = BtreePage.getnItems(pg);
pageStack[sp] = pageId;
posStack[sp] = pos = 0;
} while (++sp < pageStack.length);
break;
}
}
} else {
posStack[sp-1] = pos;
}
if (sp != 0 && till != null && -BtreePage.compareStr(till, pg, pos) >= till.inclusion) {
sp = 0;
}
} else { // descent order
if (--pos < 0) {
while (--sp != 0) {
db.pool.unfix(pg);
pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
if (--pos >= 0) {
posStack[sp-1] = pos;
do {
int pageId = BtreePage.getKeyStrOid(pg, pos);
db.pool.unfix(pg);
pg = db.getPage(pageId);
pageStack[sp] = pageId;
posStack[sp] = pos = BtreePage.getnItems(pg);
} while (++sp < pageStack.length);
posStack[sp-1] = --pos;
break;
}
}
} else {
posStack[sp-1] = pos;
}
if (sp != 0 && from != null && BtreePage.compareStr(from, pg, pos) >= from.inclusion) {
sp = 0;
}
}
} else if (type == ClassDescriptor.tpArrayOfByte) {
if (order == ASCENT_ORDER) {
if (++pos == end) {
while (--sp != 0) {
db.pool.unfix(pg);
pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
if (++pos <= BtreePage.getnItems(pg)) {
posStack[sp-1] = pos;
do {
int pageId = BtreePage.getKeyStrOid(pg, pos);
db.pool.unfix(pg);
pg = db.getPage(pageId);
end = BtreePage.getnItems(pg);
pageStack[sp] = pageId;
posStack[sp] = pos = 0;
} while (++sp < pageStack.length);
break;
}
}
} else {
posStack[sp-1] = pos;
}
if (sp != 0 && till != null && -compareByteArrays(till, pg, pos) >= till.inclusion) {
sp = 0;
}
} else { // descent order
if (--pos < 0) {
while (--sp != 0) {
db.pool.unfix(pg);
pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
if (--pos >= 0) {
posStack[sp-1] = pos;
do {
int pageId = BtreePage.getKeyStrOid(pg, pos);
db.pool.unfix(pg);
pg = db.getPage(pageId);
pageStack[sp] = pageId;
posStack[sp] = pos = BtreePage.getnItems(pg);
} while (++sp < pageStack.length);
posStack[sp-1] = --pos;
break;
}
}
} else {
posStack[sp-1] = pos;
}
if (sp != 0 && from != null && compareByteArrays(from, pg, pos) >= from.inclusion) {
sp = 0;
}
}
} else { // scalar type
if (order == ASCENT_ORDER) {
if (++pos == end) {
while (--sp != 0) {
db.pool.unfix(pg);
pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
if (++pos <= BtreePage.getnItems(pg)) {
posStack[sp-1] = pos;
do {
int pageId = BtreePage.getReference(pg, BtreePage.maxItems-1-pos);
db.pool.unfix(pg);
pg = db.getPage(pageId);
end = BtreePage.getnItems(pg);
pageStack[sp] = pageId;
posStack[sp] = pos = 0;
} while (++sp < pageStack.length);
break;
}
}
} else {
posStack[sp-1] = pos;
}
if (sp != 0 && till != null && -BtreePage.compare(till, pg, pos) >= till.inclusion) {
sp = 0;
}
} else { // descent order
if (--pos < 0) {
while (--sp != 0) {
db.pool.unfix(pg);
pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
if (--pos >= 0) {
posStack[sp-1] = pos;
do {
int pageId = BtreePage.getReference(pg, BtreePage.maxItems-1-pos);
db.pool.unfix(pg);
pg = db.getPage(pageId);
pageStack[sp] = pageId;
posStack[sp] = pos = BtreePage.getnItems(pg);
} while (++sp < pageStack.length);
posStack[sp-1] = --pos;
break;
}
}
} else {
posStack[sp-1] = pos;
}
if (sp != 0 && from != null && BtreePage.compare(from, pg, pos) >= from.inclusion) {
sp = 0;
}
}
}
if (db.concurrentIterator && sp != 0) {
nextKey = getCurrentKey(pg, pos);
}
db.pool.unfix(pg);
}
private void refresh() {
if (sp != 0) {
if (nextKey == null) {
reset();
} else {
if (order == ASCENT_ORDER) {
from = nextKey.key;
} else {
till = nextKey.key;
}
int next = nextKey.oid;
reset();
StorageImpl db = (StorageImpl)getStorage();
while (true) {
int pos = posStack[sp-1];
Page pg = db.getPage(pageStack[sp-1]);
int oid = type == ClassDescriptor.tpString || type == ClassDescriptor.tpArrayOfByte
? BtreePage.getKeyStrOid(pg, pos)
: BtreePage.getReference(pg, BtreePage.maxItems-1-pos);
if (oid != next) {
gotoNextItem(pg, pos);
} else {
db.pool.unfix(pg);
break;
}
}
}
}
counter = updateCounter;
}
BtreeKey getCurrentKey(Page pg, int pos) {
BtreeKey key;
switch (type) {
case ClassDescriptor.tpString:
key = new BtreeKey(null, BtreePage.getKeyStrOid(pg, pos));
key.getStr(pg, pos);
break;
case ClassDescriptor.tpArrayOfByte:
key = new BtreeKey(null, BtreePage.getKeyStrOid(pg, pos));
key.getByteArray(pg, pos);
break;
default:
key = new BtreeKey(null, BtreePage.getReference(pg, BtreePage.maxItems-1-pos));
key.extract(pg, BtreePage.firstKeyOffs + pos*ClassDescriptor.sizeof[type], type);
}
return key;
}
public void remove() {
if (currPage == 0) {
throw new NoSuchElementException();
}
StorageImpl db = (StorageImpl)getStorage();
if (!db.concurrentIterator) {
if (counter != updateCounter) {
throw new ConcurrentModificationException();
}
Page pg = db.getPage(currPage);
currKey = getCurrentKey(pg, currPos);
db.pool.unfix(pg);
if (sp != 0) {
int pos = posStack[sp-1];
pg = db.getPage(pageStack[sp-1]);
nextKey = getCurrentKey(pg, pos);
db.pool.unfix(pg);
}
// System.out.println("Deleted key=" + deletedKey.key.ival + ", next key=" + nextKey.key.ival);
}
Btree.this.removeIfExists(currKey);
refresh();
currPage = 0;
}
int[] pageStack;
int[] posStack;
int currPage;
int currPos;
int sp;
int end;
Key from;
Key till;
int order;
int counter;
BtreeKey nextKey;
BtreeKey currKey;
}
class BtreeSelectionEntryIterator extends BtreeSelectionIterator<Map.Entry<Object,T>> {
BtreeSelectionEntryIterator(Key from, Key till, int order) {
super(from, till, order);
}
protected Object getCurrent(Page pg, int pos) {
StorageImpl db = (StorageImpl)getStorage();
switch (type) {
case ClassDescriptor.tpString:
return new BtreeEntry<T>(db, unpackStrKey(pg, pos), BtreePage.getKeyStrOid(pg, pos));
case ClassDescriptor.tpArrayOfByte:
return new BtreeEntry<T>(db, unpackByteArrayKey(pg, pos), BtreePage.getKeyStrOid(pg, pos));
default:
return new BtreeEntry<T>(db, unpackKey(db, pg, pos), BtreePage.getReference(pg, BtreePage.maxItems-1-pos));
}
}
}
class BtreeEntryStartFromIterator extends BtreeSelectionEntryIterator
{
BtreeEntryStartFromIterator(int start, int order) {
super(null, null, order);
this.start = start;
reset();
}
void reset() {
super.reset();
int skip = (order == ASCENT_ORDER) ? start : nElems - start - 1;
while (--skip >= 0 && hasNext()) {
next();
}
}
int start;
}
public IterableIterator<T> iterator(Key from, Key till, int order) {
return new BtreeSelectionIterator<T>(checkKey(from), checkKey(till), order);
}
public IterableIterator<T> prefixIterator(String prefix) {
return iterator(new Key(prefix.toCharArray()),
new Key((prefix + Character.MAX_VALUE).toCharArray(), false), ASCENT_ORDER);
}
public IterableIterator<Map.Entry<Object,T>> entryIterator(Key from, Key till, int order) {
return new BtreeSelectionEntryIterator(checkKey(from), checkKey(till), order);
}
public IterableIterator<T> iterator(Object from, Object till, int order) {
return new BtreeSelectionIterator<T>(checkKey(getKeyFromObject(from)),
checkKey(getKeyFromObject(till)), order);
}
public IterableIterator<Map.Entry<Object,T>> entryIterator(Object from, Object till, int order) {
return new BtreeSelectionEntryIterator(checkKey(getKeyFromObject(from)),
checkKey(getKeyFromObject(till)), order);
}
public T getAt(int i) {
IterableIterator<Map.Entry<Object,T>> iterator;
if (i < 0 || i >= nElems) {
throw new IndexOutOfBoundsException("Position " + i + ", index size " + nElems);
}
if (i <= (nElems/2)) {
iterator = entryIterator(null, null, ASCENT_ORDER);
while (--i >= 0) {
iterator.next();
}
} else {
iterator = entryIterator(null, null, DESCENT_ORDER);
i -= nElems;
while (++i < 0) {
iterator.next();
}
}
return iterator.next().getValue();
}
public IterableIterator<Map.Entry<Object,T>> entryIterator(int start, int order) {
return new BtreeEntryStartFromIterator(start, order);
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -