class Cdb::HashTable

In-memory hash table structure. Indexes key/value pairs in a Writer.

Public Class Methods

new() click to toggle source

Creates an empty hash table.

# File lib/cdb/writer.rb, line 69
def initialize
  @count = 0
  @slots = []
end

Public Instance Methods

bytes() click to toggle source

Returns the on-disk representation of a hash table (a serialized array of 32-bit integers representing the offset of each key/value record in the cdb file).

# File lib/cdb/writer.rb, line 84
def bytes
  @slots.map { |s| s.nil? && [0, 0] || [s.hash, s.offset] }
        .flatten
        .pack('V*')
end
capacity() click to toggle source

Returns the number of slots in the table.

# File lib/cdb/writer.rb, line 91
def capacity
  @slots.length
end
put(entry) click to toggle source

Adds a hash table entry to the table.

# File lib/cdb/writer.rb, line 75
def put(entry)
  grow if should_grow?
  @slots[find_slot(entry)] = entry
  @count += 1
end

Private Instance Methods

empty_slots(count) click to toggle source
# File lib/cdb/writer.rb, line 122
def empty_slots(count)
  [nil] * count
end
find_slot(entry) click to toggle source
# File lib/cdb/writer.rb, line 113
def find_slot(entry)
  index = initial_search_index(entry)
  until @slots[index].nil?
    raise "Duplicate key [#{entry.key}]" if @slots[index].key == entry.key
    index = (index + 1) % capacity
  end
  index
end
fullness() click to toggle source
# File lib/cdb/writer.rb, line 97
def fullness
  return 1.0 if @slots.empty?
  @count / @slots.length
end
grow() click to toggle source
# File lib/cdb/writer.rb, line 106
def grow
  entries = @slots.reject(&:nil?)
  new_cap = capacity.zero? && 2 || (capacity * 2)
  @slots = empty_slots(new_cap)
  entries.each { |entry| put(entry) }
end
initial_search_index(entry) click to toggle source
# File lib/cdb/writer.rb, line 126
def initial_search_index(entry)
  (entry.hash / Cdb::NUM_HASHTABLES) % capacity
end
should_grow?() click to toggle source
# File lib/cdb/writer.rb, line 102
def should_grow?
  fullness > Cdb::HASHTABLE_MAX_FULLNESS
end