Skip to content

Instantly share code, notes, and snippets.

@dchiji

dchiji/skipgraph.erl

Created June 18, 2009 14:26
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dchiji/131918 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dchiji/131918 to your computer and use it in GitHub Desktop.
Download ZIP
Skip Graph in Erlang
Raw
skipgraph.erl
-module(sg).
-export([start/0, start/1, get_node/0, find_/1, put_/2, get_/1, get_/2]).
-define(error(X), (begin io:format("*** ERROR ~p ~p ~p~n", [?MODULE, ?LINE, X]) end)).
-define(debug(X), (begin io:format("*** DEBUG ~p ~p ~p~n", [?MODULE, ?LINE, X]) end)).
start() -> register(node_loop, spawn(fun() -> node_loop(boot(dummy_node(), 0, 0)) end)).
start(Init) ->
Pid = rpc:call(Init, sg, get_node, []),
register(node_loop, spawn(fun() -> node_loop(Pid) end)).
node_loop(Pid) ->
receive {From, get} -> From ! {ok, Pid}; _ -> pass end,
node_loop(Pid).
get_node() ->
node_loop ! {self(), get},
receive {ok, Pid} -> Pid; _ -> pass end.
init(Membership_Vector, Init, Key) -> % initialize function
Init ! {self(), {join, Key}},
[[LKey, LNode], [RKey, RNode]] = receive
{reply, {join, Left, Right}} -> [Left, Right];
Any -> ?error({init, {receive_error, Any}})
end,
[[[LKey, LNode], [RKey, RNode]] | init_join(Membership_Vector, LNode, RNode, Key, 2)].
init_join([], _, _, _, _) -> [];
init_join([Vector|T], LNode, RNode, Key, Level) ->
RNode ! {self(), {join_level, Key, Level, Vector, right}},
[NRKey, NRNode] = receive
{reply, {join_level, RKey_Node}} -> RKey_Node;
RAny -> ?error({init, {receive_error, right, RAny}})
end,
LNode ! {self(), {join_level, Key, Level, Vector, left}},
[NLKey, NLNode] = receive
{reply, {join_level, LKey_Node}} -> LKey_Node;
LAny -> ?error({init, {receive_error, left, LAny}})
end,
[[[NLKey, NLNode], [NRKey, NRNode]] | init_join(T, NLNode, NRNode, Key, Level + 1)].
boot(Init_Node, Key, Value) ->
From = self(),
Pid = spawn(fun() -> boot_(From, Init_Node, Key, Value) end),
receive {ok} -> Pid; Any -> ?error(Any) end.
boot_(From, Init_Node, Key, Value) -> % boot new peer
Level_Max = 127,
{A1, A2, A3} = now(),
random:seed(A1, A2, A3),
Membership_Vector = [random:uniform(2) - 1 || _ <- lists:duplicate(Level_Max, 0)],
Skip_List = init(Membership_Vector, Init_Node, Key),
From ! {ok},
loop([1 | Membership_Vector], Key, Value, Skip_List).
loop(Membership_Vector, Key, Value, Skip_List) ->
receive
{put, Value2} ->
loop(Membership_Vector, Key, Value2, Skip_List);
{From, {find, Key2}} ->
[Next_Key, Next_Node] = get_next(Skip_List, Key, Key2),
if
Next_Key == undef__ -> From ! {reply, {find, Key, self()}};
true -> Next_Node ! {From, {find, Key2}}
end,
loop(Membership_Vector, Key, Value, Skip_List);
{From, {get, End_Key, Lis}} ->
if
End_Key < Key -> From ! {reply, {get, Lis}};
true ->
[_Left, [_Right_Key, Right_Node]] = lists:nth(1, Skip_List),
Right_Node ! {From, {get, End_Key, [Value | Lis]}}
end,
loop(Membership_Vector, Key, Value, Skip_List);
{From, {join, From_Key}} ->
[[Left_Key, Left_Node], [Right_Key, Right_Node]] = lists:nth(1, Skip_List),
[Next_Key, Next_Node] = get_next(Skip_List, Key, From_Key),
case Next_Key of
undef__ ->
if
From_Key < Key ->
From ! {reply, {join, [Left_Key, Left_Node], [Key, self()]}},
Left_Node ! {From, {set, right, From_Key, 1}},
self() ! {From, {set, left, From_Key, 1}};
Key < From_Key ->
From ! {reply, {join, [Key, self()], [Right_Key, Right_Node]}},
Right_Node ! {From, {set, left, From_Key, 1}},
self() ! {From, {set, right, From_Key, 1}};
true ->
?error({loop, {join, {key, Key}, {from_key, From_Key}}})
end;
_ ->
Next_Node ! {From, {join, From_Key}}
end,
loop(Membership_Vector, Key, Value, Skip_List);
{From, {join_level, From_Key, Level, Vector, LR}} ->
My_Vector = lists:nth(Level, Membership_Vector),
[[_LKey, LNode], [_RKey, RNode]] = lists:nth(Level - 1, Skip_List),
if
My_Vector /= Vector ->
case LR of
right -> RNode ! {From, {join_level, From_Key, Level, Vector, LR}};
left -> LNode ! {From, {join_level, From_Key, Level, Vector, LR}}
end;
true ->
From ! {reply, {join_level, [Key, self()]}},
[[_, SLNode], [_, SRNode]] = lists:nth(Level, Skip_List),
case LR of
right ->
SLNode ! {From, {set, right, From_Key, Level}},
self() ! {From, {set, left, From_Key, Level}};
left ->
SRNode ! {From, {set, left, From_Key, Level}},
self() ! {From, {set, right, From_Key, Level}}
end
end,
loop(Membership_Vector, Key, Value, Skip_List);
{From, {set, LR, From_Key, Level}} ->
Iter = case LR of
right -> fun([Left, _Right]) -> [Left, [From_Key, From]] end;
left -> fun([_Left, Right]) -> [[From_Key, From], Right] end
end,
loop(Membership_Vector, Key, Value, n_map(Iter, Skip_List, Level));
Any ->
?error({loop_Any, Any}),
loop(Membership_Vector, Key, Value, Skip_List)
end.
dummy_node() -> spawn(fun dummy_node_/0).
dummy_node_() ->
receive
{put, _} -> pass;
{From, {get, _, Lis}} -> From ! {reply, {get, Lis}};
{From, {join, _}} -> From ! {reply, {join, [dummy__, self()], [dummy__, self()]}};
{From, {join_level, _, _, _, _}} -> From ! {reply, {join_level, [dummy__, self()]}};
{_From, {set, _, _, _}} -> pass;
Any -> ?error(Any)
end,
dummy_node_().
n_map(Func, [H | T], 1) -> [Func(H) | T];
n_map(Func, [H | T], N) -> [H | n_map(Func, T, N - 1)].
get_next(Skip_List, Key, Key2) -> get_next_iter(Skip_List, Key, Key2, [undef__, undef__]).
get_next_iter([], _, _, [Key, Node]) -> [Key, Node];
get_next_iter([[[Left_Key, Left_Node], [Right_Key, Right_Node]] | T], Key, Key2, [Key3, Node]) ->
[Next_Key, Next_Node] = if
Key < Key2 andalso (Right_Key < Key2 orelse Right_Key == Key2) andalso Right_Key /= dummy__-> [Right_Key, Right_Node];
Key2 < Key andalso (Key2 < Left_Key orelse Left_Key == Key2) andalso Left_Key /= dummy__ -> [Left_Key, Left_Node];
true -> [Key3, Node]
end,
get_next_iter(T, Key, Key2, [Next_Key, Next_Node]).
find_(Key) ->
get_node() ! {self(), {find, Key}},
receive
{reply, {find, Key2, Value}} -> [Key2, Value];
Any -> ?error({find, reply, any, Any})
end.
put_(Key, Value) ->
[Key2, Node] = find_(Key),
if
Key2 == Key -> Node ! {put, Value};
true -> boot(get_node(), Key, Value)
end.
get_(Key) -> get_(Key, Key).
get_(Start_Key, End_Key) ->
[_, Node] = find_(Start_Key),
Node ! {self(), {get, End_Key, []}},
receive
{reply, {get, Lis}} -> lists:reverse(Lis);
Any -> ?error(Any)
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment