Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
       2             : /* vim: set ts=2 et sw=2 tw=80: */
       3             : /* This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
       5             :  * You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #ifndef memory_profiler_CompactTraceTable_h
       8             : #define memory_profiler_CompactTraceTable_h
       9             : 
      10             : #include "mozilla/HashFunctions.h"
      11             : 
      12             : #include "nsDataHashtable.h"
      13             : #include "nsTArray.h"
      14             : 
      15             : namespace mozilla {
      16             : 
      17             : struct TrieNode final
      18             : {
      19             :   uint32_t parentIdx;
      20             :   uint32_t nameIdx;
      21           0 :   bool operator==(const TrieNode t) const
      22             :   {
      23           0 :     return parentIdx == t.parentIdx && nameIdx == t.nameIdx;
      24             :   }
      25           0 :   uint32_t Hash() const
      26             :   {
      27           0 :     return HashGeneric(parentIdx, nameIdx);
      28             :   }
      29             : };
      30             : 
      31             : // This class maps a Node of type T to its parent's index in the
      32             : // map. When serializing, the map is traversed and put into an ordered
      33             : // array of Nodes.
      34             : template<typename KeyClass, typename T>
      35           0 : class NodeIndexMap final
      36             : {
      37             : public:
      38           0 :   uint32_t Insert(const T& e)
      39             :   {
      40           0 :     uint32_t index = mMap.Count();
      41           0 :     if (!mMap.Get(e, &index)) {
      42           0 :       mMap.Put(e, index);
      43             :     }
      44           0 :     return index;
      45             :   }
      46             : 
      47           0 :   nsTArray<T> Serialize() const
      48             :   {
      49           0 :     nsTArray<T> v;
      50           0 :     v.SetLength(mMap.Count());
      51           0 :     for (auto iter = mMap.ConstIter(); !iter.Done(); iter.Next()) {
      52           0 :       v[iter.Data()] = iter.Key();
      53             :     }
      54           0 :     return v;
      55             :   }
      56             : 
      57             :   uint32_t Size() const
      58             :   {
      59             :     return mMap.Count();
      60             :   }
      61             : 
      62           0 :   void Clear()
      63             :   {
      64           0 :     mMap.Clear();
      65           0 :   }
      66             : private:
      67             :   nsDataHashtable<KeyClass, uint32_t> mMap;
      68             : };
      69             : 
      70             : // Backtraces are stored in a trie to save spaces.
      71             : // Function names are stored in an unique table and TrieNodes contain indexes
      72             : // into that table.
      73             : // The trie is implemented with a hash table; children are stored in
      74             : // traces[TrieNode{parent node index, branch/function name index}].
      75           0 : class CompactTraceTable final
      76             : {
      77             : public:
      78           0 :   CompactTraceTable()
      79           0 :   {
      80           0 :     mNames.Insert(nsAutoCString("(unknown)"));
      81           0 :     mTraces.Insert(TrieNode{0, 0});
      82           0 :   }
      83             : 
      84           0 :   nsTArray<nsCString> GetNames() const
      85             :   {
      86           0 :     return mNames.Serialize();
      87             :   }
      88             : 
      89           0 :   nsTArray<TrieNode> GetTraces() const
      90             :   {
      91           0 :     return mTraces.Serialize();
      92             :   }
      93             : 
      94             :   // Returns an ID to a stacktrace.
      95           0 :   uint32_t Insert(const nsTArray<nsCString>& aRawStacktrace)
      96             :   {
      97           0 :     uint32_t parent = 0;
      98           0 :     for (auto& frame: aRawStacktrace) {
      99           0 :       parent = mTraces.Insert(TrieNode{parent, mNames.Insert(frame)});
     100             :     }
     101           0 :     return parent;
     102             :   }
     103             : 
     104           0 :   void Reset()
     105             :   {
     106           0 :     mNames.Clear();
     107           0 :     mTraces.Clear();
     108           0 :   }
     109             : private:
     110             :   NodeIndexMap<nsCStringHashKey, nsCString> mNames;
     111             :   NodeIndexMap<nsGenericHashKey<TrieNode>, TrieNode> mTraces;
     112             : };
     113             : 
     114             : } // namespace mozilla
     115             : 
     116             : #endif // memory_profiler_CompactTraceTable_h