1%% 2%% %CopyrightBegin% 3%% 4%% Copyright Ericsson AB 2000-2018. 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%% The new version 2 has moved to use maps under the roof whenever a 22%% map is given. 23 24%% The previous version (version 1) uses the dynamic hashing techniques 25%% by Per-Åke Larsson as described in "The Design and Implementation 26%% of Dynamic Hashing for Sets and Tables in Icon" by Griswold and 27%% Townsend. Much of the terminology comes from that paper as well. 28 29%% The segments are all of the same fixed size and we just keep 30%% increasing the size of the top tuple as the table grows. At the 31%% end of the segments tuple we keep an empty segment which we use 32%% when we expand the segments. The segments are expanded by doubling 33%% every time n reaches maxn instead of increasing the tuple one 34%% element at a time. It is easier and does not seem detrimental to 35%% speed. The same applies when contracting the segments. 36%% 37%% Note that as the order of the keys is undefined we may freely 38%% reorder keys within in a bucket. 39 40-module(sets). 41-compile([{nowarn_deprecated_function, [{erlang,phash,2}]}]). 42 43%% Standard interface. 44-export([new/0,is_set/1,size/1,is_empty/1,to_list/1,from_list/1]). 45-export([is_element/2,add_element/2,del_element/2]). 46-export([union/2,union/1,intersection/2,intersection/1]). 47-export([is_disjoint/2]). 48-export([subtract/2,is_subset/2]). 49-export([fold/3,filter/2]). 50-export([new/1, from_list/2]). 51 52-export_type([set/0, set/1]). 53 54%% This is the value used when sets are represented as maps. 55%% We use an empty list instead of an atom as it is cheaper 56%% to serialize. 57-define(VALUE, []). 58 59%% Note: mk_seg/1 must be changed too if seg_size is changed. 60-define(seg_size, 16). 61-define(max_seg, 32). 62-define(expand_load, 5). 63-define(contract_load, 3). 64-define(exp_size, ?seg_size * ?expand_load). 65-define(con_size, ?seg_size * ?contract_load). 66-compile({no_auto_import,[size/1]}). 67 68%%------------------------------------------------------------------------------ 69 70-type seg() :: tuple(). 71-type segs(_Element) :: tuple(). 72 73%% Define a hash set. The default values are the standard ones. 74-record(set, 75 {size=0 :: non_neg_integer(), % Number of elements 76 n=?seg_size :: non_neg_integer(), % Number of active slots 77 maxn=?seg_size :: pos_integer(), % Maximum slots 78 bso=?seg_size div 2 :: non_neg_integer(), % Buddy slot offset 79 exp_size=?exp_size :: non_neg_integer(), % Size to expand at 80 con_size=?con_size :: non_neg_integer(), % Size to contract at 81 empty :: seg(), % Empty segment 82 segs :: segs(_) % Segments 83 }). 84 85-type set() :: set(_). 86 87-opaque set(Element) :: #set{segs :: segs(Element)} | #{Element => ?VALUE}. 88 89%%------------------------------------------------------------------------------ 90 91%% new() -> Set 92-spec new() -> set(). 93new() -> 94 Empty = mk_seg(?seg_size), 95 #set{empty = Empty, segs = {Empty}}. 96 97-spec new([{version, 1..2}]) -> set(). 98new([{version, 2}]) -> 99 #{}; 100new(Opts) -> 101 case proplists:get_value(version, Opts, 1) of 102 1 -> new(); 103 2 -> new([{version, 2}]) 104 end. 105 106%% from_list([Elem]) -> Set. 107%% Build a set from the elements in List. 108-spec from_list(List) -> Set when 109 List :: [Element], 110 Set :: set(Element). 111from_list(Ls) -> 112 lists:foldl(fun (E, S) -> add_element(E, S) end, new(), Ls). 113 114-spec from_list(List, [{version, 1..2}]) -> Set when 115 List :: [Element], 116 Set :: set(Element). 117from_list(Ls, [{version, 2}]) -> 118 maps:from_keys(Ls, ?VALUE); 119from_list(Ls, Opts) -> 120 case proplists:get_value(version, Opts, 1) of 121 1 -> from_list(Ls); 122 2 -> from_list(Ls, [{version, 2}]) 123 end. 124 125%%------------------------------------------------------------------------------ 126 127%% is_set(Set) -> boolean(). 128%% Return 'true' if Set is a set of elements, else 'false'. 129-spec is_set(Set) -> boolean() when 130 Set :: term(). 131is_set(#{}) -> true; 132is_set(#set{}) -> true; 133is_set(_) -> false. 134 135%% size(Set) -> int(). 136%% Return the number of elements in Set. 137-spec size(Set) -> non_neg_integer() when 138 Set :: set(). 139size(#{}=S) -> map_size(S); 140size(#set{size=Size}) -> Size. 141 142%% is_empty(Set) -> boolean(). 143%% Return 'true' if Set is an empty set, otherwise 'false'. 144-spec is_empty(Set) -> boolean() when 145 Set :: set(). 146is_empty(#{}=S) -> map_size(S)=:=0; 147is_empty(#set{size=Size}) -> Size=:=0. 148 149%% to_list(Set) -> [Elem]. 150%% Return the elements in Set as a list. 151-spec to_list(Set) -> List when 152 Set :: set(Element), 153 List :: [Element]. 154to_list(#{}=S) -> 155 maps:keys(S); 156to_list(#set{} = S) -> 157 fold(fun (Elem, List) -> [Elem|List] end, [], S). 158 159%% is_element(Element, Set) -> boolean(). 160%% Return 'true' if Element is an element of Set, else 'false'. 161-spec is_element(Element, Set) -> boolean() when 162 Set :: set(Element). 163is_element(E, #{}=S) -> 164 case S of 165 #{E := _} -> true; 166 _ -> false 167 end; 168is_element(E, #set{}=S) -> 169 Slot = get_slot(S, E), 170 Bkt = get_bucket(S, Slot), 171 lists:member(E, Bkt). 172 173%% add_element(Element, Set) -> Set. 174%% Return Set with Element inserted in it. 175-spec add_element(Element, Set1) -> Set2 when 176 Set1 :: set(Element), 177 Set2 :: set(Element). 178add_element(E, #{}=S) -> 179 S#{E=>?VALUE}; 180add_element(E, #set{}=S0) -> 181 Slot = get_slot(S0, E), 182 Bkt = get_bucket(S0, Slot), 183 case lists:member(E, Bkt) of 184 true -> 185 S0; 186 false -> 187 S1 = update_bucket(S0, Slot, [E | Bkt]), 188 maybe_expand(S1) 189 end. 190 191%% del_element(Element, Set) -> Set. 192%% Return Set but with Element removed. 193-spec del_element(Element, Set1) -> Set2 when 194 Set1 :: set(Element), 195 Set2 :: set(Element). 196del_element(E, #{}=S) -> 197 maps:remove(E, S); 198del_element(E, #set{}=S0) -> 199 Slot = get_slot(S0, E), 200 Bkt = get_bucket(S0, Slot), 201 case lists:member(E, Bkt) of 202 false -> 203 S0; 204 true -> 205 S1 = update_bucket(S0, Slot, lists:delete(E, Bkt)), 206 maybe_contract(S1, 1) 207 end. 208 209%% update_bucket(Set, Slot, NewBucket) -> UpdatedSet. 210%% Replace bucket in Slot by NewBucket 211-spec update_bucket(Set1, Slot, Bkt) -> Set2 when 212 Set1 :: set(Element), 213 Set2 :: set(Element), 214 Slot :: non_neg_integer(), 215 Bkt :: [Element]. 216update_bucket(Set, Slot, NewBucket) -> 217 SegI = ((Slot-1) div ?seg_size) + 1, 218 BktI = ((Slot-1) rem ?seg_size) + 1, 219 Segs = Set#set.segs, 220 Seg = element(SegI, Segs), 221 Set#set{segs = setelement(SegI, Segs, setelement(BktI, Seg, NewBucket))}. 222 223%% union(Set1, Set2) -> Set 224%% Return the union of Set1 and Set2. 225-spec union(Set1, Set2) -> Set3 when 226 Set1 :: set(Element), 227 Set2 :: set(Element), 228 Set3 :: set(Element). 229union(#{}=S1, #{}=S2) -> 230 maps:merge(S1,S2); 231union(S1, S2) -> 232 case size(S1) < size(S2) of 233 true -> 234 fold(fun (E, S) -> add_element(E, S) end, S2, S1); 235 false -> 236 fold(fun (E, S) -> add_element(E, S) end, S1, S2) 237 end. 238 239%% union([Set]) -> Set 240%% Return the union of the list of sets. 241-spec union(SetList) -> Set when 242 SetList :: [set(Element)], 243 Set :: set(Element). 244union([S1,S2|Ss]) -> 245 union1(union(S1, S2), Ss); 246union([S]) -> S; 247union([]) -> new(). 248 249-spec union1(set(E), [set(E)]) -> set(E). 250union1(S1, [S2|Ss]) -> 251 union1(union(S1, S2), Ss); 252union1(S1, []) -> S1. 253 254%% intersection(Set1, Set2) -> Set. 255%% Return the intersection of Set1 and Set2. 256-spec intersection(Set1, Set2) -> Set3 when 257 Set1 :: set(Element), 258 Set2 :: set(Element), 259 Set3 :: set(Element). 260intersection(#{}=S1, #{}=S2) -> 261 case map_size(S1) < map_size(S2) of 262 true -> 263 Next = maps:next(maps:iterator(S1)), 264 intersection_heuristic(Next, [], [], floor(map_size(S1) * 0.75), S1, S2); 265 false -> 266 Next = maps:next(maps:iterator(S2)), 267 intersection_heuristic(Next, [], [], floor(map_size(S2) * 0.75), S2, S1) 268 end; 269intersection(S1, S2) -> 270 case size(S1) < size(S2) of 271 true -> 272 filter(fun (E) -> is_element(E, S2) end, S1); 273 false -> 274 filter(fun (E) -> is_element(E, S1) end, S2) 275 end. 276 277%% If we are keeping more than 75% of the keys, then it is 278%% cheaper to delete them. Stop accumulating and start deleting. 279intersection_heuristic(Next, _Keep, Delete, 0, Acc, Reference) -> 280 intersection_decided(Next, remove_keys(Delete, Acc), Reference); 281intersection_heuristic({Key, _Value, Iterator}, Keep, Delete, KeepCount, Acc, Reference) -> 282 Next = maps:next(Iterator), 283 case Reference of 284 #{Key := _} -> 285 intersection_heuristic(Next, [Key | Keep], Delete, KeepCount - 1, Acc, Reference); 286 _ -> 287 intersection_heuristic(Next, Keep, [Key | Delete], KeepCount, Acc, Reference) 288 end; 289intersection_heuristic(none, Keep, _Delete, _Count, _Acc, _Reference) -> 290 maps:from_keys(Keep, ?VALUE). 291 292intersection_decided({Key, _Value, Iterator}, Acc0, Reference) -> 293 Acc1 = case Reference of 294 #{Key := _} -> Acc0; 295 #{} -> maps:remove(Key, Acc0) 296 end, 297 intersection_decided(maps:next(Iterator), Acc1, Reference); 298intersection_decided(none, Acc, _Reference) -> 299 Acc. 300 301remove_keys([K | Ks], Map) -> remove_keys(Ks, maps:remove(K, Map)); 302remove_keys([], Map) -> Map. 303 304%% intersection([Set]) -> Set. 305%% Return the intersection of the list of sets. 306-spec intersection(SetList) -> Set when 307 SetList :: [set(Element),...], 308 Set :: set(Element). 309intersection([S1,S2|Ss]) -> 310 intersection1(intersection(S1, S2), Ss); 311intersection([S]) -> S. 312 313-spec intersection1(set(E), [set(E)]) -> set(E). 314intersection1(S1, [S2|Ss]) -> 315 intersection1(intersection(S1, S2), Ss); 316intersection1(S1, []) -> S1. 317 318%% is_disjoint(Set1, Set2) -> boolean(). 319%% Check whether Set1 and Set2 are disjoint. 320-spec is_disjoint(Set1, Set2) -> boolean() when 321 Set1 :: set(Element), 322 Set2 :: set(Element). 323is_disjoint(#{}=S1, #{}=S2) -> 324 if 325 map_size(S1) < map_size(S2) -> 326 is_disjoint_1(S2, maps:iterator(S1)); 327 true -> 328 is_disjoint_1(S1, maps:iterator(S2)) 329 end; 330is_disjoint(S1, S2) -> 331 case size(S1) < size(S2) of 332 true -> 333 fold(fun (_, false) -> false; 334 (E, true) -> not is_element(E, S2) 335 end, true, S1); 336 false -> 337 fold(fun (_, false) -> false; 338 (E, true) -> not is_element(E, S1) 339 end, true, S2) 340 end. 341 342is_disjoint_1(Set, Iter) -> 343 case maps:next(Iter) of 344 {K, _, NextIter} -> 345 case Set of 346 #{K := _} -> false; 347 #{} -> is_disjoint_1(Set, NextIter) 348 end; 349 none -> 350 true 351 end. 352 353%% subtract(Set1, Set2) -> Set. 354%% Return all and only the elements of Set1 which are not also in 355%% Set2. 356-spec subtract(Set1, Set2) -> Set3 when 357 Set1 :: set(Element), 358 Set2 :: set(Element), 359 Set3 :: set(Element). 360 361subtract(#{}=S1, #{}=S2) -> 362 Next = maps:next(maps:iterator(S1)), 363 subtract_heuristic(Next, [], [], floor(map_size(S1) * 0.75), S1, S2); 364subtract(S1, S2) -> 365 filter(fun (E) -> not is_element(E, S2) end, S1). 366 367%% If we are keeping more than 75% of the keys, then it is 368%% cheaper to delete them. Stop accumulating and start deleting. 369subtract_heuristic(Next, _Keep, Delete, 0, Acc, Reference) -> 370 subtract_decided(Next, remove_keys(Delete, Acc), Reference); 371subtract_heuristic({Key, _Value, Iterator}, Keep, Delete, KeepCount, Acc, Reference) -> 372 Next = maps:next(Iterator), 373 case Reference of 374 #{Key := _} -> 375 subtract_heuristic(Next, Keep, [Key | Delete], KeepCount, Acc, Reference); 376 _ -> 377 subtract_heuristic(Next, [Key | Keep], Delete, KeepCount - 1, Acc, Reference) 378 end; 379subtract_heuristic(none, Keep, _Delete, _Count, _Acc, _Reference) -> 380 maps:from_keys(Keep, ?VALUE). 381 382subtract_decided({Key, _Value, Iterator}, Acc, Reference) -> 383 case Reference of 384 #{Key := _} -> 385 subtract_decided(maps:next(Iterator), maps:remove(Key, Acc), Reference); 386 _ -> 387 subtract_decided(maps:next(Iterator), Acc, Reference) 388 end; 389subtract_decided(none, Acc, _Reference) -> 390 Acc. 391 392%% is_subset(Set1, Set2) -> boolean(). 393%% Return 'true' when every element of Set1 is also a member of 394%% Set2, else 'false'. 395-spec is_subset(Set1, Set2) -> boolean() when 396 Set1 :: set(Element), 397 Set2 :: set(Element). 398 399is_subset(#{}=S1, #{}=S2) -> 400 if 401 map_size(S1) > map_size(S2) -> 402 false; 403 true -> 404 is_subset_1(S2, maps:iterator(S1)) 405 end; 406is_subset(S1, S2) -> 407 fold(fun (E, Sub) -> Sub andalso is_element(E, S2) end, true, S1). 408 409is_subset_1(Set, Iter) -> 410 case maps:next(Iter) of 411 {K, _, NextIter} -> 412 case Set of 413 #{K := _} -> is_subset_1(Set, NextIter); 414 #{} -> false 415 end; 416 none -> 417 true 418 end. 419 420%% fold(Fun, Accumulator, Set) -> Accumulator. 421%% Fold function Fun over all elements in Set and return Accumulator. 422-spec fold(Function, Acc0, Set) -> Acc1 when 423 Function :: fun((Element, AccIn) -> AccOut), 424 Set :: set(Element), 425 Acc0 :: Acc, 426 Acc1 :: Acc, 427 AccIn :: Acc, 428 AccOut :: Acc. 429fold(F, Acc, #{}=D) -> fold_1(F, Acc, maps:iterator(D)); 430fold(F, Acc, #set{}=D) -> fold_set(F, Acc, D). 431 432fold_1(Fun, Acc, Iter) -> 433 case maps:next(Iter) of 434 {K, _, NextIter} -> 435 fold_1(Fun, Fun(K,Acc), NextIter); 436 none -> 437 Acc 438 end. 439 440%% filter(Fun, Set) -> Set. 441%% Filter Set with Fun. 442-spec filter(Pred, Set1) -> Set2 when 443 Pred :: fun((Element) -> boolean()), 444 Set1 :: set(Element), 445 Set2 :: set(Element). 446filter(F, #{}=D) -> maps:from_keys(filter_1(F, maps:iterator(D)), ?VALUE); 447filter(F, #set{}=D) -> filter_set(F, D). 448 449filter_1(Fun, Iter) -> 450 case maps:next(Iter) of 451 {K, _, NextIter} -> 452 case Fun(K) of 453 true -> 454 [K | filter_1(Fun, NextIter)]; 455 false -> 456 filter_1(Fun, NextIter) 457 end; 458 none -> 459 [] 460 end. 461 462%% get_slot(Hashdb, Key) -> Slot. 463%% Get the slot. First hash on the new range, if we hit a bucket 464%% which has not been split use the unsplit buddy bucket. 465-spec get_slot(set(E), E) -> non_neg_integer(). 466get_slot(T, Key) -> 467 H = erlang:phash(Key, T#set.maxn), 468 if 469 H > T#set.n -> H - T#set.bso; 470 true -> H 471 end. 472 473%% get_bucket(Hashdb, Slot) -> Bucket. 474-spec get_bucket(set(), non_neg_integer()) -> term(). 475get_bucket(T, Slot) -> get_bucket_s(T#set.segs, Slot). 476 477%% fold_set(Fun, Acc, Dictionary) -> Dictionary. 478%% filter_set(Fun, Dictionary) -> Dictionary. 479 480%% Work functions for fold and filter operations. These traverse the 481%% hash structure rebuilding as necessary. Note we could have 482%% implemented map and hash using fold but these should be faster. 483%% We hope! 484 485fold_set(F, Acc, D) when is_function(F, 2) -> 486 Segs = D#set.segs, 487 fold_segs(F, Acc, Segs, tuple_size(Segs)). 488 489fold_segs(F, Acc, Segs, I) when I >= 1 -> 490 Seg = element(I, Segs), 491 fold_segs(F, fold_seg(F, Acc, Seg, tuple_size(Seg)), Segs, I-1); 492fold_segs(_, Acc, _, _) -> Acc. 493 494fold_seg(F, Acc, Seg, I) when I >= 1 -> 495 fold_seg(F, fold_bucket(F, Acc, element(I, Seg)), Seg, I-1); 496fold_seg(_, Acc, _, _) -> Acc. 497 498fold_bucket(F, Acc, [E|Bkt]) -> 499 fold_bucket(F, F(E, Acc), Bkt); 500fold_bucket(_, Acc, []) -> Acc. 501 502filter_set(F, D) when is_function(F, 1) -> 503 Segs0 = tuple_to_list(D#set.segs), 504 {Segs1,Fc} = filter_seg_list(F, Segs0, [], 0), 505 maybe_contract(D#set{segs = list_to_tuple(Segs1)}, Fc). 506 507filter_seg_list(F, [Seg|Segs], Fss, Fc0) -> 508 Bkts0 = tuple_to_list(Seg), 509 {Bkts1,Fc1} = filter_bkt_list(F, Bkts0, [], Fc0), 510 filter_seg_list(F, Segs, [list_to_tuple(Bkts1)|Fss], Fc1); 511filter_seg_list(_, [], Fss, Fc) -> 512 {lists:reverse(Fss, []),Fc}. 513 514filter_bkt_list(F, [Bkt0|Bkts], Fbs, Fc0) -> 515 {Bkt1,Fc1} = filter_bucket(F, Bkt0, [], Fc0), 516 filter_bkt_list(F, Bkts, [Bkt1|Fbs], Fc1); 517filter_bkt_list(_, [], Fbs, Fc) -> 518 {lists:reverse(Fbs),Fc}. 519 520filter_bucket(F, [E|Bkt], Fb, Fc) -> 521 case F(E) of 522 true -> filter_bucket(F, Bkt, [E|Fb], Fc); 523 false -> filter_bucket(F, Bkt, Fb, Fc+1) 524 end; 525filter_bucket(_, [], Fb, Fc) -> {Fb,Fc}. 526 527%% get_bucket_s(Segments, Slot) -> Bucket. 528%% put_bucket_s(Segments, Slot, Bucket) -> NewSegments. 529 530get_bucket_s(Segs, Slot) -> 531 SegI = ((Slot-1) div ?seg_size) + 1, 532 BktI = ((Slot-1) rem ?seg_size) + 1, 533 element(BktI, element(SegI, Segs)). 534 535put_bucket_s(Segs, Slot, Bkt) -> 536 SegI = ((Slot-1) div ?seg_size) + 1, 537 BktI = ((Slot-1) rem ?seg_size) + 1, 538 Seg = setelement(BktI, element(SegI, Segs), Bkt), 539 setelement(SegI, Segs, Seg). 540 541-spec maybe_expand(set(E)) -> set(E). 542maybe_expand(T0) when T0#set.size + 1 > T0#set.exp_size -> 543 T = maybe_expand_segs(T0), %Do we need more segments. 544 N = T#set.n + 1, %Next slot to expand into 545 Segs0 = T#set.segs, 546 Slot1 = N - T#set.bso, 547 B = get_bucket_s(Segs0, Slot1), 548 Slot2 = N, 549 {B1,B2} = rehash(B, Slot1, Slot2, T#set.maxn), 550 Segs1 = put_bucket_s(Segs0, Slot1, B1), 551 Segs2 = put_bucket_s(Segs1, Slot2, B2), 552 T#set{size = T#set.size + 1, 553 n = N, 554 exp_size = N * ?expand_load, 555 con_size = N * ?contract_load, 556 segs = Segs2}; 557maybe_expand(T) -> T#set{size = T#set.size + 1}. 558 559-spec maybe_expand_segs(set(E)) -> set(E). 560maybe_expand_segs(T) when T#set.n =:= T#set.maxn -> 561 T#set{maxn = 2 * T#set.maxn, 562 bso = 2 * T#set.bso, 563 segs = expand_segs(T#set.segs, T#set.empty)}; 564maybe_expand_segs(T) -> T. 565 566-spec maybe_contract(set(E), non_neg_integer()) -> set(E). 567maybe_contract(T, Dc) when T#set.size - Dc < T#set.con_size, 568 T#set.n > ?seg_size -> 569 N = T#set.n, 570 Slot1 = N - T#set.bso, 571 Segs0 = T#set.segs, 572 B1 = get_bucket_s(Segs0, Slot1), 573 Slot2 = N, 574 B2 = get_bucket_s(Segs0, Slot2), 575 Segs1 = put_bucket_s(Segs0, Slot1, B1 ++ B2), 576 Segs2 = put_bucket_s(Segs1, Slot2, []), %Clear the upper bucket 577 N1 = N - 1, 578 maybe_contract_segs(T#set{size = T#set.size - Dc, 579 n = N1, 580 exp_size = N1 * ?expand_load, 581 con_size = N1 * ?contract_load, 582 segs = Segs2}); 583maybe_contract(T, Dc) -> T#set{size = T#set.size - Dc}. 584 585-spec maybe_contract_segs(set(E)) -> set(E). 586maybe_contract_segs(T) when T#set.n =:= T#set.bso -> 587 T#set{maxn = T#set.maxn div 2, 588 bso = T#set.bso div 2, 589 segs = contract_segs(T#set.segs)}; 590maybe_contract_segs(T) -> T. 591 592%% rehash(Bucket, Slot1, Slot2, MaxN) -> {Bucket1,Bucket2}. 593-spec rehash([T], integer(), pos_integer(), pos_integer()) -> {[T],[T]}. 594rehash([E|T], Slot1, Slot2, MaxN) -> 595 {L1,L2} = rehash(T, Slot1, Slot2, MaxN), 596 case erlang:phash(E, MaxN) of 597 Slot1 -> {[E|L1],L2}; 598 Slot2 -> {L1,[E|L2]} 599 end; 600rehash([], _, _, _) -> {[],[]}. 601 602%% mk_seg(Size) -> Segment. 603-spec mk_seg(16) -> seg(). 604mk_seg(16) -> {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}. 605 606%% expand_segs(Segs, EmptySeg) -> NewSegs. 607%% contract_segs(Segs) -> NewSegs. 608%% Expand/contract the segment tuple by doubling/halving the number 609%% of segments. We special case the powers of 2 upto 32, this should 610%% catch most case. N.B. the last element in the segments tuple is 611%% an extra element containing a default empty segment. 612-spec expand_segs(segs(E), seg()) -> segs(E). 613expand_segs({B1}, Empty) -> 614 {B1,Empty}; 615expand_segs({B1,B2}, Empty) -> 616 {B1,B2,Empty,Empty}; 617expand_segs({B1,B2,B3,B4}, Empty) -> 618 {B1,B2,B3,B4,Empty,Empty,Empty,Empty}; 619expand_segs({B1,B2,B3,B4,B5,B6,B7,B8}, Empty) -> 620 {B1,B2,B3,B4,B5,B6,B7,B8, 621 Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty}; 622expand_segs({B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16}, Empty) -> 623 {B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16, 624 Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty, 625 Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty}; 626expand_segs(Segs, Empty) -> 627 list_to_tuple(tuple_to_list(Segs) 628 ++ lists:duplicate(tuple_size(Segs), Empty)). 629 630-spec contract_segs(segs(E)) -> segs(E). 631contract_segs({B1,_}) -> 632 {B1}; 633contract_segs({B1,B2,_,_}) -> 634 {B1,B2}; 635contract_segs({B1,B2,B3,B4,_,_,_,_}) -> 636 {B1,B2,B3,B4}; 637contract_segs({B1,B2,B3,B4,B5,B6,B7,B8,_,_,_,_,_,_,_,_}) -> 638 {B1,B2,B3,B4,B5,B6,B7,B8}; 639contract_segs({B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16, 640 _,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_}) -> 641 {B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16}; 642contract_segs(Segs) -> 643 Ss = tuple_size(Segs) div 2, 644 list_to_tuple(lists:sublist(tuple_to_list(Segs), 1, Ss)). 645