[DWARFLinkerParallel] Add StringTable class.

[avl]

Summary

This patch adds StringTable class which is used to prepare
strings for emission into the .debug_str table. Specifically,
this class translates strings if necessary, keeps them in order,
assigns index and offset.

[JDevlieghere]

llvm/include/llvm/DWARFLinkerParallel/StringsForEmission.h

22 ↗

(On Diff #510782)

Should we call this StringTable?

32 ↗

(On Diff #510782)

71 ↗

(On Diff #510782)

74 ↗

(On Diff #510782)

77 ↗

(On Diff #510782)

[avl]

addressed comments.

[JDevlieghere]

LGTM

[avl]

Thanks!

llvm/include/llvm/DWARFLinkerParallel/StringPool.h

StringPool()
                                  PerThreadStringAllocator, StringPoolEntryInfo>(
             Allocator) {}
 
   StringPool(size_t InitialSize)
       : ConcurrentHashTableByPtr<StringRef, StringEntry,
                                  PerThreadStringAllocator, StringPoolEntryInfo>(
             Allocator, InitialSize) {}
 
+  PerThreadStringAllocator &getAllocatorRef() { return Allocator; }
+
 private:
   PerThreadStringAllocator Allocator;
 };
 
 } // end of namespace dwarflinker_parallel
 } // end namespace llvm
 
 #endif // LLVM_DWARFLINKERPARALLEL_STRINGPOOL_H

llvm/include/llvm/DWARFLinkerParallel/StringTable.h

+//===- StringTable.h --------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DWARFLINKERPARALLEL_STRINGTABLE_H
+#define LLVM_DWARFLINKERPARALLEL_STRINGTABLE_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/DWARFLinkerParallel/StringPool.h"
+
+namespace llvm {
+namespace dwarflinker_parallel {
+
+using StringsVector = SmallVector<StringEntry *>;
+
+/// This class prepares strings for emission into .debug_str table:
+/// translates string if necessary, assigns index and offset, keeps in order.
+class StringTable {
+public:
+  StringTable(StringPool &Strings,
+              std::function<StringRef(StringRef)> StringsTranslator)
+      : Strings(Strings), StringsTranslator(StringsTranslator) {}
+  ~StringTable() {}
+
+  /// Add string to the vector of strings which should be emitted.
+  /// Translate input string if neccessary, assign index and offset.
+  /// \returns updated string entry.
+  StringEntry *add(StringEntry *String) {
+    // Translate string if necessary.
+    if (StringsTranslator)
+      String = Strings.insert(StringsTranslator(String->first())).first;
+
+    // Store String for emission and assign index and offset.
+    if (String->getValue() == nullptr) {
+      DwarfStringPoolEntry *NewEntry =
+          Strings.getAllocatorRef().Allocate<DwarfStringPoolEntry>();
+
+      NewEntry->Symbol = nullptr;
+      NewEntry->Index = StringEntriesForEmission.size();
+
+      if (StringEntriesForEmission.empty())
+        NewEntry->Offset = 0;
+      else {
+        StringEntry *PrevString = StringEntriesForEmission.back();
+        NewEntry->Offset =
+            PrevString->getValue()->Offset + PrevString->getKeyLength() + 1;
+      }
+
+      String->getValue() = NewEntry;
+      StringEntriesForEmission.push_back(String);
+    }
+
+    return String;
+  }
+
+  /// Erase contents of StringsForEmission.
+  void clear() { StringEntriesForEmission.clear(); }
+
+  /// Enumerate all strings in sequential order and call \p Handler for each
+  /// string.
+  void forEach(function_ref<void(DwarfStringPoolEntryRef)> Handler) const {
+    for (const StringEntry *Entry : StringEntriesForEmission)
+      Handler(*Entry);
+  }
+
+protected:
+  /// List of strings for emission.
+  StringsVector StringEntriesForEmission;
+
+  /// String pool for the translated strings.
+  StringPool &Strings;
+
+  /// Translator for the strings.
+  std::function<StringRef(StringRef)> StringsTranslator;
+};
+
+} // end of namespace dwarflinker_parallel
+} // end namespace llvm
+
+#endif // LLVM_DWARFLINKERPARALLEL_STRINGTABLE_H

llvm/unittests/DWARFLinkerParallel/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   DWARFLinkerParallel
   )
 
 add_llvm_unittest(DWARFLinkerParallelTests
   DWARFLinkerTest.cpp
   StringPoolTest.cpp
+  StringTableTest.cpp
   )
 
 target_link_libraries(DWARFLinkerParallelTests PRIVATE LLVMTestingSupport)
 
 add_dependencies(DWARFLinkerParallelTests intrinsics_gen)

llvm/unittests/DWARFLinkerParallel/StringTableTest.cpp

+//===- llvm/unittest/DWARFLinkerParallel/StringTableTest.cpp --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DWARFLinkerParallel/StringTable.h"
+#include "llvm/Support/Parallel.h"
+#include "gtest/gtest.h"
+#include <cstdlib>
+
+using namespace llvm;
+using namespace dwarflinker_parallel;
+
+namespace {
+
+TEST(StringPoolTest, TestStringTable) {
+  struct StringDescription {
+    const char *Str = nullptr;
+    uint64_t Idx = 0;
+    uint64_t Offset = 0;
+  };
+
+  SmallVector<StringDescription> InputStrings = {
+      {"first", 0, 0}, {"second", 1, 6}, {"third", 2, 13}};
+
+  StringPool Strings;
+  StringTable OutStrings(Strings, nullptr);
+
+  // Check string insertion.
+  StringEntry *FirstPtr = Strings.insert(InputStrings[0].Str).first;
+  StringEntry *SecondPtr = Strings.insert(InputStrings[1].Str).first;
+  StringEntry *ThirdPtr = Strings.insert(InputStrings[2].Str).first;
+
+  FirstPtr = OutStrings.add(FirstPtr);
+  SecondPtr = OutStrings.add(SecondPtr);
+  ThirdPtr = OutStrings.add(ThirdPtr);
+
+  // Check fields of inserted strings.
+  EXPECT_TRUE(FirstPtr->getKey() == InputStrings[0].Str);
+  EXPECT_TRUE(FirstPtr->getValue()->Offset == InputStrings[0].Offset);
+  EXPECT_TRUE(FirstPtr->getValue()->Index == InputStrings[0].Idx);
+
+  EXPECT_TRUE(SecondPtr->getKey() == InputStrings[1].Str);
+  EXPECT_TRUE(SecondPtr->getValue()->Offset == InputStrings[1].Offset);
+  EXPECT_TRUE(SecondPtr->getValue()->Index == InputStrings[1].Idx);
+
+  EXPECT_TRUE(ThirdPtr->getKey() == InputStrings[2].Str);
+  EXPECT_TRUE(ThirdPtr->getValue()->Offset == InputStrings[2].Offset);
+  EXPECT_TRUE(ThirdPtr->getValue()->Index == InputStrings[2].Idx);
+
+  // Check order enumerated strings.
+  uint64_t CurIdx = 0;
+  std::function<void(DwarfStringPoolEntryRef)> checkStr =
+      [&](DwarfStringPoolEntryRef Entry) {
+        EXPECT_TRUE(Entry.getEntry().isIndexed());
+        EXPECT_TRUE(Entry.getIndex() == CurIdx);
+        EXPECT_TRUE(Entry.getOffset() == InputStrings[CurIdx].Offset);
+        EXPECT_TRUE(Entry.getString() == InputStrings[CurIdx].Str);
+
+        CurIdx++;
+      };
+
+  OutStrings.forEach(checkStr);
+}
+
+TEST(StringPoolTest, TestStringTableWithTranslator) {
+  std::string Word;
+  std::function<StringRef(StringRef)> TranslatorFunc =
+      [&](StringRef InputString) -> StringRef {
+    Word.clear();
+    for (auto Sym : InputString)
+      Word.insert(Word.begin(), Sym);
+    Word += '0';
+    return Word;
+  };
+
+  StringPool Strings;
+  StringTable OutStrings(Strings, TranslatorFunc);
+
+  StringEntry *FirstPtr = Strings.insert("first").first;
+  StringEntry *SecondPtr = Strings.insert("second").first;
+  StringEntry *ThirdPtr = Strings.insert("third").first;
+
+  FirstPtr = OutStrings.add(FirstPtr);
+  SecondPtr = OutStrings.add(SecondPtr);
+  ThirdPtr = OutStrings.add(ThirdPtr);
+
+  EXPECT_TRUE(FirstPtr->getKey() == "tsrif0");
+  EXPECT_TRUE(FirstPtr->getValue()->Offset == 0);
+  EXPECT_TRUE(FirstPtr->getValue()->Index == 0);
+
+  EXPECT_TRUE(SecondPtr->getKey() == "dnoces0");
+  EXPECT_TRUE(SecondPtr->getValue()->Offset == 7);
+  EXPECT_TRUE(SecondPtr->getValue()->Index == 1);
+
+  EXPECT_TRUE(ThirdPtr->getKey() == "driht0");
+  EXPECT_TRUE(ThirdPtr->getValue()->Offset == 15);
+  EXPECT_TRUE(ThirdPtr->getValue()->Index == 2);
+}
+
+} // anonymous namespace