DIRECTORY
Basics USING[BITAND, BITXOR, LongNumber, LowHalf],
Triples;

TriplesImpl: CEDAR MONITOR IMPORTS Basics EXPORTS Triples
= BEGIN OPEN Triples;

AOHashVec: TYPE = ARRAY AOHashVecIndex OF AOHashList;  -- each ordered by att
AOHashVecIndex: TYPE = [0..AOHashVecLength);
AOHashVecLength: CARDINAL = 10000B;
AOHashList: TYPE = LIST OF AOHashTriple;
AOHashTriple: TYPE = RECORD[
triple: Triple_NIL,
aLink, oLink, vLink: AOHashList_NIL];

ItemHashVec: TYPE = ARRAY ItemHashVecIndex OF ItemHashList;
ItemHashVecIndex: TYPE = [0..ItemHashVecLength);
ItemHashVecLength: CARDINAL = 4000B;
ItemHashList: TYPE = LIST OF ItemLinkHen;
ItemLinkHen: TYPE = RECORD[hen: AOHashList,  -- unordered
henType: HenType];
HenType: TYPE = {att, obj, val};

TripleArgPattern: TYPE = {aov, aox, axv, xov, axx, xox, xxv, xxx};


ArgFault: PUBLIC ERROR[att, obj, val: Item] = CODE;

itemHashVec: REF ItemHashVec _ NEW[ItemHashVec _ ALL[NIL]];
aoHashVec: REF AOHashVec _ NEW[AOHashVec _ ALL[NIL]];


Make: PUBLIC ENTRY PROC[att, obj, val: Item] =
{ ENABLE UNWIND => NULL;
IF att = Any OR obj = Any OR val = Any THEN ERROR ArgFault[att, obj, val];
{ ahl: ItemHashList _ FindALink[att];
ohl: ItemHashList _ FindOLink[obj];
vhl: ItemHashList _ FindVLink[val];

aohi: AOHashVecIndex _ AOHash[att, obj];
aohl: AOHashList _ aoHashVec[aohi];
prev, rest: AOHashList _ NIL;

UNTIL aohl = NIL DO
t: Triple = aohl.first.triple;
IF att = t.att THEN
IF obj = t.obj AND val = t.val THEN RETURN
ELSE {prev _ aohl; aohl _ aohl.rest; LOOP}
ELSE IF LOOPHOLE[att, LONG CARDINAL] > LOOPHOLE[t.att, LONG CARDINAL] THEN
{prev _ aohl; aohl _ aohl.rest; LOOP}
ELSE EXIT;
ENDLOOP;

rest _ IF prev = NIL THEN aoHashVec[aohi] ELSE prev.rest;
aohl _ CONS[[triple: NEW[TripleRec _ [att, obj, val]],
aLink: ahl.first.hen,
oLink: ohl.first.hen,
vLink: vhl.first.hen
],
rest];
IF prev = NIL THEN aoHashVec[aohi] _ aohl ELSE prev.rest _ aohl;
ahl.first.hen _ ohl.first.hen _ vhl.first.hen _ aohl;
};
};

