Club Amiga de Montreal - CAM/CAM_CD_1.iso/files/375.lha/IncrStorageManager_v1.0/DynItemList.mod

Modula Implementation | 1990-05-02 | 6.4 KB | 280 lines

IMPLEMENTATION MODULE DynItemList;

(* Product: Incremental Storage Manager

   Version: 1.0

   Author:
        Daniel B. Hankins
        143 Montgomery Street
        Poughkeepsie, NY 12601
        [e-mail]

   Creation Date: 1989

   Release  Date: November 21, 1989

   Notice of Intellectual Property:
        This material is *NOT COPYRIGHTED*.  By this notice, I hereby place
   this program and all its parts in the public domain, under the definitions
   and restrictions of United States law.

   History of Revisions:
        None yet.
*)

FROM SYSTEM    IMPORT ADDRESS, TSIZE;
FROM WordAlign IMPORT WordAlign;
FROM Storage   IMPORT ALLOCATE, DEALLOCATE;

IMPORT DynItem;

TYPE
  Object     = POINTER TO ListRecord;
  ListRecord = RECORD
                 PrevList, NextList:          Object;
                 NextFreeByte:                ADDRESS;
                 AmountLeft, ItemCount, Size: LONGCARD;
                 FirstItem, LastItem,
                 LowGapItem, CurrentGapItem:  DynItem.Object;
               END;

VAR
  FirstList:      Object;
  ListRecordSize: LONGCARD;
  NilDynItem:     DynItem.Object;

CONST
  BlockSizeResolution = 1024;


PROCEDURE GetListWithSpace(Size: LONGCARD): Object;
VAR
  NewList: Object;
BEGIN
  IF FirstList = NIL THEN
    FirstList := New(Size);
    RETURN FirstList;
  END;

  NewList := FindListWithSpace(FirstList, Size);
  IF NewList <> NIL THEN
    RETURN NewList;
  END;

  NewList := New(Size);
  IF NewList = NIL THEN
    RETURN NIL;
  END;

  LinkInList(NewList, FirstList);
  RETURN NewList;
END GetListWithSpace;


PROCEDURE New(Size: LONGCARD): Object;
VAR
  NewObject: Object;
BEGIN
  Size := Size + ListRecordSize;
  Size := ((Size - 1) DIV BlockSizeResolution + 1) * BlockSizeResolution;
  ALLOCATE(NewObject, Size);
  IF NewObject = NIL THEN
    RETURN NIL;
  END;
  NewObject^.PrevList     := NIL;
  NewObject^.NextList     := NIL;
  NewObject^.AmountLeft   := Size - ListRecordSize;
  NewObject^.Size         := Size;
  NewObject^.NextFreeByte := ADDRESS(LONGCARD(NewObject) + ListRecordSize);
  NewObject^.FirstItem      := NilDynItem;
  NewObject^.LastItem       := NilDynItem;
  NewObject^.LowGapItem     := NilDynItem;
  NewObject^.CurrentGapItem := NilDynItem;
  RETURN NewObject;
END New;


PROCEDURE FindListWithSpace(List: Object; Size: LONGCARD): Object;
BEGIN
  LOOP
    IF List = NIL THEN
      RETURN NIL;
    END;

    IF List^.AmountLeft >= Size THEN
      RETURN List;
    END;

    List := List^.NextList;
  END;
END FindListWithSpace;


PROCEDURE LinkInList(NewList: Object; OldList: Object);
BEGIN
  IF OldList <> NIL THEN
    NewList^.PrevList := OldList;
    NewList^.NextList := OldList^.NextList;
    NewList^.PrevList^.NextList := NewList;
    IF NewList^.NextList <> NIL THEN
      NewList^.NextList^.PrevList := NewList;
    END;
  ELSE
    NewList^.PrevList := NIL;
    NewList^.NextList := NIL;
  END;
END LinkInList;


PROCEDURE UnlinkList(List: Object);
BEGIN
  IF List^.PrevList <> NIL THEN
    List^.PrevList^.NextList := List^.NextList;
  END;

  IF List^.NextList <> NIL THEN
    List^.NextList^.PrevList := List^.PrevList;
  END;

  IF List = FirstList THEN
    FirstList := List^.NextList;
  END;
END UnlinkList;


PROCEDURE GetChunk(List: Object; Size: LONGCARD): ADDRESS;
VAR
  Chunk: ADDRESS;
