--Transport Mechanism Filestore - Bit maps --

-- Randy Gobbel		19-May-81 13:16:21 --
-- A.D.Birrell		December 13, 1978  5:09 PM --

DIRECTORY
  BitMapDefs USING [MapLevel, Map, MapIndex],
  Storage USING [Node],
  Inline USING [BITSHIFT, BITAND, BITOR, BITNOT];

BitMap: PROGRAM IMPORTS Inline, Storage EXPORTS BitMapDefs =
  BEGIN

  OPEN BitMapDefs, Inline;

  Allocate: PROCEDURE [CARDINAL] RETURNS [POINTER] = Storage.Node;

  BitPos: TYPE = [0..16);  -- name of a bit in a word --
  unset: WORD = 0B;  -- all bits 0 --
  allSet: WORD = 177777B;  -- all bits 1 --

  MapFull: ERROR = CODE;

  FindFree: PUBLIC PROCEDURE [m: Map] RETURNS [MapIndex] =
    BEGIN
    wPos: MapIndex = IF m.level = 0 THEN 0 ELSE FindFree[m.next];
    word: WORD = m.data[wPos];
    -- now find the first 0 bit in 'word' --
    -- more efficient not to parameterise by 'width' --
    bPos: BitPos ← 0;
    half: WORD ← BITAND[word, 377B];
    IF half = 377B THEN BEGIN half ← BITSHIFT[word, -8]; bPos ← bPos + 8 END;
    BEGIN
    quart: WORD ← BITAND[half, 17B];
    IF quart = 17B THEN BEGIN quart ← BITSHIFT[half, -4]; bPos ← bPos + 4 END;
    BEGIN
    eight: WORD ← BITAND[quart, 3B];
    IF eight = 3B THEN BEGIN eight ← BITSHIFT[quart, -2]; bPos ← bPos + 2 END;
    IF eight = 1B THEN bPos ← bPos + 1 ELSE IF eight = 3B THEN ERROR MapFull[];
    END;
    END;
    RETURN[BITOR[BITSHIFT[wPos, 4], bPos]]
    END;

  Set: PUBLIC PROCEDURE [m: Map, pos: MapIndex] =
    BEGIN
    wPos: MapIndex = BITSHIFT[pos, -4];
    word: POINTER TO WORD = @(m.data[wPos]);
    word↑ ← BITOR[word↑, BITSHIFT[1B, BITAND[pos, 17B]]];
    IF word↑ = allSet AND m.level # 0 THEN Set[m.next, wPos];
    END;

  Test: PUBLIC PROCEDURE [m: Map, pos: MapIndex] RETURNS [BOOLEAN] =
    BEGIN
    wPos: MapIndex = BITSHIFT[pos, -4];
    RETURN[
      IF wPos >= LENGTH[m.data] THEN FALSE
      ELSE BITAND[m.data[wPos], BITSHIFT[1B, BITAND[pos, 17B]]] # 0]
    END;

  Clear: PUBLIC PROCEDURE [m: Map, pos: MapIndex] =
    BEGIN
    wPos: MapIndex = BITSHIFT[pos, -4];
    word: POINTER TO WORD = @(m.data[wPos]);
    bPos: BitPos = BITAND[pos, 17B];
    IF word↑ = allSet AND m.level # 0 THEN Clear[m.next, wPos];
    word↑ ← BITAND[word↑, BITNOT[BITSHIFT[1B, bPos]]];
    END;

  Create: PUBLIC PROCEDURE [size: CARDINAL] RETURNS [m: Map] =
    BEGIN
    -- beware of overflow if size = LAST[CARDINAL] --
    words: CARDINAL = size / 16 + (IF size MOD 16 = 0 THEN 0 ELSE 1);
    m ← Allocate[SIZE[MapLevel]];
    m.data ← DESCRIPTOR[Allocate[words], words];
    BEGIN
    index: CARDINAL;
    FOR index IN [0..words) DO m.data[index] ← unset ENDLOOP;
    END;
    IF words > 1 THEN
      BEGIN m.next ← Create[words]; m.level ← m.next.level + 1; END
    ELSE BEGIN m.next ← NIL --only a safety precaution-- ; m.level ← 0; END;
    END;

  END.