SequenceToOffsetTable.h [plain text]
#ifndef TBLGEN_SEQUENCE_TO_OFFSET_TABLE_H
#define TBLGEN_SEQUENCE_TO_OFFSET_TABLE_H
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cctype>
#include <functional>
#include <map>
#include <vector>
namespace llvm {
template<typename SeqT, typename Less = std::less<typename SeqT::value_type> >
class SequenceToOffsetTable {
typedef typename SeqT::value_type ElemT;
struct SeqLess : public std::binary_function<SeqT, SeqT, bool> {
Less L;
bool operator()(const SeqT &A, const SeqT &B) const {
return std::lexicographical_compare(A.rbegin(), A.rend(),
B.rbegin(), B.rend(), L);
}
};
typedef std::map<SeqT, unsigned, SeqLess> SeqMap;
SeqMap Seqs;
unsigned Entries;
static bool isSuffix(const SeqT &A, const SeqT &B) {
return A.size() <= B.size() && std::equal(A.rbegin(), A.rend(), B.rbegin());
}
public:
SequenceToOffsetTable() : Entries(0) {}
void add(const SeqT &Seq) {
assert(Entries == 0 && "Cannot call add() after layout()");
typename SeqMap::iterator I = Seqs.lower_bound(Seq);
if (I != Seqs.end() && isSuffix(Seq, I->first))
return;
I = Seqs.insert(I, std::make_pair(Seq, 0u));
if (I != Seqs.begin() && isSuffix((--I)->first, Seq))
Seqs.erase(I);
}
bool empty() const { return Seqs.empty(); }
void layout() {
assert(Entries == 0 && "Can only call layout() once");
for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
++I) {
I->second = Entries;
Entries += I->first.size() + 1;
}
}
unsigned get(const SeqT &Seq) const {
assert(Entries && "Call layout() before get()");
typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
"get() called with sequence that wasn't added first");
return I->second + (I->first.size() - Seq.size());
}
void emit(raw_ostream &OS,
void (*Print)(raw_ostream&, ElemT),
const char *Term = "0") const {
assert(Entries && "Call layout() before emit()");
for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
I != E; ++I) {
OS << " /* " << I->second << " */ ";
for (typename SeqT::const_iterator SI = I->first.begin(),
SE = I->first.end(); SI != SE; ++SI) {
Print(OS, *SI);
OS << ", ";
}
OS << Term << ",\n";
}
}
};
static inline void printChar(raw_ostream &OS, char C) {
unsigned char UC(C);
if (isalnum(UC) || ispunct(UC)) {
OS << '\'';
if (C == '\\' || C == '\'')
OS << '\\';
OS << C << '\'';
} else {
OS << unsigned(UC);
}
}
}
#endif