1 // ==++== 2 // 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // 5 // ==--== 6 /*============================================================ 7 ** 8 ** Class: ObjectIDGenerator 9 ** 10 ** 11 ** Purpose: ObjectIDGenerator is a simple id generator that keeps track of 12 ** objects with a hashtable. 13 ** 14 ** 15 ===========================================================*/ 16 namespace System.Runtime.Serialization { 17 using System; 18 using System.Runtime.CompilerServices; 19 using System.Runtime.Remoting; 20 using System.Diagnostics.Contracts; 21 22 [Serializable] 23 [System.Runtime.InteropServices.ComVisible(true)] 24 public class ObjectIDGenerator { 25 26 private const int numbins = 4; 27 28 internal int m_currentCount; 29 internal int m_currentSize; 30 internal long []m_ids; 31 internal Object []m_objs; 32 33 // Table of prime numbers to use as hash table sizes. Each entry is the 34 // smallest prime number larger than twice the previous entry. 35 private static readonly int[] sizes = { 36 5, 11, 29, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 37 102877, 205759, 411527, 823117, 1646237, 3292489, 6584983}; 38 39 // Constructs a new ObjectID generator, initializing all of the necessary variables. ObjectIDGenerator()40 public ObjectIDGenerator() { 41 m_currentCount=1; 42 m_currentSize = sizes[0]; 43 m_ids = new long[m_currentSize*numbins]; 44 m_objs = new Object[m_currentSize*numbins]; 45 } 46 47 // Determines where element obj lives, or should live, 48 // within the table. It calculates the hashcode and searches all of the 49 // bins where the given object could live. If it's not found within the bin, 50 // we rehash and go look for it in another bin. If we find the object, we 51 // set found to true and return it's position. If we can't find the object, 52 // we set found to false and return the position where the object should be inserted. 53 // FindElement(Object obj, out bool found)54 private int FindElement(Object obj, out bool found) { 55 //< 56 57 58 int hashcode = RuntimeHelpers.GetHashCode(obj); 59 int hashIncrement = (1+((hashcode&0x7FFFFFFF)%(m_currentSize-2))); 60 do { 61 int pos = ((hashcode&0x7FFFFFFF)%m_currentSize)*numbins; 62 63 for (int i=pos; i<pos+numbins; i++) { 64 if (m_objs[i]==null) { 65 found=false; 66 return i; 67 } 68 if (m_objs[i]==obj) { 69 found=true; 70 return i; 71 } 72 } 73 hashcode+=hashIncrement; 74 //the seemingly infinite loop must be revisited later. Currently it is assumed that 75 //always the array will be expanded (Rehash) when it is half full 76 }while(true); 77 } 78 79 80 // Gets the id for a particular object, generating one if needed. GetID calls 81 // FindElement to find out where the object lives or should live. If we didn't 82 // find the element, we generate an object id for it and insert the pair into the 83 // table. We return an Int64 for the object id. The out parameter firstTime 84 // is set to true if this is the first time that we have seen this object. 85 // GetId(Object obj, out bool firstTime)86 public virtual long GetId(Object obj, out bool firstTime) { 87 bool found; 88 long foundID; 89 90 if (obj==null) { 91 throw new ArgumentNullException("obj", Environment.GetResourceString("ArgumentNull_Obj")); 92 } 93 Contract.EndContractBlock(); 94 95 int pos = FindElement(obj, out found); 96 97 //We pull out foundID so that rehashing doesn't cause us to lose track of the id that we just found. 98 if (!found) { 99 #if FEATURE_REMOTING 100 BCLDebug.Trace("SER", "[ObjectIDGenerator.GetID] Adding objectid: ", (m_currentCount), " and hash code: ", 101 RuntimeHelpers.GetHashCode(obj), " at pos: ", pos, " Type: ", obj, "IsTransparentProxy: ", 102 System.Runtime.Remoting.RemotingServices.IsTransparentProxy(obj)); 103 #endif 104 //We didn't actually find the object, so we should need to insert it into 105 //the array and assign it an object id. 106 m_objs[pos]=obj; 107 m_ids[pos]=m_currentCount++; 108 foundID=m_ids[pos]; 109 if (m_currentCount > (m_currentSize*numbins)/2) { 110 Rehash(); 111 } 112 } else { 113 BCLDebug.Trace("SER", "[ObjectIDGenerator.GetID] Found objectid: ", (m_ids[pos]), " with hashcode: ", RuntimeHelpers.GetHashCode(obj), " Type: ", obj); 114 foundID = m_ids[pos]; 115 } 116 firstTime = !found; 117 118 return foundID; 119 } 120 121 // Checks to see if obj has already been assigned an id. If it has, 122 // we return that id, otherwise we return 0. 123 // HasId(Object obj, out bool firstTime)124 public virtual long HasId(Object obj, out bool firstTime) { 125 bool found; 126 127 if (obj==null) { 128 throw new ArgumentNullException("obj", Environment.GetResourceString("ArgumentNull_Obj")); 129 } 130 Contract.EndContractBlock(); 131 132 int pos = FindElement(obj, out found); 133 if (found) { 134 firstTime = false; 135 return m_ids[pos]; 136 } 137 firstTime=true; 138 return 0; 139 } 140 141 // Rehashes the table by finding the next larger size in the list provided, 142 // allocating two new arrays of that size and rehashing all of the elements in 143 // the old arrays into the new ones. Expensive but necessary. 144 // Rehash()145 private void Rehash() { 146 int i,pos; 147 long [] newIds; 148 long [] oldIds; 149 Object[] newObjs; 150 Object[] oldObjs; 151 bool found; 152 int currSize; 153 154 for (i=0, currSize=m_currentSize; i<sizes.Length && sizes[i]<=currSize; i++); 155 if (i==sizes.Length) { 156 //We just walked off the end of the array, what would you like to do now? 157 //We're pretty much hosed at this point, so just keep going. 158 throw new SerializationException(Environment.GetResourceString("Serialization_TooManyElements")); 159 } 160 m_currentSize = sizes[i]; 161 162 newIds = new long[m_currentSize*numbins]; 163 newObjs = new Object[m_currentSize*numbins]; 164 165 oldIds = m_ids; 166 oldObjs = m_objs; 167 168 m_ids = newIds; 169 m_objs = newObjs; 170 171 for (int j=0; j<oldObjs.Length; j++) { 172 if (oldObjs[j]!=null) { 173 pos = FindElement(oldObjs[j], out found); 174 m_objs[pos]=oldObjs[j]; 175 m_ids[pos] = oldIds[j]; 176 } 177 } 178 } 179 } 180 181 182 183 184 } 185 186