-- Registration Server - Implementation of using heap and BTree as a registry.

-- [Juniper]<Grapevine>MS>Registry.mesa

-- Randy Gobbel,	20-May-81 13:03:14 
-- J. Dion,		September 10, 1979.
-- Andrew Birrell,	26-Oct-82 13:18:34 

DIRECTORY
BodyDefs	USING [maxRNameLength, RName, RNameSize, Timestamp],
HeapDefs,
Inline		USING[ LowHalf ],
PupDefs		USING [PupNameLookup],
PupStream	USING [PupAddress],
Process		USING [InitializeCondition, MsecToTicks],
ProtocolDefs,
RegistryDefs,
Time		USING [Current, Packed];

Registry: MONITOR
IMPORTS BodyDefs,  HeapDefs, Inline, PupDefs, Process, Time
EXPORTS RegistryDefs =

BEGIN

HeapObjectEnded: ERROR = CODE;

MangledHeapObject: ERROR = CODE;

Copy: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
		     writer: HeapDefs.WriterHandle] =
  -- copies one component of an entry --
   BEGIN
   bLength: CARDINAL = 64;
   buffer: ARRAY [0..bLength) OF WORD;
   length: CARDINAL ← ReadComponentLength[reader];
   WriteComponentLength[writer, length];
   WHILE length > 0
   DO used: CARDINAL = HeapDefs.HeapReadData[reader,
                          [@buffer,MIN[length,bLength]] ].used;
      length ← length - used;
      HeapDefs.HeapWriteData[writer, [@buffer,used] ];
   ENDLOOP;
   END;

Skip: PUBLIC PROC[reader: HeapDefs.ReaderHandle] =
   -- skips one component of an entry --
   BEGIN
   length: CARDINAL = ReadComponentLength[reader];
   IF length > 0 --optimisation--
   THEN HeapDefs.SetReaderOffset[reader,
                                 length + HeapDefs.GetReaderOffset[reader]];
   END;

SkipIfEmpty: PUBLIC PROC[reader: HeapDefs.ReaderHandle]
                RETURNS[empty: BOOLEAN] =
   BEGIN
   pos: HeapDefs.ObjectOffset = HeapDefs.GetReaderOffset[reader];
   length: CARDINAL = ReadComponentLength[reader];
   IF length = 0
   THEN RETURN[TRUE]
   ELSE BEGIN
        HeapDefs.SetReaderOffset[reader, pos];
        RETURN[FALSE]
        END;
   END;

WriteList: PUBLIC PROC[writer: HeapDefs.WriterHandle,
                       name: BodyDefs.RName,
                       stamp: BodyDefs.Timestamp] =
   BEGIN
   -- writes single or zero entry list, with no deletions --
   IF name = NIL
   THEN { WriteEmptyList[writer]; WriteEmptyList[writer] }
   ELSE { WriteRNameList[writer,name]; WriteStampList[writer,stamp]; };
   WriteEmptyList[writer]; WriteEmptyList[writer];
   END;

StartSublist: PUBLIC PROC RETURNS[ writer: HeapDefs.WriterHandle] =
   BEGIN
   writer ← HeapDefs.HeapStartWrite[temp];
   WriteComponentLength[writer, 0]; -- place holder --
   END;

AddNameToSublist: PUBLIC PROC[writer: HeapDefs.WriterHandle,
                              name: BodyDefs.RName] =
   BEGIN
   HeapDefs.HeapWriteRName[writer, name];
   END;

