stats: RECORD[

Bump: PROC[p: POINTER TO INT, delta: INT ← 1] =

INLINE {IF RTFlags.takingStatistics THEN p^ ← p^+delta};

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
Bump[@stats.nPagesAcquired, 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.