string_pool.cr

class StringPool
  getter length

  def initialize
    @buckets = Array(Array(String)?).new(11, nil)
    @length = 0
  end

  def get(str : UInt8*, len)
    rehash if @length > 5 * @buckets.length

    index = bucket_index str, len
    bucket = @buckets[index]

    if bucket
      entry = find_entry_in_bucket(bucket, str, len)
      if entry
        return entry
      end
    else
      @buckets[index] = bucket = Array(String).new
    end

    @length += 1
    entry = String.new(str, len)
    bucket.push entry
    entry
  end

  def get(str : StringIO)
    get(str.buffer, str.bytesize)
  end

  def get(str : String)
    get(str.cstr, str.bytesize)
  end

  def bucket_index(str, len)
    hash = hash(str, len)
    (hash % @buckets.length).to_i
  end

  def find_entry_in_bucket(bucket, str, len)
    bucket.each do |entry|
      if entry.length == len
        if str.memcmp(entry.cstr, len) == 0
          return entry
        end
      end
    end
    nil
  end

  def hash(str, len)
    h = 0
    str.as_enumerable(len).each do |c|
      h = 31 * h + c
    end
    h
  end

  def rehash
    new_size = calculate_new_size(@length)
    old_buckets = @buckets
    @buckets = Array(Array(String)?).new(new_size, nil)

    old_buckets.each do |bucket|
      bucket.try &.each do |entry|
        get(entry.cstr, entry.length)
      end
    end
  end

  def calculate_new_size(size)
    i = 0
    new_size = 8
    while i < Hash::HASH_PRIMES.length
      return Hash::HASH_PRIMES[i] if new_size > size
      i += 1
      new_size <<= 1
    end
    raise "Hash table too big"
  end
end