Blog #1 : Julia Season of Code

mutable struct RobinDict{K,V} <: AbstractDict{K,V}
    #there is no need to maintain an table_size as an additional variable
    slots::Array{UInt8,1} # indicator, to be used later on
    keys::Array{K,1}
    vals::Array{V,1}
    dibs::Array{Int,1} # distance to initial bucket - critical for implementation
    count::Int
    totalcost::Int
    maxprobe::Int    # length of longest probe
    idxfloor::Int

    function RobinDict{K, V}() where {K, V}
        n = 16 # default size of an empty Dict in Julia
        new(zeros(UInt, n), Vector{K}(undef, n), Vector{V}(undef, n), zeros(Int, n), 0, 0, 0, 0)
    end

    function RobinDict{K, V}(d::RobinDict{K, V}) where {K, V}
        new(copy(d.slots), copy(d.keys), copy(d.vals), copy(d.dibs), d.count, d.totalcost, d.maxprobe, d.idxfloor)
    end

    function RobinDict{K, V}(slots, keys, vals, dibs, count, totalcost, maxprobe, idxfloor) where {K, V}
        new(slots, keys, dibs, vals, count, totalcost, maxprobe, idxfloor)
    end
end

function rh_insert!(h::RobinDict{K, V}, key::K, val::V) where {K, V}
    # table full
    if h.count == length(h.keys)
        return -1
    end
    ckey, cval, cdibs = key, val, 0
    sz = length(h.keys)
    index = hashindex(ckey, sz)
    @inbounds while true
    	if (h.slots[index] == 0x0) || (h.slots[index] == 0x1 && h.keys[index] == ckey)
    		break
    	end
        if h.dibs[index] < cdibs
            h.vals[index], cval = cval, h.vals[index]
            h.keys[index], ckey = ckey, h.keys[index]
            h.maxprobe = max(h.maxprobe, cdibs)
            h.dibs[index], cdibs = cdibs, h.dibs[index]
        end
        cdibs += 1
        h.totalcost += 1
        index = (index & (sz - 1)) + 1
    end

    @inbounds if h.slots[index] == 0x1 && h.keys[index] == ckey
        h.vals[index] = cval
        return index
    end

    @inbounds if h.slots[index] == 0x0
    	h.count += 1
    end

    @inbounds h.slots[index] = 0x1
    @inbounds h.vals[index] = cval
    @inbounds h.keys[index] = ckey
    @inbounds h.dibs[index] = cdibs
    h.totalcost += 1
    h.maxprobe = max(h.maxprobe, cdibs)
    if h.idxfloor == 0
        h.idxfloor = index
    else
        h.idxfloor = min(h.idxfloor, index)
    end
    return index
end

function rh_search(h::RobinDict{K, V}, key::K) where {K, V}
	sz = length(h.keys)
	index = hashindex(key, sz)
	while true
		if h.slots[index] == 0x0
			return -1
		elseif cdibs > h.dibs[index]
			return -1
		elseif h.keys[index] == key 
			return index
		end
		index = (index & (sz - 1)) + 1
	end
end

# backward shift deletion by not keeping any tombstones
function rh_delete!(h::RobinDict{K, V}, index) where {K, V}
    #forceful
    (index < 0) && return false;

    #this assumes that  the key is present in the dictionary at index 
    index0 = index
    sz = length(h.keys)
    while true
        index0 = (index0 & (sz - 1)) + 1
        if h.slots[index0] == 0x0
            break
        end
    end
    #index0 represents the first empty slot in linear probe
    
    # the backwards shifting algorithm
    curr = index
    next = (index & (sz - 1)) + 1

    while next != index0 
        h.slots[curr] = h.slots[next]
        h.vals[curr] = h.vals[next]
        h.keys[curr] = h.keys[next]
        h.dibs[curr] = (h.dibs[next] > 0) ? (h.dibs[next] - 1) : 0
        curr = next
        next = (next & (sz-1)) + 1
    end

    #curr is at the last position, reset back to normal
    h.slots[curr] = 0x0
    ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.keys, index-1)
    ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.vals, index-1)
    h.dibs[curr] = 0
    h.count -= 1
    h.totalcost += 1

    return h
end

function rehash!(h::RobinDict{K,V}, newsz = length(h.keys)) where {K, V}
    olds = h.slots
    oldk = h.keys
    oldv = h.vals
    oldd = h.dibs
    sz = length(olds)
    newsz = _tablesz(newsz)
    h.totalcost += 1
    h.idxfloor = 1
    if h.count == 0
        resize!(h.slots, newsz)
        fill!(h.slots, 0)
        resize!(h.keys, sz)
        resize!(h.vals, sz)
        resize!(h.dibs, sz)
        h.count = 0
        h.maxprobe = 0
        h.totalcost = 0
        h.idxfloor = 0
        return h
    end

    slots = zeros(UInt8,newsz)
    keys = Vector{K}(undef, newsz)
    vals = Vector{V}(undef, newsz)
    dibs = Vector{Int}(undef, newsz)
    fill!(dibs, 0)
    totalcost0 = h.totalcost
    count = 0
    maxprobe = 0
    idxfloor = h.idxfloor

    for i = 1:sz
        @inbounds if olds[i] == 0x1
            k = oldk[i]
            v = oldv[i]
            d = dibs[i]
            index0 = index = hashindex(k, newsz)
            while slots[index] != 0
                index = (index & (newsz-1)) + 1
            end
            probe = (index - index0) & (newsz-1)
            probe > maxprobe && (maxprobe = probe)
            index < idxfloor && (idxfloor = index)
            slots[index] = 0x1
            keys[index] = k
            vals[index] = v
            dibs[index] = d
            count += 1

            if h.totalcost != totalcost0
                # if `h` is changed by a finalizer, retry
                return rehash!(h, newsz)
            end
        end
    end

    h.slots = slots
    h.keys = keys
    h.vals = vals
    h.dibs = dibs
    h.count = count
    h.maxprobe = maxprobe
    h.idxfloor = idxfloor
    @assert h.totalcost == totalcost0
    return h
end