btreepage.cs

Perst开源实时数据库

                            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 BtreeResult.Overflow;
                    }
                    moved += keyLen;
                    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);
                        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?BtreeResult.Underflow:BtreeResult.Done;
        }
		
		
        internal 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;
        }
		
        internal 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;
        }
		
        internal static BtreeResult 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);
            }
            setnItems(pg, nItems - 1);
            return size + strKeySize * nItems < keySpace / 2?BtreeResult.Underflow:BtreeResult.Done;
        }
		
        internal static BtreeResult removeByteArrayKey(Page pg, int r)
        {
            int len = getKeyStrSize(pg, r);
            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);
            }
            setnItems(pg, nItems - 1);
            return size + strKeySize * nItems < keySpace / 2?BtreeResult.Underflow:BtreeResult.Done;
        }
		
        internal static BtreeResult replaceStrKey(StorageImpl db, Page pg, int r, BtreeKey ins, int height)
        {
            ins.oid = getKeyStrOid(pg, r);
            removeStrKey(pg, r);
            return insertStrKey(db, pg, r, ins, height);
        }
		
        internal static BtreeResult replaceByteArrayKey(StorageImpl db, Page pg, int r, BtreeKey ins, int height)
        {
            ins.oid = getKeyStrOid(pg, r);
            removeByteArrayKey(pg, r);
            return insertByteArrayKey(db, pg, r, ins, height);
        }
		
        internal static BtreeResult handlePageUnderflow(StorageImpl db, Page pg, int r, ClassDescriptor.FieldType type, BtreeKey rem, int height)
        {
            int nItems = getnItems(pg);
            if (type == ClassDescriptor.FieldType.tpString)
            {
                Page a = db.putPage(getKeyStrOid(pg, r));
                int an = getnItems(a);
                if (r < nItems)
                {
                    // exists greater page
                    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) * 2 + strKeySize * 2;
                    }
                    if (merged_size > keySpace)
                    {
                        // reallocation of nodes between pages a and b
                        int i, j, k;
                        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)
                        {