bitindeximpl.cs

Perst开源实时数据库

namespace Perst.Impl
{
    using System;
#if USE_GENERICS
    using System.Collections.Generic;
#endif
    using System.Collections;

    using System.Diagnostics;
    using Perst;

#if USE_GENERICS
    class BitIndexImpl<T> : Btree<IPersistent,T>, BitIndex<T> where T:class,IPersistent
#else
    class BitIndexImpl : Btree, BitIndex 
#endif
    { 
    
        class Key 
        { 
            internal int key;
            internal int oid;

            internal Key(int key, int oid) 
            { 
                this.key = key;
                this.oid = oid;
            }
        }

        internal BitIndexImpl() 
        : base(ClassDescriptor.FieldType.tpInt, true)
        {
        }

#if USE_GENERICS
        public int this[T obj] 
#else
        public int this[IPersistent obj] 
#endif
        {
            get 
            {
                return Get(obj);
            }
            set 
            {
                Put(obj, value);
            }
        } 
         
#if USE_GENERICS
        public int Get(T obj) 
#else
        public int Get(IPersistent obj) 
#endif
        {
            StorageImpl db = (StorageImpl)Storage;
            if (root == 0) 
            { 
                throw new StorageError(StorageError.ErrorCode.KEY_NOT_FOUND);
            } 
#if USE_GENERICS
            return BitIndexPage.find(db, root, obj.Oid, height);
#else
            return BitIndexPage.find(db, root, obj.Oid, height);
#endif
        }
 

#if USE_GENERICS
        public void Put(T obj, int mask) 
#else
        public void Put(IPersistent obj, int mask) 
#endif
        {
            StorageImpl db = (StorageImpl)Storage;
            if (db == null) 
            {             
                throw new StorageError(StorageError.ErrorCode.DELETED_OBJECT);
            }
            if (!obj.IsPersistent()) 
            { 
                db.MakePersistent(obj);
            }
            Key ins = new Key(mask, obj.Oid);
            if (root == 0) 
            { 
                root = BitIndexPage.allocate(db, 0, ins);
                height = 1;
            } 
            else 
            { 
                BtreeResult result = BitIndexPage.insert(db, root, ins, height);
                if (result == BtreeResult.Overflow) 
                { 
                    root = BitIndexPage.allocate(db, root, ins);
                    height += 1;
                }
            }
            updateCounter += 1;
            nElems += 1;
            Modify();
        }

#if USE_GENERICS
        public override bool Remove(T obj) 
#else
        public bool Remove(IPersistent obj) 
#endif
        {
            StorageImpl db = (StorageImpl)Storage;
            if (db == null) 
            {             
                throw new StorageError(StorageError.ErrorCode.DELETED_OBJECT);
            }
            if (root == 0) 
            {
                return false;
            }
            BtreeResult result = BitIndexPage.remove(db, root, obj.Oid, height);
            if (result == BtreeResult.NotFound) 
            { 
                return false;
            }
            nElems -= 1;
            if (result == BtreeResult.Underflow) 
            { 
                Page pg = db.getPage(root);
                if (BitIndexPage.getnItems(pg) == 0) 
                {                         
                    int newRoot = 0;
                    if (height != 1) 
                    { 
                        newRoot = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1);
                    }
                    db.freePage(root);
                    root = newRoot;
                    height -= 1;
                }
                db.pool.unfix(pg);
            }
            updateCounter += 1;
            Modify();
            return true;
        }
    

#if USE_GENERICS
        public override IEnumerator<T> GetEnumerator() 
#else
        public override IEnumerator GetEnumerator() 
#endif
        {
            return GetEnumerator(0, 0);
        }

#if USE_GENERICS
        public IEnumerator<T> GetEnumerator(int setBits, int clearBits) 
#else
        public IEnumerator GetEnumerator(int setBits, int clearBits) 
#endif
        {
            return new BitIndexIterator(this, setBits, clearBits);
        }

#if USE_GENERICS
        public IEnumerable<T> Select(int setBits, int clearBits) 
#else
        public IEnumerable Select(int setBits, int clearBits) 
#endif
        {
            return new BitIndexIterator(this, setBits, clearBits);
        }
    
#if USE_GENERICS    
        class BitIndexIterator : IEnumerator<T>, IEnumerable<T>, IEnumerable, PersistentEnumerator 
        { 
            internal BitIndexIterator(BitIndexImpl<T> index, int setBits, int clearBits) 
#else
        class BitIndexIterator : IEnumerable, PersistentEnumerator
        { 
            internal BitIndexIterator(BitIndexImpl index, int setBits, int clearBits) 
#endif
            { 
                sp = 0;
                counter = index.updateCounter;
                int h = index.height;
                if (h == 0) 
                { 
                    return;
                }
                db = (StorageImpl)index.Storage;
                if (db == null) 
                {             
                    throw new StorageError(StorageError.ErrorCode.DELETED_OBJECT);
                }
                this.index = index;
                this.setBits = setBits;
                this.clearBits = clearBits;

                pageStack = new int[h];
                posStack = new int[h];
            
                Reset();
            }

