-- 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.