aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bootstrap/lib/stdlib/ebin/maps.beambin2864 -> 3364 bytes
-rw-r--r--erts/emulator/beam/atom.names1
-rw-r--r--erts/emulator/beam/bif.tab3
-rw-r--r--erts/emulator/beam/erl_map.c375
-rw-r--r--erts/emulator/test/map_SUITE.erl57
-rw-r--r--erts/preloaded/ebin/erts_internal.beambin12100 -> 12128 bytes
-rw-r--r--erts/preloaded/src/erts_internal.erl17
-rw-r--r--lib/hipe/cerl/erl_bif_types.erl20
-rw-r--r--lib/stdlib/doc/src/maps.xml52
-rw-r--r--lib/stdlib/src/maps.erl61
-rw-r--r--lib/stdlib/test/maps_SUITE.erl39
11 files changed, 282 insertions, 343 deletions
diff --git a/bootstrap/lib/stdlib/ebin/maps.beam b/bootstrap/lib/stdlib/ebin/maps.beam
index f07f4f922d..6820b81db5 100644
--- a/bootstrap/lib/stdlib/ebin/maps.beam
+++ b/bootstrap/lib/stdlib/ebin/maps.beam
Binary files differ
diff --git a/erts/emulator/beam/atom.names b/erts/emulator/beam/atom.names
index fc55b687d4..42a6991c6e 100644
--- a/erts/emulator/beam/atom.names
+++ b/erts/emulator/beam/atom.names
@@ -352,6 +352,7 @@ atom instruction_counts
atom invalid
atom is_constant
atom is_seq_trace
+atom iterator
atom io
atom keypos
atom kill
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index f2c8331850..b7b66e2ee7 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -629,7 +629,6 @@ bif re:inspect/2
ubif erlang:is_map/1
gcbif erlang:map_size/1
-bif maps:to_list/1
bif maps:find/2
bif maps:get/2
bif maps:from_list/1
@@ -695,4 +694,4 @@ bif erlang:iolist_to_iovec/1
# New in 21.0
#
-bif erts_internal:map_next/2
+bif erts_internal:map_next/3
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index a5fda7b86d..135053dd18 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -139,35 +139,6 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) {
BIF_ERROR(BIF_P, BADMAP);
}
-/* maps:to_list/1 */
-
-BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) {
- if (is_flatmap(BIF_ARG_1)) {
- Uint n;
- Eterm* hp;
- Eterm *ks,*vs, res, tup;
- flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
-
- ks = flatmap_get_keys(mp);
- vs = flatmap_get_values(mp);
- n = flatmap_get_size(mp);
- hp = HAlloc(BIF_P, (2 + 3) * n);
- res = NIL;
-
- while(n--) {
- tup = TUPLE2(hp, ks[n], vs[n]); hp += 3;
- res = CONS(hp, tup, res); hp += 2;
- }
-
- BIF_RET(res);
- } else if (is_hashmap(BIF_ARG_1)) {
- return hashmap_to_list(BIF_P, BIF_ARG_1, -1);
- }
-
- BIF_P->fvalue = BIF_ARG_1;
- BIF_ERROR(BIF_P, BADMAP);
-}
-
/* erts_internal:maps_to_list/2
*
* This function should be removed once iterators are in place.
@@ -1986,21 +1957,31 @@ static Eterm hashmap_to_list(Process *p, Eterm node, Sint m) {
return res;
}
-void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) {
- Eterm hdr = *hashmap_val(node);
+static ERTS_INLINE
+Uint hashmap_node_size(Eterm hdr, Eterm **nodep)
+{
Uint sz;
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
case HAMT_SUBTAG_HEAD_ARRAY:
sz = 16;
+ if (nodep) ++*nodep;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
+ if (nodep) ++*nodep;
case HAMT_SUBTAG_NODE_BITMAP:
sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
+ ASSERT(sz < 17);
break;
default:
erts_exit(ERTS_ABORT_EXIT, "bad header");
}
+ return sz;
+}
+
+void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) {
+ Eterm hdr = *hashmap_val(node);
+ Uint sz = hashmap_node_size(hdr, NULL);
WSTACK_PUSH3((*s), (UWord)THE_NON_VALUE, /* end marker */
(UWord)(!reverse ? 0 : sz+1),
@@ -2024,20 +2005,7 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) {
ptr = boxed_val(node);
hdr = *ptr;
ASSERT(is_header(hdr));
- switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY:
- ptr++;
- sz = 16;
- break;
- case HAMT_SUBTAG_HEAD_BITMAP:
- ptr++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
- ASSERT(sz < 17);
- break;
- default:
- erts_exit(ERTS_ABORT_EXIT, "bad header");
- }
+ sz = hashmap_node_size(hdr, &ptr);
idx++;
@@ -2074,20 +2042,7 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) {
ptr = boxed_val(node);
hdr = *ptr;
ASSERT(is_header(hdr));
- switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY:
- ptr++;
- sz = 16;
- break;
- case HAMT_SUBTAG_HEAD_BITMAP:
- ptr++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
- ASSERT(sz < 17);
- break;
- default:
- erts_exit(ERTS_ERROR_EXIT, "bad header");
- }
+ sz = hashmap_node_size(hdr, &ptr);
if (idx > sz)
idx = sz;
@@ -3061,15 +3016,7 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
}
-/*
- * The iterator work in about the same way for both
- * flat- and hash-maps. It consists of a Path, Map
- * term where Path describes where to find the
- * term to get.
- *
- * In flatmap Path is just the index of the element
- * in the flatmap array.
- *
+/**
* In hashmap the Path is a bit pattern that describes
* which slot we should traverse in each hashmap node.
* Since each hashmap node can only be up to 16 elements
@@ -3079,17 +3026,35 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
* slot in the head node, and then the 1:st slot in the
* resulting node and then finally the 1:st slot in the
* node beneath. If that slot is not a leaf, then the path
- * continues down the 0:th slot until it finds a leaf and
- * returns that leaf.
+ * continues down the 0:th slot until it finds a leaf.
*
- * Once the leaf has been found, the Path to the next leaf
- * is built using a stack that was created while traversing
- * the tree down.
+ * Once the leaf has been found, the return value is created
+ * by traversing the tree using the the stack that was built
+ * when searching for the first leaf to return.
*
* The index can become a bignum, which complicates the code
* a bit. However it should be very rare that this happens
* even on a 32bit system as you would need a tree of depth
* 7 or more.
+ *
+ * If the number of elements remaining in the map is greater
+ * than how many we want to return, we build a new Path, using
+ * the stack, that points to the next leaf.
+ *
+ * The third argument to this function controls how the data
+ * is returned.
+ *
+ * iterator: The key-value associations are to be used by
+ * maps:iterator. The return has this format:
+ * {K1,V1,{K2,V2,none | [Path | Map]}}
+ * this makes the maps:next function very simple
+ * and performant.
+ *
+ * list(): The key-value associations are to be used by
+ * maps:to_list. The return has this format:
+ * [Path, Map | [{K1,V1},{K2,V2} | BIF_ARG_3]]
+ * or if no more associations remain
+ * [{K1,V1},{K2,V2} | BIF_ARG_3]
*/
#define PATH_ELEM_SIZE 4
@@ -3097,10 +3062,24 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
#define PATH_ELEM(PATH) ((PATH) & PATH_ELEM_MASK)
#define PATH_ELEMS_PER_DIGIT (sizeof(ErtsDigit) * 8 / PATH_ELEM_SIZE)
-BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
+/* How many elements we return in one call depends on the number of reductions
+ that the process has left to run. In debug we return fewer elements to test
+ the Path implementation better. */
+#if defined(DEBUG)
+#define FCALLS_ELEMS(BIF_P) ((BIF_P->fcalls / 4) & 0xF)
+#else
+#define FCALLS_ELEMS(BIF_P) (BIF_P->fcalls / 4)
+#endif
+
+#define NUM_ELEMS_TO_RETURN(BIF_P, map) \
+ ((MAX(FCALLS_ELEMS(BIF_P), 1) < hashmap_size(map)) ? \
+ MAX(FCALLS_ELEMS(BIF_P), 1) : hashmap_size(map))
- Eterm *hp = NULL, *lst,
- iter, path, map, k, v;
+
+BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) {
+
+ Eterm path, map;
+ enum { iterator, list } type;
path = BIF_ARG_1;
map = BIF_ARG_2;
@@ -3108,41 +3087,65 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
if (!is_map(map))
BIF_ERROR(BIF_P, BADARG);
- if (path == am_none)
- BIF_RET(am_none);
+ if (BIF_ARG_3 == am_iterator) {
+ type = iterator;
+ } else if (is_nil(BIF_ARG_3) || is_list(BIF_ARG_3)) {
+ type = list;
+ } else {
+ BIF_ERROR(BIF_P, BADARG);
+ }
if (is_flatmap(map)) {
- flatmap_t *mp = (flatmap_t *)flatmap_val(map);
- Uint idx, sz = flatmap_get_size(mp);
-
- if (is_not_small(path))
- BIF_ERROR(BIF_P, BADARG);
+ Uint n;
+ Eterm *ks,*vs, res, *hp;
+ flatmap_t *mp = (flatmap_t*)flatmap_val(map);
- idx = unsigned_val(path);
+ ks = flatmap_get_keys(mp);
+ vs = flatmap_get_values(mp);
+ n = flatmap_get_size(mp);
- if (sz == 0) {
- if (idx == 0)
- BIF_RET(am_none);
- else
- BIF_ERROR(BIF_P, BADARG);
- }
+ if (!is_small(BIF_ARG_1) || n < unsigned_val(BIF_ARG_1))
+ BIF_ERROR(BIF_P, BADARG);
- k = flatmap_get_keys(mp)[idx];
- v = flatmap_get_values(mp)[idx];
+ if (type == iterator) {
+ hp = HAlloc(BIF_P, 4 * n);
+ res = am_none;
- if (idx + 1 < sz) {
- path = make_small(idx + 1);
- } else if (idx < sz) {
- path = am_none;
+ while(n--) {
+ res = TUPLE3(hp, ks[n], vs[n], res); hp += 4;
+ }
} else {
- BIF_ERROR(BIF_P, BADARG);
+ hp = HAlloc(BIF_P, (2 + 3) * n);
+ res = BIF_ARG_3;
+
+ while(n--) {
+ Eterm tup = TUPLE2(hp, ks[n], vs[n]); hp += 3;
+ res = CONS(hp, tup, res); hp += 2;
+ }
}
+
+ BIF_RET(res);
} else {
Uint curr_path;
Uint path_length = 0;
Uint *path_rest = NULL;
- int i;
- Eterm node = map;
+ int i, elems = NUM_ELEMS_TO_RETURN(BIF_P, map);
+ Eterm node = map, res, *path_ptr = NULL, *hp;
+
+ /* A stack WSTACK is used when traversing the hashmap.
+ * It contains: node, idx, sz, ptr
+ *
+ * `node` is not really needed, but it is very nice to
+ * have when debugging.
+ *
+ * `idx` always points to the next un-explored entry in
+ * a node. If there are no more un-explored entries,
+ * `idx` is equal to `sz`.
+ *
+ * `sz` is the number of elements in the node.
+ *
+ * `ptr` is a pointer to where the elements of the node begins.
+ */
DECLARE_WSTACK(stack);
ASSERT(is_hashmap(node));
@@ -3152,7 +3155,7 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
} else if (is_big(path)) {
Eterm *big = big_val(path);
if (bignum_header_is_neg(*big))
- BIF_ERROR(BIF_P, BADARG);
+ goto badarg;
path_length = BIG_ARITY(big) - 1;
curr_path = BIG_DIGIT(big, 0);
path_rest = BIG_V(big) + 1;
@@ -3160,42 +3163,45 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
BIF_ERROR(BIF_P, BADARG);
}
- /* First we look for the K and V to return using the
+ if (type == iterator) {
+ /* iterator uses the format {K, V, {K, V, {K, V, [Path | Map]}}},
+ * so each element is 4 words large */
+ hp = HAlloc(BIF_P, 4 * NUM_ELEMS_TO_RETURN(BIF_P, map));
+ res = am_none;
+ } else {
+ /* list used the format [Path, Map, {K,V}, {K,V} | BIF_ARG_3],
+ * so each element is 2+3 words large */
+ hp = HAlloc(BIF_P, (2 + 3) * NUM_ELEMS_TO_RETURN(BIF_P, map));
+ res = BIF_ARG_3;
+ }
+
+ /* First we look for the leaf to start at using the
path given. While doing so, we push each map node
- and the index onto the stack so use later when
- building the next index. */
+ and the index onto the stack to use later. */
for (i = 1; ; i++) {
Eterm *ptr = hashmap_val(node),
- hdr = *ptr;
+ hdr = *ptr++;
Uint sz;
- ptr++;
-
- switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY:
- ptr++;
- sz = 16;
- break;
- case HAMT_SUBTAG_HEAD_BITMAP:
- ptr++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
- ASSERT(sz < 17);
- break;
- default:
- erts_exit(ERTS_ABORT_EXIT, "bad header");
- }
+ sz = hashmap_node_size(hdr, &ptr);
if (PATH_ELEM(curr_path) >= sz)
- BIF_ERROR(BIF_P, BADARG);
+ goto badarg;
- WSTACK_PUSH2(stack, node, PATH_ELEM(curr_path));
+ WSTACK_PUSH4(stack, node, PATH_ELEM(curr_path)+1, sz, (UWord)ptr);
- /* We have found a leaf, return it and calculate the path to next */
+ /* We have found a leaf, return it and the next X elements */
if (is_list(ptr[PATH_ELEM(curr_path)])) {
- lst = list_val(ptr[PATH_ELEM(curr_path)]);
- k = CAR(lst);
- v = CDR(lst);
+ Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]);
+ if (type == iterator) {
+ res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4;
+ /* Note where we should patch the Iterator is needed */
+ path_ptr = hp-1;
+ } else {
+ Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3;
+ res = CONS(hp, tup, res); hp += 2;
+ }
+ elems--;
break;
}
@@ -3217,48 +3223,70 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
}
}
- /* We pop the stack until we come to the next leaf to return */
- while (1) {
+ /* We traverse the hashmap and return at most `elems` elements */
+ while(1) {
+ Eterm *ptr = (Eterm*)WSTACK_POP(stack);
+ Uint sz = (Uint)WSTACK_POP(stack);
Uint idx = (Uint)WSTACK_POP(stack);
Eterm node = (Eterm)WSTACK_POP(stack);
- Eterm *ptr = hashmap_val(node),
- hdr = *ptr;
- Uint sz;
- ptr++;
-
- switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY:
- ptr++;
- sz = 16;
- break;
- case HAMT_SUBTAG_HEAD_BITMAP:
- ptr++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
- ASSERT(sz < 17);
- break;
- default:
- erts_exit(ERTS_ABORT_EXIT, "bad header");
- }
+ while (idx < sz && elems != 0 && is_list(ptr[idx])) {
+ Eterm *lst = list_val(ptr[idx]);
+ if (type == iterator) {
+ res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4;
+ } else {
+ Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3;
+ res = CONS(hp, tup, res); hp += 2;
+ }
+ elems--;
+ idx++;
+ }
- if (idx + 1 < sz) {
- curr_path = idx + 1;
+ if (elems == 0) {
+ if (idx < sz) {
+ /* There are more elements in this node to explore */
+ WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr);
+ } else {
+ /* pop stack to find the next value */
+ while (!WSTACK_ISEMPTY(stack)) {
+ Eterm *ptr = (Eterm*)WSTACK_POP(stack);
+ Uint sz = (Uint)WSTACK_POP(stack);
+ Uint idx = (Uint)WSTACK_POP(stack);
+ Eterm node = (Eterm)WSTACK_POP(stack);
+ if (idx < sz) {
+ WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr);
+ break;
+ }
+ }
+ }
break;
+ } else {
+ if (idx < sz) {
+ Eterm hdr;
+ /* Push next idx in current node */
+ WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr);
+
+ /* Push first idx in child node */
+ node = ptr[idx];
+ ptr = hashmap_val(ptr[idx]);
+ hdr = *ptr++;
+ sz = hashmap_node_size(hdr, &ptr);
+ WSTACK_PUSH4(stack, node, 0, sz, (UWord)ptr);
+ }
}
- /* We have reached the end of the iteration */
+ /* There are no more element in the hashmap */
if (WSTACK_ISEMPTY(stack)) {
- path = am_none;
break;
}
}
- if (path != am_none) {
- Uint depth = WSTACK_COUNT(stack) / 2 + 1;
+ if (!WSTACK_ISEMPTY(stack)) {
+ Uint depth = WSTACK_COUNT(stack) / 4 + 1;
/* +1 because we already have the first element in curr_path */
Eterm *path_digits = NULL;
+ Uint curr_path = 0;
/* If the path cannot fit in a small, we allocate a bignum */
if (depth >= PATH_ELEMS_PER_DIGIT) {
@@ -3269,13 +3297,21 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
path_digits = hp + big_size - 1;
}
+
/* Pop the stack to create the complete path to the next leaf */
while(!WSTACK_ISEMPTY(stack)) {
- Uint idx = (Uint)WSTACK_POP(stack);
+ Uint idx;
+
+ (void)WSTACK_POP(stack);
+ (void)WSTACK_POP(stack);
+ idx = (Uint)WSTACK_POP(stack)-1;
+ /* idx - 1 because idx in the stack is pointing to
+ the next element to fetch. */
(void)WSTACK_POP(stack);
depth--;
if (depth % PATH_ELEMS_PER_DIGIT == 0) {
+ /* Switch to next bignum element */
path_digits[0] = curr_path;
path_digits--;
curr_path = 0;
@@ -3292,15 +3328,36 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
/* The Uint could be too large for a small */
path = erts_make_integer(curr_path, BIF_P);
}
+
+ if (type == iterator) {
+ hp = HAlloc(BIF_P, 2);
+ *path_ptr = CONS(hp, path, map); hp += 2;
+ } else {
+ hp = HAlloc(BIF_P, 4);
+ res = CONS(hp, map, res); hp += 2;
+ res = CONS(hp, path, res); hp += 2;
+ }
+ } else {
+ if (type == iterator) {
+ HRelease(BIF_P, hp + 4 * elems, hp);
+ } else {
+ HRelease(BIF_P, hp + (2+3) * elems, hp);
+ }
}
+ BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems);
+ DESTROY_WSTACK(stack);
+ BIF_RET(res);
+ badarg:
+ if (type == iterator) {
+ HRelease(BIF_P, hp + 4 * elems, hp);
+ } else {
+ HRelease(BIF_P, hp + (2+3) * elems, hp);
+ }
+ BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems);
DESTROY_WSTACK(stack);
+ BIF_ERROR(BIF_P, BADARG);
}
-
- hp = HAlloc(BIF_P, 4 + 3 /* 3-tuple + 2-tuple */);
- iter = TUPLE2(hp, path, map);
- hp += 3;
- BIF_RET(TUPLE3(hp, k, v, iter));
}
/* implementation of builtin emulations */
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 3cf071b590..1e70d31b16 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -2366,41 +2366,6 @@ t_bif_map_from_list(Config) when is_list(Config) ->
{'EXIT', {badarg,_}} = (catch maps:from_list(id(42))),
ok.
-t_bif_erts_internal_maps_to_list(Config) when is_list(Config) ->
- %% small maps
- [] = erts_internal:maps_to_list(#{},-1),
- [] = erts_internal:maps_to_list(#{},-2),
- [] = erts_internal:maps_to_list(#{},10),
- [{a,1},{b,2}] = lists:sort(erts_internal:maps_to_list(#{a=>1,b=>2}, 2)),
- [{a,1},{b,2}] = lists:sort(erts_internal:maps_to_list(#{a=>1,b=>2}, -1)),
- [{_,_}] = erts_internal:maps_to_list(#{a=>1,b=>2}, 1),
- [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},-2)),
- [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},3)),
- [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},5)),
- [{_,_},{_,_}] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},2),
- [{_,_}] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},1),
- [] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},0),
-
- %% big maps
- M = maps:from_list([{I,ok}||I <- lists:seq(1,500)]),
- [] = erts_internal:maps_to_list(M,0),
- [{_,_}] = erts_internal:maps_to_list(M,1),
- [{_,_},{_,_}] = erts_internal:maps_to_list(M,2),
- Ls1 = erts_internal:maps_to_list(M,10),
- 10 = length(Ls1),
- Ls2 = erts_internal:maps_to_list(M,20),
- 20 = length(Ls2),
- Ls3 = erts_internal:maps_to_list(M,120),
- 120 = length(Ls3),
- Ls4 = erts_internal:maps_to_list(M,-1),
- 500 = length(Ls4),
-
- %% error cases
- {'EXIT', {{badmap,[{a,b},b]},_}} = (catch erts_internal:maps_to_list(id([{a,b},b]),id(1))),
- {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{}),id(a))),
- {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{1=>2}),id(<<>>))),
- ok.
-
t_bif_map_next(Config) when is_list(Config) ->
erts_debug:set_internal_state(available_internal_state, true),
@@ -2420,9 +2385,25 @@ t_bif_map_next(Config) when is_list(Config) ->
{'EXIT', {badarg,_}} = (catch maps:next(id(a))),
{'EXIT', {badarg,_}} = (catch maps:next(id([a|FM]))),
{'EXIT', {badarg,_}} = (catch maps:next(id([1|#{}]))),
- {'EXIT', {badarg,_}} = (catch maps:next(id([16#FFFFFFF|FM]))),
- {'EXIT', {badarg,_}} = (catch maps:next(id([16#F0F0F0F|FM]))),
- {'EXIT', {badarg,_}} = (catch maps:next(id([16#1234567890ABCDEF|FM]))),
+ {'EXIT', {badarg,_}} = (catch maps:next(id([-1|#{}]))),
+ {'EXIT', {badarg,_}} = (catch maps:next(id([-1|FM]))),
+ {'EXIT', {badarg,_}} = (catch maps:next(id([16#FFFFFFFFFFFFFFFF|FM]))),
+ {'EXIT', {badarg,_}} = (catch maps:next(id([-16#FFFFFFFFFFFFFFFF|FM]))),
+
+ %% This us a whitebox test that the error code works correctly.
+ %% It uses a path for a tree of depth 4 and tries to do next on
+ %% each of those paths.
+ (fun F(0) -> ok;
+ F(N) ->
+ try maps:next([N|FM]) of
+ none ->
+ F(N-1);
+ {_K,_V,_I} ->
+ F(N-1)
+ catch error:badarg ->
+ F(N-1)
+ end
+ end)(16#FFFF),
ok
after
diff --git a/erts/preloaded/ebin/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam
index 015508d326..3257c68897 100644
--- a/erts/preloaded/ebin/erts_internal.beam
+++ b/erts/preloaded/ebin/erts_internal.beam
Binary files differ
diff --git a/erts/preloaded/src/erts_internal.erl b/erts/preloaded/src/erts_internal.erl
index 46bdeaad30..efff76f1fa 100644
--- a/erts/preloaded/src/erts_internal.erl
+++ b/erts/preloaded/src/erts_internal.erl
@@ -32,7 +32,7 @@
-export([await_port_send_result/3]).
-export([cmp_term/2]).
-export([map_to_tuple_keys/1, term_type/1, map_hashmap_children/1,
- maps_to_list/2, map_next/2]).
+ maps_to_list/2, map_next/3]).
-export([open_port/2, port_command/3, port_connect/2, port_close/1,
port_control/3, port_call/3, port_info/1, port_info/2]).
@@ -367,11 +367,6 @@ term_type(_T) ->
map_hashmap_children(_M) ->
erlang:nif_error(undefined).
--spec erts_internal:flush_monitor_messages(Ref, Multi, Res) -> term() when
- Ref :: reference(),
- Multi :: boolean(),
- Res :: term().
-
%% return a list of key value pairs, at most of length N
-spec maps_to_list(M,N) -> Pairs when
M :: map(),
@@ -382,16 +377,22 @@ maps_to_list(_M, _N) ->
erlang:nif_error(undefined).
%% return the next assoc in the iterator and a new iterator
--spec map_next(I, M) -> {K,V,NI} when
+-spec map_next(I, M, A) -> {K,V,NI} | list() when
I :: non_neg_integer(),
M :: map(),
K :: term(),
V :: term(),
+ A :: iterator | list(),
NI :: maps:iterator().
-map_next(_I, _M) ->
+map_next(_I, _M, _A) ->
erlang:nif_error(undefined).
+-spec erts_internal:flush_monitor_messages(Ref, Multi, Res) -> term() when
+ Ref :: reference(),
+ Multi :: boolean(),
+ Res :: term().
+
%% erlang:demonitor(Ref, [flush]) traps to
%% erts_internal:flush_monitor_messages(Ref, Res) when
%% it needs to flush monitor messages.
diff --git a/lib/hipe/cerl/erl_bif_types.erl b/lib/hipe/cerl/erl_bif_types.erl
index a3a936322a..462a1f9dcd 100644
--- a/lib/hipe/cerl/erl_bif_types.erl
+++ b/lib/hipe/cerl/erl_bif_types.erl
@@ -1701,24 +1701,6 @@ type(maps, size, 1, Xs, Opaques) ->
t_from_range(LowerBound, UpperBound)
end
end, Opaques);
-type(maps, to_list, 1, Xs, Opaques) ->
- strict(maps, to_list, 1, Xs,
- fun ([Map]) ->
- DefK = t_map_def_key(Map, Opaques),
- DefV = t_map_def_val(Map, Opaques),
- Pairs = t_map_entries(Map, Opaques),
- EType = lists:foldl(
- fun({K,_,V},EType0) ->
- case t_is_none(V) of
- true -> t_subtract(EType0, t_tuple([K,t_any()]));
- false -> t_sup(EType0, t_tuple([K,V]))
- end
- end, t_tuple([DefK, DefV]), Pairs),
- case t_is_none(EType) of
- true -> t_nil();
- false -> t_list(EType)
- end
- end, Opaques);
type(maps, update, 3, Xs, Opaques) ->
strict(maps, update, 3, Xs,
fun ([Key, Value, Map]) ->
@@ -2648,8 +2630,6 @@ arg_types(maps, put, 3) ->
[t_any(), t_any(), t_map()];
arg_types(maps, size, 1) ->
[t_map()];
-arg_types(maps, to_list, 1) ->
- [t_map()];
arg_types(maps, update, 3) ->
[t_any(), t_any(), t_map()];
arg_types(M, F, A) when is_atom(M), is_atom(F),
diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index a3afbf8e7f..987d92989d 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -38,8 +38,7 @@
<name name="iterator"/>
<desc>
<p>An iterator representing the key value associations in a map.</p>
- <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>
- and <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>.</p>
+ <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>.</p>
<p>Consumed by <seealso marker="#next-1"><c>maps:next/1</c></seealso>,
<seealso marker="#filter-2"><c>maps:filter/2</c></seealso>,
<seealso marker="#fold-3"><c>maps:fold/3</c></seealso> and
@@ -194,9 +193,9 @@ false</code>
<desc>
<p>Returns a map iterator <c><anno>Iterator</anno></c> that can
be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
- to traverse the keys and values in a map. This call is equivalent
- to calling <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>
- with an empty map as the options.</p>
+ to traverse the key-value associations in a map. When iterating
+ over a map, the memory usage is guaranteed to be bounded no matter
+ the size of the map.</p>
<p>The call fails with a <c>{badmap,Map}</c> exception if
<c><anno>Map</anno></c> is not a map.</p>
<p><em>Example:</em></p>
@@ -215,49 +214,6 @@ none</code>
</func>
<func>
- <name name="iterator" arity="2"/>
- <fsummary>Create a map iterator.</fsummary>
- <desc>
- <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
- be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
- to traverse the keys and values in a map. The iterator will behave
- according to the given <c><anno>Opts</anno></c>.</p>
- <taglist>
- <tag>optimize</tag>
- <item>
- Configures whether the iterator should be optimized for <c>speed</c>
- or for <c>memory</c> consumption. Default is <c>speed</c>.
- </item>
- <tag>ordered</tag>
- <item>
- Configures whether the iterator should return the key value
- associations ordered on the keys according to erlang term order
- or not. The default is <c>false</c>.
- </item>
- </taglist>
- <p>Both options can be configured at the same time.</p>
- <p>The call fails with a <c>{badmap,Map}</c> exception if
- <c><anno>Map</anno></c> is not a map.</p>
- <p><em>Example:</em></p>
- <code type="none">
-> M = maps:from_list([{I,I} || I &lt;- lists:seq(1,50)]).
-#{45 => 45,6 => 6,2 => 2,49 => 49,41 => 41,33 => 33,42 => 42,
- 43 => 43,10 => 10,9 => 9,19 => 19,14 => 14,5 => 5,18 => 18,
- 31 => 31,22 => 22,29 => 29,21 => 21,27 => 27,24 => 24,
- 47 => 47,40 => 40,30 => 30,23 => 23,28 => 28,46 => 46,
- 16 => 16,38 => 38,4 => 4,...}
-> MemoryIter = maps:iterator(M, #{ optimize => memory }), ok.
-ok
-> {K1, V1, _} = maps:next(MemoryIter), {K1, V1}.
-{46,46}
-> OrderedIter = maps:iterator(M, #{ ordered => true, optimize => memory }), ok.
-ok
-> {K2, V2, _} = maps:next(OrderedIter), {K2, V2}.
-{1,1}</code>
- </desc>
- </func>
-
- <func>
<name name="keys" arity="1"/>
<fsummary></fsummary>
<desc>
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 2f2dd41979..a13f340709 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -24,7 +24,7 @@
map/2, size/1,
update_with/3, update_with/4,
without/2, with/2,
- iterator/1, iterator/2, next/1]).
+ iterator/1, next/1]).
%% BIFs
-export([get/2, find/2, from_list/1,
@@ -32,12 +32,14 @@
new/0, put/3, remove/2, take/2,
to_list/1, update/3, values/1]).
--opaque iterator() :: {non_neg_integer() | none | list(term()), map()}
- | list({term(), term()}).
+-opaque iterator() :: {term(), term(), iterator()}
+ | none | nonempty_improper_list(integer(),map()).
-export_type([iterator/0]).
--define(IS_ITERATOR(I), (is_list(I) orelse (is_map(element(2,I) andalso (is_list(element(1,I) orelse is_integer(element(1,I)))))))).
+-dialyzer({no_improper_lists, iterator/1}).
+
+-define(IS_ITERATOR(I), is_tuple(I) andalso tuple_size(I) == 3; I == none; is_integer(hd(I)) andalso is_map(tl(I))).
%% Shadowed by erl_bif_types: maps:get/2
-spec get(Key,Map) -> Value when
@@ -121,14 +123,20 @@ remove(_,_) -> erlang:nif_error(undef).
take(_,_) -> erlang:nif_error(undef).
-%% Shadowed by erl_bif_types: maps:to_list/1
-spec to_list(Map) -> [{Key,Value}] when
Map :: map(),
Key :: term(),
Value :: term().
-to_list(_) -> erlang:nif_error(undef).
+to_list(Map) when is_map(Map) ->
+ to_list_internal(erts_internal:map_next(0, Map, []));
+to_list(Map) ->
+ erlang:error({badmap,Map},[Map]).
+to_list_internal([Iter, Map | Acc]) when is_integer(Iter) ->
+ to_list_internal(erts_internal:map_next(Iter, Map, Acc));
+to_list_internal(Acc) ->
+ Acc.
%% Shadowed by erl_bif_types: maps:update/3
-spec update(Key,Value,Map1) -> Map2 when
@@ -207,7 +215,7 @@ get(Key,Map,Default) ->
Map :: map().
filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
- maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+ maps:from_list(filter_1(Pred, iterator(Map)));
filter(Pred,Iterator) when is_function(Pred,2), ?IS_ITERATOR(Iterator) ->
maps:from_list(filter_1(Pred, Iterator));
filter(Pred,Map) ->
@@ -237,7 +245,7 @@ filter_1(Pred, Iter) ->
V :: term().
fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
- lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+ fold_1(Fun,Init,iterator(Map));
fold(Fun,Init,Iterator) when is_function(Fun,3), ?IS_ITERATOR(Iterator) ->
fold_1(Fun,Init,Iterator);
fold(Fun,Init,Map) ->
@@ -260,7 +268,7 @@ fold_1(Fun, Acc, Iter) ->
V2 :: term().
map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
- maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+ maps:from_list(map_1(Fun, iterator(Map)));
map(Fun,Iterator) when is_function(Fun, 2), ?IS_ITERATOR(Iterator) ->
maps:from_list(map_1(Fun, Iterator));
map(Fun,Map) ->
@@ -286,42 +294,19 @@ size(Val) ->
Map :: map(),
Iterator :: iterator().
-iterator(M) when is_map(M) -> iterator(M, #{});
+iterator(M) when is_map(M) -> [0 | M];
iterator(M) -> erlang:error({badmap, M}, [M]).
--spec iterator(Map, Opts) -> Iterator when
- Map :: map(),
- Opts :: #{ ordered => boolean(), optimize => speed | memory },
- Iterator :: iterator().
-iterator(M, Opts) when is_map(M), is_map(Opts) ->
- case maps:merge(default_iterator_opts(), Opts) of
- #{ ordered := true, optimize := speed} -> lists:sort(maps:to_list(M));
- #{ ordered := false, optimize := speed} -> maps:to_list(M);
- #{ ordered := true, optimize := memory} -> {lists:sort(maps:keys(M)), M};
- #{ ordered := false, optimize := memory} -> {0, M}
- end;
-iterator(M, Opts) when is_map(M) ->
- erlang:error({badmap, M}, [M, Opts]);
-iterator(M, Opts) ->
- erlang:error(error_type(M), [M, Opts]).
-
-default_iterator_opts() ->
- #{ ordered => false, optimize => speed }.
-
-spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when
Iterator :: iterator(),
Key :: term(),
Value :: term(),
NextIterator :: iterator().
-next([{K, V} | T]) ->
- {K, V, T};
-next([]) ->
- none;
-next({I, M}) when is_map(M), is_integer(I) orelse is_atom(I) ->
- erts_internal:map_next(I, M);
-next({[K | T], M}) when is_map(M) ->
- {K, maps:get(K, M), {T, M}};
-next({[], M}) when is_map(M) ->
+next({K, V, I}) ->
+ {K, V, I};
+next([Path | Map]) when is_integer(Path), is_map(Map) ->
+ erts_internal:map_next(Path, Map, iterator);
+next(none) ->
none;
next(Iter) ->
erlang:error(badarg, [Iter]).
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 0021dd0657..a75751b31d 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,7 +30,7 @@
-export([t_update_with_3/1, t_update_with_4/1,
t_get_3/1, t_filter_2/1,
t_fold_3/1,t_map_2/1,t_size_1/1,
- t_iterator_1/1, t_iterator_2/1,
+ t_iterator_1/1,
t_with_2/1,t_without_2/1]).
%%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -48,7 +48,7 @@ all() ->
[t_update_with_3,t_update_with_4,
t_get_3,t_filter_2,
t_fold_3,t_map_2,t_size_1,
- t_iterator_1, t_iterator_2,
+ t_iterator_1,
t_with_2,t_without_2].
t_update_with_3(Config) when is_list(Config) ->
@@ -179,40 +179,19 @@ t_iterator_1(Config) when is_list(Config) ->
%% Large map test
- Vs = lists:seq(1,200),
- M2 = maps:from_list([{{k,I},I}||I<-Vs]),
+ Vs2 = lists:seq(1,200),
+ M2 = maps:from_list([{{k,I},I}||I<-Vs2]),
KVList2 = lists:sort(iter_kv(maps:iterator(M2))),
KVList2 = lists:sort(maps:to_list(M2)),
- ok.
-t_iterator_2(Config) when is_list(Config) ->
-
- Vs = lists:seq(1,200),
- Maps = [#{ a => 1, b => 2 }, maps:from_list([{{k,I},I}||I<-Vs])],
- Optimize = [speed, memory],
- Ordered = [true, false],
-
- [test_iterator(Map, Opt, Ord) || Map <- Maps,
- Opt <- Optimize,
- Ord <- Ordered],
+ %% Larger map test
+ Vs3 = lists:seq(1,10000),
+ M3 = maps:from_list([{{k,I},I}||I<-Vs3]),
+ KVList3 = lists:sort(iter_kv(maps:iterator(M3))),
+ KVList3 = lists:sort(maps:to_list(M3)),
ok.
-test_iterator(Map, Opt, Ord) ->
- Opts = #{ optimize => Opt, ordered => Ord },
- test_iterator_1(maps:iterator(Map, Opts), Map, Opts).
-
-test_iterator_1(Iter, OrigMap, Opts) ->
- erlang:display(Opts),
- KVs = iter_kv(Iter),
- case Opts of
- #{ ordered := true } ->
- KVs = lists:sort(maps:to_list(OrigMap));
- #{ ordered := false } ->
- OrderedKVs = lists:sort(KVs),
- OrderedKVs = lists:sort(maps:to_list(OrigMap))
- end.
-
iter_kv(I) ->
case maps:next(I) of
none ->
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 13:53:50 +0000