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