using System;
using Interlocked = System.Threading.Interlocked;
 
#if ES_BUILD_STANDALONE
namespace Microsoft.Diagnostics.Tracing
#else
namespace System.Diagnostics.Tracing
#endif
{
    /// <summary>
    /// TraceLogging: A very simple lock-free add-only dictionary.
    /// Warning: this is a copy-by-value type. Copying performs a snapshot.
    /// Accessing a readonly field always makes a copy of the field, so the
    /// GetOrAdd method will not work as expected if called on a readonly field.
    /// </summary>
    /// <typeparam name="KeyType">
    /// The type of the key, used for TryGet.
    /// </typeparam>
    /// <typeparam name="ItemType">
    /// The type of the item, used for GetOrAdd.
    /// </typeparam>
    internal struct ConcurrentSet<KeyType, ItemType>
        where ItemType : ConcurrentSetItem<KeyType, ItemType>
    {
        private ItemType[] items;
 
        public ItemType TryGet(KeyType key)
        {
            ItemType item;
            var oldItems = this.items;
 
            if (oldItems != null)
            {
                var lo = 0;
                var hi = oldItems.Length;
                do
                {
                    int i = (lo + hi) / 2;
                    item = oldItems[i];
 
                    int cmp = item.Compare(key);
                    if (cmp == 0)
                    {
                        goto Done;
                    }
                    else if (cmp < 0)
                    {
                        lo = i + 1;
                    }
                    else
                    {
                        hi = i;
                    }
                }
                while (lo != hi);
            }
 
            item = null;
 
        Done:
 
            return item;
        }
 
        public ItemType GetOrAdd(ItemType newItem)
        {
            ItemType item;
            var oldItems = this.items;
            ItemType[] newItems;
 
        Retry:
 
            if (oldItems == null)
            {
                newItems = new ItemType[] { newItem };
            }
            else
            {
                var lo = 0;
                var hi = oldItems.Length;
                do
                {
                    int i = (lo + hi) / 2;
                    item = oldItems[i];
 
                    int cmp = item.Compare(newItem);
                    if (cmp == 0)
                    {
                        goto Done;
                    }
                    else if (cmp < 0)
                    {
                        lo = i + 1;
                    }
                    else
                    {
                        hi = i;
                    }
                }
                while (lo != hi);
 
                int oldLength = oldItems.Length;
                newItems = new ItemType[oldLength + 1];
                Array.Copy(oldItems, 0, newItems, 0, lo);
                newItems[lo] = newItem;
                Array.Copy(oldItems, lo, newItems, lo + 1, oldLength - lo);
            }
 
            newItems = Interlocked.CompareExchange(ref this.items, newItems, oldItems);
            if (oldItems != newItems)
            {
                oldItems = newItems;
                goto Retry;
            }
 
            item = newItem;
 
        Done:
 
            return item;
        }
    }
}