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 #define JANET_TABLE_FLAG_STACK 0x10000
32
janet_memalloc_empty_local(int32_t count)33 static void *janet_memalloc_empty_local(int32_t count) {
34 int32_t i;
35 void *mem = janet_smalloc((size_t) count * sizeof(JanetKV));
36 JanetKV *mmem = (JanetKV *)mem;
37 for (i = 0; i < count; i++) {
38 JanetKV *kv = mmem + i;
39 kv->key = janet_wrap_nil();
40 kv->value = janet_wrap_nil();
41 }
42 return mem;
43 }
44
janet_table_init_impl(JanetTable * table,int32_t capacity,int stackalloc)45 static JanetTable *janet_table_init_impl(JanetTable *table, int32_t capacity, int stackalloc) {
46 JanetKV *data;
47 capacity = janet_tablen(capacity);
48 if (stackalloc) table->gc.flags = JANET_TABLE_FLAG_STACK;
49 if (capacity) {
50 if (stackalloc) {
51 data = janet_memalloc_empty_local(capacity);
52 } else {
53 data = (JanetKV *) janet_memalloc_empty(capacity);
54 if (NULL == data) {
55 JANET_OUT_OF_MEMORY;
56 }
57 }
58 table->data = data;
59 table->capacity = capacity;
60 } else {
61 table->data = NULL;
62 table->capacity = 0;
63 }
64 table->count = 0;
65 table->deleted = 0;
66 table->proto = NULL;
67 return table;
68 }
69
70 /* Initialize a table (for use withs scratch memory) */
janet_table_init(JanetTable * table,int32_t capacity)71 JanetTable *janet_table_init(JanetTable *table, int32_t capacity) {
72 return janet_table_init_impl(table, capacity, 1);
73 }
74
75 /* Initialize a table without using scratch memory */
janet_table_init_raw(JanetTable * table,int32_t capacity)76 JanetTable *janet_table_init_raw(JanetTable *table, int32_t capacity) {
77 return janet_table_init_impl(table, capacity, 0);
78 }
79
80 /* Deinitialize a table */
janet_table_deinit(JanetTable * table)81 void janet_table_deinit(JanetTable *table) {
82 if (table->gc.flags & JANET_TABLE_FLAG_STACK) {
83 janet_sfree(table->data);
84 } else {
85 janet_free(table->data);
86 }
87 }
88
89 /* Create a new table */
janet_table(int32_t capacity)90 JanetTable *janet_table(int32_t capacity) {
91 JanetTable *table = janet_gcalloc(JANET_MEMORY_TABLE, sizeof(JanetTable));
92 return janet_table_init_impl(table, capacity, 0);
93 }
94
95 /* Find the bucket that contains the given key. Will also return
96 * bucket where key should go if not in the table. */
janet_table_find(JanetTable * t,Janet key)97 JanetKV *janet_table_find(JanetTable *t, Janet key) {
98 return (JanetKV *) janet_dict_find(t->data, t->capacity, key);
99 }
100
101 /* Resize the dictionary table. */
janet_table_rehash(JanetTable * t,int32_t size)102 static void janet_table_rehash(JanetTable *t, int32_t size) {
103 JanetKV *olddata = t->data;
104 JanetKV *newdata;
105 int islocal = t->gc.flags & JANET_TABLE_FLAG_STACK;
106 if (islocal) {
107 newdata = (JanetKV *) janet_memalloc_empty_local(size);
108 } else {
109 newdata = (JanetKV *) janet_memalloc_empty(size);
110 if (NULL == newdata) {
111 JANET_OUT_OF_MEMORY;
112 }
113 }
114 int32_t i, oldcapacity;
115 oldcapacity = t->capacity;
116 t->data = newdata;
117 t->capacity = size;
118 t->deleted = 0;
119 for (i = 0; i < oldcapacity; i++) {
120 JanetKV *kv = olddata + i;
121 if (!janet_checktype(kv->key, JANET_NIL)) {
122 JanetKV *newkv = janet_table_find(t, kv->key);
123 *newkv = *kv;
124 }
125 }
126 if (islocal) {
127 janet_sfree(olddata);
128 } else {
129 janet_free(olddata);
130 }
131 }
132
133 /* Get a value out of the table */
janet_table_get(JanetTable * t,Janet key)134 Janet janet_table_get(JanetTable *t, Janet key) {
135 for (int i = JANET_MAX_PROTO_DEPTH; t && i; t = t->proto, --i) {
136 JanetKV *bucket = janet_table_find(t, key);
137 if (NULL != bucket && !janet_checktype(bucket->key, JANET_NIL))
138 return bucket->value;
139 }
140 return janet_wrap_nil();
141 }
142
143 /* Get a value out of the table, and record which prototype it was from. */
janet_table_get_ex(JanetTable * t,Janet key,JanetTable ** which)144 Janet janet_table_get_ex(JanetTable *t, Janet key, JanetTable **which) {
145 for (int i = JANET_MAX_PROTO_DEPTH; t && i; t = t->proto, --i) {
146 JanetKV *bucket = janet_table_find(t, key);
147 if (NULL != bucket && !janet_checktype(bucket->key, JANET_NIL)) {
148 *which = t;
149 return bucket->value;
150 }
151 }
152 return janet_wrap_nil();
153 }
154
155 /* Get a value out of the table. Don't check prototype tables. */
janet_table_rawget(JanetTable * t,Janet key)156 Janet janet_table_rawget(JanetTable *t, Janet key) {
157 JanetKV *bucket = janet_table_find(t, key);
158 if (NULL != bucket && !janet_checktype(bucket->key, JANET_NIL))
159 return bucket->value;
160 else
161 return janet_wrap_nil();
162 }
163
164 /* Remove an entry from the dictionary. Return the value that
165 * was removed. */
janet_table_remove(JanetTable * t,Janet key)166 Janet janet_table_remove(JanetTable *t, Janet key) {
167 JanetKV *bucket = janet_table_find(t, key);
168 if (NULL != bucket && !janet_checktype(bucket->key, JANET_NIL)) {
169 Janet ret = bucket->value;
170 t->count--;
171 t->deleted++;
172 bucket->key = janet_wrap_nil();
173 bucket->value = janet_wrap_false();
174 return ret;
175 } else {
176 return janet_wrap_nil();
177 }
178 }
179
180 /* Put a value into the object */
janet_table_put(JanetTable * t,Janet key,Janet value)181 void janet_table_put(JanetTable *t, Janet key, Janet value) {
182 if (janet_checktype(key, JANET_NIL)) return;
183 if (janet_checktype(key, JANET_NUMBER) && isnan(janet_unwrap_number(key))) return;
184 if (janet_checktype(value, JANET_NIL)) {
185 janet_table_remove(t, key);
186 } else {
187 JanetKV *bucket = janet_table_find(t, key);
188 if (NULL != bucket && !janet_checktype(bucket->key, JANET_NIL)) {
189 bucket->value = value;
190 } else {
191 if (NULL == bucket || 2 * (t->count + t->deleted + 1) > t->capacity) {
192 janet_table_rehash(t, janet_tablen(2 * t->count + 2));
193 }
194 bucket = janet_table_find(t, key);
195 if (janet_checktype(bucket->value, JANET_BOOLEAN))
196 --t->deleted;
197 bucket->key = key;
198 bucket->value = value;
199 ++t->count;
200 }
201 }
202 }
203
204 /* Used internally so don't check arguments
205 * Put into a table, but if the key already exists do nothing. */
janet_table_put_no_overwrite(JanetTable * t,Janet key,Janet value)206 static void janet_table_put_no_overwrite(JanetTable *t, Janet key, Janet value) {
207 JanetKV *bucket = janet_table_find(t, key);
208 if (NULL != bucket && !janet_checktype(bucket->key, JANET_NIL))
209 return;
210 if (NULL == bucket || 2 * (t->count + t->deleted + 1) > t->capacity) {
211 janet_table_rehash(t, janet_tablen(2 * t->count + 2));
212 }
213 bucket = janet_table_find(t, key);
214 if (janet_checktype(bucket->value, JANET_BOOLEAN))
215 --t->deleted;
216 bucket->key = key;
217 bucket->value = value;
218 ++t->count;
219 }
220
221 /* Clear a table */
janet_table_clear(JanetTable * t)222 void janet_table_clear(JanetTable *t) {
223 int32_t capacity = t->capacity;
224 JanetKV *data = t->data;
225 janet_memempty(data, capacity);
226 t->count = 0;
227 t->deleted = 0;
228 }
229
230 /* Clone a table. */
janet_table_clone(JanetTable * table)231 JanetTable *janet_table_clone(JanetTable *table) {
232 JanetTable *newTable = janet_gcalloc(JANET_MEMORY_TABLE, sizeof(JanetTable));
233 newTable->count = table->count;
234 newTable->capacity = table->capacity;
235 newTable->deleted = table->deleted;
236 newTable->proto = table->proto;
237 newTable->data = janet_malloc(newTable->capacity * sizeof(JanetKV));
238 if (NULL == newTable->data) {
239 JANET_OUT_OF_MEMORY;
240 }
241 memcpy(newTable->data, table->data, (size_t) table->capacity * sizeof(JanetKV));
242 return newTable;
243 }
244
245 /* Merge a table or struct into a table */
janet_table_mergekv(JanetTable * table,const JanetKV * kvs,int32_t cap)246 static void janet_table_mergekv(JanetTable *table, const JanetKV *kvs, int32_t cap) {
247 int32_t i;
248 for (i = 0; i < cap; i++) {
249 const JanetKV *kv = kvs + i;
250 if (!janet_checktype(kv->key, JANET_NIL)) {
251 janet_table_put(table, kv->key, kv->value);
252 }
253 }
254 }
255
256 /* Merge a table into another table */
janet_table_merge_table(JanetTable * table,JanetTable * other)257 void janet_table_merge_table(JanetTable *table, JanetTable *other) {
258 janet_table_mergekv(table, other->data, other->capacity);
259 }
260
261 /* Merge a struct into a table */
janet_table_merge_struct(JanetTable * table,const JanetKV * other)262 void janet_table_merge_struct(JanetTable *table, const JanetKV *other) {
263 janet_table_mergekv(table, other, janet_struct_capacity(other));
264 }
265
266 /* Convert table to struct */
janet_table_to_struct(JanetTable * t)267 const JanetKV *janet_table_to_struct(JanetTable *t) {
268 JanetKV *st = janet_struct_begin(t->count);
269 JanetKV *kv = t->data;
270 JanetKV *end = t->data + t->capacity;
271 while (kv < end) {
272 if (!janet_checktype(kv->key, JANET_NIL))
273 janet_struct_put(st, kv->key, kv->value);
274 kv++;
275 }
276 return janet_struct_end(st);
277 }
278
janet_table_proto_flatten(JanetTable * t)279 JanetTable *janet_table_proto_flatten(JanetTable *t) {
280 JanetTable *newTable = janet_table(0);
281 while (t) {
282 JanetKV *kv = t->data;
283 JanetKV *end = t->data + t->capacity;
284 while (kv < end) {
285 if (!janet_checktype(kv->key, JANET_NIL))
286 janet_table_put_no_overwrite(newTable, kv->key, kv->value);
287 kv++;
288 }
289 t = t->proto;
290 }
291 return newTable;
292 }
293
294 /* C Functions */
295
296 JANET_CORE_FN(cfun_table_new,
297 "(table/new capacity)",
298 "Creates a new empty table with pre-allocated memory "
299 "for capacity entries. This means that if one knows the number of "
300 "entries going to go in a table on creation, extra memory allocation "
301 "can be avoided. Returns the new table.") {
302 janet_fixarity(argc, 1);
303 int32_t cap = janet_getinteger(argv, 0);
304 return janet_wrap_table(janet_table(cap));
305 }
306
307 JANET_CORE_FN(cfun_table_getproto,
308 "(table/getproto tab)",
309 "Get the prototype table of a table. Returns nil if a table "
310 "has no prototype, otherwise returns the prototype.") {
311 janet_fixarity(argc, 1);
312 JanetTable *t = janet_gettable(argv, 0);
313 return t->proto
314 ? janet_wrap_table(t->proto)
315 : janet_wrap_nil();
316 }
317
318 JANET_CORE_FN(cfun_table_setproto,
319 "(table/setproto tab proto)",
320 "Set the prototype of a table. Returns the original table tab.") {
321 janet_fixarity(argc, 2);
322 JanetTable *table = janet_gettable(argv, 0);
323 JanetTable *proto = NULL;
324 if (!janet_checktype(argv[1], JANET_NIL)) {
325 proto = janet_gettable(argv, 1);
326 }
327 table->proto = proto;
328 return argv[0];
329 }
330
331 JANET_CORE_FN(cfun_table_tostruct,
332 "(table/to-struct tab)",
333 "Convert a table to a struct. Returns a new struct. This function "
334 "does not take into account prototype tables.") {
335 janet_fixarity(argc, 1);
336 JanetTable *t = janet_gettable(argv, 0);
337 return janet_wrap_struct(janet_table_to_struct(t));
338 }
339
340 JANET_CORE_FN(cfun_table_rawget,
341 "(table/rawget tab key)",
342 "Gets a value from a table without looking at the prototype table. "
343 "If a table tab does not contain t directly, the function will return "
344 "nil without checking the prototype. Returns the value in the table.") {
345 janet_fixarity(argc, 2);
346 JanetTable *table = janet_gettable(argv, 0);
347 return janet_table_rawget(table, argv[1]);
348 }
349
350 JANET_CORE_FN(cfun_table_clone,
351 "(table/clone tab)",
352 "Create a copy of a table. Updates to the new table will not change the old table, "
353 "and vice versa.") {
354 janet_fixarity(argc, 1);
355 JanetTable *table = janet_gettable(argv, 0);
356 return janet_wrap_table(janet_table_clone(table));
357 }
358
359 JANET_CORE_FN(cfun_table_clear,
360 "(table/clear tab)",
361 "Remove all key-value pairs in a table and return the modified table `tab`.") {
362 janet_fixarity(argc, 1);
363 JanetTable *table = janet_gettable(argv, 0);
364 janet_table_clear(table);
365 return janet_wrap_table(table);
366 }
367
368 JANET_CORE_FN(cfun_table_proto_flatten,
369 "(table/proto-flatten tab)",
370 "Create a new table that is the result of merging all prototypes into a new table.") {
371 janet_fixarity(argc, 1);
372 JanetTable *table = janet_gettable(argv, 0);
373 return janet_wrap_table(janet_table_proto_flatten(table));
374 }
375
376 /* Load the table module */
janet_lib_table(JanetTable * env)377 void janet_lib_table(JanetTable *env) {
378 JanetRegExt table_cfuns[] = {
379 JANET_CORE_REG("table/new", cfun_table_new),
380 JANET_CORE_REG("table/to-struct", cfun_table_tostruct),
381 JANET_CORE_REG("table/getproto", cfun_table_getproto),
382 JANET_CORE_REG("table/setproto", cfun_table_setproto),
383 JANET_CORE_REG("table/rawget", cfun_table_rawget),
384 JANET_CORE_REG("table/clone", cfun_table_clone),
385 JANET_CORE_REG("table/clear", cfun_table_clear),
386 JANET_CORE_REG("table/proto-flatten", cfun_table_proto_flatten),
387 JANET_REG_END
388 };
389 janet_core_cfuns_ext(env, NULL, table_cfuns);
390 }
391