rndbtree.cs

Perst开源实时数据库

#endif
        {
            return Put(KeyBuilder.getKeyFromObject(key), obj);
        }

#if USE_GENERICS
        public virtual V Set(Key key, V obj)
        {
            return (V)insert(key, obj, true);
        }
#else
        public virtual IPersistent Set(Key key, IPersistent obj)
        {
            return insert(key, obj, true);
        }
#endif
        
#if USE_GENERICS
        public virtual V Set(K key, V obj)
#else
        public virtual IPersistent Set(object key, IPersistent obj)
#endif
        {
            return Set(KeyBuilder.getKeyFromObject(key), obj);
        }

        internal void  allocateRootPage(BtreeKey ins, int height)
        {
            Storage s = Storage;
            BtreePage newRoot = null;
            switch (type)
            {               
                case ClassDescriptor.FieldType.tpByte: 
                    newRoot = new BtreePageOfByte(s);
                    break;
                
                case ClassDescriptor.FieldType.tpSByte: 
                    newRoot = new BtreePageOfSByte(s);
                    break;
                
                case ClassDescriptor.FieldType.tpShort: 
                    newRoot = new BtreePageOfShort(s);
                    break;
                
                case ClassDescriptor.FieldType.tpUShort: 
                    newRoot = new BtreePageOfUShort(s);
                    break;
                
                case ClassDescriptor.FieldType.tpBoolean: 
                    newRoot = new BtreePageOfBoolean(s);
                    break;
                
                case ClassDescriptor.FieldType.tpInt: 
                case ClassDescriptor.FieldType.tpOid: 
                    newRoot = new BtreePageOfInt(s);
                    break;
                
                case ClassDescriptor.FieldType.tpUInt: 
                    newRoot = new BtreePageOfInt(s);
                    break;
                
                case ClassDescriptor.FieldType.tpLong: 
                    newRoot = new BtreePageOfLong(s);
                    break;
                
                case ClassDescriptor.FieldType.tpULong: 
                    newRoot = new BtreePageOfLong(s);
                    break;
                
                case ClassDescriptor.FieldType.tpFloat: 
                    newRoot = new BtreePageOfFloat(s);
                    break;
                
                case ClassDescriptor.FieldType.tpDouble: 
                    newRoot = new BtreePageOfDouble(s);
                    break;
                
                case ClassDescriptor.FieldType.tpObject: 
                    newRoot = new BtreePageOfObject(s);
                    break;
                
                case ClassDescriptor.FieldType.tpString: 
                    newRoot = new BtreePageOfString(s);
                    break;
                
                case ClassDescriptor.FieldType.tpRaw: 
                    newRoot = new BtreePageOfRaw(s);
                    break;
                
                case ClassDescriptor.FieldType.tpDecimal: 
                    newRoot = new BtreePageOfDecimal(s);
                    break;
                
                case ClassDescriptor.FieldType.tpGuid: 
                    newRoot = new BtreePageOfGuid(s);
                    break;
                
                default: 
                    Debug.Assert(false, "Invalid type");
                    break;
                
            }
            newRoot.insert(ins, 0, height);
            newRoot.items[1] = root;
            if (height != 0) 
            { 
                newRoot.countChildren(1, height);
            }
            newRoot.nItems = 1;
            root = newRoot;
        }
        
        internal IPersistent insert(Key key, IPersistent obj, bool overwrite)
        {
            BtreeKey ins = new BtreeKey(checkKey(key), obj);
            if (root == null)
            {
                allocateRootPage(ins, 0);
                height = 1;
            }
            else
            {
                OperationResult result = root.insert(ins, height, unique, overwrite);
                if (result == OperationResult.Overflow)
                {
                    allocateRootPage(ins, height);
                    height += 1;
                }
                else if (result == OperationResult.Duplicate || result == OperationResult.Overwrite)
                {
                    return ins.oldNode;
                }
            }
            updateCounter += 1;
            nElems += 1;
            Modify();
            return null;
        }
        
#if USE_GENERICS
        public virtual void  Remove(Key key, V obj)
#else
        public virtual void  Remove(Key key, IPersistent obj)
#endif
        {
            Remove(new BtreeKey(checkKey(key), obj));
        }
        
#if USE_GENERICS
        public virtual void  Remove(K key, V obj)
#else
        public virtual void  Remove(object key, IPersistent obj)
#endif
        {
            Remove(new BtreeKey(checkKey(KeyBuilder.getKeyFromObject(key)), obj));    
        }
        
        
        internal virtual void Remove(BtreeKey rem)
        {
            if (root == null)
            {
                throw new StorageError(StorageError.ErrorCode.KEY_NOT_FOUND);
            }
            OperationResult result = root.remove(rem, height);
            if (result == OperationResult.NotFound)
            {
                throw new StorageError(StorageError.ErrorCode.KEY_NOT_FOUND);
            }
            nElems -= 1;
            if (result == OperationResult.Underflow)
            {
                if (root.nItems == 0)
                {
                    BtreePage newRoot = null;
                    if (height != 1)
                    {
                        newRoot = (BtreePage) root.items[0];
                    }
                    root.Deallocate();
                    root = newRoot;
                    height -= 1;
                }
            }
            updateCounter += 1;
            Modify();
        }
        
