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 }