-- Copyright (C) 1981, 1984, 1985  by Xerox Corporation. All rights reserved. 
--Transport Mechanism Filestore - Bit maps --

-- HGM, 15-Sep-85  0:56:21
-- Randy Gobbel		19-May-81 13:16:21 --
-- A.D.Birrell		December 13, 1978  5:09 PM --

DIRECTORY
  BitMapDefs USING [MapLevel, Map, MapIndex],
  Heap USING [MakeNode, systemZone],
  Inline USING [BITSHIFT, BITAND, BITOR, BITNOT];

BitMap: PROGRAM IMPORTS Heap, Inline EXPORTS BitMapDefs =
  BEGIN

  OPEN BitMapDefs, Inline;

  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: LONG 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: LONG 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 ¬ Heap.systemZone.NEW[MapLevel];
    m.data ¬ DESCRIPTOR[Heap.MakeNode[Heap.systemZone, words], words];
    FOR index: CARDINAL IN [0..words) DO m.data[index] ¬ unset ENDLOOP;
    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.