C This file: http://ftp.aset.psu.edu/pub/ger/fortran/hdk/exhash.for C C TO RUN ISSUE THE COMMAND: WATFOR77 EXHASH C C==========SAMPLE DRIVER FOR BRENT'S HASHING ALGORITHM. C IF PENNSYLVANIA COUNTIES ARE USED AS AN EXAMPLE HERE, C THEN THE TABLE WOULD BE 93% LOADED. REAL U(1) CHARACTER*50 KEYV(68),VALUE INTEGER TABLEN,KEYS(68),KEYC,KEYTAB,KEYVAL LOGICAL FOUND COMMON /BRENT/TABLEN,KEYTAB(73),KEYVAL(73) DATA N/0/,NPROBE/30/ C-----------TABLE LENGTH MUST BE A PRIME NUMBER. TABLEN=73 OPEN (UNIT=50,FILE='COUNTIES.DAT',STATUS='OLD') C-----------INPUT A RANDOMLY ORDERED SET OF KEYS AND ASSOCIATED C VALUES. WRITE(6,*) 'Please press Enter to end input.' 55 WRITE(6,*) 'Enter space, 3-char key, space, < 51 chars. of data:' READ(50,1,END=99) KEYC,VALUE 1 FORMAT(A4,1X,A50) N=N+1 KEYS(N)=ABS(KEYC) KEYV(N)=VALUE GO TO 55 99 IF(N.GT.TABLEN) STOP 99 LOAD=REAL(N)/REAL(TABLEN)*100.D0 WRITE(6,4) N,TABLEN,LOAD 4 FORMAT(' ,NUMBER OF TABLE ENTRIES=',I5,' HASH TABLE SIZE=',I5, * ' LOAD FACTOR=',I3,'%') C-------------BUILD TABLE. DO 10 I=1,TABLEN 10 KEYTAB(I)=0 DO 11 I=1,N CALL HASH(KEYS(I),2,INDEX,FOUND) IF(FOUND) GO TO 11 C-------------USE SUBSCRIPT POINTERS INSTEAD OF ACTUAL ASSOCIATED C VALUES. KEYVAL(INDEX)=I 11 CONTINUE C-------------PROBE FOR NPROBE RANDOM KEYS WHICH C ARE KNOWN TO BE IN THE TABLE. WRITE(6,*) 'OUTPUT FROM ',NPROBE,' RANDOM PROBES FOLLOW...' DO 1000 NP=1,NPROBE CALL GFSR(U,1) IRAND=(1.D0*U(1))*REAL(N)+1.D0 CALL HASH(KEYS(IRAND),1,INDEX,FOUND) 998 IF(.NOT.FOUND) STOP 998 999 IF(KEYS(IRAND).NE.KEYTAB(INDEX))STOP 999 KEYI = KEYTAB(INDEX) C----------OUTPUT KEY AND ASSOCIATED VALUE. WRITE(6,3) KEYTAB(INDEX),KEYV(KEYVAL(INDEX)) 3 FORMAT(' KEY=',A4,' ASSOCIATED VALUE=',A50) 1000 CONTINUE STOP END BLOCK DATA C======================================================================= C GENERALIZED FEEDBACK SHIFT REGISTER QUASIRANDOM NUMBER GENERATOR C THIS PROGRAM SET GENERATES TOUSWORTHE U(0,1) SEQUENCES C BASED ON THE PRIMITIVE TRINOMIAL X**P+X**Q+1. C C SEE LEWIS AND PAYNE, GENERALIZED FEEDBACK SHIFT REGISTER C PSEUDORANDOM NUMBER ALGORITHM, JACM 20(3), PP456-468, JULY 1973. C C THE SEQUENCE RETURNED HERE ARE FOR P=98,Q=27,DELAY=9800 AND C DAMPING FACTOR OF 5000. THE PERIOD WILL THEN BE 2**P-1 AS C NOTED IN THE ABOVE REFERENCE. THE FIRST FIVE NUMBERS OF C THIS SEQUENCE ARE IN THE SAME PUBLICATION, FIGURE 6. C C THESE PROGRAMS ARE PORTABLE AND USASI STANDARD A LA PFORT. C THEY ASSUME IN ADDITION THAT THE OPERATORS .OR., .AND. AS C APPLIED TO LOGICAL COMPUTER WORDS OPERATE ON THE WHOLE WORD. C (THUS THIS ALGORITHM WILL NOT WORK IN WATERLOO'S WATFIV VERSION C OF FORTRAN ON THE IBM 360/370 SYSTEMS). C C C MODIFICATIONS HERE WERE ONLY TO SET UP THE GENERATOR FOR C ABOVE P,Q,DELAY AND TO ENABLE IT TO PASS THROUGH PFORT. C C USE... C CALL GFSR(U,N) C TO GENERATE A SEQUENCE, U, OF LENGTH N OF U(0,1) NUMBERS. C C CALL SAVEG(J,M) C TO RECOVER THE CURRENT GFSR PARAMETERS J AND M NECESSARY TO C RESTART GFSR. M IS AN INTEGER VECTOR OF LENGTH P. C C CALL SETG(J,M) C TO SET THE CURRENT GFSR PARAMETERS J AND M TO THE ARGUMENT C VALUES. M IS AN INTEGER VECTOR OF LENGTH P. C C FUNCTION SETR(DELAY) C IS INCLUDED FOR COMPLETENESS. IT WAS USED TO GENERATE C THE DATA STATEMENT FOR M BELOW AND IS DESCRIBED IN THE C ABOVE REFERENCE IN FIGURE 7, PAGE 462. C C THE COMMON VARIABLES... C INTSIZ - IS THE NUMBER OF BITS USED TO REPRESENT THE C LARGEST MACHINE POSITIVE INTEGER. C INTSIZ=31 - IBM 360/370, XEROX SIGMA 5/7/9, SEL SYSTEMS 85/56, C PDP 11 AND VAX FORTRAN SUPPORTING 32-BIT INTEGERS. C INTSIZ=48 - CDC 6000/7000 SERIES. C INTSIZ=35 - HONEYWELL 600/6000, PDP 10, UNIVAC 1100. C INTSIZ=39 - BURROUGHS 5700/6700/7700 C INTSIZ=15 - DATA GENERAL ECLIPSE S/200, HP 2100, PDP 11 C FORTRAN SUPPORTING 16 BIT INTEGERS. C C MAXPOS - IS THE LARGEST MACHINE POSITIVE INTEGER, NAMELY C THE NUMBER 2**INTSIZ-1. C P,Q,J,M - ARE SEQUENCE PARAMETERS DESCRIBED IN THE ABOVE C REFERENCE. C INTEGER KKKK(3),MAXPOS,INTSIZ,J,P,Q,M(98) COMMON/GFSRXX/KKKK,MAXPOS,INTSIZ,J,P,Q,M DATA MAXPOS/2147483647/,INTSIZ/31/,J/ 0/,P/98/,Q/27/ DATA M( 1),M( 2),M( 3)/ 346256726, 591599773, 1943131421/ DATA M( 4),M( 5),M( 6)/ 1173234223, 1776849374, 1119416586/ DATA M( 7),M( 8),M( 9)/ 172236044, 985756773, 1554281477/ DATA M(10),M(11),M(12)/ 1503137291, 650397619, 1618395655/ DATA M(13),M(14),M(15)/ 639939067, 1448259547, 1046853128/ DATA M(16),M(17),M(18)/ 659170036, 1034934222, 279813371/ DATA M(19),M(20),M(21)/ 326930100, 367002640, 648480182/ DATA M(22),M(23),M(24)/ 1909733845, 618563844, 845531267/ DATA M(25),M(26),M(27)/ 292262469, 299413367, 2139821356/ DATA M(28),M(29),M(30)/ 1005803337, 390139420, 1161028423/ DATA M(31),M(32),M(33)/ 2034360736, 334070487, 565633315/ DATA M(34),M(35),M(36)/ 124796253, 2104169336, 2009751844/ DATA M(37),M(38),M(39)/ 1999687407, 83223028, 1591328966/ DATA M(40),M(41),M(42)/ 646701838, 1935362333, 795013136/ DATA M(43),M(44),M(45)/ 680356918, 1771711842, 1324935502/ DATA M(46),M(47),M(48)/ 1869840308, 356745634, 1061920662/ DATA M(49),M(50),M(51)/ 614951490, 261876461, 703987800/ DATA M(52),M(53),M(54)/ 797463948, 178239686, 1641708282/ DATA M(55),M(56),M(57)/ 1539695556, 1334926802, 940547749/ DATA M(58),M(59),M(60)/ 1957646566, 1878491364, 2033904942/ DATA M(61),M(62),M(63)/ 1711106005, 2138438575, 647734238/ DATA M(64),M(65),M(66)/ 1555990485, 1210108489, 1793192836/ DATA M(67),M(68),M(69)/ 1819829578, 751843064, 345621400/ DATA M(70),M(71),M(72)/ 575445974, 1640918761, 1379191461/ DATA M(73),M(74),M(75)/ 1617832156, 542966103, 1305854952/ DATA M(76),M(77),M(78)/ 1476721677, 1466811698, 1842260101/ DATA M(79),M(80),M(81)/ 1666639833, 217007402, 685228354/ DATA M(82),M(83),M(84)/ 902087789, 32432242, 789712994/ DATA M(85),M(86),M(87)/ 702791444, 1081111755, 1572116899/ DATA M(88),M(89),M(90)/ 321512624, 644413114, 863989644/ DATA M(91),M(92),M(93)/ 1348681739, 84379947, 1955819746/ DATA M(94),M(95),M(96)/ 941474606, 984690559, 1794209263/ DATA M(97),M(98) / 1704575856, 1253913135 / END C======================================================================= SUBROUTINE GFSR(U,N) REAL U(N) INTEGER KKKK(3),MAXPOS,INTSIZ,J,P,Q,M(98) COMMON/GFSRXX/KKKK,MAXPOS,INTSIZ,J,P,Q,M IF(N.LE.0) RETURN DO 1 I=1,N J=J+1 IF(J.GT.P) J=1 K=J+Q IF(K.GT.P) K=K-P C----IEOR IS THE FORTRAN 77 EXCLUSIVE OR OF TWO INTEGERS, THAT IS: C IEOR(A,B)=A .OR. B .AND. .NOT.( A .AND. B) M(J)=IEOR(M(K),M(J)) C----NORMALIZE THE RESULT ON (0.,1.). 1 U(I)=FLOAT(M(J))/FLOAT(MAXPOS) RETURN END SUBROUTINE HASH(KEY,MODE,KA,FOUND) C===============BRENT'S HASHING ALGORITHM. C SEE CACM 16(2):105-109. C C THIS ROUTINE WILL LOOK UP AND INSERT OR DELETE C INTEGER KEYS IN THE TABLE KEYTAB. VALUES ASSOCIATED C WITH THE KEYS MAY BE STORED IN THE TABLE KVTAB. THE C ROUTINE IS DESIGNED TO BE EFFICIENT, EVEN IF THE TABLE C IS NEARLY FULL, PROVIDED MOST ENTRIES ARE LOOKED UP C SEVERAL TIMES. C PARAMETERS: C /BRENT/ COMMON BLOCK DESCRIBES: C LEN: THE TABLE LENGTH. MUST BE GIVEN AS A PRIME NUMBER C BEFORE HASH IS CALLED. NO CHECK IS MADE FOR PRIMALITY C C KEYTAB: IS GIVEN AS A LEN-VECTOR FOR STORING THE KEYS. IT C MUST BE INITIALIZED TO ALL ZEROS BEFORE THE FIRST C CALL TO HASH. C C KVTAB: IS USED BY BOTH HASH AND THE CALLING PROGRAM AS C A LEN-VECOTR OF VALUES ASSOCIATED WITH KEYS IN C THE HASH TABLE, KEYTAB. KVTAB COULD ALSO BE A C POINTER VECTOR INITIALIZED TO THE INTEGERS 1,2,...LEN C IF MULTIPLE VALUES ARE ASSOCIATED WITH EACH KEY. C (KEY,MODE,KA,FOUND): C KEY: IS GIVEN AS A POSITIVE INTEGER KEY TO BE ENTERED, C DELETED, OR PROBED FOR. C THE VALUES 0 AND -1 ARE RESERVED FOR EMPTY SPACE C OR DELETED ITEM RESPECTIVELY. C C MODE: IS GIVEN AS AN INDICATOR AS FOLLOWS... C MODE=1: MEANS LOOK UP ONLY. IF THE KEY IS IN KEYTAB, THEN C KA IS RETURNED AS THE SUBSCRIPT POINTER; OTHERWISE C KA IS RETURNED 0. THE VALUE ASSOCIATED WITH C KEYTAB(KA) IS KVTAB(KA) WHEN KA IS NOT ZERO. C MODE=2: MEANS LOOK UP AND ENTER. THIS IS USED TO BUILD C THE TABLE. OTHERWISE THE KEY IS ENTERED AT C KEYTAB(KA). KA IS RETURNED AS THE POINTER SUBSCRIPT C IN EITHER CASE, OR KA=0 IF AN ENTRY IS ATTEMPTED AND C THE TABLE IS FULL OR KA=0 IF KEY=0. UPON RETURN, C WHEN FOUND=.FALSE., THE CALLING PROGRAM MUST ENTER C THE VALUE ASSOCIATED WITH KEY WHEN MODE=2. C MODE=3: MEANS LOOK UP AND DELETE. IF THE KEY IS IN THE TABLE C IT IS DELETED AND ITS FORMER ADDRESS KA IS RETURNED. C IF THE KEY IS NOT THERE, KA=0 IS RETURNED. (THE C SUBROUTINE CAN BE SIMPLIFIED CONSIDERABLY IF KEYS C NEVER DELETED). C C KA: IS RETUNED AS THE SUBSCRIPT OF KEYTAB SUCH THAT C KEY=KEYTAB(KA) OR KA IS RETURNED AS ZERO IF KEY=0 C OR KEY IS NOT IN KEYTAB. C C FOUND: IS A LOGICAL FLAG RETURNED .TRUE. IF THE KEY WAS C FOUND IN KEYTAB; ELSE FOUND IS RETURNED .FALSE. . C LOGICAL FOUND,DEL C-----------THE COMMON STATEMENT BELOW MUST BE CHANGED TO MEET C THE PROBLEM SIZE. COMMON/BRENT/LEN,KEYTAB(73),KVTAB(73) LEN2=LEN-2 IC=-1 C--------COMPUTE ADDRESS OF FIRST PROBE(IR) AND INCREMENT(IQ). C ANY INDEPENDENT PSEUDO-RANDOM FUNCTIONS OF THE KEY MAY BE USED, C PROVIDED 0