1 files changed, 113 insertions, 60 deletions

diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 8a336765f9..337567406b 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 2014-2022. All Rights Reserved.
+ * Copyright Ericsson AB 2014-2023. All Rights Reserved.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -151,6 +151,9 @@ void erts_init_map(void) {
 
 BIF_RETTYPE map_size_1(BIF_ALIST_1) {
     Sint size = erts_map_size(BIF_ARG_1);
+
+    /* NOTE: The JIT has its own implementation of this BIF. */
+
     if (size < 0) {
         BIF_P->fvalue = BIF_ARG_1;
         BIF_ERROR(BIF_P, BADMAP);
@@ -267,6 +270,7 @@ BIF_RETTYPE maps_get_2(BIF_ALIST_2) {
 }
 
 BIF_RETTYPE map_get_2(BIF_ALIST_2) {
+    /* NOTE: The JIT has its own implementation of this BIF. */
     BIF_RET(maps_get_2(BIF_CALL_ARGS));
 }
 
@@ -433,7 +437,9 @@ static Eterm flatmap_from_validated_list(Process *p, Eterm list, Eterm fill_valu
 
 	idx = size;
 
-	while(idx > 0 && (c = CMP_TERM(key,ks[idx-1])) < 0) { idx--; }
+	while(idx > 0 && (c = erts_cmp_flatmap_keys(key,ks[idx-1])) < 0) {
+            idx--;
+        }
 
 	if (c == 0) {
 	    /* last compare was equal,
@@ -700,15 +706,10 @@ from_ks_and_vs(ErtsHeapFactory *factory, Eterm *ks, Eterm *vs,
 
         sys_memcpy((void *) hp, (void *) vs, n * sizeof(Eterm));
 
-        if (fmpp) {
-            *fmpp = fmp;
-            return THE_NON_VALUE;
-        }
-        return make_flatmap(fmp);
+        *fmpp = fmp;
+        return THE_NON_VALUE;
     } else {
-        if (fmpp) {
-            *fmpp = NULL;
-        }
+        *fmpp = NULL;
         return erts_hashmap_from_ks_and_vs(factory, ks, vs, n);
     }
 }
@@ -730,21 +731,6 @@ Eterm erts_map_from_ks_and_vs(ErtsHeapFactory *factory, Eterm *ks, Eterm *vs, Ui
     return res;
 }
 
-Eterm erts_map_from_sorted_ks_and_vs(ErtsHeapFactory *factory, Eterm *ks, Eterm *vs,
-                                     Uint n)
-{
-#ifdef DEBUG
-    Uint i; 
-    /* verify that key array contains unique and sorted keys... */
-    for (i = 1; i < n; i++) {
-        ASSERT(CMP_TERM(ks[i-1], ks[i]) < 0);
-    }
-#endif
-
-    return from_ks_and_vs(factory, ks, vs, n, NULL);
-}
-
-
 Eterm erts_hashmap_from_ks_and_vs_extra(ErtsHeapFactory *factory,
                                         Eterm *ks, Eterm *vs, Uint n,
 					Eterm key, Eterm value) {
@@ -801,14 +787,7 @@ static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory,
     Uint cx;
     Eterm res;
 
-    if (n == 0) {
-	Eterm *hp;
-	hp = erts_produce_heap(factory, 2, 0);
-	hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0);
-	hp[1] = 0;
-
-	return make_hashmap(hp);
-    }
+    ASSERT(n > 0);
 
     /* sort and compact array (remove non-unique entries) */
     erts_qsort(hxns, n, sizeof(hxnode_t), hxnodecmp);
@@ -1225,6 +1204,7 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) {
 }
 
 BIF_RETTYPE is_map_key_2(BIF_ALIST_2) {
+    /* NOTE: The JIT has its own implementation of this BIF. */
     BIF_RET(maps_is_key_2(BIF_CALL_ARGS));
 }
 
@@ -1316,34 +1296,31 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
     BIF_ERROR(BIF_P, BADMAP);
 }
 
-static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
+static Eterm flatmap_merge(Process *p, Eterm map1, Eterm map2) {
     Eterm *hp,*thp;
-    Eterm tup;
     Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2;
     flatmap_t *mp1,*mp2,*mp_new;
     Uint n,n1,n2,i1,i2,need,unused_size=0;
     Sint c = 0;
 
-    mp1  = (flatmap_t*)flatmap_val(nodeA);
-    mp2  = (flatmap_t*)flatmap_val(nodeB);
+    mp1  = (flatmap_t*)flatmap_val(map1);
+    mp2  = (flatmap_t*)flatmap_val(map2);
     n1   = flatmap_get_size(mp1);
     n2   = flatmap_get_size(mp2);
 
-    if (n1 == 0) return nodeB;
-    if (n2 == 0) return nodeA;
+    if (n1 == 0) return map2;
+    if (n2 == 0) return map1;
 
     need = MAP_HEADER_FLATMAP_SZ + 1 + 2 * (n1 + n2);
 
     hp     = HAlloc(p, need);
-    thp    = hp;
-    tup    = make_tuple(thp);
-    ks     = hp + 1; hp += 1 + n1 + n2;
     mp_new = (flatmap_t*)hp; hp += MAP_HEADER_FLATMAP_SZ;
     vs     = hp; hp += n1 + n2;
+    thp    = hp;
+    ks     = hp + 1; hp += 1 + n1 + n2;
 
     mp_new->thing_word = MAP_HEADER_FLATMAP;
-    mp_new->size = 0;
-    mp_new->keys = tup;
+    mp_new->keys = make_tuple(thp);
 
     i1  = 0; i2 = 0;
     ks1 = flatmap_get_keys(mp1);
@@ -1352,7 +1329,7 @@ static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
     vs2 = flatmap_get_values(mp2);
 
     while(i1 < n1 && i2 < n2) {
-	c = CMP_TERM(ks1[i1],ks2[i2]);
+	c = (ks1[i1] == ks2[i2]) ? 0 : erts_cmp_flatmap_keys(ks1[i1],ks2[i2]);
 	if (c == 0) {
 	    /* use righthand side arguments map value,
 	     * but advance both maps */
@@ -1383,20 +1360,42 @@ static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
 	i2++;
     }
 
-    if (unused_size) {
-	/* the key tuple is embedded in the heap, write a bignum to clear it.
-	 *
-	 * release values as normal since they are on the top of the heap
-	 * size = n1 + n1 - unused_size
-	 */
-
-	*ks = make_pos_bignum_header(unused_size - 1);
-	HRelease(p, vs + unused_size, vs);
-    }
-
     n = n1 + n2 - unused_size;
-    *thp = make_arityval(n);
     mp_new->size = n;
+    *thp = make_arityval(n);
+
+    if (unused_size ) {
+        Eterm* hp_release;
+
+        if (n == n2) {
+            /* Reuse entire map2 */
+            if (n == n1
+                &&  erts_is_literal(mp1->keys, boxed_val(mp1->keys))
+                && !erts_is_literal(mp2->keys, boxed_val(mp2->keys))) {
+                /*
+                 * We want map2, but map1 has a nice literal key tuple.
+                 * Solution: MUTATE HEAP to get both.
+                 */
+                ASSERT(eq(mp1->keys, mp2->keys));
+                mp2->keys = mp1->keys;
+            }
+            HRelease(p, hp, (Eterm *)mp_new);
+            return map2;
+        }
+        else if (n == n1) {
+            /* Reuse key tuple of map1 */
+            mp_new->keys = mp1->keys;
+            /* Release key tuple and unused values */
+            hp_release = thp - unused_size;
+        }
+        else {
+            /* Unused values are embedded in the heap, write bignum to clear them */
+            *vs = make_pos_bignum_header(unused_size - 1);
+            /* Release unused keys */
+            hp_release = ks;
+        }
+	HRelease(p, hp, hp_release);
+    }
 
     /* Reshape map to a hashmap if the map exceeds the limit */
 
@@ -2201,7 +2200,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 	ASSERT(n >= 0);
 
 	/* copy map in order */
-	while (n && ((c = CMP_TERM(*ks, key)) < 0)) {
+	while (n && ((c = erts_cmp_flatmap_keys(*ks, key)) < 0)) {
 	    *shp++ = *ks++;
 	    *hp++  = *vs++;
 	    n--;
@@ -3200,7 +3199,7 @@ int erts_validate_and_sort_flatmap(flatmap_t* mp)
 
     for (ix = 1; ix < sz; ix++) {
 	jx = ix;
-	while( jx > 0 && (c = CMP_TERM(ks[jx],ks[jx-1])) <= 0 ) {
+	while( jx > 0 && (c = erts_cmp_flatmap_keys(ks[jx],ks[jx-1])) <= 0 ) {
 	    /* identical key -> error */
 	    if (c == 0) return 0;
 
@@ -3231,7 +3230,7 @@ void erts_usort_flatmap(flatmap_t* mp)
 
     for (ix = 1; ix < sz; ix++) {
 	jx = ix;
-	while( jx > 0 && (c = CMP_TERM(ks[jx],ks[jx-1])) <= 0 ) {
+	while( jx > 0 && (c = erts_cmp_flatmap_keys(ks[jx],ks[jx-1])) <= 0 ) {
 	    /* identical key -> remove it */
 	    if (c == 0) {
                 sys_memmove(ks+jx-1,ks+jx,(sz-ix)*sizeof(Eterm));
@@ -3656,6 +3655,60 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) {
         BIF_ERROR(BIF_P, BADARG);
     }
 
+    /* Handle an ordered iterator. */
+    if (type == iterator && (is_list(path) || is_nil(path))) {
+#ifdef DEBUG
+#define ORDERED_ITER_FACTOR 200
+#else
+#define ORDERED_ITER_FACTOR 32
+#endif
+        int orig_elems = MAX(1, ERTS_BIF_REDS_LEFT(BIF_P) / ORDERED_ITER_FACTOR);
+        int elems = orig_elems;
+        Uint needed = 4 * elems + 2;
+        Eterm *hp = HAlloc(BIF_P, needed);
+        Eterm *hp_end = hp + needed;
+        Eterm result = am_none;
+        Eterm *patch_ptr = &result;
+
+        while (is_list(path) && elems > 0) {
+            Eterm *lst = list_val(path);
+            Eterm key = CAR(lst);
+            Eterm res = make_tuple(hp);
+            const Eterm *value = erts_maps_get(key, map);
+            if (!value) {
+            ordered_badarg:
+                HRelease(BIF_P, hp_end, hp);
+                BIF_ERROR(BIF_P, BADARG);
+            }
+            hp[0] = make_arityval(3);
+            hp[1] = key;
+            hp[2] = *value;
+            *patch_ptr = res;
+            patch_ptr = &hp[3];
+            hp += 4;
+            path = CDR(lst);
+            elems--;
+        }
+
+        if (is_list(path)) {
+            Eterm next = CONS(hp, path, map);
+            hp += 2;
+            ASSERT(hp == hp_end);
+            *patch_ptr = next;
+            BUMP_ALL_REDS(BIF_P);
+            ASSERT(is_tuple(result));
+            BIF_RET(result);
+        } else if (is_nil(path)) {
+            HRelease(BIF_P, hp_end, hp);
+            *patch_ptr = am_none;
+            BUMP_REDS(BIF_P, ORDERED_ITER_FACTOR * (orig_elems - elems));
+            ASSERT(result == am_none || is_tuple(result));
+            BIF_RET(result);
+        } else {
+            goto ordered_badarg;
+        }
+    }
+
     if (is_flatmap(map)) {
         Uint n;
 	Eterm *ks,*vs, res, *hp;