BEGIN
  Chunk := List^.NextFreeByte;
  List^.NextFreeByte := ADDRESS(LONGCARD(List^.NextFreeByte) + Size);
  List^.AmountLeft   := List^.AmountLeft - Size;
  RETURN Chunk;
END GetChunk;


PROCEDURE LinkItem(List: Object; Item: ADDRESS);
BEGIN
(* Link it to first item in list *)
  DynItem.LinkAfter(DynItem.Object(Item), List^.LastItem);

  List^.LastItem := DynItem.Object(Item);
  IF ADDRESS(List^.FirstItem) = ADDRESS(NilDynItem) THEN
    List^.FirstItem := DynItem.Object(Item);
  END;
  List^.ItemCount := List^.ItemCount + 1;
END LinkItem;


PROCEDURE Percolate(List: Object);
VAR
  MovedItem, OldItem: DynItem.Object;
  NextAddr: ADDRESS;
  ReclaimableSpace: LONGCARD;
BEGIN
(* If ItemCount is zero, then list is no longer needed;  reclaim it and
   exit
*)
  IF List^.ItemCount = 0 THEN
    UnlinkList(List);
    DEALLOCATE(List, List^.Size);
    RETURN;
  END;

(* Move an item *)
  OldItem   := List^.CurrentGapItem;
  IF ADDRESS(OldItem) <> ADDRESS(NilDynItem) THEN
    MovedItem := DynItem.MoveDown(OldItem);

(* Update list variables *)
    IF ADDRESS(List^.FirstItem) = ADDRESS(OldItem) THEN
      List^.FirstItem := MovedItem;
    END;

    IF ADDRESS(List^.LastItem) = ADDRESS(OldItem) THEN
      List^.LastItem := MovedItem;
    END;

    IF ADDRESS(List^.LowGapItem) = ADDRESS(OldItem) THEN
      List^.LowGapItem := DynItem.GetNext(MovedItem);
    END;

    List^.CurrentGapItem := DynItem.GetNext(MovedItem);
    IF ADDRESS(List^.CurrentGapItem) = ADDRESS(NilDynItem) THEN
      List^.CurrentGapItem := List^.LowGapItem;
    END;

(* Reclaim space between last item and first free byte *)
    NextAddr := DynItem.NextAddr(List^.LastItem);
    ReclaimableSpace := LONGCARD(List^.NextFreeByte - NextAddr);
    List^.AmountLeft := List^.AmountLeft + ReclaimableSpace;
    List^.NextFreeByte := NextAddr;
  END;
END Percolate;


PROCEDURE UnlinkItem(List: Object; Item: ADDRESS);
BEGIN
  IF Item = ADDRESS(List^.LastItem) THEN
    List^.LastItem := DynItem.GetPrev(DynItem.Object(Item));
  END;

  IF Item = ADDRESS(List^.FirstItem) THEN
    List^.FirstItem := DynItem.GetNext(DynItem.Object(Item));
  END;

  IF (Item <= ADDRESS(List^.LowGapItem)) OR
     (NIL  =  ADDRESS(List^.LowGapItem)) THEN
    List^.LowGapItem := DynItem.GetNext(DynItem.Object(Item));
  END;

  IF Item = ADDRESS(List^.CurrentGapItem) THEN
    List^.CurrentGapItem := DynItem.GetNext(DynItem.Object(Item));
  END;

  IF NIL = ADDRESS(List^.CurrentGapItem) THEN
    List^.CurrentGapItem := List^.LowGapItem;
  END;

  List^.ItemCount := List^.ItemCount - 1;

  DynItem.Unlink(DynItem.Object(Item));
END UnlinkItem;


PROCEDURE NextAddr(List: Object): ADDRESS;
BEGIN
  RETURN ADDRESS(LONGCARD(List) + ListRecordSize);
END NextAddr;


PROCEDURE DisposeAll();
VAR
  CurrentList, Temp: Object;
BEGIN
  CurrentList := FirstList;
  LOOP
    IF CurrentList = NIL THEN
      EXIT;
    END;
    Temp := CurrentList^.NextList;
    DEALLOCATE(CurrentList, CurrentList^.Size);
    CurrentList := Temp;
  END;
  FirstList := NIL;
END DisposeAll;


PROCEDURE Nil(List: Object): BOOLEAN;
BEGIN
  RETURN (List = NIL);
END Nil;


BEGIN
  FirstList := NIL;
  ListRecordSize := WordAlign(TSIZE(ListRecord));
  NilDynItem := DynItem.NilObject();
END DynItemList.