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