Trailing-Edge
-
PDP-10 Archives
-
bb-x130a-sb
-
whohas.mac
There are 4 other files named whohas.mac in the archive. Click here to see a list.
TITLE WHOHAS - Hash table routines for WHO
SEARCH WHOMAC
$SETUP (WHOHAS)
Comment !
This module contains the code for the hash table that the /SUMMARY
switch uses to accumulate statistics.
!
; TABLE OF CONTENTS FOR WHOHAS
;
;
; SECTION PAGE
; 1. .HASHI - INITIALIZE HASH TABLE............................ 2
; 2. HASHS
; 2.1 SEARCH TABLE FOR ENTRY............................ 3
; 3. HASHA
; 3.1 STORE AN ENTRY IN HASH TABLE...................... 4
; 4. .HASHR
; 4.1 REHASH THE TABLE.................................. 5
; 5. .HSRTI
; 5.1 SORT THE HASH TABEL............................... 6
; 6. .HSRTE
; 6.1 FINISH UP AT END OF HASH SORT..................... 7
; 7. STORAGE................................................... 8
SUBTTL .HASHI - INITIALIZE HASH TABLE
;CALL:
; MOVEI T1,INITIAL TABLE SIZE
; MOVEI T2,ENTRY LENGTH
; PUSHJ P,.HASHI
ENTRY .HASHI
.HASHI: MOVEM T2,HREC ;SAVE ENTRY SIZE
MOVSI T3,-PRILEN ;GET LENGTH OF KNOWN PRIMES
HSHI.1: CAMLE T1,PRITAB(T3) ;FIND FIRST PRIME >+
AOBJN T3,HSHI.1 ;NONE FOUND--LOOP
JUMPGE T3,E$$HTB
MOVE T1,PRITAB(T3) ;GET THE PRIME
MOVEM T1,HLEN ;SAVE AS LENGTH OF TABLE
IMUL T1,HREC ;TIMES ENTRY SIZE
PUSHJ P,I$ALLOC## ;ALLOCATE THE CORE
MOVEM T1,HTAB ;SAVE START OF TABLE
MOVE T2,HLEN ;GET SIZE OF TABLE
IMUL T2,HREC ;TIMES ENTRYS/WORD
ADDI T2,-1(T1) ;PLUS START
MOVEM T2,HEND ;SAVE AS END OF TABLE
MOVE T1,HLEN ;GET SIZE OF TABLE
IMULI T1,^D85 ;TAKE 85%
IDIVI T1,^D100 ;..
MOVEM T1,HMAX ;AND STORE AS MAX ENTRIES
SETZM HCNT ;THE TABLE IS EMPTY
POPJ P, ;AND RETURN
$FATAL (HTB,<Hash table too big>)
PRITAB: DEC 31,41,53,73,101,149,211,307,401,503
DEC 601,701,809,907,1009,1259,1511,1753,2003
DEC 3001,3511,4001,5003,6007,7001,8009,9001,10007
DEC 12007,15013,20011,25013,30011,40009,50021
DEC 60013,70001,80021,90001,99991
PRILEN==.-PRITAB
SUBTTL HASHS -- SEARCH TABLE FOR ENTRY
;CALL:
; MOVE T1,WORD TO HASH
; PUSHJ P,HASHS
; <ERROR> ;NOT FOUND
; <NORMAL> ;T1=ADDR OF ENTRY FOUND
ENTRY .HASHS
.HASHS: MOVE T4,T1 ;COPY WORD FOR COMPARE
IDIV T1,HLEN ;APPLY HASH FUNCTION
MOVM T1,T2 ;MAGNITUDE ONLY
IMUL T1,HREC ;TIMES WORDS/ENTRY
ADD T1,HTAB ;POINT TO BEGINNING OF TABLE
HSHS.1: CAMN T4,(T1) ;SEE IF MATCHS
JRST .POPJ1## ;YES--RETURN WITH T1 POINTING
SKIPN (T1) ;SEE IF EMPTY
POPJ P, ;YES--NOT FOUND
ADD T1,HREC ;ADVANCE DOWN TABLE
CAMG T1,HEND ;STILL IN RANGE?
JRST HSHS.1 ;YES
MOVE T2,HLEN ;NO--GET SIZE
IMUL T2,HREC ;TIMES ENTRYS/RECORD
SUB T1,T2 ;WRAP AROUND
JRST HSHS.1 ;AND LOOP
SUBTTL HASHA -- STORE AN ENTRY IN HASH TABLE
;CALL:
; MOVE T1,WORD TO HASH
; PUSHJ P,HASHA
; <ERROR> ;ALREADY IN TABLE,T1=ADDR OF IT
; <NORMAL> ;T1=ADDR OF ENTRY TO STORE
ENTRY .HASHA
.HASHA: PUSHJ P,.HASHS ;FIND THE ENTRY
CAIA ;NOT FOUND--ADD
POPJ P, ;FOUND--T1 POINTS TO IT
MOVEM T4,(T1) ;STORE WORD
AOS T2,HCNT ;COUNT ENTRIES IN TABLE
CAMG T2,HMAX ;SEE IF TOO MANY
JRST .POPJ1## ;NO--JUST RETURN
PUSH P,T4 ;SAVE OLD WORD
PUSHJ P,.HASHR ;REHASH
POP P,T1 ;GET OLD WORD BACK
PUSHJ P,.HASHS ;FIND IT AGAIN
$FATAL (ENF,<Entry not found after rehash>)
JRST .POPJ1## ;AND RETURN
SUBTTL .HASHR -- REHASH THE TABLE
;CALL:
; PUSHJ P,.HASHR
.HASHR: PUSHJ P,.SAVE2## ;SAVE P1-P2
MOVE P1,HTAB ;SAVE OLD TABLE SIZE
MOVE P2,HLEN ;SAVE OLD TABLE LENGTH
AOS T1,HLEN ;ADVANCE TO NEXT SIZE
MOVE T2,HREC ;WITH SAME ENTRY SIZE
PUSHJ P,.HASHI ;INIT HASH TABLE AGAIN
HSHR.1: SKIPN T1,(P1) ;GET ENTRY
JRST HSHR.2 ;EMPTY
PUSHJ P,.HASHA ;STORE IN TABLE
JRST E$$REF ;FOUND??!!
MOVE T2,HREC ;GET ENTRY SIZE
SOJLE T2,HSHR.2 ;SKIP IF ONLY 1
ADDI T2,(T1) ;POINT TO END
HRLI T1,(P1) ;GET OLD,,NEW
BLT T1,(T2) ;MOVE EXTRA DATA
HSHR.2: SOJLE P2,HSHR.3 ;RETURN IF DONE
ADD P1,HREC ;ELSE ADVANCE TO NEXT ENTRY
JRST HSHR.1 ;AND LOOP
HSHR.3: POPJ P, ;**RETURN CORE NOW??**
$FATAL (REF,<Redundant entry found during rehash>)
SUBTTL .HSRTI -- SORT THE HASH TABEL
;CALL:
; PUSHJ P,.HSRTI
ENTRY .HSRTI
.HSRTI: MOVE T1,HCNT ;GET COUNT OF ENTRIES IN TABLE
IMUL T1,HREC ;TIMES RECORD SIZE
HRLZM T1,STAB ;SAVE LEN,,0
PUSHJ P,M$GMEM## ;ALLOCATE CORE
$FATAL (NCS,<No core for hash table sort>)
HRRM T2,STAB ;SAVE START OF TABLE
MOVE T1,HTAB ;POINT TO START OF TABLE
MOVE T2,STAB ;AND START OF SORT TABLE
MOVE T3,HLEN ;GET SIZE OF TABLE
HASS.2: SKIPN T4,(T1) ;GET KEY
JRST HASS.1 ;NONE HERE
MOVEM T4,(T2) ;STORE FOR SORT
HRRZM T1,1(T2) ;SAVE ADDR FOR SORT
ADDI T2,2 ;ADVANCE TO NEXT SORT RECORD
HASS.1: ADD T1,HREC ;ADVANCE TO NEXT HASH RECORD
SOJG T3,HASS.2 ;LOOP FOR ALL
MOVE T1,HCNT ;GET ENTRIES IN TABLE
IMULI T1,2 ;2 WORD ENTRIES
MOVNS T1 ;-N
HRLZI T1,(T1) ;-N,,0
HRR T1,STAB ;PLUS START OF TABLE
PUSHJ P,.SAVT1## ;SAVE T1
MOVE T2,[400000,,2] ;USIGN BY FIRST WORD KEY
PJRST .SORT2## ;SORT TABLE AND RETURN
SUBTTL .HSRTE -- FINISH UP AT END OF HASH SORT
;CALL:
; PUSHJ P,.HSRTE
ENTRY .HSRTE
.HSRTE: HLRZ T1,STAB ;GET LENGTH
HRRZ T2,STAB ;GET ADDRESS
PUSHJ P,M$RMEM## ;DEALLOCATE CORE
JFCL
POPJ P, ;AND RETURN
SUBTTL STORAGE
$LOW
HTAB: BLOCK 1 ;STARTING ADDR OF TABLE
HEND: BLOCK 1 ;ENDING ADDR OF TABLE
STAB: BLOCK 1 ;STARTING ADDR OF SORT TABLE
HLEN: BLOCK 1 ;ENTRIES IN TABLE
HREC: BLOCK 1 ;SIZE OF EACH ENTRY
HMAX: BLOCK 1 ;MAX TABLESIZE BEFORE REHASH
HCNT: BLOCK 1 ;ENTRIES IN TABLE NOW
END