The Labs \ Source Viewer \ SSCLI \ System.Runtime.Serialization \ ObjectIDGenerator

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

Developer Fusion