dict.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 544 行 · 第 1/2 页

%% ``The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved via the world wide web at http://www.erlang.org/.
%% 
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%% 
%% The Initial Developer of the Original Code is Ericsson Utvecklings AB.
%% Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
%% AB. All Rights Reserved.''
%% 
%%     $Id$
%%

%% We use the dynamic hashing techniques by Per-舓e Larsson as
%% described in "The Design and Implementation of Dynamic Hashing for
%% Sets and Tables in Icon" by Griswold and Townsend.  Much of the
%% terminology comes from that paper as well.
%%
%% The segments are all of the same fixed size and we just keep
%% increasing the size of the top tuple as the table grows.  At the
%% end of the segments tuple we keep an empty segment which we use
%% when we expand the segments.  The segments are expanded by doubling
%% every time n reaches maxn instead of increasing the tuple one
%% element at a time.  It is easier and does not seem detrimental to
%% speed.  The same applies when contracting the segments.
%%
%% Note that as the order of the keys is undefined we may freely
%% reorder keys within a bucket.

-module(dict).

%% Standard interface.
-export([new/0,is_key/2,to_list/1,from_list/1,size/1]).
-export([fetch/2,find/2,fetch_keys/1,erase/2]).
-export([store/3,append/3,append_list/3,update/3,update/4,update_counter/3]).
-export([fold/3,map/2,filter/2,merge/3]).

%% Deprecated interface.
-export([dict_to_list/1,list_to_dict/1]).
-deprecated([{dict_to_list,1},{list_to_dict,1}]).

%% Low-level interface.
%%-export([get_slot/2,get_bucket/2,on_bucket/3,fold_dict/3,
%%	 maybe_expand/2,maybe_contract/2]).

%% Note: mk_seg/1 must be changed too if seg_size is changed.
-define(seg_size, 16).
-define(max_seg, 32).
-define(expand_load, 5).
-define(contract_load, 3).
-define(exp_size, (?seg_size * ?expand_load)).
-define(con_size, (?seg_size * ?contract_load)).

%% Define a hashtable.  The default values are the standard ones.
-record(dict,
	{size=0			::integer(),   	% Number of elements
	 n=?seg_size		::integer(),   	% Number of active slots
	 maxn=?seg_size		::integer(),	% Maximum slots
	 bso=?seg_size div 2	::integer(),   	% Buddy slot offset
	 exp_size=?exp_size	::integer(),   	% Size to expand at
	 con_size=?con_size	::integer(),   	% Size to contract at
	 empty,					% Empty segment
	 segs			::tuple()      	% Segments
	}).

-define(kv(K,V), [K|V]).			% Key-Value pair format
%%-define(kv(K,V), {K,V}).			% Key-Value pair format

%% new() -> Table.

new() ->
    Empty = mk_seg(?seg_size),
    #dict{empty=Empty,segs={Empty}}.

%% is_key(Key, Dictionary) -> bool().

is_key(Key, D) ->
    Slot = get_slot(D, Key),
    Bkt = get_bucket(D, Slot),
    find_key(Key, Bkt).

find_key(K, [?kv(K,_Val)|_]) -> true;
find_key(K, [_|Bkt]) -> find_key(K, Bkt);
find_key(_, []) -> false.

%% to_list(Dictionary) -> [{Key,Value}].

to_list(D) ->
    fold(fun (Key, Val, List) -> [{Key,Val}|List] end, [], D).

%% from_list([{Key,Value}]) -> Dictionary.

from_list(L) ->
    lists:foldl(fun ({K,V}, D) -> store(K, V, D) end, new(), L).

%% size(Dictionary) -> integer().

