btree.cs

Perst开源实时数据库

     
        protected Key checkKey(Key key) 
        {
            if (key != null) 
            { 
                if (key.type != type)
                {
                    throw new StorageError(StorageError.ErrorCode.INCOMPATIBLE_KEY_TYPE);
                }
                if ((type == ClassDescriptor.FieldType.tpObject 
                     || type == ClassDescriptor.FieldType.tpOid) 
                    && key.ival == 0 && key.oval != null)
                {
                    IPersistent obj = (IPersistent)key.oval;
                    Storage.MakePersistent(obj);
                    key = new Key(obj, key.inclusion != 0);
                }
                if (type == ClassDescriptor.FieldType.tpString && key.oval is string) 
                {
                    key = new Key(((string)key.oval).ToCharArray(), key.inclusion != 0);
                }
            }
            return key;
        }

#if USE_GENERICS
        public virtual V Get(Key key)
        {
            key = checkKey(key);
            if (root != 0)
            {
                ArrayList list = new ArrayList();
                BtreePage.find((StorageImpl) Storage, root, key, key, this, height, list);
                if (list.Count > 1)
                {
                    throw new StorageError(StorageError.ErrorCode.KEY_NOT_UNIQUE);
                }
                else if (list.Count == 0)
                {
                    return default(V);
                }
                else
                {
                    return (V) list[0];
                }
            }
            return default(V);
        }
#else
        public virtual IPersistent Get(Key key)
        {
            key = checkKey(key);
            if (root != 0)
            {
                ArrayList list = new ArrayList();
                BtreePage.find((StorageImpl) Storage, root, key, key, this, height, list);
                if (list.Count > 1)
                {
                    throw new StorageError(StorageError.ErrorCode.KEY_NOT_UNIQUE);
                }
                else if (list.Count == 0)
                {
                    return null;
                }
                else
                {
                    return (IPersistent) list[0];
                }
            }
            return null;
        }
#endif

#if USE_GENERICS
        public virtual V Get(K key) 
#else
        public virtual IPersistent Get(object key) 
#endif
        {
            return Get(KeyBuilder.getKeyFromObject(key));
        }

#if USE_GENERICS
        internal static V[] emptySelection = new V[0];
        
        public virtual V[] Get(Key from, Key till)
#else
        internal static IPersistent[] emptySelection = new IPersistent[0];
		
        public virtual IPersistent[] Get(Key from, Key till)
#endif
        {
            if (root != 0)
            {
                ArrayList list = new ArrayList();
                BtreePage.find((StorageImpl) Storage, root, checkKey(from), checkKey(till), this, height, list);
                if (list.Count != 0)
                {
#if USE_GENERICS
                    return (V[]) list.ToArray(typeof(V));
#else
                    return (IPersistent[]) list.ToArray(typeof(IPersistent));
#endif
                }
            }
            return emptySelection;
        }
		
#if USE_GENERICS
        public V[] PrefixSearch(string key) 
#else
        public IPersistent[] PrefixSearch(string key) 
#endif
        { 
            if (ClassDescriptor.FieldType.tpString != type) 
            { 
                throw new StorageError(StorageError.ErrorCode.INCOMPATIBLE_KEY_TYPE);
            }
            if (root != 0) 
            { 
                ArrayList list = new ArrayList();
                BtreePage.prefixSearch((StorageImpl)Storage, root, key, height, list);
                if (list.Count != 0) 
                { 
#if USE_GENERICS
                    return (V[]) list.ToArray(typeof(V));
#else
                    return (IPersistent[]) list.ToArray(typeof(IPersistent));
#endif
                }
            }
            return emptySelection;
        }

#if USE_GENERICS
        public virtual V[] Get(K from, K till)
#else
        public virtual IPersistent[] Get(object from, object till)
#endif
        {
            return Get(KeyBuilder.getKeyFromObject(from), KeyBuilder.getKeyFromObject(till));
        }
            
#if USE_GENERICS
        public virtual V[] GetPrefix(string prefix)
#else
        public virtual IPersistent[] GetPrefix(string prefix)
#endif
        {
            return Get(new Key(prefix.ToCharArray()), 
                       new Key((prefix + Char.MaxValue).ToCharArray(), false));
        }
        
#if USE_GENERICS
        public virtual bool Put(Key key, V obj)
