// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

using System.Diagnostics;

namespace System.Collections.Specialized
{
    /// <devdoc>
    ///  <para>
    ///    This data structure implements IDictionary first using a linked list
    ///    (ListDictionary) and then switching over to use Hashtable when large. This is recommended
    ///    for cases where the number of elements in a dictionary is unknown and might be small.
    ///
    ///    It also has a single boolean parameter to allow case-sensitivity that is not affected by
    ///    ambient culture and has been optimized for looking up case-insensitive symbols
    ///  </para>
    /// </devdoc>
    [Serializable]
    [System.Runtime.CompilerServices.TypeForwardedFrom("System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
    public class HybridDictionary : IDictionary
    {
        // These numbers have been carefully tested to be optimal. Please don't change them
        // without doing thorough performance testing.
        private const int CutoverPoint = 9;
        private const int InitialHashtableSize = 13;
        private const int FixedSizeCutoverPoint = 6;

        // Instance variables. This keeps the HybridDictionary very light-weight when empty
        private ListDictionary? list; // Do not rename (binary serialization)
        private Hashtable? hashtable; // Do not rename (binary serialization)
        private readonly bool caseInsensitive; // Do not rename (binary serialization)

        public HybridDictionary()
        {
        }

        public HybridDictionary(int initialSize) : this(initialSize, false)
        {
        }

        public HybridDictionary(bool caseInsensitive)
        {
            this.caseInsensitive = caseInsensitive;
        }

        public HybridDictionary(int initialSize, bool caseInsensitive)
        {
            this.caseInsensitive = caseInsensitive;
            if (initialSize >= FixedSizeCutoverPoint)
            {
                if (caseInsensitive)
                {
                    hashtable = new Hashtable(initialSize, StringComparer.OrdinalIgnoreCase);
                }
                else
                {
                    hashtable = new Hashtable(initialSize);
                }
            }
        }

        public object? this[object key]
        {
            get
            {
                // Hashtable supports multiple read, one writer thread safety.
                // Although we never made the same guarantee for HybridDictionary,
                // it is still nice to do the same thing here since we have recommended
                // HybridDictionary as replacement for Hashtable.
                ListDictionary? cachedList = list;
                if (hashtable != null)
                {
                    return hashtable[key];
                }
                else if (cachedList != null)
                {
                    return cachedList[key];
                }
                // cachedList can be null in too cases:
                //   (1) The dictionary is empty, we will return null in this case
                //   (2) There is writer which is doing ChangeOver. However in that case
                //       we should see the change to hashtable as well.
                //       So it should work just fine.
                else
                {
                    ArgumentNullException.ThrowIfNull(key);
                }
                return null;
            }
            set
            {
                if (hashtable != null)
                {
                    hashtable[key] = value;
                }
                else if (list != null)
                {
                    if (list.Count >= CutoverPoint - 1)
                    {
                        ChangeOver();
                        Debug.Assert(hashtable != null);
                        hashtable[key] = value;
                    }
                    else
                    {
                        list[key] = value;
                    }
                }
                else
                {
                    list = new ListDictionary(caseInsensitive ? StringComparer.OrdinalIgnoreCase : null);
                    list[key] = value;
                }
            }
        }

        private ListDictionary List => list ??= new ListDictionary(caseInsensitive ? StringComparer.OrdinalIgnoreCase : null);

        private void ChangeOver()
        {
            Debug.Assert(list != null);
            IDictionaryEnumerator en = list.GetEnumerator();
            Hashtable newTable;
            if (caseInsensitive)
            {
                newTable = new Hashtable(InitialHashtableSize, StringComparer.OrdinalIgnoreCase);
            }
            else
            {
                newTable = new Hashtable(InitialHashtableSize);
            }
            while (en.MoveNext())
            {
                newTable.Add(en.Key, en.Value);
            }

            // Keep the order of writing to hashtable and list.
            // We assume we will see the change in hashtable if list is set to null in
            // this method in another reader thread.
            hashtable = newTable;
            list = null;
        }

        public int Count
        {
            get
            {
                ListDictionary? cachedList = list;
                if (hashtable != null)
                {
                    return hashtable.Count;
                }
                else if (cachedList != null)
                {
                    return cachedList.Count;
                }
                else
                {
                    return 0;
                }
            }
        }

        public ICollection Keys
        {
            get
            {
                if (hashtable != null)
                {
                    return hashtable.Keys;
                }
                else
                {
                    return List.Keys;
                }
            }
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        public bool IsFixedSize
        {
            get
            {
                return false;
            }
        }

        public bool IsSynchronized
        {
            get
            {
                return false;
            }
        }

        public object SyncRoot
        {
            get
            {
                return this;
            }
        }

        public ICollection Values
        {
            get
            {
                if (hashtable != null)
                {
                    return hashtable.Values;
                }
                else
                {
                    return List.Values;
                }
            }
        }

        public void Add(object key, object? value)
        {
            if (hashtable != null)
            {
                hashtable.Add(key, value);
            }
            else
            {
                if (list == null)
                {
                    list = new ListDictionary(caseInsensitive ? StringComparer.OrdinalIgnoreCase : null);
                    list.Add(key, value);
                }
                else if (list.Count + 1 >= CutoverPoint)
                {
                    ChangeOver();
                    Debug.Assert(hashtable != null);
                    hashtable.Add(key, value);
                }
                else
                {
                    list.Add(key, value);
                }
            }
        }

        public void Clear()
        {
            if (hashtable != null)
            {
                Hashtable cachedHashtable = hashtable;
                hashtable = null;
                cachedHashtable.Clear();
            }

            if (list != null)
            {
                ListDictionary cachedList = list;
                list = null;
                cachedList.Clear();
            }
        }

        public bool Contains(object key)
        {
            ListDictionary? cachedList = list;
            if (hashtable != null)
            {
                return hashtable.Contains(key);
            }
            else if (cachedList != null)
            {
                return cachedList.Contains(key);
            }
            else
            {
                ArgumentNullException.ThrowIfNull(key);
            }
            return false;
        }

        public void CopyTo(Array array, int index)
        {
            if (hashtable != null)
            {
                hashtable.CopyTo(array, index);
            }
            else
            {
                List.CopyTo(array, index);
            }
        }

        public IDictionaryEnumerator GetEnumerator()
        {
            if (hashtable != null)
            {
                return hashtable.GetEnumerator();
            }

            list ??= new ListDictionary(caseInsensitive ? StringComparer.OrdinalIgnoreCase : null);
            return list.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            if (hashtable != null)
            {
                return hashtable.GetEnumerator();
            }

            list ??= new ListDictionary(caseInsensitive ? StringComparer.OrdinalIgnoreCase : null);
            return list.GetEnumerator();
        }

        public void Remove(object key)
        {
            if (hashtable != null)
            {
                hashtable.Remove(key);
            }
            else if (list != null)
            {
                list.Remove(key);
            }
            else
            {
                ArgumentNullException.ThrowIfNull(key);
            }
        }
    }
}