1184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen//===-- SequenceToOffsetTable.h - Compress similar sequences ----*- C++ -*-===// 2184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// 3184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// 5184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// 8184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// 10184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// SequenceToOffsetTable can be used to emit a number of null-terminated 11184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// sequences as one big array. Use the same memory when a sequence is a suffix 12184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// of another. 13184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen// 14184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 15184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 1637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#ifndef LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H 1737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#define LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H 18184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 19184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 20184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen#include <algorithm> 21184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen#include <cassert> 22c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen#include <cctype> 234ffd89fa4d2788611187d1a534d2ed46adf1702cChandler Carruth#include <functional> 24862b50420122e8be173ae534fcd1668c8c4be916Craig Topper#include <map> 254ffd89fa4d2788611187d1a534d2ed46adf1702cChandler Carruth#include <vector> 26184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 27184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesennamespace llvm { 28184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 29184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen/// SequenceToOffsetTable - Collect a number of terminated sequences of T. 30184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen/// Compute the layout of a table that contains all the sequences, possibly by 31184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen/// reusing entries. 32184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen/// 33a00b80b04c5edb08639c1c6b32e9231fd8b066f7Dmitri Gribenko/// @tparam SeqT The sequence container. (vector or string). 34a00b80b04c5edb08639c1c6b32e9231fd8b066f7Dmitri Gribenko/// @tparam Less A stable comparator for SeqT elements. 35184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesentemplate<typename SeqT, typename Less = std::less<typename SeqT::value_type> > 36184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesenclass SequenceToOffsetTable { 37184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen typedef typename SeqT::value_type ElemT; 38184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 39184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Define a comparator for SeqT that sorts a suffix immediately before a 40184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // sequence with that suffix. 41184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen struct SeqLess : public std::binary_function<SeqT, SeqT, bool> { 42184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen Less L; 43184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen bool operator()(const SeqT &A, const SeqT &B) const { 44184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen return std::lexicographical_compare(A.rbegin(), A.rend(), 45184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen B.rbegin(), B.rend(), L); 46184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 47184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen }; 48184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 49184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Keep sequences ordered according to SeqLess so suffixes are easy to find. 50184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Map each sequence to its offset in the table. 51184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen typedef std::map<SeqT, unsigned, SeqLess> SeqMap; 52184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 53184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Sequences added so far, with suffixes removed. 54184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen SeqMap Seqs; 55184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 56184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Entries in the final table, or 0 before layout was called. 57184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen unsigned Entries; 58184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 59184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // isSuffix - Returns true if A is a suffix of B. 60184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen static bool isSuffix(const SeqT &A, const SeqT &B) { 61184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen return A.size() <= B.size() && std::equal(A.rbegin(), A.rend(), B.rbegin()); 62184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 63184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 64184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesenpublic: 65184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen SequenceToOffsetTable() : Entries(0) {} 66184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 67184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen /// add - Add a sequence to the table. 68184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen /// This must be called before layout(). 69184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen void add(const SeqT &Seq) { 70184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen assert(Entries == 0 && "Cannot call add() after layout()"); 71184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen typename SeqMap::iterator I = Seqs.lower_bound(Seq); 72184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 73184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // If SeqMap contains a sequence that has Seq as a suffix, I will be 74184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // pointing to it. 75184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen if (I != Seqs.end() && isSuffix(Seq, I->first)) 76184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen return; 77184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 78184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen I = Seqs.insert(I, std::make_pair(Seq, 0u)); 79184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 80184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // The entry before I may be a suffix of Seq that can now be erased. 81184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen if (I != Seqs.begin() && isSuffix((--I)->first, Seq)) 82184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen Seqs.erase(I); 83184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 84184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 85387c9dcddabe8551468647b249d3629953caab9eChris Lattner bool empty() const { return Seqs.empty(); } 864e5babe4f3aa5aaabf8ee91b10f64c9e35f2505cCraig Topper 87ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned size() const { 88ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(Entries && "Call layout() before size()"); 89ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Entries; 90ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 91ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 92184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen /// layout - Computes the final table layout. 935974c31acbf5368ffc18b23c849d0c823f91f25eCraig Topper void layout() { 94184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen assert(Entries == 0 && "Can only call layout() once"); 95184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Lay out the table in Seqs iteration order. 96184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E; 97184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen ++I) { 98184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen I->second = Entries; 99184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen // Include space for a terminator. 100184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen Entries += I->first.size() + 1; 101184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 102184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 103184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 104184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen /// get - Returns the offset of Seq in the final table. 105184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen unsigned get(const SeqT &Seq) const { 106184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen assert(Entries && "Call layout() before get()"); 107184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen typename SeqMap::const_iterator I = Seqs.lower_bound(Seq); 108184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen assert(I != Seqs.end() && isSuffix(Seq, I->first) && 109184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen "get() called with sequence that wasn't added first"); 110184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen return I->second + (I->first.size() - Seq.size()); 111184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 112184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 113184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen /// emit - Print out the table as the body of an array initializer. 114184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen /// Use the Print function to print elements. 1150d4e2ea00eac5d51a74a54dd504a8f34580041d7Jakob Stoklund Olesen void emit(raw_ostream &OS, 1160d4e2ea00eac5d51a74a54dd504a8f34580041d7Jakob Stoklund Olesen void (*Print)(raw_ostream&, ElemT), 1170d4e2ea00eac5d51a74a54dd504a8f34580041d7Jakob Stoklund Olesen const char *Term = "0") const { 118184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen assert(Entries && "Call layout() before emit()"); 119184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end(); 120184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen I != E; ++I) { 121184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen OS << " /* " << I->second << " */ "; 122184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen for (typename SeqT::const_iterator SI = I->first.begin(), 123184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen SE = I->first.end(); SI != SE; ++SI) { 124184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen Print(OS, *SI); 125184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen OS << ", "; 126184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 1270d4e2ea00eac5d51a74a54dd504a8f34580041d7Jakob Stoklund Olesen OS << Term << ",\n"; 128184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 129184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen } 130184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen}; 131184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 132c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen// Helper function for SequenceToOffsetTable<string>. 133c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesenstatic inline void printChar(raw_ostream &OS, char C) { 134c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen unsigned char UC(C); 135c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen if (isalnum(UC) || ispunct(UC)) { 136c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen OS << '\''; 137c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen if (C == '\\' || C == '\'') 138c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen OS << '\\'; 139c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen OS << C << '\''; 140c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen } else { 141c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen OS << unsigned(UC); 142c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen } 143c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen} 144c19f72bd83e8cb2cc31257008ee9d7797dbf3dbbJakob Stoklund Olesen 145184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen} // end namespace llvm 146184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen 147184440e8085379f8c3749f04dcffee8d9f16f435Jakob Stoklund Olesen#endif 148