home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Club Amiga de Montreal - CAM
/
CAM_CD_1.iso
/
files
/
375.lha
/
IncrStorageManager_v1.0
/
DynItemList.mod
< prev
next >
Wrap
Text File
|
1990-05-02
|
7KB
|
280 lines
IMPLEMENTATION MODULE DynItemList;
(* Product: Incremental Storage Manager
Version: 1.0
Author:
Daniel B. Hankins
143 Montgomery Street
Poughkeepsie, NY 12601
dan-hankins@cup.portal.com
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.