1 //===-- SequenceToOffsetTable.h - Compress similar sequences ----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // SequenceToOffsetTable can be used to emit a number of null-terminated 10 // sequences as one big array. Use the same memory when a sequence is a suffix 11 // of another. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H 16 #define LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H 17 18 #include "llvm/Support/CommandLine.h" 19 #include "llvm/Support/raw_ostream.h" 20 #include <algorithm> 21 #include <cassert> 22 #include <cctype> 23 #include <functional> 24 #include <map> 25 26 namespace llvm { 27 extern llvm::cl::opt<bool> EmitLongStrLiterals; 28 29 static inline void printChar(raw_ostream &OS, char C) { 30 unsigned char UC(C); 31 if (isalnum(UC) || ispunct(UC)) { 32 OS << '\''; 33 if (C == '\\' || C == '\'') 34 OS << '\\'; 35 OS << C << '\''; 36 } else { 37 OS << unsigned(UC); 38 } 39 } 40 41 /// SequenceToOffsetTable - Collect a number of terminated sequences of T. 42 /// Compute the layout of a table that contains all the sequences, possibly by 43 /// reusing entries. 44 /// 45 /// @tparam SeqT The sequence container. (vector or string). 46 /// @tparam Less A stable comparator for SeqT elements. 47 template<typename SeqT, typename Less = std::less<typename SeqT::value_type> > 48 class SequenceToOffsetTable { 49 typedef typename SeqT::value_type ElemT; 50 51 // Define a comparator for SeqT that sorts a suffix immediately before a 52 // sequence with that suffix. 53 struct SeqLess { 54 Less L; 55 bool operator()(const SeqT &A, const SeqT &B) const { 56 return std::lexicographical_compare(A.rbegin(), A.rend(), 57 B.rbegin(), B.rend(), L); 58 } 59 }; 60 61 // Keep sequences ordered according to SeqLess so suffixes are easy to find. 62 // Map each sequence to its offset in the table. 63 typedef std::map<SeqT, unsigned, SeqLess> SeqMap; 64 65 // Sequences added so far, with suffixes removed. 66 SeqMap Seqs; 67 68 // Entries in the final table, or 0 before layout was called. 69 unsigned Entries; 70 71 // isSuffix - Returns true if A is a suffix of B. 72 static bool isSuffix(const SeqT &A, const SeqT &B) { 73 return A.size() <= B.size() && std::equal(A.rbegin(), A.rend(), B.rbegin()); 74 } 75 76 public: 77 SequenceToOffsetTable() : Entries(0) {} 78 79 /// add - Add a sequence to the table. 80 /// This must be called before layout(). 81 void add(const SeqT &Seq) { 82 assert(Entries == 0 && "Cannot call add() after layout()"); 83 typename SeqMap::iterator I = Seqs.lower_bound(Seq); 84 85 // If SeqMap contains a sequence that has Seq as a suffix, I will be 86 // pointing to it. 87 if (I != Seqs.end() && isSuffix(Seq, I->first)) 88 return; 89 90 I = Seqs.insert(I, std::make_pair(Seq, 0u)); 91 92 // The entry before I may be a suffix of Seq that can now be erased. 93 if (I != Seqs.begin() && isSuffix((--I)->first, Seq)) 94 Seqs.erase(I); 95 } 96 97 bool empty() const { return Seqs.empty(); } 98 99 unsigned size() const { 100 assert((empty() || Entries) && "Call layout() before size()"); 101 return Entries; 102 } 103 104 /// layout - Computes the final table layout. 105 void layout() { 106 assert(Entries == 0 && "Can only call layout() once"); 107 // Lay out the table in Seqs iteration order. 108 for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E; 109 ++I) { 110 I->second = Entries; 111 // Include space for a terminator. 112 Entries += I->first.size() + 1; 113 } 114 } 115 116 /// get - Returns the offset of Seq in the final table. 117 unsigned get(const SeqT &Seq) const { 118 assert(Entries && "Call layout() before get()"); 119 typename SeqMap::const_iterator I = Seqs.lower_bound(Seq); 120 assert(I != Seqs.end() && isSuffix(Seq, I->first) && 121 "get() called with sequence that wasn't added first"); 122 return I->second + (I->first.size() - Seq.size()); 123 } 124 125 /// `emitStringLiteralDef` - Print out the table as the body of an array 126 /// initializer, where each element is a C string literal terminated by 127 /// `\0`. Falls back to emitting a comma-separated integer list if 128 /// `EmitLongStrLiterals` is false 129 void emitStringLiteralDef(raw_ostream &OS, const llvm::Twine &Decl) const { 130 assert(Entries && "Call layout() before emitStringLiteralDef()"); 131 if (!EmitLongStrLiterals) { 132 OS << Decl << " = {\n"; 133 emit(OS, printChar, "0"); 134 OS << " 0\n};\n\n"; 135 return; 136 } 137 138 OS << "\n#ifdef __GNUC__\n" 139 << "#pragma GCC diagnostic push\n" 140 << "#pragma GCC diagnostic ignored \"-Woverlength-strings\"\n" 141 << "#endif\n" 142 << Decl << " = {\n"; 143 for (auto I : Seqs) { 144 OS << " /* " << I.second << " */ \""; 145 OS.write_escaped(I.first); 146 OS << "\\0\"\n"; 147 } 148 OS << "};\n" 149 << "#ifdef __GNUC__\n" 150 << "#pragma GCC diagnostic pop\n" 151 << "#endif\n\n"; 152 } 153 154 /// emit - Print out the table as the body of an array initializer. 155 /// Use the Print function to print elements. 156 void emit(raw_ostream &OS, 157 void (*Print)(raw_ostream&, ElemT), 158 const char *Term = "0") const { 159 assert((empty() || Entries) && "Call layout() before emit()"); 160 for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end(); 161 I != E; ++I) { 162 OS << " /* " << I->second << " */ "; 163 for (typename SeqT::const_iterator SI = I->first.begin(), 164 SE = I->first.end(); SI != SE; ++SI) { 165 Print(OS, *SI); 166 OS << ", "; 167 } 168 OS << Term << ",\n"; 169 } 170 } 171 }; 172 173 } // end namespace llvm 174 175 #endif 176