mirror of
https://github.com/PDP-10/stacken.git
synced 2026-03-01 01:19:17 +00:00
301 lines
9.5 KiB
Plaintext
301 lines
9.5 KiB
Plaintext
TITLE LNKHSH - SYMBOL TABLE HASH SEARCH
|
||
SUBTTL D.M.NIXON/DMN/JLd/JNG/DZN/PAH/PY/HD/RJF 5-Feb-88
|
||
|
||
|
||
;COPYRIGHT (c) DIGITAL EQUIPMENT CORPORATION 1973,1986,1988.
|
||
; 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==2417 ;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.
|
||
;2403 New corporate Copywrite statement.
|
||
;2417 Update Copywrite statement to 1988.
|
||
|
||
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
|