Foreach: PUBLIC PROC[att, obj, val: Item, proc: ForeachProc]= {
aohl: AOHashList;
ihl: ItemHashList;
index: ItemHashVecIndex_0;
pattern: TripleArgPattern=Pattern[att, obj, val];
first: BOOL_TRUE;
nextTriple: TripleRec;
Next: ENTRY PROC[] RETURNS[more: BOOLEAN_TRUE] = INLINE {
ENABLE UNWIND => NULL;
t: Triple_NIL;
IF first THEN SELECT pattern FROM
aov, aox => aohl _ aoHashVec[AOHash[att, obj]];
axv, xov, xxv => {
vhl: ItemHashList = FindVLink[val];
aohl _ vhl.first.hen;
IF aohl = NIL THEN RemoveEmptyVHen[val, vhl]; };
axx => {
ahl: ItemHashList = FindALink[att];
aohl _ ahl.first.hen;
IF aohl = NIL THEN RemoveEmptyAHen[att, ahl]; };
xox => {
ohl: ItemHashList = FindOLink[obj];
aohl _ ohl.first.hen;
IF aohl = NIL THEN RemoveEmptyOHen[obj, ohl]; };
xxx => ihl _
CONS[[hen: NIL, henType: att], itemHashVec[index -- 0 --]];
ENDCASE => ERROR;
SELECT pattern FROM
aov, aox =>
FOR aohl_IF ~first THEN aohl.rest ELSE aohl, aohl.rest UNTIL aohl=NIL DO
t_ aohl.first.triple;
IF att = t.att THEN {
IF obj = t.obj AND (pattern = aox OR val = t.val) THEN EXIT; }
ELSE IF LOOPHOLE[att, LONG CARDINAL]<=LOOPHOLE[t.att, LONG CARDINAL] THEN {
aohl _ NIL; EXIT };
ENDLOOP;
axv =>
FOR aohl_IF ~first THEN aohl.first.vLink ELSE aohl, aohl.first.vLink UNTIL aohl = NIL DO
t _ aohl.first.triple;
IF (t.att = att) THEN EXIT;
ENDLOOP;
xov =>
FOR aohl_IF ~first THEN aohl.first.vLink ELSE aohl, aohl.first.vLink UNTIL aohl = NIL DO
t _ aohl.first.triple;
IF (t.obj = obj) THEN EXIT;
ENDLOOP;
axx => IF ~first THEN aohl_aohl.first.aLink;
xox => IF ~first THEN aohl_aohl.first.oLink;
xxv => IF ~first THEN aohl_aohl.first.vLink;
xxx => {
NextIhl: INTERNAL PROC RETURNS [BOOLEAN_FALSE] = {
WHILE (ihl _ ihl.rest)#NIL DO
IF ihl.first.henType=att THEN RETURN[TRUE]; ENDLOOP; };
WHILE aohl=NIL OR (aohl_aohl.first.aLink)=NIL DO
WHILE NOT NextIhl[] DO
IF index=LAST[ItemHashVecIndex] THEN GOTO ReallyDone;
index _ index+1;
ihl _ CONS[[hen: NIL, henType: att], itemHashVec[index]];
ENDLOOP;
aohl _ LIST[[aLink: ihl.first.hen]];
REPEAT
ReallyDone=>NULL;
ENDLOOP; };
ENDCASE => ERROR;
first_FALSE;
IF aohl=NIL THEN RETURN[FALSE];
IF t=NIL THEN t_aohl.first.triple;
IF t=NIL THEN RETURN[FALSE];
nextTriple_t^; };
WHILE (Next[] AND proc[nextTriple]) DO ENDLOOP; };

Select: PUBLIC PROC[att, obj, val: Item] RETURNS[i: Item_NIL] = {
pattern: TripleArgPattern=Pattern[att, obj, val];
SelProc: ForeachProc = {
i _ SELECT pattern FROM aox=>trip.val, axv=>trip.obj, xov=>trip.att, ENDCASE=>ERROR;
RETURN[FALSE]; };
SELECT pattern FROM
aox, axv, xov => NULL;
axx => RETURN[NIL]; -- common failing is to supply a NIL candidate.
ENDCASE => ERROR ArgFault[att, obj, val];
Foreach[att, obj, val, SelProc]; };

Is: PUBLIC PROC[att, obj, val: Item _ Any] RETURNS[ans: BOOLEAN_FALSE] = {
IsProc: ForeachProc = { ans_TRUE; RETURN[FALSE]; };
Foreach[att, obj, val, IsProc]; };

SelectCandidate: PUBLIC ENTRY PROC[att: Item, objCandidate: LONG CARDINAL]
RETURNS [ obj, val: Item ] = {
OPEN Basics;
index: AOHashVecIndex = BITAND[BITXOR[Lo[att], LowHalf[objCandidate]],
LAST[AOHashVecIndex]];
aohl: AOHashList _ aoHashVec[index];
UNTIL aohl=NIL DO
t: Triple = aohl.first.triple;
IF att = t.att THEN
IF objCandidate=LOOPHOLE[t.obj, LONG CARDINAL] THEN RETURN [ t.obj, t.val ]
ELSE { aohl _ aohl.rest; LOOP }
ELSE IF LOOPHOLE[att, LONG CARDINAL] > LOOPHOLE[t.att, LONG CARDINAL]
THEN { aohl _ aohl.rest; LOOP }
ELSE EXIT; ENDLOOP;
RETURN[ NIL, NIL ]; };

