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
|
/*
* %CopyrightBegin%
*
* Copyright Ericsson AB 2014. 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_MAP_H__
#define __ERL_MAP_H__
#include "sys.h"
/* instrinsic wrappers */
#if defined(__GNUC__)
#define hashmap_clz(x) ((Uint32) __builtin_clz((unsigned int)(x)))
#define hashmap_bitcount(x) ((Uint32) __builtin_popcount((unsigned int) (x)))
#else
Uint32 hashmap_clz(Uint32 x);
Uint32 hashmap_bitcount(Uint32 x);
#endif
/* MAP */
typedef struct map_s {
Eterm thing_word;
Uint size;
Eterm keys; /* tuple */
} map_t;
/* map node
*
* -----------
* Eterm THING
* Uint size
* Eterm Keys -> {K1, K2, K3, ..., Kn} where n = size
* ----
* Eterm V1
* ...
* Eterm Vn, where n = size
* -----------
*/
/* the head-node is a bitmap or array with an untagged size */
#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size)
#define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE))
#define hashmap_make_hash(Key) make_hash2(Key)
#define hashmap_restore_hash(Heap,Lvl,Key) \
(((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7)))
#define hashmap_shift_hash(Heap,Hx,Lvl,Key) \
(((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key)))
/* erl_term.h stuff */
#define make_map(x) make_boxed((Eterm*)(x))
#define make_map_rel(x, BASE) make_boxed_rel((Eterm*)(x),(BASE))
#define is_map(x) (is_boxed((x)) && is_map_header(*boxed_val((x))))
#define is_map_rel(RTERM,BASE) is_map(rterm2wterm(RTERM,BASE))
#define is_not_map(x) (!is_map((x)))
#define is_map_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_MAP)
#define header_is_map(x) ((((x) & (_HEADER_SUBTAG_MASK)) == MAP_SUBTAG))
#define map_val(x) (_unchecked_boxed_val((x)))
#define map_val_rel(RTERM, BASE) map_val(rterm2wterm(RTERM, BASE))
#define map_get_values(x) (((Eterm *)(x)) + 3)
#define map_get_keys(x) (((Eterm *)tuple_val(((map_t *)(x))->keys)) + 1)
#define map_get_size(x) (((map_t*)(x))->size)
#define MAP_SMALL_MAP_LIMIT (32)
#define MAP_HEADER _make_header(1,_TAG_HEADER_MAP)
#define MAP_HEADER_SIZE (sizeof(map_t) / sizeof(Eterm))
struct ErtsWStack_;
Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map);
int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res);
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);
Eterm erts_hashmap_get(Eterm key, Eterm map);
Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
#if HALFWORD_HEAP
const Eterm *
erts_maps_get_rel(Eterm key, Eterm map, Eterm *map_base);
# define erts_maps_get(A, B) erts_maps_get_rel(A, B, NULL)
#else
const Eterm *
erts_maps_get(Eterm key, Eterm map);
# define erts_maps_get_rel(A, B, B_BASE) erts_maps_get(A, B)
#endif
#endif
|
