ptrie.cs

Perst开源实时数据库

            {
                this.obj = obj;
                this.key = key;
                this.keyLength = keyLength; 
            }

            PTrieNode() {}

#if USE_GENERICS
            internal T add(ulong key, int keyLength, T obj) 
            {
                T prevObj;
#else
            internal IPersistent add(ulong key, int keyLength, IPersistent obj) 
            {
                IPersistent prevObj;
#endif
                if (key == this.key && keyLength == this.keyLength) 
                {
                    Modify();
                    prevObj = this.obj;
                    this.obj = obj;
                    return prevObj;
                }
                int keyLengthCommon = getCommonPartLength(key, keyLength, this.key, this.keyLength);
                int keyLengthDiff = this.keyLength - keyLengthCommon;
                ulong keyCommon = key >> (keyLength - keyLengthCommon);
                ulong keyDiff = this.key - (keyCommon << keyLengthDiff);
                if (keyLengthDiff > 0) 
                {
                    Modify();
                    PTrieNode newNode = new PTrieNode(keyDiff, keyLengthDiff, this.obj);
                    newNode.childZero = childZero;
                    newNode.childOne = childOne;
                
                    this.key = keyCommon;
                    this.keyLength = keyLengthCommon;
                    this.obj = null;
                
                    if (firstBit(keyDiff, keyLengthDiff) == 1) 
                    {
                        childZero = null;
                        childOne = newNode;
                    } 
                    else 
                    {
                        childZero = newNode;
                        childOne = null;
                    }
                }
            
                if (keyLength > keyLengthCommon) 
                {
                    keyLengthDiff = keyLength - keyLengthCommon;
                    keyDiff = key - (keyCommon << keyLengthDiff);
                
                    if (firstBit(keyDiff, keyLengthDiff) == 1) 
                    {
                        if (childOne != null) 
                        {
                            return childOne.add(keyDiff, keyLengthDiff, obj);
                        } 
                        else 
                        { 
                            Modify();
                            childOne = new PTrieNode(keyDiff, keyLengthDiff, obj);
                            return null;
                        }
                    } 
                    else 
                    {
                        if (childZero != null) 
                        { 
                            return childZero.add(keyDiff, keyLengthDiff, obj);
                        } 
                        else 
                        { 
                            Modify();
                            childZero = new PTrieNode(keyDiff, keyLengthDiff, obj);
                            return null;
                        }
                    }
                } 
                else 
                {
                    prevObj = this.obj;
                    this.obj = obj;
                    return prevObj;
                }            
            }
    
        
#if USE_GENERICS
            internal T findBestMatch(ulong key, int keyLength) 
#else
            internal IPersistent findBestMatch(ulong key, int keyLength) 
#endif
            {             
                if (keyLength > this.keyLength) 
                { 
                    int keyLengthCommon = getCommonPartLength(key, keyLength, this.key, this.keyLength);
                    int keyLengthDiff = keyLength - keyLengthCommon;
                    ulong keyCommon = key >> keyLengthDiff;
                    ulong keyDiff = key - (keyCommon << keyLengthDiff);

                    if (firstBit(keyDiff, keyLengthDiff) == 1) 
                    {
                        if (childOne != null) 
                        { 
                            return childOne.findBestMatch(keyDiff, keyLengthDiff);
                        }
                    } 
                    else 
                    {
                        if (childZero != null) 
                        { 
                            return childZero.findBestMatch(keyDiff, keyLengthDiff);
                        }
                    }
                }
                return obj;
            }
				
#if USE_GENERICS
            internal T findExactMatch(ulong key, int keyLength) 
#else
            internal IPersistent findExactMatch(ulong key, int keyLength) 
#endif
            {             
                if (keyLength >= this.keyLength) 
                { 
                    if (key == this.key && keyLength == this.keyLength) 
                    { 
                        return obj;
                    } 
                    else 
                    { 
                        int keyLengthCommon = getCommonPartLength(key, keyLength, this.key, this.keyLength);
                        if (keyLengthCommon == this.keyLength) 
                        { 
                            int keyLengthDiff = keyLength - keyLengthCommon;
                            ulong keyCommon = key >> keyLengthDiff;
                            ulong keyDiff = key - (keyCommon << keyLengthDiff);
                        
                            if (firstBit(keyDiff, keyLengthDiff) == 1) 
                            {
                                if (childOne != null) 
                                { 
                                    return childOne.findBestMatch(keyDiff, keyLengthDiff);
                                }
                            } 
                            else 
                            {
                                if (childZero != null) 
                                { 
                                    return childZero.findBestMatch(keyDiff, keyLengthDiff);
                                } 
                            }
                        }
                    }
                }
                return null;
            }		

            internal bool isNotUsed() 
            { 
                return obj == null && childOne == null && childZero == null;
            }

#if USE_GENERICS
            internal T remove(ulong key, int keyLength) 
            {             
                T obj;
#else
            internal IPersistent remove(ulong key, int keyLength) 
            {         
                IPersistent obj;    
#endif
                if (keyLength >= this.keyLength) 
                { 
                    if (key == this.key && keyLength == this.keyLength) 
                    { 
                        obj = this.obj;
                        this.obj = null;
                        return obj;
                    } 
                    else 
                    { 
                        int keyLengthCommon = getCommonPartLength(key, keyLength, this.key, this.keyLength);
                        int keyLengthDiff = keyLength - keyLengthCommon;
                        ulong keyCommon = key >> keyLengthDiff;
                        ulong keyDiff = key - (keyCommon << keyLengthDiff);
                    
                        if (firstBit(keyDiff, keyLengthDiff) == 1) 
                        {
                            if (childOne != null) 
                            { 
                                obj = childOne.findBestMatch(keyDiff, keyLengthDiff);
                                if (obj != null) 
                                { 
                                    if (childOne.isNotUsed()) 
                                    {
                                        Modify();
                                        childOne.Deallocate();
                                        childOne = null;
                                    }
                                    return obj;                                    
                                }
                            }
                        } 
                        else 
                        {
                            if (childZero != null) 
                            { 
                                obj = childZero.findBestMatch(keyDiff, keyLengthDiff);
                                if (obj != null) 
                                { 
                                    if (childZero.isNotUsed()) 
                                    { 
                                        Modify();
                                        childZero.Deallocate();
                                        childZero = null;
                                    }
                                    return obj;                                    
                                }
                            } 
                        }
                    }
                }
                return null;
            }		

            public override void Deallocate() 
            {
                if (childOne != null) 
                { 
                    childOne.Deallocate();
                }
                if (childZero != null) 
                { 
                    childZero.Deallocate();
                }
                base.Deallocate();
            }
        }
    }
}