[m-dev.] For review: bitmap module.

[Ralph Becket]

I've been thinking of adding this for a while and Fergus' suggestion
for the hashtable has motivated me to do it.

Ralph



Estimated hours taken: 2.5

Added a new bitmap type that efficiently stores a bitmap indexed
from 0 .. N-1 where N is the size of the bitmap.  Each bit can be
examined, set, cleared or flipped and the bitmap can be resized.

library/bitmap.m:
	Added.

I give you... the source:

%
----------------------------------------------------------------------------
%
% bitmap.m
% Ralph Becket <rbeck at microsoft.com>
% Thu Feb  1 14:38:31 GMT 2001
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix ft=mercury
%
% Efficient bitmap implementation.
%
%
----------------------------------------------------------------------------
%

:- module bitmap.

:- interface.

:- import_module array, int, bool.



:- type bitmap.

:- mode bitmap_ui == array_ui.
:- mode bitmap_di == array_di.
:- mode bitmap_uo == array_uo.

    % new(N, B) creates a 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 new(int, bool) = bitmap.
:- mode new(in, in) = bitmap_uo is det.

    % Returns the number of bits in a bitmap.
    %
:- func num_bits(bitmap) = int.
:- mode num_bits(bitmap_ui) = out is det.
:- mode num_bits(in) = out is det.

    % set(BM, I), clear(BM, I) and flip(BM, I) set, clear and flip
    % bit I in BM respectively.
    %
:- func set(bitmap, int) = bitmap.
:- mode set(bitmap_di, in) = bitmap_uo is det.

:- func clear(bitmap, int) = bitmap.
:- mode clear(bitmap_di, in) = bitmap_uo is det.

:- func flip(bitmap, int) = bitmap.
:- mode flip(bitmap_di, in) = bitmap_uo 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(bitmap, int).
:- mode is_set(bitmap_ui, in) is semidet.
:- mode is_set(in, in) is semidet.

:- pred is_clear(bitmap, int).
:- mode is_clear(bitmap_ui, in) is semidet.
:- mode is_clear(in, in) is semidet.

    % resize(BM, N, B) resizes 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(bitmap, int, bool) = bitmap.
:- mode resize(bitmap_di, in, in) = bitmap_uo is det.

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

:- implementation.

:- import_module exception.

    % A bitmap is represented as an array of ints where each int stores
    % int__bits_per_int bits.  The first element of the array (index 0)
    % is used to hold the number of bits in the bitmap.  This avoids
    % having to create a new bitmap cell on each update.
    %
    % NOTE: is it worth declaring constants `size_index' and `data_offet'?

:- type bitmap == array(int).

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

new(N, B) = BM :-
    ( if N < 0 then
        throw("bitmap__new: negative size")
      else
        X  = initializer(B),
        BM = (array__init(num_ints_required(N), X) ^ elem(0) := N)
    ).

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

resize(BM0, N, B) = BM :-
    X       = initializer(B),
    NumInts = num_ints_required(N),
    BM1     = array__resize(BM0, NumInts, X),

        % Now we need to ensure that bits N, N+1, N+2, ... up to
        % the word boundary are set or cleared as necessary.
        %
        % If X = 1 << K then -X = \(X - 1) under 2s complement.
        % That is, -X gives us all the bits from K up to the top
        % of the word.
        %
        % XXX I am assuming 2s complement arithmetic!
        %
        % For example, in the following assume int__bits_per_int = 8
        % and we have M = 6.  Then...
        %
        %   Offset =   00100000
        %   Bits   =  -00100000 /\ X = 11100000 /\ X
        %   Mask   = \-00100000      = 00011111
        %
    int__min(num_bits(BM0), N, M),
    Offset  = int_offset(M),
    Bits    =   -bitmask(M) /\ X,       % Bits we need to fill in.
    Mask    = \(-bitmask(M)),           % Mask to preserve the other bits.
    BM      = ((BM1
                    ^ elem(Offset) := (BM1 ^ elem(Offset) /\ Mask) \/ Bits)
                    ^ elem(0)      := N).

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

:- func initializer(bool) = int.

initializer(no)  = 0.
initializer(yes) = \(0).

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

:- func num_ints_required(int) = int.

num_ints_required(N) = 1 + ((N + int__bits_per_int - 1) //
int__bits_per_int).

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

:- func bitmask(int) = int.

    % NOTE: it would be nicer to use /\ with a bitmask here rather
    % than rem.  Do modern back-ends do the decent thing here if
    % int__bits_per_int is the expected power of two?
    %
bitmask(I) = 1 `unchecked_left_shift` (I `rem` int__bits_per_int).

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

:- pred in_range(bitmap, int).
:- mode in_range(bitmap_ui, in) is semidet.
:- mode in_range(in, in) is semidet.

in_range(BM, I) :- 0 =< I, I < num_bits(BM).

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

:- func int_offset(int) = int.

int_offset(I) = 1 + (I // int__bits_per_int).

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

num_bits(BM) = BM ^ elem(0).

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

set(BM, I) =
    BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) \/ bitmask(I)
 :-
    ( if in_range(BM, I) then true else throw("bitmap__set: out of range")
).

clear(BM, I) =
    BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) /\ (\ bitmask(I))
 :-
    ( if in_range(BM, I) then true else throw("bitmap__clear: out of range")
).

flip(BM, I) =
    BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) `xor` bitmask(I)
 :-
    ( if in_range(BM, I) then true else throw("bitmap__flip: out of range")
).

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

is_set(BM, I) :-
    ( if in_range(BM, I)
      then BM ^ elem(int_offset(I)) /\ bitmask(I) \= 0
      else throw("bitmap__is_set: out of range")
    ).

is_clear(BM, I) :-
    ( if in_range(BM, I)
      then BM ^ elem(int_offset(I)) /\ bitmask(I) \= 0
      else throw("bitmap__is_clear: out of range")
    ).

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

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------