1 //===-- SequenceToOffsetTable.h - Compress similar sequences ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
14 //===----------------------------------------------------------------------===//
16 #ifndef TBLGEN_SEQUENCE_TO_OFFSET_TABLE_H
17 #define TBLGEN_SEQUENCE_TO_OFFSET_TABLE_H
19 #include "llvm/Support/raw_ostream.h"
29 /// SequenceToOffsetTable - Collect a number of terminated sequences of T.
30 /// Compute the layout of a table that contains all the sequences, possibly by
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;
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> {
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);
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;
53 // Sequences added so far, with suffixes removed.
56 // Entries in the final table, or 0 before layout was called.
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());
65 SequenceToOffsetTable() : Entries(0) {}
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);
73 // If SeqMap contains a sequence that has Seq as a suffix, I will be
75 if (I != Seqs.end() && isSuffix(Seq, I->first))
78 I = Seqs.insert(I, std::make_pair(Seq, 0u));
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))
85 bool empty() const { return Seqs.empty(); }
87 /// layout - Computes the final table layout.
89 assert(Entries == 0 && "Can only call layout() once");
90 // Lay out the table in Seqs iteration order.
91 for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
94 // Include space for a terminator.
95 Entries += I->first.size() + 1;
99 /// get - Returns the offset of Seq in the final table.
100 unsigned get(const SeqT &Seq) const {
101 assert(Entries && "Call layout() before get()");
102 typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
103 assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
104 "get() called with sequence that wasn't added first");
105 return I->second + (I->first.size() - Seq.size());
108 /// emit - Print out the table as the body of an array initializer.
109 /// Use the Print function to print elements.
110 void emit(raw_ostream &OS,
111 void (*Print)(raw_ostream&, ElemT),
112 const char *Term = "0") const {
113 assert(Entries && "Call layout() before emit()");
114 for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
116 OS << " /* " << I->second << " */ ";
117 for (typename SeqT::const_iterator SI = I->first.begin(),
118 SE = I->first.end(); SI != SE; ++SI) {
127 // Helper function for SequenceToOffsetTable<string>.
128 static inline void printChar(raw_ostream &OS, char C) {
130 if (isalnum(UC) || ispunct(UC)) {
132 if (C == '\\' || C == '\'')
140 } // end namespace llvm