--- a/src/core/model/type-id.cc	Thu Jul 18 12:04:27 2013 -0700
+++ b/src/core/model/type-id.cc	Thu Jul 18 12:01:05 2013 -0700
@@ -17,21 +17,56 @@
  *
  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
  */
+#include "log.h"  // NS_ASSERT and NS_LOG
+#include "hash.h"
 #include "type-id.h"
 #include "singleton.h"
 #include "trace-source-accessor.h"
-#include "log.h"
+
+#include <map>
 #include <vector>
 #include <sstream>
+#include <iomanip>
 
 /*********************************************************************
  *         Helper code
  *********************************************************************/
 
-NS_LOG_COMPONENT_DEFINE ("TypeID");
+namespace ns3 {
+
+NS_LOG_COMPONENT_DEFINE ("TypeId");
+
+// IidManager needs to be in ns3 namespace for NS_ASSERT and NS_LOG
+// to find g_log
 
-namespace {
-
+/**
+ * \brief TypeId information manager
+ *
+ * Information records are stored in a vector.  Name and hash lookup
+ * are performed by maps to the vector index.
+ *
+ * \internal
+ * <b>Hash Chaining</b>
+ *
+ * We require all types to produce distinct hashes. What if we encounter
+ * two types that produce the same hash value?  As we move to a
+ * federated distribution model (the App store), it becomes increasingly
+ * likely that the core ns3 team *won't* discover this in test builds.
+ * Therefore, we need to handle this case explicitly.
+ *
+ * Note, we expect this to be *extremely* rare.  As of this writing we
+ * have ~400 < 2^9 types, so the probability of getting a collision
+ * when we introduce a new type is ~2^9/2^31 = 2^-22, assuming we
+ * reserve 31 bits for the hash, and one bit for chaining.  Even with
+ * double the number of types the probability of having a collision
+ * is only 2 x 10^-4.  The probability for a three-fold collision is
+ * 1 x 10^-10.
+ *
+ * Therefore, we'll handle one collision explicitly by reserving
+ * the high order bit of the hash value, and assert on higher level
+ * collisions.  The three-fold collision probability should be an
+ * acceptablly small error rate.
+ */
 class IidManager
 {
 public:
@@ -39,13 +74,15 @@
   uint16_t AllocateUid (std::string name);
   void SetParent (uint16_t uid, uint16_t parent);
   void SetGroupName (uint16_t uid, std::string groupName);
-  void AddConstructor (uint16_t uid, ns3::Callback<ns3::ObjectBase *> callback);
+  void AddConstructor (uint16_t uid, Callback<ObjectBase *> callback);
   void HideFromDocumentation (uint16_t uid);
   uint16_t GetUid (std::string name) const;
+  uint16_t GetUid (TypeId::hash_t hash) const;
   std::string GetName (uint16_t uid) const;
+  TypeId::hash_t GetHash (uint16_t uid) const;
   uint16_t GetParent (uint16_t uid) const;
   std::string GetGroupName (uint16_t uid) const;
-  ns3::Callback<ns3::ObjectBase *> GetConstructor (uint16_t uid) const;
+  Callback<ObjectBase *> GetConstructor (uint16_t uid) const;
   bool HasConstructor (uint16_t uid) const;
   uint32_t GetRegisteredN (void) const;
   uint16_t GetRegistered (uint32_t i) const;
@@ -53,41 +90,54 @@
                      std::string name,
                      std::string help, 
                      uint32_t flags,
-                     ns3::Ptr<const ns3::AttributeValue> initialValue,
-                     ns3::Ptr<const ns3::AttributeAccessor> spec,
-                     ns3::Ptr<const ns3::AttributeChecker> checker);
+                     Ptr<const AttributeValue> initialValue,
+                     Ptr<const AttributeAccessor> spec,
+                     Ptr<const AttributeChecker> checker);
   void SetAttributeInitialValue(uint16_t uid,
                                 uint32_t i,
-                                ns3::Ptr<const ns3::AttributeValue> initialValue);
+                                Ptr<const AttributeValue> initialValue);
   uint32_t GetAttributeN (uint16_t uid) const;
-  struct ns3::TypeId::AttributeInformation GetAttribute(uint16_t uid, uint32_t i) const;
+  struct TypeId::AttributeInformation GetAttribute(uint16_t uid, uint32_t i) const;
   void AddTraceSource (uint16_t uid,
                        std::string name, 
                        std::string help,
-                       ns3::Ptr<const ns3::TraceSourceAccessor> accessor);
+                       Ptr<const TraceSourceAccessor> accessor);
   uint32_t GetTraceSourceN (uint16_t uid) const;
