btreepage.cs

Perst开源实时数据库

                    if (--height != 0)
                    {
                        result = insert(db, getReference(pg, maxItems - r - 1), tree, ins, height, unique, overwrite);
                        Debug.Assert(result != BtreeResult.NotFound);
                        if (result != BtreeResult.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);
                            setReference(pg, maxItems - r - 1, ins.oid);
                            return BtreeResult.Overwrite;
                        }
                        else if (unique) 
                        { 
                            return BtreeResult.Duplicate;
                        }
                    }
                    db.pool.unfix(pg);
                    pg = null;
                    pg = db.putPage(pageId);
                    int itemSize = ClassDescriptor.Sizeof[(int)tree.FieldType];
                    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 BtreeResult.Done;
                    }
                    else
                    {
                        /* page is full then divide page */
                        pageId = db.allocatePage();
                        Page b = db.putPage(pageId);
                        Debug.Assert(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.FieldType);
                        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 BtreeResult.Overflow;
                    }
                }
            }
            finally
            {
                if (pg != null) 
                { 
                    db.pool.unfix(pg);
                }
            }
        }
		
        internal static BtreeResult 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
                        {
                            Debug.Assert(moved + (bn + 1) * strKeySize <= keySpace, "String fits in the B-Tree page");
                            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;
                            Debug.Assert(size + (n - i + 1) * strKeySize <= keySpace, "String fits in the B-Tree page");
                            setKeyStrOffs(pg, r - i, keySpace - size);
                            setKeyStrSize(pg, r - i, len);
                            setKeyStrOid(pg, r - i, ins.oid);
                            setKeyStrChars(pg, keySpace - size, sval);
                        }
                        setnItems(b, bn);
                        setSize(b, moved);
                        setSize(pg, size);
                        setnItems(pg, nItems);
                        ins.oid = pageId;
                        db.pool.unfix(b);
                        return BtreeResult.Overflow;
                    }
                    moved += keyLen * 2;
                    prevDelta = delta;
                    Debug.Assert(moved + (bn + 1) * strKeySize <= keySpace, "String fits in the B-Tree page");
                    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?BtreeResult.Underflow:BtreeResult.Done;
        }
		
        internal static BtreeResult 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;
            // insert before e[r]
            byte[] bval = (byte[])ins.key.oval;        
            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
                        {
                            Debug.Assert(moved + (bn + 1) * strKeySize <= keySpace, "String fits in the B-Tree page");
                            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;
                            Debug.Assert(size + (n - i + 1) * strKeySize <= keySpace, "String fits in the B-Tree page");
                            setKeyStrOffs(pg, r - i, keySpace - size);
                            setKeyStrSize(pg, r - i, len);