1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 
5 using System.Collections;
6 using System.Collections.Generic;
7 using System.Runtime.CompilerServices;
8 
9 namespace System.Runtime.Serialization
10 {
11     internal class ObjectToIdCache
12     {
13         internal int m_currentCount;
14         internal int[] m_ids;
15         internal Object[] m_objs;
16         internal bool[] m_isWrapped;
17 
ObjectToIdCache()18         public ObjectToIdCache()
19         {
20             m_currentCount = 1;
21             m_ids = new int[GetPrime(1)];
22             m_objs = new Object[m_ids.Length];
23             m_isWrapped = new bool[m_ids.Length];
24         }
25 
GetId(object obj, ref bool newId)26         public int GetId(object obj, ref bool newId)
27         {
28             bool isEmpty, isWrapped;
29             int position = FindElement(obj, out isEmpty, out isWrapped);
30             if (!isEmpty)
31             {
32                 newId = false;
33                 return m_ids[position];
34             }
35             if (!newId)
36                 return -1;
37 
38             int id = m_currentCount++;
39             m_objs[position] = obj;
40             m_ids[position] = id;
41             m_isWrapped[position] = isWrapped;
42             if (m_currentCount >= (m_objs.Length - 1))
43                 Rehash();
44             return id;
45         }
46 
47         // (oldObjId, oldObj-id, newObj-newObjId) => (oldObj-oldObjId, newObj-id, newObjId )
ReassignId(int oldObjId, object oldObj, object newObj)48         public int ReassignId(int oldObjId, object oldObj, object newObj)
49         {
50             bool isEmpty, isWrapped;
51             int position = FindElement(oldObj, out isEmpty, out isWrapped);
52             if (isEmpty)
53                 return 0;
54             int id = m_ids[position];
55             if (oldObjId > 0)
56                 m_ids[position] = oldObjId;
57             else
58                 RemoveAt(position);
59             position = FindElement(newObj, out isEmpty, out isWrapped);
60             int newObjId = 0;
61             if (!isEmpty)
62                 newObjId = m_ids[position];
63             m_objs[position] = newObj;
64             m_ids[position] = id;
65             m_isWrapped[position] = isWrapped;
66             return newObjId;
67         }
68 
FindElement(object obj, out bool isEmpty, out bool isWrapped)69         private int FindElement(object obj, out bool isEmpty, out bool isWrapped)
70         {
71             isWrapped = false;
72             int position = ComputeStartPosition(obj);
73             for (int i = position; i != (position - 1); i++)
74             {
75                 if (m_objs[i] == null)
76                 {
77                     isEmpty = true;
78                     return i;
79                 }
80                 if (m_objs[i] == obj)
81                 {
82                     isEmpty = false;
83                     return i;
84                 }
85                 if (i == (m_objs.Length - 1))
86                 {
87                     isWrapped = true;
88                     i = -1;
89                 }
90             }
91             // m_obj must ALWAYS have at least one slot empty (null).
92             DiagnosticUtility.DebugAssert("Object table overflow");
93             throw System.Runtime.Serialization.DiagnosticUtility.ExceptionUtility.ThrowHelperError(XmlObjectSerializer.CreateSerializationException(SR.Format(SR.ObjectTableOverflow)));
94         }
95 
RemoveAt(int position)96         private void RemoveAt(int position)
97         {
98             int cacheSize = m_objs.Length;
99             int lastVacantPosition = position;
100             for (int next = (position == cacheSize - 1) ? 0 : position + 1; next != position; next++)
101             {
102                 if (m_objs[next] == null)
103                 {
104                     m_objs[lastVacantPosition] = null;
105                     m_ids[lastVacantPosition] = 0;
106                     m_isWrapped[lastVacantPosition] = false;
107                     return;
108                 }
109                 int nextStartPosition = ComputeStartPosition(m_objs[next]);
110                 // If we wrapped while placing an object, then it must be that the start position wasn't wrapped to begin with
111                 bool isNextStartPositionWrapped = next < position && !m_isWrapped[next];
112                 bool isLastVacantPositionWrapped = lastVacantPosition < position;
113 
114                 // We want to avoid moving objects in the cache if the next bucket position is wrapped, but the last vacant position isn't
115                 // 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
116                 if ((nextStartPosition <= lastVacantPosition && !(isNextStartPositionWrapped && !isLastVacantPositionWrapped)) ||
117                     (isLastVacantPositionWrapped && !isNextStartPositionWrapped))
118                 {
119                     m_objs[lastVacantPosition] = m_objs[next];
120                     m_ids[lastVacantPosition] = m_ids[next];
121                     // A wrapped object might become unwrapped if it moves from the front of the array to the end of the array
122                     m_isWrapped[lastVacantPosition] = m_isWrapped[next] && next > lastVacantPosition;
123                     lastVacantPosition = next;
124                 }
125                 if (next == (cacheSize - 1))
126                 {
127                     next = -1;
128                 }
129             }
130             // m_obj must ALWAYS have at least one slot empty (null).
131             DiagnosticUtility.DebugAssert("Object table overflow");
132             throw System.Runtime.Serialization.DiagnosticUtility.ExceptionUtility.ThrowHelperError(XmlObjectSerializer.CreateSerializationException(SR.Format(SR.ObjectTableOverflow)));
133         }
134 
ComputeStartPosition(object o)135         private int ComputeStartPosition(object o)
136         {
137             return (RuntimeHelpers.GetHashCode(o) & 0x7FFFFFFF) % m_objs.Length;
138         }
139 
Rehash()140         private void Rehash()
141         {
142             int size = GetPrime(m_objs.Length + 1); // The lookup does an inherent doubling
143             int[] oldIds = m_ids;
144             object[] oldObjs = m_objs;
145             m_ids = new int[size];
146             m_objs = new Object[size];
147             m_isWrapped = new bool[size];
148 
149             for (int j = 0; j < oldObjs.Length; j++)
150             {
151                 object obj = oldObjs[j];
152                 if (obj != null)
153                 {
154                     bool found, isWrapped;
155                     int position = FindElement(obj, out found, out isWrapped);
156                     m_objs[position] = obj;
157                     m_ids[position] = oldIds[j];
158                     m_isWrapped[position] = isWrapped;
159                 }
160             }
161         }
162 
GetPrime(int min)163         private static int GetPrime(int min)
164         {
165             for (int i = 0; i < primes.Length; i++)
166             {
167                 int prime = primes[i];
168                 if (prime >= min) return prime;
169             }
170 
171             return min;
172         }
173 
174         internal static readonly int[] primes =
175         {
176             3, 7, 17, 37, 89, 197, 431, 919, 1931, 4049, 8419, 17519, 36353,
177             75431, 156437, 324449, 672827, 1395263, 2893249, 5999471,
178             11998949, 23997907, 47995853, 95991737, 191983481, 383966977, 767933981, 1535867969,
179             2146435069, 0X7FEFFFFF
180             // 0X7FEFFFFF is not prime, but it is the largest possible array size. There's nowhere to go from here.
181         };
182     }
183 }