-- ZoneInternal.mesa (last edited by: Luniewski on:  February 5, 1981  9:56 AM)

DIRECTORY
  Zone USING [BlockSize, Handle, Status];

-- This interface defines the basic structure of a zone -
-- the form of its various headers and pointers.

ZoneInternal: DEFINITIONS =
BEGIN OPEN Zone;

OrderedBase: TYPE = LONG ORDERED BASE POINTER;
RPtr: TYPE = OrderedBase RELATIVE ORDERED POINTER;
NodePointer: TYPE = OrderedBase RELATIVE ORDERED POINTER TO NodeHeader;
FreeNodePointer: TYPE =
  OrderedBase RELATIVE ORDERED POINTER TO free NodeHeader;
InuseNodePointer: TYPE =
  OrderedBase RELATIVE ORDERED POINTER TO inuse NodeHeader;

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

ZonePointer: TYPE = LONG ORDERED POINTER TO ZoneHeader;

-- To ensure that the Recreate procedure can be implemented,
-- the seal, version, and root fields must be in the first three words.
ZoneHeader: TYPE = MACHINE DEPENDENT RECORD [
  seal (0): CARDINAL ← zoneSeal, -- MUST BE FIRST WORD
  version (1): CARDINAL ← zoneVersion, -- MUST BE SECOND WORD
  root (2): OrderedBase RELATIVE POINTER ← LOOPHOLE[0], -- MUST BE THIRD WORD
  LOCK(3): MONITORLOCK,
  node (4): free NodeHeader,
  freeList (7), rover (10B): FreeNodePointer,
    -- freeList always points to node, the head of the free list
    -- rover is a roving pointer which points into the middle of the
    -- (circular) free list to slow down fragmentation
    -- (see Knuth, Vol I, p. 597 #6)
  length (11B): BlockSize,
  nextSegment (12B): SegmentPointer, -- link to additional segments of zone
  zoneBase (13B): OrderedBase,
  threshold (15B:0..14): BlockSize,
  checking (15B:15..15): BOOLEAN];
zoneSeal: CARDINAL = 122576B; -- DO NOT EVER CHANGE THIS
zoneVersion: CARDINAL = 100B; -- CHANGE THIS WHENEVER NODE OR ZONE CHANGED

SegmentPointer: TYPE = OrderedBase RELATIVE ORDERED POINTER TO SegmentHeader;
SegmentHeader: TYPE = RECORD [
  nextSegment: SegmentPointer, -- link to additional segments of zone
  length: BlockSize];

CheckNode: PROCEDURE [zH: Handle, node: NodePointer]
  RETURNS [s: Status];
  -- Checks that node is entirely contained within zone.  If node is free,
  -- checks that node is on free list

CheckZone: PROCEDURE [zH: Handle] RETURNS [s: Status];
  -- First validates zone, then checks each of its nodes.  Also
  -- checks that free list has no loops in it

ValidateZone: PROCEDURE [zH: Handle] RETURNS [Status];
  -- Checks that all of zones pointers and counts are consistent

END.

LOG

March 31, 1980  4:44 PM	Luniewski
	Created file

December 22, 1980  2:32 PM	Gobbel
	Added CheckNode, CheckZone, ValidateZone

January 7, 1981  6:04 PM	McJones
	Added stuff for Recreate

January 7, 1981  6:04 PM	Gobbel
	Change Base to OrderedBase, miscellaneous touchups...

February 5, 1981  9:56 AM	Luniewski
	Delete Recreate & Get/Set RootNode - now in Zone.