<commit_before>% @copyright 2007-2010 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin

%   Licensed under the Apache License, Version 2.0 (the "License");
%   you may not use this file except in compliance with the License.
%   You may obtain a copy of the License at
%
%       http://www.apache.org/licenses/LICENSE-2.0
%
%   Unless required by applicable law or agreed to in writing, software
%   distributed under the License is distributed on an "AS IS" BASIS,
%   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%   See the License for the specific language governing permissions and
%   limitations under the License.

%% @author <NAME> <<EMAIL>>
%% @doc Routing Table
%% @end
%% @version $Id$
-module(rt_chord).
-author('<EMAIL>').
-vsn('$Id$').

-behaviour(rt_beh).
-include("scalaris.hrl").

% routingtable behaviour
-export([empty/1, empty_ext/1,
         hash_key/1, get_random_node_id/0, next_hop/2, init_stabilize/3,
         filter_dead_node/2, to_pid_list/1, get_size/1, get_keys_for_replicas/1,
         n/0, dump/1, to_list/1, export_rt_to_dht_node/4,
         update_pred_succ_in_dht_node/3, handle_custom_message/2,
         check/6, check/5, check_fd/2,
         check_config/0]).

% stabilize for Chord
-export([stabilize/5]).

-ifdef(with_export_type_support).
-export_type([key/0, rt/0, custom_message/0, external_rt/0]).
-endif.

%% userdevguide-begin rt_chord:types
-opaque(key()::non_neg_integer()).
-opaque(rt()::gb_tree()).
-type(external_rt()::gb_tree()).        %% @todo: make opaque
-type(index() :: {pos_integer(), pos_integer()}).
-opaque(custom_message() ::
       {rt_get_node_response, Index::pos_integer(), Node::node:node_type()}).
%% userdevguide-end rt_chord:types

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Key Handling
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% userdevguide-begin rt_chord:empty
%% @doc Creates an empty routing table.
-spec empty(node:node_type()) -> rt().
empty(_Succ) -> gb_trees:empty().
%% userdevguide-end rt_chord:empty

%% @doc Hashes the key to the identifier space.
-spec hash_key(iodata() | integer()) -> key().
hash_key(Key) -> hash_key_(Key).

%% @doc Hashes the key to the identifier space (internal).
%%      Note: Needed for dialyzer to cope with the opaque key() type and the
%%      use of key() in get_keys_for_replicas/1.
-spec hash_key_(iodata() | integer()) -> non_neg_integer().
hash_key_(Key) when is_integer(Key) ->
    <<N:128>> = erlang:md5(erlang:term_to_binary(Key)),
    N;
hash_key_(Key) ->
    <<N:128>> = erlang:md5(Key),
    N.

%% @doc Generates a random node id.
%%      In this case it is a random 128-bit string.
-spec get_random_node_id() -> key().
get_random_node_id() ->
    hash_key(randoms:getRandomId()).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% RT Management
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% userdevguide-begin rt_chord:init_stabilize
%% @doc Starts the stabilization routine.
-spec init_stabilize(key(), node:node_type(), rt()) -> rt().
init_stabilize(Id, _Succ, RT) ->
    % calculate the longest finger
    Key = calculateKey(Id, first_index()),
    % trigger a lookup for Key
    lookup:unreliable_lookup(Key, {rt_get_node, comm:this(), first_index()}),
    RT.
%% userdevguide-end rt_chord:init_stabilize

%% userdevguide-begin rt_chord:filter_dead_node
%% @doc Removes dead nodes from the routing table.
-spec filter_dead_node(rt(), comm:mypid()) -> rt().
filter_dead_node(RT, DeadPid) ->
    DeadIndices = [Index || {Index, Node}  <- gb_trees:to_list(RT),
                            node:equals(Node, DeadPid)],
    lists:foldl(fun(Index, Tree) -> gb_trees:delete(Index, Tree) end,
                RT, DeadIndices).
%% userdevguide-end rt_chord:filter_dead_node

