From 39c35199f5118a59f337b695a934c6bfcbf0813b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 13 Jan 2014 16:23:56 +0100 Subject: erts: Let erlang:binary_to_term/1 handle unsorted Maps Maps may be encoded with keys in arbitrary order. This is fine, as long as keys are unique. --- erts/emulator/beam/external.c | 35 ++++++++++++++++++++++++++--------- 1 file changed, 26 insertions(+), 9 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index e8b77b9f37..57251286c8 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -3790,24 +3790,41 @@ dec_term_atom_common: } } - /* Iterate through all the maps and check for validity + /* Iterate through all the maps and check for validity and sort keys * - done here for when we know it is complete. */ while (maps_head) { - Eterm *keys; - Sint arity; + map_t *mp = (map_t*)maps_head; + Eterm *ks = map_get_keys(mp); + Eterm *vs = map_get_values(mp); + Uint sz = map_get_size(mp); + Uint ix,jx; + Eterm tmp; + int c; next = (Eterm *)(EXPAND_POINTER(*maps_head)); - keys = tuple_val(*(maps_head + 2)); - arity = arityval(*keys++); - while(arity-- > 1) { - if (CMP_TERM(keys[arity-1],keys[arity]) >= 0) { - goto error; + /* sort */ + + for ( ix = 1; ix < sz; ix++) { + jx = ix; + while( jx > 0 && (c = CMP_TERM(ks[jx],ks[jx-1])) <= 0 ) { + /* identical key -> error */ + if (c == 0) goto error; + + tmp = ks[jx]; + ks[jx] = ks[jx - 1]; + ks[jx - 1] = tmp; + + tmp = vs[jx]; + vs[jx] = vs[jx - 1]; + vs[jx - 1] = tmp; + + jx--; } - } + } *maps_head = MAP_HEADER; maps_head = next; } -- cgit v1.2.3