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 <functional>
21 #include <algorithm>
22 #include <vector>
23 #include <cassert>
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 /// @param SeqT The sequence container. (vector or string).
32 /// @param 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 : public std::binary_function<SeqT, SeqT, bool> {
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   /// layout - Computes the final table layout.
84   void layout() {
85     assert(Entries == 0 && "Can only call layout() once");
86     // Lay out the table in Seqs iteration order.
87     for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
88          ++I) {
89       I->second = Entries;
90       // Include space for a terminator.
91       Entries += I->first.size() + 1;
92     }
93   }
94 
95   /// get - Returns the offset of Seq in the final table.
96   unsigned get(const SeqT &Seq) const {
97     assert(Entries && "Call layout() before get()");
98     typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
99     assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
100            "get() called with sequence that wasn't added first");
101     return I->second + (I->first.size() - Seq.size());
102   }
103 
104   /// emit - Print out the table as the body of an array initializer.
105   /// Use the Print function to print elements.
106   void emit(raw_ostream &OS,
107             void (*Print)(raw_ostream&, ElemT),
108             const char *Term = "0") const {
109     assert(Entries && "Call layout() before emit()");
110     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
111          I != E; ++I) {
112       OS << "  /* " << I->second << " */ ";
113       for (typename SeqT::const_iterator SI = I->first.begin(),
114              SE = I->first.end(); SI != SE; ++SI) {
115         Print(OS, *SI);
116         OS << ", ";
117       }
118       OS << Term << ",\n";
119     }
120   }
121 };
122 
123 } // end namespace llvm
124 
125 #endif
126