-  struct ns3::TypeId::TraceSourceInformation GetTraceSource(uint16_t uid, uint32_t i) const;
+  struct TypeId::TraceSourceInformation GetTraceSource(uint16_t uid, uint32_t i) const;
   bool MustHideFromDocumentation (uint16_t uid) const;
 
 private:
   bool HasTraceSource (uint16_t uid, std::string name);
   bool HasAttribute (uint16_t uid, std::string name);
+  static TypeId::hash_t Hasher (const std::string name);
 
   struct IidInformation {
     std::string name;
+    TypeId::hash_t hash;
     uint16_t parent;
     std::string groupName;
     bool hasConstructor;
-    ns3::Callback<ns3::ObjectBase *> constructor;
+    Callback<ObjectBase *> constructor;
     bool mustHideFromDocumentation;
-    std::vector<struct ns3::TypeId::AttributeInformation> attributes;
-    std::vector<struct ns3::TypeId::TraceSourceInformation> traceSources;
+    std::vector<struct TypeId::AttributeInformation> attributes;
+    std::vector<struct TypeId::TraceSourceInformation> traceSources;
   };
   typedef std::vector<struct IidInformation>::const_iterator Iterator;
 
   struct IidManager::IidInformation *LookupInformation (uint16_t uid) const;
 
   std::vector<struct IidInformation> m_information;
+
+  typedef std::map<std::string, uint16_t> namemap_t;
+  namemap_t m_namemap;
+
+  typedef std::map<TypeId::hash_t, uint16_t> hashmap_t;
+  hashmap_t m_hashmap;
+
+  
+  // To handle the first collision, we reserve the high bit as a
+  // chain flag:
+  enum { HashChainFlag = 0x80000000};
 };
 
 IidManager::IidManager ()
@@ -95,22 +145,70 @@
   NS_LOG_FUNCTION (this);
 }
 
+  //static
+TypeId::hash_t
+IidManager::Hasher (const std::string name)
+{
+  static ns3::Hasher hasher ( Create<Hash::Function::Murmur3> () );
+  return hasher.clear ().GetHash32 (name);
+}
+  
 uint16_t
 IidManager::AllocateUid (std::string name)
 {
   NS_LOG_FUNCTION (this << name);
-  uint16_t j = 1;
-  for (Iterator i = m_information.begin (); i != m_information.end (); i++)
-    {
-      if (i->name == name)
-        {
-          NS_FATAL_ERROR ("Trying to allocate twice the same uid: " << name);
-          return 0;
-        }
-      j++;
-    }
-  struct IidInformation information;
+  // Type names are definitive: equal names are equal types
+  NS_ASSERT_MSG (m_namemap.count (name) == 0,
+                 "Trying to allocate twice the same uid: " << name);
+  
+  TypeId::hash_t hash = Hasher (name) & (~HashChainFlag);
+  if (m_hashmap.count (hash) == 1) {
+    NS_LOG_ERROR ("Hash chaining TypeId for '" << name << "'.  "
+                 << "This is not a bug, but is extremely unlikely.  "
+                 << "Please contact the ns3 developers.");
+    // ns3 developer contacted about this message:
+    // You have four options (in order of difficulty):
+    //   1. Let it ride, and play the odds that a third collision
+    //        never appears.
+    //   2. Change the name of the new (or old) tag, even trivially, to
+    //        remove the collision.
+    //   3. Switch to 64-bit hashes.
+    //   4. Implement 2-bit (or higher) chaining.
+    //
+    //  Oh, by the way, I owe you a beer, since I bet Mathieu that
+    //  this would never happen..  -- Peter Barnes, LLNL
+
+    NS_ASSERT_MSG (m_hashmap.count (hash | HashChainFlag) == 0,
+                   "Triplicate hash detected while chaining TypeId for '"
+                   << name
+                   << "'. Please contact the ns3 developers for assistance.");
+    // ns3 developer contacted about this message:
+    // You have three options: #2-4 above.
+    //
+    // Oh, by the way, I have no idea how this crazy hashing idea got
+    // into ns3.  -- Peter Barnes, LLNL
+    
+    // Alphabetize the two types, so it's deterministic
+    struct IidInformation * hinfo = LookupInformation (GetUid (hash));
+    if (name > hinfo->name)
+      { // new type gets chained
+        NS_LOG_LOGIC ("New TypeId '" << name << "' getting chained.");
+        hash = hash | HashChainFlag;
+      }
+    else
+      { // chain old type
+        NS_LOG_LOGIC ("Old TypeId '" << hinfo->name << "' getting chained.");
+        uint32_t oldUid = GetUid (hinfo->hash);
+        m_hashmap.erase (m_hashmap.find (hinfo->hash));
+        hinfo->hash = hash | HashChainFlag;
+        m_hashmap.insert (std::make_pair (hinfo->hash, oldUid));
+        // leave new hash unchained
+      }
+  }
+
+ struct IidInformation information;
   information.name = name;
+  information.hash = hash;
   information.parent = 0;
   information.groupName = "";
   information.hasConstructor = false;
@@ -118,6 +216,10 @@
   m_information.push_back (information);
   uint32_t uid = m_information.size ();
   NS_ASSERT (uid <= 0xffff);
+
+  // Add to both maps:
+  m_namemap.insert (std::make_pair (name, uid));
+  m_hashmap.insert (std::make_pair (hash, uid));
   return uid;
 }
 
