• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
26 namespace 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.
34 template<typename SeqT, typename Less = std::less<typename SeqT::value_type> >
35 class 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;
operatorSeqLess42     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.
isSuffix(const SeqT & A,const SeqT & 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 
63 public:
SequenceToOffsetTable()64   SequenceToOffsetTable() : Entries(0) {}
65 
66   /// add - Add a sequence to the table.
67   /// This must be called before layout().
add(const SeqT & Seq)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 
empty()84   bool empty() const { return Seqs.empty(); }
85 
size()86   unsigned size() const {
87     assert(Entries && "Call layout() before size()");
88     return Entries;
89   }
90 
91   /// layout - Computes the final table layout.
layout()92   void layout() {
93     assert(Entries == 0 && "Can only call layout() once");
94     // Lay out the table in Seqs iteration order.
95     for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
96          ++I) {
97       I->second = Entries;
98       // Include space for a terminator.
99       Entries += I->first.size() + 1;
100     }
101   }
102 
103   /// get - Returns the offset of Seq in the final table.
get(const SeqT & Seq)104   unsigned get(const SeqT &Seq) const {
105     assert(Entries && "Call layout() before get()");
106     typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
107     assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
108            "get() called with sequence that wasn't added first");
109     return I->second + (I->first.size() - Seq.size());
110   }
111 
112   /// emit - Print out the table as the body of an array initializer.
113   /// Use the Print function to print elements.
114   void emit(raw_ostream &OS,
115             void (*Print)(raw_ostream&, ElemT),
116             const char *Term = "0") const {
117     assert(Entries && "Call layout() before emit()");
118     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
119          I != E; ++I) {
120       OS << "  /* " << I->second << " */ ";
121       for (typename SeqT::const_iterator SI = I->first.begin(),
122              SE = I->first.end(); SI != SE; ++SI) {
123         Print(OS, *SI);
124         OS << ", ";
125       }
126       OS << Term << ",\n";
127     }
128   }
129 };
130 
131 // Helper function for SequenceToOffsetTable<string>.
printChar(raw_ostream & OS,char C)132 static inline void printChar(raw_ostream &OS, char C) {
133   unsigned char UC(C);
134   if (isalnum(UC) || ispunct(UC)) {
135     OS << '\'';
136     if (C == '\\' || C == '\'')
137       OS << '\\';
138     OS << C << '\'';
139   } else {
140     OS << unsigned(UC);
141   }
142 }
143 
144 } // end namespace llvm
145 
146 #endif
147