PDP-10 Archive: 10,7/link/lnkhsh.mac from cuspmar86binsrc_2of2

Trailing-Edge - PDP-10 Archives - cuspmar86binsrc_2of2_bb-fp63a-sb - 10,7/link/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/PAH/PY	2-OCT-85



;COPYRIGHT (c) DIGITAL EQUIPMENT CORPORATION 1974,1984,1986. ALL RIGHTS RESERVED.
;
;
;THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY BE USED AND COPIED
;ONLY  IN  ACCORDANCE  WITH  THE  TERMS  OF  SUCH LICENSE AND WITH THE
;INCLUSION OF THE ABOVE COPYRIGHT NOTICE.  THIS SOFTWARE OR ANY  OTHER
;COPIES THEREOF MAY NOT BE PROVIDED OR OTHERWISE MADE AVAILABLE TO ANY
;OTHER PERSON.  NO TITLE TO AND OWNERSHIP OF THE  SOFTWARE  IS  HEREBY
;TRANSFERRED.
;
;
;THE INFORMATION IN THIS SOFTWARE IS SUBJECT TO CHANGE WITHOUT  NOTICE
;AND  SHOULD  NOT  BE  CONSTRUED  AS A COMMITMENT BY DIGITAL EQUIPMENT
;CORPORATION.
;
;DIGITAL ASSUMES NO RESPONSIBILITY FOR THE USE OR RELIABILITY  OF  ITS
;SOFTWARE ON EQUIPMENT WHICH IS NOT SUPPLIED BY DIGITAL.


SEARCH	LNKPAR,LNKLOW,MACTEN,UUOSYM,SCNMAC
SALL

ENTRY	TRYSYM


CUSTVR==0		;CUSTOMER VERSION
DECVER==6		;DEC VERSION
DECMVR==0		;DEC MINOR VERSION
DECEVR==2276		;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).

;Start of Version 5.1
;2026	Update copyright notice.

;Start of Version 6
;2216	Handle long symbols in TRYSYM.
;2267	Fix problem with short symbol passed as long symbol.
;2275	Don't allow long symbol hash to produce zero value.
;2276	Update copyright notice.

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
	MOVE	T2,1(T1)	;[2216] Get the name or length and pointer
	TLNN	W2,770000	;[2216] Long symbol?
	 JRST	LTRY		;[2216] Yes, use long compare
	CAME	W2,T2		;[2216] Compare name
	JRST	NOMACH		;Not the same
	JRST 	MATCH

;[2216] Here for a long symbol.  Compare the entire name
;[2216] It is possible for short symbol compared against long.
;[2216] This could be OK if the long symbol is padded with zero words.

LTRY:	SPUSH <T1,P1,P2>	;[2216] Save some acs
	TLNE	T2,770000	;[2216] Is it long?
	 JRST	[MOVEI T2,1(T1)	;[2216] No, point at the symbol
		 MOVEI T1,1	;[2216] It's only one word long
		 JRST LTRY1]	;[2216] Look at the second word
	HLRZ 	T1,T2		;[2216] Get the count
	ADD	T2,GS.LB	;[2216] Absolute address of long symbol name
LTRY1:	HRLI	T2,(POINT 36,)	;[2216] Byte pointer
	MOVEI	P1,(W2)		;[2216] Get the address
	HRLI	P1,(POINT 36,)	;[2216] Make a byte pointer
	HLRZ	T4,W2		;[2216] Get the count
LTRY2:	EXTEND	T1,[CMPSN	;[2216] Compare strings
			0
			0]
	 JRST LMATCH		;[2216] A match
	SPOP <P2,P1,T1>		;[2216] No match, restore acs
	JRST NOMACH		;[2216] Try again
LMATCH: SPOP <P2,P1,T1>		;[2216] Restore acs 
	JRST MATCH		;[2216] See if defined

;INITIALIZE  FOR SEARCH

HASH:	MOVE	P3,W2		;[2216] Get short symbol or long symbol pointer
	TLNE	W2,770000	;[2216] Long symbol?
	 JRST	SHASH		;[2216] No

;[2216] Here for long symbol - Check for a short symbol in disguise
	HLRZ	T1,W2		;[2216] Count of words in symbol
	CAIN	T1,1		;[2216] Only one word long?
	 JRST	[MOVE W2,(W2)	;[2216] Yes, it's a short symbol
		 MOVE P3,W2	;[2267] Use it for hash
		 JRST SHASH]	;[2216] Treat it as such

;[2216] Here if it is a real long symbol - XOR the words
	SETZ	P3,		;[2216] Clear the hash value
	MOVNS	T1		;[2216] Make it negative for half of AOBJN
	HRLZS	T1		;[2216] Put in left half, account for first word
	HRR	T1,W2		;[2216] Address of symbol
LHASH1:	XOR	P3,(T1)		;[2216] XOR all the symbol words
	AOBJN	T1,LHASH1	

	JUMPN	P3,SHASH	;[2275] Is it zero?
	 MOVE	P3,(W2)		;[2275] Yes, just use first six characters

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
	PUSHJ	P,TRYS1H	;[2216] 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