EndSublist: PUBLIC PROC[writer: HeapDefs.WriterHandle, count: CARDINAL]
                RETURNS[reader: HeapDefs.ReaderHandle] =
   BEGIN
   offset: HeapDefs.ObjectOffset ← HeapDefs.GetWriterOffset[writer];
   HeapDefs.SetWriterOffset[writer, HeapDefs.objectStart];
   WriteComponentLength[writer, Inline.LowHalf[offset-SIZE[CARDINAL]]];
   HeapDefs.SetWriterOffset[writer, offset];
   WriteComponentLength[writer, count * SIZE[BodyDefs.Timestamp]];
   BEGIN
      stamp: BodyDefs.Timestamp = MakeTimestamp[];
      THROUGH [0..count) DO WriteTimestamp[writer, stamp] ENDLOOP;
   END;
   WriteEmptyList[writer]; WriteEmptyList[writer]; -- deletions --
   BEGIN
      GetReader: PROC[obj: HeapDefs.ObjectNumber] =
         { reader ← HeapDefs.HeapStartRead[obj] };
      HeapDefs.HeapEndWrite[writer, GetReader];
   END;
   END;

EnumerateRList: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                            work: PROC[BodyDefs.RName]RETURNS[done:BOOLEAN]] =
   BEGIN
   length: CARDINAL ← ReadComponentLength[reader];
   WHILE length > 0
   DO name: BodyDefs.RName = [BodyDefs.maxRNameLength];
      [] ← HeapDefs.HeapReadRName[reader, name];
      length ← length - BodyDefs.RNameSize[name];
      IF work[name] THEN EXIT;
   ENDLOOP;
   END;

ReadPrefix: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                        name: BodyDefs.RName]
               RETURNS[type: ProtocolDefs.RNameType,
                        stamp: BodyDefs.Timestamp] =
   BEGIN
   length: CARDINAL = ReadComponentLength[reader];
   stamp ← ReadTimestamp[reader];
   [,] ← HeapDefs.HeapReadData[reader, [@type,SIZE[ProtocolDefs.RNameType]]];
   [] ← HeapDefs.HeapReadRName[reader, name];
   IF length # SIZE[ProtocolDefs.RNameType] + SIZE[BodyDefs.Timestamp] +
         BodyDefs.RNameSize[name]
   THEN ERROR MangledHeapObject;
   END;

WritePrefix: PUBLIC PROC[writer: HeapDefs.WriterHandle,
                         type: ProtocolDefs.RNameType,
                         stamp: POINTER TO BodyDefs.Timestamp,
                         name: BodyDefs.RName] =
   BEGIN
   WriteComponentLength[writer, SIZE[ProtocolDefs.RNameType] +
                                SIZE[BodyDefs.Timestamp] +
                                BodyDefs.RNameSize[name] ];
   WriteTimestamp[writer, stamp↑];
   HeapDefs.HeapWriteData[writer, [@type,SIZE[ProtocolDefs.RNameType]]];
   HeapDefs.HeapWriteRName[writer, name];
   END;

ReadPassword: PUBLIC PROC[reader: HeapDefs.ReaderHandle]
                 RETURNS [pw: ProtocolDefs.Password,
                          stamp: BodyDefs.Timestamp] =
   BEGIN
   IF ReadComponentLength[reader] # SIZE [ProtocolDefs.Password] +
        SIZE[BodyDefs.Timestamp] 
   THEN ERROR MangledHeapObject;
   stamp ← ReadTimestamp[reader];
   [] ← HeapDefs.HeapReadData [reader, [@pw, SIZE [ProtocolDefs.Password]]];
   END;

WritePassword: PUBLIC PROC[writer: HeapDefs.WriterHandle,
                           pw: ProtocolDefs.Password,
                           stamp: BodyDefs.Timestamp] =
   BEGIN
   WriteComponentLength[writer,
                     SIZE[ProtocolDefs.Password]+SIZE[BodyDefs.Timestamp]];
   WriteTimestamp[writer, stamp];
   HeapDefs.HeapWriteData [writer, [@pw, SIZE [ProtocolDefs.Password]]];
   END;

ReadConnect: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                         connect: ProtocolDefs.Connect]
                RETURNS [stamp: BodyDefs.Timestamp] =
   BEGIN
   [] ← ReadComponentLength[reader];
   stamp ← ReadTimestamp[reader];
   connect.length ← LAST[CARDINAL];
   [,] ← HeapDefs.HeapReadData[reader, [@(connect.length),SIZE[CARDINAL]] ];
   IF connect.length > connect.maxlength
   THEN ERROR MangledHeapObject;
   [] ← HeapDefs.HeapReadData [reader,
          [@(connect.text), (1+connect.length)/2] ];
   END;

