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/doc/src/erl_ext_dist.xml | 13 ++--- erts/emulator/beam/external.c | 55 +++++++--------------- erts/emulator/test/map_SUITE.erl | 19 +++++--- lib/debugger/test/map_SUITE.erl | 9 ++-- lib/erl_interface/doc/src/ei.xml | 18 ++++--- .../ei_decode_encode_test.c | 5 +- .../com/ericsson/otp/erlang/OtpErlangMap.java | 4 -- .../test/jinterface_SUITE_data/Maps.java | 8 ++-- 8 files changed, 56 insertions(+), 75 deletions(-) diff --git a/erts/doc/src/erl_ext_dist.xml b/erts/doc/src/erl_ext_dist.xml index 9a53f3f829..fa083db4c7 100644 --- a/erts/doc/src/erl_ext_dist.xml +++ b/erts/doc/src/erl_ext_dist.xml @@ -581,23 +581,20 @@ 1 4 N - M 116 Arity - Keys - Values + Pairs

MAP_EXT encodes a map. The Arity field is an unsigned 4 byte integer in big endian format that determines the number of - key-value pairs in the map. All key terms follow in the Keys - section and then all value terms in the Values section. Keys - and values are paired according to order; first key with first value - and so on. Duplicate keys are not allowed within the same - map. + key-value pairs in the map. Key and value pairs (Ki => Vi) + are encoded in the Pairs section in the following order: + K1, V1, K2, V2,..., Kn, Vn. + Duplicate keys are not allowed within the same map.

Since: OTP 17.0

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); diff --git a/lib/debugger/test/map_SUITE.erl b/lib/debugger/test/map_SUITE.erl index e9f4ea1fad..741ad2dc41 100644 --- a/lib/debugger/test/map_SUITE.erl +++ b/lib/debugger/test/map_SUITE.erl @@ -790,16 +790,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() >>), @@ -829,7 +829,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); diff --git a/lib/erl_interface/doc/src/ei.xml b/lib/erl_interface/doc/src/ei.xml index 1756ee8a7d..90495eebd6 100644 --- a/lib/erl_interface/doc/src/ei.xml +++ b/lib/erl_interface/doc/src/ei.xml @@ -422,19 +422,18 @@ ei_x_encode_empty_list(&x); Encode a map

This function encodes a map header, with a specified arity. The next - arity terms encoded will be the keys of the map, and the next - arity terms after that will be the corresponding values in - same order.

+ arity*2 terms encoded will be the keys and values of the map + encoded in the following order: K1, V1, K2, V2, ..., Kn, Vn. +

E.g. to encode the map #{a => "Apple", b => "Banana"}:

 ei_x_encode_map_header(&x, 2);
 ei_x_encode_atom(&x, "a");
-ei_x_encode_atom(&x, "b");
 ei_x_encode_string(&x, "Apple");
+ei_x_encode_atom(&x, "b");
 ei_x_encode_string(&x, "Banana");
-

A correctly encoded map can not have duplicate keys, but no check - for duplicate keys is done by this function.

+

A correctly encoded map can not have duplicate keys.

 @@ -664,10 +663,9 @@ ei_x_encode_string(&x, "Banana");

This function decodes a map header from the binary format. The number of key-value pairs is returned in - arity. Keys and values follows, first all keys and then all values, - which makes a total of arity*2 terms. - Keys and values are paired according to their order, the first key - with the first value and so on. If arity is zero, it's an empty map. + *arity. Keys and values follow in the following order: + K1, V1, K2, V2, ..., Kn, Vn. This makes a total of + arity*2 terms. If arity is zero, it's an empty map. A correctly encoded map does not have duplicate keys.

 diff --git a/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c b/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c index 790d498a1d..fcf546105b 100644 --- a/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c +++ b/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c @@ -527,8 +527,9 @@ TESTCASE(test_ei_decode_encode) { /* #{atom => atom, atom => pid, port => ref }*/ struct Type* map[] = { &map_type, - &my_atom_type, &my_atom_type, &port_type, - &my_atom_type, &pid_type, &ref_type + &my_atom_type, &my_atom_type, + &my_atom_type, &pid_type, + &port_type, &ref_type }; decode_encode(map, 7); } diff --git a/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java b/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java index 7c1cf84e98..03c18e55a2 100644 --- a/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java +++ b/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java @@ -125,8 +125,6 @@ public class OtpErlangMap extends OtpErlangObject implements Serializable, for (int i = 0; i < arity; i++) { keys[i] = buf.read_any(); - } - for (int i = 0; i < arity; i++) { values[i] = buf.read_any(); } } else { @@ -227,8 +225,6 @@ public class OtpErlangMap extends OtpErlangObject implements Serializable, for (int i = 0; i < arity; i++) { buf.write_any(keys[i]); - } - for (int i = 0; i < arity; i++) { buf.write_any(values[i]); } } diff --git a/lib/jinterface/test/jinterface_SUITE_data/Maps.java b/lib/jinterface/test/jinterface_SUITE_data/Maps.java index 136a665f23..653defc621 100644 --- a/lib/jinterface/test/jinterface_SUITE_data/Maps.java +++ b/lib/jinterface/test/jinterface_SUITE_data/Maps.java @@ -42,16 +42,16 @@ class Maps { runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 1, 100, 0, 1, 97, 100, 0, 1, 98 }, "#{a => b}", 2); // make sure keys are sorted here, jinterface doesn't reorder them - runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 100, 0, 1, 97, - 106, 97, 1 }, "#{2 => [],a => 1}", 3); + runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 106, + 100, 0, 1, 97, 97, 1 }, "#{2 => [],a => 1}", 3); runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 1, 104, 1, 97, 3, 108, 0, 0, 0, 1, 100, 0, 1, 114, 106 }, "#{{3} => [r]}", 4); try { // #{2 => [],a => 1} final OtpErlangMap map = new OtpErlangMap(new OtpInputStream( - new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 100, 0, 1, - 97, 106, 97, 1 })); + new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 106, + 100, 0, 1, 97, 97, 1 })); if (map.arity() != 2) { fail(5); -- cgit v1.2.3