@@ -153,7 +255,7 @@
 }
 
 void 
-IidManager::AddConstructor (uint16_t uid, ns3::Callback<ns3::ObjectBase *> callback)
+IidManager::AddConstructor (uint16_t uid, Callback<ObjectBase *> callback)
 {
   NS_LOG_FUNCTION (this << uid << &callback);
   struct IidInformation *information = LookupInformation (uid);
@@ -169,17 +271,28 @@
 IidManager::GetUid (std::string name) const
 {
   NS_LOG_FUNCTION (this << name);
-  uint32_t j = 1;
-  for (Iterator i = m_information.begin (); i != m_information.end (); i++)
+  namemap_t::const_iterator it = m_namemap.find (name);
+  if (it != m_namemap.end ())
+    {
+      return it->second;
+    }
+  else
     {
-      if (i->name == name)
-        {
-          NS_ASSERT (j <= 0xffff);
-          return j;
-        }
-      j++;
+      return 0;
     }
-  return 0;
+}
+uint16_t 
+IidManager::GetUid (TypeId::hash_t hash) const
+{
+  hashmap_t::const_iterator it = m_hashmap.find (hash);
+  if (it != m_hashmap.end ())
+    {
+    return it->second;
+    }
+  else
+    { // hash not found 
+      return 0;
+    }
 }
 std::string 
 IidManager::GetName (uint16_t uid) const
@@ -188,6 +301,13 @@
   struct IidInformation *information = LookupInformation (uid);
   return information->name;
 }
+TypeId::hash_t
+IidManager::GetHash (uint16_t uid) const
+{
+  NS_LOG_FUNCTION (this << uid);
+  struct IidInformation *information = LookupInformation (uid);
+  return information->hash;
+}
 uint16_t 
 IidManager::GetParent (uint16_t uid) const
 {
@@ -203,7 +323,7 @@
   return information->groupName;
 }
 
