Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : #include <stdlib.h>
4 : : #include <string.h>
5 : : #include "julia.h"
6 : : #include "julia_internal.h"
7 : : #ifndef _OS_WINDOWS_
8 : : #include <unistd.h>
9 : : #endif
10 : : #include "julia_assert.h"
11 : :
12 : : // compute empirical max-probe for a given size
13 : : #define max_probe(size) ((size) <= 1024 ? 16 : (size) >> 6)
14 : : #define h2index(hv, sz) (size_t)((hv) & ((sz)-1))
15 : :
16 : : #ifdef __cplusplus
17 : : extern "C" {
18 : : #endif
19 : :
20 : 6153180 : static inline size_t jl_intref(const jl_array_t *arr, size_t idx) JL_NOTSAFEPOINT
21 : : {
22 : 6153180 : jl_value_t *el = jl_tparam0(jl_typeof(arr));
23 [ + + ]: 6153180 : if (el == (jl_value_t*)jl_uint8_type)
24 : 5160730 : return ((uint8_t*)jl_array_data(arr))[idx];
25 [ + - ]: 992444 : else if (el == (jl_value_t*)jl_uint16_type)
26 : 992444 : return ((uint16_t*)jl_array_data(arr))[idx];
27 [ # # ]: 0 : else if (el == (jl_value_t*)jl_uint32_type)
28 : 0 : return ((uint32_t*)jl_array_data(arr))[idx];
29 : : else
30 : 0 : abort();
31 : : }
32 : :
33 : 349390 : static inline void jl_intset(const jl_array_t *arr, size_t idx, size_t val) JL_NOTSAFEPOINT
34 : : {
35 : 349390 : jl_value_t *el = jl_tparam0(jl_typeof(arr));
36 [ + + ]: 349390 : if (el == (jl_value_t*)jl_uint8_type)
37 : 284565 : ((uint8_t*)jl_array_data(arr))[idx] = val;
38 [ + - ]: 64825 : else if (el == (jl_value_t*)jl_uint16_type)
39 : 64825 : ((uint16_t*)jl_array_data(arr))[idx] = val;
40 [ # # ]: 0 : else if (el == (jl_value_t*)jl_uint32_type)
41 : 0 : ((uint32_t*)jl_array_data(arr))[idx] = val;
42 : : else
43 : 0 : abort();
44 : 349390 : }
45 : :
46 : 182755 : static inline size_t jl_max_int(const jl_array_t *arr)
47 : : {
48 : 182755 : jl_value_t *el = jl_tparam0(jl_typeof(arr));
49 [ + + ]: 182755 : if (el == (jl_value_t*)jl_uint8_type)
50 : 133679 : return 0xFF;
51 [ + + ]: 49076 : else if (el == (jl_value_t*)jl_uint16_type)
52 : 22204 : return 0xFFFF;
53 [ - + ]: 26872 : else if (el == (jl_value_t*)jl_uint32_type)
54 : 0 : return 0xFFFFFFFF;
55 [ + - ]: 26872 : else if (el == (jl_value_t*)jl_any_type)
56 : 26872 : return 0;
57 : : else
58 : 0 : abort();
59 : : }
60 : :
61 : 56186 : static jl_array_t *jl_alloc_int_1d(size_t np, size_t len)
62 : : {
63 : : jl_value_t *ty;
64 [ + + ]: 56186 : if (np < 0xFF) {
65 : 56051 : ty = jl_array_uint8_type;
66 : : }
67 [ + - ]: 135 : else if (np < 0xFFFF) {
68 : : static jl_value_t *int16 JL_ALWAYS_LEAFTYPE = NULL;
69 [ + + ]: 135 : if (int16 == NULL)
70 : 7 : int16 = jl_apply_array_type((jl_value_t*)jl_uint16_type, 1);
71 : 135 : ty = int16;
72 : : }
73 : : else {
74 [ # # ]: 0 : assert(np < 0x7FFFFFFF);
75 : : static jl_value_t *int32 JL_ALWAYS_LEAFTYPE = NULL;
76 [ # # ]: 0 : if (int32 == NULL)
77 : 0 : int32 = jl_apply_array_type((jl_value_t*)jl_uint32_type, 1);
78 : 0 : ty = int32;
79 : : }
80 : 56186 : jl_array_t *a = jl_alloc_array_1d(ty, len);
81 : 56186 : memset(a->data, 0, len * a->elsize);
82 : 56186 : return a;
83 : : }
84 : :
85 : 3431550 : ssize_t jl_smallintset_lookup(jl_array_t *cache, smallintset_eq eq, const void *key, jl_svec_t *data, uint_t hv)
86 : : {
87 : 3431550 : size_t sz = jl_array_len(cache);
88 [ + + ]: 3431550 : if (sz == 0)
89 : 54056 : return -1;
90 : 3377490 : JL_GC_PUSH1(&cache);
91 [ + + ]: 3377490 : size_t maxprobe = max_probe(sz);
92 : 3377490 : size_t index = h2index(hv, sz);
93 : 3377490 : size_t orig = index;
94 : 3377490 : size_t iter = 0;
95 : : do {
96 : 5006250 : size_t val1 = jl_intref(cache, index);
97 [ + + ]: 5006250 : if (val1 == 0) {
98 : 309096 : JL_GC_POP();
99 : 309096 : return -1;
100 : : }
101 [ + + ]: 4697160 : if (eq(val1 - 1, key, data, hv)) {
102 : 3063650 : JL_GC_POP();
103 : 3063650 : return val1 - 1;
104 : : }
105 : 1633500 : index = (index + 1) & (sz - 1);
106 : 1633500 : iter++;
107 [ + + + - ]: 1633500 : } while (iter <= maxprobe && index != orig);
108 : 4742 : JL_GC_POP();
109 : 4742 : return -1;
110 : : }
111 : :
112 : 378628 : static int smallintset_insert_(jl_array_t *a, uint_t hv, size_t val1)
113 : : {
114 : 378628 : size_t sz = jl_array_len(a);
115 [ + + ]: 378628 : if (sz <= 1)
116 : 26872 : return 0;
117 : : size_t orig, index, iter;
118 : 351756 : iter = 0;
119 : 351756 : index = h2index(hv, sz);
120 : 351756 : orig = index;
121 [ + + ]: 351756 : size_t maxprobe = max_probe(sz);
122 : : do {
123 [ + + ]: 663533 : if (jl_intref(a, index) == 0) {
124 : 349390 : jl_intset(a, index, val1);
125 : 349390 : return 1;
126 : : }
127 : 314143 : index = (index + 1) & (sz - 1);
128 : 314143 : iter++;
129 [ + + + - ]: 314143 : } while (iter <= maxprobe && index != orig);
130 : 2366 : return 0;
131 : : }
132 : :
133 : : static void smallintset_rehash(_Atomic(jl_array_t*) *pcache, jl_value_t *parent, smallintset_hash hash, jl_svec_t *data, size_t newsz, size_t np);
134 : :
135 : 182755 : void jl_smallintset_insert(_Atomic(jl_array_t*) *pcache, jl_value_t *parent, smallintset_hash hash, size_t val, jl_svec_t *data)
136 : : {
137 : 182755 : jl_array_t *a = jl_atomic_load_relaxed(pcache);
138 [ + + ]: 182755 : if (val + 1 > jl_max_int(a))
139 : 26948 : smallintset_rehash(pcache, parent, hash, data, jl_array_len(a), val + 1);
140 : 29238 : while (1) {
141 : 211993 : a = jl_atomic_load_relaxed(pcache);
142 [ + + ]: 211993 : if (smallintset_insert_(a, hash(val, data), val + 1))
143 : 182755 : return;
144 : :
145 : : /* table full */
146 : : /* rehash to grow and retry the insert */
147 : : /* it's important to grow the table really fast; otherwise we waste */
148 : : /* lots of time rehashing all the keys over and over. */
149 : : size_t newsz;
150 : 29238 : a = jl_atomic_load_relaxed(pcache);
151 : 29238 : size_t sz = jl_array_len(a);
152 [ + + ]: 29238 : if (sz < HT_N_INLINE)
153 : 26872 : newsz = HT_N_INLINE;
154 [ + - + + ]: 2366 : else if (sz >= (1 << 19) || (sz <= (1 << 8)))
155 : 2302 : newsz = sz << 1;
156 : : else
157 : 64 : newsz = sz << 2;
158 : 29238 : smallintset_rehash(pcache, parent, hash, data, newsz, 0);
159 : : }
160 : : }
161 : :
162 : 56186 : static void smallintset_rehash(_Atomic(jl_array_t*) *pcache, jl_value_t *parent, smallintset_hash hash, jl_svec_t *data, size_t newsz, size_t np)
163 : : {
164 : 56186 : jl_array_t *a = jl_atomic_load_relaxed(pcache);
165 : 56186 : size_t sz = jl_array_len(a);
166 : : size_t i;
167 [ + + ]: 297882 : for (i = 0; i < sz; i += 1) {
168 : 241696 : size_t val = jl_intref(a, i);
169 [ + + ]: 241696 : if (val > np)
170 : 13763 : np = val;
171 : : }
172 : 0 : while (1) {
173 : 56186 : jl_array_t *newa = jl_alloc_int_1d(np, newsz);
174 : 56186 : JL_GC_PUSH1(&newa);
175 [ + + ]: 297882 : for (i = 0; i < sz; i += 1) {
176 : 241696 : size_t val1 = jl_intref(a, i);
177 [ + + ]: 241696 : if (val1 != 0) {
178 [ - + ]: 166635 : if (!smallintset_insert_(newa, hash(val1 - 1, data), val1)) {
179 : 0 : break;
180 : : }
181 : : }
182 : : }
183 : 56186 : JL_GC_POP();
184 [ + - ]: 56186 : if (i == sz) {
185 : 56186 : jl_atomic_store_release(pcache, newa);
186 : 56186 : jl_gc_wb(parent, newa);
187 : 56186 : return;
188 : : }
189 : 0 : newsz <<= 1;
190 : : }
191 : : }
192 : :
193 : :
194 : : #ifdef __cplusplus
195 : : }
196 : : #endif
|
