mirror of
https://github.com/Mercury-Language/mercury.git
synced 2026-04-15 01:13:30 +00:00
222 lines
8.1 KiB
Mathematica
222 lines
8.1 KiB
Mathematica
%---------------------------------------------------------------------------%
|
|
% vim: ft=mercury ts=4 sw=4 et
|
|
%---------------------------------------------------------------------------%
|
|
% Copyright (C) 2004-2006, 2011 The University of Melbourne.
|
|
% Copyright (C) 2013-2016, 2018, 2022, 2024-2026 The Mercury team.
|
|
% This file is distributed under the terms specified in COPYING.LIB.
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% File: version_store.m.
|
|
% Author: Ralph Becket <rafe@cs.mu.oz.au>
|
|
% Stability: medium.
|
|
%
|
|
% See the header comments in version_array.m for an explanation of version
|
|
% types.
|
|
%
|
|
% A version_store is similar to, albeit slightly slower than, an ordinary
|
|
% store, but does not depend upon uniqueness.
|
|
%
|
|
% Note that, unlike ordinary stores, liveness of data is via the version store
|
|
% rather than the mutvars. This means that dead data (i.e. data whose mutvar
|
|
% is out of scope) in a version_store may not be garbage collected.
|
|
%
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- module version_store.
|
|
:- interface.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- type version_store(S).
|
|
|
|
:- type mutvar(T, S).
|
|
|
|
% Construct a new version store. This is distinguished from other
|
|
% version stores by its existentially quantified type. This means
|
|
% the compiler can automatically detect any attempt to use a mutvar
|
|
% with the wrong version store.
|
|
%
|
|
:- some [S] func init = version_store(S).
|
|
|
|
% new_mutvar(X, Mutvar, VS0, VS) adds a new mutvar with value reference X
|
|
% to the version store.
|
|
%
|
|
:- pred new_mutvar(T::in, mutvar(T, S)::out,
|
|
version_store(S)::in, version_store(S)::out) is det.
|
|
|
|
% new_cyclic_mutvar(F, Mutvar, VS0, VS) adds a new mutvar with value
|
|
% reference F(Mutvar) to the version store. This can be used to
|
|
% construct cyclic terms.
|
|
%
|
|
:- pred new_cyclic_mutvar((func(mutvar(T, S)) = T)::in, mutvar(T, S)::out,
|
|
version_store(S)::in, version_store(S)::out) is det.
|
|
|
|
% copy_mutvar(Mutvar, NewMutvar, VS0, VS) constructs NewMutvar
|
|
% with the same value reference as Mutvar.
|
|
%
|
|
:- pred copy_mutvar(mutvar(T, S)::in, mutvar(T, S)::out,
|
|
version_store(S)::in, version_store(S)::out) is det.
|
|
|
|
% lookup(VS, Mutvar) = Element:
|
|
% VS ^ elem(Mutvar) = Element:
|
|
%
|
|
% Return the Element referenced by Mutvar in the version store VS.
|
|
%
|
|
:- func lookup(version_store(S), mutvar(T, S)) = T.
|
|
% NOTE_TO_IMPLEMENTORS: XXX There should be a pred version of lookup.
|
|
:- func elem(mutvar(T, S), version_store(S)) = T.
|
|
|
|
% get_mutvar(Mutvar, Element, VS, VS):
|
|
%
|
|
% Return the Element referenced by Mutvar in the version store VS,
|
|
% and also return the unchanged version store. This version of lookup
|
|
% may be useful in code using state variables.
|
|
%
|
|
:- pred get_mutvar(mutvar(T, S)::in, T::out,
|
|
version_store(S)::in, version_store(S)::out) is det.
|
|
|
|
% set(VS0, Mutvar, X) = VS:
|
|
% set_mutvar(Mutvar, X, VS0, VS):
|
|
% VS0 ^ elem(Mutvar) := X = VS:
|
|
%
|
|
% Update the version store VS0 so that Mutvar now refers to value X,
|
|
% returning the new version store as VS.
|
|
%
|
|
:- func set(version_store(S), mutvar(T, S), T) = version_store(S).
|
|
:- pred set_mutvar(mutvar(T, S)::in, T::in,
|
|
version_store(S)::in, version_store(S)::out) is det.
|
|
% NOTE_TO_IMPLEMENTORS: XXX The pred version should be "set", not "set_mutvar".
|
|
:- func 'elem :='(mutvar(T, S), version_store(S), T) = version_store(S).
|
|
|
|
% unsafe_rewind(VS) produces a version of VS for which all accesses
|
|
% are O(1). Invoking this predicate renders undefined VS and all later
|
|
% versions that were derived by performing individual updates.
|
|
% Only use this when you are absolutely certain there are no live
|
|
% references to VS or later versions of VS.
|
|
%
|
|
% A predicate version is also provided.
|
|
%
|
|
:- func unsafe_rewind(version_store(T)) = version_store(T).
|
|
:- pred unsafe_rewind(version_store(T)::in, version_store(T)::out) is det.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- implementation.
|
|
|
|
:- import_module counter.
|
|
:- import_module int.
|
|
:- import_module unit.
|
|
:- import_module univ.
|
|
:- import_module version_array.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% Each mutvar contains an index into the version_array;
|
|
% its value is stored in the indicated slot in the version_array.
|
|
%
|
|
% We maintain a counter that, when allocated from, tells us the number
|
|
% of the next free slot in the array. This is what we use to allocate
|
|
% new mutvars. We store this counter at index 0 of the version_array,
|
|
% so all mutvars contain a strictly positive index.
|
|
%
|
|
% Whenever the version_array is about to run out of slots, we double
|
|
% its size. We never shrink the version_array.
|
|
%
|
|
% The slots in the version_array beyond the slot belonging to the last
|
|
% allocated mutvar are not meaningful.
|
|
%
|
|
:- type version_store(S)
|
|
---> version_store(version_array(univ)).
|
|
|
|
:- type mutvar(T, S)
|
|
---> mutvar(int).
|
|
% This integer must be strictly greater than zero.
|
|
|
|
:- type some_version_store_type
|
|
---> some_version_store_type.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
init = version_store(VA) `with_type` version_store(some_version_store_type) :-
|
|
counter.init(1, Counter),
|
|
% Using 256 as the initial size of the array is a compromise between
|
|
% - wasting too much memory in small version_stores
|
|
% (which would happen with larger initial sizes), and
|
|
% - requiring too many reallocations for large version stores
|
|
% (which would happen with smaller initial sizes).
|
|
VA = version_array.init(256, univ(Counter)).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
new_mutvar(X, Mutvar, !VS) :-
|
|
new_cyclic_mutvar(func(_) = X, Mutvar, !VS).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
new_cyclic_mutvar(F, Mutvar, !VS) :-
|
|
CounterMutvar = mutvar(0),
|
|
Counter0 = version_store.lookup(!.VS, CounterMutvar),
|
|
counter.allocate(I, Counter0, Counter),
|
|
Mutvar = mutvar(I),
|
|
Size0 = size(!.VS),
|
|
( if I >= Size0 then
|
|
resize(Size0 + Size0, !VS)
|
|
else
|
|
true
|
|
),
|
|
set_mutvar(CounterMutvar, Counter, !VS),
|
|
set_mutvar(Mutvar, F(Mutvar), !VS).
|
|
|
|
:- func size(version_store(S)) = int.
|
|
|
|
size(version_store(VA)) = size(VA).
|
|
|
|
:- pred resize(int::in, version_store(S)::in, version_store(S)::out) is det.
|
|
|
|
resize(N, version_store(VA0), version_store(VA)) :-
|
|
version_array.resize(N, univ(unit), VA0, VA).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
copy_mutvar(Mutvar0, Mutvar, VS0, VS) :-
|
|
get_mutvar(Mutvar0, Value, VS0, _VS),
|
|
new_mutvar(Value, Mutvar, VS0, VS).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
lookup(VS, Mutvar) = Value :-
|
|
version_store.get_mutvar(Mutvar, Value, VS, _VS).
|
|
|
|
elem(Mutvar, VS) = Value :-
|
|
version_store.get_mutvar(Mutvar, Value, VS, _VS).
|
|
|
|
get_mutvar(mutvar(I), Value, VS, VS) :-
|
|
VS = version_store(VA),
|
|
UnivValue = version_array.lookup(VA, I),
|
|
det_univ_to_type(UnivValue, Value).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
set(VS0, Mutvar, Value) = VS :-
|
|
version_store.set_mutvar(Mutvar, Value, VS0, VS).
|
|
|
|
set_mutvar(mutvar(I), Value, version_store(VA0), version_store(VA)) :-
|
|
version_array.set(I, univ(Value), VA0, VA).
|
|
|
|
'elem :='(Mutvar, VS0, Value) = VS :-
|
|
version_store.set_mutvar(Mutvar, Value, VS0, VS).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
unsafe_rewind(VS0) = VS :-
|
|
version_store.unsafe_rewind(VS0, VS).
|
|
|
|
unsafe_rewind(version_store(VA0), version_store(VA)) :-
|
|
version_array.unsafe_rewind(VA0, VA).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
:- end_module version_store.
|
|
%---------------------------------------------------------------------------%
|