btreepage.cs

Perst开源实时数据库

namespace Perst.Impl
{
    using System;
    using System.Collections;
    using System.Diagnostics;
    using Perst;
	
    internal class BtreePage
    {
        internal const int firstKeyOffs = 4;
        internal const int keySpace = Page.pageSize - firstKeyOffs;
        internal const int strKeySize = 8;
        internal const int maxItems = keySpace / 4;
		
        internal static int getnItems(Page pg)
        {
            return Bytes.unpack2(pg.data, 0);
        }
        internal static int getSize(Page pg)
        {
            return Bytes.unpack2(pg.data, 2);
        }
        internal static int getKeyStrOid(Page pg, int index)
        {
            return Bytes.unpack4(pg.data, firstKeyOffs + index * 8);
        }
        internal static int getKeyStrSize(Page pg, int index)
        {
            return Bytes.unpack2(pg.data, firstKeyOffs + index * 8 + 4);
        }
        internal static int getKeyStrOffs(Page pg, int index)
        {
            return Bytes.unpack2(pg.data, firstKeyOffs + index * 8 + 6);
        }
		
        internal static int getReference(Page pg, int index)
        {
            return Bytes.unpack4(pg.data, firstKeyOffs + index * 4);
        }
		
        internal static void  setnItems(Page pg, int nItems)
        {
            Bytes.pack2(pg.data, 0, (short) nItems);
        }
        internal static void  setSize(Page pg, int size)
        {
            Bytes.pack2(pg.data, 2, (short) size);
        }
        internal static void  setKeyStrOid(Page pg, int index, int oid)
        {
            Bytes.pack4(pg.data, firstKeyOffs + index * 8, oid);
        }
        internal static void  setKeyStrSize(Page pg, int index, int size)
        {
            Bytes.pack2(pg.data, firstKeyOffs + index * 8 + 4, (short) size);
        }
        internal static void  setKeyStrOffs(Page pg, int index, int offs)
        {
            Bytes.pack2(pg.data, firstKeyOffs + index * 8 + 6, (short) offs);
        }
        internal static void  setKeyStrChars(Page pg, int offs, char[] str)
        {
            int len = str.Length;
            for (int i = 0; i < len; i++)
            {
                Bytes.pack2(pg.data, firstKeyOffs + offs, (short) str[i]);
                offs += 2;
            }
        }
        internal static void setKeyBytes(Page pg, int offs, byte[] bytes) 
        { 
            Array.Copy(bytes, 0, pg.data, firstKeyOffs + offs, bytes.Length);
        }

        internal static void  setReference(Page pg, int index, int oid)
        {
            Bytes.pack4(pg.data, firstKeyOffs + index * 4, oid);
        }
		
        internal static int compare(Key key, Page pg, int i)
        {
            long i8;
            ulong u8;
            int i4;
            uint u4;
            float r4;
            double r8;
            switch (key.type)
            {
                case ClassDescriptor.FieldType.tpSByte: 
                    return (sbyte) key.ival - (sbyte)pg.data[BtreePage.firstKeyOffs + i];
                
                case ClassDescriptor.FieldType.tpBoolean: 
                case ClassDescriptor.FieldType.tpByte: 
                    return (byte)key.ival - pg.data[BtreePage.firstKeyOffs + i];
				
                case ClassDescriptor.FieldType.tpShort: 
                    return (short) key.ival - Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i * 2);
                case ClassDescriptor.FieldType.tpUShort: 
                    return (ushort) key.ival - (ushort)Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i * 2);
				
                case ClassDescriptor.FieldType.tpChar: 
                    return (char) key.ival - (char) Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i * 2);
				
                case ClassDescriptor.FieldType.tpObject: 
                case ClassDescriptor.FieldType.tpUInt: 
                case ClassDescriptor.FieldType.tpOid: 
                case ClassDescriptor.FieldType.tpEnum: 
                    u4 = (uint)Bytes.unpack4(pg.data, BtreePage.firstKeyOffs + i * 4);
                    return (uint)key.ival < u4 ? -1 : (uint)key.ival == u4 ? 0 : 1;

                case ClassDescriptor.FieldType.tpInt: 
                    i4 = Bytes.unpack4(pg.data, BtreePage.firstKeyOffs + i * 4);
                    return key.ival < i4 ? -1 : key.ival == i4 ? 0 : 1;
				
                case ClassDescriptor.FieldType.tpLong: 
                    i8 = Bytes.unpack8(pg.data, BtreePage.firstKeyOffs + i * 8);
                    return key.lval < i8 ? -1 : key.lval == i8 ? 0 : 1;

                case ClassDescriptor.FieldType.tpDate: 
                case ClassDescriptor.FieldType.tpULong: 
                    u8 = (ulong)Bytes.unpack8(pg.data, BtreePage.firstKeyOffs + i * 8);
                    return (ulong)key.lval < u8 ? -1 : (ulong)key.lval == u8 ? 0 : 1;
				
