llvm/llvm/utils/TableGen/Basic/SequenceToOffsetTable.h

//===-- SequenceToOffsetTable.h - Compress similar sequences ----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// SequenceToOffsetTable can be used to emit a number of null-terminated
// sequences as one big array.  Use the same memory when a sequence is a suffix
// of another.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_UTILS_TABLEGEN_BASIC_SEQUENCETOOFFSETTABLE_H
#define LLVM_UTILS_TABLEGEN_BASIC_SEQUENCETOOFFSETTABLE_H

#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>

namespace llvm {
extern cl::opt<bool> EmitLongStrLiterals;

inline void printChar(raw_ostream &OS, char C) { … }

/// SequenceToOffsetTable - Collect a number of terminated sequences of T.
/// Compute the layout of a table that contains all the sequences, possibly by
/// reusing entries.
///
/// @tparam SeqT The sequence container. (vector or string).
/// @tparam Less A stable comparator for SeqT elements.
template <typename SeqT, typename Less = std::less<typename SeqT::value_type>>
class SequenceToOffsetTable {
  typedef typename SeqT::value_type ElemT;

  // Define a comparator for SeqT that sorts a suffix immediately before a
  // sequence with that suffix.
  struct SeqLess {
    Less L;
    bool operator()(const SeqT &A, const SeqT &B) const {
      return std::lexicographical_compare(A.rbegin(), A.rend(), B.rbegin(),
                                          B.rend(), L);
    }
  };

  // Keep sequences ordered according to SeqLess so suffixes are easy to find.
  // Map each sequence to its offset in the table.
  typedef std::map<SeqT, unsigned, SeqLess> SeqMap;

  // Sequences added so far, with suffixes removed.
  SeqMap Seqs;

  // Entries in the final table, or 0 before layout was called.
  unsigned Entries;

  // isSuffix - Returns true if A is a suffix of B.
  static bool isSuffix(const SeqT &A, const SeqT &B) { … }

public:
  SequenceToOffsetTable() : … { … }

  /// add - Add a sequence to the table.
  /// This must be called before layout().
  void add(const SeqT &Seq) { … }

  bool empty() const { … }

  unsigned size() const { … }

  /// layout - Computes the final table layout.
  void layout() { … }

  /// get - Returns the offset of Seq in the final table.
  unsigned get(const SeqT &Seq) const { … }

  /// `emitStringLiteralDef` - Print out the table as the body of an array
  /// initializer, where each element is a C string literal terminated by
  /// `\0`. Falls back to emitting a comma-separated integer list if
  /// `EmitLongStrLiterals` is false
  void emitStringLiteralDef(raw_ostream &OS, const Twine &Decl) const { … }

  /// emit - Print out the table as the body of an array initializer.
  /// Use the Print function to print elements.
  void emit(raw_ostream &OS, void (*Print)(raw_ostream &, ElemT),
            const char *Term = "0") const { … }
};

} // end namespace llvm

#endif // LLVM_UTILS_TABLEGEN_BASIC_SEQUENCETOOFFSETTABLE_H