1 files changed, 67 insertions, 0 deletions
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