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