// cache.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// An Fst implementation that caches FST elements of a delayed
// computation.
#ifndef FST_LIB_CACHE_H__
#define FST_LIB_CACHE_H__
#include <vector>
using std::vector;
#include <list>
#include <fst/vector-fst.h>
DECLARE_bool(fst_default_cache_gc);
DECLARE_int64(fst_default_cache_gc_limit);
namespace fst {
struct CacheOptions {
bool gc; // enable GC
size_t gc_limit; // # of bytes allowed before GC
CacheOptions(bool g, size_t l) : gc(g), gc_limit(l) {}
CacheOptions()
: gc(FLAGS_fst_default_cache_gc),
gc_limit(FLAGS_fst_default_cache_gc_limit) {}
};
// A CacheStateAllocator allocates and frees CacheStates
// template <class S>
// struct CacheStateAllocator {
// S *Allocate(StateId s);
// void Free(S *state, StateId s);
// };
//
// A simple allocator class, can be overridden as needed,
// maintains a single entry cache.
template <class S>
struct DefaultCacheStateAllocator {
typedef typename S::Arc::StateId StateId;
DefaultCacheStateAllocator() : mru_(NULL) { }
~DefaultCacheStateAllocator() {
delete mru_;
}
S *Allocate(StateId s) {
if (mru_) {
S *state = mru_;
mru_ = NULL;
state->Reset();
return state;
}
return new S();
}
void Free(S *state, StateId s) {
if (mru_) {
delete mru_;
}
mru_ = state;
}
private:
S *mru_;
};
// VectorState but additionally has a flags data member (see
// CacheState below). This class is used to cache FST elements with
// the flags used to indicate what has been cached. Use HasStart()
// HasFinal(), and HasArcs() to determine if cached and SetStart(),
// SetFinal(), AddArc(), (or PushArc() and SetArcs()) to cache. Note
// you must set the final weight even if the state is non-final to
// mark it as cached. If the 'gc' option is 'false', cached items have
// the extent of the FST - minimizing computation. If the 'gc' option
// is 'true', garbage collection of states (not in use in an arc
// iterator and not 'protected') is performed, in a rough
// approximation of LRU order, when 'gc_limit' bytes is reached -
// controlling memory use. When 'gc_limit' is 0, special optimizations
// apply - minimizing memory use.
template <class S, class C = DefaultCacheStateAllocator<S> >
class CacheBaseImpl : public VectorFstBaseImpl<S> {
public:
typedef S State;
typedef C Allocator;
typedef typename State::Arc Arc;
typedef typename Arc::Weight Weight;
typedef typename Arc::StateId StateId;
using FstImpl<Arc>::Type;
using FstImpl<Arc>::Properties;
using FstImpl<Arc>::SetProperties;
using VectorFstBaseImpl<State>::NumStates;
using VectorFstBaseImpl<State>::Start;
using VectorFstBaseImpl<State>::AddState;
using VectorFstBaseImpl<State>::SetState;
using VectorFstBaseImpl<State>::ReserveStates;
explicit CacheBaseImpl(C *allocator = 0)
: cache_start_(false), nknown_states_(0), min_unexpanded_state_id_(0),
cache_first_state_id_(kNoStateId), cache_first_state_(0),
cache_gc_(FLAGS_fst_default_cache_gc), cache_size_(0),
cache_limit_(FLAGS_fst_default_cache_gc_limit > kMinCacheLimit ||
FLAGS_fst_default_cache_gc_limit == 0 ?
FLAGS_fst_default_cache_gc_limit : kMinCacheLimit),
protect_(false) {
allocator_ = allocator ? allocator : new C();
}
explicit CacheBaseImpl(const CacheOptions &opts, C *allocator = 0)
: cache_start_(false), nknown_states_(0),
min_unexpanded_state_id_(0), cache_first_state_id_(kNoStateId),
cache_first_state_(0), cache_gc_(opts.gc), cache_size_(0),
cache_limit_(opts.gc_limit > kMinCacheLimit || opts.gc_limit == 0 ?
opts.gc_limit : kMinCacheLimit),
protect_(false) {
allocator_ = allocator ? allocator : new C();
}
// Preserve gc parameters. If preserve_cache true, also preserves
// cache data.
CacheBaseImpl(const CacheBaseImpl<S, C> &impl, bool preserve_cache = false)
: VectorFstBaseImpl<S>(), cache_start_(false), nknown_states_(0),
min_unexpanded_state_id_(0), cache_first_state_id_(kNoStateId),
cache_first_state_(0), cache_gc_(impl.cache_gc_), cache_size_(0),
cache_limit_(impl.cache_limit_),
protect_(impl.protect_) {
allocator_ = new C();
if (preserve_cache) {
cache_start_ = impl.cache_start_;
nknown_states_ = impl.nknown_states_;
expanded_states_ = impl.expanded_states_;
min_unexpanded_state_id_ = impl.min_unexpanded_state_id_;
if (impl.cache_first_state_id_ != kNoStateId) {
cache_first_state_id_ = impl.cache_first_state_id_;
cache_first_state_ = allocator_->Allocate(cache_first_state_id_);
*cache_first_state_ = *impl.cache_first_state_;
}
cache_states_ = impl.cache_states_;
cache_size_ = impl.cache_size_;
ReserveStates(impl.NumStates());
for (StateId s = 0; s < impl.NumStates(); ++s) {
const S *state =
static_cast<const VectorFstBaseImpl<S> &>(impl).GetState(