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


90 version_bitmap

%--------------------------------------------------%
% Copyright (C) 2004-2007, 2010-2011 The University of Melbourne
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% 
% File: version_bitmap.m.
% Author: Ralph Becket <rafe@cs.mu.oz.au>.
% Stability: low.
% 
% (See the header comments in version_array.m for an explanation of version
% types.)
%
% Version bitmaps: an implementation of bitmaps using version arrays.
%
% The advantage of version bitmaps is that in the common, singly threaded,
% case, they are almost as fast as unique bitmaps, but can be treated as
% ordinary ground values rather than unique values.
% 
%--------------------------------------------------%
%--------------------------------------------------%

:- module version_bitmap.
:- interface.

:- import_module bool.

%--------------------------------------------------%

:- type version_bitmap.
    
    % init(N, B) creates a version_bitmap of size N (indexed 0 .. N-1)
    % setting each bit if B = yes and clearing each bit if B = no.
    % An exception is thrown if N is negative.
    %
:- func init(int, bool) = version_bitmap.

    % Returns the number of bits in a version_bitmap.
    %
:- func num_bits(version_bitmap) = int.

    % set(BM, I), clear(BM, I) and flip(BM, I) set, clear and flip
    % bit I in BM respectively.  An exception is thrown if I is out
    % of range.  Predicate versions are also provided.
    %
:- func set(version_bitmap, int) = version_bitmap.
:- pred set(int::in, version_bitmap::in, version_bitmap::out) is det.

:- func clear(version_bitmap, int) = version_bitmap.
:- pred clear(int::in, version_bitmap::in, version_bitmap::out) is det.

:- func flip(version_bitmap, int) = version_bitmap.
:- pred flip(int::in, version_bitmap::in, version_bitmap::out) is det.

    % is_set(BM, I) and is_clear(BM, I) succeed iff bit I in BM
    % is set or clear respectively.
    %
:- pred is_set(version_bitmap::in, int::in) is semidet.
:- pred is_clear(version_bitmap::in, int::in) is semidet.

    % Get the given bit.
    %
:- func version_bitmap ^ bit(int) = bool.

    % Set the given bit.
    %
:- func (version_bitmap ^ bit(int) := bool) = version_bitmap.

    % Create a new copy of a version_bitmap.
    %
:- func copy(version_bitmap) = version_bitmap.

    % Set operations; the second argument is altered in all cases.
    %
:- func complement(version_bitmap) = version_bitmap.

:- func union(version_bitmap, version_bitmap) = version_bitmap.

:- func intersect(version_bitmap, version_bitmap) = version_bitmap.

:- func difference(version_bitmap, version_bitmap) = version_bitmap.

:- func xor(version_bitmap, version_bitmap) = version_bitmap.

    % resize(BM, N, B) resizes version_bitmap BM to have N bits; if N is
    % smaller than the current number of bits in BM then the excess
    % are discarded.  If N is larger than the current number of bits
    % in BM then the new bits are set if B = yes and cleared if
    % B = no.
    %
:- func resize(version_bitmap, int, bool) = version_bitmap.

    % Version of the above suitable for use with state variables.
    %
:- pred resize(int::in, bool::in, version_bitmap::in, version_bitmap::out)
            is det.

    % unsafe_rewind(B) produces a version of B for which all accesses are
    % O(1).  Invoking this predicate renders B 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 B or later
    % versions of B.
    %
:- func unsafe_rewind(version_bitmap) = version_bitmap.

    % A version of the above suitable for use with state variables.
    %
:- pred unsafe_rewind(version_bitmap::in, version_bitmap::out) is det.

%--------------------------------------------------%
%--------------------------------------------------%


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