text: //
  // Copyright 2016 Pixar
  //
  // Licensed under the Apache License, Version 2.0 (the "Apache License")
  // with the following modification; you may not use this file except in
  // compliance with the Apache License and the following modification to it:
  // Section 6. Trademarks. is deleted and replaced with:
  //
  // 6. Trademarks. This License does not grant permission to use the trade
  //    names, trademarks, service marks, or product names of the Licensor
  //    and its affiliates, except as required to comply with Section 4(c) of
  //    the License and to reproduce the content of the NOTICE file.
  //
  // You may obtain a copy of the Apache License at
  //
  //     http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the Apache License with the above modification is
  // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  // KIND, either express or implied. See the Apache License for the specific
  // language governing permissions and limitations under the Apache License.
  //
  
  #include "pxr/pxr.h"
  #include "pxr/usd/sdf/path.h"
  #include "pxr/usd/sdf/tokens.h"
  #include "pxr/usd/sdf/instantiatePool.h"
  #include "pxr/base/tf/bitUtils.h"
  #include "pxr/base/tf/diagnostic.h"
  #include "pxr/base/tf/hash.h"
  #include "pxr/base/tf/iterator.h"
  #include "pxr/base/tf/mallocTag.h"
  #include "pxr/base/tf/staticData.h"
  #include "pxr/base/tf/stl.h"
  
  #include "pxr/base/trace/trace.h"
  
  #include <boost/functional/hash.hpp>
  #include <tbb/concurrent_hash_map.h>
  
  #include <atomic>
  #include <utility>
  #include <vector>
  
  using std::string;
  using std::vector;
  
  PXR_NAMESPACE_OPEN_SCOPE
  
  SDF_INSTANTIATE_POOL(Sdf_PathPrimTag, Sdf_SizeofPrimPathNode, /*regionBits=*/8);
  SDF_INSTANTIATE_POOL(Sdf_PathPropTag, Sdf_SizeofPropPathNode, /*regionBits=*/8);
  
  // Size of path nodes is important, so we want the compiler to tell us if it
  // changes.
  static_assert(sizeof(Sdf_PrimPathNode) == 3 * sizeof(void *), "");
  static_assert(sizeof(Sdf_PrimPropertyPathNode) == 3 * sizeof(void *), "");
  
  struct Sdf_PathNodePrivateAccess
  {
      template <class Handle>
      static inline tbb::atomic<unsigned int> &
      GetRefCount(Handle h) {
          Sdf_PathNode const *p =
              reinterpret_cast<Sdf_PathNode const *>(h.GetPtr());
          return p->_refCount;
      }
  
      template <class T, class Pool, class ... Args>
      static inline typename Pool::Handle
      New(Sdf_PathNode const *parent, Args const & ... args) {
          typename Pool::Handle h = Pool::Allocate();
          char *p = h.GetPtr();
          T *tp = reinterpret_cast<T *>(p);
          new (tp) T(parent, args...);
          return h;
      }
  };
  
  typedef Sdf_PathNodePrivateAccess Access;
  
  namespace {
  
  template <class T>
  struct _ParentAnd { const Sdf_PathNode *parent; T value; };
  
  // Allow void for 'expression' path case, which has no additional data.
  template <> struct _ParentAnd<void> { const Sdf_PathNode *parent; };
  
  template <class T>
  inline _ParentAnd<T>
  _MakeParentAnd(const Sdf_PathNode *parent, const T &value) {
      _ParentAnd<T> ret;
      ret.parent = parent;
      ret.value = value;
      return ret;
  }
  
  inline _ParentAnd<void>
  _MakeParentAnd(const Sdf_PathNode *parent) {
      _ParentAnd<void> ret;
      ret.parent = parent;
      return ret;
  }
  
  inline size_t
  hash_value(const Sdf_PathNode *p)
  {
      return TfHash()(p);
  }
  
  template <class T>
  struct _HashParentAnd
  {
      inline bool equal(const T &l, const T &r) const {
          return l.parent == r.parent && l.value == r.value;
      }
  
      inline size_t hash(const T &t) const {
          size_t h = reinterpret_cast<uintptr_t>(t.parent) >> 4;
          boost::hash_combine(h, t.value);
          return h;
      }
   };
  
  template <>
  struct _HashParentAnd<_ParentAnd<void> >
  {
      inline bool equal(const _ParentAnd<void> &l,
                        const _ParentAnd<void> &r) const {
          return l.parent == r.parent;
      }
  
      inline size_t hash(const _ParentAnd<void> &t) const {
          return reinterpret_cast<uintptr_t>(t.parent) >> 4;
      }
  };
  
  template <class T>
  struct _PrimTable {
      using Pool = Sdf_PathPrimPartPool;
      using PoolHandle = Sdf_PathPrimHandle;
      using NodeHandle = Sdf_PathPrimNodeHandle;
      using Type = tbb::concurrent_hash_map<
          _ParentAnd<T>, PoolHandle, _HashParentAnd<_ParentAnd<T> > >;
      
      Type map;
  };
  
  template <class T>
  struct _PropTable {
      using Pool = Sdf_PathPropPartPool;
      using PoolHandle = Sdf_PathPropHandle;
      using NodeHandle = Sdf_PathPropNodeHandle;
      using Type = tbb::concurrent_hash_map<
          _ParentAnd<T>, PoolHandle, _HashParentAnd<_ParentAnd<T> > >;
  
      Type map;
  };
  
  using _PrimTokenTable = _PrimTable<TfToken>;
  using _PropTokenTable = _PropTable<TfToken>;
  using _PrimVarSelTable = _PrimTable<Sdf_PathNode::VariantSelectionType>;
  using _PropTargetTable = _PropTable<SdfPath>;
  using _PropVoidTable = _PropTable<void>;
  
  template <class PathNode, class Table, class ... Args>
  inline typename Table::NodeHandle
  _FindOrCreate(Table &table,
                const Sdf_PathNode *parent,
                const Args & ... args)
  {
      typename Table::Type::accessor accessor;
      if (table.map.insert(accessor, _MakeParentAnd(parent, args...)) ||
          Access::GetRefCount(accessor->second).fetch_and_increment() == 0) {
          // Either there was no entry in the table, or there was but it had begun
          // dying (another client dropped its refcount to 0).  We have to create
          // a new entry in the table.  When the client that is killing the other
          // node it looks for itself in the table, it will either not find itself
          // or will find a different node and so won't remove it.
          typename Table::PoolHandle newNode =
              Access::New<PathNode, typename Table::Pool>(parent, args...);
          accessor->second = newNode;
      }
      return typename Table::NodeHandle(accessor->second, /* add_ref = */ false);
  }
  
  template <class Table, class ... Args>
  inline void
  _Remove(const Sdf_PathNode *pathNode,
          Table &table, const Sdf_PathNodeConstRefPtr &parent,
          const Args & ... args)
  {
      // If there's an entry for this key that has pathNode, erase it.  Even if
      // there's an entry present it may not be pathNode, since another node may
      // have been created since we decremented our refcount and started being
      // destroyed.  If it is this node, we remove it.
      typename Table::Type::accessor accessor;
      if (table.map.find(accessor, _MakeParentAnd(parent.get(), args...)) &&
          accessor->second.GetPtr() == reinterpret_cast<char const *>(pathNode)) {
          table.map.erase(accessor);
      }
  }
  
  } // anon
  
  
  void
  Sdf_PrimPartPathNode::operator delete(void *p)
  {
      using PoolHandle = Sdf_PathPrimPartPool::Handle;
      Sdf_PathPrimPartPool::Free(
          PoolHandle::GetHandle(reinterpret_cast<char *>(p)));
  }
  
  void
  Sdf_PropPartPathNode::operator delete(void *p)
  {
      using PoolHandle = Sdf_PathPropPartPool::Handle;
      Sdf_PathPropPartPool::Free(
          PoolHandle::GetHandle(reinterpret_cast<char *>(p)));
  }
  
  // Preallocate some space in the prim and prim property tables.
  TF_MAKE_STATIC_DATA(_PropTargetTable, _mapperNodes) {}
  TF_MAKE_STATIC_DATA(_PropTargetTable, _targetNodes) {}
  TF_MAKE_STATIC_DATA(_PropTokenTable, _mapperArgNodes) {}
  TF_MAKE_STATIC_DATA(_PrimTokenTable, _primNodes) {
      _primNodes->map.rehash(32768); }
  TF_MAKE_STATIC_DATA(_PropTokenTable, _primPropertyNodes) {
      _primPropertyNodes->map.rehash(32768); }
  TF_MAKE_STATIC_DATA(_PropTokenTable, _relAttrNodes) {}
  TF_MAKE_STATIC_DATA(_PrimVarSelTable, _primVarSelNodes) {}
  TF_MAKE_STATIC_DATA(_PropVoidTable, _expressionNodes) {}
  
  TF_MAKE_STATIC_DATA(Sdf_PathNode const *, _absoluteRootNode) {
      *_absoluteRootNode = Sdf_RootPathNode::New(true);
      TF_AXIOM((*_absoluteRootNode)->GetCurrentRefCount() == 1);
  }
  TF_MAKE_STATIC_DATA(Sdf_PathNode const *, _relativeRootNode) {
      *_relativeRootNode = Sdf_RootPathNode::New(false);
      TF_AXIOM((*_relativeRootNode)->GetCurrentRefCount() == 1);
  }
  
  Sdf_PathNode const *
  Sdf_RootPathNode::New(bool isAbsolute)
  {
      Sdf_PathPrimPartPool::Handle h = Sdf_PathPrimPartPool::Allocate();
      char *p = h.GetPtr();
      Sdf_RootPathNode *tp = reinterpret_cast<Sdf_RootPathNode *>(p);
      new (tp) Sdf_RootPathNode(isAbsolute);
      return tp;
  }
  
  Sdf_PathNode const *
  Sdf_PathNode::GetAbsoluteRootNode() {
      return *_absoluteRootNode;
  }
  
  Sdf_PathNode const *
  Sdf_PathNode::GetRelativeRootNode() {
      return *_relativeRootNode;
  }
  
  Sdf_PathPrimNodeHandle
  Sdf_PathNode::FindOrCreatePrim(Sdf_PathNode const *parent,
                                 const TfToken &name)
  {
      return _FindOrCreate<Sdf_PrimPathNode>(*_primNodes, parent, name);
  }
      
  Sdf_PathPropNodeHandle
  Sdf_PathNode::FindOrCreatePrimProperty(Sdf_PathNode const *parent, 
                                         const TfToken &name)
  {
      // NOTE!  We explicitly set the parent to null here in order to create a
      // separate prefix tree for property-like paths.
  
      return _FindOrCreate<Sdf_PrimPropertyPathNode>(
          *_primPropertyNodes, nullptr, name);
  }
      
  Sdf_PathPrimNodeHandle
  Sdf_PathNode::FindOrCreatePrimVariantSelection(
      Sdf_PathNode const *parent, 
      const TfToken &variantSet,
      const TfToken &variant)
  {
      return _FindOrCreate<Sdf_PrimVariantSelectionNode>(
          *_primVarSelNodes, parent, VariantSelectionType(variantSet, variant));
  }
  
  Sdf_PathPropNodeHandle
  Sdf_PathNode::FindOrCreateTarget(Sdf_PathNode const *parent, 
                                   SdfPath const &targetPath)
  {
      return _FindOrCreate<Sdf_TargetPathNode>(*_targetNodes, parent, targetPath);
  }
  
  Sdf_PathPropNodeHandle
  Sdf_PathNode
  ::FindOrCreateRelationalAttribute(Sdf_PathNode const *parent, 
                                    const TfToken &name)
  {
      return _FindOrCreate<Sdf_RelationalAttributePathNode>(
          *_relAttrNodes, parent, name);
  }
  
  Sdf_PathPropNodeHandle
  Sdf_PathNode
  ::FindOrCreateMapper(Sdf_PathNode const *parent, 
                       SdfPath const &targetPath)
  {
      return _FindOrCreate<Sdf_MapperPathNode>(*_mapperNodes, parent, targetPath);
  }
  
  Sdf_PathPropNodeHandle
  Sdf_PathNode::FindOrCreateMapperArg(Sdf_PathNode const *parent, 
                                      const TfToken &name)
  {
      return _FindOrCreate<Sdf_MapperArgPathNode>(*_mapperArgNodes, parent, name);
  }
      
  Sdf_PathPropNodeHandle
  Sdf_PathNode::FindOrCreateExpression(Sdf_PathNode const *parent)
  {
      return _FindOrCreate<Sdf_ExpressionPathNode>(*_expressionNodes, parent);
  }
  
  Sdf_PathNode::Sdf_PathNode(bool isAbsolute) :
      _refCount(1),
      _elementCount(0),
      _nodeType(RootNode),
      _isAbsolute(isAbsolute),
      _containsPrimVariantSelection(false),
      _containsTargetPath(false),
      _hasToken(false)
  {
  }
  
  const Sdf_PathNode::VariantSelectionType &
  Sdf_PathNode::_GetEmptyVariantSelection() const {
      static VariantSelectionType _emptyVariantSelection;
      return _emptyVariantSelection;
  }
  
  using _PropToTokenTable = 
      tbb::concurrent_hash_map<Sdf_PathNode const *, TfToken>;
  using _PrimToPropTokenTables =
      tbb::concurrent_hash_map<Sdf_PathNode const *, _PropToTokenTable>;
  
  static TfStaticData<_PrimToPropTokenTables> _pathTokenTable;
  
  const TfToken &
  Sdf_PathNode::GetPathToken(Sdf_PathNode const *primPart,
                             Sdf_PathNode const *propPart)
  {
      // Set the cache bit.  We only ever read this during the dtor, and that has
      // to be exclusive to all other execution.
      primPart->_hasToken = true;
  
      // Attempt to insert.
      TfAutoMallocTag2 tag("Sdf", "SdfPath");
      TfAutoMallocTag tag2("Sdf_PathNode::GetPathToken");
  
      _PrimToPropTokenTables::accessor primAccessor;
      _pathTokenTable->insert(
          primAccessor, std::make_pair(primPart, _PropToTokenTable()));
      auto &propToTokenTable = primAccessor->second;
      // Release the primAccessor here, since the call to _CreatePathToken below
      // can cause reentry here (for embedded target paths).
      primAccessor.release();
      _PropToTokenTable::accessor propAccessor;
      if (propToTokenTable.insert(
              propAccessor,std::make_pair(propPart, TfToken()))) {
          // We won the race, build and set the token.
          propAccessor->second = _CreatePathToken(primPart, propPart);
      }
      return propAccessor->second;
  }
  
  TfToken
  Sdf_PathNode::_CreatePathToken(Sdf_PathNode const *primPart,
                                 Sdf_PathNode const *propPart)
  {
      TRACE_FUNCTION();
  
      if (primPart == GetRelativeRootNode() && !propPart) {
          return SdfPathTokens->relativeRoot;
      }
  
      Sdf_PathNode const * const root = (primPart->IsAbsolutePath() ?
                                         Sdf_PathNode::GetAbsoluteRootNode() : 
                                         Sdf_PathNode::GetRelativeRootNode());
      
      std::vector<const Sdf_PathNode *> nodes;
      nodes.reserve(primPart->GetElementCount() +
                    (propPart ? propPart->GetElementCount() : 0));
      
      Sdf_PathNode const *curNode = propPart;
      while (curNode) {
          nodes.push_back(curNode);
          curNode = curNode->GetParentNode();
      }
      curNode = primPart;
      while (curNode && (curNode != root)) {
          nodes.push_back(curNode);
          curNode = curNode->GetParentNode();
      }
  
      std::string str;
      if (primPart->IsAbsolutePath()) {
          // Put the leading / on absolute
          str.append(SdfPathTokens->absoluteIndicator.GetString());
      }
  
      TfToken prevElem;
      Sdf_PathNode::NodeType prevNodeType = Sdf_PathNode::NumNodeTypes;
      TF_REVERSE_FOR_ALL(i, nodes) {
          const Sdf_PathNode * const node = *i;
          Sdf_PathNode::NodeType curNodeType = node->GetNodeType();
          if (prevNodeType == Sdf_PathNode::PrimNode && 
              (curNodeType == Sdf_PathNode::PrimNode ||
               // This covers cases like '../.property'
               prevElem == SdfPathTokens->parentPathElement)) {
              str.append(SdfPathTokens->childDelimiter.GetString());
          }
          TfToken elem = node->GetElement();
          str.append(elem.GetString());
          prevElem.Swap(elem);
          prevNodeType = curNodeType;
      }
  
      return TfToken(str);
  }
  
  void
  Sdf_PathNode::_RemovePathTokenFromTable() const
  {
      _pathTokenTable->erase(this);
  }
  
  // Returns true if \p identifier has at least one namespace delimiter.
  static inline bool
  _HasNamespaceDelimiter(const std::string& identifier)
  {
      return identifier.find(SdfPathTokens->namespaceDelimiter.GetString()[0]) !=
                                                          std::string::npos;
  }
  
  bool
  Sdf_PathNode::_IsNamespacedImpl() const
  {
      return _HasNamespaceDelimiter(GetName().GetString());
  }
  
  void
  Sdf_PathNode::AppendText(std::string *str) const
  {
      switch (_nodeType) {
      case RootNode:
          return;
      case PrimNode:
          str->append(_Downcast<Sdf_PrimPathNode>()->_name.GetString());
          return;
      case PrimPropertyNode:
          str->append(SdfPathTokens->propertyDelimiter.GetString());
          str->append(_Downcast<Sdf_PrimPropertyPathNode>()->_name.GetString());
          return;
      case PrimVariantSelectionNode:
          _Downcast<Sdf_PrimVariantSelectionNode>()->_AppendText(str);
          return;
      case TargetNode:
          _Downcast<Sdf_TargetPathNode>()->_AppendText(str);
          return;
      case RelationalAttributeNode:
          str->append(SdfPathTokens->propertyDelimiter.GetString());
          str->append(_Downcast<Sdf_RelationalAttributePathNode>()->
                      _name.GetString());
          return;
      case MapperNode:
          _Downcast<Sdf_MapperPathNode>()->_AppendText(str);
          return;
      case MapperArgNode:
          _Downcast<Sdf_MapperArgPathNode>()->_AppendText(str);
          return;
      case ExpressionNode:
          _Downcast<Sdf_ExpressionPathNode>()->_AppendText(str);
          return;
      default:
          return;
      };
  }
  
  Sdf_PrimPathNode::~Sdf_PrimPathNode() {
      _Remove(this, *_primNodes, GetParentNode(), _name);
  }
  
  Sdf_PrimPropertyPathNode::~Sdf_PrimPropertyPathNode() {
      _Remove(this, *_primPropertyNodes, GetParentNode(), _name);
  }
  
  const TfToken &
  Sdf_PrimVariantSelectionNode::_GetNameImpl() const
  {
      return _variantSelection->second.IsEmpty()
              ? _variantSelection->first
              : _variantSelection->second;
  }
  
  void
  Sdf_PrimVariantSelectionNode::_AppendText(std::string *str) const
  {
      std::string const &vset = _variantSelection->first.GetString();
      std::string const &vsel = _variantSelection->second.GetString();
      str->reserve(str->size() + vset.size() + vsel.size() + 3);
      str->push_back('{');
      str->append(vset);
      str->push_back('=');
      str->append(vsel);
      str->push_back('}');
  }
  
  Sdf_PrimVariantSelectionNode::~Sdf_PrimVariantSelectionNode() {
      _Remove(this, *_primVarSelNodes, GetParentNode(), *_variantSelection);
  }
  
  void
  Sdf_TargetPathNode::_AppendText(std::string *str) const {
      std::string const &open =
          SdfPathTokens->relationshipTargetStart.GetString();
      std::string const &target = _targetPath.GetString();
      std::string const &close =
          SdfPathTokens->relationshipTargetEnd.GetString();
      str->reserve(str->size() + open.size() + target.size() + close.size());
      str->append(open);
      str->append(target);
      str->append(close);
  }
  
  Sdf_TargetPathNode::~Sdf_TargetPathNode() {
      _Remove(this, *_targetNodes, GetParentNode(), _targetPath);
  }
  
  Sdf_RelationalAttributePathNode::~Sdf_RelationalAttributePathNode() {
      _Remove(this, *_relAttrNodes, GetParentNode(), _name);
  }
  
  void
  Sdf_MapperPathNode::_AppendText(std::string *str) const {
      std::string const &delim = SdfPathTokens->propertyDelimiter.GetString();
      std::string const &mapperIndicator =
          SdfPathTokens->mapperIndicator.GetString();
      std::string const &open =
          SdfPathTokens->relationshipTargetStart.GetString();
      std::string const &target = _targetPath.GetString();
      std::string const &close = SdfPathTokens->relationshipTargetEnd.GetString();
      str->reserve(str->size() + delim.size() + mapperIndicator.size() +
                   open.size() + target.size() + close.size());
      str->append(delim);
      str->append(mapperIndicator);
      str->append(open);
      str->append(target);
      str->append(close);
  }
  
  Sdf_MapperPathNode::~Sdf_MapperPathNode() {
      _Remove(this, *_mapperNodes, GetParentNode(), _targetPath);
  }
  
  void
  Sdf_MapperArgPathNode::_AppendText(std::string *str) const {
      std::string const &delim = SdfPathTokens->propertyDelimiter.GetString();
      std::string const &name = _name.GetString();
      str->reserve(str->size() + delim.size() + name.size());
      str->append(delim);
      str->append(name);
  }
  
  Sdf_MapperArgPathNode::~Sdf_MapperArgPathNode() {
      _Remove(this, *_mapperArgNodes, GetParentNode(), _name);
  }
  
  void
  Sdf_ExpressionPathNode::_AppendText(std::string *str) const {
      std::string const &delim = SdfPathTokens->propertyDelimiter.GetString();
      std::string const &expr = SdfPathTokens->expressionIndicator.GetString();
      str->reserve(str->size() + delim.size() + expr.size());
      str->append(delim);
      str->append(expr);
  }
  
  Sdf_ExpressionPathNode::~Sdf_ExpressionPathNode() {
      _Remove(this, *_expressionNodes, GetParentNode());
  }
  
  struct Sdf_Stats {
      // Counts
      int numNodes;
      int numNodeRefs;
  
      // Histograms
      vector<int> lengthTable;
      vector<int> numChildrenTable;
      size_t typeTable[Sdf_PathNode::NumNodeTypes];
  };
  
  template <class Table>
  static void
  _GatherChildrenFrom(Sdf_PathNode const *parent,
                      Table const &table,
                      vector<Sdf_PathNodeConstRefPtr> *result)
  {
      TF_FOR_ALL(i, table.map) {
          if (i->first.parent == parent)
              result->emplace_back(
                  reinterpret_cast<Sdf_PathNode const *>(i->second.GetPtr()));
      }
  }
  
  static vector<Sdf_PathNodeConstRefPtr>
  _GetChildren(Sdf_PathNode const *pathNode)
  {
      // XXX: SLOW.  For path stats debugging only.
      vector<Sdf_PathNodeConstRefPtr> children;
      _GatherChildrenFrom(pathNode, *_mapperNodes, &children);
      _GatherChildrenFrom(pathNode, *_targetNodes, &children);
      _GatherChildrenFrom(pathNode, *_mapperArgNodes, &children);
      _GatherChildrenFrom(pathNode, *_primNodes, &children);
      _GatherChildrenFrom(pathNode, *_primPropertyNodes, &children);
      _GatherChildrenFrom(pathNode, *_relAttrNodes, &children);
      _GatherChildrenFrom(pathNode, *_primVarSelNodes, &children);
      _GatherChildrenFrom(pathNode, *_expressionNodes, &children);
      return children;
  }
  
  static void _Visit(Sdf_PathNode const *path, Sdf_Stats *stats)
  {
      stats->numNodes++;
      stats->numNodeRefs += path->GetCurrentRefCount();
      stats->typeTable[path->GetNodeType()] += 1;
  
      // Accumulate length histogram
      const size_t len = path->GetElementCount()+1; // add 1 for abs/rel root
      while (stats->lengthTable.size() <= len)
          stats->lengthTable.push_back(0);
      stats->lengthTable[len]++;
  
      const std::vector<Sdf_PathNodeConstRefPtr> children = _GetChildren(path);
  
      // Accumulate children count histogram
      const size_t numChildren = children.size();
      while (stats->numChildrenTable.size() <= numChildren)
          stats->numChildrenTable.push_back(0);
      stats->numChildrenTable[numChildren]++;
  
      TF_FOR_ALL(child, children) {
          _Visit(child->get(), stats);
      }
  }
  
  void Sdf_DumpPathStats()
  {
      Sdf_Stats stats;
      stats.numNodes = 0;
      stats.numNodeRefs = 0;
      memset(stats.typeTable, 0, sizeof(stats.typeTable));
  
      _Visit( Sdf_PathNode::GetAbsoluteRootNode(), &stats );
      _Visit( Sdf_PathNode::GetRelativeRootNode(), &stats );
  
      printf("Sdf_PathNode stats:\n");
      printf("\tnum node refs: %i\n", stats.numNodeRefs);
      printf("\tnum nodes:     %i\n", stats.numNodes);
      printf("\tsizeof(SdfPath), aka node ref:  %zu\n", sizeof(SdfPath));
      printf("\tsizeof(Sdf_PathNode), aka node: %zu\n", sizeof(Sdf_PathNode));
  
      // XXX: Use TfEnum.
      char const *enumNameMap[Sdf_PathNode::NumNodeTypes];
      enumNameMap[Sdf_PathNode::RootNode] = "RootNode";
      enumNameMap[Sdf_PathNode::PrimNode] = "PrimNode";
      enumNameMap[Sdf_PathNode::PrimPropertyNode] = "PrimPropertyNode";
      enumNameMap[Sdf_PathNode::PrimVariantSelectionNode] =
          "PrimVariantSelectionNode";
      enumNameMap[Sdf_PathNode::TargetNode] = "TargetNode";
      enumNameMap[Sdf_PathNode::RelationalAttributeNode] =
          "RelationalAttributeNode";
      enumNameMap[Sdf_PathNode::MapperNode] = "MapperNode";
      enumNameMap[Sdf_PathNode::MapperArgNode] = "MapperArgNode";
      enumNameMap[Sdf_PathNode::ExpressionNode] = "ExpressionNode";
  
      printf("------------------------------------------------");
      printf("-- By Type\n");
      for (size_t i = 0; i != Sdf_PathNode::NumNodeTypes; ++i) {
          printf("\t%32ss: %8zu -- %6.2f%%\n",
                 enumNameMap[i], stats.typeTable[i],
                 100.0 * double(stats.typeTable[i]) / double(stats.numNodes));
      }
  
      printf("------------------------------------------------");
      printf("-- By Length\n");
      size_t totalLen = 0;
      for (size_t i=0; i < stats.lengthTable.size();++i) {
          printf("\tnum nodes with %3zu components : %i\n",
                 i, stats.lengthTable[i] );
          totalLen += i * stats.lengthTable[i];
      }
      printf("\tavg num components: %g\n",
             totalLen / float(stats.numNodes));
  
      printf("------------------------------------------------");
      printf("-- By Number of Children\n");
      for (size_t i=0; i < stats.numChildrenTable.size(); ++i) {
          printf("\tnum nodes with %3zu children : %i\n",
                 i, stats.numChildrenTable[i] );
      }
  
      size_t numChildren = 0;
      for (size_t i=1; i < stats.numChildrenTable.size(); ++i) {
          numChildren += i*stats.numChildrenTable[i];
      }
      printf("\tavg num children (for nodes with any children): %g\n",
             numChildren / float(stats.numNodes - stats.numChildrenTable[0]));
  
      printf("\n");
  }
  
  PXR_NAMESPACE_CLOSE_SCOPE
  