WriteConnect: PUBLIC PROC[writer: HeapDefs.WriterHandle,
                          connect: ProtocolDefs.Connect,
                          stamp: BodyDefs.Timestamp] =
   BEGIN
   WriteComponentLength[writer,
       SIZE[BodyDefs.Timestamp] + SIZE[CARDINAL] + (1+connect.length)/2];
   WriteTimestamp[writer, stamp];
   HeapDefs.HeapWriteData[writer, [@(connect.length),SIZE[CARDINAL]] ];
   HeapDefs.HeapWriteData [writer,
      [@(connect.text), (1+connect.length)/2] ];
   END;

WriteStampList: PROC[writer: HeapDefs.WriterHandle,
                          stamp: BodyDefs.Timestamp] =
   BEGIN
   WriteComponentLength[writer, SIZE [BodyDefs.Timestamp]];
   WriteTimestamp[writer, stamp];
   END;

WriteRNameList: PROC[writer: HeapDefs.WriterHandle,
                          name: BodyDefs.RName] =
   BEGIN
   WriteComponentLength[writer, BodyDefs.RNameSize[name] ];
   HeapDefs.HeapWriteRName[writer, name];
   END;

WriteEmptyList: PROC[writer: HeapDefs.WriterHandle] = INLINE
   BEGIN
   zero: CARDINAL ← 0;
   HeapDefs.HeapWriteData[writer, [@zero,SIZE[CARDINAL]] ];
   END;

ReadComponentLength: PROC[reader: HeapDefs.ReaderHandle]
                     RETURNS[length: CARDINAL] = INLINE
   BEGIN
   length ← LAST[CARDINAL];
   [,] ← HeapDefs.HeapReadData[reader, [@length,SIZE[CARDINAL]] ];
   END;

WriteComponentLength: PROC[writer: HeapDefs.WriterHandle,
                           length: CARDINAL] =
   BEGIN
   HeapDefs.HeapWriteData[writer, [@length,SIZE[CARDINAL]] ];
   END;

ReadTimestamp: PROC[reader: HeapDefs.ReaderHandle]
           RETURNS [stamp: BodyDefs.Timestamp] = INLINE
   BEGIN
   [,] ← HeapDefs.HeapReadData [reader,
                                [@stamp, SIZE [BodyDefs.Timestamp]] ];
   END;

WriteTimestamp: PROCEDURE [writer: HeapDefs.WriterHandle,
                           stamp: BodyDefs.Timestamp] =
   BEGIN
   HeapDefs.HeapWriteData [writer, [@stamp, SIZE [BodyDefs.Timestamp]]];
   END;


-- single-name updates --

-- RegistryDefs.UpdateInfo: TYPE = { done, noChange, outOfDate };
--   noChange => name already (not) there (timestamp may have been altered)
--   outOfDate => better timestamp already in list

AddName: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                     name: BodyDefs.RName,
                     stamp: POINTER TO BodyDefs.Timestamp,
                     writer: HeapDefs.WriterHandle]
            RETURNS[ info: RegistryDefs.UpdateInfo ] =
   BEGIN
   memInfo: RegistryDefs.UpdateInfo =
     SingleChangeToSublist[reader, name, stamp, writer, add];
   delMemInfo: RegistryDefs.UpdateInfo =
     SingleChangeToSublist[reader, name, stamp, writer, remove];
   info ← SELECT memInfo FROM
     done => IF delMemInfo = outOfDate THEN outOfDate ELSE done,
     noChange => IF delMemInfo = noChange THEN noChange ELSE ERROR,
     outOfDate => IF delMemInfo = noChange THEN outOfDate ELSE ERROR,
     ENDCASE => ERROR;
   END;

