1#include "include/pw.h"
2#include "src/pw_alloc.h"
3#include "src/types/set_internal.h"
4
5/****************************************************************
6 * Basic set operations
7 */
8
9static inline unsigned lookup(_PwSet* set, PwValuePtr item, unsigned* ht_index)
10{
11 return _pw_ht_lookup(&set->hash_table, item, &set->items, 1, ht_index);
12}
13
14static _PwSet* _pw_set_copy_on_write(PwValuePtr value, _PwSet* set)
15{
16 _PwStructData* sdata = (_PwStructData*) value->struct_data;
17 if (_pw_atomic_load(&sdata->refcount) <= 1) {
18 // okay to modify in-place
19 return set;
20 }
21 // make a copy
22 PwValue copy = PW_NULL;
23 if (!pw_deepcopy(©, value)) {
24 return nullptr;
25 }
26 // replace value with the copy
27 pw_destroy(value);
28 pw_move(value, ©);
29 return get_set(value);
30}
31
32static _PwSet* _pw_set_noiter_cow(PwValuePtr set)
33{
34 if (pw_iteration_in_progress(set)) {
35 return nullptr;
36 }
37 _PwSet* s = get_set(set);
38 if (_pw_array_is_immutable(&s->items)) {
39 s = _pw_set_copy_on_write(set, s);
40 }
41 return s;
42}
43
44static _PwSet* _pw_set_noiter_cow2(PwValuePtr set, PwValuePtr value)
45{
46 if (pw_iteration_in_progress(set)) {
47 return nullptr;
48 }
49 _PwSet* s = get_set(set);
50 if (_pw_array_is_immutable(&s->items)) {
51 if (!pw_is_immutable(value)) {
52 pw_set_status(PwStatus(PweImmutableRequired));
53 return nullptr;
54 }
55 s = _pw_set_copy_on_write(set, s);
56 }
57 return s;
58}
59
60[[nodiscard]] static bool update_set(PwValuePtr self, _PwSet* set, PwValuePtr value)
61{
62 // lookup value in the set
63
64 if (lookup(set, value, nullptr) != UINT_MAX) {
65 // found item
66 return true;
67 }
68
69 // item not found, append
70
71 if (!_pw_ht_expand(&set->hash_table, self->type_id, &set->items, 1)) {
72 return false;
73 }
74 unsigned item_index = _pw_array_length(&set->items);
75 _pw_ht_set_item(&set->hash_table, pw_hash(value), item_index);
76
77 return _pw_array_append_item(self, &set->items, value);
78}
79
80/****************************************************************
81 * Basic interface
82 */
83
84static void set_fini(PwValuePtr self, _PwSet* set, _PwCompoundChain* tail)
85{
86 _pw_destroy_array(self, &set->items, tail);
87
88 _PwHashTable* ht = &set->hash_table;
89 _pw_ht_free(self->type_id, ht);
90}
91
92static bool set_create(PwMethod_Basic_create* mthis, PwValuePtr result, PwCtorArgs* ctor_args)
93{
94 if (!pw_super(mthis, result, ctor_args)) {
95 return false;
96 }
97
98 PwSetCtorArgs* args = pw_this_ctor_args();
99 if (!args) {
100 // try set type id as an alias
101 args = pw_get_ctor_args(PwTypeId_Set, ctor_args);
102 }
103 unsigned capacity = PWSET_INITIAL_CAPACITY;
104 if (args && args->capacity) {
105 capacity = args->capacity;
106 if (capacity <= PWSET_INITIAL_CAPACITY) {
107 capacity = PWSET_INITIAL_CAPACITY;
108 } else if (capacity > (1 << (UINT_WIDTH - 2))) {
109 if (!pw_super_call(destroy, mthis, result, nullptr)) { /* no op */ }
110 pw_set_status(PwStatus(PweDataSizeTooBig));
111 return false;
112 }
113 }
114 _PwSet* set = pw_this_data(result);
115 if (_pw_alloc_array(result->type_id, &set->items, capacity)) {
116 if (_pw_ht_rebuild(result->type_id, &set->hash_table, &set->items, 1)) {
117 return true;
118 }
119 }
120 set_fini(result, set, nullptr);
121
122 if (!pw_super_call(destroy, mthis, result, nullptr)) { /* no op */ }
123 return false;
124}
125
126static bool set_destroy(PwMethod_Basic_destroy* mthis, PwValuePtr self, _PwCompoundChain* tail)
127{
128 PwValuePtr value_seen = _pw_on_chain(self, tail);
129 if (value_seen) {
130 return true;
131 }
132 set_fini(self, pw_this_data(self), tail);
133 return pw_super(mthis, self, tail);
134}
135
136static bool set_is_immutable(PwMethod_Basic_is_immutable* mthis, PwValuePtr self)
137{
138 _PwSet* set = pw_this_data(self);
139 return _pw_array_is_immutable(&set->items);
140}
141
142static bool set_hash(PwMethod_Basic_hash* mthis, PwValuePtr self, PwHashContext* ctx, _PwCompoundChain* tail)
143{
144 if (_pw_on_chain(self, tail)) {
145 return true;
146 }
147 _PwSet* set = pw_this_data(self);
148 _pw_hash_uint64(ctx, PwTypeId_BasicSet);
149
150 _PwCompoundChain cc_link = {
151 .prev = tail,
152 .value = self
153 };
154 _pw_array_hash(&set->items, ctx, &cc_link);
155 return true;
156}
157
158static bool set_deepcopy(PwMethod_Basic_deepcopy* mthis, PwValuePtr self, PwValuePtr result, _PwCompoundChain* tail)
159{
160 if (_pw_on_chain(self, tail)) {
161 pw_set_status(PwStatus(PweNotImplemented, "Cannot copy circularly referenced data"));
162 return false;
163 }
164 _PwSet* src_set = pw_this_data(self);
165
166 PwSetCtorArgs args = {
167 .type_id = PwTypeId_BasicSet,
168 .capacity = _pw_array_length(&src_set->items)
169 };
170 if (!pw_create2(self->type_id, &args, result)) {
171 return false;
172 }
173 _PwSet* dest_set = pw_this_data(result); // this is okay because result type is the same as self
174
175 pw_hard_assert(dest_set->items.capacity >= src_set->items.length);
176
177 if (!_pw_array_deepcopy(&src_set->items, &dest_set->items, result)) {
178 goto failed;
179 }
180 if (!_pw_ht_rebuild(result->type_id, &dest_set->hash_table, &dest_set->items, 1)) {
181 goto failed;
182 }
183 return true;
184
185failed:
186 pw_destroy(result);
187 return false;
188}
189
190static bool set_dump(PwMethod_Basic_dump* mthis, PwValuePtr self, FILE* fp, int indent, _PwCompoundChain* tail)
191{
192 if (!pw_super(mthis, self, fp, indent, tail)) {
193 return false;
194 }
195
196 _PwCompoundChain cc_link = {
197 .prev = tail,
198 .value = self
199 };
200
201 _PwSet* set = pw_this_data(self);
202 _pw_print_indent(fp, indent + 4);
203 fprintf(fp, "Set: %u items, array capacity=%u%s\n",
204 _pw_array_length(&set->items), _pw_array_capacity(&set->items),
205 _pw_array_is_immutable(&set->items)? ", immutable" : "");
206
207 PwValuePtr item = _pw_array_items_ptr(&set->items, 0);
208 PwValuePtr end = item + _pw_array_length(&set->items);
209 while (item < end) {
210
211 PwValuePtr key = item++;
212 PwValuePtr value = item++;
213
214 _pw_print_indent(fp, indent + 8);
215 fputs("Key:\n", fp);
216 if (!_pw_call_dump(fp, key, indent + 12, &cc_link)) {
217 return false;
218 }
219
220 _pw_print_indent(fp, indent + 8);
221 fputs("Value:\n", fp);
222 if (!_pw_call_dump(fp, value, indent + 12, &cc_link)) {
223 return false;
224 }
225 }
226
227 _pw_print_indent(fp, indent);
228
229 _PwHashTable* ht = &set->hash_table;
230 fprintf(fp, "hash table item size %u, capacity=%u (bitmask %llx)\n",
231 ht->item_size, ht->capacity, (unsigned long long) ht->hash_bitmask);
232
233 unsigned hex_width = ht->item_size;
234 unsigned dec_width;
235 switch (ht->item_size) {
236 case 1: dec_width = 3; break;
237 case 2: dec_width = 5; break;
238 case 3: dec_width = 8; break;
239 case 4: dec_width = 10; break;
240 case 5: dec_width = 13; break;
241 case 6: dec_width = 15; break;
242 case 7: dec_width = 17; break;
243 default: dec_width = 20; break;
244 }
245 char fmt[64];
246 snprintf(fmt, sizeof(fmt), "%%%ux: %%-%uu", hex_width, dec_width);
247 unsigned line_len = 0;
248 _pw_print_indent(fp, indent);
249 for (unsigned i = 0; i < ht->capacity; i++ ) {
250 unsigned item_index = ht->get_item(ht, i);
251 fprintf(fp, fmt, i, item_index);
252 line_len += dec_width + hex_width + 4;
253 if (line_len < 80) {
254 fputs(" ", fp);
255 } else {
256 fputc('\n', fp);
257 line_len = 0;
258 _pw_print_indent(fp, indent);
259 }
260 }
261 if (line_len) {
262 fputc('\n', fp);
263 }
264 return true;
265}
266
267static bool set_to_string(PwMethod_Basic_to_string* mthis, PwValuePtr self, PwValuePtr result, _PwCompoundChain* tail)
268{
269 pw_set_status(PwStatus(PweNotImplemented));
270 return false;
271}
272
273static bool set_is_true(PwMethod_Basic_is_true* mthis, PwValuePtr self, _PwCompoundChain* tail)
274{
275 _PwSet* set = pw_this_data(self);
276 return _pw_array_length(&set->items);
277}
278
279static bool set_equal(PwMethod_Basic_equal* mthis, PwValuePtr self, PwValuePtr other, _PwCompoundChain* tail)
280{
281 _PwSet* s1 = pw_this_data(self);
282 _PwSet* s2 = _pw_get_struct_ptr(other, PwTypeId_BasicSet);
283 if (!s2) {
284 return false;
285 }
286 if (_pw_on_chain(self, tail)) {
287 // equality criteria for circularly referenced data is undefined
288 return false;
289 }
290 return _pw_array_eq(self, &s1->items, &s2->items, tail);
291}
292
293static bool set_iter_children(PwMethod_Basic_iter_children* mthis, PwValuePtr self,
294 _PwCompoundChain* tail, PwCallback_OnChild on_child, void* udata)
295{
296 _PwSet* set = pw_this_data(self);
297 _pw_array_iter_children(self, &set->items, tail, on_child, udata);
298 return true;
299}
300
301// inherited methods
302#define set_clone nullptr
303#define set_decref nullptr
304
305
306PwInterface_Basic _pw_basic_set_basic_interface = {
307#define X(name, ...) .name = { .func = set_##name } __VA_OPT__(,)
308 PW_BASIC_INTERFACE_METHODS
309#undef X
310};
311
312/****************************************************************
313 * implementation of common set functions
314 */
315
316[[nodiscard]] static bool __set_del(PwValuePtr self, _PwSet* set, PwValuePtr value)
317{
318 // lookup key in the set
319 unsigned ht_index;
320 unsigned item_index = lookup(set, value, &ht_index);
321 if (item_index == UINT_MAX) {
322 // key not found
323 pw_set_status(PwStatus(PweKeyNotFound));
324 return false;
325 }
326
327 _PwHashTable* ht = &set->hash_table;
328
329 // delete value
330 bool is_last_item = item_index + 1 == _pw_array_length(&set->items);
331 if (!_pw_array_del(self, &set->items, item_index, item_index + 1)) {
332 return false;
333 }
334
335 // delete item from hash table
336 bool adjust = !is_last_item;
337 _pw_ht_delete_item(ht, ht_index, item_index, adjust);
338 return true;
339}
340
341/****************************************************************
342 * set functions
343 */
344
345[[nodiscard]] bool _pw_set_va(uint16_t result_type, PwValuePtr result, ...)
346{
347 va_list ap;
348 va_start(ap);
349 if (!pw_create(result_type, result)) {
350 _pw_destroy_args(ap);
351 va_end(ap);
352 return false;
353 }
354 bool ret = pw_add_to_set_ap(result, ap);
355 va_end(ap);
356 return ret;
357}
358
359[[nodiscard]] bool pw_add_to_set(PwValuePtr self, PwValuePtr value)
360{
361 _PwSet* set = _pw_set_noiter_cow2(self, value);
362 if (!set) {
363 return false;
364 }
365 return update_set(self, set, value);
366}
367
368[[nodiscard]] bool _pw_add_to_set_va(PwValuePtr self, ...)
369{
370 va_list ap;
371 va_start(ap);
372 bool ret = pw_add_to_set_ap(self, ap);
373 va_end(ap);
374 return ret;
375}
376
377[[nodiscard]] bool pw_add_to_set_ap(PwValuePtr self, va_list ap)
378{
379 _PwSet* set = _pw_set_noiter_cow(self);
380 if (!set) {
381 return false;
382 }
383 for (;;) {
384 PwValue value = va_arg(ap, _PwValue);
385 if (pw_is_status(&value)) {
386 if (pw_is_va_end(&value)) {
387 return true;
388 }
389 pw_set_status(pw_clone(&value));
390 goto failure;
391 }
392 if (_pw_array_is_immutable(&set->items)) {
393 if (!pw_is_immutable(&value)) {
394 pw_set_status(PwStatus(PweImmutableRequired));
395 goto failure;
396 }
397 }
398 if (!update_set(self, set, &value)) {
399 goto failure;
400 }
401 pw_destroy(&value); // the item is cloned when added to the array
402 }
403
404failure:
405 _pw_destroy_args(ap);
406 return false;
407}
408
409[[nodiscard]] bool _pw_del_from_set(PwValuePtr self, PwValuePtr value)
410{
411 _PwSet* set = _pw_set_noiter_cow(self);
412 if (!set) {
413 return false;
414 }
415 return __set_del(self, set, value);
416}
417
418unsigned pw_length_of_set(PwValuePtr self)
419{
420 _PwSet* set = get_set(self);
421 if (!set) {
422 return false;
423 }
424 return _pw_array_length(&set->items);
425}
426
427[[nodiscard]] bool _pw_set_has_item(PwValuePtr self, PwValuePtr value)
428{
429 _PwSet* set = get_set(self);
430 if (!set) {
431 return false;
432 }
433 return lookup(set, value, nullptr) != UINT_MAX;
434}
435
436[[nodiscard]] bool pw_item_of_set(PwValuePtr self, unsigned index, PwValuePtr value)
437{
438 _PwSet* set = get_set(self);
439 if (!set) {
440 return false;
441 }
442 if (index < _pw_array_length(&set->items)) {
443 PwValuePtr item_ptr = _pw_array_items_ptr(&set->items, index);
444 pw_clone2(value, item_ptr);
445 return true;
446 }
447 pw_set_status(PwStatus(PweIndexOutOfRange));
448 return false;
449}