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