14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// cache.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// An Fst implementation that caches FST elements of a delayed 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// computation. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_CACHE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_CACHE_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <list> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/vector-fst.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectDECLARE_bool(fst_default_cache_gc); 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectDECLARE_int64(fst_default_cache_gc_limit); 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct CacheOptions { 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool gc; // enable GC 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t gc_limit; // # of bytes allowed before GC 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheOptions(bool g, size_t l) : gc(g), gc_limit(l) {} 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheOptions() 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : gc(FLAGS_fst_default_cache_gc), 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project gc_limit(FLAGS_fst_default_cache_gc_limit) {} 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// This is a VectorFstBaseImpl container that holds a State similar to 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// VectorState but additionally has a flags data member (see 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// CacheState below). This class is used to cache FST elements with 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the flags used to indicate what has been cached. Use HasStart() 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// HasFinal(), and HasArcs() to determine if cached and SetStart(), 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// SetFinal(), AddArc(), and SetArcs() to cache. Note you must set the 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// final weight even if the state is non-final to mark it as 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// cached. If the 'gc' option is 'false', cached items have the extent 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of the FST - minimizing computation. If the 'gc' option is 'true', 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// garbage collection of states (not in use in an arc iterator) is 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// performed, in a rough approximation of LRU order, when 'gc_limit' 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bytes is reached - controlling memory use. When 'gc_limit' is 0, 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// special optimizations apply - minimizing memory use. 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass CacheBaseImpl : public VectorFstBaseImpl<S> { 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<typename S::Arc>::Type; 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using VectorFstBaseImpl<S>::NumStates; 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using VectorFstBaseImpl<S>::AddState; 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S State; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename S::Arc Arc; 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheBaseImpl() 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : cache_start_(false), nknown_states_(0), min_unexpanded_state_id_(0), 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_id_(kNoStateId), cache_first_state_(0), 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_gc_(FLAGS_fst_default_cache_gc), cache_size_(0), 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_limit_(FLAGS_fst_default_cache_gc_limit > kMinCacheLimit || 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FLAGS_fst_default_cache_gc_limit == 0 ? 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FLAGS_fst_default_cache_gc_limit : kMinCacheLimit) {} 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit CacheBaseImpl(const CacheOptions &opts) 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : cache_start_(false), nknown_states_(0), 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project min_unexpanded_state_id_(0), cache_first_state_id_(kNoStateId), 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_(0), cache_gc_(opts.gc), cache_size_(0), 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_limit_(opts.gc_limit > kMinCacheLimit || opts.gc_limit == 0 ? 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project opts.gc_limit : kMinCacheLimit) {} 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~CacheBaseImpl() { 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete cache_first_state_; 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Gets a state from its ID; state must exist. 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *GetState(StateId s) const { 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == cache_first_state_id_) 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return cache_first_state_; 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return VectorFstBaseImpl<S>::GetState(s); 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Gets a state from its ID; state must exist. 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *GetState(StateId s) { 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == cache_first_state_id_) 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return cache_first_state_; 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return VectorFstBaseImpl<S>::GetState(s); 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Gets a state from its ID; return 0 if it doesn't exist. 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *CheckState(StateId s) const { 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == cache_first_state_id_) 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return cache_first_state_; 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (s < NumStates()) 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return VectorFstBaseImpl<S>::GetState(s); 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 0; 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Gets a state from its ID; add it if necessary. 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *ExtendState(StateId s) { 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == cache_first_state_id_) { 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return cache_first_state_; // Return 1st cached state 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (cache_limit_ == 0 && cache_first_state_id_ == kNoStateId) { 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_id_ = s; // Remember 1st cached state 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_ = new S; 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return cache_first_state_; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (cache_first_state_id_ != kNoStateId && 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_->ref_count == 0) { 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_id_ = s; // Reuse 1st cached state 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_->Reset(); 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return cache_first_state_; // Return 1st cached state 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (NumStates() <= s) // Add state to main cache 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddState(0); 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!VectorFstBaseImpl<S>::GetState(s)) { 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetState(s, new S); 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_first_state_id_ != kNoStateId) { // Forget 1st cached state 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (NumStates() <= cache_first_state_id_) 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddState(0); 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetState(cache_first_state_id_, cache_first_state_); 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_gc_) { 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_states_.push_back(cache_first_state_id_); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_size_ += sizeof(S) + 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_->arcs.capacity() * sizeof(Arc); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_limit_ = kMinCacheLimit; 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_id_ = kNoStateId; 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_first_state_ = 0; 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_gc_) { 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_states_.push_back(s); 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_size_ += sizeof(S); 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_size_ > cache_limit_) 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GC(s, false); 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return VectorFstBaseImpl<S>::GetState(s); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void SetStart(StateId s) { 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFstBaseImpl<S>::SetStart(s); 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_start_ = true; 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s >= nknown_states_) 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nknown_states_ = s + 1; 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void SetFinal(StateId s, Weight w) { 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *state = ExtendState(s); 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->final = w; 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->flags |= kCacheFinal | kCacheRecent; 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void AddArc(StateId s, const Arc &arc) { 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *state = ExtendState(s); 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->arcs.push_back(arc); 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Marks arcs of state s as cached. 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void SetArcs(StateId s) { 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *state = ExtendState(s); 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Arc> &arcs = state->arcs; 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->niepsilons = state->noepsilons = 0; 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (unsigned int a = 0; a < arcs.size(); ++a) { 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = arcs[a]; 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.nextstate >= nknown_states_) 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nknown_states_ = arc.nextstate + 1; 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.ilabel == 0) 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++state->niepsilons; 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.olabel == 0) 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++state->noepsilons; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ExpandedState(s); 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->flags |= kCacheArcs | kCacheRecent; 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_gc_ && s != cache_first_state_id_) { 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_size_ += arcs.capacity() * sizeof(Arc); 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_size_ > cache_limit_) 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GC(s, false); 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void ReserveArcs(StateId s, size_t n) { 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *state = ExtendState(s); 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->arcs.reserve(n); 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Is the start state cached? 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool HasStart() const { return cache_start_; } 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Is the final weight of state s cached? 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool HasFinal(StateId s) const { 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = CheckState(s); 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (state && state->flags & kCacheFinal) { 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->flags |= kCacheRecent; 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Are arcs of state s cached? 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool HasArcs(StateId s) const { 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = CheckState(s); 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (state && state->flags & kCacheArcs) { 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->flags |= kCacheRecent; 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) const { 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = GetState(s); 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return state->final; 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) const { 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = GetState(s); 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return state->arcs.size(); 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) const { 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = GetState(s); 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return state->niepsilons; 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) const { 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = GetState(s); 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return state->noepsilons; 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Provides information needed for generic arc iterator. 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const { 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const S *state = GetState(s); 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = 0; 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->narcs = state->arcs.size(); 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->arcs = data->narcs > 0 ? &(state->arcs[0]) : 0; 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->ref_count = &(state->ref_count); 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++(*data->ref_count); 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Number of known states. 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId NumKnownStates() const { return nknown_states_; } 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Find the mininum never-expanded state Id 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId MinUnexpandedState() const { 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (min_unexpanded_state_id_ < (StateId)expanded_states_.size() && 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project expanded_states_[min_unexpanded_state_id_]) 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++min_unexpanded_state_id_; 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return min_unexpanded_state_id_; 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Removes from cache_states_ and uncaches (not referenced-counted) 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // states that have not been accessed since the last GC until 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // cache_limit_/3 bytes are uncached. If that fails to free enough, 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // recurs uncaching recently visited states as well. If still 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // unable to free enough memory, then widens cache_limit_. 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void GC(StateId current, bool free_recent) { 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!cache_gc_) 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "CacheImpl: Enter GC: object = " << Type() << "(" << this 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "), free recently cached = " << free_recent 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ", cache size = " << cache_size_ 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ", cache limit = " << cache_limit_ << "\n"; 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename list<StateId>::iterator siter = cache_states_.begin(); 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t cache_target = (2 * cache_limit_)/3 + 1; 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (siter != cache_states_.end()) { 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = *siter; 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S* state = VectorFstBaseImpl<S>::GetState(s); 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (cache_size_ > cache_target && state->ref_count == 0 && 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (free_recent || !(state->flags & kCacheRecent)) && s != current) { 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_size_ -= sizeof(S) + state->arcs.capacity() * sizeof(Arc); 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete state; 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetState(s, 0); 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_states_.erase(siter++); 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state->flags &= ~kCacheRecent; 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++siter; 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!free_recent && cache_size_ > cache_target) { 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GC(current, true); 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (cache_size_ > cache_target) { 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_limit_ *= 2; 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cache_target *= 2; 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "CacheImpl: Exit GC: object = " << Type() << "(" << this 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "), free recently cached = " << free_recent 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ", cache size = " << cache_size_ 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ", cache limit = " << cache_limit_ << "\n"; 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const uint32 kCacheFinal = 0x0001; // Final weight has been cached 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const uint32 kCacheArcs = 0x0002; // Arcs have been cached 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const uint32 kCacheRecent = 0x0004; // Mark as visited since GC 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const size_t kMinCacheLimit; // Minimum (non-zero) cache limit 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void ExpandedState(StateId s) { 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s < min_unexpanded_state_id_) 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)expanded_states_.size() <= s) 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project expanded_states_.push_back(false); 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project expanded_states_[s] = true; 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool cache_start_; // Is the start state cached? 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nknown_states_; // # of known states 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> expanded_states_; // states that have been expanded 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project mutable StateId min_unexpanded_state_id_; // minimum never-expanded state Id 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId cache_first_state_id_; // First cached state id 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S *cache_first_state_; // First cached state 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project list<StateId> cache_states_; // list of currently cached states 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool cache_gc_; // enable GC 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t cache_size_; // # of bytes cached 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t cache_limit_; // # of bytes allowed before GC 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitStateIterator(StateIteratorData<Arc> *); // disallow 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(CacheBaseImpl); 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst size_t CacheBaseImpl<S>::kMinCacheLimit = 8096; 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Arcs implemented by an STL vector per state. Similar to VectorState 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// but adds flags and ref count to keep track of what has been cached. 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct CacheState { 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheState() : final(Weight::Zero()), flags(0), ref_count(0) {} 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Reset() { 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project flags = 0; 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ref_count = 0; 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.resize(0); 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final; // Final weight 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<A> arcs; // Arcs represenation 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t niepsilons; // # of input epsilons 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t noepsilons; // # of output epsilons 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project mutable uint32 flags; 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project mutable int ref_count; 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// A CacheBaseImpl with a commonly used CacheState. 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass CacheImpl : public CacheBaseImpl< CacheState<A> > { 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl() {} 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit CacheImpl(const CacheOptions &opts) 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheBaseImpl< CacheState<A> >(opts) {} 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(CacheImpl); 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Use this to make a state iterator for a CacheBaseImpl-derived Fst. 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You'll need to make this class a friend of your derived Fst. 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Note this iterator only returns those states reachable from 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the initial state, so consider implementing a class-specific one. 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class F> 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass CacheStateIterator : public StateIteratorBase<typename F::Arc> { 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename F::Arc Arc; 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit CacheStateIterator(const F &fst) : fst_(fst), s_(0) {} 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Done() const { 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ < fst_.impl_->NumKnownStates()) 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst_.Start(); // force start state 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ < fst_.impl_->NumKnownStates()) 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int u = fst_.impl_->MinUnexpandedState(); 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project u < fst_.impl_->NumKnownStates(); 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project u = fst_.impl_->MinUnexpandedState()) { 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator<F>(fst_, u); // force state expansion 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ < fst_.impl_->NumKnownStates()) 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Value() const { return s_; } 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Next() { ++s_; } 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Reset() { s_ = 0; } 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const F &fst_; 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s_; 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Use this to make an arc iterator for a CacheBaseImpl-derived Fst. 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You'll need to make this class a friend of your derived Fst and 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// define types Arc and State. 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class F> 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass CacheArcIterator { 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename F::Arc Arc; 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename F::State State; 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheArcIterator(const F &fst, StateId s) : i_(0) { 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_ = fst.impl_->ExtendState(s); 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++state_->ref_count; 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~CacheArcIterator() { --state_->ref_count; } 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Done() const { return i_ >= state_->arcs.size(); } 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc& Value() const { return state_->arcs[i_]; } 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Next() { ++i_; } 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Reset() { i_ = 0; } 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Seek(size_t a) { i_ = a; } 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const State *state_; 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t i_; 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(CacheArcIterator); 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_CACHE_H__ 462