Dummy1: PROC[a, b, c: Item] = {NULL};
Dummy2: PROC[a: Item] = {NULL};

Erase: PUBLIC PROC[att, obj, val: Item] = {
SELECT Pattern[att, obj, val] FROM
aov => []_SimpleErase[[att, obj, val]];
xxx => Clear[];
ENDCASE => { Foreach[att, obj, val, SimpleErase]; }; };



SimpleErase: ENTRY PROC[trip: TripleRec] RETURNS[ continue: BOOLEAN_TRUE] = {
OPEN trip;
ENABLE UNWIND => NULL;
ahl, ohl, vhl: ItemHashList;
aohi: AOHashVecIndex;
aohl, prev: AOHashList_NIL;

IF Pattern[att, obj, val] # aov THEN ERROR;

ahl _ FindALink[att];
ohl _ FindOLink[obj];
vhl _ FindVLink[val];

aohi _ AOHash[att, obj];
aohl _ aoHashVec[aohi];
prev _ NIL;

UNTIL aohl = NIL DO
c: LONG CARDINAL = LOOPHOLE[aohl.first.triple.att];
{
SELECT LOOPHOLE[att, LONG CARDINAL] FROM
=c => IF obj#aohl.first.triple.obj OR val#aohl.first.triple.val THEN GOTO Loop;
<c => EXIT;
ENDCASE-->c-- => GOTO Loop;
EXITS
Loop => { prev_aohl; aohl_aohl.rest; LOOP; }; };

IF prev = NIL THEN aoHashVec[aohi] _ aohl.rest ELSE prev.rest _ aohl.rest;

prev _ NIL;
aohl _ ahl.first.hen;
UNTIL aohl = NIL DO
IF obj = aohl.first.triple.obj AND val = aohl.first.triple.val THEN {
IF prev = NIL THEN ahl.first.hen _ aohl.first.aLink
ELSE prev.first.aLink _ aohl.first.aLink;
EXIT; }
ELSE {prev _ aohl; aohl _ aohl.first.aLink}; ENDLOOP;
prev _ NIL;
aohl _ ohl.first.hen;
UNTIL aohl = NIL DO
IF att = aohl.first.triple.att AND val = aohl.first.triple.val THEN {
IF prev = NIL THEN ohl.first.hen _ aohl.first.oLink
ELSE prev.first.oLink _ aohl.first.oLink;
EXIT; }
ELSE {prev _ aohl; aohl _ aohl.first.oLink}; ENDLOOP;
prev _ NIL;
aohl _ vhl.first.hen;
UNTIL aohl = NIL DO
IF att = aohl.first.triple.att AND obj = aohl.first.triple.obj THEN {
IF prev = NIL THEN vhl.first.hen _ aohl.first.vLink
ELSE prev.first.vLink _ aohl.first.vLink;
EXIT; }
ELSE { prev _ aohl; aohl _ aohl.first.vLink }; ENDLOOP;

EXIT; ENDLOOP;

IF ahl.first.hen = NIL THEN RemoveEmptyAHen[att, ahl];
IF ohl.first.hen = NIL THEN RemoveEmptyOHen[obj, ohl];
IF vhl.first.hen = NIL THEN RemoveEmptyVHen[val, vhl]; };

Pattern: PROC[att, obj, val: Item] RETURNS[TripleArgPattern] =
{ RETURN[IF att = Any THEN
IF obj = Any THEN
IF val = Any THEN xxx ELSE xxv
ELSE IF val = Any THEN xox ELSE xov
ELSE IF obj = Any THEN
IF val = Any THEN axx ELSE axv
ELSE IF val = Any THEN aox ELSE aov]};

Clear: ENTRY PROC =
{ ENABLE UNWIND => NULL;
FOR i: ItemHashVecIndex IN ItemHashVecIndex DO itemHashVec[i] _ NIL ENDLOOP;
FOR i: AOHashVecIndex IN AOHashVecIndex DO aoHashVec[i] _ NIL ENDLOOP;
};

