// 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;
using System.Diagnostics;
using System.Threading;

namespace Microsoft.CodeAnalysis.Collections
{
    /// <summary>
    /// A set of ints that is small, thread-safe and lock free.
    /// Several assumptions have been made that allow it to be small and fast:
    /// 1. Deletes never happen.
    /// 2. The size is small. In dogfooding experiments, 89% had 4 or fewer elements and
    ///    98% had 8 or fewer elements. The largest size was 17.
    /// 3. As a result of assumption 2, linear look-up is good enough.
    /// 4. One value, in this case int.MinValue, is used as a sentinel and may never appear in the set.
    /// </summary>
    internal class SmallConcurrentSetOfInts
    {
        // The set is a singly-linked list of nodes each containing up to 4 values.
        // Empty slots contain the "unoccupied" sentinel value.
        private int _v1;
        private int _v2;
        private int _v3;
        private int _v4;
        private SmallConcurrentSetOfInts? _next;

        private const int unoccupied = int.MinValue;

        public SmallConcurrentSetOfInts()
        {
            _v1 = _v2 = _v3 = _v4 = unoccupied;
        }

        private SmallConcurrentSetOfInts(int initialValue)
        {
            _v1 = initialValue;
            _v2 = _v3 = _v4 = unoccupied;
        }

        /// <summary>
        /// Determine if the given integer appears in the set.
        /// </summary>
        /// <param name="i">The value to look up.</param>
        /// <returns>true if <paramref name="i"/> appears in the set. false otherwise.</returns>
        public bool Contains(int i)
        {
            Debug.Assert(i != unoccupied);
            return SmallConcurrentSetOfInts.Contains(this, i);
        }

        private static bool Contains(SmallConcurrentSetOfInts set, int i)
        {
            SmallConcurrentSetOfInts? current = set;
            do
            {
                // PERF: Not testing for unoccupied slots since it adds complexity. The extra comparisons
                // would slow down this inner loop such that any benefit of an 'early out' would be lost.
                if (current._v1 == i || current._v2 == i || current._v3 == i || current._v4 == i)
                {
                    return true;
                }

                current = current._next;
            }
            while (current != null);

            return false;
        }

        /// <summary>
        /// Insert the given value into the set.
        /// </summary>
        /// <param name="i">The value to insert</param>
        /// <returns>true if <paramref name="i"/> was added. false if it was already present.</returns>
        public bool Add(int i)
        {
            Debug.Assert(i != unoccupied);
            return SmallConcurrentSetOfInts.Add(this, i);
        }

        private static bool Add(SmallConcurrentSetOfInts set, int i)
        {
            bool added = false;

            while (true)
            {
                if (AddHelper(ref set._v1, i, ref added) ||
                    AddHelper(ref set._v2, i, ref added) ||
                    AddHelper(ref set._v3, i, ref added) ||
                    AddHelper(ref set._v4, i, ref added))
                {
                    return added;
                }

                var nextSet = set._next;
                if (nextSet == null)
                {
                    // Need to add a new 'block'.
                    SmallConcurrentSetOfInts tail = new SmallConcurrentSetOfInts(initialValue: i);

                    nextSet = Interlocked.CompareExchange(ref set._next, tail, null);
                    if (nextSet == null)
                    {
                        // Successfully added a new tail
                        return true;
                    }
                    // Lost the race. Another thread added a new tail so resume searching from there.
                }

                set = nextSet;
            }
        }

        /// <summary>
        /// If the given slot is unoccupied, then try to replace it with a new value.
        /// </summary>
        /// <param name="slot">The slot to examine.</param>
        /// <param name="i">The new value to insert if the slot is unoccupied.</param>
        /// <param name="added">An out param indicating whether the slot was successfully updated.</param>
        /// <returns>true if the value in the slot either now contains, or already contained <paramref name="i"/>. false otherwise.</returns>
        private static bool AddHelper(ref int slot, int i, ref bool added)
        {
            Debug.Assert(!added);

            int val = slot;

            if (val == unoccupied)
            {
                val = Interlocked.CompareExchange(ref slot, i, unoccupied);

                if (val == unoccupied)
                {
                    // Successfully replaced the value
                    added = true;
                    return true;
                }
                // Lost the race with another thread
            }

            return (val == i);
        }
    }
}