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