RemoveName: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                        name: BodyDefs.RName,
                        stamp: POINTER TO BodyDefs.Timestamp,
                        writer: HeapDefs.WriterHandle]
               RETURNS[ info: RegistryDefs.UpdateInfo ] =
   BEGIN
   memInfo: RegistryDefs.UpdateInfo =
     SingleChangeToSublist[reader, name, stamp, writer, remove];
   delMemInfo: RegistryDefs.UpdateInfo =
     SingleChangeToSublist[reader, name, stamp, writer, add];
   info ← SELECT delMemInfo FROM
     done => IF memInfo = outOfDate THEN outOfDate ELSE memInfo,
     noChange => IF memInfo = noChange THEN noChange ELSE ERROR,
     outOfDate => IF memInfo = noChange THEN outOfDate ELSE ERROR,
     ENDCASE => ERROR;
   END;

SingleChangeToSublist: PROC[reader: HeapDefs.ReaderHandle,
                                   name: BodyDefs.RName,
                                   stamp: POINTER TO BodyDefs.Timestamp,
                                   writer: HeapDefs.WriterHandle,
                                   change: {add,remove} ]
                          RETURNS[ info: RegistryDefs.UpdateInfo ] =
   BEGIN
   beforeCount: CARDINAL ← 0;
   afterCount: CARDINAL ← 0;
   member: BodyDefs.RName = [BodyDefs.maxRNameLength];
   originalLength: CARDINAL = ReadComponentLength[reader];
   length: CARDINAL ← originalLength;
   lengthPos: HeapDefs.ObjectOffset = HeapDefs.GetWriterOffset[writer];
   ResetLength: PROC =
      BEGIN -- length didn't change after all --
      now: HeapDefs.ObjectOffset = HeapDefs.GetWriterOffset[writer];
      HeapDefs.SetWriterOffset[writer, lengthPos];
      WriteComponentLength[writer, originalLength];
      HeapDefs.SetWriterOffset[writer, now];
      END;
   WriteComponentLength[writer, IF change = add
                 THEN length + BodyDefs.RNameSize[name]
                 ELSE length - BodyDefs.RNameSize[name] ];
   info ← done;

   -- copy preceding names --
   WHILE length > 0
   DO [] ← HeapDefs.HeapReadRName[reader, member];
      length ← length - BodyDefs.RNameSize[member];
      SELECT CompareRNames[member, name] FROM
        less =>
          BEGIN
          HeapDefs.HeapWriteRName[writer, member];
          beforeCount ← beforeCount + 1;
          END;
        equal =>
          BEGIN
          IF change = add
          THEN { info ← noChange; HeapDefs.HeapWriteRName[writer, name] };
          EXIT
          END;
        greater =>
          BEGIN
          IF change = add
          THEN HeapDefs.HeapWriteRName[writer, name]
          ELSE info ← noChange;
          afterCount ← 1;
          HeapDefs.HeapWriteRName[writer, member];
          EXIT
          END;
      ENDCASE => ERROR;
   REPEAT
   FINISHED =>
      IF change = add
      THEN HeapDefs.HeapWriteRName[writer, name]
      ELSE info ← noChange;
   ENDLOOP;

   -- copy following names --
   WHILE length > 0
   DO [] ← HeapDefs.HeapReadRName[reader, member];
      length ← length - BodyDefs.RNameSize[member];
      HeapDefs.HeapWriteRName[writer, member];
      afterCount ← afterCount + 1;
   ENDLOOP;

   SELECT info FROM
     done => NULL;
     noChange => ResetLength[];
   ENDCASE => ERROR;

   -- stamp list length --
   WriteComponentLength[writer, 
       IF info = noChange
       THEN ReadComponentLength[reader]
       ELSE IF change = add
            THEN ReadComponentLength[reader] + SIZE[BodyDefs.Timestamp]
            ELSE ReadComponentLength[reader] - SIZE[BodyDefs.Timestamp] ];
   THROUGH [1..beforeCount]
   DO WriteTimestamp[writer, ReadTimestamp[reader] ]; ENDLOOP;
   IF change = add
   THEN BEGIN
        IF info = done
        THEN WriteTimestamp[writer, stamp↑]
        ELSE BEGIN
             prev: BodyDefs.Timestamp = ReadTimestamp[reader];
             best: BodyDefs.Timestamp;
             SELECT CompareTimestamps[stamp↑, prev ] FROM
               less => { best ← prev; info ← outOfDate };
               equal => best ← stamp↑;
               greater => best ← stamp↑;
               ENDCASE => ERROR;
             WriteTimestamp[writer, best];
             END;
        END
   ELSE IF info = noChange
        THEN NULL
        ELSE BEGIN
             prev: BodyDefs.Timestamp = ReadTimestamp[reader];
             IF CompareTimestamps[stamp↑, prev ] = less THEN info ← outOfDate;
             END;
   THROUGH [1..afterCount]
   DO WriteTimestamp[writer, ReadTimestamp[reader] ]; ENDLOOP;
   END;


