ptrie.cs

Perst开源实时数据库

using System;
using Perst;
#if USE_GENERICS
using System.Collections.Generic;
#else
using System.Collections;
#endif

namespace Perst.Impl
{
#if USE_GENERICS
    class PTrie<T> : PersistentCollection<T>, PatriciaTrie<T>  where T:class,IPersistent 
#else
    class PTrie : PersistentCollection, PatriciaTrie 
#endif
    { 
        private PTrieNode rootZero;
        private PTrieNode rootOne;
        private int       count;


#if USE_GENERICS
        public override IEnumerator<T> GetEnumerator() 
        {
            List<T> list = new List<T>();
#else
        public override IEnumerator GetEnumerator() 
        {
            ArrayList list = new ArrayList();
#endif
            fill(list, rootZero);
            fill(list, rootOne);
            return list.GetEnumerator();
        }

#if USE_GENERICS
        private static void fill(List<T> list, PTrieNode node) { 
#else
        private static void fill(ArrayList list, PTrieNode node) { 
#endif
            if (node != null) {
                list.Add(node.obj);
                fill(list, node.childZero);
                fill(list, node.childOne);
            }
        }

        public override int Count 
        { 
            get 
            {
                return count;
            }
        }

        private static int firstBit(ulong key, int keyLength)
        {
            return (int)(key >> (keyLength - 1)) & 1;
        }

        private static int getCommonPartLength(ulong keyA, int keyLengthA, ulong keyB, int keyLengthB)
        {
            if (keyLengthA > keyLengthB) 
            {
                keyA >>= keyLengthA - keyLengthB;
                keyLengthA = keyLengthB;
            } 
            else 
            {
                keyB >>= keyLengthB - keyLengthA;
                keyLengthB = keyLengthA;
            }
            ulong diff = keyA ^ keyB;
        
            int count = 0;
            while (diff != 0) 
            {
                diff >>= 1;
                count += 1;
            }
            return keyLengthA - count;
        }

#if USE_GENERICS
        public T Add(PatriciaTrieKey key, T obj) 
#else
        public IPersistent Add(PatriciaTrieKey key, IPersistent obj) 
#endif
        { 
            Modify();
            count += 1;

            if (firstBit(key.mask, key.length) == 1) 
            {
                if (rootOne != null) 
                { 
                    return rootOne.add(key.mask, key.length, obj);
                } 
                else 
                { 
                    rootOne = new PTrieNode(key.mask, key.length, obj);
                    return null;
                }
            } 
            else 
            { 
                if (rootZero != null) 
                { 
                    return rootZero.add(key.mask, key.length, obj);
                } 
                else 
                { 
                    rootZero = new PTrieNode(key.mask, key.length, obj);
                    return null;
                }
            }            
        }
    
#if USE_GENERICS
        public T FindBestMatch(PatriciaTrieKey key) 
#else
        public IPersistent FindBestMatch(PatriciaTrieKey key) 
#endif
        {
            if (firstBit(key.mask, key.length) == 1) 
            {
                if (rootOne != null) 
                { 
                    return rootOne.findBestMatch(key.mask, key.length);
                } 
            } 
            else 
            { 
                if (rootZero != null) 
                { 
                    return rootZero.findBestMatch(key.mask, key.length);
                } 
            }
            return null;
        }
    

#if USE_GENERICS
        public T FindExactMatch(PatriciaTrieKey key) 
#else
        public IPersistent FindExactMatch(PatriciaTrieKey key) 
#endif
        {
            if (firstBit(key.mask, key.length) == 1) 
            {
                if (rootOne != null) 
                { 
                    return rootOne.findExactMatch(key.mask, key.length);
                } 
            } 
            else 
            { 
                if (rootZero != null) 
                { 
                    return rootZero.findExactMatch(key.mask, key.length);
                } 
            }
            return null;
        }
    
#if USE_GENERICS
        public T Remove(PatriciaTrieKey key) 
        { 
             T obj;
#else
        public IPersistent Remove(PatriciaTrieKey key) 
        { 
            IPersistent obj;
#endif
            if (firstBit(key.mask, key.length) == 1) 
            {
                if (rootOne != null) 
                { 
                    obj = rootOne.remove(key.mask, key.length);
                    if (obj != null) 
                    { 
                        Modify();
                        count -= 1;
                        if (rootOne.isNotUsed()) 
                        { 
                            rootOne.Deallocate();
                            rootOne = null;
                        }
                        return obj;
                    }
                }  
            } 
            else 
            { 
                if (rootZero != null) 
                { 
                    obj = rootZero.remove(key.mask, key.length);
                    if (obj != null) 
                    { 
                        Modify();
                        count -= 1;
                        if (rootZero.isNotUsed()) 
                        { 
                            rootZero.Deallocate();
                            rootZero = null;
                        }
                        return obj;
                    }
                }  
            }
            return null;
        }

#if USE_GENERICS
        public override void Clear() 
#else
        public void Clear() 
#endif
        {
            if (rootOne != null) 
            { 
                rootOne.Deallocate();
                rootOne = null;
            }
            if (rootZero != null) 
            { 
                rootZero.Deallocate();
                rootZero = null;
            }
            count = 0;
        }

        class PTrieNode : Persistent 
        {
            internal ulong       key;
            internal int         keyLength;
#if USE_GENERICS
            internal T           obj;
#else
            internal IPersistent obj;
#endif
            internal PTrieNode   childZero;
            internal PTrieNode   childOne;

#if USE_GENERICS
            internal PTrieNode(ulong key, int keyLength, T obj)
#else
            internal PTrieNode(ulong key, int keyLength, IPersistent obj)
#endif