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