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