                case ClassDescriptor.FieldType.tpFloat: 
                    r4 = Bytes.unpackF4(pg.data, BtreePage.firstKeyOffs + i * 4);
                    return key.dval < r4 ? -1 : key.dval == r4 ? 0 : 1;
				
                case ClassDescriptor.FieldType.tpDouble: 
                    r8 = Bytes.unpackF8(pg.data, BtreePage.firstKeyOffs + i * 8);
                    return key.dval < r8 ? -1 : key.dval == r8 ? 0 : 1;

                case ClassDescriptor.FieldType.tpDecimal:
                   return key.dec.CompareTo(Bytes.unpackDecimal(pg.data, BtreePage.firstKeyOffs + i*16));

                case ClassDescriptor.FieldType.tpGuid:
                    return key.guid.CompareTo(Bytes.unpackGuid(pg.data, BtreePage.firstKeyOffs + i*16));
            }
            Debug.Assert(false, "Invalid type");
            return 0;
        }
		
		
        internal static int compareStr(Key key, Page pg, int i)
        {
            char[] chars = (char[])key.oval;
            int alen = chars.Length;
            int blen = BtreePage.getKeyStrSize(pg, i);
            int minlen = alen < blen?alen:blen;
            int offs = BtreePage.getKeyStrOffs(pg, i) + BtreePage.firstKeyOffs;
            byte[] b = pg.data;
            for (int j = 0; j < minlen; j++)
            {
                int diff = chars[j] - (char) Bytes.unpack2(b, offs);
                if (diff != 0)
                {
                    return diff;
                }
                offs += 2;
            }
            return alen - blen;
        }
		
		
        internal static bool find(StorageImpl db, int pageId, Key firstKey, Key lastKey, Btree tree, int height, ArrayList result)
        {
            Page pg = db.getPage(pageId);
            int l = 0, n = getnItems(pg), r = n;
            int oid;
            height -= 1;
            try
            {
                if (tree.FieldType == ClassDescriptor.FieldType.tpString)
                {
                    if (firstKey != null)
                    {
                        while (l < r)
                        {
                            int i = (l + r) >> 1;
                            if (compareStr(firstKey, pg, i) >= firstKey.inclusion)
                            {
                                l = i + 1;
                            }
                            else
                            {
                                r = i;
                            }
                        }
                        Debug.Assert(r == l);
                    }
                    if (lastKey != null)
                    {
                        if (height == 0)
                        {
                            while (l < n)
                            {
                                if (- compareStr(lastKey, pg, l) >= lastKey.inclusion)
                                {
                                    return false;
                                }
                                oid = getKeyStrOid(pg, l);
                                result.Add(db.lookupObject(oid, null));
                                l += 1;
                            }
                        }
                        else
                        {
                            do 
                            {
                                if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result))
                                {
                                    return false;
                                }
                                if (l == n)
                                {
                                    return true;
                                }
                            }
                            while (compareStr(lastKey, pg, l++) >= 0);
                            return false;
                        }
                    }
                    else
                    {
                        if (height == 0)
                        {
                            while (l < n)
                            {
                                oid = getKeyStrOid(pg, l);
                                result.Add(db.lookupObject(oid, null));
                                l += 1;
                            }
                        }
                        else
                        {
                            do 
                            {
                                if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result))
                                {
                                    return false;
                                }
                            }
                            while (++l <= n);
                        }
                    }
                }
                else if (tree.FieldType == ClassDescriptor.FieldType.tpArrayOfByte)
                {
                    if (firstKey != null)
                    {
                        while (l < r)
                        {
                            int i = (l + r) >> 1;
                            if (tree.compareByteArrays(firstKey, pg, i) >= firstKey.inclusion)
                            {
                                l = i + 1;
                            }
                            else
                            {
                                r = i;
                            }
                        }
                        Debug.Assert(r == l);
                    }
                    if (lastKey != null)
                    {
                        if (height == 0)
                        {
                            while (l < n)
                            {
                                if (-tree.compareByteArrays(lastKey, pg, l) >= lastKey.inclusion)
                                {
                                    return false;
                                }
                                oid = getKeyStrOid(pg, l);
                                result.Add(db.lookupObject(oid, null));
                                l += 1;
                            }
                        }
                        else
                        {
                            do 
                            {
                                if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result))
                                {
                                    return false;
                                }
                                if (l == n)
                                {
                                    return true;
                                }
                            }
                            while (tree.compareByteArrays(lastKey, pg, l++) >= 0);
                            return false;
                        }
                    }
                    else
                    {
                        if (height == 0)
                        {
                            while (l < n)
                            {
                                oid = getKeyStrOid(pg, l);
                                result.Add(db.lookupObject(oid, null));
                                l += 1;
                            }
                        }
                        else
                        {
                            do 
                            {
                                if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result))
                                {
                                    return false;