-ns3::Callback<ns3::ObjectBase *> 
+Callback<ObjectBase *> 
 IidManager::GetConstructor (uint16_t uid) const
 {
   NS_LOG_FUNCTION (this << uid);
@@ -244,7 +364,7 @@
   struct IidInformation *information  = LookupInformation (uid);
   while (true)
     {
-      for (std::vector<struct ns3::TypeId::AttributeInformation>::const_iterator i = information->attributes.begin ();
+      for (std::vector<struct TypeId::AttributeInformation>::const_iterator i = information->attributes.begin ();
            i != information->attributes.end (); ++i)
         {
           if (i->name == name)
@@ -269,9 +389,9 @@
                           std::string name,
                           std::string help, 
                           uint32_t flags,
-                          ns3::Ptr<const ns3::AttributeValue> initialValue,
-                          ns3::Ptr<const ns3::AttributeAccessor> accessor,
-                          ns3::Ptr<const ns3::AttributeChecker> checker)
+                          Ptr<const AttributeValue> initialValue,
+                          Ptr<const AttributeAccessor> accessor,
+                          Ptr<const AttributeChecker> checker)
 {
   NS_LOG_FUNCTION (this << uid << name << help << flags << initialValue << accessor << checker);
   struct IidInformation *information = LookupInformation (uid);
@@ -280,7 +400,7 @@
       NS_FATAL_ERROR ("Attribute \"" << name << "\" already registered on tid=\"" << 
                       information->name << "\"");
     }
-  struct ns3::TypeId::AttributeInformation info;
+  struct TypeId::AttributeInformation info;
   info.name = name;
   info.help = help;
   info.flags = flags;
@@ -293,7 +413,7 @@
 void 
 IidManager::SetAttributeInitialValue(uint16_t uid,
                                      uint32_t i,
-                                     ns3::Ptr<const ns3::AttributeValue> initialValue)
+                                     Ptr<const AttributeValue> initialValue)
 {
   NS_LOG_FUNCTION (this << uid << i << initialValue);
   struct IidInformation *information = LookupInformation (uid);
@@ -310,7 +430,7 @@
   struct IidInformation *information = LookupInformation (uid);
   return information->attributes.size ();
 }
-struct ns3::TypeId::AttributeInformation 
+struct TypeId::AttributeInformation 
 IidManager::GetAttribute(uint16_t uid, uint32_t i) const
 {
   NS_LOG_FUNCTION (this << uid << i);
@@ -327,7 +447,7 @@
   struct IidInformation *information  = LookupInformation (uid);
   while (true)
     {
-      for (std::vector<struct ns3::TypeId::TraceSourceInformation>::const_iterator i = information->traceSources.begin ();
+      for (std::vector<struct TypeId::TraceSourceInformation>::const_iterator i = information->traceSources.begin ();
            i != information->traceSources.end (); ++i)
         {
           if (i->name == name)
@@ -351,7 +471,7 @@
 IidManager::AddTraceSource (uint16_t uid,
                             std::string name, 
                             std::string help,
-                            ns3::Ptr<const ns3::TraceSourceAccessor> accessor)
+                            Ptr<const TraceSourceAccessor> accessor)
 {
   NS_LOG_FUNCTION (this << uid << name << help << accessor);
   struct IidInformation *information  = LookupInformation (uid);
@@ -360,7 +480,7 @@
       NS_FATAL_ERROR ("Trace source \"" << name << "\" already registered on tid=\"" << 
                       information->name << "\"");
     }
-  struct ns3::TypeId::TraceSourceInformation source;
+  struct TypeId::TraceSourceInformation source;
   source.name = name;
   source.help = help;
   source.accessor = accessor;
@@ -373,7 +493,7 @@
   struct IidInformation *information = LookupInformation (uid);
   return information->traceSources.size ();
 }
-struct ns3::TypeId::TraceSourceInformation 
+struct TypeId::TraceSourceInformation 
 IidManager::GetTraceSource(uint16_t uid, uint32_t i) const
 {
   NS_LOG_FUNCTION (this << uid << i);
@@ -389,7 +509,7 @@
   return information->mustHideFromDocumentation;
 }
 
-} // anonymous namespace
+} // namespace ns3
 
 namespace ns3 {
 
@@ -431,6 +551,25 @@
   *tid = TypeId (uid);
   return true;
 }
+TypeId
+TypeId::LookupByHash (hash_t hash)
+{
+  uint16_t uid = Singleton<IidManager>::Get ()->GetUid (hash);
+  NS_ASSERT_MSG (uid != 0, "Assert in TypeId::LookupByHash: 0x"
+                 << std::hex << hash << std::dec << " not found");
+  return TypeId (uid);
+}
+bool
+TypeId::LookupByHashFailSafe (hash_t hash, TypeId *tid)
+{
+  uint16_t uid = Singleton<IidManager>::Get ()->GetUid (hash);
+  if (uid == 0)
+    {
+      return false;
+    }
+  *tid = TypeId (uid);
+  return true;
+}
 
 uint32_t 
 TypeId::GetRegisteredN (void)
@@ -522,6 +661,13 @@
   return name;
 }
 
