utils/TableGen/SequenceToOffsetTable.h

   1 //===-- SequenceToOffsetTable.h - Compress similar sequences ----*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // SequenceToOffsetTable can be used to emit a number of null-terminated
  10 // sequences as one big array.  Use the same memory when a sequence is a suffix
  11 // of another.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H
  16 #define LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H
  17
  18 #include "llvm/Support/raw_ostream.h"
  19 #include <algorithm>
  20 #include <cassert>
  21 #include <cctype>
  22 #include <functional>
  23 #include <map>
  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 /// @tparam SeqT The sequence container. (vector or string).
  32 /// @tparam 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 {
  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   bool empty() const { return Seqs.empty(); }
  84
  85   unsigned size() const {
  86     assert(Entries && "Call layout() before size()");
  87     return Entries;
  88   }
  89
  90   /// layout - Computes the final table layout.
  91   void layout() {
  92     assert(Entries == 0 && "Can only call layout() once");
  93     // Lay out the table in Seqs iteration order.
  94     for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
  95          ++I) {
  96       I->second = Entries;
  97       // Include space for a terminator.
  98       Entries += I->first.size() + 1;
  99     }
 100   }
 101
 102   /// get - Returns the offset of Seq in the final table.
 103   unsigned get(const SeqT &Seq) const {
 104     assert(Entries && "Call layout() before get()");
 105     typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
 106     assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
 107            "get() called with sequence that wasn't added first");
 108     return I->second + (I->first.size() - Seq.size());
 109   }
 110
 111   /// emit - Print out the table as the body of an array initializer.
 112   /// Use the Print function to print elements.
 113   void emit(raw_ostream &OS,
 114             void (*Print)(raw_ostream&, ElemT),
 115             const char *Term = "0") const {
 116     assert(Entries && "Call layout() before emit()");
 117     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
 118          I != E; ++I) {
 119       OS << "  /* " << I->second << " */ ";
 120       for (typename SeqT::const_iterator SI = I->first.begin(),
 121              SE = I->first.end(); SI != SE; ++SI) {
 122         Print(OS, *SI);
 123         OS << ", ";
 124       }
 125       OS << Term << ",\n";
 126     }
 127   }
 128 };
 129
 130 // Helper function for SequenceToOffsetTable<string>.
 131 static inline void printChar(raw_ostream &OS, char C) {
 132   unsigned char UC(C);
 133   if (isalnum(UC) || ispunct(UC)) {
 134     OS << '\'';
 135     if (C == '\\' || C == '\'')
 136       OS << '\\';
 137     OS << C << '\'';
 138   } else {
 139     OS << unsigned(UC);
 140   }
 141 }
 142
 143 } // end namespace llvm
 144
 145 #endif