From c543d5bff7fb23c3f44cc4817c0654117de78919 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 12 Mar 2014 20:11:10 +0100 Subject: erts: Change external format for maps to be: 116,Arity, K1,V1,K2,V2,...,Kn,Vn instead of: 116,Arity, K1,K2,...,Kn, V1,V2,....,Vn We think this will be better for future internal map structures like HAMT. Would be bad if we need to iterate twice over HAMT in term_to_binary, one for keys and one for values. --- erts/emulator/beam/external.c | 55 +++++++++++++--------------------------- erts/emulator/test/map_SUITE.erl | 19 +++++++++----- 2 files changed, 31 insertions(+), 43 deletions(-) (limited to 'erts/emulator') diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index 9671cde228..656de7c49a 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -2562,29 +2562,25 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, { map_t *mp = (map_t*)map_val(obj); Uint size = map_get_size(mp); - Eterm *mptr; *ep++ = MAP_EXT; put_int32(size, ep); ep += 4; - /* Push values first */ if (size > 0) { - mptr = map_get_values(mp); + Eterm *kptr = map_get_keys(mp); + Eterm *vptr = map_get_values(mp); + for (i = size-1; i >= 1; i--) { WSTACK_PUSH(s, ENC_TERM); - WSTACK_PUSH(s, (UWord) mptr[i]); + WSTACK_PUSH(s, (UWord) vptr[i]); + WSTACK_PUSH(s, ENC_TERM); + WSTACK_PUSH(s, (UWord) kptr[i]); } WSTACK_PUSH(s, ENC_TERM); - WSTACK_PUSH(s, (UWord) mptr[0]); - - mptr = map_get_keys(mp); - for (i = size-1; i >= 1; i--) { - WSTACK_PUSH(s, ENC_TERM); - WSTACK_PUSH(s, (UWord) mptr[i]); - } + WSTACK_PUSH(s, (UWord) vptr[0]); - obj = mptr[0]; + obj = kptr[0]; goto L_jump_start; } } @@ -3518,16 +3514,16 @@ dec_term_atom_common: keys = make_tuple(hp); *hp++ = make_arityval(size); - kptr = hp; hp += size; + kptr = hp - 1; mp = (map_t*)hp; hp += MAP_HEADER_SIZE; - vptr = hp; hp += size; + vptr = hp - 1; - /* kptr, first word for keys - * vptr, first word for values + /* kptr, last word for keys + * vptr, last word for values */ /* @@ -3542,27 +3538,12 @@ dec_term_atom_common: mp->keys = keys; *objp = make_map(mp); - /* We assume the map is wellformed, meaning: - * - ascending key order - * - unique keys - */ - - objp = vptr + size - 1; - n = size; - - while (n-- > 0) { - *objp = (Eterm) COMPRESS_POINTER(next); - next = objp; - objp--; - } - - objp = kptr + size - 1; - n = size; - - while (n-- > 0) { - *objp = (Eterm) COMPRESS_POINTER(next); - next = objp; - objp--; + for (n = size; n; n--) { + *vptr = (Eterm) COMPRESS_POINTER(next); + *kptr = (Eterm) COMPRESS_POINTER(vptr); + next = kptr; + vptr--; + kptr--; } } break; diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 753d6f7727..888ed8e272 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -813,16 +813,16 @@ t_map_encode_decode(Config) when is_list(Config) -> %% literally #{ b=>2, a=>1 } in the internal order #{ a:=1, b:=2 } = - erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,100,0,1,97,97,2,97,1>>), + erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,97,2,100,0,1,97,97,1>>), %% literally #{ "hi" => "value", a=>33, b=>55 } in the internal order #{ a:=33, b:=55, "hi" := "value"} = erlang:binary_to_term(<<131,116,0,0,0,3, 107,0,2,104,105, % "hi" :: list() - 100,0,1,97, % a :: atom() - 100,0,1,98, % b :: atom() 107,0,5,118,97,108,117,101, % "value" :: list() + 100,0,1,97, % a :: atom() 97,33, % 33 :: integer() + 100,0,1,98, % b :: atom() 97,55 % 55 :: integer() >>), @@ -834,11 +834,17 @@ t_map_encode_decode(Config) when is_list(Config) -> %% uniqueness violation %% literally #{ a=>1, "hi"=>"value", a=>2 } {'EXIT',{badarg,[{_,_,_,_}|_]}} = (catch - erlang:binary_to_term(<<131,116,0,0,0,3,100,0,1,97,107,0,2,104,105,100,0,1,97,97,1,107,0,5,118,97,108,117,101,97,2>>)), + erlang:binary_to_term(<<131,116,0,0,0,3, + 100,0,1,97, + 97,1, + 107,0,2,104,105, + 107,0,5,118,97,108,117,101, + 100,0,1,97, + 97,2>>)), %% bad size (too large) {'EXIT',{badarg,[{_,_,_,_}|_]}} = (catch - erlang:binary_to_term(<<131,116,0,0,0,12,100,0,1,97,100,0,1,98,97,1,97,1>>)), + erlang:binary_to_term(<<131,116,0,0,0,12,100,0,1,97,97,1,100,0,1,98,97,1>>)), %% bad size (too small) .. should fail just truncate it .. weird. %% possibly change external format so truncated will be #{a:=1} @@ -852,7 +858,8 @@ map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, M0) -> B0 = erlang:term_to_binary(M1), Ls = lists:sort(fun(A,B) -> erts_internal:cmp_term(A,B) < 0 end, [{K, erlang:term_to_binary(K), erlang:term_to_binary(V)}|EncodedPairs]), %% sort Ks and Vs according to term spec, then match it - ok = match_encoded_map(B0, length(Ls), [Kbin||{_,Kbin,_}<-Ls] ++ [Vbin||{_,_,Vbin}<-Ls]), + KVbins = lists:foldr(fun({_,Kbin,Vbin}, Acc) -> [Kbin,Vbin | Acc] end, [], Ls), + ok = match_encoded_map(B0, length(Ls), KVbins), %% decode and match it M1 = erlang:binary_to_term(B0), map_encode_decode_and_match(Pairs,Ls,M1); -- cgit v1.2.3