rndbtree.cs

Perst开源实时数据库

            internal override object getKeyValue(int i)
            {
                return data[i];
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfObject(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return (int) key.ival - data.GetRaw(i).Oid;
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                data[i] = (IPersistent) key.key.oval;
            }
            
            internal BtreePageOfObject(Storage s):base(s, MAX_ITEMS)
            {
                data = s.CreateLink(MAX_ITEMS);
                data.Length = MAX_ITEMS;
            }
            
            internal BtreePageOfObject()
            {
            }
        }
        
        class BtreePageOfString:BtreePage
        {
            override internal Array Data
            {
                get
                {
                    return data;
                }
                
            }
            internal string[] data;
            
            internal const int MAX_ITEMS = 100;
            
            
            internal override Key getKey(int i)
            {
                return new Key(data[i]);
            }
            
            internal override object getKeyValue(int i)
            {
                return data[i];
            }
            
            internal override void  clearKeyValue(int i)
            {
                data[i] = null;
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfString(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return ((string) key.oval).CompareTo(data[i]);
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                data[i] = (string) key.key.oval;
            }
            
            internal override void  memset(int i, int len)
            {
                while (--len >= 0)
                {
                    items[i] = null;
                    data[i] = null;
                    i += 1;
                }
            }
            
            internal virtual bool prefixSearch(string key, int height, ArrayList result)
            {
                int l = 0, n = nItems, r = n;
                height -= 1;
                while (l < r)
                {
                    int i = (l + r) >> 1;
                    if (!key.StartsWith(data[i]) && key.CompareTo(data[i]) > 0)
                    {
                        l = i + 1;
                    }
                    else
                    {
                        r = i;
                    }
                }
                Debug.Assert(r == l);
                if (height == 0)
                {
                    while (l < n)
                    {
                        if (key.CompareTo(data[l]) < 0)
                        {
                            return false;
                        }
                        result.Add(items[l]);
                        l += 1;
                    }
                }
                else
                {
                    do 
                    {
                        if (!((BtreePageOfString) items[l]).prefixSearch(key, height, result))
                        {
                            return false;
                        }
                        if (l == n)
                        {
                            return true;
                        }
                    }
                    while (key.CompareTo(data[l++]) >= 0);
                    return false;
                }
                return true;
            }
            
            
            internal BtreePageOfString(Storage s):base(s, MAX_ITEMS)
            {
                data = new string[MAX_ITEMS];
            }
            
            internal BtreePageOfString()
            {
            }
        }
        
        class BtreePageOfRaw:BtreePage
        {
            override internal Array Data
            {
                get
                {
                    return (Array)data;
                }
                
            }
            internal object data;
            
            internal const int MAX_ITEMS = 100;
            
            
            internal override Key getKey(int i)
            {
                return new Key((IComparable)((object[]) data)[i]);
            }
            
            internal override object getKeyValue(int i)
            {
                return ((object[])data)[i];
            }
            
            internal override void  clearKeyValue(int i)
            {
                ((object[])data)[i] = null;
            }
            
            internal override BtreePage clonePage()
            {
                return new BtreePageOfRaw(Storage);
            }
            
            internal override int compare(Key key, int i)
            {
                return ((IComparable) key.oval).CompareTo(((object[]) data)[i]);
            }
            
            internal override void  insert(BtreeKey key, int i)
            {
                items[i] = key.node;
                ((object[])data)[i] = key.key.oval;
            }
            
            internal BtreePageOfRaw(Storage s):base(s, MAX_ITEMS)
            {
                data = new object[MAX_ITEMS];
            }
            
            internal BtreePageOfRaw()
            {
            }
        }
        
        
        
        internal static ClassDescriptor.FieldType checkType(Type c)
        {
            ClassDescriptor.FieldType elemType = ClassDescriptor.getTypeCode(c);
            if ((int)elemType > (int)ClassDescriptor.FieldType.tpOid
                && elemType != ClassDescriptor.FieldType.tpDecimal
                && elemType != ClassDescriptor.FieldType.tpRaw
                && elemType != ClassDescriptor.FieldType.tpGuid) 
            {
                throw new StorageError(StorageError.ErrorCode.UNSUPPORTED_INDEX_TYPE, c);
            }
            return elemType;
        }
        
#if USE_GENERICS
        internal RndBtree(bool unique)
        {
            type = checkType(typeof(K));
            this.unique = unique;
        }
#else
        internal RndBtree(Type cls, bool unique)
        {
            type = checkType(cls);
            this.unique = unique;
        }
#endif
        
        internal RndBtree(ClassDescriptor.FieldType type, bool unique)
        {
            this.type = type;
            this.unique = unique;
        }
        
        internal enum OperationResult 
        { 
            Done, 
            Overflow,
            Underflow,
            NotFound,
            Duplicate,
            Overwrite
        }
        
        public override int Count 
        { 
            get 
            {
                return nElems;
            }
        }

#if USE_GENERICS
        public V this[K key] 
#else
        public IPersistent this[object key] 
#endif
        {
            get 
            {
                return Get(key);
            }
            set 
            {
                Set(key, value);
            }
        } 
        
#if USE_GENERICS
        public V[] this[K from, K till] 
#else
        public IPersistent[] this[object from, object till] 
#endif
        {
            get 
            {
                return Get(from, till);
            }
        }


        internal virtual 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 (key.oval is char[])
                {
                    key = new Key(new string((char[]) key.oval), key.inclusion != 0);
                }
            }
            return key;
        }
        
#if USE_GENERICS
        public virtual V Get(Key key)
#else
        public virtual IPersistent Get(Key key)
#endif
        {
            key = checkKey(key);
            if (root != null)
            {
                ArrayList list = new ArrayList();
                root.find(key, key, height, list);
                if (list.Count > 1)
                {
                    throw new StorageError(StorageError.ErrorCode.KEY_NOT_UNIQUE);
                }
                else if (list.Count == 0)
                {
                    return null;
                }
                else
                {
#if USE_GENERICS
                    return (V) list[0];
#else
                    return (IPersistent) list[0];
#endif
                }
            }
            return null;
        }

#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[] PrefixSearch(string key)
#else
        internal static IPersistent[] emptySelection = new IPersistent[0];
        
        public virtual IPersistent[] PrefixSearch(string key)
#endif
        {
            if (ClassDescriptor.FieldType.tpString != type)
            {
                throw new StorageError(StorageError.ErrorCode.INCOMPATIBLE_KEY_TYPE);
            }
            if (root != null)
            {
                ArrayList list = new ArrayList();
                ((BtreePageOfString) root).prefixSearch(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(Key from, Key till)
#else
        public virtual IPersistent[] Get(Key from, Key till)
#endif
        {
            if (root != null)
            {
                ArrayList list = new ArrayList();
                root.find(checkKey(from), checkKey(till), 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 bool Put(Key key, V obj)
#else
        public virtual bool Put(Key key, IPersistent obj)
#endif
        {
            return insert(key, obj, false) == null;
        }
        
#if USE_GENERICS
        public virtual bool Put(K key, V obj)
#else
        public virtual bool Put(object key, IPersistent obj)