1 /* 2 * %CopyrightBegin% 3 * 4 * Copyright Ericsson AB 2014-2017. All Rights Reserved. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * %CopyrightEnd% 19 */ 20 21 22 #ifndef __ERL_MAP_H__ 23 #define __ERL_MAP_H__ 24 25 #include "sys.h" 26 27 /* instrinsic wrappers */ 28 #if ERTS_AT_LEAST_GCC_VSN__(3, 4, 0) 29 #define hashmap_clz(x) ((Uint32) __builtin_clz((unsigned int)(x))) 30 #define hashmap_bitcount(x) ((Uint32) __builtin_popcount((unsigned int) (x))) 31 #else 32 Uint32 hashmap_clz(Uint32 x); 33 Uint32 hashmap_bitcount(Uint32 x); 34 #endif 35 36 /* MAP */ 37 38 typedef struct flatmap_s { 39 Eterm thing_word; 40 Uint size; 41 Eterm keys; /* tuple */ 42 } flatmap_t; 43 /* map node 44 * 45 * ----------- 46 * Eterm THING 47 * Uint size 48 * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = size 49 * ---- 50 * Eterm V1 51 * ... 52 * Eterm Vn, where n = size 53 * ----------- 54 */ 55 56 /* the head-node is a bitmap or array with an untagged size */ 57 58 59 #define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) 60 #define hashmap_make_hash(Key) make_internal_hash(Key, 0) 61 62 #define hashmap_restore_hash(Heap,Lvl,Key) \ 63 (((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7))) 64 #define hashmap_shift_hash(Heap,Hx,Lvl,Key) \ 65 (((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key))) 66 67 /* erl_term.h stuff */ 68 #define flatmap_get_values(x) (((Eterm *)(x)) + sizeof(flatmap_t)/sizeof(Eterm)) 69 #define flatmap_get_keys(x) (((Eterm *)tuple_val(((flatmap_t *)(x))->keys)) + 1) 70 #define flatmap_get_size(x) (((flatmap_t*)(x))->size) 71 72 #ifdef DEBUG 73 #define MAP_SMALL_MAP_LIMIT (3) 74 #else 75 #define MAP_SMALL_MAP_LIMIT (32) 76 #endif 77 78 struct ErtsWStack_; 79 struct ErtsEStack_; 80 81 Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map); 82 int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res); 83 int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res); 84 int erts_maps_take(Process *p, Eterm key, Eterm map, Eterm *res, Eterm *value); 85 86 Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, 87 Eterm node, int is_update); 88 int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz, 89 Uint *upsz, struct ErtsEStack_ *sp, int is_update); 90 Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, 91 Uint *upsz, struct ErtsEStack_ *sp); 92 93 int erts_validate_and_sort_flatmap(flatmap_t* map); 94 void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node, int reverse); 95 Eterm* hashmap_iterator_next(struct ErtsWStack_* s); 96 Eterm* hashmap_iterator_prev(struct ErtsWStack_* s); 97 int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp); 98 Eterm erts_hashmap_from_array(ErtsHeapFactory*, Eterm *leafs, Uint n, int reject_dupkeys); 99 100 #define erts_hashmap_from_ks_and_vs(F, KS, VS, N) \ 101 erts_hashmap_from_ks_and_vs_extra((F), (KS), (VS), (N), THE_NON_VALUE, THE_NON_VALUE); 102 103 Eterm erts_map_from_ks_and_vs(ErtsHeapFactory *factory, Eterm *ks, Eterm *vs, Uint n); 104 Eterm erts_hashmap_from_ks_and_vs_extra(ErtsHeapFactory *factory, 105 Eterm *ks, Eterm *vs, Uint n, 106 Eterm k, Eterm v); 107 108 const Eterm *erts_maps_get(Eterm key, Eterm map); 109 110 const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm map); 111 112 /* hamt nodes v2.0 113 * 114 * node :: leaf | array | bitmap 115 * head 116 */ 117 typedef struct hashmap_head_s { 118 Eterm thing_word; 119 Uint size; 120 Eterm items[1]; 121 } hashmap_head_t; 122 123 /* thing_word tagscheme 124 * Need two bits for map subtags 125 * 126 * Original HEADER representation: 127 * 128 * aaaaaaaaaaaaaaaa aaaaaaaaaatttt00 arity:26, tag:4 129 * 130 * For maps we have: 131 * 132 * vvvvvvvvvvvvvvvv aaaaaaaamm111100 val:16, arity:8, mtype:2 133 * 134 * unsure about trailing zeros 135 * 136 * map-tag: 137 * 00 - flat map tag (non-hamt) -> val:16 = #items 138 * 01 - map-node bitmap tag -> val:16 = bitmap 139 * 10 - map-head (array-node) -> val:16 = 0xffff 140 * 11 - map-head (bitmap-node) -> val:16 = bitmap 141 */ 142 143 /* erl_map.h stuff */ 144 145 #define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2))) 146 147 #define MAKE_MAP_HEADER(Type,Arity,Val) \ 148 (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_MAP)) 149 150 #define MAP_HEADER_FLATMAP \ 151 MAKE_MAP_HEADER(MAP_HEADER_TAG_FLATMAP_HEAD,0x1,0x0) 152 153 #define MAP_HEADER_HAMT_HEAD_ARRAY \ 154 MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_ARRAY,0x1,0xffff) 155 156 #define MAP_HEADER_HAMT_HEAD_BITMAP(Bmp) \ 157 MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_BITMAP,0x1,Bmp) 158 159 #define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \ 160 MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp) 161 162 #define MAP_HEADER_FLATMAP_SZ (sizeof(flatmap_t) / sizeof(Eterm)) 163 164 #define HAMT_NODE_ARRAY_SZ (17) 165 #define HAMT_HEAD_ARRAY_SZ (18) 166 #define HAMT_NODE_BITMAP_SZ(n) (1 + n) 167 #define HAMT_HEAD_BITMAP_SZ(n) (2 + n) 168 169 /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ 170 #define _HEADER_MAP_SUBTAG_MASK (0xfc) 171 /* 1 bit map tag + 1 ignore bit + 4 bits subtag + 2 ignore bits */ 172 #define _HEADER_MAP_HASHMAP_HEAD_MASK (0xbc) 173 174 #define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | MAP_SUBTAG) 175 #define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | MAP_SUBTAG) 176 #define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | MAP_SUBTAG) 177 #define HAMT_SUBTAG_HEAD_FLATMAP ((MAP_HEADER_TAG_FLATMAP_HEAD << _HEADER_ARITY_OFFS) | MAP_SUBTAG) 178 179 #define hashmap_index(hash) (((Uint32)hash) & 0xf) 180 181 /* hashmap heap size: 182 [one cons cell + one list term in parent node] per key 183 [one header + one boxed term in parent node] per inner node 184 [one header + one size word] for root node 185 Observed average number of nodes per key is about 0.35. 186 */ 187 #define HASHMAP_WORDS_PER_KEY 3 188 #define HASHMAP_WORDS_PER_NODE 2 189 #ifdef DEBUG 190 # define HASHMAP_ESTIMATED_TOT_NODE_SIZE(KEYS) \ 191 (HASHMAP_WORDS_PER_NODE * (KEYS) * 3/10) /* slightly under estimated */ 192 #else 193 # define HASHMAP_ESTIMATED_TOT_NODE_SIZE(KEYS) \ 194 (HASHMAP_WORDS_PER_NODE * (KEYS) * 4/10) /* slightly over estimated */ 195 #endif 196 #define HASHMAP_ESTIMATED_HEAP_SIZE(KEYS) \ 197 ((KEYS)*HASHMAP_WORDS_PER_KEY + HASHMAP_ESTIMATED_TOT_NODE_SIZE(KEYS)) 198 #endif 199