size(#dict{size=N}) when is_integer(N), N >= 0 -> N. 

%% fetch(Key, Dictionary) -> Value.

fetch(Key, D) ->
    Slot = get_slot(D, Key),
    Bkt = get_bucket(D, Slot),
    fetch_val(Key, Bkt).

fetch_val(K, [?kv(K,Val)|_]) -> Val;
fetch_val(K, [_|Bkt]) -> fetch_val(K, Bkt).

%% find(Key, Dictionary) -> {ok,Value} | error.

find(Key, D) ->
    Slot = get_slot(D, Key),
    Bkt = get_bucket(D, Slot),
    find_val(Key, Bkt).

find_val(K, [?kv(K,Val)|_]) -> {ok,Val};
find_val(K, [_|Bkt]) -> find_val(K, Bkt);
find_val(_, []) -> error.

%% fetch_keys(Dictionary) -> [Key].

fetch_keys(D) ->
    fold(fun (Key, _Val, Keys) -> [Key|Keys] end, [], D).

%% erase(Key, Dictionary) -> NewDictionary.
%%  Erase all elements with key Key.

erase(Key, D0) -> 
    Slot = get_slot(D0, Key),
    {D1,Dc} = on_bucket(fun (B0) -> erase_key(Key, B0) end,
			D0, Slot),
    maybe_contract(D1, Dc).

erase_key(Key, [?kv(Key,_Val)|Bkt]) -> {Bkt,1};
erase_key(Key, [E|Bkt0]) ->
    {Bkt1,Dc} = erase_key(Key, Bkt0),
    {[E|Bkt1],Dc};
erase_key(_, []) -> {[],0}.

%% store(Key, Value, Dictionary) -> Dictionary.

store(Key, Val, D0) ->
    Slot = get_slot(D0, Key),
    {D1,Ic} = on_bucket(fun (B0) -> store_bkt_val(Key, Val, B0) end,
			D0, Slot),
    maybe_expand(D1, Ic).

%% store_bkt_val(Key, Val, Bucket) -> {NewBucket,PutCount}.

store_bkt_val(Key, New, [?kv(Key,_Old)|Bkt]) -> {[?kv(Key,New)|Bkt],0};
store_bkt_val(Key, New, [Other|Bkt0]) ->
    {Bkt1,Ic} = store_bkt_val(Key, New, Bkt0),
    {[Other|Bkt1],Ic};
store_bkt_val(Key, New, []) -> {[?kv(Key,New)],1}.

%% append(Key, Value, Dictionary) -> Dictionary.

append(Key, Val, D0) ->
    Slot = get_slot(D0, Key),
    {D1,Ic} = on_bucket(fun (B0) -> append_bkt(Key, Val, B0) end,
			D0, Slot),
    maybe_expand(D1, Ic).

%% append_bkt(Key, Val, Bucket) -> {NewBucket,PutCount}.

append_bkt(Key, Val, [?kv(Key,Bag)|Bkt]) -> {[?kv(Key,Bag ++ [Val])|Bkt],0};
append_bkt(Key, Val, [Other|Bkt0]) ->
    {Bkt1,Ic} = append_bkt(Key, Val, Bkt0),
    {[Other|Bkt1],Ic};
append_bkt(Key, Val, []) -> {[?kv(Key,[Val])],1}.

%% append_list(Key, List, Dictionary) -> Dictionary.

append_list(Key, L, D0) ->
    Slot = get_slot(D0, Key),
    {D1,Ic} = on_bucket(fun (B0) -> app_list_bkt(Key, L, B0) end,
			D0, Slot),
    maybe_expand(D1, Ic).

%% app_list_bkt(Key, L, Bucket) -> {NewBucket,PutCount}.

app_list_bkt(Key, L, [?kv(Key,Bag)|Bkt]) -> {[?kv(Key,Bag ++ L)|Bkt],0};
app_list_bkt(Key, L, [Other|Bkt0]) ->
    {Bkt1,Ic} = app_list_bkt(Key, L, Bkt0),
    {[Other|Bkt1],Ic};
app_list_bkt(Key, L, []) -> {[?kv(Key,L)],1}.

% %% first_key(Table) -> {ok,Key} | error.
% %%  Find the "first" key in a Table.

% first_key(T) ->
%     case next_bucket(T, 1) of
% 	[?kv(K,Val)|Bkt] -> {ok,K};
% 	[] -> error				%No elements
%     end.

% next_bucket(T, Slot) when Slot > T#dict.n -> [];
% next_bucket(T, Slot) ->
%     case get_bucket(T, Slot) of
% 	[] -> next_bucket(T, Slot+1);		%Empty bucket
% 	B -> B
%     end.

%% next_key(Table, Key) -> {ok,NextKey} | error.

% next_key(T, Key) ->
%     Slot = get_slot(T, Key),
%     B = get_bucket(T, Slot),
%     %% Find a bucket with something in it.
%     Bkt = case bucket_after_key(Key, B) of
% 	      no_key -> exit(badarg);
% 	      [] -> next_bucket(T, Slot+1);
% 	      Rest -> Rest
% 	  end,
%     case Bkt of
% 	[?kv(Next,Val)|_] -> {ok,Next};
% 	[] -> error				%We have reached the end!
%     end.

% bucket_after_key(Key, [?kv(Key,Val)|Bkt]) -> Bkt;
% bucket_after_key(Key, [Other|Bkt]) ->
%     bucket_after_key(Key, Bkt);
% bucket_after_key(Key, []) -> no_key.		%Key not found!

%% on_key(Fun, Key, Dictionary) -> Dictionary.

% on_key(F, Key, D0) ->
%     Slot = get_slot(D0, Key),
%     {D1,Dc} = on_bucket(fun (B0) -> on_key_bkt(Key, F, B0) end,
% 			D0, Slot),
%     maybe_contract(D1, Dc).

% on_key_bkt(Key, F, [?kv(Key,Val)|Bkt]) ->
%     case F(Val) of
% 	{ok,New} -> {[?kv(Key,New)|Bkt],0}; 
% 	erase -> {Bkt,1}
%     end;
% on_key_bkt(Key, F, [Other|Bkt0]) ->
%     {Bkt1,Dc} = on_key_bkt(Key, F, Bkt0),
%     {[Other|Bkt1],Dc}.

%% update(Key, Fun, Dictionary) -> Dictionary.

update(Key, F, D0) ->
    Slot = get_slot(D0, Key),
    {D1,_Uv} = on_bucket(fun (B0) -> update_bkt(Key, F, B0) end, D0, Slot),
    D1.

update_bkt(Key, F, [?kv(Key,Val)|Bkt]) ->
    Upd = F(Val),
    {[?kv(Key,Upd)|Bkt],Upd};
update_bkt(Key, F, [Other|Bkt0]) ->
    {Bkt1,Upd} = update_bkt(Key, F, Bkt0),
    {[Other|Bkt1],Upd}.

%% update(Key, Fun, Init, Dictionary) -> Dictionary.

update(Key, F, Init, D0) ->
    Slot = get_slot(D0, Key),
    {D1,Ic} = on_bucket(fun (B0) -> update_bkt(Key, F, Init, B0) end,
			D0, Slot),
    maybe_expand(D1, Ic).

update_bkt(Key, F, _, [?kv(Key,Val)|Bkt]) ->
    {[?kv(Key,F(Val))|Bkt],0};
update_bkt(Key, F, I, [Other|Bkt0]) ->