-- file: FSPDefs.Mesa; edited by Sandman on Jan 15, 1980 9:43 AM
-- Copyright  Xerox Corporation 1979, 1980


  -- types and formats of zone headers and nodes

  BlockSize: TYPE = CARDINAL [0..77777B];

  NodePointer: TYPE = POINTER TO NodeHeader;
  FreeNodePointer: TYPE = POINTER TO free NodeHeader;

  NodeHeader: TYPE = RECORD [
    length: BlockSize,
      SELECT state: * FROM
	inuse => NULL,
	free => [fwdp, backp: FreeNodePointer],

  Deallocator: TYPE = PROCEDURE [POINTER];

  ZonePointer: TYPE = POINTER TO ZoneHeader;

  ZoneHeader: TYPE = RECORD [
    node: free NodeHeader,
    rover: FreeNodePointer, -- roving pointer to slow down fragmentation
    -- (see Knuth, Vol I, p. 597 #6)
    lock: MONITORLOCK,
    restOfZone: ZonePointer, -- link to additional segments of zone
    length: BlockSize,
    deallocate: Deallocator,
    threshold: PUBLIC BlockSize,
    checking: PUBLIC BOOLEAN ← FALSE];

  ZoneOverhead: CARDINAL = SIZE[ZoneHeader] + SIZE[inuse NodeHeader];
  NodeOverhead: CARDINAL = SIZE[inuse NodeHeader];

  -- NOTE: A zone whose largest possible node is N words, must have
  --   N + ZoneOverhead + NodeOverhead words of storage
  -- public procedures and signals

  MakeNewZone: PROCEDURE [
    base: POINTER, length: BlockSize, deallocate: Deallocator]
    RETURNS [z: ZonePointer];
  MakeZone: PROCEDURE [base: POINTER, length: BlockSize] RETURNS [z: ZonePointer];
  AddToNewZone: PROCEDURE [
    z: ZonePointer, base: POINTER, length: BlockSize, deallocate: Deallocator];
  AddToZone: PROCEDURE [z: ZonePointer, base: POINTER, length: BlockSize];
  PruneZone: PROCEDURE [z: ZonePointer] RETURNS [BOOLEAN];
  DestroyZone: PROCEDURE [z: ZonePointer];
  DoNothingDeallocate: Deallocator; -- adds storage to System Heap

  NoRoomInZone: SIGNAL [z: ZonePointer]; -- not enough space to fill a request

  MakeNode: PROCEDURE [z: ZonePointer, n: BlockSize] RETURNS [POINTER];
  FreeNode: PROCEDURE [z: ZonePointer, p: POINTER];
  SplitNode: PROCEDURE [z: ZonePointer, p: POINTER, n: BlockSize];
  NodeSize: PROCEDURE [p: POINTER] RETURNS [BlockSize];

  ZoneTooSmall: ERROR [POINTER];
  ZoneTooLarge: ERROR [POINTER];
  InvalidZone: ERROR [POINTER]; -- zone header looks fishy

  NodeLoop: ERROR [ZonePointer];
  InvalidNode: ERROR [POINTER]; -- node appears damaged