FindALink: INTERNAL PROC[att: Item] RETURNS[ihl: ItemHashList] =
{ ihvi: ItemHashVecIndex = ItemHash[att];
ihl _ itemHashVec[ihvi];
UNTIL ihl = NIL DO
IF ihl.first.henType = att AND ihl.first.hen # NIL AND ihl.first.hen.first.triple.att = att THEN
RETURN[ihl]
ELSE ihl _ ihl.rest;
ENDLOOP;
itemHashVec[ihvi] _ ihl _ CONS[[hen: NIL, henType: att], itemHashVec[ihvi]];
};

FindOLink: INTERNAL PROC[obj: Item] RETURNS[ihl: ItemHashList] =
{ ihvi: ItemHashVecIndex = ItemHash[obj];
ihl _ itemHashVec[ihvi];
UNTIL ihl = NIL DO
IF ihl.first.henType = obj AND ihl.first.hen # NIL AND ihl.first.hen.first.triple.obj = obj THEN
RETURN[ihl]
ELSE ihl _ ihl.rest;
ENDLOOP;
itemHashVec[ihvi] _ ihl _ CONS[[hen: NIL, henType: obj], itemHashVec[ihvi]];
};


FindVLink: INTERNAL PROC[val: Item] RETURNS[ihl: ItemHashList] =
{ ihvi: ItemHashVecIndex = ItemHash[val];
ihl _ itemHashVec[ihvi];
UNTIL ihl = NIL DO
IF ihl.first.henType = val AND ihl.first.hen # NIL AND ihl.first.hen.first.triple.val = val THEN
RETURN[ihl]
ELSE ihl _ ihl.rest;
ENDLOOP;
itemHashVec[ihvi] _ ihl _ CONS[[hen: NIL, henType: val], itemHashVec[ihvi]];
};

RemoveEmptyAHen: INTERNAL PROC[att: Item, ahl: ItemHashList] =
{ ihvi: ItemHashVecIndex = ItemHash[att];
ihl: ItemHashList _ itemHashVec[ihvi];
prev: ItemHashList _ NIL;
IF ahl.first.henType # att THEN ERROR;
UNTIL ihl = NIL DO
IF ihl = ahl THEN
{IF prev = NIL THEN itemHashVec[ihvi] _ ihl.rest ELSE prev.rest _ ihl.rest; RETURN}
ELSE {prev _ ihl; ihl _ ihl.rest};
ENDLOOP;
ERROR;
};

RemoveEmptyOHen: INTERNAL PROC[obj: Item, ohl: ItemHashList] =
{ ihvi: ItemHashVecIndex = ItemHash[obj];
ihl: ItemHashList _ itemHashVec[ihvi];
prev: ItemHashList _ NIL;
IF ohl.first.henType # obj THEN ERROR;
UNTIL ihl = NIL DO
IF ihl = ohl THEN
{IF prev = NIL THEN itemHashVec[ihvi] _ ihl.rest ELSE prev.rest _ ihl.rest; RETURN}
ELSE {prev _ ihl; ihl _ ihl.rest};
ENDLOOP;
ERROR;
};

RemoveEmptyVHen: INTERNAL PROC[val: Item, vhl: ItemHashList] =
{ ihvi: ItemHashVecIndex = ItemHash[val];
ihl: ItemHashList _ itemHashVec[ihvi];
prev: ItemHashList _ NIL;
IF vhl.first.henType # val THEN ERROR;
UNTIL ihl = NIL DO
IF ihl = vhl THEN
{IF prev = NIL THEN itemHashVec[ihvi] _ ihl.rest ELSE prev.rest _ ihl.rest; RETURN}
ELSE {prev _ ihl; ihl _ ihl.rest};
ENDLOOP;
ERROR;
};

AOHash: INTERNAL PROC[att, obj: Item] RETURNS[AOHashVecIndex] =
{OPEN Basics; RETURN[BITAND[BITXOR[Lo[att], Lo[obj]], LAST[AOHashVecIndex]]]};

ItemHash: INTERNAL PROC[item: Item] RETURNS[ItemHashVecIndex] =
{OPEN Basics; RETURN[BITAND[BITXOR[Hi[item], Lo[item]], LAST[ItemHashVecIndex]]]};

Lo: PROC[item: Item] RETURNS [CARDINAL] = TRUSTED INLINE {
RETURN[LOOPHOLE[item, Basics.LongNumber].lo];
};