#else
        public virtual bool Put(Key key, IPersistent obj)
#endif
        {
            return insert(key, obj, false) >= 0;
        }

#if USE_GENERICS
        public virtual bool Put(K key, V obj)
#else
        public virtual bool Put(object key, IPersistent obj)
#endif
        {
            return Put(KeyBuilder.getKeyFromObject(key), obj);
        }

#if USE_GENERICS
        public virtual V Set(Key key, V obj)
        {
            int oid = insert(key, obj, true);
            return (oid != 0) ? (V)((StorageImpl)Storage).lookupObject(oid, null) : null;
        }
#else
        public virtual IPersistent Set(Key key, IPersistent obj)
        {
            int oid = insert(key, obj, true);
            return (oid != 0) ? ((StorageImpl)Storage).lookupObject(oid, null) : null;
        }
#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);
        }

        public int insert(Key key, IPersistent obj, bool overwrite)
        {
            StorageImpl db = (StorageImpl) Storage;
            if (db == null) 
            { 
                throw new StorageError(Perst.StorageError.ErrorCode.DELETED_OBJECT);
            }
            if (!obj.IsPersistent())
            {
                db.MakePersistent(obj);
            }
            BtreeKey ins = new BtreeKey(checkKey(key), obj.Oid);
            if (root == 0)
            {
                root = BtreePage.allocate(db, 0, type, ins);
                height = 1;
            }
            else
            {
                BtreeResult result = BtreePage.insert(db, root, this, ins, height, unique, overwrite);
                if (result == BtreeResult.Overflow)
                {
                    root = BtreePage.allocate(db, root, type, ins);
                    height += 1;
                }
                else if (result == BtreeResult.Duplicate)
                {
                    return -1;
                }
                else if (result == BtreeResult.Overwrite)
                {
                    return ins.oldOid;
                }
            }
            nElems += 1;
            updateCounter += 1;
            Modify();
            return 0;
        }
		
#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.Oid));
        }
		
#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.Oid));    
        }
 		
        internal virtual void remove(BtreeKey rem)
        {
            StorageImpl db = (StorageImpl) Storage;
            if (db == null) 
            { 
                throw new StorageError(Perst.StorageError.ErrorCode.DELETED_OBJECT);
            }
            if (root == 0)
            {
                throw new StorageError(StorageError.ErrorCode.KEY_NOT_FOUND);
            }
            BtreeResult result = BtreePage.remove(db, root, this, rem, height);
            if (result == BtreeResult.NotFound)
            {
                throw new StorageError(StorageError.ErrorCode.KEY_NOT_FOUND);
            }
            nElems -= 1;
            if (result == BtreeResult.Underflow)
            {
                Page pg = db.getPage(root);
                if (BtreePage.getnItems(pg) == 0)
                {
                    int newRoot = 0;
                    if (height != 1)  
                    {         
                        newRoot = (type == ClassDescriptor.FieldType.tpString || type == ClassDescriptor.FieldType.tpArrayOfByte)
                            ? BtreePage.getKeyStrOid(pg, 0)
                            : BtreePage.getReference(pg, BtreePage.maxItems - 1);
                    }
                    db.freePage(root);
                    root = newRoot;
                    height -= 1;
                }
                db.pool.unfix(pg);
            }
            else if (result == BtreeResult.Overflow)
            {
                root = BtreePage.allocate(db, root, type, rem);
                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), 0);
            StorageImpl db = (StorageImpl)Storage;
            remove(rk);
#if USE_GENERICS
            return (V)db.lookupObject(rk.oldOid, null);
#else
            return db.lookupObject(rk.oldOid, null);
#endif
        }		
            
#if USE_GENERICS
        public virtual V RemoveKey(K key)
#else
        public virtual IPersistent Remove(object key)
#endif
        {
            return Remove(KeyBuilder.getKeyFromObject(key));
        }

        public virtual int Size()
        {
            return nElems;
        }
		
#if USE_GENERICS
        public override void Clear() 
#else
        public void Clear() 
#endif
        {
            if (root != 0)
            {
                BtreePage.purge((StorageImpl) Storage, root, type, height);
                root = 0;
                nElems = 0;
                height = 0;
                updateCounter += 1;
                Modify();
            }
        }
		
#if USE_GENERICS
        public virtual V[] ToArray()