consistent hashing functions

%% Consistent hashing functions
%%
%% First, hash memcached servers to unsigned integers on a continuum. To
%% map a key to a memcached server, hash the key to an unsigned integer
%% and locate the next largest integer on the continuum. That integer
%% represents the hashed server that the key maps to.
%% reference: http://www8.org/w8-papers/2a-webserver/caching/paper2.html
hash_to_uint(Host, Port) when is_list(Host), is_integer(Port) ->
    hash_to_uint(Host ++ integer_to_list(Port)).
 
hash_to_uint(Key) when is_list(Key) -> 
    <<Int:128/unsigned-integer>> = erlang:md5(Key), Int.
 
map_key(#state{continuum=Continuum, sockets=Sockets}, Key) when is_list(Key) ->
    {Host, Port} = find_next_largest(hash_to_uint(Key), Continuum),
    Pool = proplists:get_value({Host, Port}, Sockets),
    lists:nth(random:uniform(length(Pool)), Pool).
    
find_next_largest(Int, Continuum) ->
    {A,B} = lists:split(length(Continuum) div 2, Continuum),
    case find_next_largest(Int, A, B) of
        undefined ->
            [{_, Val}|_] = Continuum,
            Val;
        Val -> Val
    end.
    
find_next_largest(Int, [], [{Pivot, _}|_]) when Int >= Pivot -> undefined;
 
find_next_largest(Int, [], [{Pivot, Val}|_]) when Int < Pivot -> Val;
 
find_next_largest(Int, Front, [{Pivot, Val} | _]) when Int < Pivot ->
    {Last, _} = lists:last(Front),
    case Int >= Last of
        true -> Val;
        false ->
            {A, B} = lists:split(length(Front) div 2, Front),
            find_next_largest(Int, A, B)
    end;
    
find_next_largest(Int, _, [{Pivot,_} | _]=Back) when Int >= Pivot ->
    {A, B} = lists:split(length(Back) div 2, Back),
    find_next_largest(Int, A, B).