utils/TableGen/SequenceToOffsetTable.h

   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 #include <vector>
  26
  27 namespace llvm {
  28
  29 /// SequenceToOffsetTable - Collect a number of terminated sequences of T.
  30 /// Compute the layout of a table that contains all the sequences, possibly by
  31 /// reusing entries.
  32 ///
  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;
  38
  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> {
  42     Less L;
  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);
  46     }
  47   };
  48
  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;
  52
  53   // Sequences added so far, with suffixes removed.
  54   SeqMap Seqs;
  55
  56   // Entries in the final table, or 0 before layout was called.
  57   unsigned Entries;
  58
  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());
  62   }
  63
  64 public:
  65   SequenceToOffsetTable() : Entries(0) {}
  66
  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);
  72
  73     // If SeqMap contains a sequence that has Seq as a suffix, I will be
  74     // pointing to it.
  75     if (I != Seqs.end() && isSuffix(Seq, I->first))
  76       return;
  77
  78     I = Seqs.insert(I, std::make_pair(Seq, 0u));
  79
  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))
  82       Seqs.erase(I);
  83   }
  84
  85   bool empty() const { return Seqs.empty(); }
  86
  87   unsigned size() const {
  88     assert(Entries && "Call layout() before size()");
  89     return Entries;
  90   }
  91
  92   /// layout - Computes the final table layout.
  93   void layout() {
  94     assert(Entries == 0 && "Can only call layout() once");
  95     // Lay out the table in Seqs iteration order.
  96     for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
  97          ++I) {
  98       I->second = Entries;
  99       // Include space for a terminator.
 100       Entries += I->first.size() + 1;
 101     }
 102   }
 103
 104   /// get - Returns the offset of Seq in the final table.
 105   unsigned get(const SeqT &Seq) const {
 106     assert(Entries && "Call layout() before get()");
 107     typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
 108     assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
 109            "get() called with sequence that wasn't added first");
 110     return I->second + (I->first.size() - Seq.size());
 111   }
 112
 113   /// emit - Print out the table as the body of an array initializer.
 114   /// Use the Print function to print elements.
 115   void emit(raw_ostream &OS,
 116             void (*Print)(raw_ostream&, ElemT),
 117             const char *Term = "0") const {
 118     assert(Entries && "Call layout() before emit()");
 119     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
 120          I != E; ++I) {
 121       OS << "  /* " << I->second << " */ ";
 122       for (typename SeqT::const_iterator SI = I->first.begin(),
 123              SE = I->first.end(); SI != SE; ++SI) {
 124         Print(OS, *SI);
 125         OS << ", ";
 126       }
 127       OS << Term << ",\n";
 128     }
 129   }
 130 };
 131
 132 // Helper function for SequenceToOffsetTable<string>.
 133 static inline void printChar(raw_ostream &OS, char C) {
 134   unsigned char UC(C);
 135   if (isalnum(UC) || ispunct(UC)) {
 136     OS << '\'';
 137     if (C == '\\' || C == '\'')
 138       OS << '\\';
 139     OS << C << '\'';
 140   } else {
 141     OS << unsigned(UC);
 142   }
 143 }
 144
 145 } // end namespace llvm
 146
 147 #endif