Next: version_array2d, Previous: varset, Up: Top [Contents]

%--------------------------------------------------% % vim: ts=4 sw=4 et ft=mercury %--------------------------------------------------% % Copyright (C) 2004-2012 The University of Melbourne. % Copyright (C) 2014-2020 The Mercury Team. % This file is distributed under the terms specified in COPYING.LIB. %--------------------------------------------------% % % File: version_array.m. % Author: Ralph Becket <rafe@cs.mu.oz.au>. % Stability: low. % % Version types are efficient pure implementations of typically imperative % structures, subject to the following caveat: efficient access is only % guaranteed for the "latest" version of a given structure. An older version % incurs an access cost proportional to the number of its descendants. % % For example, if A0 is a version array, and A1 is created by updating A0, % and A2 is created by updating A1, ..., and An is created by updating An-1, % then accesses to An cost O(1) (assuming no further versions of the array % have been created from An), but accesses to A0 cost O(n). % % Updates to older versions of the structure (for example A(n-1)) may have % additional costs, for arrays this cost is O(m) where m is the size of the % array, as the whole array is copied to make a new version array. % % Most version data structures come with impure, unsafe means to "rewind" % to an earlier version, restoring that version's O(1) access times, but % leaving later versions undefined (i.e. only do this if you are discarding % all later versions of the structure.) % % The motivation for using version types is that they are ordinary ground % structures and do not depend upon uniqueness, while in many circumstances % offering similar levels of performance. % % This module implements version arrays. A version array provides O(1) % access and update for the "latest" version of the array. "Older" % versions of the array incur an O(k) penalty on accesses where k is % the number of updates that have been made since. % % The advantage of version arrays is that in the common, singly threaded, % case, they are almost as fast as unique arrays, but can be treated as % ordinary ground values rather than unique values. % % Version arrays are zero based. % %--------------------------------------------------% %--------------------------------------------------% :- module version_array. :- interface. :- import_module list. :- import_module pretty_printer. %--------------------------------------------------% :- type version_array(T). % An `version_array.index_out_of_bounds' is the exception thrown % on out-of-bounds array accesses. The string describes % the predicate or function reporting the error. % :- type version_array.index_out_of_bounds ---> version_array.index_out_of_bounds(string). %--------------------------------------------------% % empty_array returns the empty array. % :- func empty = version_array(T). % init(N, X) returns an array of size N with each item initialised to X. % :- func init(int, T) = version_array(T). % Same as empty/0 except the resulting version_array is not thread safe. % % That is your program can crash or behave strangely if you attempt to % concurrently access or update the array from different threads, or any % two arrays produced from operations on the same original array. % However this version is much quicker if you guarantee that you never % concurrently access the version array. % :- func unsafe_empty = version_array(T). % Same as init(N, X) except the resulting version_array is not thread safe. % % That is your program can crash or behave strangely if you attempt to % concurrently access or update the array from different threads, or any % two arrays produced from operations on the same original array. % However this version is much quicker if you guarantee that you never % concurrently access the version array. % :- func unsafe_init(int, T) = version_array(T). % version_array(Xs) returns an array constructed from the items in the list % Xs. % :- func version_array(list(T)) = version_array(T). % A synonym for the above. % :- func from_list(list(T)) = version_array(T). % from_reverse_list(Xs) returns an array constructed from the items in the % list Xs in reverse order. % :- func from_reverse_list(list(T)) = version_array(T). % lookup(A, I) = X iff the I'th member of A is X. % (The first item has index 0). % :- func lookup(version_array(T), int) = T. % A ^ elem(I) = lookup(A, I) % :- func version_array(T) ^ elem(int) = T. % set(I, X, A0, A): A is a copy of array A0 with item I updated to be X. % An exception is thrown if I is out of bounds. % :- pred set(int::in, T::in, version_array(T)::in, version_array(T)::out) is det. % (A0 ^ elem(I) := X) = A is equivalent to set(I, X, A0, A). % :- func (version_array(T) ^ elem(int) := T) = version_array(T). % size(A) = N if A contains N items (i.e. the valid indices for A % range from 0 to N - 1). % :- func size(version_array(T)) = int. % max(Z) = size(A) - 1. % Returns -1 for an empty array. % :- func max(version_array(T)) = int. % is_empty(Array) is true iff Array is the empty array. % :- pred is_empty(version_array(T)::in) is semidet. % resize(A, N, X) returns a new array whose items from % 0..min(size(A), N - 1) are taken from A and whose items % from min(size(A), N - 1)..(N - 1) (if any) are initialised to X. % A predicate version is also provided. % :- func resize(version_array(T), int, T) = version_array(T). :- pred resize(int::in, T::in, version_array(T)::in, version_array(T)::out) is det. % copy(A) is a copy of array A. Access to the copy is O(1). % :- func copy(version_array(T)) = version_array(T). % list(A) = Xs where Xs is the list of items in A % (i.e. A = version_array(Xs)). % :- func list(version_array(T)) = list(T). % A synonym for the above. % :- func to_list(version_array(T)) = list(T). % foldl(F, A, X) is equivalent to list.foldl(F, list(A), X). % :- func foldl(func(T1, T2) = T2, version_array(T1), T2) = T2. % foldl(P, A, !X) is equivalent to list.foldl(P, list(A), !X). % :- pred foldl(pred(T1, T2, T2), version_array(T1), T2, T2). :- mode foldl(pred(in, in, out) is det, in, in, out) is det. :- mode foldl(pred(in, mdi, muo) is det, in, mdi, muo) is det. :- mode foldl(pred(in, di, uo) is det, in, di, uo) is det. :- mode foldl(pred(in, in, out) is semidet, in, in, out) is semidet. :- mode foldl(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet. :- mode foldl(pred(in, di, uo) is semidet, in, di, uo) is semidet. % foldl2(P, A, !Acc1, !Acc2) is equivalent to % list.foldl2(P, list(A), !Acc1, !Acc2) but more efficient. % :- pred foldl2(pred(T1, T2, T2, T3, T3), version_array(T1), T2, T2, T3, T3). :- mode foldl2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det. :- mode foldl2(pred(in, in, out, mdi, muo) is det, in, in, out, mdi, muo) is det. :- mode foldl2(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det. :- mode foldl2(pred(in, in, out, in, out) is semidet, in, in, out, in, out) is semidet. :- mode foldl2(pred(in, in, out, mdi, muo) is semidet, in, in, out, mdi, muo) is semidet. :- mode foldl2(pred(in, in, out, di, uo) is semidet, in, in, out, di, uo) is semidet. % foldr(F, A, X) is equivalent to list.foldr(F, list(A), Xs). % :- func foldr(func(T1, T2) = T2, version_array(T1), T2) = T2. :- pred foldr(pred(T1, T2, T2), version_array(T1), T2, T2). :- mode foldr(pred(in, in, out) is det, in, in, out) is det. :- mode foldr(pred(in, mdi, muo) is det, in, mdi, muo) is det. :- mode foldr(pred(in, di, uo) is det, in, di, uo) is det. :- mode foldr(pred(in, in, out) is semidet, in, in, out) is semidet. :- mode foldr(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet. :- mode foldr(pred(in, di, uo) is semidet, in, di, uo) is semidet. :- pred foldr2(pred(T1, T2, T2, T3, T3), version_array(T1), T2, T2, T3, T3). :- mode foldr2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det. :- mode foldr2(pred(in, in, out, mdi, muo) is det, in, in, out, mdi, muo) is det. :- mode foldr2(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det. :- mode foldr2(pred(in, in, out, in, out) is semidet, in, in, out, in, out) is semidet. :- mode foldr2(pred(in, in, out, mdi, muo) is semidet, in, in, out, mdi, muo) is semidet. :- mode foldr2(pred(in, in, out, di, uo) is semidet, in, in, out, di, uo) is semidet. % version_array.all_true(Pred, Array): % True iff Pred is true for every element of Array. % :- pred all_true(pred(T)::in(pred(in) is semidet), version_array(T)::in) is semidet. % version_array.all_false(Pred, Array): % True iff Pred is false for every element of Array. % :- pred all_false(pred(T)::in(pred(in) is semidet), version_array(T)::in) is semidet. % unsafe_rewind(A) produces a version of A for which all accesses are O(1). % Invoking this predicate renders A and all later versions undefined that % were derived by performing individual updates. Only use this when you are % absolutely certain there are no live references to A or later versions % of A. (A predicate version is also provided.) % :- func unsafe_rewind(version_array(T)) = version_array(T). :- pred unsafe_rewind(version_array(T)::in, version_array(T)::out) is det. % Convert a version_array to a pretty_printer.doc for formatting. % :- func version_array_to_doc(version_array(T)) = pretty_printer.doc. %--------------------------------------------------% %--------------------------------------------------% % The first implementation of version arrays used nb_references. % This incurred three memory allocations for every update. This version % works at a lower level, but only performs one allocation per update. %--------------------------------------------------%

Next: version_array2d, Previous: varset, Up: Top [Contents]