%% @doc Returns the pids of the routing table entries.
-spec to_pid_list(rt()) -> [comm:mypid()].
to_pid_list(RT) ->
    [node:pidX(Node) || Node <- gb_trees:values(RT)].

%% @doc Returns the size of the routing table.
-spec get_size(rt() | external_rt()) -> non_neg_integer().
get_size(RT) ->
    gb_trees:size(RT).

%% @doc Keep a key in the address space. See n/0.
-spec normalize(Key::non_neg_integer()) -> key().
normalize(Key) ->
    Key band 16#FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.

%% @doc Returns the size of the address space.
-spec n() -> non_neg_integer().
n() ->
    16#100000000000000000000000000000000.

%% @doc Returns the replicas of the given key.
-spec get_keys_for_replicas(iodata() | integer()) -> [key()].
get_keys_for_replicas(Key) ->
    HashedKey = hash_key_(Key),
    [HashedKey,
     HashedKey bxor 16#40000000000000000000000000000000,
     HashedKey bxor 16#80000000000000000000000000000000,
     HashedKey bxor 16#C0000000000000000000000000000000
    ].

%% @doc Dumps the RT state for output in the web interface.
-spec dump(RT::rt()) -> KeyValueList::[{Index::non_neg_integer(), Node::string()}].
dump(RT) ->
    [{Index, lists:flatten(io_lib:format("~p", [Node]))} || {Index, Node} <- gb_trees:to_list(RT)].

%% userdevguide-begin rt_chord:stabilize
%% @doc Updates one entry in the routing table and triggers the next update.
-spec stabilize(key(), node:node_type(), rt(), pos_integer(), node:node_type())
        -> rt().
stabilize(Id, Succ, RT, Index, Node) ->
    case node:is_valid(Node)                        % do not add null nodes
        andalso (node:id(Succ) =/= node:id(Node))   % reached succ?
        andalso (not intervals:in(                  % there should be nothing shorter
                   node:id(Node),                   %   than succ
                   intervals:mk_from_node_ids(Id, node:id(Succ)))) of 
        true ->
            NewRT = gb_trees:enter(Index, Node, RT),
            Key = calculateKey(Id, next_index(Index)),
            lookup:unreliable_lookup(Key, {rt_get_node, comm:this(),
                                           next_index(Index)}),
            NewRT;
        _ -> RT
    end.
%% userdevguide-end rt_chord:stabilize

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Finger calculation
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% @private
-spec calculateKey(key(), index()) -> key().
calculateKey(Id, {I, J}) ->
    % N / K^I * (J + 1)
    Offset = (n() div util:pow(config:read(chord_base), I)) * (J + 1),
    %io:format("~p: ~p + ~p~n", [{I, J}, Id, Offset]),
    normalize(Id + Offset).

-spec first_index() -> index().
first_index() ->
   {1, config:read(chord_base) - 2}.

-spec next_index(index()) -> index().
next_index({I, 1}) ->
    {I + 1, config:read(chord_base) - 2};
next_index({I, J}) ->
    {I, J - 1}.

%% @doc Checks whether config parameters of the rt_chord process exist and are
%%      valid.
-spec check_config() -> boolean().
check_config() ->
    config:is_integer(chord_base) and
        config:is_greater_than_equal(chord_base, 2).

-include("rt_generic.hrl").

%% userdevguide-begin rt_chord:handle_custom_message
%% @doc Chord reacts on 'rt_get_node_response' messages in response to its
%%      'rt_get_node' messages.
-spec handle_custom_message(custom_message(), rt_loop:state_init()) -> rt_loop:state_init();
                           (any(), rt_loop:state_init()) -> unknown_event.
handle_custom_message({rt_get_node_response, Index, Node}, State) ->
    OldRT = rt_loop:get_rt(State),
    Id = rt_loop:get_id(State),
    Succ = rt_loop:get_succ(State),
    Pred = rt_loop:get_pred(State),
    NewRT = stabilize(Id, Succ, OldRT, Index, Node),<commit_msg>- fixed spec of function rt_chord:handle_custom_message/2<commit_after>% @copyright 2007-2010 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin

