btreepage.cs

Perst开源实时数据库

                                }
                            }
                            while (++l <= n);
                        }
                    }
                }
                else
                {
                    if (firstKey != null)
                    {
                        while (l < r)
                        {
                            int i = (l + r) >> 1;
                            if (compare(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 (- compare(lastKey, pg, l) >= lastKey.inclusion)
                                {
                                    return false;
                                }
                                oid = getReference(pg, maxItems - 1 - l);
                                result.Add(db.lookupObject(oid, null));
                                l += 1;
                            }
                            return true;
                        }
                        else
                        {
                            do 
                            {
                                if (!find(db, getReference(pg, maxItems - 1 - l), firstKey, lastKey, tree, height, result))
                                {
                                    return false;
                                }
                                if (l == n)
                                {
                                    return true;
                                }
                            }
                            while (compare(lastKey, pg, l++) >= 0);
                            return false;
                        }
                    }
                    if (height == 0)
                    {
                        while (l < n)
                        {
                            oid = getReference(pg, maxItems - 1 - l);
                            result.Add(db.lookupObject(oid, null));
                            l += 1;
                        }
                    }
                    else
                    {
                        do 
                        {
                            if (!find(db, getReference(pg, maxItems - 1 - l), firstKey, lastKey, tree, height, result))
                            {
                                return false;
                            }
                        }
                        while (++l <= n);
                    }
                }
            }
            finally
            {
                db.pool.unfix(pg);
            }
            return true;
        }
		
		
        static int comparePrefix(string key, Page pg, int i) 
        { 
            int alen = key.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 = key[j] - (char)Bytes.unpack2(b, offs);
                if (diff != 0) 
                { 
                    return diff;
                }
                offs += 2;
            }
            return minlen - blen;
        }

        internal static bool prefixSearch(StorageImpl db, int pageId, string key,
                                    int height, ArrayList result)
        {
            Page pg = db.getPage(pageId);
            int l = 0, n = getnItems(pg), r = n;
            int oid;
            height -= 1;
            try 
            { 
                while (l < r)  
                {
                    int i = (l+r) >> 1;
                    if (comparePrefix(key, pg, i) > 0) 
                    {
                        l = i + 1; 
                    } 
                    else 
                    { 
                        r = i;
                    }
                }
                Debug.Assert(r == l); 
                if (height == 0) 
                { 
                    while (l < n) 
                    { 
                        if (comparePrefix(key, pg, l) < 0) 
                        { 
                            return false;
                        }
                        oid = getKeyStrOid(pg, l);
                        result.Add(db.lookupObject(oid, null));
                        l += 1;
                    }
                } 
                else 
                { 
                    do 
                    {
                        if (!prefixSearch(db, getKeyStrOid(pg, l), key, height, result)) 
                        {
                            return false;
                        }
                        if (l == n) 
                        { 
                            return true;
                        }
                    } while (comparePrefix(key, pg, l++) >= 0);
                    return false;
                }
            } 
            finally 
            { 
                db.pool.unfix(pg);
            }
            return true;
        }    

        internal static int allocate(StorageImpl db, int root, ClassDescriptor.FieldType type, BtreeKey ins)
        {
            int pageId = db.allocatePage();
            Page pg = db.putPage(pageId);
            setnItems(pg, 1);
            if (type == ClassDescriptor.FieldType.tpString)
            {
                char[] sval = (char[])ins.key.oval;
                int len = sval.Length;
                setSize(pg, len * 2);
                setKeyStrOffs(pg, 0, keySpace - len * 2);
                setKeyStrSize(pg, 0, len);
                setKeyStrOid(pg, 0, ins.oid);
                setKeyStrOid(pg, 1, root);
                setKeyStrChars(pg, keySpace - len * 2, sval);
            }
            else if (type == ClassDescriptor.FieldType.tpArrayOfByte)
            {
                byte[] bval = (byte[])ins.key.oval;
                int len = bval.Length;
                setSize(pg, len);
                setKeyStrOffs(pg, 0, keySpace - len);
                setKeyStrSize(pg, 0, len);
                setKeyStrOid(pg, 0, ins.oid);
                setKeyStrOid(pg, 1, root);
                setKeyBytes(pg, keySpace - len, bval);
            }
            else
            {
                ins.pack(pg, 0);
                setReference(pg, maxItems - 2, root);
            }
            db.pool.unfix(pg);
            return pageId;
        }
		
		
        internal static void  memcpy(Page dst_pg, int dst_idx, Page src_pg, int src_idx, int len, int itemSize)
        {
            Array.Copy(src_pg.data, firstKeyOffs + src_idx * itemSize, dst_pg.data, firstKeyOffs + dst_idx * itemSize, len * itemSize);
        }
		
        internal static BtreeResult insert(StorageImpl db, int pageId, Btree tree, BtreeKey ins, int height, bool unique, bool overwrite)
        {
            Page pg = db.getPage(pageId);
            BtreeResult result;
            int l = 0, n = getnItems(pg), r = n;
            int ahead = unique ? 1 : 0;
            try
            {
                if (tree.FieldType == ClassDescriptor.FieldType.tpString)
                {
                    while (l < r)
                    {
                        int i = (l + r) >> 1;
                        if (compareStr(ins.key, pg, i) >= ahead)
                        {
                            l = i + 1;
                        }
                        else
                        {
                            r = i;
                        }
                    }
                    Debug.Assert(l == r);
                    if (--height != 0)
                    {
                        result = insert(db, getKeyStrOid(pg, r), tree, ins, height, unique, overwrite);
                        Debug.Assert(result != BtreeResult.NotFound);
                        if (result != BtreeResult.Overflow)
                        {
                            return result;
                        }
                    }
                    else if (r < n && compareStr(ins.key, pg, r) == 0)
                    {
                        if (overwrite) 
                        { 
                            db.pool.unfix(pg);
                            pg = null;
                            pg = db.putPage(pageId);
                            setKeyStrOid(pg, r, ins.oid);
                            return BtreeResult.Overwrite;
                        }
                        else if (unique) 
                        { 
                            return BtreeResult.Duplicate;
                        }
                    }
                    db.pool.unfix(pg);
                    pg = null;
                    pg = db.putPage(pageId);
                    return insertStrKey(db, pg, r, ins, height);
                }
                else if (tree.FieldType == ClassDescriptor.FieldType.tpArrayOfByte)
                {
                    while (l < r)
                    {
                        int i = (l + r) >> 1;
                        if (tree.compareByteArrays(ins.key, pg, i) >= ahead)
                        {
                            l = i + 1;
                        }
                        else
                        {
                            r = i;
                        }
                    }
                    Debug.Assert(l == r);
                    if (--height != 0)
                    {
                        result = insert(db, getKeyStrOid(pg, r), tree, ins, height, unique, overwrite);
                        Debug.Assert(result != BtreeResult.NotFound);
                        if (result != BtreeResult.Overflow)
                        {
                            return result;
                        }
                    }
                    else if (r < n && tree.compareByteArrays(ins.key, pg, r) == 0)
                    {
                        if (overwrite) 
                        { 
                            db.pool.unfix(pg);
                            pg = null;
                            pg = db.putPage(pageId);
                            setKeyStrOid(pg, r, ins.oid);
                            return BtreeResult.Overwrite;
                        }
                        else if (unique) 
                        { 
                            return BtreeResult.Duplicate;
                        }
                    }
                    db.pool.unfix(pg);
                    pg = null;
                    pg = db.putPage(pageId);
                    return insertByteArrayKey(db, pg, r, ins, height);
                }
                else
                {
                    while (l < r)
                    {
                        int i = (l + r) >> 1;
                        if (compare(ins.key, pg, i) >= ahead)
                            l = i + 1;
                        else
                            r = i;
                    }
                    Debug.Assert(l == r);
                    /* insert before e[r] */