FST  openfst-1.8.3
OpenFst Library
cache.h
Go to the documentation of this file.
1 // Copyright 2005-2024 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // An FST implementation that caches FST elements of a delayed computation.
19 
20 #ifndef FST_CACHE_H_
21 #define FST_CACHE_H_
22 
23 #include <algorithm>
24 #include <cstddef>
25 #include <cstdint>
26 #include <functional>
27 #include <list>
28 #include <memory>
29 #include <new>
30 #include <utility>
31 #include <vector>
32 
33 #include <fst/flags.h>
34 #include <fst/log.h>
35 #include <fst/fst.h>
36 #include <fst/memory.h>
37 #include <fst/mutable-fst.h>
38 #include <fst/properties.h>
39 #include <fst/util.h>
40 #include <fst/vector-fst.h>
41 #include <unordered_map>
42 #include <functional>
43 
44 DECLARE_bool(fst_default_cache_gc);
45 DECLARE_int64(fst_default_cache_gc_limit);
46 
47 namespace fst {
48 
49 // Options for controlling caching behavior; higher level than CacheImplOptions.
50 struct CacheOptions {
51  bool gc; // Enables GC.
52  size_t gc_limit; // Number of bytes allowed before GC.
53 
54  explicit CacheOptions(
55  bool gc = FST_FLAGS_fst_default_cache_gc,
56  size_t gc_limit = FST_FLAGS_fst_default_cache_gc_limit)
57  : gc(gc), gc_limit(gc_limit) {}
58 };
59 
60 // Options for controlling caching behavior, at a lower level than
61 // CacheOptions; templated on the cache store and allows passing the store.
62 template <class CacheStore>
64  bool gc; // Enables GC.
65  size_t gc_limit; // Number of bytes allowed before GC.
66  CacheStore *store; // Cache store.
67  bool own_store; // Should CacheImpl takes ownership of the store?
68 
69  explicit CacheImplOptions(
70  bool gc = FST_FLAGS_fst_default_cache_gc,
71  size_t gc_limit = FST_FLAGS_fst_default_cache_gc_limit,
72  CacheStore *store = nullptr)
73  : gc(gc), gc_limit(gc_limit), store(store), own_store(true) {}
74 
75  explicit CacheImplOptions(const CacheOptions &opts)
76  : gc(opts.gc), gc_limit(opts.gc_limit), store(nullptr), own_store(true) {}
77 };
78 
79 // Cache flags.
80 inline constexpr uint8_t kCacheFinal = 0x01; // Final weight has been cached.
81 inline constexpr uint8_t kCacheArcs = 0x02; // Arcs have been cached.
82 inline constexpr uint8_t kCacheInit = 0x04; // Initialized by GC.
83 inline constexpr uint8_t kCacheRecent = 0x08; // Visited since GC.
84 inline constexpr uint8_t kCacheFlags =
85  kCacheFinal | kCacheArcs | kCacheInit | kCacheRecent;
86 
87 // Cache state, with arcs stored in a per-state std::vector.
88 template <class A, class M = PoolAllocator<A>>
89 class CacheState {
90  public:
91  using Arc = A;
92  using Label = typename Arc::Label;
93  using StateId = typename Arc::StateId;
94  using Weight = typename Arc::Weight;
95 
96  using ArcAllocator = M;
97  using StateAllocator = typename std::allocator_traits<
98  ArcAllocator>::template rebind_alloc<CacheState<A, M>>;
99 
100  // Provides STL allocator for arcs.
101  explicit CacheState(const ArcAllocator &alloc)
102  : final_weight_(Weight::Zero()),
103  niepsilons_(0),
104  noepsilons_(0),
105  arcs_(alloc),
106  flags_(0),
107  ref_count_(0) {}
108 
109  CacheState(const CacheState<A> &state, const ArcAllocator &alloc)
110  : final_weight_(state.Final()),
111  niepsilons_(state.NumInputEpsilons()),
112  noepsilons_(state.NumOutputEpsilons()),
113  arcs_(state.arcs_.begin(), state.arcs_.end(), alloc),
114  flags_(state.Flags()),
115  ref_count_(0) {}
116 
117  void Reset() {
118  final_weight_ = Weight::Zero();
119  niepsilons_ = 0;
120  noepsilons_ = 0;
121  ref_count_ = 0;
122  flags_ = 0;
123  arcs_.clear();
124  }
125 
126  Weight Final() const { return final_weight_; }
127 
128  size_t NumInputEpsilons() const { return niepsilons_; }
129 
130  size_t NumOutputEpsilons() const { return noepsilons_; }
131 
132  size_t NumArcs() const { return arcs_.size(); }
133 
134  const Arc &GetArc(size_t n) const { return arcs_[n]; }
135 
136  // Used by the ArcIterator<Fst<Arc>> efficient implementation.
137  const Arc *Arcs() const { return !arcs_.empty() ? &arcs_[0] : nullptr; }
138 
139  // Accesses flags; used by the caller.
140  uint8_t Flags() const { return flags_; }
141 
142  // Accesses ref count; used by the caller.
143  int RefCount() const { return ref_count_; }
144 
145  void SetFinal(Weight weight = Weight::One()) {
146  final_weight_ = std::move(weight);
147  }
148 
149  void ReserveArcs(size_t n) { arcs_.reserve(n); }
150 
151  // Adds one arc at a time with all needed book-keeping; use PushArc and
152  // SetArcs for a more efficient alternative.
153  void AddArc(const Arc &arc) {
154  IncrementNumEpsilons(arc);
155  arcs_.push_back(arc);
156  }
157 
158  void AddArc(Arc &&arc) {
159  IncrementNumEpsilons(arc);
160  arcs_.push_back(std::move(arc));
161  }
162 
163  // Adds one arc at a time with delayed book-keeping; finalize with SetArcs().
164  void PushArc(const Arc &arc) { arcs_.push_back(arc); }
165 
166  void PushArc(Arc &&arc) { arcs_.push_back(std::move(arc)); }
167 
168  // Adds one arc at a time with delayed book-keeping; finalize with SetArcs().
169  template <class... T>
170  void EmplaceArc(T &&...ctor_args) {
171  arcs_.emplace_back(std::forward<T>(ctor_args)...);
172  }
173 
174  // Finalizes arcs book-keeping; call only once.
175  void SetArcs() {
176  for (const auto &arc : arcs_) {
177  IncrementNumEpsilons(arc);
178  }
179  }
180 
181  // Modifies nth arc.
182  void SetArc(const Arc &arc, size_t n) {
183  if (arcs_[n].ilabel == 0) --niepsilons_;
184  if (arcs_[n].olabel == 0) --noepsilons_;
185  IncrementNumEpsilons(arc);
186  arcs_[n] = arc;
187  }
188 
189  // Deletes all arcs.
190  void DeleteArcs() {
191  niepsilons_ = 0;
192  noepsilons_ = 0;
193  arcs_.clear();
194  }
195 
196  void DeleteArcs(size_t n) {
197  for (size_t i = 0; i < n; ++i) {
198  if (arcs_.back().ilabel == 0) --niepsilons_;
199  if (arcs_.back().olabel == 0) --noepsilons_;
200  arcs_.pop_back();
201  }
202  }
203 
204  // Sets status flags; used by the caller.
205  void SetFlags(uint8_t flags, uint8_t mask) const {
206  flags_ &= ~mask;
207  flags_ |= flags;
208  }
209 
210  // Mutates reference counts; used by the caller.
211 
212  int IncrRefCount() const { return ++ref_count_; }
213 
214  int DecrRefCount() const { return --ref_count_; }
215 
216  // Used by the ArcIterator<Fst<Arc>> efficient implementation.
217  int *MutableRefCount() const { return &ref_count_; }
218 
219  // Used for state class allocation.
220  void *operator new(size_t size, StateAllocator *alloc) {
221  return alloc->allocate(1);
222  }
223 
224  // For state destruction and memory freeing.
225  static void Destroy(CacheState<Arc> *state, StateAllocator *alloc) {
226  if (state) {
227  state->~CacheState<Arc>();
228  alloc->deallocate(state, 1);
229  }
230  }
231 
232  private:
233  // Update the number of epsilons as a result of having added an arc.
234  void IncrementNumEpsilons(const Arc &arc) {
235  if (arc.ilabel == 0) ++niepsilons_;
236  if (arc.olabel == 0) ++noepsilons_;
237  }
238 
239  Weight final_weight_; // Final weight.
240  size_t niepsilons_; // # of input epsilons.
241  size_t noepsilons_; // # of output epsilons.
242  std::vector<Arc, ArcAllocator> arcs_; // Arcs representation.
243  mutable uint8_t flags_;
244  mutable int ref_count_; // If 0, available for GC.
245 };
246 
247 // Cache store, allocating and storing states, providing a mapping from state
248 // IDs to cached states, and an iterator over these states. The state template
249 // argument must implement the CacheState interface. The state for a StateId s
250 // is constructed when requested by GetMutableState(s) if it is not yet stored.
251 // Initially, a state has a reference count of zero, but the user may increment
252 // or decrement this to control the time of destruction. In particular, a state
253 // is destroyed when:
254 //
255 // 1. This instance is destroyed, or
256 // 2. Clear() or Delete() is called, or
257 // 3. Possibly (implementation-dependently) when:
258 // - Garbage collection is enabled (as defined by opts.gc),
259 // - The cache store size exceeds the limits (as defined by opts.gc_limits),
260 // - The state's reference count is zero, and
261 // - The state is not the most recently requested state.
262 //
263 // template <class S>
264 // class CacheStore {
265 // public:
266 // using State = S;
267 // using Arc = typename State::Arc;
268 // using StateId = typename Arc::StateId;
269 //
270 // // Required constructors/assignment operators.
271 // explicit CacheStore(const CacheOptions &opts);
272 //
273 // // Returns nullptr if state is not stored.
274 // const State *GetState(StateId s);
275 //
276 // // Creates state if state is not stored.
277 // State *GetMutableState(StateId s);
278 //
279 // // Similar to State::AddArc() but updates cache store book-keeping.
280 // void AddArc(State *state, const Arc &arc);
281 //
282 // // Similar to State::SetArcs() but updates cache store book-keeping; call
283 // // only once.
284 // void SetArcs(State *state);
285 //
286 // // Similar to State::DeleteArcs() but updates cache store book-keeping.
287 //
288 // void DeleteArcs(State *state);
289 //
290 // void DeleteArcs(State *state, size_t n);
291 //
292 // // Deletes all cached states.
293 // void Clear();
294 //
295 // // Number of cached states.
296 // StateId CountStates();
297 //
298 // // Iterates over cached states (in an arbitrary order); only needed if
299 // // opts.gc is true.
300 // bool Done() const; // End of iteration.
301 // StateId Value() const; // Current state.
302 // void Next(); // Advances to next state (when !Done).
303 // void Reset(); // Returns to initial condition.
304 // void Delete(); // Deletes current state and advances to next.
305 // };
306 
307 // Container cache stores.
308 
309 // This class uses a vector of pointers to states to store cached states.
310 template <class S>
312  public:
313  using State = S;
314  using Arc = typename State::Arc;
315  using StateId = typename Arc::StateId;
316  using StateList = std::list<StateId, PoolAllocator<StateId>>;
317 
318  // Required constructors/assignment operators.
319  explicit VectorCacheStore(const CacheOptions &opts) : cache_gc_(opts.gc) {
320  Clear();
321  Reset();
322  }
323 
325  : cache_gc_(store.cache_gc_) {
326  CopyStates(store);
327  Reset();
328  }
329 
330  ~VectorCacheStore() { Clear(); }
331 
333  if (this != &store) {
334  CopyStates(store);
335  Reset();
336  }
337  return *this;
338  }
339 
340  bool InBounds(StateId s) const {
341  return s < static_cast<StateId>(state_vec_.size());
342  }
343 
344  // Returns nullptr if state is not stored.
345  const State *GetState(StateId s) const {
346  return InBounds(s) ? state_vec_[s] : nullptr;
347  }
348 
349  // Creates state if state is not stored.
351  State *state = nullptr;
352  if (InBounds(s)) {
353  state = state_vec_[s];
354  } else {
355  state_vec_.resize(s + 1, nullptr);
356  }
357  if (!state) {
358  state = new (&state_alloc_) State(arc_alloc_);
359  state_vec_[s] = state;
360  if (cache_gc_) state_list_.push_back(s);
361  }
362  return state;
363  }
364 
365  // Similar to State::AddArc() but updates cache store book-keeping
366  void AddArc(State *state, const Arc &arc) { state->AddArc(arc); }
367 
368  // Similar to State::SetArcs() but updates cache store book-keeping; call
369  // only once.
370  void SetArcs(State *state) { state->SetArcs(); }
371 
372  // Deletes all arcs.
373  void DeleteArcs(State *state) { state->DeleteArcs(); }
374 
375  // Deletes some arcs.
376  void DeleteArcs(State *state, size_t n) { state->DeleteArcs(n); }
377 
378  // Deletes all cached states.
379  void Clear() {
380  for (State *s : state_vec_) {
381  State::Destroy(s, &state_alloc_);
382  }
383  state_vec_.clear();
384  state_list_.clear();
385  }
386 
388  return std::count_if(state_vec_.begin(), state_vec_.end(),
389  [](const State *s) { return s != nullptr; });
390  }
391 
392  // Iterates over cached states (in an arbitrary order); only works if GC is
393  // enabled (o.w. avoiding state_list_ overhead).
394  bool Done() const { return iter_ == state_list_.end(); }
395 
396  StateId Value() const { return *iter_; }
397 
398  void Next() { ++iter_; }
399 
400  void Reset() { iter_ = state_list_.begin(); }
401 
402  // Deletes current state and advances to next.
403  void Delete() {
404  State::Destroy(state_vec_[*iter_], &state_alloc_);
405  state_vec_[*iter_] = nullptr;
406  state_list_.erase(iter_++);
407  }
408 
409  private:
410  void CopyStates(const VectorCacheStore<State> &store) {
411  Clear();
412  state_vec_.reserve(store.state_vec_.size());
413  for (size_t s = 0; s < store.state_vec_.size(); ++s) {
414  State *state = nullptr;
415  const auto *store_state = store.state_vec_[s];
416  if (store_state) {
417  state = new (&state_alloc_) State(*store_state, arc_alloc_);
418  if (cache_gc_) state_list_.push_back(s);
419  }
420  state_vec_.push_back(state);
421  }
422  }
423 
424  bool cache_gc_; // Supports iteration when true.
425  std::vector<State *> state_vec_; // Vector of states (or null).
426  StateList state_list_; // List of states.
427  typename StateList::iterator iter_; // State list iterator.
428  typename State::StateAllocator state_alloc_; // For state allocation.
429  typename State::ArcAllocator arc_alloc_; // For arc allocation.
430 };
431 
432 // This class uses a hash map from state IDs to pointers to cached states.
433 template <class S>
435  public:
436  using State = S;
437  using Arc = typename State::Arc;
438  using StateId = typename Arc::StateId;
439 
440  using StateMap =
441  std::unordered_map<StateId, State *, std::hash<StateId>,
442  std::equal_to<StateId>,
444 
445  // Required constructors/assignment operators.
446  explicit HashCacheStore(const CacheOptions &opts) {
447  Clear();
448  Reset();
449  }
450 
452  CopyStates(store);
453  Reset();
454  }
455 
456  ~HashCacheStore() { Clear(); }
457 
459  if (this != &store) {
460  CopyStates(store);
461  Reset();
462  }
463  return *this;
464  }
465 
466  // Returns nullptr if state is not stored.
467  const State *GetState(StateId s) const {
468  const auto it = state_map_.find(s);
469  return it != state_map_.end() ? it->second : nullptr;
470  }
471 
472  // Creates state if state is not stored.
474  auto *&state = state_map_[s];
475  if (!state) state = new (&state_alloc_) State(arc_alloc_);
476  return state;
477  }
478 
479  // Similar to State::AddArc() but updates cache store book-keeping.
480  void AddArc(State *state, const Arc &arc) { state->AddArc(arc); }
481 
482  // Similar to State::SetArcs() but updates internal cache size; call only
483  // once.
484  void SetArcs(State *state) { state->SetArcs(); }
485 
486  // Deletes all arcs.
487  void DeleteArcs(State *state) { state->DeleteArcs(); }
488 
489  // Deletes some arcs.
490  void DeleteArcs(State *state, size_t n) { state->DeleteArcs(n); }
491 
492  // Deletes all cached states.
493  void Clear() {
494  for (auto &[unused_state_id, state_ptr] : state_map_) {
495  State::Destroy(state_ptr, &state_alloc_);
496  }
497  state_map_.clear();
498  }
499 
500  StateId CountStates() const { return state_map_.size(); }
501 
502  // Iterates over cached states (in an arbitrary order).
503  bool Done() const { return iter_ == state_map_.end(); }
504 
505  StateId Value() const { return iter_->first; }
506 
507  void Next() { ++iter_; }
508 
509  void Reset() { iter_ = state_map_.begin(); }
510 
511  // Deletes current state and advances to next.
512  void Delete() {
513  State::Destroy(iter_->second, &state_alloc_);
514  state_map_.erase(iter_++);
515  }
516 
517  private:
518  void CopyStates(const HashCacheStore<State> &store) {
519  Clear();
520  for (auto &[state_id, state_ptr] : store.state_map_) {
521  state_map_[state_id] = new (&state_alloc_) State(*state_ptr, arc_alloc_);
522  }
523  }
524 
525  StateMap state_map_; // Map from state ID to state.
526  typename StateMap::iterator iter_; // State map iterator.
527  typename State::StateAllocator state_alloc_; // For state allocation.
528  typename State::ArcAllocator arc_alloc_; // For arc allocation.
529 };
530 
531 // Garbage-colllection cache stores.
532 
533 // This class implements a simple garbage collection scheme when
534 // 'opts.gc_limit = 0'. In particular, the first cached state is reused for each
535 // new state so long as the reference count is zero on the to-be-reused state.
536 // Otherwise, the full underlying store is used. The caller can increment the
537 // reference count to inhibit the GC of in-use states (e.g., in an ArcIterator).
538 //
539 // The typical use case for this optimization is when a single pass over a
540 // cached
541 // FST is performed with only one-state expanded at a time.
542 template <class CacheStore>
544  public:
545  using State = typename CacheStore::State;
546  using Arc = typename State::Arc;
547  using StateId = typename Arc::StateId;
548 
549  // Required constructors/assignment operators.
550  explicit FirstCacheStore(const CacheOptions &opts)
551  : store_(opts),
552  cache_gc_(opts.gc_limit == 0), // opts.gc ignored historically.
553  cache_first_state_id_(kNoStateId),
554  cache_first_state_(nullptr) {}
555 
557  : store_(store.store_),
558  cache_gc_(store.cache_gc_),
559  cache_first_state_id_(store.cache_first_state_id_),
560  cache_first_state_(store.cache_first_state_id_ != kNoStateId
561  ? store_.GetMutableState(0)
562  : nullptr) {}
563 
565  const FirstCacheStore<CacheStore> &store) {
566  if (this != &store) {
567  store_ = store.store_;
568  cache_gc_ = store.cache_gc_;
569  cache_first_state_id_ = store.cache_first_state_id_;
570  cache_first_state_ = store.cache_first_state_id_ != kNoStateId
571  ? store_.GetMutableState(0)
572  : nullptr;
573  }
574  return *this;
575  }
576 
577  // Returns nullptr if state is not stored.
578  const State *GetState(StateId s) const {
579  // store_ state 0 may hold first cached state; the rest are shifted by 1.
580  return s == cache_first_state_id_ ? cache_first_state_
581  : store_.GetState(s + 1);
582  }
583 
584  // Creates state if state is not stored.
586  // store_ state 0 used to hold first cached state; the rest are shifted by
587  // 1.
588  if (cache_first_state_id_ == s) {
589  return cache_first_state_; // Request for first cached state.
590  }
591  if (cache_gc_) {
592  if (cache_first_state_id_ == kNoStateId) {
593  cache_first_state_id_ = s; // Sets first cached state.
594  cache_first_state_ = store_.GetMutableState(0);
595  cache_first_state_->SetFlags(kCacheInit, kCacheInit);
596  cache_first_state_->ReserveArcs(2 * kAllocSize);
597  return cache_first_state_;
598  } else if (cache_first_state_->RefCount() == 0) {
599  cache_first_state_id_ = s; // Updates first cached state.
600  cache_first_state_->Reset();
601  cache_first_state_->SetFlags(kCacheInit, kCacheInit);
602  return cache_first_state_;
603  } else { // Keeps first cached state.
604  cache_first_state_->SetFlags(0, kCacheInit); // Clears initialized bit.
605  cache_gc_ = false; // Disables GC.
606  }
607  }
608  auto *state = store_.GetMutableState(s + 1);
609  return state;
610  }
611 
612  // Similar to State::AddArc() but updates cache store book-keeping.
613  void AddArc(State *state, const Arc &arc) { store_.AddArc(state, arc); }
614 
615  // Similar to State::SetArcs() but updates internal cache size; call only
616  // once.
617  void SetArcs(State *state) { store_.SetArcs(state); }
618 
619  // Deletes all arcs
620  void DeleteArcs(State *state) { store_.DeleteArcs(state); }
621 
622  // Deletes some arcs
623  void DeleteArcs(State *state, size_t n) { store_.DeleteArcs(state, n); }
624 
625  // Deletes all cached states
626  void Clear() {
627  store_.Clear();
628  cache_first_state_id_ = kNoStateId;
629  cache_first_state_ = nullptr;
630  }
631 
632  StateId CountStates() const { return store_.CountStates(); }
633 
634  // Iterates over cached states (in an arbitrary order). Only needed if GC is
635  // enabled.
636  bool Done() const { return store_.Done(); }
637 
638  StateId Value() const {
639  // store_ state 0 may hold first cached state; rest shifted + 1.
640  const auto s = store_.Value();
641  return s ? s - 1 : cache_first_state_id_;
642  }
643 
644  void Next() { store_.Next(); }
645 
646  void Reset() { store_.Reset(); }
647 
648  // Deletes current state and advances to next.
649  void Delete() {
650  if (Value() == cache_first_state_id_) {
651  cache_first_state_id_ = kNoStateId;
652  cache_first_state_ = nullptr;
653  }
654  store_.Delete();
655  }
656 
657  private:
658  CacheStore store_; // Underlying store.
659  bool cache_gc_; // GC enabled.
660  StateId cache_first_state_id_; // First cached state ID.
661  State *cache_first_state_; // First cached state.
662 };
663 
664 // This class implements mark-sweep garbage collection on an underlying cache
665 // store. If GC is enabled, garbage collection of states is performed in a
666 // rough approximation of LRU order once when 'gc_limit' bytes is reached. The
667 // caller can increment the reference count to inhibit the GC of in-use state
668 // (e.g., in an ArcIterator). With GC enabled, the 'gc_limit' parameter allows
669 // the caller to trade-off time vs. space.
670 template <class CacheStore>
672  public:
673  using State = typename CacheStore::State;
674  using Arc = typename State::Arc;
675  using StateId = typename Arc::StateId;
676 
677  // Required constructors/assignment operators.
678  explicit GCCacheStore(const CacheOptions &opts)
679  : store_(opts),
680  cache_gc_request_(opts.gc),
681  cache_limit_(opts.gc_limit > kMinCacheLimit ? opts.gc_limit
682  : kMinCacheLimit),
683  cache_gc_(false),
684  cache_size_(0) {}
685 
686  // Returns 0 if state is not stored.
687  const State *GetState(StateId s) const { return store_.GetState(s); }
688 
689  // Creates state if state is not stored
691  auto *state = store_.GetMutableState(s);
692  if (cache_gc_request_ && !(state->Flags() & kCacheInit)) {
693  state->SetFlags(kCacheInit, kCacheInit);
694  cache_size_ += sizeof(State) + state->NumArcs() * sizeof(Arc);
695  // GC is enabled once an uninited state (from underlying store) is seen.
696  cache_gc_ = true;
697  if (cache_size_ > cache_limit_) GC(state, false);
698  }
699  return state;
700  }
701 
702  // Similar to State::AddArc() but updates cache store book-keeping.
703  void AddArc(State *state, const Arc &arc) {
704  store_.AddArc(state, arc);
705  if (cache_gc_ && (state->Flags() & kCacheInit)) {
706  cache_size_ += sizeof(Arc);
707  if (cache_size_ > cache_limit_) GC(state, false);
708  }
709  }
710 
711  // Similar to State::SetArcs() but updates internal cache size; call only
712  // once.
713  void SetArcs(State *state) {
714  store_.SetArcs(state);
715  if (cache_gc_ && (state->Flags() & kCacheInit)) {
716  cache_size_ += state->NumArcs() * sizeof(Arc);
717  if (cache_size_ > cache_limit_) GC(state, false);
718  }
719  }
720 
721  // Deletes all arcs.
722  void DeleteArcs(State *state) {
723  if (cache_gc_ && (state->Flags() & kCacheInit)) {
724  cache_size_ -= state->NumArcs() * sizeof(Arc);
725  }
726  store_.DeleteArcs(state);
727  }
728 
729  // Deletes some arcs.
730  void DeleteArcs(State *state, size_t n) {
731  if (cache_gc_ && (state->Flags() & kCacheInit)) {
732  cache_size_ -= n * sizeof(Arc);
733  }
734  store_.DeleteArcs(state, n);
735  }
736 
737  // Deletes all cached states.
738  void Clear() {
739  store_.Clear();
740  cache_size_ = 0;
741  }
742 
743  StateId CountStates() const { return store_.CountStates(); }
744 
745  // Iterates over cached states (in an arbitrary order); only needed if GC is
746  // enabled.
747  bool Done() const { return store_.Done(); }
748 
749  StateId Value() const { return store_.Value(); }
750 
751  void Next() { store_.Next(); }
752 
753  void Reset() { store_.Reset(); }
754 
755  // Deletes current state and advances to next.
756  void Delete() {
757  if (cache_gc_) {
758  const auto *state = store_.GetState(Value());
759  if (state->Flags() & kCacheInit) {
760  cache_size_ -= sizeof(State) + state->NumArcs() * sizeof(Arc);
761  }
762  }
763  store_.Delete();
764  }
765 
766  // Removes from the cache store (not referenced-counted and not the current)
767  // states that have not been accessed since the last GC until at most
768  // cache_fraction * cache_limit_ bytes are cached. If that fails to free
769  // enough, attempts to uncaching recently visited states as well. If still
770  // unable to free enough memory, then widens cache_limit_.
771  void GC(const State *current, bool free_recent, float cache_fraction = 0.666);
772 
773  // Returns the current cache size in bytes or 0 if GC is disabled.
774  size_t CacheSize() const { return cache_size_; }
775 
776  // Returns the cache limit in bytes.
777  size_t CacheLimit() const { return cache_limit_; }
778 
779  private:
780  static constexpr size_t kMinCacheLimit = 8096; // Minimum cache limit.
781 
782  CacheStore store_; // Underlying store.
783  bool cache_gc_request_; // GC requested but possibly not yet enabled.
784  size_t cache_limit_; // Number of bytes allowed before GC.
785  bool cache_gc_; // GC enabled
786  size_t cache_size_; // Number of bytes cached.
787 };
788 
789 template <class CacheStore>
790 void GCCacheStore<CacheStore>::GC(const State *current, bool free_recent,
791  float cache_fraction) {
792  if (!cache_gc_) return;
793  VLOG(2) << "GCCacheStore: Enter GC: object = "
794  << "(" << this << "), free recently cached = " << free_recent
795  << ", cache size = " << cache_size_
796  << ", cache frac = " << cache_fraction
797  << ", cache limit = " << cache_limit_ << "\n";
798  size_t cache_target = cache_fraction * cache_limit_;
799  store_.Reset();
800  while (!store_.Done()) {
801  auto *state = store_.GetMutableState(store_.Value());
802  if (cache_size_ > cache_target && state->RefCount() == 0 &&
803  (free_recent || !(state->Flags() & kCacheRecent)) && state != current) {
804  if (state->Flags() & kCacheInit) {
805  size_t size = sizeof(State) + state->NumArcs() * sizeof(Arc);
806  if (size < cache_size_) {
807  cache_size_ -= size;
808  }
809  }
810  store_.Delete();
811  } else {
812  state->SetFlags(0, kCacheRecent);
813  store_.Next();
814  }
815  }
816  if (!free_recent && cache_size_ > cache_target) { // Recurses on recent.
817  GC(current, true, cache_fraction);
818  } else if (cache_target > 0) { // Widens cache limit.
819  while (cache_size_ > cache_target) {
820  cache_limit_ *= 2;
821  cache_target *= 2;
822  }
823  } else if (cache_size_ > 0) {
824  FSTERROR() << "GCCacheStore:GC: Unable to free all cached states";
825  }
826  VLOG(2) << "GCCacheStore: Exit GC: object = "
827  << "(" << this << "), free recently cached = " << free_recent
828  << ", cache size = " << cache_size_
829  << ", cache frac = " << cache_fraction
830  << ", cache limit = " << cache_limit_ << "\n";
831 }
832 
833 // This class is the default cache state and store used by CacheBaseImpl.
834 // It uses VectorCacheStore for storage decorated by FirstCacheStore
835 // and GCCacheStore to do (optional) garbage collection.
836 template <class Arc>
838  : public GCCacheStore<FirstCacheStore<VectorCacheStore<CacheState<Arc>>>> {
839  public:
840  explicit DefaultCacheStore(const CacheOptions &opts)
842  }
843 };
844 
845 namespace internal {
846 
847 // This class is used to cache FST elements stored in states of type State
848 // (see CacheState) with the flags used to indicate what has been cached. Use
849 // HasStart(), HasFinal(), and HasArcs() to determine if cached and SetStart(),
850 // SetFinal(), AddArc(), (or PushArc() and SetArcs()) to cache. Note that you
851 // must set the final weight even if the state is non-final to mark it as
852 // cached. The state storage method and any garbage collection policy are
853 // determined by the cache store. If the store is passed in with the options,
854 // CacheBaseImpl takes ownership.
855 template <class State,
856  class CacheStore = DefaultCacheStore<typename State::Arc>>
857 class CacheBaseImpl : public FstImpl<typename State::Arc> {
858  public:
859  using Arc = typename State::Arc;
860  using StateId = typename Arc::StateId;
861  using Weight = typename Arc::Weight;
862 
863  using Store = CacheStore;
864 
865  using FstImpl<Arc>::Type;
867 
868  explicit CacheBaseImpl(const CacheOptions &opts = CacheOptions())
869  : has_start_(false),
870  cache_start_(kNoStateId),
871  nknown_states_(0),
872  min_unexpanded_state_id_(0),
873  max_expanded_state_id_(-1),
874  cache_gc_(opts.gc),
875  cache_limit_(opts.gc_limit),
876  cache_store_(new CacheStore(opts)),
877  new_cache_store_(true),
878  own_cache_store_(true) {}
879 
881  : has_start_(false),
882  cache_start_(kNoStateId),
883  nknown_states_(0),
884  min_unexpanded_state_id_(0),
885  max_expanded_state_id_(-1),
886  cache_gc_(opts.gc),
887  cache_limit_(opts.gc_limit),
888  cache_store_(
889  opts.store ? opts.store
890  : new CacheStore(CacheOptions(opts.gc, opts.gc_limit))),
891  new_cache_store_(!opts.store),
892  own_cache_store_(opts.store ? opts.own_store : true) {}
893 
894  // Preserve gc parameters. If preserve_cache is true, also preserves
895  // cache data.
897  bool preserve_cache = false)
898  : FstImpl<Arc>(),
899  has_start_(false),
900  cache_start_(kNoStateId),
901  nknown_states_(0),
902  min_unexpanded_state_id_(0),
903  max_expanded_state_id_(-1),
904  cache_gc_(impl.cache_gc_),
905  cache_limit_(impl.cache_limit_),
906  cache_store_(new CacheStore(CacheOptions(cache_gc_, cache_limit_))),
907  new_cache_store_(impl.new_cache_store_ || !preserve_cache),
908  own_cache_store_(true) {
909  if (preserve_cache) {
910  *cache_store_ = *impl.cache_store_;
911  has_start_ = impl.has_start_;
912  cache_start_ = impl.cache_start_;
913  nknown_states_ = impl.nknown_states_;
914  expanded_states_ = impl.expanded_states_;
915  min_unexpanded_state_id_ = impl.min_unexpanded_state_id_;
916  max_expanded_state_id_ = impl.max_expanded_state_id_;
917  }
918  }
919 
920  ~CacheBaseImpl() override {
921  if (own_cache_store_) delete cache_store_;
922  }
923 
924  void SetStart(StateId s) {
925  cache_start_ = s;
926  has_start_ = true;
927  if (s >= nknown_states_) nknown_states_ = s + 1;
928  }
929 
930  void SetFinal(StateId s, Weight weight = Weight::One()) {
931  auto *state = cache_store_->GetMutableState(s);
932  state->SetFinal(std::move(weight));
933  static constexpr auto flags = kCacheFinal | kCacheRecent;
934  state->SetFlags(flags, flags);
935  }
936 
937  // Adds a single arc to a state but delays cache book-keeping. SetArcs must
938  // be called when all PushArc and EmplaceArc calls at a state are complete.
939  // Do not mix with calls to AddArc.
940  void PushArc(StateId s, const Arc &arc) {
941  auto *state = cache_store_->GetMutableState(s);
942  state->PushArc(arc);
943  }
944 
945  void PushArc(StateId s, Arc &&arc) {
946  auto *state = cache_store_->GetMutableState(s);
947  state->PushArc(std::move(arc));
948  }
949 
950  // Adds a single arc to a state but delays cache book-keeping. SetArcs must
951  // be called when all PushArc and EmplaceArc calls at a state are complete.
952  // Do not mix with calls to AddArc.
953  template <class... T>
954  void EmplaceArc(StateId s, T &&...ctor_args) {
955  auto *state = cache_store_->GetMutableState(s);
956  state->EmplaceArc(std::forward<T>(ctor_args)...);
957  }
958 
959  // Marks arcs of a state as cached and does cache book-keeping after all
960  // calls to PushArc have been completed. Do not mix with calls to AddArc.
961  void SetArcs(StateId s) {
962  auto *state = cache_store_->GetMutableState(s);
963  cache_store_->SetArcs(state);
964  const auto narcs = state->NumArcs();
965  for (size_t a = 0; a < narcs; ++a) {
966  const auto &arc = state->GetArc(a);
967  if (arc.nextstate >= nknown_states_) nknown_states_ = arc.nextstate + 1;
968  }
969  SetExpandedState(s);
970  static constexpr auto flags = kCacheArcs | kCacheRecent;
971  state->SetFlags(flags, flags);
972  }
973 
974  void ReserveArcs(StateId s, size_t n) {
975  auto *state = cache_store_->GetMutableState(s);
976  state->ReserveArcs(n);
977  }
978 
979  void DeleteArcs(StateId s) {
980  auto *state = cache_store_->GetMutableState(s);
981  cache_store_->DeleteArcs(state);
982  }
983 
984  void DeleteArcs(StateId s, size_t n) {
985  auto *state = cache_store_->GetMutableState(s);
986  cache_store_->DeleteArcs(state, n);
987  }
988 
989  void Clear() {
990  nknown_states_ = 0;
991  min_unexpanded_state_id_ = 0;
992  max_expanded_state_id_ = -1;
993  has_start_ = false;
994  cache_start_ = kNoStateId;
995  cache_store_->Clear();
996  }
997 
998  // Is the start state cached?
999  bool HasStart() const {
1000  if (!has_start_ && Properties(kError)) has_start_ = true;
1001  return has_start_;
1002  }
1003 
1004  // Is the final weight of the state cached?
1005  bool HasFinal(StateId s) const {
1006  const auto *state = cache_store_->GetState(s);
1007  if (state && state->Flags() & kCacheFinal) {
1008  state->SetFlags(kCacheRecent, kCacheRecent);
1009  return true;
1010  } else {
1011  return false;
1012  }
1013  }
1014 
1015  // Are arcs of the state cached?
1016  bool HasArcs(StateId s) const {
1017  const auto *state = cache_store_->GetState(s);
1018  if (state && state->Flags() & kCacheArcs) {
1019  state->SetFlags(kCacheRecent, kCacheRecent);
1020  return true;
1021  } else {
1022  return false;
1023  }
1024  }
1025 
1026  StateId Start() const { return cache_start_; }
1027 
1028  Weight Final(StateId s) const {
1029  const auto *state = cache_store_->GetState(s);
1030  return state->Final();
1031  }
1032 
1033  size_t NumArcs(StateId s) const {
1034  const auto *state = cache_store_->GetState(s);
1035  return state->NumArcs();
1036  }
1037 
1038  size_t NumInputEpsilons(StateId s) const {
1039  const auto *state = cache_store_->GetState(s);
1040  return state->NumInputEpsilons();
1041  }
1042 
1043  size_t NumOutputEpsilons(StateId s) const {
1044  const auto *state = cache_store_->GetState(s);
1045  return state->NumOutputEpsilons();
1046  }
1047 
1048  // Provides information needed for generic arc iterator.
1050  const auto *state = cache_store_->GetState(s);
1051  data->base = nullptr;
1052  data->narcs = state->NumArcs();
1053  data->arcs = state->Arcs();
1054  data->ref_count = state->MutableRefCount();
1055  state->IncrRefCount();
1056  }
1057 
1058  // Number of known states.
1059  StateId NumKnownStates() const { return nknown_states_; }
1060 
1061  // Updates number of known states, taking into account the passed state ID.
1063  if (s >= nknown_states_) nknown_states_ = s + 1;
1064  }
1065 
1066  // Finds the mininum never-expanded state ID.
1068  while (min_unexpanded_state_id_ <= max_expanded_state_id_ &&
1069  ExpandedState(min_unexpanded_state_id_)) {
1070  ++min_unexpanded_state_id_;
1071  }
1072  return min_unexpanded_state_id_;
1073  }
1074 
1075  // Returns maximum ever-expanded state ID.
1076  StateId MaxExpandedState() const { return max_expanded_state_id_; }
1077 
1079  if (s > max_expanded_state_id_) max_expanded_state_id_ = s;
1080  if (s < min_unexpanded_state_id_) return;
1081  if (s == min_unexpanded_state_id_) ++min_unexpanded_state_id_;
1082  if (cache_gc_ || cache_limit_ == 0) {
1083  if (expanded_states_.size() <= static_cast<size_t>(s))
1084  expanded_states_.resize(s + 1, false);
1085  expanded_states_[s] = true;
1086  }
1087  }
1088 
1089  bool ExpandedState(StateId s) const {
1090  if (cache_gc_ || cache_limit_ == 0) {
1091  return expanded_states_[s];
1092  } else if (new_cache_store_) {
1093  return cache_store_->GetState(s) != nullptr;
1094  } else {
1095  // If the cache was not created by this class, then the cached state needs
1096  // to be inspected to update nknown_states_.
1097  return false;
1098  }
1099  }
1100 
1101  const CacheStore *GetCacheStore() const { return cache_store_; }
1102 
1103  CacheStore *GetCacheStore() { return cache_store_; }
1104 
1105  // Caching on/off switch, limit and size accessors.
1106 
1107  bool GetCacheGc() const { return cache_gc_; }
1108 
1109  size_t GetCacheLimit() const { return cache_limit_; }
1110 
1111  private:
1112  mutable bool has_start_; // Is the start state cached?
1113  StateId cache_start_; // ID of start state.
1114  StateId nknown_states_; // Number of known states.
1115  std::vector<bool> expanded_states_; // States that have been expanded.
1116  mutable StateId min_unexpanded_state_id_; // Minimum never-expanded state ID
1117  mutable StateId max_expanded_state_id_; // Maximum ever-expanded state ID
1118  bool cache_gc_; // GC enabled.
1119  size_t cache_limit_; // Number of bytes allowed before GC.
1120  CacheStore *cache_store_; // The store of cached states.
1121  bool new_cache_store_; // Was the store was created by class?
1122  bool own_cache_store_; // Is the store owned by class?
1123 
1124  CacheBaseImpl &operator=(const CacheBaseImpl &impl) = delete;
1125 };
1126 
1127 // A CacheBaseImpl with the default cache state type.
1128 template <class Arc>
1129 class CacheImpl : public CacheBaseImpl<CacheState<Arc>> {
1130  public:
1132 
1133  CacheImpl() = default;
1134 
1135  explicit CacheImpl(const CacheOptions &opts)
1136  : CacheBaseImpl<CacheState<Arc>>(opts) {}
1137 
1138  CacheImpl(const CacheImpl<Arc> &impl, bool preserve_cache = false)
1139  : CacheBaseImpl<State>(impl, preserve_cache) {}
1140 
1141  private:
1142  CacheImpl &operator=(const CacheImpl &impl) = delete;
1143 };
1144 
1145 } // namespace internal
1146 
1147 // Use this to make a state iterator for a CacheBaseImpl-derived FST, which must
1148 // have Arc and Store types defined. Note this iterator only returns those
1149 // states reachable from the initial state, so consider implementing a
1150 // class-specific one.
1151 //
1152 // This class may be derived from.
1153 template <class FST>
1154 class CacheStateIterator : public StateIteratorBase<typename FST::Arc> {
1155  public:
1156  using Arc = typename FST::Arc;
1157  using StateId = typename Arc::StateId;
1158  using Weight = typename Arc::Weight;
1159 
1160  using Store = typename FST::Store;
1161  using State = typename Store::State;
1163 
1165  : fst_(fst), impl_(impl), s_(0) {
1166  fst_.Start(); // Forces start state.
1167  }
1168 
1169  bool Done() const final {
1170  if (s_ < impl_->NumKnownStates()) return false;
1171  for (StateId u = impl_->MinUnexpandedState(); u < impl_->NumKnownStates();
1172  u = impl_->MinUnexpandedState()) {
1173  // Forces state expansion.
1174  ArcIterator<FST> aiter(fst_, u);
1176  for (; !aiter.Done(); aiter.Next()) {
1177  impl_->UpdateNumKnownStates(aiter.Value().nextstate);
1178  }
1179  impl_->SetExpandedState(u);
1180  if (s_ < impl_->NumKnownStates()) return false;
1181  }
1182  return true;
1183  }
1184 
1185  StateId Value() const final { return s_; }
1186 
1187  void Next() final { ++s_; }
1188 
1189  void Reset() final { s_ = 0; }
1190 
1191  private:
1192  const FST &fst_;
1193  Impl *impl_;
1194  StateId s_;
1195 };
1196 
1197 // Used to make an arc iterator for a CacheBaseImpl-derived FST, which must
1198 // have Arc and State types defined.
1199 template <class FST>
1201  public:
1202  using Arc = typename FST::Arc;
1203  using StateId = typename Arc::StateId;
1204  using Weight = typename Arc::Weight;
1205 
1206  using Store = typename FST::Store;
1207  using State = typename Store::State;
1209 
1210  CacheArcIterator(Impl *impl, StateId s) : i_(0) {
1211  state_ = impl->GetCacheStore()->GetMutableState(s);
1212  state_->IncrRefCount();
1213  }
1214 
1215  ~CacheArcIterator() { state_->DecrRefCount(); }
1216 
1217  bool Done() const { return i_ >= state_->NumArcs(); }
1218 
1219  const Arc &Value() const { return state_->GetArc(i_); }
1220 
1221  void Next() { ++i_; }
1222 
1223  size_t Position() const { return i_; }
1224 
1225  void Reset() { i_ = 0; }
1226 
1227  void Seek(size_t a) { i_ = a; }
1228 
1229  constexpr uint8_t Flags() const { return kArcValueFlags; }
1230 
1231  void SetFlags(uint8_t flags, uint8_t mask) {}
1232 
1233  private:
1234  const State *state_;
1235  size_t i_;
1236 
1237  CacheArcIterator(const CacheArcIterator &) = delete;
1238  CacheArcIterator &operator=(const CacheArcIterator &) = delete;
1239 };
1240 
1241 // Use this to make a mutable arc iterator for a CacheBaseImpl-derived FST,
1242 // which must have types Arc and Store defined.
1243 template <class FST>
1245  : public MutableArcIteratorBase<typename FST::Arc> {
1246  public:
1247  using Arc = typename FST::Arc;
1248  using StateId = typename Arc::StateId;
1249  using Weight = typename Arc::Weight;
1250 
1251  using Store = typename FST::Store;
1252  using State = typename Store::State;
1254 
1255  // User must call MutateCheck() in the constructor.
1256  CacheMutableArcIterator(Impl *impl, StateId s) : i_(0), s_(s), impl_(impl) {
1257  state_ = impl_->GetCacheStore()->GetMutableState(s_);
1258  state_->IncrRefCount();
1259  }
1260 
1261  ~CacheMutableArcIterator() override { state_->DecrRefCount(); }
1262 
1263  bool Done() const final { return i_ >= state_->NumArcs(); }
1264 
1265  const Arc &Value() const final { return state_->GetArc(i_); }
1266 
1267  void Next() final { ++i_; }
1268 
1269  size_t Position() const final { return i_; }
1270 
1271  void Reset() final { i_ = 0; }
1272 
1273  void Seek(size_t a) final { i_ = a; }
1274 
1275  void SetValue(const Arc &arc) final { state_->SetArc(arc, i_); }
1276 
1277  uint8_t Flags() const final { return kArcValueFlags; }
1278 
1279  void SetFlags(uint8_t, uint8_t) final {}
1280 
1281  private:
1282  size_t i_;
1283  StateId s_;
1284  Impl *impl_;
1285  State *state_;
1286 
1288  CacheMutableArcIterator &operator=(const CacheMutableArcIterator &) = delete;
1289 };
1290 
1291 // Wrap existing CacheStore implementation to use with ExpanderFst.
1292 template <class CacheStore>
1294  public:
1295  using State = typename CacheStore::State;
1296  using Arc = typename CacheStore::Arc;
1297  using StateId = typename Arc::StateId;
1298  using Weight = typename Arc::Weight;
1299 
1301  : store_(opts) {}
1302 
1303  template <class Expander>
1304  State *FindOrExpand(Expander &expander, StateId s) {
1305  auto *state = store_.GetMutableState(s);
1306  if (state->Flags()) {
1307  state->SetFlags(kCacheRecent, kCacheRecent);
1308  } else {
1309  StateBuilder builder(state);
1310  expander.Expand(s, &builder);
1311  state->SetFlags(kCacheFlags, kCacheFlags);
1312  store_.SetArcs(state);
1313  }
1314  return state;
1315  }
1316 
1317  private:
1318  CacheStore store_;
1319 
1320  struct StateBuilder {
1321  State *state;
1322 
1323  explicit StateBuilder(State *state_) : state(state_) {}
1324 
1325  void AddArc(const Arc &arc) { state->PushArc(arc); }
1326 
1327  void AddArc(Arc &&arc) { state->PushArc(std::move(arc)); }
1328 
1329  void SetFinal(Weight weight = Weight::One()) {
1330  state->SetFinal(std::move(weight));
1331  }
1332  };
1333 };
1334 
1335 } // namespace fst
1336 
1337 #endif // FST_CACHE_H_
void GC(const State *current, bool free_recent, float cache_fraction=0.666)
Definition: cache.h:790
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:124
VectorCacheStore(const VectorCacheStore< S > &store)
Definition: cache.h:324
void Seek(size_t a)
Definition: cache.h:1227
size_t CacheLimit() const
Definition: cache.h:777
bool Done() const
Definition: cache.h:636
VectorCacheStore & operator=(const VectorCacheStore &store)
Definition: cache.h:332
State * GetMutableState(StateId s)
Definition: cache.h:585
CacheImpl(const CacheOptions &opts)
Definition: cache.h:1135
constexpr uint8_t kCacheArcs
Definition: cache.h:81
constexpr uint8_t kArcValueFlags
Definition: fst.h:453
uint8_t Flags() const final
Definition: cache.h:1277
CacheState(const ArcAllocator &alloc)
Definition: cache.h:101
size_t NumInputEpsilons(StateId s) const
Definition: cache.h:1038
CacheOptions(bool gc=FST_FLAGS_fst_default_cache_gc, size_t gc_limit=FST_FLAGS_fst_default_cache_gc_limit)
Definition: cache.h:54
HashCacheStore(const HashCacheStore< S > &store)
Definition: cache.h:451
const Arc & Value() const
Definition: cache.h:1219
constexpr uint8_t kArcNoCache
Definition: fst.h:452
void EmplaceArc(T &&...ctor_args)
Definition: cache.h:170
bool HasFinal(StateId s) const
Definition: cache.h:1005
const Arc & GetArc(size_t n) const
Definition: cache.h:134
GCCacheStore(const CacheOptions &opts)
Definition: cache.h:678
bool ExpandedState(StateId s) const
Definition: cache.h:1089
void PushArc(const Arc &arc)
Definition: cache.h:164
StateId CountStates() const
Definition: cache.h:743
StateId Start() const
Definition: cache.h:1026
size_t NumOutputEpsilons() const
Definition: cache.h:130
DECLARE_int64(fst_default_cache_gc_limit)
void Reset() final
Definition: cache.h:1189
typename Arc::StateId StateId
Definition: cache.h:93
typename SynchronizeFst< Arc >::Store Store
Definition: cache.h:1206
void SetFinal(StateId s, Weight weight=Weight::One())
Definition: cache.h:930
M ArcAllocator
Definition: cache.h:96
typename Arc::StateId StateId
Definition: cache.h:1248
void SetFlags(uint8_t flags, uint8_t mask) const
Definition: cache.h:205
void UpdateNumKnownStates(StateId s)
Definition: cache.h:1062
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:107
~CacheMutableArcIterator() override
Definition: cache.h:1261
void SetArcs(State *state)
Definition: cache.h:713
constexpr uint8_t kCacheRecent
Definition: cache.h:83
StateId Value() const
Definition: cache.h:505
constexpr uint8_t kCacheFlags
Definition: cache.h:84
constexpr uint64_t kError
Definition: properties.h:52
FirstCacheStore< CacheStore > & operator=(const FirstCacheStore< CacheStore > &store)
Definition: cache.h:564
int RefCount() const
Definition: cache.h:143
CacheState(const CacheState< A > &state, const ArcAllocator &alloc)
Definition: cache.h:109
typename std::allocator_traits< ArcAllocator >::template rebind_alloc< CacheState< A, M >> StateAllocator
Definition: cache.h:98
typename CacheStore::State State
Definition: cache.h:1295
void AddArc(State *state, const Arc &arc)
Definition: cache.h:703
void Next()
Definition: cache.h:751
StateId CountStates() const
Definition: cache.h:500
typename SynchronizeFst< Arc >::Arc Arc
Definition: cache.h:1156
bool Done() const
Definition: cache.h:1217
size_t NumArcs() const
Definition: cache.h:132
Weight Final() const
Definition: cache.h:126
constexpr int kAllocSize
Definition: memory.h:35
State * FindOrExpand(Expander &expander, StateId s)
Definition: cache.h:1304
std::unordered_map< StateId, State *, std::hash< StateId >, std::equal_to< StateId >, PoolAllocator< std::pair< const StateId, State * >>> StateMap
Definition: cache.h:443
bool Done() const
Definition: cache.h:747
CacheStore * store
Definition: cache.h:66
typename Arc::Weight Weight
Definition: cache.h:1249
typename Store::State State
Definition: cache.h:1252
State * GetMutableState(StateId s)
Definition: cache.h:690
size_t CacheSize() const
Definition: cache.h:774
bool Done() const
Definition: cache.h:394
void SetArcs(State *state)
Definition: cache.h:617
void DeleteArcs(State *state)
Definition: cache.h:620
constexpr int kNoStateId
Definition: fst.h:196
typename Arc::Weight Weight
Definition: cache.h:94
const Arc & Value() const
Definition: fst.h:536
static void Destroy(CacheState< Arc > *state, StateAllocator *alloc)
Definition: cache.h:225
void SetFlags(uint8_t flags, uint8_t mask)
Definition: cache.h:1231
size_t NumArcs(StateId s) const
Definition: cache.h:1033
typename SynchronizeFst< Arc >::Store Store
Definition: cache.h:1160
bool GetCacheGc() const
Definition: cache.h:1107
CacheImpl(const CacheImpl< Arc > &impl, bool preserve_cache=false)
Definition: cache.h:1138
#define FSTERROR()
Definition: util.h:56
void SetFlags(uint8_t flags, uint8_t mask)
Definition: fst.h:570
typename Arc::Weight Weight
Definition: cache.h:1298
CacheBaseImpl(const CacheImplOptions< CacheStore > &opts)
Definition: cache.h:880
typename Arc::StateId StateId
Definition: cache.h:1297
CacheStore * GetCacheStore()
Definition: cache.h:1103
constexpr uint8_t kCacheFinal
Definition: cache.h:80
VectorCacheStore(const CacheOptions &opts)
Definition: cache.h:319
const State * GetState(StateId s) const
Definition: cache.h:578
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:118
typename FST::Arc Arc
Definition: cache.h:1247
State * GetMutableState(StateId s)
Definition: cache.h:350
std::list< StateId, PoolAllocator< StateId >> StateList
Definition: cache.h:316
void DeleteArcs(StateId s, size_t n)
Definition: cache.h:984
typename Arc::StateId StateId
Definition: cache.h:438
void SetArcs(State *state)
Definition: cache.h:484
CacheBaseImpl(const CacheBaseImpl< State, CacheStore > &impl, bool preserve_cache=false)
Definition: cache.h:896
typename State::Arc Arc
Definition: cache.h:437
bool HasStart() const
Definition: cache.h:999
constexpr uint8_t kCacheInit
Definition: cache.h:82
void SetArc(const Arc &arc, size_t n)
Definition: cache.h:182
void AddArc(const Arc &arc)
Definition: cache.h:153
HashCacheStore & operator=(const HashCacheStore &store)
Definition: cache.h:458
void AddArc(Arc &&arc)
Definition: cache.h:158
typename FirstCacheStore< VectorCacheStore< CacheState< Arc > > >::State State
Definition: cache.h:673
CacheBaseImpl(const CacheOptions &opts=CacheOptions())
Definition: cache.h:868
const Arc & Value() const final
Definition: cache.h:1265
size_t Position() const
Definition: cache.h:1223
void ReserveArcs(StateId s, size_t n)
Definition: cache.h:974
FirstCacheStore(const CacheOptions &opts)
Definition: cache.h:550
StateId Value() const final
Definition: cache.h:1185
void DeleteArcs(State *state)
Definition: cache.h:487
const Arc * Arcs() const
Definition: cache.h:137
void Reset()
Definition: cache.h:117
const State * GetState(StateId s) const
Definition: cache.h:345
#define VLOG(level)
Definition: log.h:54
CacheArcIterator(Impl *impl, StateId s)
Definition: cache.h:1210
void Seek(size_t a) final
Definition: cache.h:1273
size_t NumInputEpsilons() const
Definition: cache.h:128
void SetValue(const Arc &arc) final
Definition: cache.h:1275
StateId Value() const
Definition: cache.h:396
void ReserveArcs(size_t n)
Definition: cache.h:149
size_t Position() const final
Definition: cache.h:1269
bool Done() const
Definition: fst.h:532
void DeleteArcs(State *state)
Definition: cache.h:722
CacheImplOptions(bool gc=FST_FLAGS_fst_default_cache_gc, size_t gc_limit=FST_FLAGS_fst_default_cache_gc_limit, CacheStore *store=nullptr)
Definition: cache.h:69
void DeleteArcs(State *state, size_t n)
Definition: cache.h:623
StateId MinUnexpandedState() const
Definition: cache.h:1067
void SetArcs(State *state)
Definition: cache.h:370
void SetFlags(uint8_t, uint8_t) final
Definition: cache.h:1279
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const
Definition: cache.h:1049
void SetFinal(Weight weight=Weight::One())
Definition: cache.h:145
State * GetMutableState(StateId s)
Definition: cache.h:473
int DecrRefCount() const
Definition: cache.h:214
DefaultCacheStore(const CacheOptions &opts)
Definition: cache.h:840
void Clear()
Definition: cache.h:738
int * MutableRefCount() const
Definition: cache.h:217
void EmplaceArc(StateId s, T &&...ctor_args)
Definition: cache.h:954
std::unique_ptr< ArcIteratorBase< Arc > > base
Definition: fst.h:494
bool Done() const final
Definition: cache.h:1263
bool HasArcs(StateId s) const
Definition: cache.h:1016
bool Done() const
Definition: cache.h:503
void SetStart(StateId s)
Definition: cache.h:924
StateId Value() const
Definition: cache.h:749
typename Arc::Label Label
Definition: cache.h:92
void DeleteArcs(size_t n)
Definition: cache.h:196
StateId MaxExpandedState() const
Definition: cache.h:1076
void PushArc(StateId s, const Arc &arc)
Definition: cache.h:940
HashCacheStore(const CacheOptions &opts)
Definition: cache.h:446
void SetExpandedState(StateId s)
Definition: cache.h:1078
CacheImplOptions(const CacheOptions &opts)
Definition: cache.h:75
typename SynchronizeFst< Arc >::Arc Arc
Definition: cache.h:1202
const State * GetState(StateId s) const
Definition: cache.h:467
CacheMutableArcIterator(Impl *impl, StateId s)
Definition: cache.h:1256
Weight Final(StateId s) const
Definition: cache.h:1028
StateId NumKnownStates() const
Definition: cache.h:1059
void DeleteArcs(State *state)
Definition: cache.h:373
void Reset()
Definition: cache.h:753
bool Done() const final
Definition: cache.h:1169
const Arc * arcs
Definition: fst.h:495
void DeleteArcs(State *state, size_t n)
Definition: cache.h:730
typename FST::Store Store
Definition: cache.h:1251
ExpanderCacheStore(const CacheOptions &opts=CacheOptions())
Definition: cache.h:1300
FirstCacheStore(const FirstCacheStore< CacheStore > &store)
Definition: cache.h:556
bool InBounds(StateId s) const
Definition: cache.h:340
void DeleteArcs(StateId s)
Definition: cache.h:979
int IncrRefCount() const
Definition: cache.h:212
void PushArc(StateId s, Arc &&arc)
Definition: cache.h:945
void Next() final
Definition: cache.h:1187
StateId CountStates() const
Definition: cache.h:387
const CacheStore * GetCacheStore() const
Definition: cache.h:1101
void SetArcs()
Definition: cache.h:175
void AddArc(State *state, const Arc &arc)
Definition: cache.h:480
size_t GetCacheLimit() const
Definition: cache.h:1109
void DeleteArcs(State *state, size_t n)
Definition: cache.h:376
typename CacheState< A >::Arc Arc
Definition: cache.h:859
constexpr uint8_t Flags() const
Definition: cache.h:1229
DECLARE_bool(fst_default_cache_gc)
~CacheBaseImpl() override
Definition: cache.h:920
void PushArc(Arc &&arc)
Definition: cache.h:166
size_t gc_limit
Definition: cache.h:52
const State * GetState(StateId s) const
Definition: cache.h:687
StateId CountStates() const
Definition: cache.h:632
void AddArc(State *state, const Arc &arc)
Definition: cache.h:366
int * ref_count
Definition: fst.h:497
uint8_t Flags() const
Definition: cache.h:140
size_t NumOutputEpsilons(StateId s) const
Definition: cache.h:1043
typename CacheStore::Arc Arc
Definition: cache.h:1296
void Destroy(ArcIterator< FST > *aiter, MemoryPool< ArcIterator< FST >> *pool)
Definition: fst.h:593
size_t narcs
Definition: fst.h:496
StateId Value() const
Definition: cache.h:638
void DeleteArcs()
Definition: cache.h:190
void DeleteArcs(State *state, size_t n)
Definition: cache.h:490
void AddArc(State *state, const Arc &arc)
Definition: cache.h:613
void Delete()
Definition: cache.h:756
void SetArcs(StateId s)
Definition: cache.h:961
CacheStateIterator(const FST &fst, Impl *impl)
Definition: cache.h:1164
void Next()
Definition: fst.h:540