Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

! 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