%   Licensed under the Apache License, Version 2.0 (the "License");
%   you may not use this file except in compliance with the License.
%   You may obtain a copy of the License at
%
%       http://www.apache.org/licenses/LICENSE-2.0
%
%   Unless required by applicable law or agreed to in writing, software
%   distributed under the License is distributed on an "AS IS" BASIS,
%   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%   See the License for the specific language governing permissions and
%   limitations under the License.

%% @author <NAME> <<EMAIL>>
%% @doc Routing Table
%% @end
%% @version $Id$
-module(rt_chord).
-author('<EMAIL>').
-vsn('$Id$').

-behaviour(rt_beh).
-include("scalaris.hrl").

% routingtable behaviour
-export([empty/1, empty_ext/1,
         hash_key/1, get_random_node_id/0, next_hop/2, init_stabilize/3,
         filter_dead_node/2, to_pid_list/1, get_size/1, get_keys_for_replicas/1,
         n/0, dump/1, to_list/1, export_rt_to_dht_node/4,
         update_pred_succ_in_dht_node/3, handle_custom_message/2,
         check/6, check/5, check_fd/2,
         check_config/0]).

% stabilize for Chord
-export([stabilize/5]).

-ifdef(with_export_type_support).
-export_type([key/0, rt/0, custom_message/0, external_rt/0]).
-endif.

%% userdevguide-begin rt_chord:types
-opaque(key()::non_neg_integer()).
-opaque(rt()::gb_tree()).
-type(external_rt()::gb_tree()).        %% @todo: make opaque
-type(index() :: {pos_integer(), pos_integer()}).
-opaque(custom_message() ::
       {rt_get_node_response, Index::pos_integer(), Node::node:node_type()}).
%% userdevguide-end rt_chord:types

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Key Handling
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% userdevguide-begin rt_chord:empty
%% @doc Creates an empty routing table.
-spec empty(node:node_type()) -> rt().
empty(_Succ) -> gb_trees:empty().
%% userdevguide-end rt_chord:empty

%% @doc Hashes the key to the identifier space.
-spec hash_key(iodata() | integer()) -> key().
hash_key(Key) -> hash_key_(Key).

%% @doc Hashes the key to the identifier space (internal).
%%      Note: Needed for dialyzer to cope with the opaque key() type and the
%%      use of key() in get_keys_for_replicas/1.
-spec hash_key_(iodata() | integer()) -> non_neg_integer().
hash_key_(Key) when is_integer(Key) ->
    <<N:128>> = erlang:md5(erlang:term_to_binary(Key)),
    N;
hash_key_(Key) ->
    <<N:128>> = erlang:md5(Key),
    N.

%% @doc Generates a random node id.
%%      In this case it is a random 128-bit string.
-spec get_random_node_id() -> key().
get_random_node_id() ->
    hash_key(randoms:getRandomId()).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% RT Management
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% userdevguide-begin rt_chord:init_stabilize
%% @doc Starts the stabilization routine.
-spec init_stabilize(key(), node:node_type(), rt()) -> rt().
init_stabilize(Id, _Succ, RT) ->
    % calculate the longest finger
    Key = calculateKey(Id, first_index()),
    % trigger a lookup for Key
    lookup:unreliable_lookup(Key, {rt_get_node, comm:this(), first_index()}),
    RT.
%% userdevguide-end rt_chord:init_stabilize

%% userdevguide-begin rt_chord:filter_dead_node
%% @doc Removes dead nodes from the routing table.
-spec filter_dead_node(rt(), comm:mypid()) -> rt().
filter_dead_node(RT, DeadPid) ->
    DeadIndices = [Index || {Index, Node}  <- gb_trees:to_list(RT),
                            node:equals(Node, DeadPid)],
    lists:foldl(fun(Index, Tree) -> gb_trees:delete(Index, Tree) end,
                RT, DeadIndices).
%% userdevguide-end rt_chord:filter_dead_node

%% @doc Returns the pids of the routing table entries.
-spec to_pid_list(rt()) -> [comm:mypid()].
to_pid_list(RT) ->
    [node:pidX(Node) || Node <- gb_trees:values(RT)].

