bitindeximpl.cs

Perst开源实时数据库

            internal static int allocate(StorageImpl db, int root, Key ins) 
            {
                int pageId = db.allocatePage();
                Page pg = db.putPage(pageId);
                setnItems(pg, 1);
                setItem(pg, 0, ins.key);
                setItem(pg, maxItems-1, ins.oid);
                setItem(pg, maxItems-2, root);
                db.pool.unfix(pg);
                return pageId;
            }
        
            static void memcpy(Page dst_pg, int dst_idx, Page src_pg, int src_idx, int len) 
            { 
                Array.Copy(src_pg.data, firstKeyOffs + src_idx*4, 
                    dst_pg.data, firstKeyOffs + dst_idx*4, 
                    len*4);
            }
        
            internal static int find(StorageImpl db, int pageId, int oid, int height)
            {
                Page pg = db.getPage(pageId);
                try 
                { 
                    int i, n = getnItems(pg), l = 0, r = n;
                    if (--height == 0) 
                    {
                        while (l < r)  
                        {
                            i = (l+r) >> 1;
                            if (oid > getItem(pg, maxItems-1-i)) 
                            { 
                                l = i+1; 
                            } 
                            else 
                            { 
                                r = i;
                            }
                        }
                        if (r < n && getItem(pg, maxItems-r-1) == oid) 
                        {
                            return getItem(pg, r);
                        }
                        throw new StorageError(StorageError.ErrorCode.KEY_NOT_FOUND);                    
                    } 
                    else 
                    { 
                        while (l < r)  
                        {
                            i = (l+r) >> 1;
                            if (oid > getItem(pg, i)) 
                            { 
                                l = i+1; 
                            } 
                            else 
                            { 
                                r = i;
                            }
                        }
                        return find(db, getItem(pg, maxItems-r-1), oid, height);
                    }
                } 
                finally 
                { 
                    if (pg != null) 
                    { 
                        db.pool.unfix(pg);
                    }
                }
            }

            internal static BtreeResult insert(StorageImpl db, int pageId, Key ins, int height)
            {
                Page pg = db.getPage(pageId);
                int l = 0, n = getnItems(pg), r = n;
                int oid = ins.oid;
                try 
                { 
                    if (--height != 0) 
                    {
                        while (l < r)  
                        {
                            int i = (l+r) >> 1;
                            if (oid > getItem(pg, i)) 
                            { 
                                l = i+1; 
                            } 
                            else 
                            { 
                                r = i;
                            }
                        }
                        Debug.Assert(l == r);
                        /* insert before e[r] */
                        BtreeResult result = insert(db, getItem(pg, maxItems-r-1), ins, height);
                        Debug.Assert(result != BtreeResult.NotFound);
                        if (result != BtreeResult.Overflow) 
                        {
                            return result;
                        }
                        n += 1;
                    } 
                    else 
                    { 
                        while (l < r)  
                        {
                            int i = (l+r) >> 1;
                            if (oid > getItem(pg,  maxItems-1-i)) 
                            { 
                                l = i+1; 
                            } 
                            else 
                            { 
                                r = i;
                            }
                        }
                        if (r < n && oid == getItem(pg,  maxItems-1-r)) 
                        { 
                            db.pool.unfix(pg);
                            pg = null;
                            pg = db.putPage(pageId);
                            setItem(pg, r, ins.key);
                            return BtreeResult.Overwrite;
                        }
                    }
                    db.pool.unfix(pg);
                    pg = null;
                    pg = db.putPage(pageId);
                    if (n < max) 
                    {
                        memcpy(pg, r+1, pg, r, n - r);
                        memcpy(pg, maxItems-n-1, pg, maxItems-n, n-r);
                        setItem(pg, r, ins.key);
                        setItem(pg, maxItems-1-r, ins.oid);
                        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);
                            memcpy(b, r+1, pg, r, m-r-1);
                            memcpy(pg, 0, pg, m-1, max-m+1);
                            memcpy(b, maxItems-r, pg, maxItems-r, r);
                            setItem(b, r, ins.key);
                            setItem(b, maxItems-1-r, ins.oid);
                            memcpy(b, maxItems-m, pg, maxItems-m+1, m-r-1);
                            memcpy(pg, maxItems-max+m-1, pg, maxItems-max, max-m+1);
                        } 
                        else 
                        {
                            memcpy(b, 0, pg, 0, m);
                            memcpy(pg, 0, pg, m, r-m);
                            memcpy(pg, r-m+1, pg, r, max-r);
                            memcpy(b, maxItems-m, pg, maxItems-m, m);
                            memcpy(pg, maxItems-r+m, pg, maxItems-r, r-m);
                            setItem(pg, r-m, ins.key);
                            setItem(pg, maxItems-1-r+m, ins.oid);
                            memcpy(pg, maxItems-max+m-1, pg, maxItems-max, max-r);
                        }
                        ins.oid = pageId;
                        if (height == 0) 
                        {
                            ins.key = getItem(b, maxItems-m);
                            setnItems(pg, max - m + 1);
                            setnItems(b, m);
                        } 
                        else 
                        {
                            ins.key = getItem(b, m-1);
                            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 handlePageUnderflow(StorageImpl db, Page pg, int r, int height)
            {
                int nItems = getnItems(pg);
                Page a = db.putPage(getItem(pg, maxItems-r-1));
                int an = getnItems(a);
                if (r < nItems) 
                { // exists greater page
                    Page b = db.getPage(getItem(pg, maxItems-r-2));
                    int bn = getnItems(b); 
                    Debug.Assert(bn >= an);
                    if (height != 1) 
                    { 
                        memcpy(a, an, pg, r, 1);
                        an += 1;
                        bn += 1;
                    }
                    if (an+bn > max) 
                    { 
                        // reallocation of nodes between pages a and b
                        int i = bn - ((an + bn) >> 1);
                        db.pool.unfix(b);
                        b = db.putPage(getItem(pg, maxItems-r-2));
                        memcpy(a, an, b, 0, i);
                        memcpy(b, 0, b, i, bn-i);
                        memcpy(a, maxItems-an-i, b, maxItems-i, i);
                        memcpy(b, maxItems-bn+i, b, maxItems-bn, bn-i);
                        if (height != 1) 
                        { 
                            memcpy(pg, r, a, an+i-1, 1);
                        } 
                        else 
                        { 
                            memcpy(pg, r, a, maxItems-an-i, 1);
                        }
                        setnItems(b, getnItems(b) - i);
                        setnItems(a, getnItems(a) + i);
                        db.pool.unfix(a);
                        db.pool.unfix(b);
                        return BtreeResult.Done;
                    } 
                    else 
                    { // merge page b to a  
                        memcpy(a, an, b, 0, bn);
                        memcpy(a, maxItems-an-bn, b, maxItems-bn, bn);
                        db.freePage(getItem(pg, maxItems-r-2));
                        memcpy(pg, maxItems-nItems, pg, maxItems-nItems-1, 
                            nItems - r - 1);
                        memcpy(pg, r, pg, r+1, nItems - r - 1);
                        setnItems(a, getnItems(a) + bn);
                        setnItems(pg, nItems - 1);
                        db.pool.unfix(a);
                        db.pool.unfix(b);
                        return nItems < max/2 ? BtreeResult.Underflow : BtreeResult.Done;
                    }
                } 
                else 
                { // page b is before a
                    Page b = db.getPage(getItem(pg, maxItems-r));
                    int bn = getnItems(b); 
                    Debug.Assert(bn >= an);
                    if (height != 1) 
                    { 
                        an += 1;
                        bn += 1;
                    }
                    if (an+bn > max) 
                    { 
                        // reallocation of nodes between pages a and b
                        int i = bn - ((an + bn) >> 1);
                        db.pool.unfix(b);
                        b = db.putPage(getItem(pg, maxItems-r));
                        memcpy(a, i, a, 0, an);
                        memcpy(a, 0, b, bn-i, i);
                        memcpy(a, maxItems-an-i, a, maxItems-an, an);
                        memcpy(a, maxItems-i, b, maxItems-bn, i);
                        if (height != 1) 
                        { 
                            memcpy(a, i-1, pg, r-1, 1);
                            memcpy(pg, r-1, b, bn-i-1, 1);
                        } 
                        else 
                        { 
                            memcpy(pg, r-1, b, maxItems-bn+i, 1);
                        }
                        setnItems(b, getnItems(b) - i);
                        setnItems(a, getnItems(a) + i);
                        db.pool.unfix(a);
                        db.pool.unfix(b);
                        return BtreeResult.Done;
                    } 
                    else 
                    { // merge page b to a
                        memcpy(a, bn, a, 0, an);
                        memcpy(a, 0, b, 0, bn);
                        memcpy(a, maxItems-an-bn, a, maxItems-an, an);
                        memcpy(a, maxItems-bn, b, maxItems-bn, bn);
                        if (height != 1) 
                        { 
                            memcpy(a, bn-1, pg, r-1, 1);
                        }
                        db.freePage(getItem(pg, maxItems-r));
                        setItem(pg, maxItems-r, getItem(pg, maxItems-r-1));
                        setnItems(a, getnItems(a) + bn);
                        setnItems(pg, nItems - 1);
                        db.pool.unfix(a);
                        db.pool.unfix(b);
                        return nItems < max/2 ? BtreeResult.Underflow : BtreeResult.Done;
                    }
                }
            }
   
            internal static BtreeResult remove(StorageImpl db, int pageId, int oid, int height)
            {
                Page pg = db.getPage(pageId);
                try 
                { 
                    int i, n = getnItems(pg), l = 0, r = n;
                    if (--height == 0) 
                    {
                        while (l < r)  
                        {
                            i = (l+r) >> 1;
                            if (oid > getItem(pg, maxItems-1-i)) 
                            { 
                                l = i+1; 
                            } 
                            else 
                            { 
                                r = i;
                            }
                        }
                        if (r < n && getItem(pg, maxItems-r-1) == oid) 
                        {
                            db.pool.unfix(pg);
                            pg = null;
                            pg = db.putPage(pageId);
                            memcpy(pg, r, pg, r+1, n - r - 1);
                            memcpy(pg, maxItems-n+1, pg, maxItems-n, n - r - 1);
                            setnItems(pg, --n);
                            return n < max/2 ? BtreeResult.Underflow : BtreeResult.Done;
                        }
                        return BtreeResult.NotFound;
                    } 
                    else 
                    { 
                        while (l < r)  
                        {
                            i = (l+r) >> 1;
                            if (oid > getItem(pg, i)) 
                            { 
                                l = i+1; 
                            } 
                            else 
                            { 
                                r = i;
                            }
                        }
                        BtreeResult result = remove(db, getItem(pg, maxItems-r-1), oid, height);
                        if (result == BtreeResult.Underflow) 
                        { 
                            db.pool.unfix(pg);
                            pg = null;
                            pg = db.putPage(pageId);
                            return handlePageUnderflow(db, pg, r, height);
                        }
                        return result;
                    }
                } 
                finally 
                { 
                    if (pg != null) 
                    { 
                        db.pool.unfix(pg);
                    }
                }
            }
        }
    }
}