Title: Hashtable of types for R2R modules

Description: This change replaces the hashtable of types that we dynamically build at module load time with a statically built hashtable at crossgen time, for R2R modules. Typedef tokens and exported type tokens are stored in that hashtable, hashed by their full type name.

Changes include:
- Adding support for NativeFormat hashtables (NativeFormat hashtable reader and writer + supporting functionalities)
- Changes to prevent the allocation and building of m_pAvailableClasses and m_pAvailableClassesCaseIns for a R2R module
- Logic in crossgen to build the hashtable of types, using the NativeFormat (table saved to a new section)
- Refactoring the type lookup functions to return results in a HashedTypeEntry data structure, which supports token based results, as well as EEClassHashEntry_t* based results
- Changes/Cleanup to the ClassLoader::GetClassValue to support the new lookup type
- Fixed small bugs in the std implementation
- Fallback to old hashtable lookup algorithm supported for:
	1) Case insensitive type loading
	2) R2R image built with older version of crossgen (not having static hashtable)

Tested following scenarios:
	- Token based lookups
	- Type name based lookups (Type.GetType API), including case insensitive scenarios
	- Nested types
	- Forwarded types (and forwarded nested types), up to 2 levels of forwarding
	- Old R2R image created with previous version of crossgen

1 files changed, 82 insertions, 0 deletions

diff --git a/src/zap/nativeformatwriter.h b/src/zap/nativeformatwriter.h
index 49349a0b1a..99db10d210 100644
--- a/src/zap/nativeformatwriter.h
+++ b/src/zap/nativeformatwriter.h
@@ -167,6 +167,11 @@ namespace NativeFormat
             RollbackTo(offset);
         }
 
+        void PatchByteAt(int offset, byte value)
+        {
+            m_Buffer[offset] = value;
+        }
+
         //
         // Same encoding as what's used by CTL
         //
@@ -218,6 +223,26 @@ namespace NativeFormat
 
 
     //
+    // Data structure building blocks
+    //
+
+    class UnsignedConstant : public Vertex
+    {
+        unsigned m_value;
+
+    public:
+        UnsignedConstant(unsigned value)
+            : m_value(value)
+        {
+        }
+
+        virtual void Save(NativeWriter * pWriter)
+        {
+            pWriter->WriteUnsigned(m_value);
+        }
+    };
+
+    //
     // Sparse array. Good for random access based on index
     //
     class VertexArray : public Vertex
@@ -270,4 +295,61 @@ namespace NativeFormat
 
         virtual void Save(NativeWriter * pWriter);
     };
+
+    //
+    // Hashtable. Good for random access based on hashcode + key
+    //
+    class VertexHashtable : public Vertex
+    {
+        struct Entry
+        {
+            Entry()
+                : offset(-1), hashcode(0), pVertex(NULL)
+            {
+            }
+
+            Entry(unsigned hashcode, Vertex * pVertex)
+                : offset(0), hashcode(hashcode), pVertex(pVertex)
+            {
+            }
+
+            int offset;
+
+            unsigned hashcode;
+            Vertex * pVertex;
+        };
+
+        vector<Entry> m_Entries;
+
+        // How many entries to target per bucket. Higher fill factor means smaller size, but worse runtime perf.
+        int m_nFillFactor;
+
+        // Number of buckets choosen for the table. Must be power of two. 0 means that the table is still open for mutation.
+        int m_nBuckets;
+
+        // Current size of index entry
+        int m_entryIndexSize; // 0 - uint8, 1 - uint16, 2 - uint32
+
+        void ComputeLayout();
+
+    public:
+        static const int DefaultFillFactor = 13;
+
+        VertexHashtable(int fillFactor = DefaultFillFactor)
+        {
+            m_nBuckets = 0;
+
+            m_nFillFactor = fillFactor;
+        }
+
+        void Append(unsigned hashcode, Vertex * pElement)
+        {
+            // The table needs to be open for mutation
+            assert(m_nBuckets == 0);
+
+            m_Entries.push_back(Entry(hashcode, pElement));
+        }
+
+        virtual void Save(NativeWriter * pWriter);
+    };
 };