            public void Reset()
            {
                sp = 0;
                int h = index.height;
                int pageId = index.root;
                while (--h >= 0) 
                { 
                    pageStack[sp] = pageId;
                    posStack[sp] = 0;
                    Page pg = db.getPage(pageId);
                    sp += 1;
                    pageId = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1);
                    db.pool.unfix(pg);
                }
            }
        
#if USE_GENERICS    
            IEnumerator IEnumerable.GetEnumerator()
            {
                return this;
            }

            public IEnumerator<T> GetEnumerator() 
#else
            public IEnumerator GetEnumerator() 
#endif
            {
                return this;
            }

#if USE_GENERICS    
            object IEnumerator.Current
            {
                get
                {
                    return getCurrent();
                }
            }

            public virtual T Current
#else
            public virtual object Current
#endif
            {
                get 
                {

#if USE_GENERICS    
                    return (T)getCurrent();
#else
                    return getCurrent();
#endif
                }
            }

            private object getCurrent()
            {
                if (sp == 0)
                {
                    throw new InvalidOperationException();
                }
                int pos = posStack[sp - 1];
                Page pg = db.getPage(pageStack[sp - 1]);
                IPersistent curr = db.lookupObject(BitIndexPage.getItem(pg, BitIndexPage.maxItems - pos), null);
                db.pool.unfix(pg);
                return curr;
            }


            public int CurrentOid 
            {
                get 
                {
                    int pos = posStack[sp - 1];
                    Page pg = db.getPage(pageStack[sp - 1]);
                    int oid = BitIndexPage.getItem(pg, BitIndexPage.maxItems - pos);
                    db.pool.unfix(pg);
                    return oid;
                }
            }

            public void Dispose() {}

            public bool MoveNext() 
            {
                if (counter != index.updateCounter) 
                { 
                    throw new InvalidOperationException("B-Tree was modified");
                }
                if (sp == 0) 
                {
                    return false;
                }
                int pos = posStack[sp-1];   
                Page pg = db.getPage(pageStack[sp-1]);
                do 
                { 
                    int end = BitIndexPage.getnItems(pg); 

                    while (pos < end) 
                    { 
                        int mask = BitIndexPage.getItem(pg, pos);
                        pos += 1;
                        if ((setBits & mask) == setBits && (clearBits & mask) == 0) 
                        { 
                            posStack[sp-1] = pos;
                            db.pool.unfix(pg);
                            return true;
                        }
                    }

                    while (--sp != 0) 
                    { 
                        db.pool.unfix(pg);
                        pos = posStack[sp-1];
                        pg = db.getPage(pageStack[sp-1]);
                        if (++pos <= BitIndexPage.getnItems(pg)) 
                        {
                            posStack[sp-1] = pos;
                            do 
                            { 
                                int pageId = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1-pos);
                                db.pool.unfix(pg);
                                pg = db.getPage(pageId);
                                pageStack[sp] = pageId;
                                posStack[sp] = pos = 0;
                            } while (++sp < pageStack.Length);
                            break;
                        }
                     }
                } while (sp != 0);

                db.pool.unfix(pg);
                return false;
            }

 
#if USE_GENERICS    
            BitIndexImpl<T> index;
#else
            BitIndexImpl    index;
#endif
            StorageImpl     db;
            int[]           pageStack;
            int[]           posStack;
            int             sp;
            int             setBits;
            int             clearBits;
            int             counter;
        }

     
        class BitIndexPage : BtreePage 
        { 
            const int max = keySpace / 8;    

            internal static int getItem(Page pg, int index) 
            { 
                return Bytes.unpack4(pg.data, firstKeyOffs + index*4);
            }
    
            internal static void setItem(Page pg, int index, int mask) 
            { 
                Bytes.pack4(pg.data, firstKeyOffs + index*4, mask);
            }