1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2000-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%% We use the dynamic hashing techniques by Per-Åke Larsson as
22%% described in "The Design and Implementation of Dynamic Hashing for
23%% Sets and Tables in Icon" by Griswold and Townsend.  Much of the
24%% terminology comes from that paper as well.
25%%
26%% The segments are all of the same fixed size and we just keep
27%% increasing the size of the top tuple as the table grows.  At the
28%% end of the segments tuple we keep an empty segment which we use
29%% when we expand the segments.  The segments are expanded by doubling
30%% every time n reaches maxn instead of increasing the tuple one
31%% element at a time.  It is easier and does not seem detrimental to
32%% speed.  The same applies when contracting the segments.
33%%
34%% Note that as the order of the keys is undefined we may freely
35%% reorder keys within a bucket.
36
37-module(dict).
38
39%% Standard interface.
40-export([new/0,is_key/2,to_list/1,from_list/1,size/1,is_empty/1]).
41-export([fetch/2,find/2,fetch_keys/1,erase/2,take/2]).
42-export([store/3,append/3,append_list/3,update/3,update/4,update_counter/3]).
43-export([fold/3,map/2,filter/2,merge/3]).
44
45-export_type([dict/0, dict/2]).
46
47%% Low-level interface.
48%%-export([get_slot/2,get_bucket/2,on_bucket/3,fold_dict/3,
49%%	 maybe_expand/2,maybe_contract/2]).
50
51%% Note: mk_seg/1 must be changed too if seg_size is changed.
52-define(seg_size, 16).
53-define(max_seg, 32).
54-define(expand_load, 5).
55-define(contract_load, 3).
56-define(exp_size, (?seg_size * ?expand_load)).
57-define(con_size, (?seg_size * ?contract_load)).
58
59-type segs(_Key, _Value) :: tuple().
60
61%% Define a hashtable.  The default values are the standard ones.
62-record(dict,
63	{size=0		      :: non_neg_integer(),   	% Number of elements
64	 n=?seg_size	      :: non_neg_integer(),   	% Number of active slots
65	 maxn=?seg_size	      :: non_neg_integer(),	% Maximum slots
66	 bso=?seg_size div 2  :: non_neg_integer(),   	% Buddy slot offset
67	 exp_size=?exp_size   :: non_neg_integer(),   	% Size to expand at
68	 con_size=?con_size   :: non_neg_integer(),   	% Size to contract at
69	 empty		      :: tuple(),		% Empty segment
70	 segs		      :: segs(_, _)	      	% Segments
71	}).
72
73
74-type dict() :: dict(_, _).
75
76-opaque dict(Key, Value) :: #dict{segs :: segs(Key, Value)}.
77
78-define(kv(K,V), [K|V]).			% Key-Value pair format
79%%-define(kv(K,V), {K,V}).			% Key-Value pair format
80
81-spec new() -> dict().
82
83new() ->
84    Empty = mk_seg(?seg_size),
85    #dict{empty=Empty,segs={Empty}}.
86
87-spec is_key(Key, Dict) -> boolean() when
88      Dict :: dict(Key, Value :: term()).
89
90is_key(Key, D) ->
91    Slot = get_slot(D, Key),
92    Bkt = get_bucket(D, Slot),
93    find_key(Key, Bkt).
94
95find_key(K, [?kv(K,_Val)|_]) -> true;
96find_key(K, [_|Bkt]) -> find_key(K, Bkt);
97find_key(_, []) -> false.
98
99-spec to_list(Dict) -> List when
100      Dict :: dict(Key, Value),
101      List :: [{Key, Value}].
102
103to_list(D) ->
104    fold(fun (Key, Val, List) -> [{Key,Val}|List] end, [], D).
105
106-spec from_list(List) -> Dict when
107      Dict :: dict(Key, Value),
108      List :: [{Key, Value}].
109
110from_list(L) ->
111    lists:foldl(fun ({K,V}, D) -> store(K, V, D) end, new(), L).
112
113-spec size(Dict) -> non_neg_integer() when
114      Dict :: dict().
115
116size(#dict{size=N}) when is_integer(N), N >= 0 -> N.
117
118-spec is_empty(Dict) -> boolean() when
119      Dict :: dict().
120
121is_empty(#dict{size=N}) -> N =:= 0.
122
123-spec fetch(Key, Dict) -> Value when
124      Dict :: dict(Key, Value).
125
126fetch(Key, D) ->
127    Slot = get_slot(D, Key),
128    Bkt = get_bucket(D, Slot),
129    try fetch_val(Key, Bkt)
130    catch
131	badarg -> erlang:error(badarg, [Key, D])
132    end.
133
134fetch_val(K, [?kv(K,Val)|_]) -> Val;
135fetch_val(K, [_|Bkt]) -> fetch_val(K, Bkt);
136fetch_val(_, []) -> throw(badarg).
137
138-spec find(Key, Dict) -> {'ok', Value} | 'error' when
139      Dict :: dict(Key, Value).
140
141find(Key, D) ->
142    Slot = get_slot(D, Key),
143    Bkt = get_bucket(D, Slot),
144    find_val(Key, Bkt).
145
146find_val(K, [?kv(K,Val)|_]) -> {ok,Val};
147find_val(K, [_|Bkt]) -> find_val(K, Bkt);
148find_val(_, []) -> error.
149
150-spec fetch_keys(Dict) -> Keys when
151      Dict :: dict(Key, Value :: term()),
152      Keys :: [Key].
153
154fetch_keys(D) ->
155    fold(fun (Key, _Val, Keys) -> [Key|Keys] end, [], D).
156
157-spec erase(Key, Dict1) -> Dict2 when
158      Dict1 :: dict(Key, Value),
159      Dict2 :: dict(Key, Value).
160
161%%  Erase all elements with key Key.
162
163erase(Key, D0) ->
164    Slot = get_slot(D0, Key),
165    {D1,Dc} = on_bucket(fun (B0) -> erase_key(Key, B0) end,
166			D0, Slot),
167    maybe_contract(D1, Dc).
168
169erase_key(Key, [?kv(Key,_Val)|Bkt]) -> {Bkt,1};
170erase_key(Key, [E|Bkt0]) ->
171    {Bkt1,Dc} = erase_key(Key, Bkt0),
172    {[E|Bkt1],Dc};
173erase_key(_, []) -> {[],0}.
174
175-spec take(Key, Dict) -> {Value, Dict1} | error when
176      Dict :: dict(Key, Value),
177      Dict1 :: dict(Key, Value),
178      Key :: term(),
179      Value :: term().
180
181take(Key, D0) ->
182    Slot = get_slot(D0, Key),
183    case on_bucket(fun (B0) -> take_key(Key, B0) end, D0, Slot) of
184	{D1,{Value,Dc}} ->
185            {Value, maybe_contract(D1, Dc)};
186	{_,error} -> error
187    end.
188
189take_key(Key, [?kv(Key,Val)|Bkt]) ->
190    {Bkt,{Val,1}};
191take_key(Key, [E|Bkt0]) ->
192    {Bkt1,Res} = take_key(Key, Bkt0),
193    {[E|Bkt1],Res};
194take_key(_, []) -> {[],error}.
195
196-spec store(Key, Value, Dict1) -> Dict2 when
197      Dict1 :: dict(Key, Value),
198      Dict2 :: dict(Key, Value).
199
200store(Key, Val, D0) ->
201    Slot = get_slot(D0, Key),
202    {D1,Ic} = on_bucket(fun (B0) -> store_bkt_val(Key, Val, B0) end,
203			D0, Slot),
204    maybe_expand(D1, Ic).
205
206%% store_bkt_val(Key, Val, Bucket) -> {NewBucket,PutCount}.
207
208store_bkt_val(Key, New, [?kv(Key,_Old)|Bkt]) -> {[?kv(Key,New)|Bkt],0};
209store_bkt_val(Key, New, [Other|Bkt0]) ->
210    {Bkt1,Ic} = store_bkt_val(Key, New, Bkt0),
211    {[Other|Bkt1],Ic};
212store_bkt_val(Key, New, []) -> {[?kv(Key,New)],1}.
213
214-spec append(Key, Value, Dict1) -> Dict2 when
215      Dict1 :: dict(Key, Value),
216      Dict2 :: dict(Key, Value).
217
218append(Key, Val, D0) ->
219    Slot = get_slot(D0, Key),
220    {D1,Ic} = on_bucket(fun (B0) -> append_bkt(Key, Val, B0) end,
221			D0, Slot),
222    maybe_expand(D1, Ic).
223
224%% append_bkt(Key, Val, Bucket) -> {NewBucket,PutCount}.
225
226append_bkt(Key, Val, [?kv(Key,Bag)|Bkt]) -> {[?kv(Key,Bag ++ [Val])|Bkt],0};
227append_bkt(Key, Val, [Other|Bkt0]) ->
228    {Bkt1,Ic} = append_bkt(Key, Val, Bkt0),
229    {[Other|Bkt1],Ic};
230append_bkt(Key, Val, []) -> {[?kv(Key,[Val])],1}.
231
232-spec append_list(Key, ValList, Dict1) -> Dict2 when
233      Dict1 :: dict(Key, Value),
234      Dict2 :: dict(Key, Value),
235      ValList :: [Value].
236
237append_list(Key, L, D0) ->
238    Slot = get_slot(D0, Key),
239    {D1,Ic} = on_bucket(fun (B0) -> app_list_bkt(Key, L, B0) end,
240			D0, Slot),
241    maybe_expand(D1, Ic).
242
243%% app_list_bkt(Key, L, Bucket) -> {NewBucket,PutCount}.
244
245app_list_bkt(Key, L, [?kv(Key,Bag)|Bkt]) -> {[?kv(Key,Bag ++ L)|Bkt],0};
246app_list_bkt(Key, L, [Other|Bkt0]) ->
247    {Bkt1,Ic} = app_list_bkt(Key, L, Bkt0),
248    {[Other|Bkt1],Ic};
249app_list_bkt(Key, L, []) -> {[?kv(Key,L)],1}.
250
251%% %% first_key(Table) -> {ok,Key} | error.
252%% %%  Find the "first" key in a Table.
253
254%% first_key(T) ->
255%%     case next_bucket(T, 1) of
256%% 	[?kv(K,Val)|Bkt] -> {ok,K};
257%% 	[] -> error				%No elements
258%%     end.
259
260%% next_bucket(T, Slot) when Slot > T#dict.n -> [];
261%% next_bucket(T, Slot) ->
262%%     case get_bucket(T, Slot) of
263%% 	[] -> next_bucket(T, Slot+1);		%Empty bucket
264%% 	B -> B
265%%     end.
266
267%% %% next_key(Table, Key) -> {ok,NextKey} | error.
268
269%% next_key(T, Key) ->
270%%     Slot = get_slot(T, Key),
271%%     B = get_bucket(T, Slot),
272%%     %% Find a bucket with something in it.
273%%     Bkt = case bucket_after_key(Key, B) of
274%% 	      no_key -> exit(badarg);
275%% 	      [] -> next_bucket(T, Slot+1);
276%% 	      Rest -> Rest
277%% 	  end,
278%%     case Bkt of
279%% 	[?kv(Next,Val)|_] -> {ok,Next};
280%% 	[] -> error				%We have reached the end!
281%%     end.
282
283%% bucket_after_key(Key, [?kv(Key,Val)|Bkt]) -> Bkt;
284%% bucket_after_key(Key, [Other|Bkt]) ->
285%%     bucket_after_key(Key, Bkt);
286%% bucket_after_key(Key, []) -> no_key.		%Key not found!
287
288%% %% on_key(Fun, Key, Dictionary) -> Dictionary.
289
290%% on_key(F, Key, D0) ->
291%%     Slot = get_slot(D0, Key),
292%%     {D1,Dc} = on_bucket(fun (B0) -> on_key_bkt(Key, F, B0) end,
293%% 			D0, Slot),
294%%     maybe_contract(D1, Dc).
295
296%% on_key_bkt(Key, F, [?kv(Key,Val)|Bkt]) ->
297%%     case F(Val) of
298%% 	{ok,New} -> {[?kv(Key,New)|Bkt],0};
299%% 	erase -> {Bkt,1}
300%%     end;
301%% on_key_bkt(Key, F, [Other|Bkt0]) ->
302%%     {Bkt1,Dc} = on_key_bkt(Key, F, Bkt0),
303%%     {[Other|Bkt1],Dc}.
304
305-spec update(Key, Fun, Dict1) -> Dict2 when
306      Dict1 :: dict(Key, Value),
307      Dict2 :: dict(Key, Value),
308      Fun :: fun((Value1 :: Value) -> Value2 :: Value).
309
310update(Key, F, D0) ->
311    Slot = get_slot(D0, Key),
312    try on_bucket(fun (B0) -> update_bkt(Key, F, B0) end, D0, Slot) of
313	{D1,_Uv} -> D1
314    catch
315	badarg -> erlang:error(badarg, [Key, F, D0])
316    end.
317
318update_bkt(Key, F, [?kv(Key,Val)|Bkt]) ->
319    Upd = F(Val),
320    {[?kv(Key,Upd)|Bkt],Upd};
321update_bkt(Key, F, [Other|Bkt0]) ->
322    {Bkt1,Upd} = update_bkt(Key, F, Bkt0),
323    {[Other|Bkt1],Upd};
324update_bkt(_Key, _F, []) ->
325    throw(badarg).
326
327-spec update(Key, Fun, Initial, Dict1) -> Dict2 when
328      Dict1 :: dict(Key, Value),
329      Dict2 :: dict(Key, Value),
330      Fun :: fun((Value1 :: Value) -> Value2 :: Value),
331      Initial :: Value.
332
333update(Key, F, Init, D0) ->
334    Slot = get_slot(D0, Key),
335    {D1,Ic} = on_bucket(fun (B0) -> update_bkt(Key, F, Init, B0) end,
336			D0, Slot),
337    maybe_expand(D1, Ic).
338
339update_bkt(Key, F, _, [?kv(Key,Val)|Bkt]) ->
340    {[?kv(Key,F(Val))|Bkt],0};
341update_bkt(Key, F, I, [Other|Bkt0]) ->
342    {Bkt1,Ic} = update_bkt(Key, F, I, Bkt0),
343    {[Other|Bkt1],Ic};
344update_bkt(Key, F, I, []) when is_function(F, 1) -> {[?kv(Key,I)],1}.
345
346-spec update_counter(Key, Increment, Dict1) -> Dict2 when
347      Dict1 :: dict(Key, Value),
348      Dict2 :: dict(Key, Value),
349      Increment :: number().
350
351update_counter(Key, Incr, D0) when is_number(Incr) ->
352    Slot = get_slot(D0, Key),
353    {D1,Ic} = on_bucket(fun (B0) -> counter_bkt(Key, Incr, B0) end,
354			D0, Slot),
355    maybe_expand(D1, Ic).
356
357-dialyzer({no_improper_lists, counter_bkt/3}).
358
359counter_bkt(Key, I, [?kv(Key,Val)|Bkt]) ->
360    {[?kv(Key,Val+I)|Bkt],0};
361counter_bkt(Key, I, [Other|Bkt0]) ->
362    {Bkt1,Ic} = counter_bkt(Key, I, Bkt0),
363    {[Other|Bkt1],Ic};
364counter_bkt(Key, I, []) -> {[?kv(Key,I)],1}.
365
366-spec fold(Fun, Acc0, Dict) -> Acc1 when
367      Fun :: fun((Key, Value, AccIn) -> AccOut),
368      Dict :: dict(Key, Value),
369      Acc0 :: Acc,
370      Acc1 :: Acc,
371      AccIn :: Acc,
372      AccOut :: Acc.
373
374%%  Fold function Fun over all "bags" in Table and return Accumulator.
375
376fold(F, Acc, D) -> fold_dict(F, Acc, D).
377
378-spec map(Fun, Dict1) -> Dict2 when
379      Fun :: fun((Key, Value1) -> Value2),
380      Dict1 :: dict(Key, Value1),
381      Dict2 :: dict(Key, Value2).
382
383map(F, D) -> map_dict(F, D).
384
385-spec filter(Pred, Dict1) -> Dict2 when
386      Pred :: fun((Key , Value) -> boolean()),
387      Dict1 :: dict(Key, Value),
388      Dict2 :: dict(Key, Value).
389
390filter(F, D) -> filter_dict(F, D).
391
392-spec merge(Fun, Dict1, Dict2) -> Dict3 when
393      Fun :: fun((Key, Value1, Value2) -> Value),
394      Dict1 :: dict(Key, Value1),
395      Dict2 :: dict(Key, Value2),
396      Dict3 :: dict(Key, Value).
397
398merge(F, D1, D2) when D1#dict.size < D2#dict.size ->
399    fold_dict(fun (K, V1, D) ->
400		      update(K, fun (V2) -> F(K, V1, V2) end, V1, D)
401	      end, D2, D1);
402merge(F, D1, D2) ->
403    fold_dict(fun (K, V2, D) ->
404		      update(K, fun (V1) -> F(K, V1, V2) end, V2, D)
405	      end, D1, D2).
406
407
408%% get_slot(Hashdb, Key) -> Slot.
409%%  Get the slot.  First hash on the new range, if we hit a bucket
410%%  which has not been split use the unsplit buddy bucket.
411
412get_slot(T, Key) ->
413    H = erlang:phash(Key, T#dict.maxn),
414    if
415	H > T#dict.n -> H - T#dict.bso;
416	true -> H
417    end.
418
419%% get_bucket(Hashdb, Slot) -> Bucket.
420
421get_bucket(T, Slot) -> get_bucket_s(T#dict.segs, Slot).
422
423%% on_bucket(Fun, Hashdb, Slot) -> {NewHashDb,Result}.
424%%  Apply Fun to the bucket in Slot and replace the returned bucket.
425
426on_bucket(F, T, Slot) ->
427    SegI = ((Slot-1) div ?seg_size) + 1,
428    BktI = ((Slot-1) rem ?seg_size) + 1,
429    Segs = T#dict.segs,
430    Seg = element(SegI, Segs),
431    B0 = element(BktI, Seg),
432    {B1,Res} = F(B0),				%Op on the bucket.
433    {T#dict{segs=setelement(SegI, Segs, setelement(BktI, Seg, B1))},Res}.
434
435%% fold_dict(Fun, Acc, Dictionary) -> Acc.
436%% map_dict(Fun, Dictionary) -> Dictionary.
437%% filter_dict(Fun, Dictionary) -> Dictionary.
438%%
439%%  Work functions for fold, map and filter operations.  These
440%%  traverse the hash structure rebuilding as necessary.  Note we
441%%  could have implemented map and filter using fold but these are
442%%  faster.  We hope!
443
444fold_dict(F, Acc, #dict{size=0}) when is_function(F, 3) ->
445    Acc;
446fold_dict(F, Acc, D) ->
447    Segs = D#dict.segs,
448    fold_segs(F, Acc, Segs, tuple_size(Segs)).
449
450fold_segs(F, Acc, Segs, I) when I >= 1 ->
451    Seg = element(I, Segs),
452    fold_segs(F, fold_seg(F, Acc, Seg, tuple_size(Seg)), Segs, I-1);
453fold_segs(F, Acc, _, 0) when is_function(F, 3) -> Acc.
454
455fold_seg(F, Acc, Seg, I) when I >= 1 ->
456    fold_seg(F, fold_bucket(F, Acc, element(I, Seg)), Seg, I-1);
457fold_seg(F, Acc, _, 0) when is_function(F, 3) -> Acc.
458
459fold_bucket(F, Acc, [?kv(Key,Val)|Bkt]) ->
460    fold_bucket(F, F(Key, Val, Acc), Bkt);
461fold_bucket(F, Acc, []) when is_function(F, 3) -> Acc.
462
463map_dict(F, #dict{size=0} = Dict) when is_function(F, 2) ->
464    Dict;
465map_dict(F, D) ->
466    Segs0 = tuple_to_list(D#dict.segs),
467    Segs1 = map_seg_list(F, Segs0),
468    D#dict{segs=list_to_tuple(Segs1)}.
469
470map_seg_list(F, [Seg|Segs]) ->
471    Bkts0 = tuple_to_list(Seg),
472    Bkts1 = map_bkt_list(F, Bkts0),
473    [list_to_tuple(Bkts1)|map_seg_list(F, Segs)];
474map_seg_list(F, []) when is_function(F, 2) -> [].
475
476map_bkt_list(F, [Bkt0|Bkts]) ->
477    [map_bucket(F, Bkt0)|map_bkt_list(F, Bkts)];
478map_bkt_list(F, []) when is_function(F, 2) -> [].
479
480map_bucket(F, [?kv(Key,Val)|Bkt]) ->
481    [?kv(Key,F(Key, Val))|map_bucket(F, Bkt)];
482map_bucket(F, []) when is_function(F, 2) -> [].
483
484filter_dict(F, #dict{size=0} = Dict) when is_function(F, 2) ->
485    Dict;
486filter_dict(F, D) ->
487    Segs0 = tuple_to_list(D#dict.segs),
488    {Segs1,Fc} = filter_seg_list(F, Segs0, [], 0),
489    maybe_contract(D#dict{segs=list_to_tuple(Segs1)}, Fc).
490
491filter_seg_list(F, [Seg|Segs], Fss, Fc0) ->
492    Bkts0 = tuple_to_list(Seg),
493    {Bkts1,Fc1} = filter_bkt_list(F, Bkts0, [], Fc0),
494    filter_seg_list(F, Segs, [list_to_tuple(Bkts1)|Fss], Fc1);
495filter_seg_list(F, [], Fss, Fc) when is_function(F, 2) ->
496    {lists:reverse(Fss, []),Fc}.
497
498filter_bkt_list(F, [Bkt0|Bkts], Fbs, Fc0) ->
499    {Bkt1,Fc1} = filter_bucket(F, Bkt0, [], Fc0),
500    filter_bkt_list(F, Bkts, [Bkt1|Fbs], Fc1);
501filter_bkt_list(F, [], Fbs, Fc) when is_function(F, 2) ->
502    {lists:reverse(Fbs),Fc}.
503
504filter_bucket(F, [?kv(Key,Val)=E|Bkt], Fb, Fc) ->
505    case F(Key, Val) of
506	true -> filter_bucket(F, Bkt, [E|Fb], Fc);
507	false -> filter_bucket(F, Bkt, Fb, Fc+1)
508    end;
509filter_bucket(F, [], Fb, Fc) when is_function(F, 2) ->
510    {lists:reverse(Fb),Fc}.
511
512%% get_bucket_s(Segments, Slot) -> Bucket.
513%% put_bucket_s(Segments, Slot, Bucket) -> NewSegments.
514
515get_bucket_s(Segs, Slot) ->
516    SegI = ((Slot-1) div ?seg_size) + 1,
517    BktI = ((Slot-1) rem ?seg_size) + 1,
518    element(BktI, element(SegI, Segs)).
519
520put_bucket_s(Segs, Slot, Bkt) ->
521    SegI = ((Slot-1) div ?seg_size) + 1,
522    BktI = ((Slot-1) rem ?seg_size) + 1,
523    Seg = setelement(BktI, element(SegI, Segs), Bkt),
524    setelement(SegI, Segs, Seg).
525
526%% In maybe_expand(), the variable Ic only takes the values 0 or 1,
527%% but type inference is not strong enough to infer this. Thus, the
528%% use of explicit pattern matching and an auxiliary function.
529
530maybe_expand(T, 0) -> maybe_expand_aux(T, 0);
531maybe_expand(T, 1) -> maybe_expand_aux(T, 1).
532
533maybe_expand_aux(T0, Ic) when T0#dict.size + Ic > T0#dict.exp_size ->
534    T = maybe_expand_segs(T0),			%Do we need more segments.
535    N = T#dict.n + 1,				%Next slot to expand into
536    Segs0 = T#dict.segs,
537    Slot1 = N - T#dict.bso,
538    B = get_bucket_s(Segs0, Slot1),
539    Slot2 = N,
540    [B1|B2] = rehash(B, Slot1, Slot2, T#dict.maxn),
541    Segs1 = put_bucket_s(Segs0, Slot1, B1),
542    Segs2 = put_bucket_s(Segs1, Slot2, B2),
543    T#dict{size=T#dict.size + Ic,
544	   n=N,
545	   exp_size=N * ?expand_load,
546	   con_size=N * ?contract_load,
547	   segs=Segs2};
548maybe_expand_aux(T, Ic) -> T#dict{size=T#dict.size + Ic}.
549
550maybe_expand_segs(T) when T#dict.n =:= T#dict.maxn ->
551    T#dict{maxn=2 * T#dict.maxn,
552	   bso=2 * T#dict.bso,
553	   segs=expand_segs(T#dict.segs, T#dict.empty)};
554maybe_expand_segs(T) -> T.
555
556maybe_contract(T, Dc) when T#dict.size - Dc < T#dict.con_size,
557			   T#dict.n > ?seg_size ->
558    N = T#dict.n,
559    Slot1 = N - T#dict.bso,
560    Segs0 = T#dict.segs,
561    B1 = get_bucket_s(Segs0, Slot1),
562    Slot2 = N,
563    B2 = get_bucket_s(Segs0, Slot2),
564    Segs1 = put_bucket_s(Segs0, Slot1, B1 ++ B2),
565    Segs2 = put_bucket_s(Segs1, Slot2, []),	%Clear the upper bucket
566    N1 = N - 1,
567    maybe_contract_segs(T#dict{size=T#dict.size - Dc,
568			       n=N1,
569			       exp_size=N1 * ?expand_load,
570			       con_size=N1 * ?contract_load,
571			       segs=Segs2});
572maybe_contract(T, Dc) -> T#dict{size=T#dict.size - Dc}.
573
574maybe_contract_segs(T) when T#dict.n =:= T#dict.bso ->
575    T#dict{maxn=T#dict.maxn div 2,
576	   bso=T#dict.bso div 2,
577	   segs=contract_segs(T#dict.segs)};
578maybe_contract_segs(T) -> T.
579
580%% rehash(Bucket, Slot1, Slot2, MaxN) -> [Bucket1|Bucket2].
581%%  Yes, we should return a tuple, but this is more fun.
582
583rehash([?kv(Key,_Bag)=KeyBag|T], Slot1, Slot2, MaxN) ->
584    [L1|L2] = rehash(T, Slot1, Slot2, MaxN),
585    case erlang:phash(Key, MaxN) of
586	Slot1 -> [[KeyBag|L1]|L2];
587	Slot2 -> [L1|[KeyBag|L2]]
588    end;
589rehash([], _Slot1, _Slot2, _MaxN) -> [[]|[]].
590
591%% mk_seg(Size) -> Segment.
592
593mk_seg(16) -> {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}.
594
595%% expand_segs(Segs, EmptySeg) -> NewSegs.
596%% contract_segs(Segs) -> NewSegs.
597%%  Expand/contract the segment tuple by doubling/halving the number
598%%  of segments.  We special case the powers of 2 upto 32, this should
599%%  catch most case.  N.B. the last element in the segments tuple is
600%%  an extra element containing a default empty segment.
601
602expand_segs({B1}, Empty) ->
603    {B1,Empty};
604expand_segs({B1,B2}, Empty) ->
605    {B1,B2,Empty,Empty};
606expand_segs({B1,B2,B3,B4}, Empty) ->
607    {B1,B2,B3,B4,Empty,Empty,Empty,Empty};
608expand_segs({B1,B2,B3,B4,B5,B6,B7,B8}, Empty) ->
609    {B1,B2,B3,B4,B5,B6,B7,B8,
610     Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty};
611expand_segs({B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16}, Empty) ->
612    {B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16,
613     Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,
614     Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty};
615expand_segs(Segs, Empty) ->
616    list_to_tuple(tuple_to_list(Segs)
617    ++ lists:duplicate(tuple_size(Segs), Empty)).
618
619contract_segs({B1,_}) ->
620    {B1};
621contract_segs({B1,B2,_,_}) ->
622    {B1,B2};
623contract_segs({B1,B2,B3,B4,_,_,_,_}) ->
624    {B1,B2,B3,B4};
625contract_segs({B1,B2,B3,B4,B5,B6,B7,B8,_,_,_,_,_,_,_,_}) ->
626    {B1,B2,B3,B4,B5,B6,B7,B8};
627contract_segs({B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16,
628	       _,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_}) ->
629    {B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16};
630contract_segs(Segs) ->
631    Ss = tuple_size(Segs) div 2,
632    list_to_tuple(lists:sublist(tuple_to_list(Segs), 1, Ss)).
633