1#include "include/pw.h"
2#include "src/pw_alloc.h"
3#include "src/types/map_internal.h"
4
5/****************************************************************
6 * Basic map operations
7 */
8
9static inline unsigned get_map_length(_PwMap* map)
10{
11 return _pw_array_length(&map->kv_pairs) >> 1;
12}
13
14static inline unsigned lookup(_PwMap* map, PwValuePtr key, unsigned* ht_index)
15{
16 return _pw_ht_lookup(&map->hash_table, key, &map->kv_pairs, 2, ht_index);
17}
18
19static _PwMap* _pw_map_copy_on_write(PwValuePtr value, _PwMap* map)
20{
21 _PwStructData* sdata = (_PwStructData*) value->struct_data;
22 if (_pw_atomic_load(&sdata->refcount) <= 1) {
23 // okay to modify in-place
24 return map;
25 }
26 // make a copy
27 PwValue copy = PW_NULL;
28 if (!pw_deepcopy(©, value)) {
29 return nullptr;
30 }
31 // replace value with the copy
32 pw_destroy(value);
33 pw_move(value, ©);
34 return get_map(value);
35}
36
37static _PwMap* _pw_map_noiter_cow(PwValuePtr map)
38{
39 if (pw_iteration_in_progress(map)) {
40 return nullptr;
41 }
42 _PwMap* m = get_map(map);
43 if (_pw_array_is_immutable(&m->kv_pairs)) {
44 m = _pw_map_copy_on_write(map, m);
45 }
46 return m;
47}
48
49static _PwMap* _pw_map_noiter_cow2(PwValuePtr map, PwValuePtr key, PwValuePtr value)
50{
51 if (!pw_is_immutable(key)) {
52 pw_set_status(PwStatus(PweImmutableRequired));
53 return nullptr;
54 }
55 if (pw_iteration_in_progress(map)) {
56 return nullptr;
57 }
58 _PwMap* m = get_map(map);
59 if (_pw_array_is_immutable(&m->kv_pairs)) {
60 if (!pw_is_immutable(value)) {
61 pw_set_status(PwStatus(PweImmutableRequired));
62 return nullptr;
63 }
64 m = _pw_map_copy_on_write(map, m);
65 }
66 return m;
67}
68
69[[nodiscard]] static bool update_map(PwValuePtr self, _PwMap* map, PwValuePtr key, PwValuePtr value)
70{
71 // lookup key in the map
72
73 unsigned item_index = lookup(map, key, nullptr);
74
75 if (item_index != UINT_MAX) {
76 // found key, update value
77 unsigned value_index = (item_index << 1) + 1;
78 _pw_array_replace_item(self, &map->kv_pairs, value_index, value);
79 return true;
80 }
81
82 // key not found, append key and value
83
84 if (!_pw_ht_expand(&map->hash_table, self->type_id, &map->kv_pairs, 2)) {
85 return false;
86 }
87 item_index = _pw_array_length(&map->kv_pairs) >> 1;
88 _pw_ht_set_item(&map->hash_table, pw_hash(key), item_index);
89
90 if (!_pw_array_append_item(self, &map->kv_pairs, key)) {
91 return false;
92 }
93 return _pw_array_append_item(self, &map->kv_pairs, value);
94}
95
96/****************************************************************
97 * Basic interface
98 */
99
100static void map_fini(PwValuePtr self, _PwMap* map, _PwCompoundChain* tail)
101{
102 _pw_destroy_array(self, &map->kv_pairs, tail);
103
104 _PwHashTable* ht = &map->hash_table;
105 _pw_ht_free(self->type_id, ht);
106}
107
108static bool map_create(PwMethod_Basic_create* mthis, PwValuePtr result, PwCtorArgs* ctor_args)
109{
110 if (!pw_super(mthis, result, ctor_args)) {
111 return false;
112 }
113
114 PwMapCtorArgs* args = pw_this_ctor_args();
115 if (!args) {
116 // try Map type id as an alias
117 args = pw_get_ctor_args(PwTypeId_Map, ctor_args);
118 }
119 unsigned capacity = PWMAP_INITIAL_CAPACITY;
120 if (args && args->capacity) {
121 capacity = args->capacity;
122 if (capacity <= PWMAP_INITIAL_CAPACITY) {
123 capacity = PWMAP_INITIAL_CAPACITY;
124 } else if (capacity > (1 << (UINT_WIDTH - 2))) {
125 if (!pw_super_call(destroy, mthis, result, nullptr)) { /* no op */ }
126 pw_set_status(PwStatus(PweDataSizeTooBig));
127 return false;
128 }
129 }
130 _PwMap* map = pw_this_data(result);
131 if (_pw_alloc_array(result->type_id, &map->kv_pairs, capacity * 2)) {
132 if (_pw_ht_rebuild(result->type_id, &map->hash_table, &map->kv_pairs, 2)) {
133 return true;
134 }
135 }
136 map_fini(result, map, nullptr);
137
138 if (!pw_super_call(destroy, mthis, result, nullptr)) { /* no op */ }
139 return false;
140}
141
142static bool map_destroy(PwMethod_Basic_destroy* mthis, PwValuePtr self, _PwCompoundChain* tail)
143{
144 PwValuePtr value_seen = _pw_on_chain(self, tail);
145 if (value_seen) {
146 return true;
147 }
148 map_fini(self, pw_this_data(self), tail);
149 return pw_super(mthis, self, tail);
150}
151
152static bool map_is_immutable(PwMethod_Basic_is_immutable* mthis, PwValuePtr self)
153{
154 _PwMap* map = pw_this_data(self);
155 return _pw_array_is_immutable(&map->kv_pairs);
156}
157
158static bool map_hash(PwMethod_Basic_hash* mthis, PwValuePtr self, PwHashContext* ctx, _PwCompoundChain* tail)
159{
160 if (_pw_on_chain(self, tail)) {
161 return true;
162 }
163 _PwMap* map = pw_this_data(self);
164 _pw_hash_uint64(ctx, PwTypeId_BasicMap);
165
166 _PwCompoundChain cc_link = {
167 .prev = tail,
168 .value = self
169 };
170 _pw_array_hash(&map->kv_pairs, ctx, &cc_link);
171 return true;
172}
173
174static bool map_deepcopy(PwMethod_Basic_deepcopy* mthis, PwValuePtr self, PwValuePtr result, _PwCompoundChain* tail)
175{
176 if (_pw_on_chain(self, tail)) {
177 pw_set_status(PwStatus(PweNotImplemented, "Cannot copy circularly referenced data"));
178 return false;
179 }
180 _PwMap* src_map = pw_this_data(self);
181
182 PwMapCtorArgs args = {
183 .type_id = PwTypeId_BasicMap,
184 .capacity = get_map_length(src_map)
185 };
186 if (!pw_create2(self->type_id, &args, result)) {
187 return false;
188 }
189 _PwMap* dest_map = pw_this_data(result); // this is okay because result type is the same as self
190
191 pw_hard_assert(dest_map->kv_pairs.capacity >= src_map->kv_pairs.length);
192
193 if (!_pw_array_deepcopy(&src_map->kv_pairs, &dest_map->kv_pairs, result)) {
194 goto failed;
195 }
196 if (!_pw_ht_rebuild(result->type_id, &dest_map->hash_table, &dest_map->kv_pairs, 2)) {
197 goto failed;
198 }
199 return true;
200
201failed:
202 pw_destroy(result);
203 return false;
204}
205
206static bool map_dump(PwMethod_Basic_dump* mthis, PwValuePtr self, FILE* fp, int indent, _PwCompoundChain* tail)
207{
208 if (!pw_super(mthis, self, fp, indent, tail)) {
209 return false;
210 }
211
212 _PwCompoundChain cc_link = {
213 .prev = tail,
214 .value = self
215 };
216
217 _PwMap* map = pw_this_data(self);
218 _pw_print_indent(fp, indent + 4);
219 fprintf(fp, "Map: %u items, array length/capacity=%u/%u%s\n",
220 get_map_length(map), _pw_array_length(&map->kv_pairs), _pw_array_capacity(&map->kv_pairs),
221 _pw_array_is_immutable(&map->kv_pairs)? ", immutable" : "");
222
223 PwValuePtr item = _pw_array_items_ptr(&map->kv_pairs, 0);
224 PwValuePtr end = item + _pw_array_length(&map->kv_pairs);
225 while (item < end) {
226
227 PwValuePtr key = item++;
228 PwValuePtr value = item++;
229
230 _pw_print_indent(fp, indent + 8);
231 fputs("Key:\n", fp);
232 if (!_pw_call_dump(fp, key, indent + 12, &cc_link)) {
233 return false;
234 }
235
236 _pw_print_indent(fp, indent + 8);
237 fputs("Value:\n", fp);
238 if (!_pw_call_dump(fp, value, indent + 12, &cc_link)) {
239 return false;
240 }
241 }
242
243 _pw_print_indent(fp, indent);
244
245 _PwHashTable* ht = &map->hash_table;
246 fprintf(fp, "hash table item size %u, capacity=%u (bitmask %llx)\n",
247 ht->item_size, ht->capacity, (unsigned long long) ht->hash_bitmask);
248
249 unsigned hex_width = ht->item_size;
250 unsigned dec_width;
251 switch (ht->item_size) {
252 case 1: dec_width = 3; break;
253 case 2: dec_width = 5; break;
254 case 3: dec_width = 8; break;
255 case 4: dec_width = 10; break;
256 case 5: dec_width = 13; break;
257 case 6: dec_width = 15; break;
258 case 7: dec_width = 17; break;
259 default: dec_width = 20; break;
260 }
261 char fmt[64];
262 snprintf(fmt, sizeof(fmt), "%%%ux: %%-%uu", hex_width, dec_width);
263 unsigned line_len = 0;
264 _pw_print_indent(fp, indent);
265 for (unsigned i = 0; i < ht->capacity; i++ ) {
266 unsigned item_index = ht->get_item(ht, i);
267 fprintf(fp, fmt, i, item_index);
268 line_len += dec_width + hex_width + 4;
269 if (line_len < 80) {
270 fputs(" ", fp);
271 } else {
272 fputc('\n', fp);
273 line_len = 0;
274 _pw_print_indent(fp, indent);
275 }
276 }
277 if (line_len) {
278 fputc('\n', fp);
279 }
280 return true;
281}
282
283static bool map_to_string(PwMethod_Basic_to_string* mthis, PwValuePtr self, PwValuePtr result, _PwCompoundChain* tail)
284{
285 pw_set_status(PwStatus(PweNotImplemented));
286 return false;
287}
288
289static bool map_is_true(PwMethod_Basic_is_true* mthis, PwValuePtr self, _PwCompoundChain* tail)
290{
291 return get_map_length(pw_this_data(self));
292}
293
294static bool map_equal(PwMethod_Basic_equal* mthis, PwValuePtr self, PwValuePtr other, _PwCompoundChain* tail)
295{
296 _PwMap* m1 = pw_this_data(self);
297 _PwMap* m2 = _pw_get_struct_ptr(other, PwTypeId_BasicMap);
298 if (!m2) {
299 return false;
300 }
301 if (_pw_on_chain(self, tail)) {
302 // equality criteria for circularly referenced data is undefined
303 return false;
304 }
305 return _pw_array_eq(self, &m1->kv_pairs, &m2->kv_pairs, tail);
306}
307
308static bool map_iter_children(PwMethod_Basic_iter_children* mthis, PwValuePtr self,
309 _PwCompoundChain* tail, PwCallback_OnChild on_child, void* udata)
310{
311 _PwMap* map = pw_this_data(self);
312 _pw_array_iter_children(self, &map->kv_pairs, tail, on_child, udata);
313 return true;
314}
315
316// inherited methods
317#define map_clone nullptr
318#define map_decref nullptr
319
320
321PwInterface_Basic _pw_basic_map_basic_interface = {
322#define X(name, ...) .name = { .func = map_##name } __VA_OPT__(,)
323 PW_BASIC_INTERFACE_METHODS
324#undef X
325};
326
327/****************************************************************
328 * implementation of common map functions
329 */
330
331[[nodiscard]] static bool __map_get(PwValuePtr self, _PwMap* map, PwValuePtr key, PwValuePtr result)
332{
333 // lookup key in the map
334 unsigned item_index = lookup(map, key, nullptr);
335
336 if (item_index == UINT_MAX) {
337 // key not found
338 pw_set_status(PwStatus(PweKeyNotFound));
339 return false;
340 }
341 // return value
342 unsigned value_index = (item_index << 1) + 1;
343 pw_clone2(result, _pw_array_items_ptr(&map->kv_pairs, value_index));
344 return true;
345}
346
347[[nodiscard]] static bool __map_del(PwValuePtr self, _PwMap* map, PwValuePtr key)
348{
349 // lookup key in the map
350 unsigned ht_index;
351 unsigned item_index = lookup(map, key, &ht_index);
352 if (item_index == UINT_MAX) {
353 // key not found
354 pw_set_status(PwStatus(PweKeyNotFound));
355 return false;
356 }
357
358 _PwHashTable* ht = &map->hash_table;
359
360 // delete key-value pair
361 unsigned kv_index = item_index << 1;
362 bool is_last_pair = kv_index + 2 == _pw_array_length(&map->kv_pairs);
363 if (!_pw_array_del(self, &map->kv_pairs, kv_index, kv_index + 2)) {
364 return false;
365 }
366
367 // delete item from hash table
368 bool adjust = !is_last_pair;
369 _pw_ht_delete_item(ht, ht_index, item_index, adjust);
370 return true;
371}
372
373/****************************************************************
374 * RandomAccess interface
375 */
376
377static bool ra_map_length(PwMethod_RandomAccess_length* mthis, PwValuePtr self, unsigned* result)
378{
379 *result = get_map_length(pw_this_data(self));
380 return true;
381}
382
383static bool ra_map_get_item(PwMethod_RandomAccess_get_item* mthis, PwValuePtr self, PwValuePtr key, PwValuePtr result)
384{
385 return __map_get(self, pw_this_data(self), key, result);
386}
387
388static bool ra_map_get_item_s(PwMethod_RandomAccess_get_item_s* mthis, PwValuePtr self, ssize_t key, PwValuePtr result)
389{
390 PwValue k = PW_SIGNED(key);
391 return __map_get(self, pw_this_data(self), &k, result);
392}
393
394static bool ra_map_get_item_u(PwMethod_RandomAccess_get_item_u* mthis, PwValuePtr self, unsigned key, PwValuePtr result)
395{
396 PwValue k = PW_UNSIGNED(key);
397 return __map_get(self, pw_this_data(self), &k, result);
398}
399
400static bool ra_map_set_item(PwMethod_RandomAccess_set_item* mthis, PwValuePtr self, PwValuePtr key, PwValuePtr value)
401{
402 _PwMap* map = _pw_map_noiter_cow2(self, key, value);
403 if (!map) {
404 return false;
405 }
406 return update_map(self, map, key, value);
407}
408
409static bool ra_map_set_item_s(PwMethod_RandomAccess_set_item_s* mthis, PwValuePtr self, ssize_t key, PwValuePtr value)
410{
411 PwValue k = PW_SIGNED(key);
412
413 _PwMap* map = _pw_map_noiter_cow2(self, &k, value);
414 if (!map) {
415 return false;
416 }
417 return update_map(self, map, &k, value);
418}
419
420static bool ra_map_set_item_u(PwMethod_RandomAccess_set_item_u* mthis, PwValuePtr self, unsigned key, PwValuePtr value)
421{
422 PwValue k = PW_UNSIGNED(key);
423
424 _PwMap* map = _pw_map_noiter_cow2(self, &k, value);
425 if (!map) {
426 return false;
427 }
428 return update_map(self, map, &k, value);
429}
430
431static bool ra_map_delete_item(PwMethod_RandomAccess_delete_item* mthis, PwValuePtr self, PwValuePtr key)
432{
433 _PwMap* map = _pw_map_noiter_cow(self);
434 if (!map) {
435 return false;
436 }
437 return __map_del(self, map, key);
438}
439
440static bool ra_map_delete_item_s(PwMethod_RandomAccess_delete_item_s* mthis, PwValuePtr self, ssize_t key)
441{
442 _PwMap* map = _pw_map_noiter_cow(self);
443 if (!map) {
444 return false;
445 }
446 PwValue k = PW_SIGNED(key);
447 return __map_del(self, map, &k);
448}
449
450static bool ra_map_delete_item_u(PwMethod_RandomAccess_delete_item_u* mthis, PwValuePtr self, unsigned key)
451{
452 _PwMap* map = _pw_map_noiter_cow(self);
453 if (!map) {
454 return false;
455 }
456 PwValue k = PW_UNSIGNED(key);
457 return __map_del(self, map, &k);
458}
459
460static bool ra_map_pop_item(PwMethod_RandomAccess_pop_item* mthis, PwValuePtr self, PwValuePtr result)
461{
462 pw_set_status(PwStatus(PweNotImplemented, "pop_item method is not implemented for BasicMap"));
463 return false;
464}
465
466PwInterface_RandomAccess _pw_basic_map_random_access_interface = {
467#define X(name, ...) .name = { .func = ra_map_##name } __VA_OPT__(,)
468 PW_RANDOM_ACCESS_INTERFACE_METHODS
469#undef X
470};
471
472/****************************************************************
473 * map functions
474 */
475
476[[nodiscard]] bool _pw_map_va(uint16_t result_type, PwValuePtr result, ...)
477{
478 va_list ap;
479 va_start(ap);
480 if (!pw_create(result_type, result)) {
481 _pw_destroy_args(ap);
482 va_end(ap);
483 return false;
484 }
485 bool ret = pw_map_update_ap(result, ap);
486 va_end(ap);
487 return ret;
488}
489
490[[nodiscard]] bool _pw_map_get(PwValuePtr self, PwValuePtr key, PwValuePtr result)
491{
492 _PwMap* map = get_map(self);
493 if (!map) {
494 return false;
495 }
496 return __map_get(self, map, key, result);
497}
498
499[[nodiscard]] bool pw_map_update(PwValuePtr self, PwValuePtr key, PwValuePtr value)
500{
501 _PwMap* map = _pw_map_noiter_cow2(self, key, value);
502 if (!map) {
503 return false;
504 }
505 return update_map(self, map, key, value);
506}
507
508[[nodiscard]] bool _pw_map_update_va(PwValuePtr self, ...)
509{
510 va_list ap;
511 va_start(ap);
512 bool ret = pw_map_update_ap(self, ap);
513 va_end(ap);
514 return ret;
515}
516
517[[nodiscard]] bool pw_map_update_ap(PwValuePtr self, va_list ap)
518{
519 _PwMap* map = _pw_map_noiter_cow(self);
520 if (!map) {
521 return false;
522 }
523 bool done = false; // for special case when value is missing
524 while (!done) {
525 PwValue key = va_arg(ap, _PwValue);
526 if (pw_is_status(&key)) {
527 if (pw_is_va_end(&key)) {
528 return true;
529 }
530 pw_set_status(pw_clone(&key)); // clone because key will be destroyed on context exit
531 goto failure;
532 }
533 if (!pw_is_immutable(&key)) {
534 pw_set_status(PwStatus(PweImmutableRequired));
535 goto failure;
536 }
537 PwValue value = va_arg(ap, _PwValue);
538 if (pw_is_status(&value)) {
539 if (pw_is_va_end(&value)) {
540 pw_destroy(&value);
541 value = PwNull();
542 done = true;
543 } else {
544 pw_set_status(pw_clone(&value)); // clone because value will be destroyed on context exit
545 goto failure;
546 }
547 }
548 if (_pw_array_is_immutable(&map->kv_pairs)) {
549 if (!pw_is_immutable(&value)) {
550 pw_set_status(PwStatus(PweImmutableRequired));
551 goto failure;
552 }
553 }
554 if (!update_map(self, map, &key, &value)) {
555 goto failure;
556 }
557 // key and value are cloned when added to the internal array
558 pw_destroy(&key);
559 pw_destroy(&value);
560 }
561
562failure:
563 // consume args
564 if (!done) {
565 _pw_destroy_args(ap);
566 }
567 return false;
568}
569
570[[nodiscard]] bool _pw_map_del(PwValuePtr self, PwValuePtr key)
571{
572 _PwMap* map = _pw_map_noiter_cow(self);
573 if (!map) {
574 return false;
575 }
576 return __map_del(self, map, key);
577}
578
579unsigned pw_map_length(PwValuePtr self)
580{
581 _PwMap* map = get_map(self);
582 if (!map) {
583 return false;
584 }
585 return get_map_length(map);
586}
587
588[[nodiscard]] bool _pw_map_has_key(PwValuePtr self, PwValuePtr key)
589// XXX make this a part of map interface?
590{
591 _PwMap* map = get_map(self);
592 if (!map) {
593 return false;
594 }
595 return lookup(map, key, nullptr) != UINT_MAX;
596}
597
598[[nodiscard]] bool pw_map_item(PwValuePtr self, unsigned index, PwValuePtr key, PwValuePtr value)
599// XXX make this a part of map interface?
600{
601 _PwMap* map = get_map(self);
602 if (!map) {
603 return false;
604 }
605 index <<= 1;
606 if (index < _pw_array_length(&map->kv_pairs)) {
607 PwValuePtr kv_ptr = _pw_array_items_ptr(&map->kv_pairs, index);
608 pw_clone2(key, kv_ptr++);
609 pw_clone2(value, kv_ptr);
610 return true;
611 }
612 pw_set_status(PwStatus(PweIndexOutOfRange));
613 return false;
614}