lld/COFF/DebugTypes.cpp

908 /// A concurrent hash table for global type hashing. It is based on this paper:
912 /// This hash table is meant to be used in two phases:
919 /// those values to recover the ghash key from a side table. This allows us to
920 /// shrink the table entries further at the cost of some loads, and sidesteps
929   GHashCell *table = nullptr;
935   /// Initialize the table with the given size. Because the table cannot be
936   /// resized, the initial size of the table must be large enough to contain all
940   /// Insert the cell with the given ghash into the table. Return the insertion
941   /// position in the table. It is safe for the caller to store the insertion
942   /// position because the table cannot be resized.
947 /// A ghash table cell for deduplicating types from TpiSources.
1004   GHashTable table;
1008 GHashTable::~GHashTable() { delete[] table; }
1011   table = new GHashCell[newTableSize];
1012   memset(table, 0, newTableSize * sizeof(GHashCell));
1034     auto *cellPtr = reinterpret_cast<std::atomic<GHashCell> *>(&table[idx]);
1053       // beginning with a bigger table. There is no difference between rehashing
1055       report_fatal_error("ghash table is full");
1079   // Estimate the size of hash table needed to deduplicate ghashes. This *must*
1080   // be larger than the number of unique types, or hash table insertion may not
1082   // it is a gross overestimate. The table size could be reduced to save memory,
1083   // but it would require implementing rehashing, and this table is generally
1090   // Cap the table size so that we can use 32-bit cell indices. Type indices are
1094   ghashState.table.init(static_cast<uint32_t>(tableSize));
1097   // the contents of the hash table cell, but we can remember the insertion
1098   // position. Because the table does not rehash, the position will not change
1112           ghashState.table.insert(ctx, ghash, GHashCell(isItem, tpiSrcIdx, i));
1130   for (const GHashCell &cell : ArrayRef(ghashState.table.table, tableSize)) {
1135   log(formatv("ghash table load factor: {0:p} (size {1} / capacity {2})\n",
1159     // Update the ghash table to store the destination PDB type index in the
1160     // table.
1164     ghashState.table.table[ghashCellIndex] =
1201 /// Given the index into the ghash table for a particular type, return the type
1205   GHashCell cell = g->table.table[ghashCellIdx];