FST  openfst-1.7.1
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  // Returns nullptr if state is not stored.
314  const State *GetState(StateId s) const {
315  return s < state_vec_.size() ? state_vec_[s] : nullptr;
316  }
317 
318  // Creates state if state is not stored.
320  State *state = nullptr;
321  if (s >= state_vec_.size()) {
322  state_vec_.resize(s + 1, nullptr);
323  } else {
324  state = state_vec_[s];
325  }
326  if (!state) {
327  state = new (&state_alloc_) State(arc_alloc_);
328  state_vec_[s] = state;
329  if (cache_gc_) state_list_.push_back(s);
330  }
331  return state;
332  }
333 
334  // Similar to State::AddArc() but updates cache store book-keeping
335  void AddArc(State *state, const Arc &arc) { state->AddArc(arc); }
336 
337  // Similar to State::SetArcs() but updates cache store book-keeping; call
338  // only once.
339  void SetArcs(State *state) { state->SetArcs(); }
340 
341  // Deletes all arcs.
342  void DeleteArcs(State *state) { state->DeleteArcs(); }
343 
344  // Deletes some arcs.
345  void DeleteArcs(State *state, size_t n) { state->DeleteArcs(n); }
346 
347  // Deletes all cached states.
348  void Clear() {
349  for (StateId s = 0; s < state_vec_.size(); ++s) {
350  State::Destroy(state_vec_[s], &state_alloc_);
351  }
352  state_vec_.clear();
353  state_list_.clear();
354  }
355 
357  return std::count_if(state_vec_.begin(), state_vec_.end(),
358  [](const State *s) { return s != nullptr; });
359  }
360 
361  // Iterates over cached states (in an arbitrary order); only works if GC is
362  // enabled (o.w. avoiding state_list_ overhead).
363  bool Done() const { return iter_ == state_list_.end(); }
364 
365  StateId Value() const { return *iter_; }
366 
367  void Next() { ++iter_; }
368 
369  void Reset() { iter_ = state_list_.begin(); }
370 
371  // Deletes current state and advances to next.
372  void Delete() {
373  State::Destroy(state_vec_[*iter_], &state_alloc_);
374  state_vec_[*iter_] = nullptr;
375  state_list_.erase(iter_++);
376  }
377 
378  private:
379  void CopyStates(const VectorCacheStore<State> &store) {
380  Clear();
381  state_vec_.reserve(store.state_vec_.size());
382  for (StateId s = 0; s < store.state_vec_.size(); ++s) {
383  State *state = nullptr;
384  const auto *store_state = store.state_vec_[s];
385  if (store_state) {
386  state = new (&state_alloc_) State(*store_state, arc_alloc_);
387  if (cache_gc_) state_list_.push_back(s);
388  }
389  state_vec_.push_back(state);
390  }
391  }
392 
393  bool cache_gc_; // Supports iteration when true.
394  std::vector<State *> state_vec_; // Vector of states (or null).
395  StateList state_list_; // List of states.
396  typename StateList::iterator iter_; // State list iterator.
397  typename State::StateAllocator state_alloc_; // For state allocation.
398  typename State::ArcAllocator arc_alloc_; // For arc allocation.
399 };
400 
401 // This class uses a hash map from state IDs to pointers to cached states.
402 template <class S>
404  public:
405  using State = S;
406  using Arc = typename State::Arc;
407  using StateId = typename Arc::StateId;
408 
409  using StateMap =
410  std::unordered_map<StateId, State *, std::hash<StateId>,
411  std::equal_to<StateId>,
413 
414  // Required constructors/assignment operators.
415  explicit HashCacheStore(const CacheOptions &opts) {
416  Clear();
417  Reset();
418  }
419 
421  CopyStates(store);
422  Reset();
423  }
424 
425  ~HashCacheStore() { Clear(); }
426 
428  if (this != &store) {
429  CopyStates(store);
430  Reset();
431  }
432  return *this;
433  }
434 
435  // Returns nullptr if state is not stored.
436  const State *GetState(StateId s) const {
437  const auto it = state_map_.find(s);
438  return it != state_map_.end() ? it->second : nullptr;
439  }
440 
441  // Creates state if state is not stored.
443  auto *&state = state_map_[s];
444  if (!state) state = new (&state_alloc_) State(arc_alloc_);
445  return state;
446  }
447 
448  // Similar to State::AddArc() but updates cache store book-keeping.
449  void AddArc(State *state, const Arc &arc) { state->AddArc(arc); }
450 
451  // Similar to State::SetArcs() but updates internal cache size; call only
452  // once.
453  void SetArcs(State *state) { state->SetArcs(); }
454 
455  // Deletes all arcs.
456  void DeleteArcs(State *state) { state->DeleteArcs(); }
457 
458  // Deletes some arcs.
459  void DeleteArcs(State *state, size_t n) { state->DeleteArcs(n); }
460 
461  // Deletes all cached states.
462  void Clear() {
463  for (auto it = state_map_.begin(); it != state_map_.end(); ++it) {
464  State::Destroy(it->second, &state_alloc_);
465  }
466  state_map_.clear();
467  }
468 
469  StateId CountStates() const { return state_map_.size(); }
470 
471  // Iterates over cached states (in an arbitrary order).
472  bool Done() const { return iter_ == state_map_.end(); }
473 
474  StateId Value() const { return iter_->first; }
475 
476  void Next() { ++iter_; }
477 
478  void Reset() { iter_ = state_map_.begin(); }
479 
480  // Deletes current state and advances to next.
481  void Delete() {
482  State::Destroy(iter_->second, &state_alloc_);
483  state_map_.erase(iter_++);
484  }
485 
486  private:
487  void CopyStates(const HashCacheStore<State> &store) {
488  Clear();
489  for (auto it = store.state_map_.begin(); it != store.state_map_.end();
490  ++it) {
491  state_map_[it->first] =
492  new (&state_alloc_) State(*it->second, arc_alloc_);
493  }
494  }
495 
496  StateMap state_map_; // Map from state ID to state.
497  typename StateMap::iterator iter_; // State map iterator.
498  typename State::StateAllocator state_alloc_; // For state allocation.
499  typename State::ArcAllocator arc_alloc_; // For arc allocation.
500 };
501 
502 // Garbage-colllection cache stores.
503 
504 // This class implements a simple garbage collection scheme when
505 // 'opts.gc_limit = 0'. In particular, the first cached state is reused for each
506 // new state so long as the reference count is zero on the to-be-reused state.
507 // Otherwise, the full underlying store is used. The caller can increment the
508 // reference count to inhibit the GC of in-use states (e.g., in an ArcIterator).
509 //
510 // The typical use case for this optimization is when a single pass over a
511 // cached
512 // FST is performed with only one-state expanded at a time.
513 template <class CacheStore>
515  public:
516  using State = typename CacheStore::State;
517  using Arc = typename State::Arc;
518  using StateId = typename Arc::StateId;
519 
520  // Required constructors/assignment operators.
521  explicit FirstCacheStore(const CacheOptions &opts)
522  : store_(opts),
523  cache_gc_(opts.gc_limit == 0), // opts.gc ignored historically.
524  cache_first_state_id_(kNoStateId),
525  cache_first_state_(nullptr) {}
526 
528  : store_(store.store_),
529  cache_gc_(store.cache_gc_),
530  cache_first_state_id_(store.cache_first_state_id_),
531  cache_first_state_(store.cache_first_state_id_ != kNoStateId
532  ? store_.GetMutableState(0)
533  : nullptr) {}
534 
536  const FirstCacheStore<CacheStore> &store) {
537  if (this != &store) {
538  store_ = store.store_;
539  cache_gc_ = store.cache_gc_;
540  cache_first_state_id_ = store.cache_first_state_id_;
541  cache_first_state_ = store.cache_first_state_id_ != kNoStateId
542  ? store_.GetMutableState(0)
543  : nullptr;
544  }
545  return *this;
546  }
547 
548  // Returns nullptr if state is not stored.
549  const State *GetState(StateId s) const {
550  // store_ state 0 may hold first cached state; the rest are shifted by 1.
551  return s == cache_first_state_id_ ? cache_first_state_
552  : store_.GetState(s + 1);
553  }
554 
555  // Creates state if state is not stored.
557  // store_ state 0 used to hold first cached state; the rest are shifted by
558  // 1.
559  if (cache_first_state_id_ == s) {
560  return cache_first_state_; // Request for first cached state.
561  }
562  if (cache_gc_) {
563  if (cache_first_state_id_ == kNoStateId) {
564  cache_first_state_id_ = s; // Sets first cached state.
565  cache_first_state_ = store_.GetMutableState(0);
566  cache_first_state_->SetFlags(kCacheInit, kCacheInit);
567  cache_first_state_->ReserveArcs(2 * kAllocSize);
568  return cache_first_state_;
569  } else if (cache_first_state_->RefCount() == 0) {
570  cache_first_state_id_ = s; // Updates first cached state.
571  cache_first_state_->Reset();
572  cache_first_state_->SetFlags(kCacheInit, kCacheInit);
573  return cache_first_state_;
574  } else { // Keeps first cached state.
575  cache_first_state_->SetFlags(0, kCacheInit); // Clears initialized bit.
576  cache_gc_ = false; // Disables GC.
577  }
578  }
579  auto *state = store_.GetMutableState(s + 1);
580  return state;
581  }
582 
583  // Similar to State::AddArc() but updates cache store book-keeping.
584  void AddArc(State *state, const Arc &arc) { store_.AddArc(state, arc); }
585 
586  // Similar to State::SetArcs() but updates internal cache size; call only
587  // once.
588  void SetArcs(State *state) { store_.SetArcs(state); }
589 
590  // Deletes all arcs
591  void DeleteArcs(State *state) { store_.DeleteArcs(state); }
592 
593  // Deletes some arcs
594  void DeleteArcs(State *state, size_t n) { store_.DeleteArcs(state, n); }
595 
596  // Deletes all cached states
597  void Clear() {
598  store_.Clear();
599  cache_first_state_id_ = kNoStateId;
600  cache_first_state_ = nullptr;
601  }
602 
603  StateId CountStates() const { return store_.CountStates(); }
604 
605  // Iterates over cached states (in an arbitrary order). Only needed if GC is
606  // enabled.
607  bool Done() const { return store_.Done(); }
608 
609  StateId Value() const {
610  // store_ state 0 may hold first cached state; rest shifted + 1.
611  const auto s = store_.Value();
612  return s ? s - 1 : cache_first_state_id_;
613  }
614 
615  void Next() { store_.Next(); }
616 
617  void Reset() { store_.Reset(); }
618 
619  // Deletes current state and advances to next.
620  void Delete() {
621  if (Value() == cache_first_state_id_) {
622  cache_first_state_id_ = kNoStateId;
623  cache_first_state_ = nullptr;
624  }
625  store_.Delete();
626  }
627 
628  private:
629  CacheStore store_; // Underlying store.
630  bool cache_gc_; // GC enabled.
631  StateId cache_first_state_id_; // First cached state ID.
632  State *cache_first_state_; // First cached state.
633 };
634 
635 // This class implements mark-sweep garbage collection on an underlying cache
636 // store. If GC is enabled, garbage collection of states is performed in a
637 // rough approximation of LRU order once when 'gc_limit' bytes is reached. The
638 // caller can increment the reference count to inhibit the GC of in-use state
639 // (e.g., in an ArcIterator). With GC enabled, the 'gc_limit' parameter allows
640 // the caller to trade-off time vs. space.
641 template <class CacheStore>
643  public:
644  using State = typename CacheStore::State;
645  using Arc = typename State::Arc;
646  using StateId = typename Arc::StateId;
647 
648  // Required constructors/assignment operators.
649  explicit GCCacheStore(const CacheOptions &opts)
650  : store_(opts),
651  cache_gc_request_(opts.gc),
652  cache_limit_(opts.gc_limit > kMinCacheLimit ? opts.gc_limit
653  : kMinCacheLimit),
654  cache_gc_(false),
655  cache_size_(0) {}
656 
657  // Returns 0 if state is not stored.
658  const State *GetState(StateId s) const { return store_.GetState(s); }
659 
660  // Creates state if state is not stored
662  auto *state = store_.GetMutableState(s);
663  if (cache_gc_request_ && !(state->Flags() & kCacheInit)) {
664  state->SetFlags(kCacheInit, kCacheInit);
665  cache_size_ += sizeof(State) + state->NumArcs() * sizeof(Arc);
666  // GC is enabled once an uninited state (from underlying store) is seen.
667  cache_gc_ = true;
668  if (cache_size_ > cache_limit_) GC(state, false);
669  }
670  return state;
671  }
672 
673  // Similar to State::AddArc() but updates cache store book-keeping.
674  void AddArc(State *state, const Arc &arc) {
675  store_.AddArc(state, arc);
676  if (cache_gc_ && (state->Flags() & kCacheInit)) {
677  cache_size_ += sizeof(Arc);
678  if (cache_size_ > cache_limit_) GC(state, false);
679  }
680  }
681 
682  // Similar to State::SetArcs() but updates internal cache size; call only
683  // once.
684  void SetArcs(State *state) {
685  store_.SetArcs(state);
686  if (cache_gc_ && (state->Flags() & kCacheInit)) {
687  cache_size_ += state->NumArcs() * sizeof(Arc);
688  if (cache_size_ > cache_limit_) GC(state, false);
689  }
690  }
691 
692  // Deletes all arcs.
693  void DeleteArcs(State *state) {
694  if (cache_gc_ && (state->Flags() & kCacheInit)) {
695  cache_size_ -= state->NumArcs() * sizeof(Arc);
696  }
697  store_.DeleteArcs(state);
698  }
699 
700  // Deletes some arcs.
701  void DeleteArcs(State *state, size_t n) {
702  if (cache_gc_ && (state->Flags() & kCacheInit)) {
703  cache_size_ -= n * sizeof(Arc);
704  }
705  store_.DeleteArcs(state, n);
706  }
707 
708  // Deletes all cached states.
709  void Clear() {
710  store_.Clear();
711  cache_size_ = 0;
712  }
713 
714  StateId CountStates() const { return store_.CountStates(); }
715 
716  // Iterates over cached states (in an arbitrary order); only needed if GC is
717  // enabled.
718  bool Done() const { return store_.Done(); }
719 
720  StateId Value() const { return store_.Value(); }
721 
722  void Next() { store_.Next(); }
723 
724  void Reset() { store_.Reset(); }
725 
726  // Deletes current state and advances to next.
727  void Delete() {
728  if (cache_gc_) {
729  const auto *state = store_.GetState(Value());
730  if (state->Flags() & kCacheInit) {
731  cache_size_ -= sizeof(State) + state->NumArcs() * sizeof(Arc);
732  }
733  }
734  store_.Delete();
735  }
736 
737  // Removes from the cache store (not referenced-counted and not the current)
738  // states that have not been accessed since the last GC until at most
739  // cache_fraction * cache_limit_ bytes are cached. If that fails to free
740  // enough, attempts to uncaching recently visited states as well. If still
741  // unable to free enough memory, then widens cache_limit_.
742  void GC(const State *current, bool free_recent, float cache_fraction = 0.666);
743 
744  // Returns the current cache size in bytes or 0 if GC is disabled.
745  size_t CacheSize() const { return cache_size_; }
746 
747  // Returns the cache limit in bytes.
748  size_t CacheLimit() const { return cache_limit_; }
749 
750  private:
751  static constexpr size_t kMinCacheLimit = 8096; // Minimum cache limit.
752 
753  CacheStore store_; // Underlying store.
754  bool cache_gc_request_; // GC requested but possibly not yet enabled.
755  size_t cache_limit_; // Number of bytes allowed before GC.
756  bool cache_gc_; // GC enabled
757  size_t cache_size_; // Number of bytes cached.
758 };
759 
760 template <class CacheStore>
761 void GCCacheStore<CacheStore>::GC(const State *current, bool free_recent,
762  float cache_fraction) {
763  if (!cache_gc_) return;
764  VLOG(2) << "GCCacheStore: Enter GC: object = "
765  << "(" << this << "), free recently cached = " << free_recent
766  << ", cache size = " << cache_size_
767  << ", cache frac = " << cache_fraction
768  << ", cache limit = " << cache_limit_ << "\n";
769  size_t cache_target = cache_fraction * cache_limit_;
770  store_.Reset();
771  while (!store_.Done()) {
772  auto *state = store_.GetMutableState(store_.Value());
773  if (cache_size_ > cache_target && state->RefCount() == 0 &&
774  (free_recent || !(state->Flags() & kCacheRecent)) && state != current) {
775  if (state->Flags() & kCacheInit) {
776  size_t size = sizeof(State) + state->NumArcs() * sizeof(Arc);
777  if (size < cache_size_) {
778  cache_size_ -= size;
779  }
780  }
781  store_.Delete();
782  } else {
783  state->SetFlags(0, kCacheRecent);
784  store_.Next();
785  }
786  }
787  if (!free_recent && cache_size_ > cache_target) { // Recurses on recent.
788  GC(current, true, cache_fraction);
789  } else if (cache_target > 0) { // Widens cache limit.
790  while (cache_size_ > cache_target) {
791  cache_limit_ *= 2;
792  cache_target *= 2;
793  }
794  } else if (cache_size_ > 0) {
795  FSTERROR() << "GCCacheStore:GC: Unable to free all cached states";
796  }
797  VLOG(2) << "GCCacheStore: Exit GC: object = "
798  << "(" << this << "), free recently cached = " << free_recent
799  << ", cache size = " << cache_size_
800  << ", cache frac = " << cache_fraction
801  << ", cache limit = " << cache_limit_ << "\n";
802 }
803 
804 template <class CacheStore>
806 
807 // This class is the default cache state and store used by CacheBaseImpl.
808 // It uses VectorCacheStore for storage decorated by FirstCacheStore
809 // and GCCacheStore to do (optional) garbage collection.
810 template <class Arc>
812  : public GCCacheStore<FirstCacheStore<VectorCacheStore<CacheState<Arc>>>> {
813  public:
814  explicit DefaultCacheStore(const CacheOptions &opts)
816  }
817 };
818 
819 namespace internal {
820 
821 // This class is used to cache FST elements stored in states of type State
822 // (see CacheState) with the flags used to indicate what has been cached. Use
823 // HasStart(), HasFinal(), and HasArcs() to determine if cached and SetStart(),
824 // SetFinal(), AddArc(), (or PushArc() and SetArcs()) to cache. Note that you
825 // must set the final weight even if the state is non-final to mark it as
826 // cached. The state storage method and any garbage collection policy are
827 // determined by the cache store. If the store is passed in with the options,
828 // CacheBaseImpl takes ownership.
829 template <class State,
830  class CacheStore = DefaultCacheStore<typename State::Arc>>
831 class CacheBaseImpl : public FstImpl<typename State::Arc> {
832  public:
833  using Arc = typename State::Arc;
834  using StateId = typename Arc::StateId;
835  using Weight = typename Arc::Weight;
836 
837  using Store = CacheStore;
838 
839  using FstImpl<Arc>::Type;
841 
842  explicit CacheBaseImpl(const CacheOptions &opts = CacheOptions())
843  : has_start_(false),
844  cache_start_(kNoStateId),
845  nknown_states_(0),
846  min_unexpanded_state_id_(0),
847  max_expanded_state_id_(-1),
848  cache_gc_(opts.gc),
849  cache_limit_(opts.gc_limit),
850  cache_store_(new CacheStore(opts)),
851  new_cache_store_(true),
852  own_cache_store_(true) {}
853 
855  : has_start_(false),
856  cache_start_(kNoStateId),
857  nknown_states_(0),
858  min_unexpanded_state_id_(0),
859  max_expanded_state_id_(-1),
860  cache_gc_(opts.gc),
861  cache_limit_(opts.gc_limit),
862  cache_store_(opts.store ? opts.store : new CacheStore(CacheOptions(
863  opts.gc, opts.gc_limit))),
864  new_cache_store_(!opts.store),
865  own_cache_store_(opts.store ? opts.own_store : true) {}
866 
867  // Preserve gc parameters. If preserve_cache is true, also preserves
868  // cache data.
870  bool preserve_cache = false)
871  : FstImpl<Arc>(),
872  has_start_(false),
873  cache_start_(kNoStateId),
874  nknown_states_(0),
875  min_unexpanded_state_id_(0),
876  max_expanded_state_id_(-1),
877  cache_gc_(impl.cache_gc_),
878  cache_limit_(impl.cache_limit_),
879  cache_store_(new CacheStore(CacheOptions(cache_gc_, cache_limit_))),
880  new_cache_store_(impl.new_cache_store_ || !preserve_cache),
881  own_cache_store_(true) {
882  if (preserve_cache) {
883  *cache_store_ = *impl.cache_store_;
884  has_start_ = impl.has_start_;
885  cache_start_ = impl.cache_start_;
886  nknown_states_ = impl.nknown_states_;
887  expanded_states_ = impl.expanded_states_;
888  min_unexpanded_state_id_ = impl.min_unexpanded_state_id_;
889  max_expanded_state_id_ = impl.max_expanded_state_id_;
890  }
891  }
892 
893  ~CacheBaseImpl() override { if (own_cache_store_) delete cache_store_; }
894 
895  void SetStart(StateId s) {
896  cache_start_ = s;
897  has_start_ = true;
898  if (s >= nknown_states_) nknown_states_ = s + 1;
899  }
900 
901  void SetFinal(StateId s, Weight weight) {
902  auto *state = cache_store_->GetMutableState(s);
903  state->SetFinal(std::move(weight));
904  static constexpr auto flags = kCacheFinal | kCacheRecent;
905  state->SetFlags(flags, flags);
906  }
907 
908 // Disabled to ensure PushArc not AddArc is used in existing code
909 // TODO(sorenj): re-enable for backing store
910 #if 0
911  // AddArc adds a single arc to a state and does incremental cache
912  // book-keeping. For efficiency, prefer PushArc and SetArcs below
913  // when possible.
914  void AddArc(StateId s, const Arc &arc) {
915  auto *state = cache_store_->GetMutableState(s);
916  cache_store_->AddArc(state, arc);
917  if (arc.nextstate >= nknown_states_)
918  nknown_states_ = arc.nextstate + 1;
919  SetExpandedState(s);
920  static constexpr auto flags = kCacheArcs | kCacheRecent;
921  state->SetFlags(flags, flags);
922  }
923 #endif
924 
925  // Adds a single arc to a state but delays cache book-keeping. SetArcs must
926  // be called when all PushArc and EmplaceArc calls at a state are complete.
927  // Do not mix with calls to AddArc.
928  void PushArc(StateId s, const Arc &arc) {
929  auto *state = cache_store_->GetMutableState(s);
930  state->PushArc(arc);
931  }
932 
933  void PushArc(StateId s, Arc &&arc) {
934  auto *state = cache_store_->GetMutableState(s);
935  state->PushArc(std::move(arc));
936  }
937 
938  // Adds a single arc to a state but delays cache book-keeping. SetArcs must
939  // be called when all PushArc and EmplaceArc calls at a state are complete.
940  // Do not mix with calls to AddArc.
941  template <class... T>
942  void EmplaceArc(StateId s, T &&... ctor_args) {
943  auto *state = cache_store_->GetMutableState(s);
944  state->EmplaceArc(std::forward<T>(ctor_args)...);
945  }
946 
947  // Marks arcs of a state as cached and does cache book-keeping after all
948  // calls to PushArc have been completed. Do not mix with calls to AddArc.
949  void SetArcs(StateId s) {
950  auto *state = cache_store_->GetMutableState(s);
951  cache_store_->SetArcs(state);
952  const auto narcs = state->NumArcs();
953  for (size_t a = 0; a < narcs; ++a) {
954  const auto &arc = state->GetArc(a);
955  if (arc.nextstate >= nknown_states_) nknown_states_ = arc.nextstate + 1;
956  }
957  SetExpandedState(s);
958  static constexpr auto flags = kCacheArcs | kCacheRecent;
959  state->SetFlags(flags, flags);
960  }
961 
962  void ReserveArcs(StateId s, size_t n) {
963  auto *state = cache_store_->GetMutableState(s);
964  state->ReserveArcs(n);
965  }
966 
967  void DeleteArcs(StateId s) {
968  auto *state = cache_store_->GetMutableState(s);
969  cache_store_->DeleteArcs(state);
970  }
971 
972  void DeleteArcs(StateId s, size_t n) {
973  auto *state = cache_store_->GetMutableState(s);
974  cache_store_->DeleteArcs(state, n);
975  }
976 
977  void Clear() {
978  nknown_states_ = 0;
979  min_unexpanded_state_id_ = 0;
980  max_expanded_state_id_ = -1;
981  has_start_ = false;
982  cache_start_ = kNoStateId;
983  cache_store_->Clear();
984  }
985 
986  // Is the start state cached?
987  bool HasStart() const {
988  if (!has_start_ && Properties(kError)) has_start_ = true;
989  return has_start_;
990  }
991 
992  // Is the final weight of the state cached?
993  bool HasFinal(StateId s) const {
994  const auto *state = cache_store_->GetState(s);
995  if (state && state->Flags() & kCacheFinal) {
996  state->SetFlags(kCacheRecent, kCacheRecent);
997  return true;
998  } else {
999  return false;
1000  }
1001  }
1002 
1003  // Are arcs of the state cached?
1004  bool HasArcs(StateId s) const {
1005  const auto *state = cache_store_->GetState(s);
1006  if (state && state->Flags() & kCacheArcs) {
1007  state->SetFlags(kCacheRecent, kCacheRecent);
1008  return true;
1009  } else {
1010  return false;
1011  }
1012  }
1013 
1014  StateId Start() const { return cache_start_; }
1015 
1016  Weight Final(StateId s) const {
1017  const auto *state = cache_store_->GetState(s);
1018  return state->Final();
1019  }
1020 
1021  size_t NumArcs(StateId s) const {
1022  const auto *state = cache_store_->GetState(s);
1023  return state->NumArcs();
1024  }
1025 
1026  size_t NumInputEpsilons(StateId s) const {
1027  const auto *state = cache_store_->GetState(s);
1028  return state->NumInputEpsilons();
1029  }
1030 
1031  size_t NumOutputEpsilons(StateId s) const {
1032  const auto *state = cache_store_->GetState(s);
1033  return state->NumOutputEpsilons();
1034  }
1035 
1036  // Provides information needed for generic arc iterator.
1038  const auto *state = cache_store_->GetState(s);
1039  data->base = nullptr;
1040  data->narcs = state->NumArcs();
1041  data->arcs = state->Arcs();
1042  data->ref_count = state->MutableRefCount();
1043  state->IncrRefCount();
1044  }
1045 
1046  // Number of known states.
1047  StateId NumKnownStates() const { return nknown_states_; }
1048 
1049  // Updates number of known states, taking into account the passed state ID.
1051  if (s >= nknown_states_) nknown_states_ = s + 1;
1052  }
1053 
1054  // Finds the mininum never-expanded state ID.
1056  while (min_unexpanded_state_id_ <= max_expanded_state_id_ &&
1057  ExpandedState(min_unexpanded_state_id_)) {
1058  ++min_unexpanded_state_id_;
1059  }
1060  return min_unexpanded_state_id_;
1061  }
1062 
1063  // Returns maximum ever-expanded state ID.
1064  StateId MaxExpandedState() const { return max_expanded_state_id_; }
1065 
1067  if (s > max_expanded_state_id_) max_expanded_state_id_ = s;
1068  if (s < min_unexpanded_state_id_) return;
1069  if (s == min_unexpanded_state_id_) ++min_unexpanded_state_id_;
1070  if (cache_gc_ || cache_limit_ == 0) {
1071  if (expanded_states_.size() <= s) expanded_states_.resize(s + 1, false);
1072  expanded_states_[s] = true;
1073  }
1074  }
1075 
1076  bool ExpandedState(StateId s) const {
1077  if (cache_gc_ || cache_limit_ == 0) {
1078  return expanded_states_[s];
1079  } else if (new_cache_store_) {
1080  return cache_store_->GetState(s) != nullptr;
1081  } else {
1082  // If the cache was not created by this class, then the cached state needs
1083  // to be inspected to update nknown_states_.
1084  return false;
1085  }
1086  }
1087 
1088  const CacheStore *GetCacheStore() const { return cache_store_; }
1089 
1090  CacheStore *GetCacheStore() { return cache_store_; }
1091 
1092  // Caching on/off switch, limit and size accessors.
1093 
1094  bool GetCacheGc() const { return cache_gc_; }
1095 
1096  size_t GetCacheLimit() const { return cache_limit_; }
1097 
1098  private:
1099  mutable bool has_start_; // Is the start state cached?
1100  StateId cache_start_; // ID of start state.
1101  StateId nknown_states_; // Number of known states.
1102  std::vector<bool> expanded_states_; // States that have been expanded.
1103  mutable StateId min_unexpanded_state_id_; // Minimum never-expanded state ID
1104  mutable StateId max_expanded_state_id_; // Maximum ever-expanded state ID
1105  bool cache_gc_; // GC enabled.
1106  size_t cache_limit_; // Number of bytes allowed before GC.
1107  CacheStore *cache_store_; // The store of cached states.
1108  bool new_cache_store_; // Was the store was created by class?
1109  bool own_cache_store_; // Is the store owned by class?
1110 
1111  CacheBaseImpl &operator=(const CacheBaseImpl &impl) = delete;
1112 };
1113 
1114 // A CacheBaseImpl with the default cache state type.
1115 template <class Arc>
1116 class CacheImpl : public CacheBaseImpl<CacheState<Arc>> {
1117  public:
1119 
1121 
1122  explicit CacheImpl(const CacheOptions &opts)
1123  : CacheBaseImpl<CacheState<Arc>>(opts) {}
1124 
1125  CacheImpl(const CacheImpl<Arc> &impl, bool preserve_cache = false)
1126  : CacheBaseImpl<State>(impl, preserve_cache) {}
1127 
1128  private:
1129  CacheImpl &operator=(const CacheImpl &impl) = delete;
1130 };
1131 
1132 } // namespace internal
1133 
1134 // Use this to make a state iterator for a CacheBaseImpl-derived FST, which must
1135 // have Arc and Store types defined. Note this iterator only returns those
1136 // states reachable from the initial state, so consider implementing a
1137 // class-specific one.
1138 //
1139 // This class may be derived from.
1140 template <class FST>
1141 class CacheStateIterator : public StateIteratorBase<typename FST::Arc> {
1142  public:
1143  using Arc = typename FST::Arc;
1144  using StateId = typename Arc::StateId;
1145  using Weight = typename Arc::Weight;
1146 
1147  using Store = typename FST::Store;
1148  using State = typename Store::State;
1150 
1151  CacheStateIterator(const FST &fst, Impl *impl)
1152  : fst_(fst), impl_(impl), s_(0) {
1153  fst_.Start(); // Forces start state.
1154  }
1155 
1156  bool Done() const final {
1157  if (s_ < impl_->NumKnownStates()) return false;
1158  for (StateId u = impl_->MinUnexpandedState(); u < impl_->NumKnownStates();
1159  u = impl_->MinUnexpandedState()) {
1160  // Forces state expansion.
1161  ArcIterator<FST> aiter(fst_, u);
1162  aiter.SetFlags(kArcValueFlags, kArcValueFlags | kArcNoCache);
1163  for (; !aiter.Done(); aiter.Next()) {
1164  impl_->UpdateNumKnownStates(aiter.Value().nextstate);
1165  }
1166  impl_->SetExpandedState(u);
1167  if (s_ < impl_->NumKnownStates()) return false;
1168  }
1169  return true;
1170  }
1171 
1172  StateId Value() const final { return s_; }
1173 
1174  void Next() final { ++s_; }
1175 
1176  void Reset() final { s_ = 0; }
1177 
1178  private:
1179  const FST &fst_;
1180  Impl *impl_;
1181  StateId s_;
1182 };
1183 
1184 // Used to make an arc iterator for a CacheBaseImpl-derived FST, which must
1185 // have Arc and State types defined.
1186 template <class FST>
1188  public:
1189  using Arc = typename FST::Arc;
1190  using StateId = typename Arc::StateId;
1191  using Weight = typename Arc::Weight;
1192 
1193  using Store = typename FST::Store;
1194  using State = typename Store::State;
1196 
1197  CacheArcIterator(Impl *impl, StateId s) : i_(0) {
1198  state_ = impl->GetCacheStore()->GetMutableState(s);
1199  state_->IncrRefCount();
1200  }
1201 
1202  ~CacheArcIterator() { state_->DecrRefCount(); }
1203 
1204  bool Done() const { return i_ >= state_->NumArcs(); }
1205 
1206  const Arc &Value() const { return state_->GetArc(i_); }
1207 
1208  void Next() { ++i_; }
1209 
1210  size_t Position() const { return i_; }
1211 
1212  void Reset() { i_ = 0; }
1213 
1214  void Seek(size_t a) { i_ = a; }
1215 
1216  constexpr uint32 Flags() const { return kArcValueFlags; }
1217 
1218  void SetFlags(uint32 flags, uint32 mask) {}
1219 
1220  private:
1221  const State *state_;
1222  size_t i_;
1223 
1224  CacheArcIterator(const CacheArcIterator &) = delete;
1225  CacheArcIterator &operator=(const CacheArcIterator &) = delete;
1226 };
1227 
1228 // Use this to make a mutable arc iterator for a CacheBaseImpl-derived FST,
1229 // which must have types Arc and Store defined.
1230 template <class FST>
1232  : public MutableArcIteratorBase<typename FST::Arc> {
1233  public:
1234  using Arc = typename FST::Arc;
1235  using StateId = typename Arc::StateId;
1236  using Weight = typename Arc::Weight;
1237 
1238  using Store = typename FST::Store;
1239  using State = typename Store::State;
1241 
1242  // User must call MutateCheck() in the constructor.
1243  CacheMutableArcIterator(Impl *impl, StateId s) : i_(0), s_(s), impl_(impl) {
1244  state_ = impl_->GetCacheStore()->GetMutableState(s_);
1245  state_->IncrRefCount();
1246  }
1247 
1248  ~CacheMutableArcIterator() override { state_->DecrRefCount(); }
1249 
1250  bool Done() const final { return i_ >= state_->NumArcs(); }
1251 
1252  const Arc &Value() const final { return state_->GetArc(i_); }
1253 
1254  void Next() final { ++i_; }
1255 
1256  size_t Position() const final { return i_; }
1257 
1258  void Reset() final { i_ = 0; }
1259 
1260  void Seek(size_t a) final { i_ = a; }
1261 
1262  void SetValue(const Arc &arc) final { state_->SetArc(arc, i_); }
1263 
1264  uint32 Flags() const final { return kArcValueFlags; }
1265 
1266  void SetFlags(uint32, uint32) final {}
1267 
1268  private:
1269  size_t i_;
1270  StateId s_;
1271  Impl *impl_;
1272  State *state_;
1273 
1275  CacheMutableArcIterator &operator=(const CacheMutableArcIterator &) = delete;
1276 };
1277 
1278 // Wrap existing CacheStore implementation to use with ExpanderFst.
1279 template <class CacheStore>
1281  public:
1282  using State = typename CacheStore::State;
1283  using Arc = typename CacheStore::Arc;
1284  using StateId = typename Arc::StateId;
1285  using Weight = typename Arc::Weight;
1286 
1288  : store_(opts) {}
1289 
1290  template <class Expander>
1291  State *FindOrExpand(Expander &expander, StateId s) { // NOLINT
1292  auto *state = store_.GetMutableState(s);
1293  if (state->Flags()) {
1294  state->SetFlags(kCacheRecent, kCacheRecent);
1295  } else {
1296  StateBuilder builder(state);
1297  expander.Expand(s, &builder);
1298  state->SetFlags(kCacheFlags, kCacheFlags);
1299  store_.SetArcs(state);
1300  }
1301  return state;
1302  }
1303 
1304  private:
1305  CacheStore store_;
1306 
1307  struct StateBuilder {
1308  State *state;
1309 
1310  explicit StateBuilder(State *state_) : state(state_) {}
1311 
1312  void AddArc(const Arc &arc) { state->PushArc(arc); }
1313 
1314  void AddArc(Arc &&arc) { state->PushArc(std::move(arc)); }
1315 
1316  void SetFinal(Weight weight) { state->SetFinal(std::move(weight)); }
1317  };
1318 };
1319 
1320 } // namespace fst
1321 
1322 #endif // FST_CACHE_H_
void GC(const State *current, bool free_recent, float cache_fraction=0.666)
Definition: cache.h:761
void SetFinal(StateId s, Weight weight)
Definition: cache.h:901
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:1214
size_t CacheLimit() const
Definition: cache.h:748
bool Done() const
Definition: cache.h:607
State * GetMutableState(StateId s)
Definition: cache.h:556
CacheImpl(const CacheOptions &opts)
Definition: cache.h:1122
CacheState(const ArcAllocator &alloc)
Definition: cache.h:76
size_t NumInputEpsilons(StateId s) const
Definition: cache.h:1026
HashCacheStore(const HashCacheStore< S > &store)
Definition: cache.h:420
const Arc & Value() const
Definition: cache.h:1206
void EmplaceArc(T &&...ctor_args)
Definition: cache.h:143
bool HasFinal(StateId s) const
Definition: cache.h:993
uint32 Flags() const final
Definition: cache.h:1264
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:649
bool ExpandedState(StateId s) const
Definition: cache.h:1076
constexpr uint32 kCacheFinal
Definition: cache.h:55
void PushArc(const Arc &arc)
Definition: cache.h:137
StateId CountStates() const
Definition: cache.h:714
StateId Start() const
Definition: cache.h:1014
size_t NumOutputEpsilons() const
Definition: cache.h:105
DECLARE_int64(fst_default_cache_gc_limit)
void Reset() final
Definition: cache.h:1176
typename Arc::StateId StateId
Definition: cache.h:68
typename SynchronizeFst< Arc >::Store Store
Definition: cache.h:1193
M ArcAllocator
Definition: cache.h:71
typename Arc::StateId StateId
Definition: cache.h:1235
void SetFlags(uint32, uint32) final
Definition: cache.h:1266
void UpdateNumKnownStates(StateId s)
Definition: cache.h:1050
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:82
~CacheMutableArcIterator() override
Definition: cache.h:1248
void SetArcs(State *state)
Definition: cache.h:684
StateId Value() const
Definition: cache.h:474
void SetFinal(Weight weight)
Definition: cache.h:120
FirstCacheStore< CacheStore > & operator=(const FirstCacheStore< CacheStore > &store)
Definition: cache.h:535
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:1282
void AddArc(State *state, const Arc &arc)
Definition: cache.h:674
void Next()
Definition: cache.h:722
StateId CountStates() const
Definition: cache.h:469
typename SynchronizeFst< Arc >::Arc Arc
Definition: cache.h:1143
bool Done() const
Definition: cache.h:1204
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:1291
std::unordered_map< StateId, State *, std::hash< StateId >, std::equal_to< StateId >, PoolAllocator< std::pair< const StateId, State * >>> StateMap
Definition: cache.h:412
bool Done() const
Definition: cache.h:718
CacheStore * store
Definition: cache.h:42
typename Arc::Weight Weight
Definition: cache.h:1236
typename Store::State State
Definition: cache.h:1239
State * GetMutableState(StateId s)
Definition: cache.h:661
size_t CacheSize() const
Definition: cache.h:745
bool Done() const
Definition: cache.h:363
void SetArcs(State *state)
Definition: cache.h:588
void DeleteArcs(State *state)
Definition: cache.h:591
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:1021
typename SynchronizeFst< Arc >::Store Store
Definition: cache.h:1147
bool GetCacheGc() const
Definition: cache.h:1094
CacheImpl(const CacheImpl< Arc > &impl, bool preserve_cache=false)
Definition: cache.h:1125
#define FSTERROR()
Definition: util.h:35
typename Arc::Weight Weight
Definition: cache.h:1285
CacheBaseImpl(const CacheImplOptions< CacheStore > &opts)
Definition: cache.h:854
typename Arc::StateId StateId
Definition: cache.h:1284
CacheStore * GetCacheStore()
Definition: cache.h:1090
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:549
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:93
typename FST::Arc Arc
Definition: cache.h:1234
State * GetMutableState(StateId s)
Definition: cache.h:319
std::list< StateId, PoolAllocator< StateId >> StateList
Definition: cache.h:289
void DeleteArcs(StateId s, size_t n)
Definition: cache.h:972
typename Arc::StateId StateId
Definition: cache.h:407
void SetArcs(State *state)
Definition: cache.h:453
CacheBaseImpl(const CacheBaseImpl< State, CacheStore > &impl, bool preserve_cache=false)
Definition: cache.h:869
typename State::Arc Arc
Definition: cache.h:406
bool HasStart() const
Definition: cache.h:987
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:644
CacheBaseImpl(const CacheOptions &opts=CacheOptions())
Definition: cache.h:842
void SetFlags(uint32 flags, uint32 mask)
Definition: cache.h:1218
const Arc & Value() const final
Definition: cache.h:1252
size_t Position() const
Definition: cache.h:1210
void SetFlags(uint32 flags, uint32 mask)
Definition: fst.h:541
void ReserveArcs(StateId s, size_t n)
Definition: cache.h:962
FirstCacheStore(const CacheOptions &opts)
Definition: cache.h:521
StateId Value() const final
Definition: cache.h:1172
void DeleteArcs(State *state)
Definition: cache.h:456
const Arc * Arcs() const
Definition: cache.h:112
void Reset()
Definition: cache.h:92
const State * GetState(StateId s) const
Definition: cache.h:314
#define VLOG(level)
Definition: log.h:49
CacheArcIterator(Impl *impl, StateId s)
Definition: cache.h:1197
void Seek(size_t a) final
Definition: cache.h:1260
size_t NumInputEpsilons() const
Definition: cache.h:103
void SetValue(const Arc &arc) final
Definition: cache.h:1262
StateId Value() const
Definition: cache.h:365
void ReserveArcs(size_t n)
Definition: cache.h:122
size_t Position() const final
Definition: cache.h:1256
bool Done() const
Definition: fst.h:499
void DeleteArcs(State *state)
Definition: cache.h:693
void DeleteArcs(State *state, size_t n)
Definition: cache.h:594
StateId MinUnexpandedState() const
Definition: cache.h:1055
void SetArcs(State *state)
Definition: cache.h:339
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const
Definition: cache.h:1037
State * GetMutableState(StateId s)
Definition: cache.h:442
int DecrRefCount() const
Definition: cache.h:187
DefaultCacheStore(const CacheOptions &opts)
Definition: cache.h:814
void Clear()
Definition: cache.h:709
int * MutableRefCount() const
Definition: cache.h:190
void EmplaceArc(StateId s, T &&...ctor_args)
Definition: cache.h:942
bool Done() const final
Definition: cache.h:1250
bool HasArcs(StateId s) const
Definition: cache.h:1004
constexpr uint32 kCacheFlags
Definition: cache.h:59
VectorCacheStore< State > & operator=(const VectorCacheStore< State > &store)
Definition: cache.h:305
bool Done() const
Definition: cache.h:472
void SetStart(StateId s)
Definition: cache.h:895
StateId Value() const
Definition: cache.h:720
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:1064
void PushArc(StateId s, const Arc &arc)
Definition: cache.h:928
HashCacheStore(const CacheOptions &opts)
Definition: cache.h:415
void SetExpandedState(StateId s)
Definition: cache.h:1066
CacheImplOptions(const CacheOptions &opts)
Definition: cache.h:50
typename SynchronizeFst< Arc >::Arc Arc
Definition: cache.h:1189
const State * GetState(StateId s) const
Definition: cache.h:436
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:1243
Weight Final(StateId s) const
Definition: cache.h:1016
StateId NumKnownStates() const
Definition: cache.h:1047
void DeleteArcs(State *state)
Definition: cache.h:342
void Reset()
Definition: cache.h:724
bool Done() const final
Definition: cache.h:1156
const Arc * arcs
Definition: fst.h:462
void DeleteArcs(State *state, size_t n)
Definition: cache.h:701
constexpr uint64 kError
Definition: properties.h:33
constexpr uint32 kCacheInit
Definition: cache.h:57
typename FST::Store Store
Definition: cache.h:1238
ExpanderCacheStore(const CacheOptions &opts=CacheOptions())
Definition: cache.h:1287
FirstCacheStore(const FirstCacheStore< CacheStore > &store)
Definition: cache.h:527
void DeleteArcs(StateId s)
Definition: cache.h:967
typename VectorCacheStore< CacheState< Arc > >::State State
Definition: cache.h:516
int IncrRefCount() const
Definition: cache.h:185
constexpr uint32 Flags() const
Definition: cache.h:1216
void PushArc(StateId s, Arc &&arc)
Definition: cache.h:933
void Next() final
Definition: cache.h:1174
StateId CountStates() const
Definition: cache.h:356
ArcIteratorBase< Arc > * base
Definition: fst.h:461
const CacheStore * GetCacheStore() const
Definition: cache.h:1088
void SetArcs()
Definition: cache.h:148
void AddArc(State *state, const Arc &arc)
Definition: cache.h:449
constexpr uint32 kCacheRecent
Definition: cache.h:58
size_t GetCacheLimit() const
Definition: cache.h:1096
void DeleteArcs(State *state, size_t n)
Definition: cache.h:345
HashCacheStore< State > & operator=(const HashCacheStore< State > &store)
Definition: cache.h:427
typename CacheState< A >::Arc Arc
Definition: cache.h:833
DECLARE_bool(fst_default_cache_gc)
~CacheBaseImpl() override
Definition: cache.h:893
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:658
StateId CountStates() const
Definition: cache.h:603
void AddArc(State *state, const Arc &arc)
Definition: cache.h:335
int * ref_count
Definition: fst.h:464
size_t NumOutputEpsilons(StateId s) const
Definition: cache.h:1031
typename CacheStore::Arc Arc
Definition: cache.h:1283
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:609
void DeleteArcs()
Definition: cache.h:163
constexpr uint32 kCacheArcs
Definition: cache.h:56
void DeleteArcs(State *state, size_t n)
Definition: cache.h:459
void AddArc(State *state, const Arc &arc)
Definition: cache.h:584
void Delete()
Definition: cache.h:727
void SetArcs(StateId s)
Definition: cache.h:949
CacheStateIterator(const FST &fst, Impl *impl)
Definition: cache.h:1151
void Next()
Definition: fst.h:507