-- General merge algorithm --

Inlist: TYPE = RECORD [
        RNameReader, TimestampReader: HeapDefs.ReaderHandle,
        RNameWordsLeft, TimestampWordsLeft: CARDINAL,
        RNameStart, TimestampStart: HeapDefs.ObjectOffset,
        name: BodyDefs.RName,
        stamp: BodyDefs.Timestamp,
        empty: BOOLEAN];

Outlist:TYPE = RECORD [
        RNameWriter, TimestampWriter: HeapDefs.WriterHandle,
        RNameStart: HeapDefs.ObjectOffset,
        RNameWordsUsed, TimestampWordsUsed: CARDINAL];

MergeLists: PUBLIC PROC[reader1, reader2: HeapDefs.ReaderHandle,
                        writer: HeapDefs.WriterHandle]
               RETURNS [newer1, newer2: BOOLEAN] =
   BEGIN
   -- allocate buffers for R-Names locally, to avoid FSP fragmentation --
   name1: BodyDefs.RName = [BodyDefs.maxRNameLength];
   name2: BodyDefs.RName = [BodyDefs.maxRNameLength];
   name3: BodyDefs.RName = [BodyDefs.maxRNameLength];
   name4: BodyDefs.RName = [BodyDefs.maxRNameLength];
   addlist1, addlist2, dellist1, dellist2: Inlist;
   n1, n2: BOOLEAN;
   CreateInlist [@addlist1, name1, reader1];
   CreateInlist [@dellist1, name2, reader1];
   CreateInlist [@addlist2, name3, reader2];
   CreateInlist [@dellist2, name4, reader2];
   [newer1, newer2] ←
      MergeSublists [@addlist1, @addlist2, @dellist1, @dellist2, writer];
   ResetInlist [@addlist1];
   ResetInlist [@dellist1];
   ResetInlist [@addlist2];
   ResetInlist [@dellist2];
   [n1, n2] ← 
      MergeSublists [@dellist1, @dellist2, @addlist1, @addlist2, writer];
   newer1 ← newer1 OR n1;
   newer2 ← newer2 OR n2;
   DeleteInlist [@addlist1];
   DeleteInlist [@dellist1];
   DeleteInlist [@addlist2];
   DeleteInlist [@dellist2];
END;


MergeSublists:

PROCEDURE [add1, add2, del1, del2: POINTER TO Inlist, writer: HeapDefs.WriterHandle]
RETURNS [newer1, newer2: BOOLEAN] =
BEGIN
  outlist: Outlist;
  CreateOutlist [@outlist, writer];
  newer1 ← newer2 ← FALSE;
  UNTIL CompareElements [add1, add2] = Null
  DO WHILE CompareElements [add1, add2] = Less
      DO WHILE CompareElements [del2, add1] = Less DO Get [del2] ENDLOOP;
         IF ~(CompareElements [del2, add1] = Equal
              AND Newer [del2, add1])
         THEN BEGIN Put [add1, @outlist]; newer1 ← TRUE END;
         Get [add1]
      ENDLOOP;
      IF CompareElements [add1, add2] = Equal
      THEN BEGIN
             IF Newer [add1, add2]
             THEN BEGIN Put [add1, @outlist]; newer1 ← TRUE END
             ELSE BEGIN Put [add2, @outlist]; newer2 ← TRUE END;
             Get [add1]; Get [add2]
           END;
      WHILE CompareElements [add2, add1]= Less
      DO WHILE CompareElements [del1, add2]= Less DO Get [del1] ENDLOOP;
         IF ~(CompareElements [del1, add2]= Equal
              AND Newer [del1, add2])
         THEN BEGIN Put [add2, @outlist]; newer2 ← TRUE END;
         Get [add2]
      ENDLOOP;
  ENDLOOP;
  DeleteOutlist [@outlist, writer]
