1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2002-2016. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20
21%%
22%%%----------------------------------------------------------------------
23%%% Purpose : Implements hashing functionality for fragmented tables
24%%%----------------------------------------------------------------------
25
26%header_doc_include
27-module(mnesia_frag_hash).
28
29%% Fragmented Table Hashing callback functions
30-export([
31	 init_state/2,
32	 add_frag/1,
33	 del_frag/1,
34	 key_to_frag_number/2,
35	 match_spec_to_frag_numbers/2
36	]).
37
38%header_doc_include
39%%-behaviour(mnesia_frag_hash).
40
41%impl_doc_include
42-record(hash_state,
43	{n_fragments,
44	 next_n_to_split,
45	 n_doubles,
46	 function}).
47
48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
49
50init_state(_Tab, State) when State == undefined ->
51    #hash_state{n_fragments     = 1,
52		next_n_to_split = 1,
53		n_doubles       = 0,
54		function        = phash2}.
55
56convert_old_state({hash_state, N, P, L}) ->
57    #hash_state{n_fragments     = N,
58		next_n_to_split = P,
59		n_doubles       = L,
60		function        = phash}.
61
62%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
63
64add_frag(#hash_state{next_n_to_split = SplitN, n_doubles = L, n_fragments = N} = State) ->
65    P = SplitN + 1,
66    NewN = N + 1,
67    State2 = case power2(L) + 1 of
68		 P2 when P2 == P ->
69		     State#hash_state{n_fragments      = NewN,
70				      n_doubles        = L + 1,
71				      next_n_to_split = 1};
72		 _ ->
73		     State#hash_state{n_fragments     = NewN,
74				      next_n_to_split = P}
75	     end,
76    {State2, [SplitN], [NewN]};
77add_frag(OldState) ->
78    State = convert_old_state(OldState),
79    add_frag(State).
80
81%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
82
83del_frag(#hash_state{next_n_to_split = SplitN, n_doubles = L, n_fragments = N} = State) ->
84    P = SplitN - 1,
85    if
86	P < 1 ->
87	    L2 = L - 1,
88	    MergeN = power2(L2),
89	    State2 = State#hash_state{n_fragments     = N - 1,
90				      next_n_to_split = MergeN,
91				      n_doubles       = L2},
92	    {State2, [N], [MergeN]};
93	true ->
94	    MergeN = P,
95	    State2 = State#hash_state{n_fragments     = N - 1,
96				      next_n_to_split = MergeN},
97	    {State2, [N], [MergeN]}
98	end;
99del_frag(OldState) ->
100    State = convert_old_state(OldState),
101    del_frag(State).
102
103%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
104
105key_to_frag_number(#hash_state{function = phash, n_fragments = N, n_doubles = L}, Key) ->
106    A = erlang:phash(Key, power2(L + 1)),
107    if
108	A > N ->
109	    A - power2(L);
110	true ->
111	    A
112    end;
113key_to_frag_number(#hash_state{function = phash2, n_fragments = N, n_doubles = L}, Key) ->
114    A = erlang:phash2(Key, power2(L + 1)) + 1,
115    if
116	A > N ->
117	    A - power2(L);
118	true ->
119	    A
120    end;
121key_to_frag_number(OldState, Key) ->
122    State = convert_old_state(OldState),
123    key_to_frag_number(State, Key).
124
125%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
126
127match_spec_to_frag_numbers(#hash_state{n_fragments = N} = State, MatchSpec) ->
128    case MatchSpec of
129	[{HeadPat, _, _}] when is_tuple(HeadPat), tuple_size(HeadPat) > 2 ->
130	    KeyPat = element(2, HeadPat),
131	    case has_var(KeyPat) of
132		false ->
133		    [key_to_frag_number(State, KeyPat)];
134		true ->
135		    lists:seq(1, N)
136	    end;
137	_ ->
138	    lists:seq(1, N)
139    end;
140match_spec_to_frag_numbers(OldState, MatchSpec) ->
141    State = convert_old_state(OldState),
142    match_spec_to_frag_numbers(State, MatchSpec).
143
144power2(Y) ->
145    1 bsl Y. % trunc(math:pow(2, Y)).
146
147%impl_doc_include
148
149has_var(Pat) ->
150    mnesia:has_var(Pat).
151