PDP-10 Archive: language-sources/lnkhsh.mac from BB-D868D-BM

Trailing-Edge - PDP-10 Archives - BB-D868D-BM - language-sources/lnkhsh.mac

There are 38 other files named lnkhsh.mac in the archive. Click here to see a list.

TITLE LNKHSH - SYMBOL TABLE HASH SEARCH
SUBTTL	D.M.NIXON/DMN/JLd/JNG/DZN	24-Aug-79


;THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY ONLY BE USED
;  OR COPIED IN ACCORDANCE WITH THE TERMS OF SUCH LICENSE.
;
;COPYRIGHT (C) 1973, 1979 BY DIGITAL EQUIPMENT CORPORATION


SEARCH	LNKPAR,LNKLOW,MACTEN,UUOSYM,SCNMAC
SALL

ENTRY	TRYSYM


CUSTVR==0		;CUSTOMER VERSION
DECVER==4		;DEC VERSION
DECMVR==1		;DEC MINOR VERSION
DECEVR==1220		;DEC EDIT VERSION


SEGMENT

SUBTTL	REVISION HISTORY


;START OF VERSION 2
;135	ADD OVERLAY FACILITY
;162	CHECK FOR CALLING TRYSYM WITH 0 NAME

;START OF VERSION 2B
;271	Suppress searching Bound Globals when rehashing
;272	Continue to issue "RGS" message only if user could
;	have done something about it -- changed /HASHSIZE.
;404	Insert edit 340, which vanished.

;START OF VERSION 2C
;476	Insert missing FTOVERLAY conditionals.
;477	Count bound globals when computing HSPACE after rehashing.
;530	Get triplet flags definitions right
;557	Clean up the listing for release.

;START OF VERSION 3A
;560	Release on both TOPS-10 and TOPS-20 as LINK version 3A(560)


;START OF VERSION 4
;731	SEARCH MACTEN,UUOSYM
;765	Release on both TOPS-10 and TOPS-20 as LINK version 4(765)

;START OF VERSION 4A
;1174	Label and clean up all error messages.
;1217	Clean up the listings for release.
;1220	Release on both TOPS-10 and TOPS-20 as version 4A(1220).

SUBTTL	SYMBOL TABLE HASH SEARCH


;ONE AUXILIARY TABLE IS USED (HASHTB)
;		LH - 18 BIT HASH TOTAL FOR SYMBOL
;		RH - LOCATION OF THE WORD IN NAMTAB, RELATIVE TO
;			       THE START OF NAMTAB
;	NAMTAB - THE NAMES, IN SIXBIT (USUALLY GS.LB)

;AN ATTEMPT IS MADE TO FIND AN ENTRY MATCHING NAMWRD IN THE FOLLOWING MANNER:
;	1) HASH-TOTAL NAMWRD BY XORING ALL THE WORDS TOGETHER, THEN XORING THE
;	   HALVES OF THE RESULT.
;	2) DIVIDE THE HASH-TOTAL BY THE SIZE OF HASHTB (HT.PRM)
;	   THE QUOTIENT BECOMES Q, THE REMAINDER R(0).
;	3) IF LH HASHTB (R) IS UNEQUAL TO THE HASH-TOTAL, GO TO STEP 5.
;	4) IF THE NAMTAB ENTRY, WHOSE RELATIVE ADDRESS IS IN THE RH OF
;	   HASHTB (R), IS EQUAL TO NAMWRD, THE MATCH IS MADE
;	   AND THE ROUTINE EXITS; ELSE GO TO STEP 6.
;	5) IF HASHTB (R) IS ZERO, THERE IS NO MATCHING ENTRY.
;	6) COMPUTE A NEW R BY ADDING Q TO R.  NOTE THAT
;		R(I) = R(0) + Q*I
;	7) STEPS 3 THRU 6 ARE EXECUTED "HT.PRM" TIMES, THEN NO MORE
;	   ATTEMPTS ARE MADE.

;HERE TO SEARCH GLOBAL SYMBOL TABLE FOR AN ENTRY

