Google
 

Trailing-Edge - PDP-10 Archives - BB-T573C-DD_1986 - 10,7/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