+TypeId::hash_t
+TypeId::GetHash (void) const
+{
+  hash_t hash = Singleton<IidManager>::Get ()->GetHash (m_tid);
+  return hash;
+}
+
 bool 
 TypeId::HasConstructor (void) const
 {

--- a/src/core/model/type-id.h	Thu Jul 18 12:04:27 2013 -0700
+++ b/src/core/model/type-id.h	Thu Jul 18 12:01:05 2013 -0700
@@ -25,6 +25,7 @@
 #include "trace-source-accessor.h"
 #include "attribute-helper.h"
 #include "callback.h"
+#include "hash.h"
 #include <string>
 #include <stdint.h>
 
@@ -40,6 +41,10 @@
  *  - the base class of the subclass
  *  - the set of accessible constructors in the subclass
  *  - the set of 'attributes' accessible in the subclass
+ *
+ * \internal
+ *  See the discussion in IidManager about hash chaining of TypeId's.
+ *
  */
 class TypeId
 {
@@ -57,18 +62,23 @@
     std::string name;
     std::string help;
     uint32_t flags;
-    ns3::Ptr<const ns3::AttributeValue> originalInitialValue;
-    ns3::Ptr<const ns3::AttributeValue> initialValue;
-    ns3::Ptr<const ns3::AttributeAccessor> accessor;
-    ns3::Ptr<const ns3::AttributeChecker> checker;
+    Ptr<const AttributeValue> originalInitialValue;
+    Ptr<const AttributeValue> initialValue;
+    Ptr<const AttributeAccessor> accessor;
+    Ptr<const AttributeChecker> checker;
   };
   struct TraceSourceInformation {
     std::string name;
     std::string help;
-    ns3::Ptr<const ns3::TraceSourceAccessor> accessor;
+    Ptr<const TraceSourceAccessor> accessor;
   };
 
   /**
+   * Type of hash values
+   */
+  typedef uint32_t hash_t;
+
+  /**
    * \param name the name of the requested TypeId
    * \returns the unique id associated with the requested
    *          name. 
@@ -84,6 +94,21 @@
    * \returns true if the requested name was found, false otherwise.
    */
   static bool LookupByNameFailSafe (std::string name, TypeId *tid);
+  /**
+   * \param hash the hash to lookup
+   * \returns the unique id associated with the requested hash.
+   *
+   * This method cannot fail: it will crash if the input 
+   * hash does not match an existing TypeId.
+   */
+  static TypeId LookupByHash (hash_t hash);
+  /**
+   * \param hash the hash of the requested TypeId
+   * \param tid a pointer to the TypeId instance where the 
+   *        result of this function should be stored.
+   * \returns true if the requested hash was found, false otherwise.
+   */
+  static bool LookupByHashFailSafe (hash_t hash, TypeId *tid);
 
   /**
    * \returns the number of TypeId instances registered.
@@ -138,6 +163,11 @@
   std::string GetName (void) const;
 
   /**
+   * \returns the hash of this interface.
+   */
+  hash_t GetHash (void) const;
+
+  /**
    * \returns true if this TypeId has a constructor
    */
   bool HasConstructor (void) const;

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/core/test/type-id-test-suite.cc	Thu Jul 18 12:01:05 2013 -0700
@@ -0,0 +1,321 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Lawrence Livermore National Laboratory
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Peter D. Barnes, Jr. <pdbarnes@llnl.gov>
+ */
+
+#include <iostream>
+#include <iomanip>
+#include <ctime>
+
+#include "ns3/type-id.h"
+#include "ns3/test.h"
+#include "ns3/log.h"
+
+using namespace std;
+
+namespace ns3 {
+
+
+const std::string suite("type-id: ");
+  
+//----------------------------
+//
+// Test for uniqueness of all TypeIds
+
+class UniqueTypeIdTestCase : public TestCase
+{
+public:
+  UniqueTypeIdTestCase ();
+  virtual ~UniqueTypeIdTestCase ();
+private:
+  virtual void DoRun (void);
+  enum { HashChainFlag = 0x80000000};
+};
+
+UniqueTypeIdTestCase::UniqueTypeIdTestCase ()
+  : TestCase ("Check uniqueness of all TypeIds")
+{
+}
+
+UniqueTypeIdTestCase::~UniqueTypeIdTestCase ()
+{
+}
+
+void
+UniqueTypeIdTestCase::DoRun (void)
+{
+  cout << suite << endl;
+  cout << suite << GetName () << endl;
+  
+  // Use same custom hasher as TypeId
+  ns3::Hasher hasher = ns3::Hasher ( Create<Hash::Function::Murmur3> () );
+  
+  uint32_t nids = TypeId::GetRegisteredN ();
+
+  cout << suite << "UniqueTypeIdTestCase: nids: " << nids << endl;
+  cout << suite << "TypeId list:" << endl;
+  cout << suite << "TypeId  Chain  hash          Name" << endl;
+  
+  for (uint32_t i = 0; i < nids; ++i)
+    {
+      const TypeId tid = TypeId::GetRegistered (i);
+      cout << suite << "" << std::setw(6) << tid.GetUid ();
+      if (tid.GetHash () & HashChainFlag)
+        {
+          cout << "  chain";
+        }
+      else
+        {
+          cout << "       ";
+        }
+      cout << "  0x"     << std::setfill ('0') << std::hex << std::setw (8)
+           << tid.GetHash () << std::dec << std::setfill (' ')
+           << "    "     << tid.GetName ()
+           << endl;
+
+      NS_TEST_ASSERT_MSG_EQ (tid.GetUid (),
+                             TypeId::LookupByName (tid.GetName ()).GetUid (),
+                             "LookupByName returned different TypeId for "
+                             << tid.GetName ());
+
+      // Mask off HashChainFlag in this test, since tid might have been chained
+      NS_TEST_ASSERT_MSG_EQ ((tid.GetHash () & (~HashChainFlag)),
+                             (hasher.clear ().GetHash32 (tid.GetName ()) & (~HashChainFlag)),
+                             "TypeId .hash and Hash32 (.name) unequal for "
+                             << tid.GetName ());
+
+      NS_TEST_ASSERT_MSG_EQ (tid.GetUid (),
+                             TypeId::LookupByHash (tid.GetHash ()).GetUid (),
+                             "LookupByHash returned different TypeId for "
+                             << tid.GetName ());
+      
+    }
+
+  cout << suite << "<-- end TypeId list -->" << endl;
+}
+
+
+//----------------------------
+//
+// Collision test
+
+class CollisionTestCase : public TestCase
+{
+public:
+  CollisionTestCase ();
+  virtual ~CollisionTestCase ();
+private:
+  virtual void DoRun (void);
+  enum { HashChainFlag = 0x80000000};
+};
+
+CollisionTestCase::CollisionTestCase ()
+  : TestCase ("Check behavour when type names collide")
+{
+}
+
+CollisionTestCase::~CollisionTestCase ()
+{
+}
+
+void
+CollisionTestCase::DoRun (void)
+{
+  cout << suite << endl;
+  cout << suite << GetName () << endl;
+  
+  // Register two types whose hashes collide, in alphabetical order
+  // Murmur3 collision from /usr/share/dict/web2
+  string t1Name = "daemon";
+  string t2Name = "unerring";
+  cout << suite << "creating colliding types "
+       << "'" << t1Name << "', '" << t2Name << "'"
+       << " in alphabetical order:"
+       << endl;
+  TypeId t1 (t1Name.c_str ());
+  TypeId t2 (t2Name.c_str ());
+
+  // Check that they are alphabetical: t1 name < t2 name
+  NS_TEST_ASSERT_MSG_EQ ( (t1.GetHash () & HashChainFlag), 0,
+                         "First and lesser TypeId has HashChainFlag set");
+  cout << suite << "collision: first,lesser  not chained: OK" << endl;
+
+  NS_TEST_ASSERT_MSG_NE ( (t2.GetHash () & HashChainFlag), 0,
+                         "Second and greater TypeId does not have HashChainFlag set");
+  cout << suite << "collision: second,greater    chained: OK" << endl;
+
+
+  // Register colliding types in reverse alphabetical order
+  // Murmur3 collision from /usr/share/dict/web2
+  string t3Name = "trigonon";
+  string t4Name = "seriation";
+  cout << suite << "creating colliding types "
+       << "'" << t3Name << "', '" << t4Name << "'"
+       << " in reverse alphabetical order:"
+       << endl;
+  TypeId t3 (t3Name.c_str ());
+  TypeId t4 (t4Name.c_str ());
+
+  // Check that they are alphabetical: t3 name > t4 name
+  NS_TEST_ASSERT_MSG_NE ( (t3.GetHash () & HashChainFlag), 0,
+                          "First and greater TypeId does not have HashChainFlag set");
+  cout << suite << "collision: first,greater     chained: OK" << endl;
+
+  NS_TEST_ASSERT_MSG_EQ ( (t4.GetHash () & HashChainFlag), 0,
+                          "Second and lesser TypeId has HashChainFlag set");
+  cout << suite << "collision: second,lesser not chained: OK" << endl;
+
+  /** TODO Extra credit:  register three types whose hashes collide
+   *
+   *  None found in /usr/share/dict/web2
+   */
+  
+}
+  
+  
+//----------------------------
+//
+// Performance test
+
+class LookupTimeTestCase : public TestCase
+{
+public:
+  LookupTimeTestCase ();
+  virtual ~LookupTimeTestCase ();
+private:
+  void DoRun (void);
+  void DoSetup (void);
+  void Report (const std::string how, const uint32_t delta) const ;
+
+  enum { REPETITIONS = 100000 };
+};
+
+LookupTimeTestCase::LookupTimeTestCase ()
+  : TestCase ("Measure average lookup time")
+{
+}
+
+LookupTimeTestCase::~LookupTimeTestCase ()
+{
+}
+
+void
+LookupTimeTestCase::DoRun (void)
+{
+  cout << suite << endl;
+  cout << suite << GetName () << endl;
+  
+  uint32_t nids = TypeId::GetRegisteredN ();
+
+  int start = clock ();
+  for (uint32_t j = 0; j < REPETITIONS; ++j)
+    {
+      for (uint32_t i = 0; i < nids; ++i)
+        {
+          const TypeId tid = TypeId::GetRegistered (i);
+          const TypeId sid = TypeId::LookupByName (tid.GetName ());
+        }
+  }
+  int stop = clock ();
+  Report ("name", stop - start);
+
+  start = clock ();
+  for (uint32_t j = 0; j < REPETITIONS; ++j)
+    {
+      for (uint32_t i = 0; i < nids; ++i)
+        {
+          const TypeId tid = TypeId::GetRegistered (i);
+          const TypeId sid = TypeId::LookupByHash (tid.GetHash ());
+        }
+  }
+  stop = clock ();
+  Report ("hash", stop - start);
+  
+}
+
+void
+LookupTimeTestCase::DoSetup (void)
+{
+  uint32_t nids = TypeId::GetRegisteredN ();
+  
+  cout << suite << "Lookup time: reps: " << REPETITIONS
+       << ", num TypeId's: " << nids
+       << endl;
+
+}
+
+void
+LookupTimeTestCase::Report (const std::string how,
+                            const uint32_t    delta) const
+{
+  double nids = TypeId::GetRegisteredN ();
+  double reps = nids * REPETITIONS;
+  
+  double per = 1E6 * double(delta) / (reps * double(CLOCKS_PER_SEC));
+  
+  cout << suite << "Lookup time: by " << how << ": "
+       << "ticks: " << delta
+       << "\tper: "   << per
+       << " microsec/lookup"
+       << endl;					
+}
+
+
+//----------------------------
+//
+// TypeId test suites
+
+class TypeIdTestSuite : public TestSuite
+{
+public:
+  TypeIdTestSuite ();
+};
+  
+TypeIdTestSuite::TypeIdTestSuite ()
+  : TestSuite ("type-id", UNIT)
+{
+  // Turn on logging, so we see the result of collisions
+  LogComponentEnable ("TypeId", ns3::LogLevel(LOG_ERROR|LOG_PREFIX_FUNC));
+  
+  // If the CollisionTestCase is performed before the
+  // UniqueIdTestCase, the artificial collisions added by
+  // CollisionTestCase will show up in the list of TypeIds
+  // as chained.
+  AddTestCase (new UniqueTypeIdTestCase);
+  AddTestCase (new CollisionTestCase);
+}
+
+static TypeIdTestSuite g_TypeIdTestSuite;  
+  
+
+class TypeIdPerformanceSuite : public TestSuite
+{
+public:
+  TypeIdPerformanceSuite ();
+};
+  
+TypeIdPerformanceSuite::TypeIdPerformanceSuite ()
+  : TestSuite ("type-id-perf", PERFORMANCE)
+{
+  AddTestCase (new LookupTimeTestCase);
+}
+
+static TypeIdPerformanceSuite g_TypeIdPerformanceSuite;  
+  
+
+}  // namespace ns3

--- a/src/core/wscript	Thu Jul 18 12:04:27 2013 -0700
+++ b/src/core/wscript	Thu Jul 18 12:01:05 2013 -0700
@@ -178,6 +178,7 @@
         'test/type-traits-test-suite.cc',
         'test/watchdog-test-suite.cc',
         'test/hash-test-suite.cc',
+        'test/type-id-test-suite.cc',
         ]
 
     headers = bld(features='ns3header')