btreepage.java

这个是perst-269.zip下面的SOURCECODE,和大家分享了。

                    }
                    setnItems(b, bn);
                    setSize(b, moved);
                    setSize(pg, size);
                    setnItems(pg, nItems);
                    ins.oid = pageId;
                    db.pool.unfix(b);
                    return Btree.op_overflow;
                }
                moved += keyLen*2;
                prevDelta = delta;
                Assert.that("String fits in the B-Tree page", 
                            moved + (bn+1)*strKeySize <= keySpace);
                setKeyStrSize(b, bn, keyLen);
                setKeyStrOffs(b, bn, keySpace - moved);
                if (bn == r) { 
                    setKeyStrOid(b, bn, ins.oid);
                    setKeyStrChars(b, keySpace - moved, sval);
                } else { 
                    setKeyStrOid(b, bn, getKeyStrOid(pg, i));
                    memcpy(b, keySpace - moved, pg, getKeyStrOffs(pg, i), keyLen*2, 1);
                    size -= keyLen*2;
                    i += 1;
                }
            }
        }
        setnItems(pg, nItems);
        setSize(pg, size);
        return size + strKeySize*(nItems+1) < keySpace/2 
            ? Btree.op_underflow : Btree.op_done;
    }

    static int insertByteArrayKey(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;
        byte[] bval = (byte[])ins.key.oval;
        // insert before e[r]
        int len = bval.length;
        if (size + len + (n+1)*strKeySize <= keySpace) { 
            memcpy(pg, r+1, pg, r, n-r, strKeySize);
            size += len;
            setKeyStrOffs(pg, r, keySpace - size);
            setKeyStrSize(pg, r, len);
            setKeyStrOid(pg, r, ins.oid);
            setKeyBytes(pg, keySpace - size, bval);
            nItems += 1;
        } else { // page is full then divide page
            int  pageId = db.allocatePage();
            Page b = db.putPage(pageId);
            int  moved = 0;
            int  inserted = len + 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 + (bn+1)*strKeySize) 
                    - (j*strKeySize + size - subSize + inserted);
                if (delta >= -prevDelta) {
                    if (height == 0) { 
                        ins.getByteArray(b, bn-1);
                    } else {
                        Assert.that("String fits in the B-Tree page", 
                                    moved + (bn+1)*strKeySize <= keySpace);
                        if (bn != r) { 
                            ins.getByteArray(pg, i);
                            setKeyStrOid(b, bn, getKeyStrOid(pg, i));
                            size -= keyLen;
                            i += 1;
                        } else {
                            setKeyStrOid(b, bn, ins.oid);
                        }
                    }
                    nItems = compactifyByteArrays(pg, i);             
                    if (bn < r || (bn == r && height == 0)) { 
                        memcpy(pg, r-i+1, pg, r-i, n - r, strKeySize);
                        size += len;
                        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);
                        setKeyBytes(pg, keySpace - size, bval);
                    }
                    setnItems(b, bn);
                    setSize(b, moved);
                    setSize(pg, size);
                    setnItems(pg, nItems);
                    ins.oid = pageId;
                    db.pool.unfix(b);
                    return Btree.op_overflow;
                }
                moved += keyLen;
                prevDelta = delta;
                Assert.that("String fits in the B-Tree page", 
                            moved + (bn+1)*strKeySize <= keySpace);
                setKeyStrSize(b, bn, keyLen);
                setKeyStrOffs(b, bn, keySpace - moved);
                if (bn == r) { 
                    setKeyStrOid(b, bn, ins.oid);
                    setKeyBytes(b, keySpace - moved, bval);
                } else { 
                    setKeyStrOid(b, bn, getKeyStrOid(pg, i));
                    memcpy(b, keySpace - moved, pg, getKeyStrOffs(pg, i), keyLen, 1);
                    size -= keyLen;
                    i += 1;
                }
            }
        }
        setnItems(pg, nItems);
        setSize(pg, size);
        return size + strKeySize*(nItems+1) < keySpace/2 
            ? Btree.op_underflow : Btree.op_done;
    }


    static int compactifyStrings(Page pg, int m) 
    {
        int i, j, offs, len, n = getnItems(pg);
        int[] size  = new int[keySpace/2+1];
        int[] index = new int[keySpace/2+1];
        if (m == 0) { 
            return n;
        }
        int nZeroLengthStrings = 0;
        if (m < 0) {
            m = -m;
            for (i = 0; i < n-m; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i) >>> 1;
                    size[offs + len] = len;
                    index[offs + len] = i;
                } else { 
                    nZeroLengthStrings += 1;
                }
            }   
            for (; i < n; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i) >>> 1;
                    size[offs + len] = len;
                    index[offs + len] = -1;
                }
            }
        } else { 
            for (i = 0; i < m; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i) >>> 1;
                    size[offs + len] = len;
                    index[offs + len] = -1;
                }
            }
            for (; i < n; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i) >>> 1;
                    size[offs + len] = len;
                    index[offs + len] = i - m;
                } else { 
                    nZeroLengthStrings += 1;
                }                   
                setKeyStrOid(pg, i-m, getKeyStrOid(pg, i));
                setKeyStrSize(pg, i-m, len);
            }   
            setKeyStrOid(pg, i-m, getKeyStrOid(pg, i));
        }
        int nItems = n -= m;
        n -= nZeroLengthStrings;
        for (offs = keySpace/2, i = offs; n != 0; i -= len) { 
            len = size[i];
            j = index[i];
            if (j >= 0) {
                offs -= len;
                n -= 1;
                setKeyStrOffs(pg, j, offs*2);
                if (offs != i - len) { 
                    memcpy(pg, offs, pg, i - len, len, 2);
                }
            }
        }
        return nItems;
    }
    
    static int compactifyByteArrays(Page pg, int m) 
    {
        int i, j, offs, len, n = getnItems(pg);
        int[] size  = new int[keySpace+1];
        int[] index = new int[keySpace+1];
        if (m == 0) { 
            return n;
        }
        int nZeroLengthArrays = 0;
        if (m < 0) {
            m = -m;
            for (i = 0; i < n-m; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i);
                    size[offs + len] = len;
                    index[offs + len] = i;
                } else { 
                    nZeroLengthArrays += 1;
                }
            }   
            for (; i < n; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i);
                    size[offs + len] = len;
                    index[offs + len] = -1;
                }
            }
        } else { 
            for (i = 0; i < m; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i);
                    size[offs + len] = len;
                    index[offs + len] = -1;
                }
            }
            for (; i < n; i++) { 
                len = getKeyStrSize(pg, i);
                if (len != 0) { 
                    offs = getKeyStrOffs(pg, i);
                    size[offs + len] = len;
                    index[offs + len] = i - m;
                } else { 
                    nZeroLengthArrays += 1;
                }                   
                setKeyStrOid(pg, i-m, getKeyStrOid(pg, i));
                setKeyStrSize(pg, i-m, len);
            }   
            setKeyStrOid(pg, i-m, getKeyStrOid(pg, i));
        }
        int nItems = n -= m;
        n -= nZeroLengthArrays;
        for (offs = keySpace, i = offs; n != 0; i -= len) { 
            len = size[i];
            j = index[i];
            if (j >= 0) {
                offs -= len;
                n -= 1;
                setKeyStrOffs(pg, j, offs);
                if (offs != i - len) { 
                    memcpy(pg, offs, pg, i - len, len, 1);
                }
            }
        }
        return nItems;
    }
    
    static int removeStrKey(Page pg, int r)
    {
        int len = getKeyStrSize(pg, r)*2;
        int offs = getKeyStrOffs(pg, r);
        int size = getSize(pg);
        int nItems = getnItems(pg);
        if ((nItems+1)*strKeySize >= keySpace) { 
            memcpy(pg, r, pg, r+1, nItems-r-1, strKeySize);
        } else { 
            memcpy(pg, r, pg, r+1, nItems-r, strKeySize);
        } 
        if (len != 0) { 
            memcpy(pg, keySpace - size + len, pg, keySpace - size, size - keySpace + offs, 1);
            for (int i = nItems; --i >= 0; ) { 
                if (getKeyStrOffs(pg, i) < offs) { 
                    setKeyStrOffs(pg, i, getKeyStrOffs(pg, i) + len);
                }
            }
            setSize(pg, size -= len);
        }