20 #ifndef FST_ARC_ARENA_H_ 21 #define FST_ARC_ARENA_H_ 33 #include <unordered_map> 60 template <
typename Arc>
63 explicit ArcArena(
size_t block_size = 256,
size_t max_retained_size = 1e6)
64 : block_size_(block_size), max_retained_size_(max_retained_size) {
65 blocks_.emplace_back(MakeSharedBlock(block_size_));
66 first_block_size_ = block_size_;
67 total_size_ = block_size_;
68 arcs_ = blocks_.back().get();
69 end_ = arcs_ + block_size_;
77 block_size_(copy.block_size_),
78 first_block_size_(copy.first_block_size_),
79 total_size_(copy.total_size_),
80 max_retained_size_(copy.max_retained_size_),
81 blocks_(copy.blocks_) {
82 NewBlock(block_size_);
86 if (next_ + n < end_)
return;
92 size_t length = next_ - arcs_;
100 const auto *arcs = arcs_;
107 size_t Size() {
return total_size_; }
111 if (total_size_ > first_block_size_) {
112 first_block_size_ = std::min(max_retained_size_, total_size_);
113 blocks_.back() = MakeSharedBlock(first_block_size_);
115 total_size_ = first_block_size_;
116 arcs_ = blocks_.back().get();
117 end_ = arcs_ + first_block_size_;
124 void NewBlock(
size_t n) {
125 const auto length = next_ - arcs_;
126 const auto new_block_size = std::max(n, block_size_);
127 total_size_ += new_block_size;
128 blocks_.emplace_back(MakeSharedBlock(new_block_size));
129 std::copy(arcs_, next_, blocks_.back().get());
130 arcs_ = blocks_.back().get();
131 next_ = arcs_ + length;
132 end_ = arcs_ + new_block_size;
135 std::shared_ptr<Arc[]> MakeSharedBlock(
size_t size) {
136 return std::shared_ptr<Arc[]>(
new Arc[size]);
143 size_t first_block_size_;
145 size_t max_retained_size_;
146 std::list<std::shared_ptr<Arc[]>> blocks_;
178 State(
Weight final_weight, int32_t niepsilons, int32_t noepsilons,
179 int32_t narcs,
const Arc *arcs)
180 : final_weight_(std::move(final_weight)),
181 niepsilons_(niepsilons),
182 noepsilons_(noepsilons),
195 template <
class Expander>
197 const auto &[it, success] = cache_.emplace(state_id,
nullptr);
198 if (!success)
return it->second;
200 StateBuilder builder(&arena_);
201 expander.Expand(state_id, &builder);
202 const auto arcs = arena_.GetArcs();
203 size_t narcs = builder.narcs_;
204 size_t niepsilons = 0;
205 size_t noepsilons = 0;
206 for (
size_t i = 0; i < narcs; ++i) {
207 if (arcs[i].ilabel == 0) ++niepsilons;
208 if (arcs[i].olabel == 0) ++noepsilons;
210 states_.emplace_back(
211 State(builder.final_weight_, niepsilons, noepsilons, narcs, arcs));
213 auto state = &states_.back();
219 auto it = cache_.find(state_id);
220 return (it == cache_.end()) ?
nullptr : it->second;
227 : arena_(arena), final_weight_(Weight::Zero()), narcs_(0) {}
229 void SetFinal(Weight weight) { final_weight_ = std::move(weight); }
231 void ReserveArcs(
size_t n) { arena_->ReserveArcs(n); }
233 void AddArc(
const Arc &arc) {
235 arena_->PushArc(arc);
242 Weight final_weight_;
246 std::unordered_map<StateId, State *> cache_;
247 std::deque<State> states_;
253 #endif // FST_ARC_ARENA_H_
typename Arc::StateId StateId
void PushArc(const Arc &arc)
typename Arc::Weight Weight
size_t NumOutputEpsilons() const
const Arc & GetArc(size_t n) const
int * MutableRefCount() const
State * Find(StateId state_id) const
ArcArena(size_t block_size=256, size_t max_retained_size=1e6)
State * FindOrExpand(Expander &expander, StateId state_id)
void ReserveArcs(size_t n)
ArcArena(const ArcArena ©)
size_t NumInputEpsilons() const