darts.h | Explore in Territory

#ifndef DARTS_H_
#define DARTS_H_

#include <cstdio>
#include <exception>
#include <new>

#if DARTS_DISABLE_EXCEPTIONS
#include "absl/log/absl_check.h"
#endif

#define DARTS_VERSION …

// DARTS_THROW() throws a <Darts::Exception> whose message starts with the
// file name and the line number. For example, DARTS_THROW("error message") at
// line 123 of "darts.h" throws a <Darts::Exception> which has a pointer to
// "darts.h:123: exception: error message". The message is available by using
// what() as well as that of <std::exception>.
#define DARTS_INT_TO_STR …
#define DARTS_LINE_TO_STR …
#define DARTS_LINE_STR …

#if DARTS_DISABLE_EXCEPTIONS
#define DARTS_THROW …
#else
#define DARTS_THROW …
#endif

namespace Darts {

// The following namespace hides the internal types and classes.
namespace Details {

// This header assumes that <int> and <unsigned int> are 32-bit integer types.
//
// Darts-clone keeps values associated with keys. The type of the values is
// <value_type>. Note that the values must be positive integers because the
// most significant bit (MSB) of each value is used to represent whether the
// corresponding unit is a leaf or not. Also, the keys are represented by
// sequences of <char_type>s. <uchar_type> is the unsigned type of <char_type>.
char_type;
uchar_type;
value_type;

// The main structure of Darts-clone is an array of <DoubleArrayUnit>s, and the
// unit type is actually a wrapper of <id_type>.
id_type;

// <progress_func_type> is the type of callback functions for reporting the
// progress of building a dictionary. See also build() of <DoubleArray>.
// The 1st argument receives the progress value and the 2nd argument receives
// the maximum progress value. A usage example is to show the progress
// percentage, 100.0 * (the 1st argument) / (the 2nd argument).
progress_func_type;

// <DoubleArrayUnit> is the type of double-array units and it is a wrapper of
// <id_type> in practice.
class DoubleArrayUnit { … };

#if !DARTS_DISABLE_EXCEPTIONS
// Darts-clone throws an <Exception> for memory allocation failure, invalid
// arguments or a too large offset. The last case means that there are too many
// keys in the given set of keys. Note that the `msg' of <Exception> must be a
// constant or static string because an <Exception> keeps only a pointer to
// that string.
class Exception : public std::exception {
 public:
  explicit Exception(const char* msg = NULL) throw() : msg_(msg) {}
  Exception(const Exception& rhs) throw() : msg_(rhs.msg_) {}
  virtual ~Exception() throw() {}

  // <Exception> overrides what() of <std::exception>.
  virtual const char* what() const throw() {
    return (msg_ != NULL) ? msg_ : "";
  }

 private:
  const char* msg_;

