// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
using System;
 
namespace Microsoft.Xml
{
    using System;
 
 
    /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable"]/*' />
    /// <devdoc>
    ///    <para>
    ///       XmlNameTable implemented as a simple hash table.
    ///    </para>
    /// </devdoc>
    public class NameTable : XmlNameTable
    {
        //
        // Private types
        //
        private class Entry
        {
            internal string str;
            internal int hashCode;
            internal Entry next;
 
            internal Entry(string str, int hashCode, Entry next)
            {
                this.str = str;
                this.hashCode = hashCode;
                this.next = next;
            }
        }
 
        //
        // Fields
        //
        private Entry[] _entries;
        private int _count;
        private int _mask;
        private int _hashCodeRandomizer;
 
        //
        // Constructor
        //
        /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.NameTable"]/*' />
        /// <devdoc>
        ///      Public constructor.
        /// </devdoc>
        public NameTable()
        {
            _mask = 31;
            _entries = new Entry[_mask + 1];
            _hashCodeRandomizer = Environment.TickCount;
        }
 
        //
        // XmlNameTable public methods
        //
        /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Add"]/*' />
        /// <devdoc>
        ///      Add the given string to the NameTable or return
        ///      the existing string if it is already in the NameTable.
        /// </devdoc>
        public override string Add(string key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }
            int len = key.Length;
            if (len == 0)
            {
                return string.Empty;
            }
            int hashCode = len + _hashCodeRandomizer;
            // use key.Length to eliminate the rangecheck
            for (int i = 0; i < key.Length; i++)
            {
                hashCode += (hashCode << 7) ^ key[i];
            }
            // mix it a bit more
            hashCode -= hashCode >> 17;
            hashCode -= hashCode >> 11;
            hashCode -= hashCode >> 5;
 
            for (Entry e = _entries[hashCode & _mask]; e != null; e = e.next)
            {
                if (e.hashCode == hashCode && e.str.Equals(key))
                {
                    return e.str;
                }
            }
            return AddEntry(key, hashCode);
        }
 
        /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Add1"]/*' />
        /// <devdoc>
        ///      Add the given string to the NameTable or return
        ///      the existing string if it is already in the NameTable.
        /// </devdoc>
        public override string Add(char[] key, int start, int len)
        {
            if (len == 0)
            {
                return string.Empty;
            }
 
            int hashCode = len + _hashCodeRandomizer;
            hashCode += (hashCode << 7) ^ key[start];   // this will throw IndexOutOfRangeException in case the start index is invalid
            int end = start + len;
            for (int i = start + 1; i < end; i++)
            {
                hashCode += (hashCode << 7) ^ key[i];
            }
            // mix it a bit more
            hashCode -= hashCode >> 17;
            hashCode -= hashCode >> 11;
            hashCode -= hashCode >> 5;
 
            for (Entry e = _entries[hashCode & _mask]; e != null; e = e.next)
            {
                if (e.hashCode == hashCode && TextEquals(e.str, key, start, len))
                {
                    return e.str;
                }
            }
            return AddEntry(new string(key, start, len), hashCode);
        }
 
        /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Get"]/*' />
        /// <devdoc>
        ///      Find the matching string in the NameTable.
        /// </devdoc>
        public override string Get(string value)
        {
            if (value == null)
            {
                throw new ArgumentNullException("value");
            }
            if (value.Length == 0)
            {
                return string.Empty;
            }
 
            int len = value.Length + _hashCodeRandomizer;
            int hashCode = len;
            // use value.Length to eliminate the rangecheck
            for (int i = 0; i < value.Length; i++)
            {
                hashCode += (hashCode << 7) ^ value[i];
            }
            // mix it a bit more
            hashCode -= hashCode >> 17;
            hashCode -= hashCode >> 11;
            hashCode -= hashCode >> 5;
 
            for (Entry e = _entries[hashCode & _mask]; e != null; e = e.next)
            {
                if (e.hashCode == hashCode && e.str.Equals(value))
                {
                    return e.str;
                }
            }
            return null;
        }
 
        /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Get1"]/*' />
        /// <devdoc>
        ///      Find the matching string atom given a range of
        ///      characters.
        /// </devdoc>
        public override string Get(char[] key, int start, int len)
        {
            if (len == 0)
            {
                return string.Empty;
            }
 
            int hashCode = len + _hashCodeRandomizer;
            hashCode += (hashCode << 7) ^ key[start];   // this will throw IndexOutOfRangeException in case the start index is invalid
            int end = start + len;
            for (int i = start + 1; i < end; i++)
            {
                hashCode += (hashCode << 7) ^ key[i];
            }
            // mix it a bit more
            hashCode -= hashCode >> 17;
            hashCode -= hashCode >> 11;
            hashCode -= hashCode >> 5;
 
            for (Entry e = _entries[hashCode & _mask]; e != null; e = e.next)
            {
                if (e.hashCode == hashCode && TextEquals(e.str, key, start, len))
                {
                    return e.str;
                }
            }
            return null;
        }
 
        //
        // Private methods
        //
 
        private string AddEntry(string str, int hashCode)
        {
            int index = hashCode & _mask;
            Entry e = new Entry(str, hashCode, _entries[index]);
            _entries[index] = e;
            if (_count++ == _mask)
            {
                Grow();
            }
            return e.str;
        }
 
        private void Grow()
        {
            int newMask = _mask * 2 + 1;
            Entry[] oldEntries = _entries;
            Entry[] newEntries = new Entry[newMask + 1];
 
            // use oldEntries.Length to eliminate the rangecheck            
            for (int i = 0; i < oldEntries.Length; i++)
            {
                Entry e = oldEntries[i];
                while (e != null)
                {
                    int newIndex = e.hashCode & newMask;
                    Entry tmp = e.next;
                    e.next = newEntries[newIndex];
                    newEntries[newIndex] = e;
                    e = tmp;
                }
            }
 
            _entries = newEntries;
            _mask = newMask;
        }
 
        private static bool TextEquals(string str1, char[] str2, int str2Start, int str2Length)
        {
            if (str1.Length != str2Length)
            {
                return false;
            }
            // use array.Length to eliminate the rangecheck
            for (int i = 0; i < str1.Length; i++)
            {
                if (str1[i] != str2[str2Start + i])
                {
                    return false;
                }
            }
            return true;
        }
    }
}