persistentlistimpl.cs

Perst开源实时数据库

namespace Perst.Impl
{
    using System;
    using Perst;
    using System.Collections;
    using System.Diagnostics;
#if USE_GENERICS
    using System.Collections.Generic;
    using Link=Link<IPersistent>;
#endif


#if USE_GENERICS
    public class PersistentListImpl<T> : PersistentCollection<T>, IPersistentList<T> where T:class,IPersistent
#else
    public class PersistentListImpl : PersistentCollection, IPersistentList
#endif
    {
        internal int      nElems;
        internal ListPage root;

        [NonSerialized()]
        internal int modCount;

        internal const int nLeafPageItems = (Page.pageSize-ObjectHeader.Sizeof-8)/4;
        internal const int nIntermediatePageItems = (Page.pageSize-ObjectHeader.Sizeof-12)/8;

        internal class TreePosition 
        {
            /**
             * B-Tree page where element is located
             */
            internal ListPage page;

            /**
             * Index of first element at the page
             */
            internal int index;
        }

    
        internal class ListPage : Persistent 
        {
            internal int   nItems;
            internal Link  items;

            internal virtual IPersistent this[int i] 
            { 
                get
                {
                    return items[i];
                }
                set 
                {
                    items[i] = value;
                }
            }

            internal virtual IPersistent getPosition(TreePosition pos, int i) 
            { 
                pos.page = this;
                pos.index -= i;
                return items[i];
            }

            internal virtual IPersistent getRawPosition(TreePosition pos, int i) 
            { 
                pos.page = this;
                pos.index -= i;
                return items.GetRaw(i);
            }

            internal virtual void prune() 
            { 
                Deallocate();
            }

            internal void clear(int i, int len) 
            { 
                while (--len >= 0) 
                { 
                    items[i++] = null;
                }
            }

            internal virtual void copy(int dstOffs, ListPage src, int srcOffs, int len) 
            { 
                Array.Copy(src.items.ToRawArray(), srcOffs, items.ToRawArray(), dstOffs, len);
            }

            internal virtual int MaxItems 
            {
                get
                {
                    return nLeafPageItems;
                }
            }

            internal virtual void setItem(int i, IPersistent obj) 
            {
                items[i] = obj;
            }

            internal virtual int size() 
            {
                return nItems;
            }

            internal virtual ListPage clonePage() 
            { 
                return new ListPage(Storage);
            }

            internal ListPage() {}

            internal ListPage(Storage storage) : base(storage)
            {
                int max = MaxItems;
                items = storage.CreateLink(max);
                items.Length = max;
            }

            internal virtual void remove(int i) 
            {
                nItems -= 1;
                copy(i, this, i+1, nItems-i);
                items[nItems] = null;
                Modify();
            }

            internal virtual bool underflow() 
            {
                return nItems < MaxItems/2;
            }

            internal virtual ListPage add(int i, IPersistent obj) 
            {
                int max = MaxItems;
                Modify();
                if (nItems < max) 
                {
                    copy(i+1, this, i, nItems-i);
                    setItem(i, obj);
                    nItems += 1;
                    return null;
                } 
                else 
                {
                    ListPage b = clonePage();
                    int m = max/2;
                    if (i < m) 
                    {
                        b.copy(0, this, 0, i);
                        b.copy(i+1, this, i, m-i-1);
                        copy(0, this, m-1, max-m+1);
                        b.setItem(i, obj);
                    } 
                    else 
                    {
                        b.copy(0, this, 0, m);
                        copy(0, this, m, i-m);
                        copy(i-m+1, this, i, max-i);
                        setItem(i-m, obj);
                    }
                    clear(max-m+1, m-1);
                    nItems = max-m+1;
                    b.nItems = m;
                    return b;
                }
            }
        }
 
        internal class ListIntermediatePage : ListPage 
        {
            internal int[] nChildren;

            internal override IPersistent getPosition(TreePosition pos, int i) 
            { 
                int j;
                for (j = 0; i >= nChildren[j]; j++) 
                {
                    i -= nChildren[j];
                }
                return ((ListPage)items[j]).getPosition(pos, i);
            }

            internal override IPersistent getRawPosition(TreePosition pos, int i) 
            { 
                int j;
                for (j = 0; i >= nChildren[j]; j++) 
                {
                    i -= nChildren[j];
                }
                return ((ListPage)items[j]).getRawPosition(pos, i);
            }
            
            internal override IPersistent this[int i] 
            {
                get 
                {
                    int j;
                    for (j = 0; i >= nChildren[j]; j++) 
                    {
                        i -= nChildren[j];
                    }
                    return ((ListPage)items[j])[i];
                }
    
                set 
                {
                    int j;
                    for (j = 0; i >= nChildren[j]; j++) 
                    {
                        i -= nChildren[j];
                    }
                    ((ListPage)items[j])[i] = value;
                }
            }

            internal override ListPage add(int i, IPersistent obj) 
            {
                int j;
                for (j = 0; i >= nChildren[j]; j++) 
                {
                    i -= nChildren[j];
                }
                ListPage pg = (ListPage)items[j];
                ListPage overflow = pg.add(i, obj);
                if (overflow != null) 
                { 
                    countChildren(j, pg);
                    overflow = base.add(j, overflow);
                } 
                else 
                {
                    Modify();
                    if (nChildren[j] != int.MaxValue) 
                    { 
                        nChildren[j] += 1;
                    }
                }                
                return overflow;
            }

            internal override void remove(int i) 
            {
                int j;
                for (j = 0; i >= nChildren[j]; j++) 
                {
                    i -= nChildren[j];
                }
                ListPage pg = (ListPage)items[j];
                pg.remove(i);
                Modify();
                if (pg.underflow()) 
                { 
                    handlePageUnderflow(pg, j);
                } 
                else 
                {
                    if (nChildren[j] != int.MaxValue) 
                    { 
                        nChildren[j] -= 1;
                    }
                }
            }

            internal void countChildren(int i, ListPage pg)
            {
                if (nChildren[i] != int.MaxValue) 
                { 
                    nChildren[i] = pg.size();
                }
            }
        
            internal override void prune() 
            { 
                for (int i = 0; i < nItems; i++) 
                {
                    ((ListPage)items[i]).prune();
                }
                Deallocate();
            }

            void handlePageUnderflow(ListPage a, int r) 
            {
                int an = a.nItems;
                int max = a.MaxItems;
                if (r+1 < nItems) 
                { // exists greater page
                    ListPage b = (ListPage)items[r+1];
                    int bn = b.nItems; 
                    Debug.Assert(bn >= an);
                    if (an + bn > max) 
                    { 
                        // reallocation of nodes between pages a and b
                        int i = bn - ((an + bn) >> 1);
                        b.Modify();
                        a.copy(an, b, 0, i);
                        b.copy(0, b, i, bn-i);
                        b.clear(bn-i, i);
                        b.nItems -= i;
                        a.nItems += i;
                        nChildren[r] = a.size();
                        countChildren(r+1, b);
                    } 
                    else 
                    { // merge page b to a  
                        a.copy(an, b, 0, bn);
                        a.nItems += bn;
                        nItems -= 1;
                        nChildren[r] = nChildren[r+1];
                        copy(r+1, this, r+2, nItems-r-1);
                        countChildren(r, a);
                        items[nItems] = null;
                        b.Deallocate();
                    }
                } 
                else 
                { // page b is before a
                    ListPage b = (ListPage)items[r-1];
                    int bn = b.nItems; 
                    Debug.Assert(bn >= an);
                    b.Modify();
                    if (an + bn > max) 
                    { 
                        // reallocation of nodes between pages a and b
                        int i = bn - ((an + bn) >> 1);
                        b.Modify();
                        a.copy(i, a, 0, an);
                        a.copy(0, b, bn-i, i);
                        b.clear(bn-i, i);
                        b.nItems -= i;
                        a.nItems += i;
                        nChildren[r-1] = b.size();
                        countChildren(r, a);
                    } 
                    else 
                    { // merge page b to a
                        b.copy(bn, a, 0, an);
                        b.nItems += an;
                        nItems -= 1;
                        nChildren[r-1] = nChildren[r];
                        countChildren(r-1, b);
                        items[r] = null;
                        a.Deallocate();
                    }
                }
            }

            internal override void copy(int dstOffs, ListPage src, int srcOffs, int len) 
            { 
                base.copy(dstOffs, src, srcOffs, len);
                Array.Copy(((ListIntermediatePage)src).nChildren, srcOffs, nChildren, dstOffs, len); 
            }

            internal override int MaxItems 
            {
                get 
                {
                    return nIntermediatePageItems;
                }
            }

            internal override void setItem(int i, IPersistent obj) 
            {
                base.setItem(i, obj);
                nChildren[i] = ((ListPage)obj).size();
            }

            internal override int size() 
            {
                if (nChildren[nItems-1] == int.MaxValue) 
                { 
                    return int.MaxValue;
                } 
                else 
                { 
                    int n = 0;
                    for (int i = 0; i < nItems; i++) 
                    { 
                        n += nChildren[i];
                    }
                    return n;
                }
            }

            internal override ListPage clonePage() 
            { 
                return new ListIntermediatePage(Storage);