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 : 77717800 : static inline size_t jl_intref(const jl_array_t *arr, size_t idx) JL_NOTSAFEPOINT
21 : : {
22 : 77717800 : jl_value_t *el = jl_tparam0(jl_typeof(arr));
23 [ + + ]: 77717800 : if (el == (jl_value_t*)jl_uint8_type)
24 : 50628400 : return ((uint8_t*)jl_array_data(arr))[idx];
25 [ + - ]: 27089400 : else if (el == (jl_value_t*)jl_uint16_type)
26 : 27089400 : 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 : 4008940 : static inline void jl_intset(const jl_array_t *arr, size_t idx, size_t val) JL_NOTSAFEPOINT
34 : : {
35 : 4008940 : jl_value_t *el = jl_tparam0(jl_typeof(arr));
36 [ + + ]: 4008940 : if (el == (jl_value_t*)jl_uint8_type)
37 : 2111530 : ((uint8_t*)jl_array_data(arr))[idx] = val;
38 [ + - ]: 1897410 : else if (el == (jl_value_t*)jl_uint16_type)
39 : 1897410 : ((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 : 4008940 : }
45 : :
46 : 1940750 : static inline size_t jl_max_int(const jl_array_t *arr)
47 : : {
48 : 1940750 : jl_value_t *el = jl_tparam0(jl_typeof(arr));
49 [ + + ]: 1940750 : if (el == (jl_value_t*)jl_uint8_type)
50 : 973925 : return 0xFF;
51 [ + + ]: 966823 : else if (el == (jl_value_t*)jl_uint16_type)
52 : 873394 : return 0xFFFF;
53 [ - + ]: 93429 : else if (el == (jl_value_t*)jl_uint32_type)
54 : 0 : return 0xFFFFFFFF;
55 [ + - ]: 93429 : else if (el == (jl_value_t*)jl_any_type)
56 : 93429 : return 0;
57 : : else
58 : 0 : abort();
59 : : }
60 : :
61 : 204799 : static jl_array_t *jl_alloc_int_1d(size_t np, size_t len)
62 : : {
63 : : jl_value_t *ty;
64 [ + + ]: 204799 : if (np < 0xFF) {
65 : 202237 : ty = jl_array_uint8_type;
66 : : }
67 [ + - ]: 2562 : else if (np < 0xFFFF) {
68 : : static jl_value_t *int16 JL_ALWAYS_LEAFTYPE = NULL;
69 [ + + ]: 2562 : if (int16 == NULL)
70 : 51 : int16 = jl_apply_array_type((jl_value_t*)jl_uint16_type, 1);
71 : 2562 : 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 : 204799 : jl_array_t *a = jl_alloc_array_1d(ty, len);
81 : 204799 : memset(a->data, 0, len * a->elsize);
82 : 204799 : return a;
83 : : }
84 : :
85 : 42400600 : ssize_t jl_smallintset_lookup(jl_array_t *cache, smallintset_eq eq, const void *key, jl_svec_t *data, uint_t hv)
86 : : {
87 : 42400600 : size_t sz = jl_array_len(cache);
88 [ + + ]: 42400600 : if (sz == 0)
89 : 190078 : return -1;
90 : 42210500 : JL_GC_PUSH1(&cache);
91 [ + + ]: 42210500 : size_t maxprobe = max_probe(sz);
92 : 42210500 : size_t index = h2index(hv, sz);
93 : 42210500 : size_t orig = index;
94 : 42210500 : size_t iter = 0;
95 : : do {
96 : 64109100 : size_t val1 = jl_intref(cache, index);
97 [ + + ]: 64109100 : if (val1 == 0) {
98 : 3691670 : JL_GC_POP();
99 : 3691670 : return -1;
100 : : }
101 [ + + ]: 60417400 : if (eq(val1 - 1, key, data, hv)) {
102 : 38485400 : JL_GC_POP();
103 : 38485400 : return val1 - 1;
104 : : }
105 : 21932000 : index = (index + 1) & (sz - 1);
106 : 21932000 : iter++;
107 [ + + + - ]: 21932000 : } while (iter <= maxprobe && index != orig);
108 : 33355 : JL_GC_POP();
109 : 33355 : return -1;
110 : : }
111 : :
112 : 4118980 : static int smallintset_insert_(jl_array_t *a, uint_t hv, size_t val1)
113 : : {
114 : 4118980 : size_t sz = jl_array_len(a);
115 [ + + ]: 4118980 : if (sz <= 1)
116 : 93429 : return 0;
117 : : size_t orig, index, iter;
118 : 4025550 : iter = 0;
119 : 4025550 : index = h2index(hv, sz);
120 : 4025550 : orig = index;
121 [ + + ]: 4025550 : size_t maxprobe = max_probe(sz);
122 : : do {
123 [ + + ]: 7371390 : if (jl_intref(a, index) == 0) {
124 : 4008940 : jl_intset(a, index, val1);
125 : 4008940 : return 1;
126 : : }
127 : 3362450 : index = (index + 1) & (sz - 1);
128 : 3362450 : iter++;
129 [ + + + - ]: 3362450 : } while (iter <= maxprobe && index != orig);
130 : 16611 : 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 : 1940750 : 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 : 1940750 : jl_array_t *a = jl_atomic_load_relaxed(pcache);
138 [ + + ]: 1940750 : if (val + 1 > jl_max_int(a))
139 : 94759 : smallintset_rehash(pcache, parent, hash, data, jl_array_len(a), val + 1);
140 : 110040 : while (1) {
141 : 2050790 : a = jl_atomic_load_relaxed(pcache);
142 [ + + ]: 2050790 : if (smallintset_insert_(a, hash(val, data), val + 1))
143 : 1940750 : 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 : 110040 : a = jl_atomic_load_relaxed(pcache);
151 : 110040 : size_t sz = jl_array_len(a);
152 [ + + ]: 110040 : if (sz < HT_N_INLINE)
153 : 93429 : newsz = HT_N_INLINE;
154 [ + - + + ]: 16611 : else if (sz >= (1 << 19) || (sz <= (1 << 8)))
155 : 15343 : newsz = sz << 1;
156 : : else
157 : 1268 : newsz = sz << 2;
158 : 110040 : smallintset_rehash(pcache, parent, hash, data, newsz, 0);
159 : : }
160 : : }
161 : :
162 : 204799 : 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 : 204799 : jl_array_t *a = jl_atomic_load_relaxed(pcache);
165 : 204799 : size_t sz = jl_array_len(a);
166 : : size_t i;
167 [ + + ]: 3323460 : for (i = 0; i < sz; i += 1) {
168 : 3118660 : size_t val = jl_intref(a, i);
169 [ + + ]: 3118660 : if (val > np)
170 : 101448 : np = val;
171 : : }
172 : 0 : while (1) {
173 : 204799 : jl_array_t *newa = jl_alloc_int_1d(np, newsz);
174 : 204799 : JL_GC_PUSH1(&newa);
175 [ + + ]: 3323460 : for (i = 0; i < sz; i += 1) {
176 : 3118660 : size_t val1 = jl_intref(a, i);
177 [ + + ]: 3118660 : if (val1 != 0) {
178 [ - + ]: 2068190 : if (!smallintset_insert_(newa, hash(val1 - 1, data), val1)) {
179 : 0 : break;
180 : : }
181 : : }
182 : : }
183 : 204799 : JL_GC_POP();
184 [ + - ]: 204799 : if (i == sz) {
185 : 204799 : jl_atomic_store_release(pcache, newa);
186 : 204799 : jl_gc_wb(parent, newa);
187 : 204799 : return;
188 : : }
189 : 0 : newsz <<= 1;
190 : : }
191 : : }
192 : :
193 : :
194 : : #ifdef __cplusplus
195 : : }
196 : : #endif
|
