diff options
Diffstat (limited to 'erts')
| -rw-r--r-- | erts/emulator/Makefile.in | 3 | ||||
| -rw-r--r-- | erts/emulator/beam/copy.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_bif_guard.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_gc.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 85 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_hashmap.h | 96 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.c | 4 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.h | 67 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_printf_term.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/external.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/utils.c | 1 | ||||
| -rw-r--r-- | erts/emulator/hipe/hipe_gc.c | 1 |
12 files changed, 71 insertions, 191 deletions
diff --git a/erts/emulator/Makefile.in b/erts/emulator/Makefile.in index db7eac4690..a632faf57d 100644 --- a/erts/emulator/Makefile.in +++ b/erts/emulator/Makefile.in @@ -785,8 +785,7 @@ RUN_OBJS = \ $(OBJDIR)/erl_zlib.o $(OBJDIR)/erl_nif.o \ $(OBJDIR)/erl_bif_binary.o $(OBJDIR)/erl_ao_firstfit_alloc.o \ $(OBJDIR)/erl_thr_queue.o $(OBJDIR)/erl_sched_spec_pre_alloc.o \ - $(OBJDIR)/erl_ptab.o $(OBJDIR)/erl_map.o \ - $(OBJDIR)/erl_hashmap.o + $(OBJDIR)/erl_ptab.o $(OBJDIR)/erl_map.o ifeq ($(TARGET),win32) DRV_OBJS = \ diff --git a/erts/emulator/beam/copy.c b/erts/emulator/beam/copy.c index 6294ba9412..5901c00d0a 100644 --- a/erts/emulator/beam/copy.c +++ b/erts/emulator/beam/copy.c @@ -33,7 +33,6 @@ #include "erl_binary.h" #include "erl_bits.h" #include "dtrace-wrapper.h" -#include "erl_hashmap.h" static void move_one_frag(Eterm** hpp, Eterm* src, Uint src_sz, ErlOffHeap*); diff --git a/erts/emulator/beam/erl_bif_guard.c b/erts/emulator/beam/erl_bif_guard.c index a5d1d3a5cb..bc0891422b 100644 --- a/erts/emulator/beam/erl_bif_guard.c +++ b/erts/emulator/beam/erl_bif_guard.c @@ -34,7 +34,6 @@ #include "big.h" #include "erl_binary.h" #include "erl_map.h" -#include "erl_hashmap.h" static Eterm gc_double_to_integer(Process* p, double x, Eterm* reg, Uint live); diff --git a/erts/emulator/beam/erl_gc.c b/erts/emulator/beam/erl_gc.c index bdf7aa362e..d1a7ee113b 100644 --- a/erts/emulator/beam/erl_gc.c +++ b/erts/emulator/beam/erl_gc.c @@ -31,7 +31,6 @@ #include "erl_binary.h" #include "erl_bits.h" #include "erl_map.h" -#include "erl_hashmap.h" #include "error.h" #include "big.h" #include "erl_gc.h" diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c deleted file mode 100644 index 0c146137f5..0000000000 --- a/erts/emulator/beam/erl_hashmap.c +++ /dev/null @@ -1,85 +0,0 @@ -/* - * %CopyrightBegin% - * - * Copyright Ericsson AB 2011. All Rights Reserved. - * - * The contents of this file are subject to the Erlang Public License, - * Version 1.1, (the "License"); you may not use this file except in - * compliance with the License. You should have received a copy of the - * Erlang Public License along with this software. If not, it can be - * retrieved online at http://www.erlang.org/. - * - * Software distributed under the License is distributed on an "AS IS" - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See - * the License for the specific language governing rights and limitations - * under the License. - * - * %CopyrightEnd% - * - * hashmaps are an adaption of Rich Hickeys Persistent HashMaps - * which were an adaption of Phil Bagwells - Hash Array Mapped Tries - * - * Author: Björn-Egil Dahlberg - */ -/* - * Ls = lists:seq(1,188888). - * A = lists:foldl(fun(I,O) -> hashmap:put(I,I,O) end, hashmap:new(), Ls). - * lists:foreach(fun(I) -> io:format("looking up ~p got ~p~n", [I, hashmap:get(I, A)]), I = hashmap:get(I,A) end, Ls). - * - * lists:foldl(fun(I,O) -> hashmap:put(I,I,O) end, hashmap:new(), lists:seq(1,7)). - * lists:foldl(fun(I,O) -> hashmap:info(O), hashmap:put(I,I,O) end, hashmap:new(), lists:seq(1,5)). - * - */ - -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif - -#include "sys.h" -#include "erl_vm.h" -#include "global.h" -#include "erl_process.h" -#include "error.h" -#include "bif.h" - -#include "erl_map.h" -#include "erl_hashmap.h" - -#if 0 -static char *format_binary(Uint64 x, char *b) { - int z; - b[64] = '\0'; - for (z = 0; z < 64; z++) { - b[63-z] = ((x>>z) & 0x1) ? '1' : '0'; - } - return b; -} -#endif - -/* hashmap:new/0 */ - -/* hashmap:put/3 */ - -/* hashmap:update/3 */ - -/* hashmap:to_list/1 */ - -/* hashmap:from_list/1 */ - -/* hashmap:get/2 */ - -/* hashmap:find/2 */ - -/* hashmap:remove/2 */ - -/* hashmap:size/1 */ - -/* erlang:is_hashmap/1 */ - -/* hashmap:is_key/2 */ - -/* hashmap:keys/1 */ - -/* hashmap:values/1 */ - -/* hashmap:info/0 */ diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h deleted file mode 100644 index 7ac33b34b0..0000000000 --- a/erts/emulator/beam/erl_hashmap.h +++ /dev/null @@ -1,96 +0,0 @@ -/* - * %CopyrightBegin% - * - * Copyright Ericsson AB 2011. All Rights Reserved. - * - * The contents of this file are subject to the Erlang Public License, - * Version 1.1, (the "License"); you may not use this file except in - * compliance with the License. You should have received a copy of the - * Erlang Public License along with this software. If not, it can be - * retrieved online at http://www.erlang.org/. - * - * Software distributed under the License is distributed on an "AS IS" - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See - * the License for the specific language governing rights and limitations - * under the License. - * - * %CopyrightEnd% - */ - - -#ifndef __ERL_HASH_H__ -#define __ERL_HASH_H__ - -#include "sys.h" -#include "erl_term.h" - -int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp); - -/* HASH */ - -/* hamt nodes v2.0 - * - * node :: leaf | array | bitmap - * head - */ -typedef struct hashmap_head_s { - Eterm thing_word; - Uint size; - Eterm items[1]; -} hashmap_head_t; - -/* thing_word tagscheme - * Need two bits for map subtags - * - * Original HEADER representation: - * - * aaaaaaaaaaaaaaaa aaaaaaaaaatttt00 arity:26, tag:4 - * - * For maps we have: - * - * vvvvvvvvvvvvvvvv aaaaaaaamm111100 val:16, arity:8, mtype:2 - * - * unsure about trailing zeros - * - * map-tag: - * 00 - flat map tag (non-hamt) -> val:16 = #items - * 01 - map-node bitmap tag -> val:16 = bitmap - * 10 - map-head (array-node) -> val:16 = 0xffff - * 11 - map-head (bitmap-node) -> val:16 = bitmap - */ - -/* erl_map.h stuff */ - -#define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2))) - -#define MAKE_MAP_HEADER(Type,Arity,Val) \ - (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_HASHMAP)) - -#define MAP_HEADER_HAMT_HEAD_ARRAY \ - MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_ARRAY,0x1,0xffff) - -#define MAP_HEADER_HAMT_HEAD_BITMAP(Bmp) \ - MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_BITMAP,0x1,Bmp) - -#define MAP_HEADER_HAMT_NODE_ARRAY \ - make_arityval(16) - -#define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \ - MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp) - -#define HAMT_HEAD_EMPTY_SZ (2) -#define HAMT_NODE_ARRAY_SZ (17) -#define HAMT_HEAD_ARRAY_SZ (18) -#define HAMT_NODE_BITMAP_SZ(n) (1 + n) -#define HAMT_HEAD_BITMAP_SZ(n) (2 + n) - -#define _HEADER_MAP_SUBTAG_MASK (0xfc) /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ -/* SUBTAG_NODE_ARRAY is in fact a tuple with 16 elements */ -#define HAMT_SUBTAG_NODE_ARRAY (((16 << _HEADER_ARITY_OFFS) | ARITYVAL_SUBTAG) & _HEADER_MAP_SUBTAG_MASK) -#define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) -#define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) -#define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) - -#define hashmap_index(hash) (((Uint32)hash) & 0xf) - -#endif diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 8ae02e0183..4242807933 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -16,6 +16,9 @@ * * %CopyrightEnd% * + * hashmaps are an adaption of Rich Hickeys Persistent HashMaps + * which were an adaption of Phil Bagwells - Hash Array Mapped Tries + * * Author: Björn-Egil Dahlberg */ @@ -31,7 +34,6 @@ #include "bif.h" #include "erl_map.h" -#include "erl_hashmap.h" /* BIFs * diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index 428cfe9b63..7fddc9c240 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -91,6 +91,7 @@ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res); int erts_validate_and_sort_map(map_t* map); void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node); Eterm* hashmap_iterator_next(struct ErtsWStack_* s); +int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp); Eterm erts_hashmap_get(Eterm key, Eterm map); Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n); @@ -104,4 +105,70 @@ erts_maps_get(Eterm key, Eterm map); # define erts_maps_get_rel(A, B, B_BASE) erts_maps_get(A, B) #endif +/* hamt nodes v2.0 + * + * node :: leaf | array | bitmap + * head + */ +typedef struct hashmap_head_s { + Eterm thing_word; + Uint size; + Eterm items[1]; +} hashmap_head_t; + +/* thing_word tagscheme + * Need two bits for map subtags + * + * Original HEADER representation: + * + * aaaaaaaaaaaaaaaa aaaaaaaaaatttt00 arity:26, tag:4 + * + * For maps we have: + * + * vvvvvvvvvvvvvvvv aaaaaaaamm111100 val:16, arity:8, mtype:2 + * + * unsure about trailing zeros + * + * map-tag: + * 00 - flat map tag (non-hamt) -> val:16 = #items + * 01 - map-node bitmap tag -> val:16 = bitmap + * 10 - map-head (array-node) -> val:16 = 0xffff + * 11 - map-head (bitmap-node) -> val:16 = bitmap + */ + +/* erl_map.h stuff */ + +#define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2))) + +#define MAKE_MAP_HEADER(Type,Arity,Val) \ + (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_HASHMAP)) + +#define MAP_HEADER_HAMT_HEAD_ARRAY \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_ARRAY,0x1,0xffff) + +#define MAP_HEADER_HAMT_HEAD_BITMAP(Bmp) \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_BITMAP,0x1,Bmp) + +#define MAP_HEADER_HAMT_NODE_ARRAY \ + make_arityval(16) + +#define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp) + +#define HAMT_HEAD_EMPTY_SZ (2) +#define HAMT_NODE_ARRAY_SZ (17) +#define HAMT_HEAD_ARRAY_SZ (18) +#define HAMT_NODE_BITMAP_SZ(n) (1 + n) +#define HAMT_HEAD_BITMAP_SZ(n) (2 + n) + +#define _HEADER_MAP_SUBTAG_MASK (0xfc) /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ +/* SUBTAG_NODE_ARRAY is in fact a tuple with 16 elements */ +#define HAMT_SUBTAG_NODE_ARRAY (((16 << _HEADER_ARITY_OFFS) | ARITYVAL_SUBTAG) & _HEADER_MAP_SUBTAG_MASK) +#define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) + +#define hashmap_index(hash) (((Uint32)hash) & 0xf) + + #endif diff --git a/erts/emulator/beam/erl_printf_term.c b/erts/emulator/beam/erl_printf_term.c index b07b7785dd..81fd19693a 100644 --- a/erts/emulator/beam/erl_printf_term.c +++ b/erts/emulator/beam/erl_printf_term.c @@ -26,7 +26,6 @@ #include "big.h" #include "erl_map.h" #include "erl_binary.h" -#include "erl_hashmap.h" #define PRINT_CHAR(CNT, FN, ARG, C) \ do { \ diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index 9030b528a4..af8db4c265 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -45,7 +45,6 @@ #include "erl_bits.h" #include "erl_zlib.h" #include "erl_map.h" -#include "erl_hashmap.h" #define in_area(ptr,start,nbytes) ((UWord)((char*)(ptr) - (char*)(start)) < (nbytes)) diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index f595cfbacd..d234e8fc68 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -32,7 +32,6 @@ #include "erl_binary.h" #include "erl_bits.h" #include "erl_map.h" -#include "erl_hashmap.h" #include "packet_parser.h" #include "erl_gc.h" #define ERTS_WANT_DB_INTERNAL__ diff --git a/erts/emulator/hipe/hipe_gc.c b/erts/emulator/hipe/hipe_gc.c index 398cbcdf14..b10263f6e2 100644 --- a/erts/emulator/hipe/hipe_gc.c +++ b/erts/emulator/hipe/hipe_gc.c @@ -28,7 +28,6 @@ #include "global.h" #include "erl_gc.h" -#include "erl_hashmap.h" #include "hipe_stack.h" #include "hipe_gc.h" |