;ENTET VIA	PUSHJ P,TRYSYM
;W1 = FLAGS (TESTED FOR LONG SYMBOL BY PT.EXT)
;W2 = FIRST 6 CHARACTERS OF SYMBOL NAME
;W3 = VALUE (IF NOT EXTENDED) NOT USED
;W3 = POINTER (IF EXTENDED) TO EXTENDED SYMBOL BLOCK IN GS 

;RETURNS ARE 
;+1 SYMBOL NOT IN TABLE
;+2 SYMBOL IN TABLE BUT UNDEFINED
;+3 SYMBOL IN TABLE AND DEFINED

;RETURNS WITH FOLLOWING SETUP
;P1= QUOTIENT IN SEARCH
;P2= REMAINDER IN SEARCH
;P3= HASH TOTAL
;P4= NM12SZ PRIME NUMBER WITH WHICH TO HASH
;ALSO USES T1 _ T4

TRYSYM:	SKIPGE	HSPACE		;ENOUGH SPACE IN TABLE TO MAKE IT WORTHWHILE?
	JRST	REHASH		;NO, EXPAND TABLE FIRST
	JUMPE	W2,E$$ISN	;[1174] 0 IS ILLEGAL SYMBOL
TRYS1H:	PUSHJ	P,HASH		;INITIALIZE FOR SEARCH
	JRST	TRYS1B

TRYS1A:	ADD	P2,P1		;R_R+Q
	CAML	P2,HT.PRM	;STILL INSIDE TABLE
	SUB	P2,HT.PRM	;NO INSURE THAT IT IS

TRYS1B:	MOVS	T1,@HT.PTR	;GET HASH TOTAL (AND PTR)
	CAIN	P3,(T1)		;IS THIS THE ONE WE WANT?
	JRST	COMPAR		;MAYBE, CHECK THE SYMBOL NAME

	JUMPE	T1,NOFIND	;EXIT IF NULL ENTRY IN HASHTB

NOMACH:	SOJG	P4,TRYS1A	;YES, LOOP
				;TRIED ALL THE TABLE - YOU LOSE
NOFIND:
IFN FTOVERLAY,<
	SKIPGE	BG.SCH		;ANY BOUND GLOBALS WE CAN LOOK AT?
	JRST	TRY.BG##	;YES, TRY THEM
>
	POPJ	P,		;NON-SKIP RETURN

MATCH:	HRL	P2,P1		;SAVE Q IN R
	MOVE	P1,T1		;GET ADDRESS OF SYMBOL
	MOVE	T1,(P1)		;GET PRIMARY FLAGS
	TXNN	T1,PS.REQ!PS.UDF	;SEE IF DEFINED YET
CPOPJ2:	AOS	(P)		;YES
CPOPJ1:	AOS	(P)		;SKIP RETURN
CPOPJ:	POPJ	P,

COMPAR:	SKIPGE	HSPACE		;IF NO SPACE IN TABLE
	JRST	NOMACH		;WE ARE REHASHING ONLY

	HLRZ	T1,T1		;GET ADDRESS OF SYMBOL BLOCK
	ADD	T1,NAMLOC	;LOCATED IN CORE
	CAME	W2,1(T1)	;COMPARE FIRST 6 CHAR OF NAME
	JRST	NOMACH		;NOT THE SAME  KEEP TRYING
				;TEST FOR LONG SYMBOL
	MOVE	T2,0(T1)	;GET FLAGS
	TXNN	T2,PT.EXT	;EXTENDED (MUST BE IF LONG)
	JRST	MATCH		;NO
	MOVE	T2,.L(T1)	;GET NEXT TRIPLET FLAGS
	TXNE	T2,S.SYM	;MUST BE SYMBOL TYPE
	TXNN	T2,S.LNM	;AND EXTENDED NAME AT THAT
	JRST	MATCH		;NO, WE'VE GOT IT ALL
IFE .EXSYM,<
E$$ESN::.ERR.	(MS,,V%L,L%F,S%F,ESN,<Extended symbol not expected>) ;[1174]
>
IFN .EXSYM,<
	MOVE	T2,W3		;GET LONG SYMBOL POINTER
