Trailing-Edge
-
PDP-10 Archives
-
ap-c796e-sb
-
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 27-Feb-78
;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, 1978 BY DIGITAL EQUIPMENT CORPORATION, MAYNARD, MASS.
ENTRY TRYSYM
SEARCH LNKPAR,LNKLOW,MACTEN,UUOSYM,SCNMAC
CUSTVR==0 ;CUSTOMER VERSION
DECVER==4 ;DEC VERSION
DECMVR==0 ;DEC MINOR VERSION
DECEVR==765 ;DEC EDIT VERSION
SALL
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)
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,ILLSYM ;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,<
.ERR. (MS,,V%L,L%F,S%F,ESN,<Extended symbol not expected>)>
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,<
.ERR. (MS,,V%L,L%F,S%F,ESN)>
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
.ERR. (MS,.EC,V%L,L%I,S%I,RGS,<Rehashing Global symbol table from >)
.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,<
.ERR. (MS,,V%L,L%F,S%F,ESN)>
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
ILLSYM: .ERR. (MS,.EC,V%L,L%F,S%F,ISN,<Illegal symbol name >)
.ETC. (SBX,.EP,,,,W2)
END