Class: FastExists::Probabilistic::Cuckoo

Inherits:
Object
  • Object
show all
Defined in:
lib/fast_exists/probabilistic/cuckoo.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(capacity: 10_000, bucket_size: 4, max_kicks: 500) ⇒ Cuckoo

Returns a new instance of Cuckoo.



11
12
13
14
15
16
17
18
19
20
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 11

def initialize(capacity: 10_000, bucket_size: 4, max_kicks: 500)
  @capacity = capacity
  @bucket_size = bucket_size
  @max_kicks = max_kicks
  @num_buckets = (capacity.to_f / bucket_size).ceil
  @num_buckets = 1 if @num_buckets < 1
  @buckets = Array.new(@num_buckets) { [] }
  @count = 0
  @mutex = Mutex.new
end

Instance Attribute Details

#bucket_size ⇒ Object (readonly)

Returns the value of attribute bucket_size.



9
10
11
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 9

def bucket_size
  @bucket_size
end

#capacity ⇒ Object (readonly)

Returns the value of attribute capacity.



9
10
11
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 9

def capacity
  @capacity
end

#count ⇒ Object (readonly)

Returns the value of attribute count.



9
10
11
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 9

def count
  @count
end

#fingerprint_size ⇒ Object (readonly)

Returns the value of attribute fingerprint_size.



9
10
11
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 9

def fingerprint_size
  @fingerprint_size
end

Instance Method Details

#add(element) ⇒ Object 



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 22

def add(element)
  fp = fingerprint(element.to_s)
  i1 = hash_index(element.to_s)
  i2 = alt_index(i1, fp)

  @mutex.synchronize do
    if @buckets[i1].size < @bucket_size
      @buckets[i1] << fp
      @count += 1
      return true
    end

    if @buckets[i2].size < @bucket_size
      @buckets[i2] << fp
      @count += 1
      return true
    end

    # Kicking eviction loop
    curr_idx = rand(2) == 0 ? i1 : i2
    curr_fp = fp

    @max_kicks.times do
      evicted_fp = @buckets[curr_idx][rand(@buckets[curr_idx].size)]
      idx_in_bucket = @buckets[curr_idx].index(evicted_fp)
      @buckets[curr_idx][idx_in_bucket] = curr_fp

      curr_fp = evicted_fp
      curr_idx = alt_index(curr_idx, curr_fp)

      if @buckets[curr_idx].size < @bucket_size
        @buckets[curr_idx] << curr_fp
        @count += 1
        return true
      end
    end

    raise CapacityExceededError, "Cuckoo filter is full"
  end
end

#clear ⇒ Object 



92
93
94
95
96
97
98
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 92

def clear
  @mutex.synchronize do
    @buckets.each(&:clear)
    @count = 0
  end
  true
end

#contains?(element) ⇒ Boolean

Returns:

  • (Boolean) 


63
64
65
66
67
68
69
70
71
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 63

def contains?(element)
  fp = fingerprint(element.to_s)
  i1 = hash_index(element.to_s)
  i2 = alt_index(i1, fp)

  @mutex.synchronize do
    @buckets[i1].include?(fp) || @buckets[i2].include?(fp)
  end
end

#delete(element) ⇒ Object 



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 73

def delete(element)
  fp = fingerprint(element.to_s)
  i1 = hash_index(element.to_s)
  i2 = alt_index(i1, fp)

  @mutex.synchronize do
    if (idx = @buckets[i1].index(fp))
      @buckets[i1].delete_at(idx)
      @count -= 1
      return true
    elsif (idx = @buckets[i2].index(fp))
      @buckets[i2].delete_at(idx)
      @count -= 1
      return true
    end
  end
  false
end

#stats ⇒ Object 



100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/fast_exists/probabilistic/cuckoo.rb', line 100

def stats
  @mutex.synchronize do
    {
      type: :cuckoo,
      inserted_items: @count,
      capacity: @capacity,
      buckets: @num_buckets,
      bucket_size: @bucket_size
    }
  end
end