%% @doc Returns the size of the routing table.
-spec get_size(rt() | external_rt()) -> non_neg_integer().
get_size(RT) ->
    gb_trees:size(RT).

%% @doc Keep a key in the address space. See n/0.
-spec normalize(Key::non_neg_integer()) -> key().
normalize(Key) ->
    Key band 16#FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.

%% @doc Returns the size of the address space.
-spec n() -> non_neg_integer().
n() ->
    16#100000000000000000000000000000000.

%% @doc Returns the replicas of the given key.
-spec get_keys_for_replicas(iodata() | integer()) -> [key()].
get_keys_for_replicas(Key) ->
    HashedKey = hash_key_(Key),
    [HashedKey,
     HashedKey bxor 16#40000000000000000000000000000000,
     HashedKey bxor 16#80000000000000000000000000000000,
     HashedKey bxor 16#C0000000000000000000000000000000
    ].

%% @doc Dumps the RT state for output in the web interface.
-spec dump(RT::rt()) -> KeyValueList::[{Index::non_neg_integer(), Node::string()}].
dump(RT) ->
    [{Index, lists:flatten(io_lib:format("~p", [Node]))} || {Index, Node} <- gb_trees:to_list(RT)].

%% userdevguide-begin rt_chord:stabilize
%% @doc Updates one entry in the routing table and triggers the next update.
-spec stabilize(key(), node:node_type(), rt(), pos_integer(), node:node_type())
        -> rt().
stabilize(Id, Succ, RT, Index, Node) ->
    case node:is_valid(Node)                        % do not add null nodes
        andalso (node:id(Succ) =/= node:id(Node))   % reached succ?
        andalso (not intervals:in(                  % there should be nothing shorter
                   node:id(Node),                   %   than succ
                   intervals:mk_from_node_ids(Id, node:id(Succ)))) of 
        true ->
            NewRT = gb_trees:enter(Index, Node, RT),
            Key = calculateKey(Id, next_index(Index)),
            lookup:unreliable_lookup(Key, {rt_get_node, comm:this(),
                                           next_index(Index)}),
            NewRT;
        _ -> RT
    end.
%% userdevguide-end rt_chord:stabilize

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Finger calculation
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% @private
-spec calculateKey(key(), index()) -> key().
calculateKey(Id, {I, J}) ->
    % N / K^I * (J + 1)
    Offset = (n() div util:pow(config:read(chord_base), I)) * (J + 1),
    %io:format("~p: ~p + ~p~n", [{I, J}, Id, Offset]),
    normalize(Id + Offset).

-spec first_index() -> index().
first_index() ->
   {1, config:read(chord_base) - 2}.

-spec next_index(index()) -> index().
next_index({I, 1}) ->
    {I + 1, config:read(chord_base) - 2};
next_index({I, J}) ->
    {I, J - 1}.

%% @doc Checks whether config parameters of the rt_chord process exist and are
%%      valid.
-spec check_config() -> boolean().
check_config() ->
    config:is_integer(chord_base) and
        config:is_greater_than_equal(chord_base, 2).

-include("rt_generic.hrl").

%% userdevguide-begin rt_chord:handle_custom_message
%% @doc Chord reacts on 'rt_get_node_response' messages in response to its
%%      'rt_get_node' messages.
-spec handle_custom_message(custom_message(), rt_loop:state_init()) -> rt_loop:state_init().
handle_custom_message({rt_get_node_response, Index, Node}, State) ->
    OldRT = rt_loop:get_rt(State),
    Id = rt_loop:get_id(State),
    Succ = rt_loop:get_succ(State),
    Pred = rt_loop:get_pred(State),
    NewRT = stabilize(Id, Succ, OldRT, Index, Node),
{'fraction_non_alphanumeric': 0.19702085402184707, 'fraction_numerical': 0.026150281363786824, 'mean_word_length': 3.8760490639122014, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 102, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 10, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4392989', 'n_tokens_mistral': 5378, 'n_tokens_neox': 4908, 'n_words': 1195}