  // Disallows operator=.
  Exception& operator=(const Exception&);
};
#endif  // !DARTS_DISABLE_EXCEPTIONS

}  // namespace Details

// <DoubleArrayImpl> is the interface of Darts-clone. Note that other
// classes should not be accessed from outside.
//
// <DoubleArrayImpl> has 4 template arguments but only the 3rd one is used as
// the type of values. Note that the given <T> is used only from outside, and
// the internal value type is not changed from <Darts::Details::value_type>.
// In build(), given values are casted from <T> to <Darts::Details::value_type>
// by using static_cast. On the other hand, values are casted from
// <Darts::Details::value_type> to <T> in searching dictionaries.
template <typename, typename, typename T, typename>
class DoubleArrayImpl { … };

// <DoubleArray> is the typical instance of <DoubleArrayImpl>. It uses <int>
// as the type of values and it is suitable for most cases.
DoubleArray;

// The interface section ends here. For using Darts-clone, there is no need
// to read the remaining section, which gives the implementation of
// Darts-clone.

//
// Member functions of DoubleArrayImpl (except build()).
//

template <typename A, typename B, typename T, typename C>
int DoubleArrayImpl<A, B, T, C>::open(const char* file_name,
                                      const char* mode,
                                      std::size_t offset,
                                      std::size_t size) { … }

template <typename A, typename B, typename T, typename C>
int DoubleArrayImpl<A, B, T, C>::save(const char* file_name,
                                      const char* mode,
                                      std::size_t) const { … }

template <typename A, typename B, typename T, typename C>
template <typename U>
inline U DoubleArrayImpl<A, B, T, C>::exactMatchSearch(
    const key_type* key,
    std::size_t length,
    std::size_t node_pos) const { … }

template <typename A, typename B, typename T, typename C>
template <typename U>
inline std::size_t DoubleArrayImpl<A, B, T, C>::commonPrefixSearch(
    const key_type* key,
    U* results,
    std::size_t max_num_results,
    std::size_t length,
    std::size_t node_pos) const { … }

template <typename A, typename B, typename T, typename C>
inline typename DoubleArrayImpl<A, B, T, C>::value_type
DoubleArrayImpl<A, B, T, C>::traverse(const key_type* key,
                                      std::size_t& node_pos,
                                      std::size_t& key_pos,
                                      std::size_t length) const { … }

namespace Details {

//
// Memory management of array.
//

template <typename T>
class AutoArray { … };

//
// Memory management of resizable array.
//

template <typename T>
class AutoPool { … };

template <typename T>
void AutoPool<T>::resize_buf(std::size_t size) { … }

//
// Memory management of stack.
//

template <typename T>
class AutoStack { … };

//
// Succinct bit vector.
//

class BitVector { … };

inline void BitVector::build() { … }

//
// Keyset.
//

template <typename T>
class Keyset { … };

//
// Node of Directed Acyclic Word Graph (DAWG).
//

class DawgNode { … };

//
// Fixed unit of Directed Acyclic Word Graph (DAWG).
//

class DawgUnit { … };

//
// Directed Acyclic Word Graph (DAWG) builder.
//

class DawgBuilder { … };

inline void DawgBuilder::init() { … }

inline void DawgBuilder::finish() { … }

inline void DawgBuilder::insert(const char* key,
                                std::size_t length,
                                value_type value) { … }

inline void DawgBuilder::clear() { … }

inline void DawgBuilder::flush(id_type id) { … }

inline void DawgBuilder::expand_table() { … }

inline id_type DawgBuilder::find_unit(id_type id, id_type* hash_id) const { … }

inline id_type DawgBuilder::find_node(id_type node_id, id_type* hash_id) const { … }

inline bool DawgBuilder::are_equal(id_type node_id, id_type unit_id) const { … }

inline id_type DawgBuilder::hash_unit(id_type id) const { … }

inline id_type DawgBuilder::hash_node(id_type id) const { … }

inline id_type DawgBuilder::append_unit() { … }

inline id_type DawgBuilder::append_node() { … }

//
// Unit of double-array builder.
//

class DoubleArrayBuilderUnit { … };

//
// Extra unit of double-array builder.
//

class DoubleArrayBuilderExtraUnit { … };

//
// DAWG -> double-array converter.
//

class DoubleArrayBuilder { … };

template <typename T>
void DoubleArrayBuilder::build(const Keyset<T>& keyset) { … }

inline void DoubleArrayBuilder::copy(std::size_t* size_ptr,
                                     DoubleArrayUnit** buf_ptr) const { … }

inline void DoubleArrayBuilder::clear() { … }

template <typename T>
void DoubleArrayBuilder::build_dawg(const Keyset<T>& keyset,
                                    DawgBuilder* dawg_builder) { … }

inline void DoubleArrayBuilder::build_from_dawg(const DawgBuilder& dawg) { … }

inline void DoubleArrayBuilder::build_from_dawg(const DawgBuilder& dawg,
                                                id_type dawg_id,
                                                id_type dic_id) { … }

inline id_type DoubleArrayBuilder::arrange_from_dawg(const DawgBuilder& dawg,
                                                     id_type dawg_id,
                                                     id_type dic_id) { … }

template <typename T>
void DoubleArrayBuilder::build_from_keyset(const Keyset<T>& keyset) { … }

template <typename T>
void DoubleArrayBuilder::build_from_keyset(const Keyset<T>& keyset,
                                           std::size_t begin,
                                           std::size_t end,
                                           std::size_t depth,
                                           id_type dic_id) { … }

template <typename T>
id_type DoubleArrayBuilder::arrange_from_keyset(const Keyset<T>& keyset,
                                                std::size_t begin,
                                                std::size_t end,
                                                std::size_t depth,
                                                id_type dic_id) { … }

inline id_type DoubleArrayBuilder::find_valid_offset(id_type id) const { … }

inline bool DoubleArrayBuilder::is_valid_offset(id_type id,
                                                id_type offset) const { … }

inline void DoubleArrayBuilder::reserve_id(id_type id) { … }

inline void DoubleArrayBuilder::expand_units() { … }

inline void DoubleArrayBuilder::fix_all_blocks() { … }

inline void DoubleArrayBuilder::fix_block(id_type block_id) { … }

}  // namespace Details

//
// Member function build() of DoubleArrayImpl.
//

template <typename A, typename B, typename T, typename C>
int DoubleArrayImpl<A, B, T, C>::build(
    std::size_t num_keys,
    const key_type* const* keys,
    const std::size_t* lengths,
    const value_type* values,
    Details::progress_func_type progress_func) { … }

}  // namespace Darts

#undef DARTS_INT_TO_STR
#undef DARTS_LINE_TO_STR
#undef DARTS_LINE_STR
#undef DARTS_THROW

#endif  // DARTS_H_
chromium/third_party/sentencepiece/src/third_party/darts_clone/darts.h
