1 /*
2 * Copyright (c) 2021 Calvin Rose
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20 * IN THE SOFTWARE.
21 */
22
23 #ifndef JANET_AMALG
24 #include "features.h"
25 #include <janet.h>
26 #include "gc.h"
27 #include "util.h"
28 #include <math.h>
29 #endif
30
31 /* Begin creation of a struct */
janet_struct_begin(int32_t count)32 JanetKV *janet_struct_begin(int32_t count) {
33 /* Calculate capacity as power of 2 after 2 * count. */
34 int32_t capacity = janet_tablen(2 * count);
35 if (capacity < 0) capacity = janet_tablen(count + 1);
36
37 size_t size = sizeof(JanetStructHead) + (size_t) capacity * sizeof(JanetKV);
38 JanetStructHead *head = janet_gcalloc(JANET_MEMORY_STRUCT, size);
39 head->length = count;
40 head->capacity = capacity;
41 head->hash = 0;
42 head->proto = NULL;
43
44 JanetKV *st = (JanetKV *)(head->data);
45 janet_memempty(st, capacity);
46 return st;
47 }
48
49 /* Find an item in a struct without looking for prototypes. Should be similar to janet_dict_find, but
50 * specialized to structs (slightly more compact). */
janet_struct_find(const JanetKV * st,Janet key)51 const JanetKV *janet_struct_find(const JanetKV *st, Janet key) {
52 int32_t cap = janet_struct_capacity(st);
53 int32_t index = janet_maphash(cap, janet_hash(key));
54 int32_t i;
55 for (i = index; i < cap; i++)
56 if (janet_checktype(st[i].key, JANET_NIL) || janet_equals(st[i].key, key))
57 return st + i;
58 for (i = 0; i < index; i++)
59 if (janet_checktype(st[i].key, JANET_NIL) || janet_equals(st[i].key, key))
60 return st + i;
61 return NULL;
62 }
63
64 /* Put a kv pair into a struct that has not yet been fully constructed.
65 * Nil keys and values are ignored, extra keys are ignore, and duplicate keys are
66 * ignored.
67 *
68 * Runs will be in sorted order, as the collisions resolver essentially
69 * preforms an in-place insertion sort. This ensures the internal structure of the
70 * hash map is independent of insertion order.
71 */
janet_struct_put_ext(JanetKV * st,Janet key,Janet value,int replace)72 void janet_struct_put_ext(JanetKV *st, Janet key, Janet value, int replace) {
73 int32_t cap = janet_struct_capacity(st);
74 int32_t hash = janet_hash(key);
75 int32_t index = janet_maphash(cap, hash);
76 int32_t i, j, dist;
77 int32_t bounds[4] = {index, cap, 0, index};
78 if (janet_checktype(key, JANET_NIL) || janet_checktype(value, JANET_NIL)) return;
79 if (janet_checktype(key, JANET_NUMBER) && isnan(janet_unwrap_number(key))) return;
80 /* Avoid extra items */
81 if (janet_struct_hash(st) == janet_struct_length(st)) return;
82 for (dist = 0, j = 0; j < 4; j += 2)
83 for (i = bounds[j]; i < bounds[j + 1]; i++, dist++) {
84 int status;
85 int32_t otherhash;
86 int32_t otherindex, otherdist;
87 JanetKV *kv = st + i;
88 /* We found an empty slot, so just add key and value */
89 if (janet_checktype(kv->key, JANET_NIL)) {
90 kv->key = key;
91 kv->value = value;
92 /* Update the temporary count */
93 janet_struct_hash(st)++;
94 return;
95 }
96 /* Robinhood hashing - check if colliding kv pair
97 * is closer to their source than current. We use robinhood
98 * hashing to ensure that equivalent structs that are constructed
99 * with different order have the same internal layout, and therefor
100 * will compare properly - i.e., {1 2 3 4} should equal {3 4 1 2}.
101 * Collisions are resolved via an insertion sort insertion. */
102 otherhash = janet_hash(kv->key);
103 otherindex = janet_maphash(cap, otherhash);
104 otherdist = (i + cap - otherindex) & (cap - 1);
105 if (dist < otherdist)
106 status = -1;
107 else if (otherdist < dist)
108 status = 1;
109 else if (hash < otherhash)
110 status = -1;
111 else if (otherhash < hash)
112 status = 1;
113 else
114 status = janet_compare(key, kv->key);
115 /* If other is closer to their ideal slot */
116 if (status == 1) {
117 /* Swap current kv pair with pair in slot */
118 JanetKV temp = *kv;
119 kv->key = key;
120 kv->value = value;
121 key = temp.key;
122 value = temp.value;
123 /* Save dist and hash of new kv pair */
124 dist = otherdist;
125 hash = otherhash;
126 } else if (status == 0) {
127 if (replace) {
128 /* A key was added to the struct more than once - replace old value */
129 kv->value = value;
130 }
131 return;
132 }
133 }
134 }
135
janet_struct_put(JanetKV * st,Janet key,Janet value)136 void janet_struct_put(JanetKV *st, Janet key, Janet value) {
137 janet_struct_put_ext(st, key, value, 1);
138 }
139
140 /* Finish building a struct */
janet_struct_end(JanetKV * st)141 const JanetKV *janet_struct_end(JanetKV *st) {
142 if (janet_struct_hash(st) != janet_struct_length(st)) {
143 /* Error building struct, probably duplicate values. We need to rebuild
144 * the struct using only the values that went in. The second creation should always
145 * succeed. */
146 JanetKV *newst = janet_struct_begin(janet_struct_hash(st));
147 for (int32_t i = 0; i < janet_struct_capacity(st); i++) {
148 JanetKV *kv = st + i;
149 if (!janet_checktype(kv->key, JANET_NIL)) {
150 janet_struct_put(newst, kv->key, kv->value);
151 }
152 }
153 janet_struct_proto(newst) = janet_struct_proto(st);
154 st = newst;
155 }
156 janet_struct_hash(st) = janet_kv_calchash(st, janet_struct_capacity(st));
157 if (janet_struct_proto(st)) {
158 janet_struct_hash(st) += 2654435761u * janet_struct_hash(janet_struct_proto(st));
159 }
160 return (const JanetKV *)st;
161 }
162
163 /* Get an item from a struct without looking into prototypes. */
janet_struct_rawget(const JanetKV * st,Janet key)164 Janet janet_struct_rawget(const JanetKV *st, Janet key) {
165 const JanetKV *kv = janet_struct_find(st, key);
166 return kv ? kv->value : janet_wrap_nil();
167 }
168
169 /* Get an item from a struct */
janet_struct_get(const JanetKV * st,Janet key)170 Janet janet_struct_get(const JanetKV *st, Janet key) {
171 for (int i = JANET_MAX_PROTO_DEPTH; st && i; --i, st = janet_struct_proto(st)) {
172 const JanetKV *kv = janet_struct_find(st, key);
173 if (NULL != kv && !janet_checktype(kv->key, JANET_NIL)) {
174 return kv->value;
175 }
176 }
177 return janet_wrap_nil();
178 }
179
180 /* Get an item from a struct, and record which prototype the item came from. */
janet_struct_get_ex(const JanetKV * st,Janet key,JanetStruct * which)181 Janet janet_struct_get_ex(const JanetKV *st, Janet key, JanetStruct *which) {
182 for (int i = JANET_MAX_PROTO_DEPTH; st && i; --i, st = janet_struct_proto(st)) {
183 const JanetKV *kv = janet_struct_find(st, key);
184 if (NULL != kv && !janet_checktype(kv->key, JANET_NIL)) {
185 *which = st;
186 return kv->value;
187 }
188 }
189 return janet_wrap_nil();
190 }
191
192 /* Convert struct to table */
janet_struct_to_table(const JanetKV * st)193 JanetTable *janet_struct_to_table(const JanetKV *st) {
194 JanetTable *table = janet_table(janet_struct_capacity(st));
195 int32_t i;
196 for (i = 0; i < janet_struct_capacity(st); i++) {
197 const JanetKV *kv = st + i;
198 if (!janet_checktype(kv->key, JANET_NIL)) {
199 janet_table_put(table, kv->key, kv->value);
200 }
201 }
202 return table;
203 }
204
205 /* C Functions */
206
207 JANET_CORE_FN(cfun_struct_with_proto,
208 "(struct/with-proto proto & kvs)",
209 "Create a structure, as with the usual struct constructor but set the "
210 "struct prototype as well.") {
211 janet_arity(argc, 1, -1);
212 JanetStruct proto = janet_optstruct(argv, argc, 0, NULL);
213 if (!(argc & 1))
214 janet_panic("expected odd number of arguments");
215 JanetKV *st = janet_struct_begin(argc / 2);
216 for (int32_t i = 1; i < argc; i += 2) {
217 janet_struct_put(st, argv[i], argv[i + 1]);
218 }
219 janet_struct_proto(st) = proto;
220 return janet_wrap_struct(janet_struct_end(st));
221 }
222
223 JANET_CORE_FN(cfun_struct_getproto,
224 "(struct/getproto st)",
225 "Return the prototype of a struct, or nil if it doesn't have one.") {
226 janet_fixarity(argc, 1);
227 JanetStruct st = janet_getstruct(argv, 0);
228 return janet_struct_proto(st)
229 ? janet_wrap_struct(janet_struct_proto(st))
230 : janet_wrap_nil();
231 }
232
233 JANET_CORE_FN(cfun_struct_flatten,
234 "(struct/proto-flatten st)",
235 "Convert a struct with prototypes to a struct with no prototypes by merging "
236 "all key value pairs from recursive prototypes into one new struct.") {
237 janet_fixarity(argc, 1);
238 JanetStruct st = janet_getstruct(argv, 0);
239
240 /* get an upper bounds on the number of items in the final struct */
241 int64_t pair_count = 0;
242 JanetStruct cursor = st;
243 while (cursor) {
244 pair_count += janet_struct_length(cursor);
245 cursor = janet_struct_proto(cursor);
246 }
247
248 if (pair_count > INT32_MAX) {
249 janet_panic("struct too large");
250 }
251
252 JanetKV *accum = janet_struct_begin((int32_t) pair_count);
253 cursor = st;
254 while (cursor) {
255 for (int32_t i = 0; i < janet_struct_capacity(cursor); i++) {
256 const JanetKV *kv = cursor + i;
257 if (!janet_checktype(kv->key, JANET_NIL)) {
258 janet_struct_put_ext(accum, kv->key, kv->value, 0);
259 }
260 }
261 cursor = janet_struct_proto(cursor);
262 }
263 return janet_wrap_struct(janet_struct_end(accum));
264 }
265
266 JANET_CORE_FN(cfun_struct_to_table,
267 "(struct/to-table st &opt recursive)",
268 "Convert a struct to a table. If recursive is true, also convert the "
269 "table's prototypes into the new struct's prototypes as well.") {
270 janet_arity(argc, 1, 2);
271 JanetStruct st = janet_getstruct(argv, 0);
272 int recursive = argc > 1 && janet_truthy(argv[1]);
273 JanetTable *tab = NULL;
274 JanetStruct cursor = st;
275 JanetTable *tab_cursor = tab;
276 do {
277 if (tab) {
278 tab_cursor->proto = janet_table(janet_struct_length(cursor));
279 tab_cursor = tab_cursor->proto;
280 } else {
281 tab = janet_table(janet_struct_length(cursor));
282 tab_cursor = tab;
283 }
284 /* TODO - implement as memcpy since struct memory should be compatible
285 * with table memory */
286 for (int32_t i = 0; i < janet_struct_capacity(cursor); i++) {
287 const JanetKV *kv = cursor + i;
288 if (!janet_checktype(kv->key, JANET_NIL)) {
289 janet_table_put(tab_cursor, kv->key, kv->value);
290 }
291 }
292 cursor = janet_struct_proto(cursor);
293 } while (recursive && cursor);
294 return janet_wrap_table(tab);
295 }
296
297 /* Load the struct module */
janet_lib_struct(JanetTable * env)298 void janet_lib_struct(JanetTable *env) {
299 JanetRegExt struct_cfuns[] = {
300 JANET_CORE_REG("struct/with-proto", cfun_struct_with_proto),
301 JANET_CORE_REG("struct/getproto", cfun_struct_getproto),
302 JANET_CORE_REG("struct/proto-flatten", cfun_struct_flatten),
303 JANET_CORE_REG("struct/to-table", cfun_struct_to_table),
304 JANET_REG_END
305 };
306 janet_core_cfuns_ext(env, NULL, struct_cfuns);
307 }
308