SUBROUTINE HASH(KEY,MODE,KA,FOUND)
C This file: http://ftp.aset.psu.edu/pub/ger/fortran/hdk/hash.for
C
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<IQ<LEN AND 0<IR<=LEN .
      IQ=MOD(IABS(KEY),LEN2)+1
      IR=MOD(IABS(KEY),LEN)+1
      KA=IR
C-----------LOOK IN THE TABLE.
20    KT=KEYTAB(KA)
C----------CHECK FOR AN EMPTY SPACE, A DELETE ENTRY, OR A MATCH.
      IF(KT.EQ.0) GO TO 30
      IF(KT.EQ.-1) GO TO 40
      IF(KT.EQ.KEY) GO TO 60
      IC=IC+1
C---------COMPUTE ADDRESS OF NEXT PROBE.
      KA=KA+IQ
      IF(KA.GT.LEN)KA=KA-LEN
C----------SEE IF WHOLE TABLE HAS BEEN SEARCHED.
      IF(KA.NE.IR) GO TO 20
C---------THE KEY IS NOT IN THE TABLE.
30    FOUND=.FALSE.
C---------RETURN WITH KA=0 UNLES AN ENTRY HAS TO BE MADE.
      IF((MODE.EQ.2).AND.(IC.LE.LEN2) .AND.(KEY.NE.0).AND.(KEY.NE.-1))
     * GO TO 70
      KA=0
      RETURN
C-----------A DELETED ENTRY HAS BEEN FOUND.
40    IA=KA
C----------COMPUTE ADDRESS OF NEXT PROBE.
50    IA=IA+IQ
      IF(IA.GT.LEN) IA=IA-LEN
      IS=KEYTAB(IA)
C----------CHECK FOR AN EMPTY SPACE OR A COMPLETE SCAN OF THE TABLE.
      IF((IS.EQ.0) .OR.(IA.EQ.IR)) GO TO 30
C------------CHECK FOR A MISMATCH OR A DELETED ENTRY.
      IF((IS.NE.KEY).OR.(IS.EQ.-1)) GO TO 50
C----------KEY FOUND.  MOVE IT AND THE ASSOCIAATED VALUE TO SAVE PROBES
C          ON THE NEXT SEARCH FOR THE SAME KEY.
      KVTAB(KA)=KVTAB(IA)
      KEYTAB(KA)=IS
      KEYTAB(IA)=-1
C----------THE KEY IS IN THE TABLE.
60    FOUND=.TRUE.
C----------DELETE IT IF MODE=3
      IF(MODE.EQ.3) KEYTAB(KA)=-1
      RETURN
C-----------LOOK FOR THE BEST WAY TO MAKE AN ENTRY.
70    IF(IC.LE.0) GO TO 120
C----------SET DEL IF A DELETED ENTRY HAS BEEN FOUND.
      DEL=KT.NE.0
      IA=KA
      IS=0
C-----------COMPUTE THE MAXIMUM LENGTH TO SEARCH ALONG CURRENT CHAIN.
80    IX=IC-IS
C-----------COMPUTE INCREMENT JQ FOR CURRENT CHAIN.
      JQ=MOD(IABS(KEYTAB(IR)),LEN2)+1
      JR=IR
C----------LOOK ALONG THE CHAIN.
90    JR=JR+JQ
      IF(JR.GT.LEN) JR=JR-LEN
      KT=KEYTAB(JR)
C----------CHECK FOR A HOLE (AN EMPTY SPACE OR DELETED ENTRY).
      IF((KT.EQ.0).OR.(KT.EQ.-1)) GO TO 100
      IX=IX-1
      IF(IX.GT.0) GO TO 90
      GO TO 110
C----------SKIP IF THIS IS AN EMPTY SPACE AND A DELETED ENTRY HAS
C          ALREADY BEEN FOUND.
100   IF(DEL.AND.(KT.EQ.0)) GO TO 110
C------------CHECK FOR A DELETED ENTRY.
      IF(KT.NE.0) DEL=.TRUE.
C-----------SAVE LOCATION OF HOLE.
      IA=JR
      KA=IR
      IC=IC-IX
C------------MOVE DOWN TO THE NEXT CHAIN.
110   IS=IS+1
      IR=IR+IQ
      IF(IR.GT.LEN) IR=IR-LEN
C---------GO BACK IF A BETTER HOLE MIGHT STILL BE FOUND.
      IF(IC.GT.IS) GO TO 80
C---------SKIP IF THERE IS NOTHING TO MOVE.
      IF(IA.EQ.KA) GO TO 120
C---------MOVE AN OLD ENTRY AND ITS ASSOCIATED VALUE TO MAKE ROOM FOR
C         THE NEW ENTRY.
      KVTAB(IA)=KVTAB(KA)
      KEYTAB(IA)=KEYTAB(KA)
C---------ENTER THE NEW KEY, BUT NOT ITS ASSICIATED VALUE.
120   KEYTAB(KA)=KEY
      RETURN
      END