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 ;[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 ;[2216] No match, restore acs JRST NOMACH ;[2216] Try again LMATCH: SPOP ;[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,) ;[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,) ;[1174] .ETC. (SBX,.EC!.EP,,,,W2) ;[1174] .ETC. (JMP,,,,,.ETIMF##) ;[1174] SUBTTL THE END END