--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.