Class: YTLJit::CuckooHash

Inherits:
Object show all
Defined in:
lib/ytljit/dyna_method.rb

Overview

Dynamic Method Search 

using cuckoo hashing

Constant Summary collapse

PRIMES = 
[ 
 3,
 5,
 7,
 8 + 3,
 17,
 16 + 3,
 32 + 5,
 64 + 3,
 128 + 3,
 256 + 27,
 512 + 9,
 1024 + 9,
 2048 + 5,
 4096 + 3,
 8192 + 27,
 16384 + 43,
 32768 + 3,
 65536 + 45,
 131072 + 29,
 262144 + 3,
 524288 + 21,
 1048576 + 7,
 2097152 + 17,
 4194304 + 15,
 8388608 + 9,
 16777216 + 43,
 33554432 + 35,
 67108864 + 15,
 134217728 + 29,
 268435456 + 3,
 536870912 + 11,
 1073741824 + 85,
 0
]

Instance Method Summary collapse

Constructor Details

#initialize(elements) ⇒ CuckooHash

Returns a new instance of CuckooHash.



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/ytljit/dyna_method.rb', line 46

def initialize(elements)
  es = elements.size
  @plimepos = 0
  PRIMES.each_with_index do |n, i|
    if es / 2 < n then
      @primepos = i
      break
    end
  end
  @tabsizea = PRIMES[@primepos]
  @tabsizeb = PRIMES[@primepos - 1]
  
  @value = [Array.new(@tabsizea), Array.new(@tabsizeb)]
  @key = [Array.new(@tabsizea), Array.new(@tabsizeb)]
  @hfunc = [gen_hash_function_a(@tabsizea), gen_hash_function_b(@tabsizeb)]
  fill(elements)
end

Instance Method Details

#fill(elements) ⇒ Object 



64
65
66
67
68
69
 
# File 'lib/ytljit/dyna_method.rb', line 64

def fill(elements)
  elements.each do |key, value|
    keyadd = ((key.__id__ >> 1) << 2)
    insert(keyadd, value)
  end
end

#gen_hash_function_a(size) ⇒ Object 



121
122
123
124
125
 
# File 'lib/ytljit/dyna_method.rb', line 121

def gen_hash_function_a(size)
  lambda {|v|
    (v / 20 + v) % size
  }
end

#gen_hash_function_b(size) ⇒ Object 



127
128
129
130
131
 
# File 'lib/ytljit/dyna_method.rb', line 127

def gen_hash_function_b(size)
  lambda {|v|
    ((v / 21) + v * 31) % size
  }
end

#insert(keyadd, value) ⇒ Object 



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/ytljit/dyna_method.rb', line 70

def insert(keyadd, value)
  while true
    @tabsizea.times do 
      hv = @hfunc[0].call(keyadd)
      
      vala = @value[0][hv]
      keyadda = @key[0][hv]
      @value[0][hv] = value
      @key[0][hv] = keyadd
      if vala == nil then
        return true
      end
      keyadd = keyadda
      
      hv = @hfunc[1].call(keyadd)
      valb = @value[1][hv]
      keyaddb = @key[1][hv]
      @value[1][hv] = vala
      @key[1][hv] = keyadd
      if valb == nil then
        return true
      end
      keyadd = keyaddb
      value = valb
    end
    
    rehash
  end
end

#rehash ⇒ Object 



100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/ytljit/dyna_method.rb', line 100

def rehash
  ovalue = @value
  okey = @key
  if @tabsizea == @tabsizeb then
    @primepos += 1
    @tabsizea = PRIMES[@primepos]
  else
    @tabsizeb = PRIMES[@primepos]
  end
  @value = [Array.new(@tabsizea), Array.new(@tabsizeb)]
  @key = [Array.new(@tabsizea), Array.new(@tabsizeb)]
  @hfunc = [gen_hash_function_a(@tabsizea), gen_hash_function_b(@tabsizeb)]
  [0, 1].each do |n|
    okey[n].each_with_index do |ele, i|
      if ele then
        insert(ele, ovalue[n][i])
      end
    end
  end
end