-- RunsImpl.Mesa
-- last edited 26-Mar-82 17:56:53 by Paul Rovner

DIRECTORY
  Environment USING[wordsPerPage],
  RTFlags USING[checking],
  RTOS USING[GetPermanentDataPages],
  RTQuanta USING[PagesPerQuantum],
  Runs;

RunsImpl: MONITOR  -- protects runs
  IMPORTS RTOS
  EXPORTS Runs =

  BEGIN
  OPEN Environment, RTOS, RTQuanta, Runs;

-- Signals

OverlappingInterval: PUBLIC SIGNAL = CODE;
MissingInterval: PUBLIC ERROR = CODE;
CantFindInterval: PUBLIC ERROR = CODE;

-- Global variables

runs: Run ← NIL;

RunAllocProc: ENTRY PROC RETURNS[run: Run] =
INLINE
  {ENABLE UNWIND => NULL;
   IF runs = NIL
    THEN {p: Run ← GetPermanentDataPages[PagesPerQuantum];  -- NOTE arg must be a multiple of PagesPerQuantum
          FOR offset: CARDINAL ← 0, offset+SIZE[RunRec] UNTIL offset+SIZE[RunRec] > PagesPerQuantum*wordsPerPage
	    DO q: Run = p+offset;
	       q.rnNext ← runs;
	       runs ← q
	   ENDLOOP};
   run ← runs;
   runs ← runs.rnNext};

RunFreeProc: ENTRY PROC[run: Run] =
INLINE
  {ENABLE UNWIND => NULL;
   run.rnNext ← runs;
   runs ← run};

-- Initialization

-- Add and delete intervals

AddInterval: PUBLIC PROC[pRn: LONG POINTER TO Run, iFrom, n: RunValue] =
 {iTo: RunValue = iFrom+n;	-- not included
  rn, rnNew: Run;
  IF RTFlags.checking AND n = 0 THEN ERROR;
  
  DO
    IF (rn ← pRn↑) = NIL THEN EXIT;
    IF rn.iTo >= iFrom
     THEN  -- stop here
       {SELECT rn.iFrom FROM
          > iTo => EXIT;  -- insert before here
          = iTo => rn.iFrom ← iFrom; -- just lower iFrom
          ENDCASE =>
           {IF rn.iTo # iFrom THEN SIGNAL OverlappingInterval[];
            IF rn.rnNext # NIL AND rn.rnNext.iFrom <= iTo
	     THEN  -- merge
              {iFrom ← rn.iTo ← rn.rnNext.iTo;
               DelRun[@rn.rnNext];
               LOOP}  -- might extend further
             ELSE IF iTo > rn.iTo THEN rn.iTo ← iTo};
        RETURN}
      ELSE pRn ← @rn.rnNext;
    ENDLOOP;
  rnNew ← RunAllocProc[];	-- allocate a new RunRec
  rnNew↑ ← [iFrom: iFrom, iTo: iTo, rnNext: rn];
  pRn↑ ← rnNew};	-- insert it before rn

DeleteInterval: PUBLIC PROC[pRn: LONG POINTER TO Run, iFrom, n: RunValue] =
 {iTo: RunValue = iFrom+n;
  rn: Run;
  IF RTFlags.checking AND n = 0 THEN ERROR;
  
  UNTIL (rn ← pRn↑) = NIL
    DO
     IF rn.iTo <= iFrom
      THEN {pRn ← @rn.rnNext; LOOP}; -- not there yet
     IF (iFrom < rn.iFrom)  OR (iTo > rn.iTo)
      THEN ERROR MissingInterval[];
     IF iTo = rn.iTo
      THEN
       {IF iFrom = rn.iFrom
         THEN DelRun[pRn]	-- delete the entire run
         ELSE rn.iTo ← iFrom}  -- delete a final segment of the run
      ELSE IF iFrom = rn.iFrom
      THEN rn.iFrom ← iTo	-- delete an initial segment of the run
      ELSE  -- remove a central segment of the run
       {rn1: Run = RunAllocProc[];
        rn1↑ ← [iFrom: iTo, iTo: rn.iTo, rnNext: rn.rnNext];
        rn.iTo ← iFrom;
        rn.rnNext ← rn1};
     RETURN;
   ENDLOOP;
  ERROR MissingInterval[]};

-- Internal procedures

DelRun: PROC[pRn: LONG POINTER TO Run] =
 {rn: Run ← pRn↑; pRn↑ ← rn.rnNext; RunFreeProc[rn]};

-- Find and map intervals

FindInterval: PUBLIC PROC[pRn: LONG POINTER TO Run, n: RunValue] RETURNS[iFrom: RunValue] =
 {rn: Run;
  iTo: RunValue;
  IF RTFlags.checking AND n = 0 THEN ERROR;
  
  UNTIL (rn ← pRn↑) = NIL
    DO
     IF RTFlags.checking AND rn.iTo <= rn.iFrom THEN ERROR;
     IF rn.iTo >= (iTo ← rn.iFrom+n)
      THEN {iFrom ← rn.iFrom;
            IF iTo = rn.iTo THEN DelRun[pRn] ELSE rn.iFrom ← iTo;
            RETURN};
     pRn ← @rn.rnNext;
   ENDLOOP;
  ERROR CantFindInterval[]};

MapIntervals: PUBLIC PROC[pRn: LONG POINTER TO Run, proc: PROC[iFrom, n: RunValue]] =
 {rn: Run;
  rnNext: Run ← pRn↑;
  UNTIL (rn ← rnNext) = NIL
    DO
     rnNext ← rn.rnNext;  -- OK if proc deletes rn, not OK if merge occurs
     IF RTFlags.checking AND rn.iTo <= rn.iFrom THEN ERROR;
     proc[rn.iFrom, rn.iTo-rn.iFrom];
   ENDLOOP};


END.