! File: LSTPKG.BLI ! ! This work was supported by the Advanced Research ! Projects Agency of the Office of the Secretary of ! Defense (F44620-73-C-0074) and is monitored by the ! Air Force Office of Scientific Research. MODULE LSTPKG(TIMER=EXTERNAL(SIX12))= BEGIN SWITCHES NOLIST; REQUIRE COMMON.BEG; REQUIRE GTST.BEG; REQUIRE GTX.BEG; REQUIRE OVLYLO.BEG; REQUIRE LDSF.BEG; SWITCHES LIST; REQUIRE FLOW.BEG; BEGIN ! GENERAL LIST-MANIPULATION ROUTINES !---------------------------------------- ! LISTS ARE DOUBLY-LINKED AND HOMOGENEOUS AND ONE-LEVEL. THE ! FORMAT OF A LIST HEADER IS: ! 0: LLINK,,RLINK ! 1: REMOVE,,ENTER ! THE REMOVE FIELD IS AN INDEX INTO A TABLE OF VARIOUS TYPES OF ITEMS ! THAT MIGHT BE SUSPENDED FROM A PARTICULAR LIST. AT THE TIME ! OF THIS WRITING THERE ARE FOUR: ! 0: BASIC LIST -- ALL ITEMS OF SIZE 2 ! 1: BOGUS-POINTER LIST -- EACH ITEM POINTS TO A BOGUS-TYPE ! NODE AND IS ITSELF OF SIZE 2 ! 2: ITERSECT LIST -- SIZE OF ITEM IS IN "ITEMSIZEF" FIELD ! 3: RHO LIST -- ALL ITEMS OF SIZE 3 ! THE ENTER FIELD IS THE ADDRESS OF THE ROUTINE WHICH COMPUTES THE ! POSITION IN A LIST WHERE AN ITEM IS TO BE ENTERED. ! SORTED LISTS ARE ARRANGED IN DESCENDING (FROM RLINK) ORDER ! ACCORDING TO THE VALUE OF WORD #1 IN ITEM. GLOBAL ROUTINE DELINK(A)= !REMOVES ITEM A FROM LIST TO WHICH IT IS APPENDED BEGIN MAP ITEM A; A[PRVRLINK]_.A[RLINK]; A[NXTLLINK]_.A[LLINK]; A[RLINK]_A[LLINK]_.A[BASE] END; GLOBAL ROUTINE LINK(A,TOO)= !INSERTS ITEM A INTO A LIST IMMEDIATELY AFTER THE ITEM TOO BEGIN MAP ITEM A:TOO; A[PRVRLINK]_.TOO[RLINK]; TOO[NXTLLINK]_.A[LLINK]; A[LLINK]_.TOO[BASE]; TOO[RLINK]_.A[BASE] END; ROUTINE RELINK(A,TOO)= ! REMOVES ITEM A FROM ITS PRESENT LIST AND INSERTS IT AFTER TOO LINK(DELINK(.A),.TOO); GLOBAL ROUTINE EMPTY(L)= ! PREDICATE INDICATING EMPTY LIST BEGIN MAP LSTHDR L; .L[BASE] EQL .L[RLINK] END; GLOBAL ROUTINE ENLST(L,A)= ! ENTER ITEM A ON LIST L ACCORDING TO THE INSERTION DISCIPLINE ! EVOKED BY L'S ENTER ROUTINE BEGIN MAP LSTHDR L; RELINK(.A,(.L[ENTER])(.L[BASE],.A)) END; GLOBAL ROUTINE SORTENTER(L,A)= ! ! RETURNS ADDRESS OF ITEM TO THE RIGHT OF WHICH ITEM A SHOULD ! BE ENTERED ON SORTED LIST L. ! BEGIN MAP LSTHDR L; MAP ITEM A; REGISTER ITEM I,AVAL; I_.L[RLINK]; L_.L[BASE]; AVAL_.A[DATITEM(1)]; WHILE .I NEQ .L DO BEGIN IF .AVAL GEQ .I[DATITEM(1)] THEN RETURN .I[LLINK]; I_.I[RLINK] END; .I[LLINK] END; GLOBAL ROUTINE XSORTENTER(L,A)= ! ! SAME AS SORTENTER, BUT TAILORED TO LISTS OF NAME-CSPARENTS. ! BEGIN MAP LSTHDR L; MAP ITEM A; MACRO ! ALSO SEE DELAY DATA1=1,1,0,35$, ISCSP=1,1,35,1$, LST1=1,2,18,18$, LST2=1,2,0,18$; REGISTER ITEM I,DATA; I_L_.L[BASE]; DATA_.A[DATA1]; UNTIL (I_.I[RLINK]) EQL .L DO BEGIN IF .I[DATA1] LSS .DATA THEN EXITLOOP; IF .I[DATA1] EQL .DATA THEN BEGIN A[DATITEM(1)]_.I[DATITEM(1)]; A[DATITEM(2)]_.I[DATITEM(2)]; IF .A[ISCSP] THEN IF .A[LST1] NEQ 0 THEN ( A[LST2]_.A[LST1]; A[LST1]_0 ); I_.I[RLINK]; RELITEM(.I[LLINK],3); EXITLOOP END END; .I[LLINK] END; GLOBAL ROUTINE LIFOENTER(L,A)= ! ! LIKE SORTENTER EXCEPT LIFO DISCIPLINE ! (MAP LSTHDR L;.L[BASE]); GLOBAL ROUTINE MAKITEM(N)= ! MAKES UP A LIST ITEM OF SIZE N+1 WORDS (N DATA ITEMS) INITIALIZED ! TO POINT TO ITSELF BEGIN REGISTER ITEM CHUNK; CHUNK_GETSPACE(GT,.N+1); MOVECORE(N-.N,CHUNK[DATITEM(1)],.N); CHUNK[RLINK]_CHUNK[LLINK]_.CHUNK[BASE] END; GLOBAL ROUTINE MAKHDR(R,E)= ! MAKES UP A LIST HEADER WITH REMOVE AND ENTER ROUTINES R AND E ! RESPECTIVELY MAKITEM(.R^18 OR (.E AND #777777),1); GLOBAL ROUTINE MAKINTLST(SIZE,OLD,NEW)= ! ! MAKES UP AN INTERSECT-TYPE LIST OF ITEMS SIZED "SIZE+2" ! WHOSE FIRST DATA ENTRIES COME FROM OLD AND SUSPENDS THIS NEW ! LIST FROM NEW. ! INTDATITEM: ! 0: LLINK,,RLINK ! 1: FORMAL-PARENT,,#-OF-ENTRIES ! 2: ENTRY #1 ! ......... ! SIZE+1: ENTRY #SIZE ! ! CONCLUDES BY RELEASING THE OLD LIST. ! BEGIN MAP LSTHDR OLD:NEW; REGISTER LSTHDR L, ITEM CHUNK; OLD_L_.OLD[BASE]; WHILE (L_.L[RLINK]) NEQ .OLD DO BEGIN CHUNK_GETSPACE(GT,.SIZE+2); CHUNK[RLINK]_CHUNK[LLINK]_.CHUNK; CHUNK[ITEMFPARENT]_.L[ITEMFPARENT]; CHUNK[ITEMSIZEF]_.SIZE; CHUNK[INTDATITEM(1)]_.L[DATITEM(1)]; ENLST(.NEW,.CHUNK) END; RELLST(.OLD) END; GLOBAL ROUTINE RELITEM(A,ASIZE)= ! ! RELEASES ITEM A WHOSE SIZE IS ASIZE ! RELEASESPACE(GT,DELINK(.A),.ASIZE); GLOBAL ROUTINE RELLST(HDR)= ! RELEASES ALL ITEMS (AND HEADER) OF LIST HEADED BY HDR ! S IS THE TABULAR COMPUTATION DESCRIBED AT THE HEAD OF THE ! FILE FOR DETERMINING THE SIZE OF A LIST'S ITEMS. BEGIN MACRO S=CASE .HDR[REMOVE] OF SET 2; (RELEASESPACE(GT,.I[RDATITEM(1)],BASEGTNODESIZE); 2); .I[ITEMSIZEF]+2; 3 TES$; MAP LSTHDR HDR; REGISTER ITEM I,J; I_.HDR[RLINK]; HDR_.HDR[BASE]; IF .HDR EQL 0 THEN RETURN; WHILE .I NEQ .HDR DO BEGIN J_.I[RLINK]; RELEASESPACE(GT,.I,S); I_.J END; RELEASESPACE(GT,.HDR,2) END; MACRO ADDTOINTITEM(N,TOO,NEW)= ! INSERT DATA WORD OF ITEM NEW INTO N-TH ENTRY OF ITERSECT-ITEM ! TOO TOO[INTDATITEM(.N)]_.NEW[DATITEM(1)]$; GLOBAL ROUTINE SORTFINT(N,RESHDR,NXTHDR)= ! COMPUTES THE FORMAL INTERSET OF RESHDR AND NXTHDR AND LEAVES ! RESULT IN RESHDR. (I.E. RESHDR_.RESHDR /\ .NXTHDR). N IS A ! COUNT OF THE NUMBER OF ITERATIONS. ALL FORMAL INTERSECTS OF ! THE FORM: R _ N1 /\ N2 /\ N3 /\ ... /\ NK ARE COMPUTED AS: ! MAKINTLST(K,R,N1); ! INCR I FROM 2 TO K DO ! SORTFINT(I,R,N[I]); BEGIN REGISTER ITEM PRES:PNXT,VALRES,VALNXT; MAP LSTHDR RESHDR:NXTHDR; MACRO UDRES=( PRES_.PRES[RLINK]; VALRES_.PRES[ITEMFPARENT])$; MACRO UDNXT=( IF (PNXT_.PNXT[RLINK]) EQL .NXTHDR THEN VALNXT_0 ELSE VALNXT_.PNXT[ITEMFPARENT])$; PRES_RESHDR_.RESHDR[BASE]; PNXT_NXTHDR_.NXTHDR[BASE]; UDRES; UDNXT; WHILE .PRES NEQ .RESHDR DO BEGIN MACRO ITERATE=EXITBLOCK$; IF .VALRES EQL .VALNXT THEN BEGIN ADDTOINTITEM(N,PRES,PNXT); UDNXT; UDRES; ITERATE END; IF .VALRES GTR .VALNXT THEN BEGIN DO (UDRES; RELITEM(.PRES[LLINK],.PRES[PRVITEMSIZEF]); IF .PRES EQL .RESHDR THEN EXITLOOP[2]) UNTIL .VALRES LEQ .VALNXT; ITERATE END; DO UDNXT UNTIL .VALNXT LEQ .VALRES END; RELLST(.NXTHDR); .RESHDR[BASE] END; GLOBAL ROUTINE PULSELIST(ROUT,LIST,CONST)= ! CALLS ROUT(X,.CONST) WHERE X IS THE FIRST REAL ! ELEMENT OF EACH LIST ELEMENT BEGIN MAP LSTHDR LIST; BIND LEXEME LLEX=LIST; REGISTER ITEM I; LOCAL X; X_(.LLEX[LTYPF] NEQ CHIT) AND (.LLEX[LTYPF] NEQ RHOT); I_.LIST[RLINK]; WHILE .I NEQ .LLEX[ADDRF] DO BEGIN (.ROUT)(LEXOUT(GTTYP,.I[RINTDATITEM(.X)]),.CONST); I_.I[RLINK] END; END; GLOBAL ROUTINE RHOPULSE(ROUT,LIST)= ! SPECIAL KIND OF PULSELIST, CURRENTLY USED ONLY IN DELAY ON RHO LISTS BEGIN MAP LSTHDR LIST; BIND LEXEME LLEX=LIST; REGISTER ITEM I; I_.LIST[RLINK]; WHILE .I NEQ .LLEX[ADDRF] DO BEGIN (.ROUT)(LEXOUT(GTTYP,.I[RINTDATITEM(0)]),3); (.ROUT)(LEXOUT(GTTYP,.I[RINTDATITEM(1)]),3); I_.I[RLINK] END END; GLOBAL ROUTINE OLDFIXLIST(LIST)= ! TURN OFF MUSTGENCODE BITS ON ALL ALPHA, OMEGA NODES. BEGIN MAP LSTHDR LIST;BIND LEXEME LLEX=LIST; REGISTER ITEM I,GTVEC NODE; I_.LIST[RLINK]; WHILE .I NEQ .LLEX[ADDRF] DO BEGIN INCR J FROM 1 TO .I[ITEMSIZEF] DO BEGIN NODE_.I[RINTDATITEM(.J)]; NODE[MUSTGENCODE]_0 END; I_.I[RLINK] END; END; GLOBAL ROUTINE FIXLIST(LIST)= ! SETS REGF'S OF ALL CSPARENTS OF A NODE BEGIN MAP LSTHDR LIST; BIND LEXEME LLEX=LIST; REGISTER ITEM I; LOCAL GTVEC NODE:NEW,T; LOCAL X,Y; IF .LLEX[LTYPF] EQL CHIT THEN RETURN; I_.LIST[RLINK]; X_(.LLEX[LTYPF] NEQ RHOT); Y_IF .LLEX[LTYPF] EQL RHOT THEN 1 ELSE .I[ITEMSIZEF]; WHILE .I NEQ .LLEX[ADDRF] DO BEGIN REGISTER REGVAL; IF .X THEN IF .I[ITEMSIZEF] EQL 1 THEN RETURN; NODE_.I[RINTDATITEM(.X)]; REGVAL_.NODE[REGF]; INCR J FROM .X+1 TO .Y DO BEGIN NODE_.I[RINTDATITEM(.J)]; NODE_.NODE[CSPARENT]; NODE[REGF]_.REGVAL; END; I_.I[RLINK] END; END; END END