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]; }; 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; 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. zTriplesImpl.Mesa Last Modified by Paul Rovner on 23-Apr-81 17:59:27 Last Edited by: Swinehart, April 3, 1987 5:10:22 pm PST, 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. Êä˜Jšœ™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˜—š Ÿœœœœ œ˜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˜J˜—…—(ô:R