1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
/*
* %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"
Eterm erts_hashmap_get(Eterm key, Eterm map);
/* erl_term.h stuff */
#define make_hashmap(x) make_boxed((Eterm*)(x))
#define make_hashmap_rel make_boxed_rel
#define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x))))
#define is_hashmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HASHMAP)
#define hashmap_val(x) _unchecked_boxed_val((x))
#define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE))
/* HASH */
#if defined(__GNUC__)
#define hashmap_bitcount(x) (Uint32) __builtin_popcount((unsigned int) (x))
#else
const Uint32 SK5 = 0x55555555, SK3 = 0x33333333;
const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF;
/* CTPOP emulation */
Uint32 hashmap_bitcount(Uint32 map) {
map -= (( map >> 1 ) & SK5 );
map = ( map & SK3 ) + (( map >> 2 ) & SK3 );
map = ( map & SKF0 ) + (( map >> 4 ) & SKF0);
map += map >> 8;
return ( map + ( map >> 16)) & 0x3F;
}
#endif
/* hamt nodes v2.0
*
* node :: leaf | array | bitmap
* head
*/
/* the head-node is a bitmap or array with an untagged size
*/
typedef struct hashmap_head_s {
Eterm thing_word;
Uint size;
Eterm items[1];
} hashmap_head_t;
/* the bitmap-node
* typedef struct hashmap_bitmap_node_s {
* Eterm thing_word;
* Eterm items[1];
* } hashmap_bitmap_node_t;
*
* the array-node is a tuple
* typedef struct hashmap_bitmap_node_s {
* Eterm thing_word;
* Eterm items[1];
* } hashmap_bitmap_node_t;
*
* the leaf-node
* cons-cell
*/
/* 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 MAP_HEADER_TAG_SZ (2)
#define MAP_HEADER_ARITY_SZ (8)
#define MAP_HEADER_VAL_SZ (16)
#define MAP_HEADER_TAG_FLAT (0x0)
#define MAP_HEADER_TAG_HAMT_NODE_BITMAP (0x1)
#define MAP_HEADER_TAG_HAMT_HEAD_ARRAY (0x2)
#define MAP_HEADER_TAG_HAMT_HEAD_BITMAP (0x3)
#define MAP_HEADER_TYPE(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS)) & (0x3))
#define MAP_HEADER_ARITY(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ)) & (0xff))
#define MAP_HEADER_VAL(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ + MAP_HEADER_ARITY_SZ)) & (0xffff))
#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_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
|