LCOMP0:	ADDI	T1,.L		;ADVANCE
	ADDI	T2,.L
	MOVE	T3,(T1)		;FLAGS
	MOVE	T4,(T2)		;DITTO
	TXNE	T3,S.SYM	;MUST BE SYMBOL TYPE
	TXNN	T3,S.LNM	;AND NAME
	JRST	[TXNE	T4,S.SYM	;2ND SYMBOL SAME TESTS
		TXNN	T4,S.LNM
		JRST	MATCH		;BOTH FINISHED
		JRST	NOMACH]		;NOT BOTH DONE
	TXNE	T4,S.SYM
	TXNN	T4,S.LNM
	JRST	NOMACH		;2ND NOT SAME LENGTH
	DMOVE	T3,1(T1)	;GET SYMBOL NAME
	CAMN	T3,1(T2)	;COMPARE
	CAME	T4,2(T2)
	JRST	NOMACH		;FAILED
	MOVE	T3,0(T1)	;GET FLAGS BACK
	MOVE	T4,0(T2)
	TXNE	T3,S.LST	;TEST FOR LAST TRIPLET
	JRST	[TXNN	T4,S.LST	;YES, TRY OTHER
		JRST	NOMACH		;NOT BOTH
		JRST	MATCH]		;BOTH
	TXNE	T4,S.LST	;LAST FOR 2ND?
	JRST	NOMACH		;YES, SO DIF LENGTH
	JRST	LCOMP0		;KEEP ON TRYING
>;END OF IFN .EXSYM

;INITIALIZE  FOR SEARCH

HASH:	MOVE	P3,W2		;GET FIRST 6 CHARS.
	TXNN	W1,PT.EXT	;LONG SYMBOL?
	JRST	SHASH		;NO
IFE .EXSYM,<
E02ESN::.ERR.	(MS,,V%L,L%F,S%F,ESN) ;[1174]
>
IFN .EXSYM,<
	MOVE	T1,W3		;GET POINTER
LHASH:	ADDI	T1,.L		;ADVANCE
	MOVE	T2,0(T1)	;GET FLAGS
	TXNE	T2,S.SYM	;SYMBOL TYPE
	TXNN	T2,S.LNM	;AND NAME
	JRST	SHASH		;GOT IT ALL
	XOR	P3,1(T1)	;FOLD IN
	XOR	P3,2(T1)
	TXNN	T2,S.LST	;DONE IF END
	JRST	LHASH		;KEEP GOING
>;END OF IFN .EXSYM

SHASH:	HLRZ	P1,P3
	HRRZ	P3,P3
	CAME	P1,P3		;WE DON'T WANT 0
	XORB	P1,P3
	MOVE	P4,HT.PRM	;ONLY 18 BITS AT MOST
	IDIVI	P1,(P4)		;REMAINDER IN P1
	JUMPE	P1,[AOJA P1,CPOPJ]	;ENSURE P1 NEVER ZERO
	CAIGE	P1,(P4)		;IS QUOTIENT LARGER THAN PRIME?
	POPJ	P,		;NO, RETURN
	SUBI	P1,(P4)		;STEP DOWN AND TRY AGAIN
	JRST	.-4		;ONLY HAPPENS OF PRIME L.T. ^D500

;HERE TO RE-HASH THE GLOBAL TABLE

REHASH:
IFN FTOVERLAY,<
	PUSH	P,BG.SCH	;REMEMBER IF BG EXITS
	SETZM	BG.SCH		;SUPPRESS SEARCHING IT
> ;END IFN FTOVERLAY
	PUSH	P,W1		;SAVE CURRENT SYMBOL INFO
	PUSH	P,W2
	PUSH	P,W3
	PUSH	P,R3		;AND A WORK ACC
	MOVN	R3,HT.PRM	;GET NUMBER
	HRLZ	R3,R3		;FIRST PART (LHS) OF AOBJN POINTER
	PUSH	P,HT.PRM	;SAVE OLD SIZE
	MOVE	T1,HT.PRM	;GET PREV
	LSH	T1,-1		;GET 50% OF IT
	SUBI	T1,^D50		;ALLOW SOME LEEWAY
	ADDM	T1,HT.PRM	;SO WE GET NEXT PRIME 50% LARGER
	PUSHJ	P,NPRIME##	;GET NEXT PRIME NUMBER FOR HASH SIZE
	MOVE	T1,GSYM		;SEE IF INITIAL /HASHSIZE:
	SUB	T1,@GS.LB	;YES IF SAME NUMBER
	JUMPE	T1,REHSH0	;SO DON'T TELL USER
	MOVE	T1,0(P)		;PUT OLD SIZE HERE FOR MESSAGE
