ttreepage.cs

Perst开源实时数据库

using System;
#if USE_GENERICS
using System.Collections.Generic;
#else
using System.Collections;
#endif

namespace Perst.Impl 
{

#if USE_GENERICS
    class TtreePage<K,V> : Persistent where V:class,IPersistent  
#else
    class TtreePage : Persistent  
#endif
    { 
        const int maxItems = (Page.pageSize-ObjectHeader.Sizeof-4*5)/4;
        const int minItems = maxItems - 2; // minimal number of items in internal node

#if USE_GENERICS
        TtreePage<K,V> left;
        TtreePage<K,V> right;
        int            balance;
        int            nItems;
        V[]            item;
#else
        TtreePage      left;
        TtreePage      right;
        int            balance;
        int            nItems;
        IPersistent[]  item;
#endif

        public override bool RecursiveLoading() 
        {
            return false;
        }

        TtreePage() {}

#if USE_GENERICS
        internal TtreePage(V mbr) 
        { 
            nItems = 1;
            item = new V[maxItems];
            item[0] = mbr;
        }
#else
        internal TtreePage(IPersistent mbr) 
        { 
            nItems = 1;
            item = new IPersistent[maxItems];
            item[0] = mbr;
        }
#endif

#if USE_GENERICS
        V loadItem(int i) 
        { 
            V mbr = item[i];
            mbr.Load();
            return mbr;
        }
#else
        IPersistent loadItem(int i) 
        { 
            IPersistent mbr = item[i];
            mbr.Load();
            return mbr;
        }
#endif

#if USE_GENERICS
        internal bool find(PersistentComparator<K,V> comparator, K minValue, BoundaryKind minBoundary, K maxValue, BoundaryKind maxBoundary, List<V> selection)
#else
        internal bool find(PersistentComparator comparator, object minValue, BoundaryKind minBoundary, object maxValue, BoundaryKind maxBoundary, ArrayList selection)
#endif
        { 
            int l, r, m, n;
            Load();
            n = nItems;
            if (minBoundary != BoundaryKind.None) 
            { 
                if (-comparator.CompareMemberWithKey(loadItem(0), minValue) >= (int)minBoundary) 
                {	    
                    if (-comparator.CompareMemberWithKey(loadItem(n-1), minValue) >= (int)minBoundary) 
                    { 
                        if (right != null) 
                        { 
                            return right.find(comparator, minValue, minBoundary, maxValue, maxBoundary, selection); 
                        } 
                        return true;
                    }
                    for (l = 0, r = n; l < r;) 
                    { 
                        m = (l + r) >> 1;
                        if (-comparator.CompareMemberWithKey(loadItem(m), minValue) >= (int)minBoundary) 
                        {
                            l = m+1;
                        } 
                        else 
                        { 
                            r = m;
                        }
                    }
                    while (r < n) 
                    { 
                        if (maxBoundary != BoundaryKind.None
                            && comparator.CompareMemberWithKey(loadItem(r), maxValue) >= (int)maxBoundary)
                        { 
                            return false;
                        }
                        selection.Add(loadItem(r));
                        r += 1;
                    }
                    if (right != null) 
                    { 
                        return right.find(comparator, minValue, minBoundary, maxValue, maxBoundary, selection); 
                    } 
                    return true;	
                }
            }	
            if (left != null) 
            { 
                if (!left.find(comparator, minValue, minBoundary, maxValue, maxBoundary, selection)) 
                { 
                    return false;
                }
            }
            for (l = 0; l < n; l++) 
            { 
                if (maxBoundary != BoundaryKind.None 
                    && comparator.CompareMemberWithKey(loadItem(l), maxValue) >= (int)maxBoundary) 
                {
                    return false;
                }
                selection.Add(loadItem(l));
            }
            if (right != null) 
            { 
                return right.find(comparator, minValue, minBoundary, maxValue, maxBoundary, selection);
            }         
            return true;
        }
    
#if USE_GENERICS
        internal bool contains(PersistentComparator<K,V> comparator, V mbr)
#else
        internal bool contains(PersistentComparator comparator, IPersistent mbr)
#endif
        { 
            int l, r, m, n;
            Load();
            n = nItems;
            if (comparator.CompareMembers(loadItem(0), mbr) < 0) 
            {	    
                if (comparator.CompareMembers(loadItem(n-1), mbr) < 0) 
                { 
                    if (right != null) 
                    { 
                        return right.contains(comparator, mbr); 
                    } 
                    return false;
                }
                for (l = 0, r = n; l < r;) 
                { 
                    m = (l + r) >> 1;
                    if (comparator.CompareMembers(loadItem(m), mbr) < 0) 
                    {
                        l = m+1;
                    } 
                    else 
                    { 
                        r = m;
                    }
                }
                while (r < n) 
                { 
                    if (mbr == loadItem(r)) 
                    { 
                        return true;
                    }
                    if (comparator.CompareMembers(item[r], mbr) > 0) 
                    { 
                        return false;
                    }
                    r += 1;
                }
                if (right != null) 
                { 
                    return right.contains(comparator, mbr); 
                } 
                return false;	
            }
            if (left != null) 
            { 
                if (left.contains(comparator, mbr)) 
                { 
                    return true;
                }
            }
            for (l = 0; l < n; l++) 
            { 
                if (mbr == loadItem(l)) 
                { 
                    return true;
                }
                if (comparator.CompareMembers(item[l], mbr) > 0) 
                {
                    return false;
                }
            }
            if (right != null) 
            { 
                return right.contains(comparator, mbr);
            }         
            return false;
        }

    
        internal const int OK         = 0;
        internal const int NOT_UNIQUE = 1;
        internal const int NOT_FOUND  = 2;
        internal const int OVERFLOW   = 3;
        internal const int UNDERFLOW  = 4;

#if USE_GENERICS
        internal int insert(PersistentComparator<K,V> comparator, V mbr, bool unique, ref TtreePage<K,V> pgRef) 
        { 
            TtreePage<K,V> pg, lp, rp;
            V reinsertItem;
#else
        internal int insert(PersistentComparator comparator, IPersistent mbr, bool unique, ref TtreePage pgRef) 
        { 
            TtreePage pg, lp, rp;
            IPersistent reinsertItem;
#endif
            Load();
            int n = nItems;
            int diff = comparator.CompareMembers(mbr, loadItem(0));
            if (diff <= 0) 
            { 
                if (unique && diff == 0) 
                { 
                    return NOT_UNIQUE;
                }
                if ((left == null || diff == 0) && n != maxItems) 
                { 
                    Modify();
                    //for (int i = n; i > 0; i--) item[i] = item[i-1];
                    Array.Copy(item, 0, item, 1, n);
                    item[0] = mbr;
                    nItems += 1;
                    return OK;
                } 
                if (left == null) 
                { 
                    Modify();
#if USE_GENERICS
                    left = new TtreePage<K,V>(mbr);
#else
                    left = new TtreePage(mbr);
#endif
                } 
                else 
                {
                    pg = pgRef;
                    pgRef = left;
                    int result = left.insert(comparator, mbr, unique, ref pgRef);
                    if (result == NOT_UNIQUE) 
                    { 
                        return NOT_UNIQUE;
                    }
                    Modify();
                    left = pgRef;
                    pgRef = pg;
                    if (result == OK) return OK;
                }
                if (balance > 0) 
                { 
                    balance = 0;
                    return OK;
                } 
                else if (balance == 0) 
                { 
                    balance = -1;
                    return OVERFLOW;
                } 
                else 
                { 
                    lp = this.left;
                    lp.Load();
                    lp.Modify();
                    if (lp.balance < 0) 
                    { // single LL turn
                        this.left = lp.right;
                        lp.right = this;
                        balance = 0;
                        lp.balance = 0;
                        pgRef = lp;
                    } 
                    else 
                    { // double LR turn
                        rp = lp.right;
                        rp.Load();
                        rp.Modify();
                        lp.right = rp.left;
                        rp.left = lp;
                        this.left = rp.right;
                        rp.right = this;
                        balance = (rp.balance < 0) ? 1 : 0;
                        lp.balance = (rp.balance > 0) ? -1 : 0;
                        rp.balance = 0;
                        pgRef = rp;
                    }
                    return OK;
                }
            } 
            diff = comparator.CompareMembers(mbr, loadItem(n-1));
            if (diff >= 0) 
            { 
                if (unique && diff == 0) 
                { 
                    return NOT_UNIQUE;
                }
                if ((right == null || diff == 0) && n != maxItems) 
                { 
                    Modify();
                    item[n] = mbr;
                    nItems += 1;
                    return OK;
                }
                if (right == null) 
                { 
                    Modify();
#if USE_GENERICS
                    right = new TtreePage<K,V>(mbr);
#else
                    right = new TtreePage(mbr);
#endif
                } 
                else 
                { 
                    pg = pgRef;
                    pgRef = right;
                    int result = right.insert(comparator, mbr, unique, ref pgRef);
                    if (result == NOT_UNIQUE) 
                    { 
                        return NOT_UNIQUE;
                    }
                    Modify();
                    right = pgRef;
                    pgRef = pg;
                    if (result == OK) return OK;
                }
                if (balance < 0) 
                { 
                    balance = 0;
                    return OK;
                } 
                else if (balance == 0) 
                { 
                    balance = 1;
                    return OVERFLOW;
                } 
                else 
                { 
                    rp = this.right;
                    rp.Load();
                    rp.Modify();
                    if (rp.balance > 0) 
                    { // single RR turn
                        this.right = rp.left;