rndbtree.cs

Perst开源实时数据库

                        memcpy(b, 0, b, i, bn - i);
                        memcpyData(this, r, a, an + i - 1, 1);
                        if (height != 1)
                        {
                            a.clearKeyValue(an + i - 1);
                        }
                        b.memset(bn - i, i);
                        b.nItems -= i;
                        a.nItems += i;
                        countChildren(r, height);
                        countChildren(r+1, height);
                        return OperationResult.Done;
                    }
                    else
                    {
                        // merge page b to a  
                        memcpy(a, an, b, 0, bn);
                        b.Deallocate();
                        memcpyData(this, r, this, r + 1, nItems - r - 1);
                        int nMergedChildren = nChildren[r+1];
                        memcpyItems(this, r + 1, this, r + 2, nItems - r - 1);
                        items[nItems] = null;
                        a.nItems += bn;
                        nItems -= 1;
                        nChildren[r] += nMergedChildren-1;
                        return nItems < (items.Size() >> 1) ? OperationResult.Underflow : OperationResult.Done;
                    }
                }
                else
                {
                    // page b is before a
                    BtreePage b = (BtreePage) items[r - 1];
                    int bn = b.nItems;
                    Debug.Assert(bn >= an);
                    if (height != 1)
                    {
                        an += 1;
                        bn += 1;
                    }
                    if (an + bn > items.Size())
                    {
                        // reallocation of nodes between pages a and b
                        int i = bn - ((an + bn) >> 1);
                        b.Modify();
                        memcpy(a, i, a, 0, an);
                        memcpy(a, 0, b, bn - i, i);
                        if (height != 1)
                        {
                            memcpyData(a, i - 1, this, r - 1, 1);
                        }
                        memcpyData(this, r - 1, b, bn - i - 1, 1);
                        if (height != 1)
                        {
                            b.clearKeyValue(bn - i - 1);
                        }
                        b.memset(bn - i, i);
                        b.nItems -= i;
                        a.nItems += i;
                        countChildren(r-1, height);
                        countChildren(r, height);
                        return OperationResult.Done;
                    }
                    else
                    {
                        // merge page b to a
                        memcpy(a, bn, a, 0, an);
                        memcpy(a, 0, b, 0, bn);
                        if (height != 1)
                        {
                            memcpyData(a, bn - 1, this, r - 1, 1);
                        }
                        b.Deallocate();
                        items[r - 1] = a;
                        items[nItems] = null;
                        nChildren[r-1] += nChildren[r] - 1;
                        a.nItems += bn;
                        nItems -= 1;
                        return nItems < (items.Size() >> 1) ? OperationResult.Underflow : OperationResult.Done;
                    }
                }
            }
            
            internal virtual OperationResult remove(BtreeKey rem, int height)
            {
                int i, n = nItems, l = 0, r = n;
                
                while (l < r)
                {
                    i = (l + r) >> 1;
                    if (compare(rem.key, i) > 0)
                    {
                        l = i + 1;
                    }
                    else
                    {
                        r = i;
                    }
                }
                if (--height == 0)
                {
                    IPersistent node = rem.node;
                    while (r < n)
                    {
                        if (compare(rem.key, r) == 0)
                        {
                            if (node == null || items.ContainsElement(r, node))
                            {
                                rem.oldNode = items[r];
                                Modify();
                                memcpy(this, r, this, r + 1, n - r - 1);
                                nItems = --n;
                                memset(n, 1);
                                return n < (items.Size() >> 1) ? OperationResult.Underflow : OperationResult.Done;
                            }
                        }
                        else
                        {
                            break;
                        }
                        r += 1;
                    }
                    return OperationResult.NotFound;
                }
                do 
                {
                    switch (((BtreePage) items[r]).remove(rem, height))
                    {                       
                        case OperationResult.Underflow: 
                            return handlePageUnderflow(r, rem, height);
                        
                        case OperationResult.Done: 
                            Modify();
                            nChildren[r] -= 1;
                            return OperationResult.Done;
                    }
                }
                while (++r <= n);
                
                return OperationResult.NotFound;
            }
            
            internal virtual void purge(int height)
            {
                if (--height != 0)
                {
                    int n = nItems;
                    do 
                    {
                        ((BtreePage) items[n]).purge(height);
                    }
                    while (--n >= 0);
                }
                Deallocate();
            }
            
            internal virtual int traverseForward(int height, IPersistent[] result, int pos)
            {
                int i, n = nItems;
                if (--height != 0)
                {
                    for (i = 0; i <= n; i++)
                    {
                        pos = ((BtreePage) items[i]).traverseForward(height, result, pos);
                    }
                }
                else
                {
                    for (i = 0; i < n; i++)
                    {
                        result[pos++] = items[i];
                    }
                }
                return pos;
            }
            
            internal BtreePage(Storage s, int n) : base(s)
            {
                items = s.CreateLink(n);
                items.Length = n;
                nChildren = new int[n];
            }
            
            internal BtreePage()
            {
            }
        }
        
        
        class BtreePageOfByte:BtreePage
        {
            override internal Array Data
            {
                get
                {
                    return data;
                }
                
            }
            
            protected byte[] data;
            
            const int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 1);
            
            
            internal override object getKeyValue(int i)
            {
                return data[i];
            }
            
            internal override Key getKey(int i)
            {
                return new Key(data[i]);
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfByte(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return (byte) key.ival - data[i];
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                data[i] = (byte) key.key.ival;
            }
            
            internal BtreePageOfByte(Storage s):base(s, MAX_ITEMS)
            {
                data = new byte[MAX_ITEMS];
            }
            
            internal BtreePageOfByte()
            {
            }
        }
        
        class BtreePageOfSByte:BtreePage
        {
            override internal Array Data
            {
                get
                {
                    return data;
                }
                
            }
            
            sbyte[] data;
            
            const int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 1);
            
            
            internal override object getKeyValue(int i)
            {
                return data[i];
            }
            
            internal override Key getKey(int i)
            {
                return new Key(data[i]);
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfSByte(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return (sbyte) key.ival - data[i];
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                data[i] = (sbyte) key.key.ival;
            }
            
            internal BtreePageOfSByte(Storage s):base(s, MAX_ITEMS)
            {
                data = new sbyte[MAX_ITEMS];
            }
            
            internal BtreePageOfSByte()
            {
            }
        }
        
        class BtreePageOfBoolean:BtreePageOfByte
        {
            internal override Key getKey(int i)
            {
                return new Key(data[i] != 0);
            }
            
            internal override object getKeyValue(int i)
            {
                return data[i] != 0;
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfBoolean(Storage);
            }
            
            internal BtreePageOfBoolean()
            {
            }
            
            internal BtreePageOfBoolean(Storage s):base(s)
            {
            }
        }
        
        class BtreePageOfShort:BtreePage
        {
            override internal Array Data
            {
                get
                {
                    return data;
                }
                
            }
            internal short[] data;
            
            const int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 2);
            
            
            internal override Key getKey(int i)
            {
                return new Key(data[i]);
            }
            
            internal override object getKeyValue(int i)
            {
                return data[i];
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfShort(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return (short) key.ival - data[i];
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                data[i] = (short) key.key.ival;
            }
            
            internal BtreePageOfShort(Storage s):base(s, MAX_ITEMS)
            {
                data = new short[MAX_ITEMS];
            }
            
            internal BtreePageOfShort()
            {
            }
        }
        
        class BtreePageOfUShort:BtreePage
        {
            override internal Array Data
            {
                get
                {
                    return data;
                }
                
            }
            internal ushort[] data;
            
            const int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 2);
            
            
            internal override Key getKey(int i)
            {
                return new Key(data[i]);
            }
            
            internal override object getKeyValue(int i)
            {
                return data[i];
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfUShort(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return (ushort) key.ival - data[i];
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                data[i] = (ushort) key.key.ival;
            }
            
            internal BtreePageOfUShort(Storage s):base(s, MAX_ITEMS)
            {
                data = new ushort[MAX_ITEMS];
            }
            
            internal BtreePageOfUShort()
            {
            }
        }
        
        class BtreePageOfInt:BtreePage
        {
            override internal Array Data
            {