Hashed TypeId
authorPeter D. Barnes, Jr. <barnes26@llnl.gov>
Thu, 18 Jul 2013 12:01:05 -0700
changeset 9959721b5b528cc0
parent 9958 83a573f72a4c
child 9960 e03e5de1edc9
Hashed TypeId

Speed LookupByName with std::map, add LookupByHash
Hash chaining, alphabetized
TypeId test suite
src/core/model/type-id.cc
src/core/model/type-id.h
src/core/test/type-id-test-suite.cc
src/core/wscript
     1.1 --- a/src/core/model/type-id.cc	Thu Jul 18 12:04:27 2013 -0700
     1.2 +++ b/src/core/model/type-id.cc	Thu Jul 18 12:01:05 2013 -0700
     1.3 @@ -17,21 +17,56 @@
     1.4   *
     1.5   * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
     1.6   */
     1.7 +#include "log.h"  // NS_ASSERT and NS_LOG
     1.8 +#include "hash.h"
     1.9  #include "type-id.h"
    1.10  #include "singleton.h"
    1.11  #include "trace-source-accessor.h"
    1.12 -#include "log.h"
    1.13 +
    1.14 +#include <map>
    1.15  #include <vector>
    1.16  #include <sstream>
    1.17 +#include <iomanip>
    1.18  
    1.19  /*********************************************************************
    1.20   *         Helper code
    1.21   *********************************************************************/
    1.22  
    1.23 -NS_LOG_COMPONENT_DEFINE ("TypeID");
    1.24 +namespace ns3 {
    1.25  
    1.26 -namespace {
    1.27 +NS_LOG_COMPONENT_DEFINE ("TypeId");
    1.28  
    1.29 +// IidManager needs to be in ns3 namespace for NS_ASSERT and NS_LOG
    1.30 +// to find g_log
    1.31 +
    1.32 +/**
    1.33 + * \brief TypeId information manager
    1.34 + *
    1.35 + * Information records are stored in a vector.  Name and hash lookup
    1.36 + * are performed by maps to the vector index.
    1.37 + *
    1.38 + * \internal
    1.39 + * <b>Hash Chaining</b>
    1.40 + *
    1.41 + * We require all types to produce distinct hashes. What if we encounter
    1.42 + * two types that produce the same hash value?  As we move to a
    1.43 + * federated distribution model (the App store), it becomes increasingly
    1.44 + * likely that the core ns3 team *won't* discover this in test builds.
    1.45 + * Therefore, we need to handle this case explicitly.
    1.46 + *
    1.47 + * Note, we expect this to be *extremely* rare.  As of this writing we
    1.48 + * have ~400 < 2^9 types, so the probability of getting a collision
    1.49 + * when we introduce a new type is ~2^9/2^31 = 2^-22, assuming we
    1.50 + * reserve 31 bits for the hash, and one bit for chaining.  Even with
    1.51 + * double the number of types the probability of having a collision
    1.52 + * is only 2 x 10^-4.  The probability for a three-fold collision is
    1.53 + * 1 x 10^-10.
    1.54 + *
    1.55 + * Therefore, we'll handle one collision explicitly by reserving
    1.56 + * the high order bit of the hash value, and assert on higher level
    1.57 + * collisions.  The three-fold collision probability should be an
    1.58 + * acceptablly small error rate.
    1.59 + */
    1.60  class IidManager
    1.61  {
    1.62  public:
    1.63 @@ -39,13 +74,15 @@
    1.64    uint16_t AllocateUid (std::string name);
    1.65    void SetParent (uint16_t uid, uint16_t parent);
    1.66    void SetGroupName (uint16_t uid, std::string groupName);
    1.67 -  void AddConstructor (uint16_t uid, ns3::Callback<ns3::ObjectBase *> callback);
    1.68 +  void AddConstructor (uint16_t uid, Callback<ObjectBase *> callback);
    1.69    void HideFromDocumentation (uint16_t uid);
    1.70    uint16_t GetUid (std::string name) const;
    1.71 +  uint16_t GetUid (TypeId::hash_t hash) const;
    1.72    std::string GetName (uint16_t uid) const;
    1.73 +  TypeId::hash_t GetHash (uint16_t uid) const;
    1.74    uint16_t GetParent (uint16_t uid) const;
    1.75    std::string GetGroupName (uint16_t uid) const;
    1.76 -  ns3::Callback<ns3::ObjectBase *> GetConstructor (uint16_t uid) const;
    1.77 +  Callback<ObjectBase *> GetConstructor (uint16_t uid) const;
    1.78    bool HasConstructor (uint16_t uid) const;
    1.79    uint32_t GetRegisteredN (void) const;
    1.80    uint16_t GetRegistered (uint32_t i) const;
    1.81 @@ -53,41 +90,54 @@
    1.82                       std::string name,
    1.83                       std::string help, 
    1.84                       uint32_t flags,
    1.85 -                     ns3::Ptr<const ns3::AttributeValue> initialValue,
    1.86 -                     ns3::Ptr<const ns3::AttributeAccessor> spec,
    1.87 -                     ns3::Ptr<const ns3::AttributeChecker> checker);
    1.88 +                     Ptr<const AttributeValue> initialValue,
    1.89 +                     Ptr<const AttributeAccessor> spec,
    1.90 +                     Ptr<const AttributeChecker> checker);
    1.91    void SetAttributeInitialValue(uint16_t uid,
    1.92                                  uint32_t i,
    1.93 -                                ns3::Ptr<const ns3::AttributeValue> initialValue);
    1.94 +                                Ptr<const AttributeValue> initialValue);
    1.95    uint32_t GetAttributeN (uint16_t uid) const;
    1.96 -  struct ns3::TypeId::AttributeInformation GetAttribute(uint16_t uid, uint32_t i) const;
    1.97 +  struct TypeId::AttributeInformation GetAttribute(uint16_t uid, uint32_t i) const;
    1.98    void AddTraceSource (uint16_t uid,
    1.99                         std::string name, 
   1.100                         std::string help,
   1.101 -                       ns3::Ptr<const ns3::TraceSourceAccessor> accessor);
   1.102 +                       Ptr<const TraceSourceAccessor> accessor);
   1.103    uint32_t GetTraceSourceN (uint16_t uid) const;
   1.104 -  struct ns3::TypeId::TraceSourceInformation GetTraceSource(uint16_t uid, uint32_t i) const;
   1.105 +  struct TypeId::TraceSourceInformation GetTraceSource(uint16_t uid, uint32_t i) const;
   1.106    bool MustHideFromDocumentation (uint16_t uid) const;
   1.107  
   1.108  private:
   1.109    bool HasTraceSource (uint16_t uid, std::string name);
   1.110    bool HasAttribute (uint16_t uid, std::string name);
   1.111 +  static TypeId::hash_t Hasher (const std::string name);
   1.112  
   1.113    struct IidInformation {
   1.114      std::string name;
   1.115 +    TypeId::hash_t hash;
   1.116      uint16_t parent;
   1.117      std::string groupName;
   1.118      bool hasConstructor;
   1.119 -    ns3::Callback<ns3::ObjectBase *> constructor;
   1.120 +    Callback<ObjectBase *> constructor;
   1.121      bool mustHideFromDocumentation;
   1.122 -    std::vector<struct ns3::TypeId::AttributeInformation> attributes;
   1.123 -    std::vector<struct ns3::TypeId::TraceSourceInformation> traceSources;
   1.124 +    std::vector<struct TypeId::AttributeInformation> attributes;
   1.125 +    std::vector<struct TypeId::TraceSourceInformation> traceSources;
   1.126    };
   1.127    typedef std::vector<struct IidInformation>::const_iterator Iterator;
   1.128  
   1.129    struct IidManager::IidInformation *LookupInformation (uint16_t uid) const;
   1.130  
   1.131    std::vector<struct IidInformation> m_information;
   1.132 +
   1.133 +  typedef std::map<std::string, uint16_t> namemap_t;
   1.134 +  namemap_t m_namemap;
   1.135 +
   1.136 +  typedef std::map<TypeId::hash_t, uint16_t> hashmap_t;
   1.137 +  hashmap_t m_hashmap;
   1.138 +
   1.139 +  
   1.140 +  // To handle the first collision, we reserve the high bit as a
   1.141 +  // chain flag:
   1.142 +  enum { HashChainFlag = 0x80000000};
   1.143  };
   1.144  
   1.145  IidManager::IidManager ()
   1.146 @@ -95,22 +145,70 @@
   1.147    NS_LOG_FUNCTION (this);
   1.148  }
   1.149  
   1.150 +  //static
   1.151 +TypeId::hash_t
   1.152 +IidManager::Hasher (const std::string name)
   1.153 +{
   1.154 +  static ns3::Hasher hasher ( Create<Hash::Function::Murmur3> () );
   1.155 +  return hasher.clear ().GetHash32 (name);
   1.156 +}
   1.157 +  
   1.158  uint16_t
   1.159  IidManager::AllocateUid (std::string name)
   1.160  {
   1.161    NS_LOG_FUNCTION (this << name);
   1.162 -  uint16_t j = 1;
   1.163 -  for (Iterator i = m_information.begin (); i != m_information.end (); i++)
   1.164 -    {
   1.165 -      if (i->name == name)
   1.166 -        {
   1.167 -          NS_FATAL_ERROR ("Trying to allocate twice the same uid: " << name);
   1.168 -          return 0;
   1.169 -        }
   1.170 -      j++;
   1.171 -    }
   1.172 -  struct IidInformation information;
   1.173 +  // Type names are definitive: equal names are equal types
   1.174 +  NS_ASSERT_MSG (m_namemap.count (name) == 0,
   1.175 +                 "Trying to allocate twice the same uid: " << name);
   1.176 +  
   1.177 +  TypeId::hash_t hash = Hasher (name) & (~HashChainFlag);
   1.178 +  if (m_hashmap.count (hash) == 1) {
   1.179 +    NS_LOG_ERROR ("Hash chaining TypeId for '" << name << "'.  "
   1.180 +                 << "This is not a bug, but is extremely unlikely.  "
   1.181 +                 << "Please contact the ns3 developers.");
   1.182 +    // ns3 developer contacted about this message:
   1.183 +    // You have four options (in order of difficulty):
   1.184 +    //   1. Let it ride, and play the odds that a third collision
   1.185 +    //        never appears.
   1.186 +    //   2. Change the name of the new (or old) tag, even trivially, to
   1.187 +    //        remove the collision.
   1.188 +    //   3. Switch to 64-bit hashes.
   1.189 +    //   4. Implement 2-bit (or higher) chaining.
   1.190 +    //
   1.191 +    //  Oh, by the way, I owe you a beer, since I bet Mathieu that
   1.192 +    //  this would never happen..  -- Peter Barnes, LLNL
   1.193 +
   1.194 +    NS_ASSERT_MSG (m_hashmap.count (hash | HashChainFlag) == 0,
   1.195 +                   "Triplicate hash detected while chaining TypeId for '"
   1.196 +                   << name
   1.197 +                   << "'. Please contact the ns3 developers for assistance.");
   1.198 +    // ns3 developer contacted about this message:
   1.199 +    // You have three options: #2-4 above.
   1.200 +    //
   1.201 +    // Oh, by the way, I have no idea how this crazy hashing idea got
   1.202 +    // into ns3.  -- Peter Barnes, LLNL
   1.203 +    
   1.204 +    // Alphabetize the two types, so it's deterministic
   1.205 +    struct IidInformation * hinfo = LookupInformation (GetUid (hash));
   1.206 +    if (name > hinfo->name)
   1.207 +      { // new type gets chained
   1.208 +        NS_LOG_LOGIC ("New TypeId '" << name << "' getting chained.");
   1.209 +        hash = hash | HashChainFlag;
   1.210 +      }
   1.211 +    else
   1.212 +      { // chain old type
   1.213 +        NS_LOG_LOGIC ("Old TypeId '" << hinfo->name << "' getting chained.");
   1.214 +        uint32_t oldUid = GetUid (hinfo->hash);
   1.215 +        m_hashmap.erase (m_hashmap.find (hinfo->hash));
   1.216 +        hinfo->hash = hash | HashChainFlag;
   1.217 +        m_hashmap.insert (std::make_pair (hinfo->hash, oldUid));
   1.218 +        // leave new hash unchained
   1.219 +      }
   1.220 +  }
   1.221 +
   1.222 + struct IidInformation information;
   1.223    information.name = name;
   1.224 +  information.hash = hash;
   1.225    information.parent = 0;
   1.226    information.groupName = "";
   1.227    information.hasConstructor = false;
   1.228 @@ -118,6 +216,10 @@
   1.229    m_information.push_back (information);
   1.230    uint32_t uid = m_information.size ();
   1.231    NS_ASSERT (uid <= 0xffff);
   1.232 +
   1.233 +  // Add to both maps:
   1.234 +  m_namemap.insert (std::make_pair (name, uid));
   1.235 +  m_hashmap.insert (std::make_pair (hash, uid));
   1.236    return uid;
   1.237  }
   1.238  
   1.239 @@ -153,7 +255,7 @@
   1.240  }
   1.241  
   1.242  void 
   1.243 -IidManager::AddConstructor (uint16_t uid, ns3::Callback<ns3::ObjectBase *> callback)
   1.244 +IidManager::AddConstructor (uint16_t uid, Callback<ObjectBase *> callback)
   1.245  {
   1.246    NS_LOG_FUNCTION (this << uid << &callback);
   1.247    struct IidInformation *information = LookupInformation (uid);
   1.248 @@ -169,17 +271,28 @@
   1.249  IidManager::GetUid (std::string name) const
   1.250  {
   1.251    NS_LOG_FUNCTION (this << name);
   1.252 -  uint32_t j = 1;
   1.253 -  for (Iterator i = m_information.begin (); i != m_information.end (); i++)
   1.254 +  namemap_t::const_iterator it = m_namemap.find (name);
   1.255 +  if (it != m_namemap.end ())
   1.256      {
   1.257 -      if (i->name == name)
   1.258 -        {
   1.259 -          NS_ASSERT (j <= 0xffff);
   1.260 -          return j;
   1.261 -        }
   1.262 -      j++;
   1.263 +      return it->second;
   1.264      }
   1.265 -  return 0;
   1.266 +  else
   1.267 +    {
   1.268 +      return 0;
   1.269 +    }
   1.270 +}
   1.271 +uint16_t 
   1.272 +IidManager::GetUid (TypeId::hash_t hash) const
   1.273 +{
   1.274 +  hashmap_t::const_iterator it = m_hashmap.find (hash);
   1.275 +  if (it != m_hashmap.end ())
   1.276 +    {
   1.277 +    return it->second;
   1.278 +    }
   1.279 +  else
   1.280 +    { // hash not found 
   1.281 +      return 0;
   1.282 +    }
   1.283  }
   1.284  std::string 
   1.285  IidManager::GetName (uint16_t uid) const
   1.286 @@ -188,6 +301,13 @@
   1.287    struct IidInformation *information = LookupInformation (uid);
   1.288    return information->name;
   1.289  }
   1.290 +TypeId::hash_t
   1.291 +IidManager::GetHash (uint16_t uid) const
   1.292 +{
   1.293 +  NS_LOG_FUNCTION (this << uid);
   1.294 +  struct IidInformation *information = LookupInformation (uid);
   1.295 +  return information->hash;
   1.296 +}
   1.297  uint16_t 
   1.298  IidManager::GetParent (uint16_t uid) const
   1.299  {
   1.300 @@ -203,7 +323,7 @@
   1.301    return information->groupName;
   1.302  }
   1.303  
   1.304 -ns3::Callback<ns3::ObjectBase *> 
   1.305 +Callback<ObjectBase *> 
   1.306  IidManager::GetConstructor (uint16_t uid) const
   1.307  {
   1.308    NS_LOG_FUNCTION (this << uid);
   1.309 @@ -244,7 +364,7 @@
   1.310    struct IidInformation *information  = LookupInformation (uid);
   1.311    while (true)
   1.312      {
   1.313 -      for (std::vector<struct ns3::TypeId::AttributeInformation>::const_iterator i = information->attributes.begin ();
   1.314 +      for (std::vector<struct TypeId::AttributeInformation>::const_iterator i = information->attributes.begin ();
   1.315             i != information->attributes.end (); ++i)
   1.316          {
   1.317            if (i->name == name)
   1.318 @@ -269,9 +389,9 @@
   1.319                            std::string name,
   1.320                            std::string help, 
   1.321                            uint32_t flags,
   1.322 -                          ns3::Ptr<const ns3::AttributeValue> initialValue,
   1.323 -                          ns3::Ptr<const ns3::AttributeAccessor> accessor,
   1.324 -                          ns3::Ptr<const ns3::AttributeChecker> checker)
   1.325 +                          Ptr<const AttributeValue> initialValue,
   1.326 +                          Ptr<const AttributeAccessor> accessor,
   1.327 +                          Ptr<const AttributeChecker> checker)
   1.328  {
   1.329    NS_LOG_FUNCTION (this << uid << name << help << flags << initialValue << accessor << checker);
   1.330    struct IidInformation *information = LookupInformation (uid);
   1.331 @@ -280,7 +400,7 @@
   1.332        NS_FATAL_ERROR ("Attribute \"" << name << "\" already registered on tid=\"" << 
   1.333                        information->name << "\"");
   1.334      }
   1.335 -  struct ns3::TypeId::AttributeInformation info;
   1.336 +  struct TypeId::AttributeInformation info;
   1.337    info.name = name;
   1.338    info.help = help;
   1.339    info.flags = flags;
   1.340 @@ -293,7 +413,7 @@
   1.341  void 
   1.342  IidManager::SetAttributeInitialValue(uint16_t uid,
   1.343                                       uint32_t i,
   1.344 -                                     ns3::Ptr<const ns3::AttributeValue> initialValue)
   1.345 +                                     Ptr<const AttributeValue> initialValue)
   1.346  {
   1.347    NS_LOG_FUNCTION (this << uid << i << initialValue);
   1.348    struct IidInformation *information = LookupInformation (uid);
   1.349 @@ -310,7 +430,7 @@
   1.350    struct IidInformation *information = LookupInformation (uid);
   1.351    return information->attributes.size ();
   1.352  }
   1.353 -struct ns3::TypeId::AttributeInformation 
   1.354 +struct TypeId::AttributeInformation 
   1.355  IidManager::GetAttribute(uint16_t uid, uint32_t i) const
   1.356  {
   1.357    NS_LOG_FUNCTION (this << uid << i);
   1.358 @@ -327,7 +447,7 @@
   1.359    struct IidInformation *information  = LookupInformation (uid);
   1.360    while (true)
   1.361      {
   1.362 -      for (std::vector<struct ns3::TypeId::TraceSourceInformation>::const_iterator i = information->traceSources.begin ();
   1.363 +      for (std::vector<struct TypeId::TraceSourceInformation>::const_iterator i = information->traceSources.begin ();
   1.364             i != information->traceSources.end (); ++i)
   1.365          {
   1.366            if (i->name == name)
   1.367 @@ -351,7 +471,7 @@
   1.368  IidManager::AddTraceSource (uint16_t uid,
   1.369                              std::string name, 
   1.370                              std::string help,
   1.371 -                            ns3::Ptr<const ns3::TraceSourceAccessor> accessor)
   1.372 +                            Ptr<const TraceSourceAccessor> accessor)
   1.373  {
   1.374    NS_LOG_FUNCTION (this << uid << name << help << accessor);
   1.375    struct IidInformation *information  = LookupInformation (uid);
   1.376 @@ -360,7 +480,7 @@
   1.377        NS_FATAL_ERROR ("Trace source \"" << name << "\" already registered on tid=\"" << 
   1.378                        information->name << "\"");
   1.379      }
   1.380 -  struct ns3::TypeId::TraceSourceInformation source;
   1.381 +  struct TypeId::TraceSourceInformation source;
   1.382    source.name = name;
   1.383    source.help = help;
   1.384    source.accessor = accessor;
   1.385 @@ -373,7 +493,7 @@
   1.386    struct IidInformation *information = LookupInformation (uid);
   1.387    return information->traceSources.size ();
   1.388  }
   1.389 -struct ns3::TypeId::TraceSourceInformation 
   1.390 +struct TypeId::TraceSourceInformation 
   1.391  IidManager::GetTraceSource(uint16_t uid, uint32_t i) const
   1.392  {
   1.393    NS_LOG_FUNCTION (this << uid << i);
   1.394 @@ -389,7 +509,7 @@
   1.395    return information->mustHideFromDocumentation;
   1.396  }
   1.397  
   1.398 -} // anonymous namespace
   1.399 +} // namespace ns3
   1.400  
   1.401  namespace ns3 {
   1.402  
   1.403 @@ -431,6 +551,25 @@
   1.404    *tid = TypeId (uid);
   1.405    return true;
   1.406  }
   1.407 +TypeId
   1.408 +TypeId::LookupByHash (hash_t hash)
   1.409 +{
   1.410 +  uint16_t uid = Singleton<IidManager>::Get ()->GetUid (hash);
   1.411 +  NS_ASSERT_MSG (uid != 0, "Assert in TypeId::LookupByHash: 0x"
   1.412 +                 << std::hex << hash << std::dec << " not found");
   1.413 +  return TypeId (uid);
   1.414 +}
   1.415 +bool
   1.416 +TypeId::LookupByHashFailSafe (hash_t hash, TypeId *tid)
   1.417 +{
   1.418 +  uint16_t uid = Singleton<IidManager>::Get ()->GetUid (hash);
   1.419 +  if (uid == 0)
   1.420 +    {
   1.421 +      return false;
   1.422 +    }
   1.423 +  *tid = TypeId (uid);
   1.424 +  return true;
   1.425 +}
   1.426  
   1.427  uint32_t 
   1.428  TypeId::GetRegisteredN (void)
   1.429 @@ -522,6 +661,13 @@
   1.430    return name;
   1.431  }
   1.432  
   1.433 +TypeId::hash_t
   1.434 +TypeId::GetHash (void) const
   1.435 +{
   1.436 +  hash_t hash = Singleton<IidManager>::Get ()->GetHash (m_tid);
   1.437 +  return hash;
   1.438 +}
   1.439 +
   1.440  bool 
   1.441  TypeId::HasConstructor (void) const
   1.442  {
     2.1 --- a/src/core/model/type-id.h	Thu Jul 18 12:04:27 2013 -0700
     2.2 +++ b/src/core/model/type-id.h	Thu Jul 18 12:01:05 2013 -0700
     2.3 @@ -25,6 +25,7 @@
     2.4  #include "trace-source-accessor.h"
     2.5  #include "attribute-helper.h"
     2.6  #include "callback.h"
     2.7 +#include "hash.h"
     2.8  #include <string>
     2.9  #include <stdint.h>
    2.10  
    2.11 @@ -40,6 +41,10 @@
    2.12   *  - the base class of the subclass
    2.13   *  - the set of accessible constructors in the subclass
    2.14   *  - the set of 'attributes' accessible in the subclass
    2.15 + *
    2.16 + * \internal
    2.17 + *  See the discussion in IidManager about hash chaining of TypeId's.
    2.18 + *
    2.19   */
    2.20  class TypeId
    2.21  {
    2.22 @@ -57,18 +62,23 @@
    2.23      std::string name;
    2.24      std::string help;
    2.25      uint32_t flags;
    2.26 -    ns3::Ptr<const ns3::AttributeValue> originalInitialValue;
    2.27 -    ns3::Ptr<const ns3::AttributeValue> initialValue;
    2.28 -    ns3::Ptr<const ns3::AttributeAccessor> accessor;
    2.29 -    ns3::Ptr<const ns3::AttributeChecker> checker;
    2.30 +    Ptr<const AttributeValue> originalInitialValue;
    2.31 +    Ptr<const AttributeValue> initialValue;
    2.32 +    Ptr<const AttributeAccessor> accessor;
    2.33 +    Ptr<const AttributeChecker> checker;
    2.34    };
    2.35    struct TraceSourceInformation {
    2.36      std::string name;
    2.37      std::string help;
    2.38 -    ns3::Ptr<const ns3::TraceSourceAccessor> accessor;
    2.39 +    Ptr<const TraceSourceAccessor> accessor;
    2.40    };
    2.41  
    2.42    /**
    2.43 +   * Type of hash values
    2.44 +   */
    2.45 +  typedef uint32_t hash_t;
    2.46 +
    2.47 +  /**
    2.48     * \param name the name of the requested TypeId
    2.49     * \returns the unique id associated with the requested
    2.50     *          name. 
    2.51 @@ -84,6 +94,21 @@
    2.52     * \returns true if the requested name was found, false otherwise.
    2.53     */
    2.54    static bool LookupByNameFailSafe (std::string name, TypeId *tid);
    2.55 +  /**
    2.56 +   * \param hash the hash to lookup
    2.57 +   * \returns the unique id associated with the requested hash.
    2.58 +   *
    2.59 +   * This method cannot fail: it will crash if the input 
    2.60 +   * hash does not match an existing TypeId.
    2.61 +   */
    2.62 +  static TypeId LookupByHash (hash_t hash);
    2.63 +  /**
    2.64 +   * \param hash the hash of the requested TypeId
    2.65 +   * \param tid a pointer to the TypeId instance where the 
    2.66 +   *        result of this function should be stored.
    2.67 +   * \returns true if the requested hash was found, false otherwise.
    2.68 +   */
    2.69 +  static bool LookupByHashFailSafe (hash_t hash, TypeId *tid);
    2.70  
    2.71    /**
    2.72     * \returns the number of TypeId instances registered.
    2.73 @@ -138,6 +163,11 @@
    2.74    std::string GetName (void) const;
    2.75  
    2.76    /**
    2.77 +   * \returns the hash of this interface.
    2.78 +   */
    2.79 +  hash_t GetHash (void) const;
    2.80 +
    2.81 +  /**
    2.82     * \returns true if this TypeId has a constructor
    2.83     */
    2.84    bool HasConstructor (void) const;
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/core/test/type-id-test-suite.cc	Thu Jul 18 12:01:05 2013 -0700
     3.3 @@ -0,0 +1,321 @@
     3.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
     3.5 +/*
     3.6 + * Copyright (c) 2012 Lawrence Livermore National Laboratory
     3.7 + *
     3.8 + * This program is free software; you can redistribute it and/or modify
     3.9 + * it under the terms of the GNU General Public License version 2 as
    3.10 + * published by the Free Software Foundation;
    3.11 + *
    3.12 + * This program is distributed in the hope that it will be useful,
    3.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    3.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    3.15 + * GNU General Public License for more details.
    3.16 + *
    3.17 + * You should have received a copy of the GNU General Public License
    3.18 + * along with this program; if not, write to the Free Software
    3.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    3.20 + *
    3.21 + * Author: Peter D. Barnes, Jr. <pdbarnes@llnl.gov>
    3.22 + */
    3.23 +
    3.24 +#include <iostream>
    3.25 +#include <iomanip>
    3.26 +#include <ctime>
    3.27 +
    3.28 +#include "ns3/type-id.h"
    3.29 +#include "ns3/test.h"
    3.30 +#include "ns3/log.h"
    3.31 +
    3.32 +using namespace std;
    3.33 +
    3.34 +namespace ns3 {
    3.35 +
    3.36 +
    3.37 +const std::string suite("type-id: ");
    3.38 +  
    3.39 +//----------------------------
    3.40 +//
    3.41 +// Test for uniqueness of all TypeIds
    3.42 +
    3.43 +class UniqueTypeIdTestCase : public TestCase
    3.44 +{
    3.45 +public:
    3.46 +  UniqueTypeIdTestCase ();
    3.47 +  virtual ~UniqueTypeIdTestCase ();
    3.48 +private:
    3.49 +  virtual void DoRun (void);
    3.50 +  enum { HashChainFlag = 0x80000000};
    3.51 +};
    3.52 +
    3.53 +UniqueTypeIdTestCase::UniqueTypeIdTestCase ()
    3.54 +  : TestCase ("Check uniqueness of all TypeIds")
    3.55 +{
    3.56 +}
    3.57 +
    3.58 +UniqueTypeIdTestCase::~UniqueTypeIdTestCase ()
    3.59 +{
    3.60 +}
    3.61 +
    3.62 +void
    3.63 +UniqueTypeIdTestCase::DoRun (void)
    3.64 +{
    3.65 +  cout << suite << endl;
    3.66 +  cout << suite << GetName () << endl;
    3.67 +  
    3.68 +  // Use same custom hasher as TypeId
    3.69 +  ns3::Hasher hasher = ns3::Hasher ( Create<Hash::Function::Murmur3> () );
    3.70 +  
    3.71 +  uint32_t nids = TypeId::GetRegisteredN ();
    3.72 +
    3.73 +  cout << suite << "UniqueTypeIdTestCase: nids: " << nids << endl;
    3.74 +  cout << suite << "TypeId list:" << endl;
    3.75 +  cout << suite << "TypeId  Chain  hash          Name" << endl;
    3.76 +  
    3.77 +  for (uint32_t i = 0; i < nids; ++i)
    3.78 +    {
    3.79 +      const TypeId tid = TypeId::GetRegistered (i);
    3.80 +      cout << suite << "" << std::setw(6) << tid.GetUid ();
    3.81 +      if (tid.GetHash () & HashChainFlag)
    3.82 +        {
    3.83 +          cout << "  chain";
    3.84 +        }
    3.85 +      else
    3.86 +        {
    3.87 +          cout << "       ";
    3.88 +        }
    3.89 +      cout << "  0x"     << std::setfill ('0') << std::hex << std::setw (8)
    3.90 +           << tid.GetHash () << std::dec << std::setfill (' ')
    3.91 +           << "    "     << tid.GetName ()
    3.92 +           << endl;
    3.93 +
    3.94 +      NS_TEST_ASSERT_MSG_EQ (tid.GetUid (),
    3.95 +                             TypeId::LookupByName (tid.GetName ()).GetUid (),
    3.96 +                             "LookupByName returned different TypeId for "
    3.97 +                             << tid.GetName ());
    3.98 +
    3.99 +      // Mask off HashChainFlag in this test, since tid might have been chained
   3.100 +      NS_TEST_ASSERT_MSG_EQ ((tid.GetHash () & (~HashChainFlag)),
   3.101 +                             (hasher.clear ().GetHash32 (tid.GetName ()) & (~HashChainFlag)),
   3.102 +                             "TypeId .hash and Hash32 (.name) unequal for "
   3.103 +                             << tid.GetName ());
   3.104 +
   3.105 +      NS_TEST_ASSERT_MSG_EQ (tid.GetUid (),
   3.106 +                             TypeId::LookupByHash (tid.GetHash ()).GetUid (),
   3.107 +                             "LookupByHash returned different TypeId for "
   3.108 +                             << tid.GetName ());
   3.109 +      
   3.110 +    }
   3.111 +
   3.112 +  cout << suite << "<-- end TypeId list -->" << endl;
   3.113 +}
   3.114 +
   3.115 +
   3.116 +//----------------------------
   3.117 +//
   3.118 +// Collision test
   3.119 +
   3.120 +class CollisionTestCase : public TestCase
   3.121 +{
   3.122 +public:
   3.123 +  CollisionTestCase ();
   3.124 +  virtual ~CollisionTestCase ();
   3.125 +private:
   3.126 +  virtual void DoRun (void);
   3.127 +  enum { HashChainFlag = 0x80000000};
   3.128 +};
   3.129 +
   3.130 +CollisionTestCase::CollisionTestCase ()
   3.131 +  : TestCase ("Check behavour when type names collide")
   3.132 +{
   3.133 +}
   3.134 +
   3.135 +CollisionTestCase::~CollisionTestCase ()
   3.136 +{
   3.137 +}
   3.138 +
   3.139 +void
   3.140 +CollisionTestCase::DoRun (void)
   3.141 +{
   3.142 +  cout << suite << endl;
   3.143 +  cout << suite << GetName () << endl;
   3.144 +  
   3.145 +  // Register two types whose hashes collide, in alphabetical order
   3.146 +  // Murmur3 collision from /usr/share/dict/web2
   3.147 +  string t1Name = "daemon";
   3.148 +  string t2Name = "unerring";
   3.149 +  cout << suite << "creating colliding types "
   3.150 +       << "'" << t1Name << "', '" << t2Name << "'"
   3.151 +       << " in alphabetical order:"
   3.152 +       << endl;
   3.153 +  TypeId t1 (t1Name.c_str ());
   3.154 +  TypeId t2 (t2Name.c_str ());
   3.155 +
   3.156 +  // Check that they are alphabetical: t1 name < t2 name
   3.157 +  NS_TEST_ASSERT_MSG_EQ ( (t1.GetHash () & HashChainFlag), 0,
   3.158 +                         "First and lesser TypeId has HashChainFlag set");
   3.159 +  cout << suite << "collision: first,lesser  not chained: OK" << endl;
   3.160 +
   3.161 +  NS_TEST_ASSERT_MSG_NE ( (t2.GetHash () & HashChainFlag), 0,
   3.162 +                         "Second and greater TypeId does not have HashChainFlag set");
   3.163 +  cout << suite << "collision: second,greater    chained: OK" << endl;
   3.164 +
   3.165 +
   3.166 +  // Register colliding types in reverse alphabetical order
   3.167 +  // Murmur3 collision from /usr/share/dict/web2
   3.168 +  string t3Name = "trigonon";
   3.169 +  string t4Name = "seriation";
   3.170 +  cout << suite << "creating colliding types "
   3.171 +       << "'" << t3Name << "', '" << t4Name << "'"
   3.172 +       << " in reverse alphabetical order:"
   3.173 +       << endl;
   3.174 +  TypeId t3 (t3Name.c_str ());
   3.175 +  TypeId t4 (t4Name.c_str ());
   3.176 +
   3.177 +  // Check that they are alphabetical: t3 name > t4 name
   3.178 +  NS_TEST_ASSERT_MSG_NE ( (t3.GetHash () & HashChainFlag), 0,
   3.179 +                          "First and greater TypeId does not have HashChainFlag set");
   3.180 +  cout << suite << "collision: first,greater     chained: OK" << endl;
   3.181 +
   3.182 +  NS_TEST_ASSERT_MSG_EQ ( (t4.GetHash () & HashChainFlag), 0,
   3.183 +                          "Second and lesser TypeId has HashChainFlag set");
   3.184 +  cout << suite << "collision: second,lesser not chained: OK" << endl;
   3.185 +
   3.186 +  /** TODO Extra credit:  register three types whose hashes collide
   3.187 +   *
   3.188 +   *  None found in /usr/share/dict/web2
   3.189 +   */
   3.190 +  
   3.191 +}
   3.192 +  
   3.193 +  
   3.194 +//----------------------------
   3.195 +//
   3.196 +// Performance test
   3.197 +
   3.198 +class LookupTimeTestCase : public TestCase
   3.199 +{
   3.200 +public:
   3.201 +  LookupTimeTestCase ();
   3.202 +  virtual ~LookupTimeTestCase ();
   3.203 +private:
   3.204 +  void DoRun (void);
   3.205 +  void DoSetup (void);
   3.206 +  void Report (const std::string how, const uint32_t delta) const ;
   3.207 +
   3.208 +  enum { REPETITIONS = 100000 };
   3.209 +};
   3.210 +
   3.211 +LookupTimeTestCase::LookupTimeTestCase ()
   3.212 +  : TestCase ("Measure average lookup time")
   3.213 +{
   3.214 +}
   3.215 +
   3.216 +LookupTimeTestCase::~LookupTimeTestCase ()
   3.217 +{
   3.218 +}
   3.219 +
   3.220 +void
   3.221 +LookupTimeTestCase::DoRun (void)
   3.222 +{
   3.223 +  cout << suite << endl;
   3.224 +  cout << suite << GetName () << endl;
   3.225 +  
   3.226 +  uint32_t nids = TypeId::GetRegisteredN ();
   3.227 +
   3.228 +  int start = clock ();
   3.229 +  for (uint32_t j = 0; j < REPETITIONS; ++j)
   3.230 +    {
   3.231 +      for (uint32_t i = 0; i < nids; ++i)
   3.232 +        {
   3.233 +          const TypeId tid = TypeId::GetRegistered (i);
   3.234 +          const TypeId sid = TypeId::LookupByName (tid.GetName ());
   3.235 +        }
   3.236 +  }
   3.237 +  int stop = clock ();
   3.238 +  Report ("name", stop - start);
   3.239 +
   3.240 +  start = clock ();
   3.241 +  for (uint32_t j = 0; j < REPETITIONS; ++j)
   3.242 +    {
   3.243 +      for (uint32_t i = 0; i < nids; ++i)
   3.244 +        {
   3.245 +          const TypeId tid = TypeId::GetRegistered (i);
   3.246 +          const TypeId sid = TypeId::LookupByHash (tid.GetHash ());
   3.247 +        }
   3.248 +  }
   3.249 +  stop = clock ();
   3.250 +  Report ("hash", stop - start);
   3.251 +  
   3.252 +}
   3.253 +
   3.254 +void
   3.255 +LookupTimeTestCase::DoSetup (void)
   3.256 +{
   3.257 +  uint32_t nids = TypeId::GetRegisteredN ();
   3.258 +  
   3.259 +  cout << suite << "Lookup time: reps: " << REPETITIONS
   3.260 +       << ", num TypeId's: " << nids
   3.261 +       << endl;
   3.262 +
   3.263 +}
   3.264 +
   3.265 +void
   3.266 +LookupTimeTestCase::Report (const std::string how,
   3.267 +                            const uint32_t    delta) const
   3.268 +{
   3.269 +  double nids = TypeId::GetRegisteredN ();
   3.270 +  double reps = nids * REPETITIONS;
   3.271 +  
   3.272 +  double per = 1E6 * double(delta) / (reps * double(CLOCKS_PER_SEC));
   3.273 +  
   3.274 +  cout << suite << "Lookup time: by " << how << ": "
   3.275 +       << "ticks: " << delta
   3.276 +       << "\tper: "   << per
   3.277 +       << " microsec/lookup"
   3.278 +       << endl;					
   3.279 +}
   3.280 +
   3.281 +
   3.282 +//----------------------------
   3.283 +//
   3.284 +// TypeId test suites
   3.285 +
   3.286 +class TypeIdTestSuite : public TestSuite
   3.287 +{
   3.288 +public:
   3.289 +  TypeIdTestSuite ();
   3.290 +};
   3.291 +  
   3.292 +TypeIdTestSuite::TypeIdTestSuite ()
   3.293 +  : TestSuite ("type-id", UNIT)
   3.294 +{
   3.295 +  // Turn on logging, so we see the result of collisions
   3.296 +  LogComponentEnable ("TypeId", ns3::LogLevel(LOG_ERROR|LOG_PREFIX_FUNC));
   3.297 +  
   3.298 +  // If the CollisionTestCase is performed before the
   3.299 +  // UniqueIdTestCase, the artificial collisions added by
   3.300 +  // CollisionTestCase will show up in the list of TypeIds
   3.301 +  // as chained.
   3.302 +  AddTestCase (new UniqueTypeIdTestCase);
   3.303 +  AddTestCase (new CollisionTestCase);
   3.304 +}
   3.305 +
   3.306 +static TypeIdTestSuite g_TypeIdTestSuite;  
   3.307 +  
   3.308 +
   3.309 +class TypeIdPerformanceSuite : public TestSuite
   3.310 +{
   3.311 +public:
   3.312 +  TypeIdPerformanceSuite ();
   3.313 +};
   3.314 +  
   3.315 +TypeIdPerformanceSuite::TypeIdPerformanceSuite ()
   3.316 +  : TestSuite ("type-id-perf", PERFORMANCE)
   3.317 +{
   3.318 +  AddTestCase (new LookupTimeTestCase);
   3.319 +}
   3.320 +
   3.321 +static TypeIdPerformanceSuite g_TypeIdPerformanceSuite;  
   3.322 +  
   3.323 +
   3.324 +}  // namespace ns3
     4.1 --- a/src/core/wscript	Thu Jul 18 12:04:27 2013 -0700
     4.2 +++ b/src/core/wscript	Thu Jul 18 12:01:05 2013 -0700
     4.3 @@ -178,6 +178,7 @@
     4.4          'test/type-traits-test-suite.cc',
     4.5          'test/watchdog-test-suite.cc',
     4.6          'test/hash-test-suite.cc',
     4.7 +        'test/type-id-test-suite.cc',
     4.8          ]
     4.9  
    4.10      headers = bld(features='ns3header')