Created
June 18, 2009 14:26
-
-
Save dchiji/131918 to your computer and use it in GitHub Desktop.
Skip Graph in Erlang
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-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