END;

CreateInlist:

PROCEDURE [inlist: POINTER TO Inlist, name: BodyDefs.RName,
           reader: HeapDefs.ReaderHandle] =
BEGIN
  inlist.name ← name;
  inlist.RNameReader ← HeapDefs.CopyReader[reader];
  inlist.RNameStart ← HeapDefs.GetReaderOffset[reader];
  Skip[reader];
  inlist.TimestampReader ← HeapDefs.CopyReader [reader];
  inlist.TimestampStart ← HeapDefs.GetReaderOffset[reader];
  Skip[reader];
  inlist.RNameWordsLeft ← ReadComponentLength[inlist.RNameReader];
  inlist.TimestampWordsLeft ← ReadComponentLength[inlist.TimestampReader];
  Get[inlist];
END;

ResetInlist:
PROCEDURE [inlist: POINTER TO Inlist] =
BEGIN
  HeapDefs.SetReaderOffset[inlist.RNameReader, inlist.RNameStart];
  HeapDefs.SetReaderOffset[inlist.TimestampReader, inlist.TimestampStart];
  inlist.RNameWordsLeft ← ReadComponentLength[inlist.RNameReader];
  inlist.TimestampWordsLeft ← ReadComponentLength[inlist.TimestampReader];
  Get[inlist];
END;

DeleteInlist:

PROCEDURE [inlist: POINTER TO Inlist] =
BEGIN
  HeapDefs.HeapEndRead[inlist.RNameReader];
  HeapDefs.HeapEndRead[inlist.TimestampReader];
END;

CreateOutlist:

PROCEDURE [outlist: POINTER TO Outlist, writer: HeapDefs.WriterHandle] =
BEGIN
  outlist.RNameWriter ← writer;
  outlist.RNameStart ← HeapDefs.GetWriterOffset[writer];
  WriteComponentLength[outlist.RNameWriter, 0]--placeholder--;
  outlist.RNameWordsUsed ← 0;
  outlist.TimestampWriter ← HeapDefs.HeapStartWrite[temp];
  outlist.TimestampWordsUsed ← 0;
END;

DeleteOutlist:

PROCEDURE [outlist: POINTER TO Outlist, writer: HeapDefs.WriterHandle] =
BEGIN
  CopyToWriter: PROC [object: HeapDefs.ObjectNumber] =
    BEGIN
    reader: HeapDefs.ReaderHandle = HeapDefs.HeapStartRead [object];
    bLength: CARDINAL = 64;
    buffer: ARRAY [0..bLength) OF WORD;
    length: CARDINAL ← outlist.TimestampWordsUsed;
    WHILE length > 0
    DO used: CARDINAL = HeapDefs.HeapReadData[reader,
                          [@buffer,MIN[length,bLength]] ].used;
      length ← length - used;
      HeapDefs.HeapWriteData[writer, [@buffer,used] ];
    ENDLOOP;
    HeapDefs.HeapEndRead[reader];
    END;
  TimestampStart: HeapDefs.ObjectOffset =
      HeapDefs.GetWriterOffset[outlist.RNameWriter];
  -- write component length for RName list --
  HeapDefs.SetWriterOffset[outlist.RNameWriter, outlist.RNameStart];
  WriteComponentLength[outlist.RNameWriter, outlist.RNameWordsUsed];
  HeapDefs.SetWriterOffset[outlist.RNameWriter, TimestampStart];
  IF outlist.RNameWriter # writer THEN ERROR;
  -- write component length for timestamp list --
  WriteComponentLength[writer, outlist.TimestampWordsUsed];
  -- append timestamp list --
  HeapDefs.HeapEndWrite[outlist.TimestampWriter, CopyToWriter];
END;

Get:

PROCEDURE [inlist: POINTER TO Inlist] =
BEGIN
  IF inlist.RNameWordsLeft > 0
  THEN BEGIN
         [] ← HeapDefs.HeapReadRName [inlist.RNameReader, inlist.name];
         inlist.stamp ← ReadTimestamp [inlist.TimestampReader];
         IF inlist.TimestampWordsLeft < SIZE[BodyDefs.Timestamp]
         OR inlist.RNameWordsLeft < BodyDefs.RNameSize[inlist.name]
         THEN ERROR MangledHeapObject;
         inlist.TimestampWordsLeft ← inlist.TimestampWordsLeft -
                  SIZE[BodyDefs.Timestamp];
         inlist.RNameWordsLeft ←
                  inlist.RNameWordsLeft - BodyDefs.RNameSize[inlist.name];
         IF (inlist.TimestampWordsLeft = 0 OR inlist.RNameWordsLeft = 0)
            AND inlist.TimestampWordsLeft + inlist.RNameWordsLeft # 0
         THEN ERROR MangledHeapObject;
         inlist.empty ← FALSE;
       END
  ELSE inlist.empty ← TRUE;
END;

Put:

PROCEDURE [inlist: POINTER TO Inlist, outlist: POINTER TO Outlist] =
BEGIN
  IF inlist.empty THEN ERROR HeapObjectEnded;
  HeapDefs.HeapWriteRName [outlist.RNameWriter, inlist.name];
  outlist.RNameWordsUsed ← outlist.RNameWordsUsed + BodyDefs.RNameSize [inlist.name];
  WriteTimestamp [outlist.TimestampWriter, inlist.stamp];
  outlist.TimestampWordsUsed ← outlist.TimestampWordsUsed +
                           SIZE [BodyDefs.Timestamp];
END;

CompareElements: PROCEDURE [e1, e2: POINTER TO Inlist]
                   RETURNS [{Less, Equal, Greater, Null}] =
BEGIN
  IF e1.empty
  THEN IF e2.empty
       THEN RETURN [Null]
       ELSE RETURN [Greater]
  ELSE IF e2.empty
       THEN RETURN [Less]
       ELSE SELECT CompareRNames [e1.name, e2.name] FROM
              less => RETURN[Less];
              equal => RETURN[Equal];
              greater => RETURN[Greater];
            ENDCASE => ERROR;
END;

Newer: PROCEDURE [e1, e2: POINTER TO Inlist] RETURNS [BOOLEAN] =
   BEGIN
   RETURN [CompareTimestamps [e1.stamp, e2.stamp] = greater]
   END;

