SequenceToOffsetTable.h revision 387c9dcddabe8551468647b249d3629953caab9e 
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#include <cctype>
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/// @param SeqT The sequence container. (vector or string).
33/// @param 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