#if USE_GENERICS
        public virtual V Remove(Key key)
#else
        public virtual IPersistent Remove(Key key)
#endif
        {
            if (!unique)
            {
                throw new StorageError(StorageError.ErrorCode.KEY_NOT_UNIQUE);
            }
            BtreeKey rk = new BtreeKey(checkKey(key), null);
            Remove(rk);
#if USE_GENERICS
            return (V)rk.oldNode;
#else
            return rk.oldNode;
#endif
        }
        
#if USE_GENERICS
        public virtual V RemoveKey(K key)
#else
        public virtual IPersistent Remove(object key)
#endif
        {
            return Remove(KeyBuilder.getKeyFromObject(key));
        }
        
#if USE_GENERICS
        public virtual V[] GetPrefix(string prefix)
#else
        public virtual IPersistent[] GetPrefix(string prefix)
#endif
        {
            return Get(new Key(prefix, true), new Key(prefix + MaxChar, false));
        }
        
        
        public virtual int Size()
        {
            return nElems;
        }
        
#if USE_GENERICS
        public override void Clear() 
#else
        public void Clear() 
#endif
        {
            if (root != null)
            {
                root.purge(height);
                root = null;
                nElems = 0;
                height = 0;
                updateCounter += 1;
                Modify();
            }
        }
        
#if USE_GENERICS
        public virtual V[] ToArray()
        {
            V[] arr = new V[nElems];
            if (root != null)
            {
                root.traverseForward(height, arr, 0);
            }
            return (V[])arr;
        }
#else
        public virtual IPersistent[] ToArray()
        {
            IPersistent[] arr = new IPersistent[nElems];
            if (root != null)
            {
                root.traverseForward(height, arr, 0);
            }
            return arr;
        }
#endif
        
        public virtual Array ToArray(Type elemType)
        {
            Array arr = Array.CreateInstance(elemType, nElems);
            if (root != null)
            {
                root.traverseForward(height, (IPersistent[])arr, 0);
            }
            return arr;
        }
        
        public override void Deallocate()
        {
            if (root != null)
            {
                root.purge(height);
            }
            base.Deallocate();
        }
        
#if USE_GENERICS        
        public V GetAt(int i)
#else
        public object GetAt(int i)
#endif
        {
            if (i < 0 || i >= nElems)
            {
                throw new IndexOutOfRangeException("Position " + i + ", index size "  + nElems);
            }            
#if USE_GENERICS        
            return (V)root.getAt(i, height);
#else
            return root.getAt(i, height);
#endif
        } 
        
        public virtual IDictionaryEnumerator GetDictionaryEnumerator() 
        { 
            return GetDictionaryEnumerator(null, null, IterationOrder.AscentOrder);
        }

#if USE_GENERICS
        public override IEnumerator<V> GetEnumerator() 
#else
        public override IEnumerator GetEnumerator() 
#endif
        { 
             return GetEnumerator(null, null, IterationOrder.AscentOrder);
        }

#if USE_GENERICS        
        class BtreeSelectionIterator : IEnumerator<V>, IEnumerable<V>, IEnumerable, PersistentEnumerator
#else
        class BtreeSelectionIterator : IEnumerable, PersistentEnumerator 
#endif
        { 
#if USE_GENERICS        
            internal BtreeSelectionIterator(RndBtree<K,V> tree, Key from, Key till, IterationOrder order) 
#else
            internal BtreeSelectionIterator(RndBtree tree, Key from, Key till, IterationOrder order) 
#endif
            { 
                this.from = from;
                this.till = till;
                this.order = order;
                this.tree = tree;
                Reset();
            }

#if USE_GENERICS        
            internal BtreeSelectionIterator(RndBtree<K,V> tree, IterationOrder order) 
#else
            internal BtreeSelectionIterator(RndBtree tree, IterationOrder order) 
#endif
            { 
                this.order = order;
                this.tree = tree;
            }

#if USE_GENERICS        
            IEnumerator IEnumerable.GetEnumerator()
            {
                return this;
            }

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

            public virtual void Reset() 
            {
                int i, l, r;
                
                sp = 0;
                counter = tree.updateCounter;
                if (tree.height == 0)
                {
                    return;
                }
                BtreePage page = tree.root;
                int h = tree.height;

                pageStack = new BtreePage[h];
                posStack = new int[h];
                
                if (order == IterationOrder.AscentOrder)
                {
                    if (from == null)
                    {
                        while (--h > 0)
                        {
                            posStack[sp] = 0;
                            pageStack[sp] = page;
                            page = (BtreePage) page.items[0];
                            sp += 1;
                        }
                        posStack[sp] = 0;
                        pageStack[sp] = page;
                        end = page.nItems;
                        sp += 1;
                    }
                    else
                    {
                        while (--h > 0)
                        {
                            pageStack[sp] = page;
                            l = 0;
                            r = page.nItems;
                            while (l < r)
                            {
                                i = (l + r) >> 1;
                                if (page.compare(from, i) >= from.inclusion)
                                {
                                    l = i + 1;
                                }
                                else
                                {
                                    r = i;
                                }
                            }
                            Debug.Assert(r == l);
                            posStack[sp] = r;
                            page = (BtreePage) page.items[r];
                            sp += 1;
                        }