Hi: PROC[item: Item] RETURNS [CARDINAL] = TRUSTED INLINE {
RETURN[LOOPHOLE[item, Basics.LongNumber].hi];
};


END.

TriplesImpl.Mesa
Copyright Σ 1987 by Xerox Corporation.  All rights reserved.
Last Modified by Paul Rovner on 23-Apr-81 17:59:27
Last Edited by: Swinehart, June 15, 1987 3:28:59 pm PDT, Callbacks, with monitor unlocked (!)
TYPES
SIGNALS
VARIABLES
PUBLIC PROCs
PRIVATE PROCs
This here's the triple.  First, remove it from its AOHashList.
Now remove it from its item position link lists.

Attribute

Object

Value
Having erased, quit.
Swinehart, June 15, 1987 3:28:45 pm PDT
Select[Attribute, NIL, NIL] => NIL
changes to: Select

Κ3˜š
œ™Icode™<Jš
œ2™2Jš
œ]™]—J˜š
Οk	˜	Jšœœ
œœ˜2J˜J˜—Jšœ

œ
œœ˜9Jšœœ
œ	˜˜Jš
œ™—JšœœœœΟc˜MJšœœ˜,Jšœœ
˜#Jšœœœ
œ˜(šœœœ
˜Jšœœ
˜Jšœ œ˜%—J˜Jšœ
œœœ˜;Jšœœ˜0Jšœœ	˜$Jšœœœ
œ
˜)šœ
œœž˜9J˜—Jšœ	œ˜ J˜Jšœœ,˜BJ˜˜Jš
œ™—Jšœ
œ
œœ
˜3˜Jš
œ	™	—Jš	œ
œœœ
œ˜;Jš	œœ
œ
œ
œ˜5˜Jš
œ™J˜—šΟnœœ
œ
œ˜.šœœ
œœ
˜Jš
œœœœ
œ˜J˜%J˜#J˜#J˜J˜(J˜#Jšœœ
˜J˜šœœ
˜J˜šœ
˜šœ
œ
œ
˜*Jšœ!œ
˜*—šœ
œ
œœ
œœœ
œ˜JJšœ œ
˜%—Jšœ
œ
˜
—Jšœ
˜J˜—Jš	œœœ
œœ˜9šœœ
œ˜6J˜J˜J˜J˜J˜—Jšœœ
œœ˜@J˜5—J˜—J˜J˜—šŸœœ
œ+˜?Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ1˜1Jšœœ
œ
˜J˜šŸœœ
œœœ
œœ˜9Jšœ
œœ
˜Jšœ
œ
˜šœœ
œ	˜!Jš
œ/˜/˜J˜#J˜Jšœœ
œ˜0—˜J˜#Jš
œ˜Jšœœ
œ˜0—˜J˜#Jš
œ˜Jšœœ
œ˜0—š
œ˜Jšœœ#žœ˜;—Jšœœ
˜—šœ	˜˜š
œœœœœœ
˜HJ˜šœ
œ˜Jš
œ
œœœ
œ˜>—šœ
œ
œœ
œœœ
œœ˜KJšœœœ˜—Jšœ
˜——˜š
œœœœœœ
˜XJš
œ˜Jšœœ
œ
˜Jšœ
˜——˜š
œœœœœœ
˜XJš
œ˜Jšœœ
œ
˜Jšœ
˜——Jšœœœ˜,Jšœœœ˜,Jšœœœ˜,˜šŸœœ
œ
œœ
œ˜2šœœ
˜Jš
œœ
œ
œœ˜7——š	œœ
œœ
˜0šœ
œ˜Jšœœœ
œ˜5J˜Jšœœœ%˜9Jšœ
˜—Jšœœ˜$š
˜Jšœœ
˜—Jšœ˜——Jšœœ
˜—Jšœœ
˜Jš
œœ
œ
œ
œ˜Jšœœ
œ˜"Jš
œœ
œ
œ
œ˜J˜—Jšœ	œœ
œ˜2—J˜š
Ÿœœ
œœ	œ˜AJš
œ1˜1˜Jš	œœ	œ.œœ
˜TJšœ
œ˜—šœ	˜Jšœœ
˜Jšœœ
œž/˜CJšœœ˜)—Jš
œ#˜#J˜—š
Ÿœœ
œœ
œ˜JJšœœœ
œ˜3Jš
œ"˜"J˜—š
Ÿœœ

