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/raw_ostream.h" 19 #include <algorithm> 20 #include <cassert> 21 #include <cctype> 22 #include <functional> 23 #include <map> 24 25 namespace llvm { 26 27 /// SequenceToOffsetTable - Collect a number of terminated sequences of T. 28 /// Compute the layout of a table that contains all the sequences, possibly by 29 /// reusing entries. 30 /// 31 /// @tparam SeqT The sequence container. (vector or string). 32 /// @tparam Less A stable comparator for SeqT elements. 33 template<typename SeqT, typename Less = std::less<typename SeqT::value_type> > 34 class SequenceToOffsetTable { 35 typedef typename SeqT::value_type ElemT; 36 37 // Define a comparator for SeqT that sorts a suffix immediately before a 38 // sequence with that suffix. 39 struct SeqLess { 40 Less L; 41 bool operator()(const SeqT &A, const SeqT &B) const { 42 return std::lexicographical_compare(A.rbegin(), A.rend(), 43 B.rbegin(), B.rend(), L); 44 } 45 }; 46 47 // Keep sequences ordered according to SeqLess so suffixes are easy to find. 48 // Map each sequence to its offset in the table. 49 typedef std::map<SeqT, unsigned, SeqLess> SeqMap; 50 51 // Sequences added so far, with suffixes removed. 52 SeqMap Seqs; 53 54 // Entries in the final table, or 0 before layout was called. 55 unsigned Entries; 56 57 // isSuffix - Returns true if A is a suffix of B. 58 static bool isSuffix(const SeqT &A, const SeqT &B) { 59 return A.size() <= B.size() && std::equal(A.rbegin(), A.rend(), B.rbegin()); 60 } 61 62 public: 63 SequenceToOffsetTable() : Entries(0) {} 64 65 /// add - Add a sequence to the table. 66 /// This must be called before layout(). 67 void add(const SeqT &Seq) { 68 assert(Entries == 0 && "Cannot call add() after layout()"); 69 typename SeqMap::iterator I = Seqs.lower_bound(Seq); 70 71 // If SeqMap contains a sequence that has Seq as a suffix, I will be 72 // pointing to it. 73 if (I != Seqs.end() && isSuffix(Seq, I->first)) 74 return; 75 76 I = Seqs.insert(I, std::make_pair(Seq, 0u)); 77 78 // The entry before I may be a suffix of Seq that can now be erased. 79 if (I != Seqs.begin() && isSuffix((--I)->first, Seq)) 80 Seqs.erase(I); 81 } 82 83 bool empty() const { return Seqs.empty(); } 84 85 unsigned size() const { 86 assert((empty() || Entries) && "Call layout() before size()"); 87 return Entries; 88 } 89 90 /// layout - Computes the final table layout. 91 void layout() { 92 assert(Entries == 0 && "Can only call layout() once"); 93 // Lay out the table in Seqs iteration order. 94 for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E; 95 ++I) { 96 I->second = Entries; 97 // Include space for a terminator. 98 Entries += I->first.size() + 1; 99 } 100 } 101 102 /// get - Returns the offset of Seq in the final table. 103 unsigned get(const SeqT &Seq) const { 104 assert(Entries && "Call layout() before get()"); 105 typename SeqMap::const_iterator I = Seqs.lower_bound(Seq); 106 assert(I != Seqs.end() && isSuffix(Seq, I->first) && 107 "get() called with sequence that wasn't added first"); 108 return I->second + (I->first.size() - Seq.size()); 109 } 110 111 /// emit - Print out the table as the body of an array initializer. 112 /// Use the Print function to print elements. 113 void emit(raw_ostream &OS, 114 void (*Print)(raw_ostream&, ElemT), 115 const char *Term = "0") const { 116 assert((empty() || Entries) && "Call layout() before emit()"); 117 for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end(); 118 I != E; ++I) { 119 OS << " /* " << I->second << " */ "; 120 for (typename SeqT::const_iterator SI = I->first.begin(), 121 SE = I->first.end(); SI != SE; ++SI) { 122 Print(OS, *SI); 123 OS << ", "; 124 } 125 OS << Term << ",\n"; 126 } 127 } 128 }; 129 130 // Helper function for SequenceToOffsetTable<string>. 131 static inline void printChar(raw_ostream &OS, char C) { 132 unsigned char UC(C); 133 if (isalnum(UC) || ispunct(UC)) { 134 OS << '\''; 135 if (C == '\\' || C == '\'') 136 OS << '\\'; 137 OS << C << '\''; 138 } else { 139 OS << unsigned(UC); 140 } 141 } 142 143 } // end namespace llvm 144 145 #endif 146