diff options
| -rw-r--r-- | erts/emulator/beam/bif.tab | 11 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.c | 565 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.h | 6 |
3 files changed, 547 insertions, 35 deletions
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 8f85f931c9..306861a4c5 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -572,7 +572,6 @@ bif erlang:binary_to_float/1 bif io:printable_range/0 bif os:unsetenv/1 - # # New in R17A # @@ -582,9 +581,17 @@ bif re:inspect/2 ubif erlang:is_map/1 ubif erlang:map_size/1 bif map:to_list/1 -bif map:new/0 +bif map:find/2 bif map:get/2 +bif map:from_list/1 +bif map:is_key/2 +bif map:keys/1 +bif map:merge/2 +bif map:new/0 bif map:put/3 +bif map:remove/2 +bif map:update/3 +bif map:values/1 # # Obsolete diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 6a59fa29b8..6fd60f0689 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -32,6 +32,57 @@ #include "erl_map.h" +/* BIFs + * + * DONE: + * - erlang:is_map/1 + * - erlang:map_size/1 + * + * - map:find/2 + * - map:from_list/1 + * - map:get/2 + * - map:is_key/2 + * - map:keys/1 + * - map:merge/2 + * - map:new/0 + * - map:put/3 + * - map:remove/2 + * - map:to_list/1 + * - map:update/3 + * - map:values/1 + * + * TODO: + * - map:foldl/3 + * - map:foldr/3 + * - map:map/3 + * - map:size/1 + * - map:without/2 + * + */ + +/* erlang:map_size/1 + * the corresponding instruction is implemented in: + * beam/erl_bif_guard.c + */ + +BIF_RETTYPE map_size_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Eterm *hp; + Uint hsz = 0; + map_t *mp = (map_t*)map_val(BIF_ARG_1); + Uint n = map_get_size(mp); + + erts_bld_uint(NULL, &hsz, n); + hp = HAlloc(BIF_P, hsz); + BIF_RET(erts_bld_uint(&hp, NULL, n)); + } + + BIF_ERROR(BIF_P, BADARG); +} + +/* map:to_list/1 + */ + BIF_RETTYPE map_to_list_1(BIF_ALIST_1) { if (is_map(BIF_ARG_1)) { Uint n; @@ -56,43 +107,40 @@ BIF_RETTYPE map_to_list_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADARG); } - -/* erlang:map_size/1 - * the corresponding instruction is implemented in: - * beam/erl_bif_guard.c +/* map:find/2 + * return value if key *equals* a key in the map */ -BIF_RETTYPE map_size_1(BIF_ALIST_1) { - if (is_map(BIF_ARG_1)) { - Eterm *hp; - Uint hsz = 0; - map_t *mp = (map_t*)map_val(BIF_ARG_1); - Uint n = map_get_size(mp); +BIF_RETTYPE map_find_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm *hp, *ks,*vs, key, res; + map_t *mp; + Uint n,i; - erts_bld_uint(NULL, &hsz, n); - hp = HAlloc(BIF_P, hsz); - BIF_RET(erts_bld_uint(&hp, NULL, n)); - } + mp = (map_t*)map_val(BIF_ARG_2); + key = BIF_ARG_1; + n = map_get_size(mp); + ks = map_get_keys(mp); + vs = map_get_values(mp); + for( i = 0; i < n; i++) { + if (CMP(ks[i], key)==0) { + hp = HAlloc(BIF_P, 3); + res = make_tuple(hp); + *hp++ = make_arityval(2); + *hp++ = am_ok; + *hp++ = vs[i]; + BIF_RET(res); + } + } + BIF_RET(am_error); + } BIF_ERROR(BIF_P, BADARG); } - -BIF_RETTYPE map_new_0(BIF_ALIST_0) { - Eterm* hp; - Eterm tup; - map_t *mp; - - hp = HAlloc(BIF_P, (3 + 1)); - tup = make_tuple(hp); - *hp++ = make_arityval(0); - - mp = (map_t*)hp; - mp->thing_word = MAP_HEADER; - mp->size = 0; - mp->keys = tup; - - BIF_RET(make_map(mp)); -} +/* map:get/2 + * return value if key *matches* a key in the map + * exception bad_key if none matches + */ BIF_RETTYPE map_get_2(BIF_ALIST_2) { if (is_map(BIF_ARG_2)) { @@ -136,6 +184,297 @@ error: BIF_ERROR(BIF_P, BADARG); } +/* map:from_list/1 + * List may be unsorted [{K,V}] + */ + +BIF_RETTYPE map_from_list_1(BIF_ALIST_1) { + Eterm *kv, item = BIF_ARG_1; + Eterm *hp, *thp,*vs, *ks, keys, res; + map_t *mp; + Uint size = 0, unused_size = 0; + Sint c = 0; + Sint idx = 0; + + if (is_list(item) || is_nil(item)) { + + /* Calculate size and check validity */ + + while(is_list(item)) { + res = CAR(list_val(item)); + if (is_not_tuple(res)) + goto error; + + kv = tuple_val(res); + if (*kv != make_arityval(2)) + goto error; + + size++; + item = CDR(list_val(item)); + } + + if (is_not_nil(item)) + goto error; + + hp = HAlloc(BIF_P, 3 + 1 + (2 * size)); + thp = hp; + keys = make_tuple(hp); + *hp++ = make_arityval(size); + ks = hp; + hp += size; + mp = (map_t*)hp; + res = make_map(mp); + hp += MAP_HEADER_SIZE; + vs = hp; + + mp->thing_word = MAP_HEADER; + mp->size = size; /* set later, might shrink*/ + mp->keys = keys; + + if (size == 0) + BIF_RET(res); + + item = BIF_ARG_1; + + /* first entry */ + kv = tuple_val(CAR(list_val(item))); + ks[0] = kv[1]; + vs[0] = kv[2]; + size = 1; + item = CDR(list_val(item)); + + /* insert sort key/value pairs */ + while(is_list(item)) { + + kv = tuple_val(CAR(list_val(item))); + + /* compare ks backwards + * idx represent word index to be written (hole position). + * We cannot copy the elements when searching since we might + * have an equal key. So we search for just the index first =( + * + * It is perhaps faster to move the values in the first pass. + * Check for uniqueness during insert phase and then have a + * second phace compacting the map if duplicates are found + * during insert. .. or do someother sort .. shell-sort perhaps. + */ + + idx = size; + + while(idx > 0 && (c = CMP(kv[1],ks[idx-1])) < 0) { idx--; } + + if (c == 0) { + /* last compare was equal, + * i.e. we have to release memory + * and overwrite that key/value + */ + ks[idx-1] = kv[1]; + vs[idx-1] = kv[2]; + unused_size++; + } else { + Uint i = size; + while(i > idx) { + ks[i] = ks[i-1]; + vs[i] = vs[i-1]; + i--; + } + ks[idx] = kv[1]; + vs[idx] = kv[2]; + size++; + } + item = CDR(list_val(item)); + } + + 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 */ + + ks[size] = make_pos_bignum_header(unused_size - 1); + HRelease(BIF_P, vs + size + unused_size, vs + size); + } + + *thp = make_arityval(size); + mp->size = size; + BIF_RET(res); + } + +error: + + BIF_ERROR(BIF_P, BADARG); +} + +/* map:is_key/2 + */ + +BIF_RETTYPE map_is_key_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm *ks, key; + map_t *mp; + Uint n,i; + + mp = (map_t*)map_val(BIF_ARG_2); + key = BIF_ARG_1; + n = map_get_size(mp); + ks = map_get_keys(mp); + + if (n == 0) + BIF_RET(am_false); + + if (is_immed(key)) { + for( i = 0; i < n; i++) { + if (ks[i] == key) { + BIF_RET(am_true); + } + } + } + + for( i = 0; i < n; i++) { + if (eq(ks[i], key)) { + BIF_RET(am_true); + } + } + BIF_RET(am_false); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* map:keys/1 + */ + +BIF_RETTYPE map_keys_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Eterm *hp, *ks, res = NIL; + map_t *mp; + Uint n; + + mp = (map_t*)map_val(BIF_ARG_1); + n = map_get_size(mp); + + if (n == 0) + BIF_RET(res); + + hp = HAlloc(BIF_P, (2 * n)); + ks = map_get_keys(mp); + + while(n--) { + res = CONS(hp, ks[n], res); hp += 2; + } + + BIF_RET(res); + } + BIF_ERROR(BIF_P, BADARG); +} +/* map:merge/2 + */ + +BIF_RETTYPE map_merge_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_1) && is_map(BIF_ARG_2)) { + Eterm *hp,*thp; + Eterm tup; + Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2; + map_t *mp1,*mp2,*mp_new; + Uint n1,n2,i1,i2,need,unused_size=0; + int c = 0; + + mp1 = (map_t*)map_val(BIF_ARG_1); + mp2 = (map_t*)map_val(BIF_ARG_2); + n1 = map_get_size(mp1); + n2 = map_get_size(mp2); + + need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2); + + hp = HAlloc(BIF_P, need); + thp = hp; + tup = make_tuple(thp); + ks = hp + 1; hp += 1 + n1 + n2; + mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE; + vs = hp; hp += n1 + n2; + + mp_new->thing_word = MAP_HEADER; + mp_new->size = 0; + mp_new->keys = tup; + + i1 = 0; i2 = 0; + ks1 = map_get_keys(mp1); + vs1 = map_get_values(mp1); + ks2 = map_get_keys(mp2); + vs2 = map_get_values(mp2); + + while(i1 < n1 && i2 < n2) { + c = CMP(ks1[i1],ks2[i2]); + if ( c == 0) { + /* use righthand side arguments map value, + * but advance both maps */ + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i1++, i2++, unused_size++; + } else if ( c < 0) { + *ks++ = ks1[i1]; + *vs++ = vs1[i1]; + i1++; + } else { + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i2++; + } + } + + /* copy remaining */ + while (i1 < n1) { + *ks++ = ks1[i1]; + *vs++ = vs1[i1]; + i1++; + } + + while (i2 < n2) { + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + 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(BIF_P, vs + unused_size, vs); + } + + mp_new->size = n1 + n2 - unused_size; + *thp = make_arityval(n1 + n2 - unused_size); + + BIF_RET(make_map(mp_new)); + } + BIF_ERROR(BIF_P, BADARG); +} +/* map:new/2 + */ + +BIF_RETTYPE map_new_0(BIF_ALIST_0) { + Eterm* hp; + Eterm tup; + map_t *mp; + + hp = HAlloc(BIF_P, (3 + 1)); + tup = make_tuple(hp); + *hp++ = make_arityval(0); + + mp = (map_t*)hp; + mp->thing_word = MAP_HEADER; + mp->size = 0; + mp->keys = tup; + + BIF_RET(make_map(mp)); +} + +/* map:put/3 + */ + BIF_RETTYPE map_put_3(BIF_ALIST_3) { if (is_map(BIF_ARG_3)) { Sint n,i; @@ -242,3 +581,167 @@ BIF_RETTYPE map_put_3(BIF_ALIST_3) { BIF_ERROR(BIF_P, BADARG); } + +/* map:remove/3 + */ + +BIF_RETTYPE map_remove_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Sint n; + Sint found = 0; + Uint need; + Eterm *thp, *mhp; + Eterm *ks, *vs, res, key,tup; + map_t *mp = (map_t*)map_val(BIF_ARG_2); + + key = BIF_ARG_1; + n = map_get_size(mp); + + if (n == 0) + BIF_RET(BIF_ARG_2); + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* Assume key exists. + * Release allocated if it didn't. + * Allocate key tuple first. + */ + + need = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */ + thp = HAlloc(BIF_P, need); + mhp = thp + n; /* offset with tuple heap size */ + + tup = make_tuple(thp); + *thp++ = make_arityval(n - 1); + + res = make_map(mhp); + *mhp++ = MAP_HEADER; + *mhp++ = n - 1; + *mhp++ = tup; + + if (is_immed(key)) { + while(n--) { + if (*ks == key) { + ks++; + vs++; + found = 1; + } else { + *mhp++ = *vs++; + *thp++ = *ks++; + } + } + } else { + while(n--) { + if (eq(*ks, key)) { + ks++; + vs++; + found = 1; + } else { + *mhp++ = *vs++; + *thp++ = *ks++; + } + } + } + + if (found) + BIF_RET(res); + + /* Not found, remove allocated memory + * and return previous map. + */ + HRelease(BIF_P, thp + need, thp); + BIF_RET(BIF_ARG_2); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* map:update/3 + */ + +BIF_RETTYPE map_update_3(BIF_ALIST_3) { + if (is_map(BIF_ARG_3)) { + Sint n,i; + Sint found = 0; + Eterm* hp,*shp; + Eterm *ks,*vs, res, key; + map_t *mp = (map_t*)map_val(BIF_ARG_3); + + key = BIF_ARG_1; + n = map_get_size(mp); + + if (n == 0) { + BIF_ERROR(BIF_P, BADARG); + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* only allocate for values, + * assume key-tuple will be intact + */ + + hp = HAlloc(BIF_P, 3 + n); + shp = hp; + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = n; + *hp++ = mp->keys; + + if (is_immed(key)) { + for( i = 0; i < n; i ++) { + if (ks[i] == key) { + *hp++ = BIF_ARG_2; + vs++; + found = 1; + } else { + *hp++ = *vs++; + } + } + } else { + for( i = 0; i < n; i ++) { + if (eq(ks[i], key)) { + *hp++ = BIF_ARG_2; + vs++; + found = 1; + } else { + *hp++ = *vs++; + } + } + } + + if (found) + BIF_RET(res); + + HRelease(BIF_P, shp + 3 + n, shp); + } + BIF_ERROR(BIF_P, BADARG); +} + + +/* map:values/1 + */ + +BIF_RETTYPE map_values_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Eterm *hp, *vs, res = NIL; + map_t *mp; + Uint n; + + mp = (map_t*)map_val(BIF_ARG_1); + n = map_get_size(mp); + + if (n == 0) + BIF_RET(res); + + hp = HAlloc(BIF_P, (2 * n)); + vs = map_get_values(mp); + + while(n--) { + res = CONS(hp, vs[n], res); hp += 2; + } + + BIF_RET(res); + } + BIF_ERROR(BIF_P, BADARG); +} diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index ca8ce0f974..4f0d26e100 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -33,11 +33,12 @@ typedef struct map_s { * * ----------- * Eterm THING - * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = arity + * Uint size + * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = size * ---- * Eterm V1 * ... - * Eterm Vn, where n = arity + * Eterm Vn, where n = size * ----------- */ @@ -59,6 +60,7 @@ typedef struct map_s { #define map_get_size(x) (((map_t*)(x))->size) #define MAP_HEADER _make_header(1,_TAG_HEADER_MAP) +#define MAP_HEADER_SIZE (sizeof(map_t) / sizeof(Eterm)) #endif |