home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 2 / goldfish_vol2_cd1.bin / files / dev / e / amiga_e / src / class / hash / hash.e < prev    next >
Text File  |  1992-09-02  |  2KB  |  108 lines
  1. -> hashing module
  2.  
  3. OPT MODULE
  4.  
  5. EXPORT CONST HASH_NORMAL   = 211,
  6.              HASH_MEDIUM   = 941,
  7.              HASH_HEAVY    = 3911,
  8.              HASH_HEAVIER  = 16267
  9.  
  10. EXPORT OBJECT hashtable PRIVATE
  11.   size,entries:PTR TO LONG
  12. ENDOBJECT
  13.  
  14. EXPORT OBJECT hashlink PRIVATE
  15.   next, data, len
  16. ENDOBJECT
  17.  
  18. PROC hashtable(tablesize) OF hashtable        -> constructor
  19.   DEF table:PTR TO LONG
  20.   self.entries:=NEW table[tablesize]
  21.   self.size:=tablesize
  22. ENDPROC
  23.  
  24. PROC end() OF hashtable                -> destructor
  25.   DEF p:PTR TO LONG
  26.   p:=self.entries
  27.   END p[self.size]
  28. ENDPROC
  29.  
  30. /* hashes data, then tries to find entry.
  31.    returns hashlink, hashvalue */
  32.  
  33. PROC find(data,len) OF hashtable
  34.   DEF e,s
  35.   e:=self.entries
  36.   s:=self.size
  37.   MOVEM.L D3-D7,-(A7)
  38.   MOVE.L data,D6        -> D6=data
  39.   MOVE.L e,A1           -> A1=table
  40.   MOVE.L s,D3           -> D3=tablesize
  41.   MOVEQ  #0,D1          -> D1=hashvalue
  42.   MOVEQ  #0,D0          -> D0=hashlink
  43.   MOVE.L len,D4         -> D4=len
  44.   BEQ.S  done
  45.   MOVE.L D4,D5
  46.   MOVE.L D6,A2
  47.   SUBQ.L #1,D5
  48. loop:
  49.   LSL.W  #4,D1
  50.   ADD.B  (A2)+,D1
  51.   DBRA   D5,loop
  52.   DIVU   D3,D1
  53.   SWAP   D1
  54.   EXT.L  D1
  55.   MOVE.L A1,A2          -> now find entry
  56.   MOVE.L D1,D5
  57.   LSL.L  #2,D5
  58.   ADD.L  D5,A2          -> A2 points to spot in table
  59. findd:
  60.   MOVE.L (A2),D5        -> pick next
  61.   BEQ.S  done
  62.   MOVE.L D5,A2
  63.   CMP.L  8(A2),D4       -> if lengths are unequal, don't bother
  64.   BNE.S  findd
  65.   MOVE.L 4(A2),A0       -> get pointers to both areas
  66.   MOVE.L D6,A3
  67.   MOVE.L D4,D5
  68.   SUBQ.L #1,D5
  69. compare:                -> bytewise compare
  70.   CMPM.B (A0)+,(A3)+
  71.   BNE.S  findd
  72.   DBRA   D5,compare
  73.   MOVE.L A2,D0          -> found entry
  74. done:
  75.   MOVEM.L (A7)+,D3-D7
  76. ENDPROC D0
  77.  
  78. -> add a new hashlink
  79.  
  80. PROC add(link:PTR TO hashlink,hashvalue,data,len) OF hashtable
  81.   link.next:=self.entries[hashvalue]
  82.   link.data:=data
  83.   link.len:=len
  84.   self.entries[hashvalue]:=link
  85. ENDPROC
  86.  
  87. PROC iterate(do_proc) OF hashtable
  88.   DEF a,n,p:PTR TO hashlink, depth, r=0, num=0, table:PTR TO LONG
  89.   n:=self.size
  90.   table:=self.entries
  91.   FOR a:=1 TO n
  92.     p:=table[]++
  93.     depth:=1
  94.     WHILE p
  95.       r:=r+do_proc(p, depth++)
  96.       num++
  97.       p:=p.next
  98.     ENDWHILE
  99.   ENDFOR
  100. ENDPROC r,num
  101.  
  102. PROC calc_hash_spread() OF hashtable
  103.   DEF idepth,num
  104.   idepth,num:=self.iterate({calcspread})
  105. ENDPROC IF num THEN !idepth/num ELSE 0.0
  106.  
  107. PROC calcspread(h,depth) IS depth
  108.