Home | History | Annotate | Download | only in TableGen 
      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
    148