E$$RGS::.ERR.	(MS,.EC,V%L,L%I,S%I,RGS,<Rehashing global symbol table from >) ;[1174]
	.ETC.	(DEC,.EC!.EP,,,,T1)
	.ETC.	(STR,.EC,,,,,< to >)
	.ETC.	(DEC,.EP,,,,HT.PRM)
REHSH0:	MOVE	T2,HT.PRM	;GET NEW NUMBER
	ADDI	T2,.L-1
	IDIVI	T2,.L
	IMULI	T2,.L
	PUSHJ	P,GS.GET##	;GET SPACE
	HRR	R3,HT.PTR	;COMPLETE AOBJN POINTER TO OLD ARRAY
	PUSH	P,HT.PTR	;SAVE OLD POSITION SO WE CAN GIVE IT BACK
	HRRM	T1,HT.PTR	;NEW TABLE OF HASH TOTALS & POINTERS

REHSH1:	SKIPN	T1,(R3)		;GET POINTER
	JRST	REHSH3		;NOTHING THERE
	PUSH	P,T1		;SAVE IT
	ADD	T1,NAMLOC	;RELOCATE
	TMOVE	W1,0(T1)	;GET FLAGS, SYMBOL, VALUE
	TXNN	W1,PT.EXT	;EXTENDED SYMBOL?
	JRST	REHSH2		;NO
	MOVE	T2,.L(T1)	;YES, BUT WE ONLY CARE ABOUT LONG NAMES HERE
	TXNE	T2,S.SYM
	TXNN	T2,S.LNM	;SO IGNORE COMMON, ETC
	JRST	[TXZ	W1,PT.EXT	;NOT EXTENDED NAME
		JRST	REHSH2]		;SO REMOVE FLAG
IFE .EXSYM,<
E03ESN::.ERR.	(MS,,V%L,L%F,S%F,ESN) ;[1174]
>
	HRRZ	W3,T1		;POINT TO SYMBOL
REHSH2:	PUSHJ	P,TRYS1H	;HASH WITH NEW SIZE AND INSERT IN TABLE
	POP	P,T1		;OLD POINTER
	HRL	T1,P3		;NEW HASH TOTAL
	MOVEM	T1,@HT.PTR	;STORE IN TABLE
REHSH3:	AOBJN	R3,REHSH1	;GET NEXT
	POP	P,T1		;GET LOCATION OF OLD TABLE
	HRRZ	T1,T1		;REMOVE INDEX IN LHS
	POP	P,T2		;AND SIZE
	ADDI	T2,.L-1		;BUT PUT BACK AS MULTIPLE OF .L
	IDIVI	T2,.L
	IMULI	T2,.L
	PUSHJ	P,GS.RET##	;GIVE IT BACK
	POP	P,R3		;RESTORE ACCS
	POP	P,W3		;RESTORE OLD SYMBOL
	POP	P,W2
	POP	P,W1
IFN FTOVERLAY,<
	POP	P,BG.SCH	;REENABLE BOUND GLOBAL SEARCH
> ;END IFN FTOVERLAY
	MOVE	T1,HT.PRM	;GET NEW SIZE
	IMUL	T1,HSFACT	;SEE HOW FULL IS FULL
	IDIVI	T1,^D100
	SUB	T1,GSYM		;MINUS WHATS THERE ALREADY
IFN FTOVERLAY,<
	SUB	T1,BSYM		;COUNT BOUND GLOBALS IN THIS TABLE
> ;END IFN FTOVERLAY
	MOVEM	T1,HSPACE	;RESET  SPACE
	JRST	TRYSYM		;AND TRY AGAIN

E$$ISN::.ERR.	(MS,.EC,V%L,L%F,S%F,ISN,<Illegal symbol name >) ;[1174]
	.ETC.	(SBX,.EC!.EP,,,,W2) ;[1174]
	.ETC.	(JMP,,,,,.ETIMF##) ;[1174]

SUBTTL	THE END


	END