œœ
œ
˜JJšœ˜Jšœ˜šœœ
œ!˜FJšœ˜—J˜$šœœ
˜J˜šœ
˜Jšœœœ
œœ
œ˜KJšœœ˜—šœ
œ
œœ
œœœ
œ
˜EJšœœ˜—Jšœ
œœ
˜—Jšœœœ˜—J˜J˜%˜J˜—šŸœœ
œ˜+šœ˜"J˜'J˜Jšœ0˜7——˜J˜Jš
œ
™
J˜—šŸœœ
œœœ
œ˜MJšœ˜
Jšœ
œœ
˜J˜J˜Jšœœ
˜J˜Jšœœ
œ
˜+J˜J˜J˜J˜J˜J˜J˜Jšœœ
˜J˜šœœ
˜Jšœœ
œœ˜3˜
š	œ
œœ
œ˜(Jš	œœœœ
œ˜OJšœœ
˜Jšžœœ˜—š
˜Jšœ%œ˜0——J˜Jš
œ>™>Jšœœ
œœ˜JJ˜Jš
œ0™0J™J™	Jšœœ
˜Jš
œ˜šœœ
˜šœœœ˜EJšœœ
œ!˜3Jšœ%˜)Jšœ˜—Jšœ)œ
˜5—J™J™Jšœœ
˜J˜šœœ
˜šœœœ˜EJšœœ
œ!˜3Jšœ%˜)Jšœ˜—Jšœ'	œ
˜5—J™J™Jšœœ
˜J˜šœœ
˜šœœœ˜EJšœœ
œ!˜3Jšœ%˜)Jšœ˜—Jšœ*œ
˜7J˜—Jš
œ™Jšœœ
˜—J˜Jšœœ
œ˜6Jšœœ
œ˜6Jšœœ
œ˜9J˜—šŸœœœ˜>šœœ
œ˜šœ˜Jšœœœ˜Jšœ
œœœ˜#—šœ
œ˜Jšœœœ˜Jšœ
œœœ˜&J˜———šŸœœ
œ˜šœœ
œœ
˜Jš
œœœœ
œ
˜LJš
œœœœ
œ
˜F—J˜J˜—šŸ	œœ
œœ˜@˜)J˜šœœ
˜š	œœœ
œ&˜`Jšœ˜Jšœ˜—Jšœ
˜—Jšœœœ$˜L—J˜J˜—šŸ	œœ
œœ˜@˜)J˜šœœ
˜š	œœœ
œ&˜`Jšœ˜Jšœ˜—Jšœ
˜—Jšœœœ$˜L—J˜J˜J˜—šŸ	œœ
œœ˜@˜)J˜šœœ
˜š	œœœ
œ&˜`Jšœ˜Jšœ˜—Jšœ
˜—Jšœœœ$˜L—J˜J˜—šŸœœ
œ ˜>˜)J˜&Jšœœ
˜Jšœœ
œ
˜&šœœ
˜šœ˜Jšœ
œœ
œœœ
˜SJšœ˜"—Jšœ
˜—Jšœ
˜—J˜J˜—šŸœœ
œ ˜>˜)J˜&Jšœœ
˜Jšœœ
œ
˜&šœœ
˜šœ˜Jšœ
œœ
œœœ
˜SJšœ˜"—Jšœ
˜—Jšœ
˜—J˜J˜—šŸœœ
œ ˜>˜)J˜&Jšœœ
˜Jšœœ
œ
˜&šœœ
˜šœ˜Jšœ
œœ
œœœ
˜SJšœ˜"—Jšœ
˜—Jšœ
˜—J˜J˜—šŸœ
œœ˜?Jšœ
œ	œ
œ
œœ˜NJ˜—šŸœ
œ
œ˜?Jšœ
œ	œ
œ
œœ˜RJ˜—šŸœœ
œœœ
œ˜:Jšœ
œ˜-J˜—J˜šŸœœ
œœœ
œ˜:Jšœ
œ˜-J˜J˜J˜—Jšœ
˜J˜™'K™"KšœΟr™—K™—…—)Œ;Υ