mono/mcs/class/referencesource/System.Runtime.Serialization/System/Runtime/Serialization/ObjectToIdCache.cs

//-----------------------------------------------------------------------------
// Copyright (c) Microsoft Corporation.  All rights reserved.
//-----------------------------------------------------------------------------
namespace System.Runtime.Serialization
{
    using System.Collections;
    using System.Collections.Generic;
    using System.Runtime.CompilerServices;
    using System.Security;

    class ObjectToIdCache
    {
        internal int m_currentCount;
        internal int[] m_ids;
        internal Object[] m_objs;
        bool[] m_isWrapped;

        public ObjectToIdCache()
        {
            m_currentCount = 1;
            m_ids = new int[GetPrime(1)];
            m_objs = new Object[m_ids.Length];
            m_isWrapped = new bool[m_ids.Length];
        }

        public int GetId(object obj, ref bool newId)
        {
            bool isEmpty, isWrapped;
            int position = FindElement(obj, out isEmpty, out isWrapped);
            if (!isEmpty)
            {
                newId = false;
                return m_ids[position];
            }
            if (!newId)
                return -1;

            int id = m_currentCount++;
            m_objs[position] = obj;
            m_ids[position] = id;
            m_isWrapped[position] = isWrapped;
            if (m_currentCount >= (m_objs.Length - 1))
                Rehash();
            return id;
        }

#if NotUsed
        public bool Remove(object obj)
        {
            bool isEmpty;
            int position = FindElement(obj, out isEmpty);
            if(isEmpty)
                return false;
            RemoveAt(position);
            return true;
        }
#endif

        // (oldObjId, oldObj-id, newObj-newObjId) => (oldObj-oldObjId, newObj-id, newObjId )
        public int ReassignId(int oldObjId, object oldObj, object newObj)
        {
            bool isEmpty, isWrapped;
            int position = FindElement(oldObj, out isEmpty, out isWrapped);
            if (isEmpty)
                return 0;
            int id = m_ids[position];
            if (oldObjId > 0)
                m_ids[position] = oldObjId;
            else
                RemoveAt(position);
            position = FindElement(newObj, out isEmpty, out isWrapped);
            int newObjId = 0;
            if (!isEmpty)
                newObjId = m_ids[position];
            m_objs[position] = newObj;
            m_ids[position] = id;
            m_isWrapped[position] = isWrapped;
            return newObjId;
        }

        private int FindElement(object obj, out bool isEmpty, out bool isWrapped)
        {
            isWrapped = false;
            int position = ComputeStartPosition(obj);
            for (int i = position; i != (position - 1); i++)
            {
                if (m_objs[i] == null)
                {
                    isEmpty = true;
                    return i;
                }
                if (m_objs[i] == obj)
                {
                    isEmpty = false;
                    return i;
                }
                if (i == (m_objs.Length - 1))
                {
                    isWrapped = true;
                    i = -1;
                }
            }
            // m_obj must ALWAYS have atleast one slot empty (null).
            Fx.Assert("Object table overflow");
            throw System.Runtime.Serialization.DiagnosticUtility.ExceptionUtility.ThrowHelperError(XmlObjectSerializer.CreateSerializationException(SR.GetString(SR.ObjectTableOverflow)));
        }

        private void RemoveAt(int position)
        {
            int cacheSize = m_objs.Length;
            int lastVacantPosition = position;
            for (int next = (position == cacheSize - 1) ? 0 : position + 1; next != position; next++)
            {
                if (m_objs[next] == null)
                {
                    m_objs[lastVacantPosition] = null;
                    m_ids[lastVacantPosition] = 0;
                    m_isWrapped[lastVacantPosition] = false;
                    return;
                }
                int nextStartPosition = ComputeStartPosition(m_objs[next]);
                // If we wrapped while placing an object, then it must be that the start position wasn't wrapped to begin with
                bool isNextStartPositionWrapped = next < position && !m_isWrapped[next];
                bool isLastVacantPositionWrapped = lastVacantPosition < position;

                // We want to avoid moving objects in the cache if the next bucket position is wrapped, but the last vacant position isn't
                // and we want to make sure to move objects in the cache when the last vacant position is wrapped but the next bucket position isn't
                if ((nextStartPosition <= lastVacantPosition && !(isNextStartPositionWrapped && !isLastVacantPositionWrapped)) ||
                    (isLastVacantPositionWrapped && !isNextStartPositionWrapped))
                {
                    m_objs[lastVacantPosition] = m_objs[next];
                    m_ids[lastVacantPosition] = m_ids[next];
                    // A wrapped object might become unwrapped if it moves from the front of the array to the end of the array
                    m_isWrapped[lastVacantPosition] = m_isWrapped[next] && next > lastVacantPosition;
                    lastVacantPosition = next;
                }
                if (next == (cacheSize - 1))
                {
                    next = -1;
                }
            }
            // m_obj must ALWAYS have atleast one slot empty (null).
            Fx.Assert("Object table overflow");
            throw System.Runtime.Serialization.DiagnosticUtility.ExceptionUtility.ThrowHelperError(XmlObjectSerializer.CreateSerializationException(SR.GetString(SR.ObjectTableOverflow)));
        }

        private int ComputeStartPosition(object o)
        {
            return (RuntimeHelpers.GetHashCode(o) & 0x7FFFFFFF) % m_objs.Length;
        }

        private void Rehash()
        {
            int size = GetPrime(m_objs.Length * 2);
            int[] oldIds = m_ids;
            object[] oldObjs = m_objs;
            m_ids = new int[size];
            m_objs = new Object[size];
            m_isWrapped = new bool[size];

            for (int j = 0; j < oldObjs.Length; j++)
            {
                object obj = oldObjs[j];
                if (obj != null)
                {
                    bool found, isWrapped;
                    int position = FindElement(obj, out found, out isWrapped);
                    m_objs[position] = obj;
                    m_ids[position] = oldIds[j];
                    m_isWrapped[position] = isWrapped;
                }
            }
        }

        static int GetPrime(int min)
        {

            for (int i = 0; i < primes.Length; i++)
            {
                int prime = primes[i];
                if (prime >= min) return prime;
            }

            //outside of our predefined table. 
            //compute the hard way. 
            for (int i = (min | 1); i < Int32.MaxValue; i += 2)
            {
                if (IsPrime(i))
                    return i;
            }
            return min;
        }

        static bool IsPrime(int candidate)
        {
            if ((candidate & 1) != 0)
            {
                int limit = (int)Math.Sqrt(candidate);
                for (int divisor = 3; divisor <= limit; divisor += 2)
                {
                    if ((candidate % divisor) == 0)
                        return false;
                }
                return true;
            }
            return (candidate == 2);
        }

        [Fx.Tag.SecurityNote(Miscellaneous = "RequiresReview - Static fields are marked SecurityCritical or readonly to prevent"
            + " data from being modified or leaked to other components in appdomain.")]
        internal static readonly int[] primes = 
        {
            3, 7, 17, 37, 89, 197, 431, 919, 1931, 4049, 8419, 17519, 36353, 
            75431, 156437, 324449, 672827, 1395263, 2893249, 5999471, 
        };

    }
}