CompareRNames: PUBLIC PROC[n1, n2: BodyDefs.RName]
                  RETURNS [RegistryDefs.Comparison] =
   BEGIN
   length: CARDINAL = MIN [n1.length, n2.length];
   i: CARDINAL;
   FOR i IN [0 .. length)
   DO BEGIN
      ch1: CHARACTER = IF n1[i] IN CHARACTER['A .. 'Z] 
                       THEN (n1[i] - 'A) + 'a ELSE n1[i];
      ch2: CHARACTER = IF n2[i] IN CHARACTER['A .. 'Z] 
                       THEN (n2[i] - 'A) + 'a ELSE n2[i];
      IF ch1 < ch2 THEN RETURN [less];
      IF ch1 > ch2 THEN RETURN [greater];
      END
   ENDLOOP;
   IF n1.length < n2.length
   THEN RETURN [less]
   ELSE IF n1.length = n2.length
        THEN RETURN [equal]
        ELSE RETURN [greater];
   END;

futureLimit: CARDINAL ← 14;

CompareTimestamps: PUBLIC ENTRY PROC[t1, t2: BodyDefs.Timestamp]
                      RETURNS [RegistryDefs.Comparison] =
   BEGIN
   -- Garbage check: treat timestamps more than 14 days future as 0 --
   latest: Time.Packed =
     LOOPHOLE[ prevTime + (LONG[futureLimit] * 24) * 60 * 60 ];
   IF t1.time > latest THEN RETURN [less];
   IF t2.time > latest THEN RETURN [greater];
   IF t1.time < t2.time THEN RETURN [less];
   IF t1.time > t2.time THEN RETURN [greater];
   IF t1.net < t2.net THEN RETURN [less];
   IF t1.net > t2.net THEN RETURN [greater];
   IF t1.host < t2.host THEN RETURN [less];
   IF t1.host > t2.host THEN RETURN [greater];
   RETURN [equal]
   END;

prevTime: Time.Packed ← Time.Current[];
aWeeWhile: CONDITION;

MakeTimestamp: PUBLIC ENTRY PROCEDURE RETURNS [stamp: BodyDefs.Timestamp] =
  BEGIN
  newTime: Time.Packed;
  WHILE (newTime ← Time.Current[]) = prevTime
  DO WAIT aWeeWhile -- ensure uniqueness of timestamps -- ENDLOOP;
  stamp.net ← ThisMachine.net;
  stamp.host ← ThisMachine.host;
  stamp.time ← prevTime ← newTime;
  END;

ThisMachine: PupStream.PupAddress;


-- regPurger subroutines --

CheckStampList: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                     limit: BodyDefs.Timestamp]
              RETURNS[old: BOOLEAN] =
   BEGIN
   length: CARDINAL = ReadComponentLength[reader];
   THROUGH [0..length/SIZE[BodyDefs.Timestamp])
   DO IF CompareTimestamps[ReadTimestamp[reader], limit] = less
      THEN RETURN[TRUE];
   ENDLOOP;
   RETURN[FALSE]
   END;

FilterStampList: PUBLIC PROC[reader: HeapDefs.ReaderHandle,
                      limit: BodyDefs.Timestamp,
                      writer: HeapDefs.WriterHandle] =
   BEGIN
   namePos: HeapDefs.ObjectOffset = HeapDefs.GetWriterOffset[writer];
   nameLength: CARDINAL ← 0;
   stampLength: CARDINAL;
   stampReader: HeapDefs.ReaderHandle = HeapDefs.CopyReader[reader];
   Action: PROC[name: BodyDefs.RName] RETURNS[done:BOOLEAN] =
      BEGIN
      stamp: BodyDefs.Timestamp = ReadTimestamp[stampReader];
      done ← FALSE;
      IF CompareTimestamps[stamp, limit] # less
      THEN BEGIN
           HeapDefs.HeapWriteRName[writer, name];
           nameLength ← nameLength + BodyDefs.RNameSize[name];
           END
      ELSE stampLength ← stampLength - SIZE[BodyDefs.Timestamp];
      END;
   Skip[stampReader];
   stampLength ← ReadComponentLength[stampReader];
   WriteComponentLength[writer, 0];
   EnumerateRList[reader, Action];
   BEGIN
      newPos: HeapDefs.ObjectOffset = HeapDefs.GetWriterOffset[writer];
      HeapDefs.SetWriterOffset[writer, namePos];
      WriteComponentLength[writer, nameLength];
      HeapDefs.SetWriterOffset[writer, newPos];
   END;
   HeapDefs.HeapEndRead[stampReader];
   WriteComponentLength[writer, stampLength];
   THROUGH [0..ReadComponentLength[reader]/SIZE[BodyDefs.Timestamp])
   DO stamp: BodyDefs.Timestamp = ReadTimestamp[reader];
      IF CompareTimestamps[stamp, limit] # less
      THEN WriteTimestamp[writer, stamp];
   ENDLOOP;
   END;

PupDefs.PupNameLookup [@ThisMachine, "ME"];

Process.InitializeCondition[@aWeeWhile, Process.MsecToTicks[100]];

END.