Ruby 3.5.0dev (2025-07-01 revision c3bdf7043cca0131e7ca66c1bc76ae6e24dc8965)
set.c (c3bdf7043cca0131e7ca66c1bc76ae6e24dc8965)
1/* This implements sets using the same hash table implementation as in
2 st.c, but without a value for each hash entry. This results in the
3 same basic performance characteristics as when using an st table,
4 but uses 1/3 less memory.
5 */
6
7#include "id.h"
8#include "internal.h"
9#include "internal/bits.h"
10#include "internal/error.h"
11#include "internal/hash.h"
12#include "internal/proc.h"
13#include "internal/sanitizers.h"
14#include "internal/set_table.h"
15#include "internal/symbol.h"
16#include "internal/variable.h"
17#include "ruby_assert.h"
18
19#include <stdio.h>
20#ifdef HAVE_STDLIB_H
21#include <stdlib.h>
22#endif
23#include <string.h>
24
25#ifndef SET_DEBUG
26#define SET_DEBUG 0
27#endif
28
29#if SET_DEBUG
30#include "internal/gc.h"
31#endif
32
33static st_index_t
34dbl_to_index(double d)
35{
36 union {double d; st_index_t i;} u;
37 u.d = d;
38 return u.i;
39}
40
41static const uint64_t prime1 = ((uint64_t)0x2e0bb864 << 32) | 0xe9ea7df5;
42static const uint32_t prime2 = 0x830fcab9;
43
44static inline uint64_t
45mult_and_mix(uint64_t m1, uint64_t m2)
46{
47#if defined HAVE_UINT128_T
48 uint128_t r = (uint128_t) m1 * (uint128_t) m2;
49 return (uint64_t) (r >> 64) ^ (uint64_t) r;
50#else
51 uint64_t hm1 = m1 >> 32, hm2 = m2 >> 32;
52 uint64_t lm1 = m1, lm2 = m2;
53 uint64_t v64_128 = hm1 * hm2;
54 uint64_t v32_96 = hm1 * lm2 + lm1 * hm2;
55 uint64_t v1_32 = lm1 * lm2;
56
57 return (v64_128 + (v32_96 >> 32)) ^ ((v32_96 << 32) + v1_32);
58#endif
59}
60
61static inline uint64_t
62key64_hash(uint64_t key, uint32_t seed)
63{
64 return mult_and_mix(key + seed, prime1);
65}
66
67/* Should cast down the result for each purpose */
68#define set_index_hash(index) key64_hash(rb_hash_start(index), prime2)
69
70static st_index_t
71set_ident_hash(st_data_t n)
72{
73#ifdef USE_FLONUM /* RUBY */
74 /*
75 * - flonum (on 64-bit) is pathologically bad, mix the actual
76 * float value in, but do not use the float value as-is since
77 * many integers get interpreted as 2.0 or -2.0 [Bug #10761]
78 */
79 if (FLONUM_P(n)) {
80 n ^= dbl_to_index(rb_float_value(n));
81 }
82#endif
83
84 return (st_index_t)set_index_hash((st_index_t)n);
85}
86
87static const struct st_hash_type identhash = {
88 rb_st_numcmp,
89 set_ident_hash,
90};
91
92static const struct st_hash_type objhash = {
93 rb_any_cmp,
94 rb_any_hash,
95};
96
97VALUE rb_cSet;
98
99#define id_each idEach
100static ID id_each_entry;
101static ID id_any_p;
102static ID id_new;
103static ID id_i_hash;
104static ID id_set_iter_lev;
105
106#define RSET_INITIALIZED FL_USER1
107#define RSET_LEV_MASK (FL_USER13 | FL_USER14 | FL_USER15 | /* FL 13..19 */ \
108 FL_USER16 | FL_USER17 | FL_USER18 | FL_USER19)
109#define RSET_LEV_SHIFT (FL_USHIFT + 13)
110#define RSET_LEV_MAX 127 /* 7 bits */
111
112#define SET_ASSERT(expr) RUBY_ASSERT_MESG_WHEN(SET_DEBUG, expr, #expr)
113
114#define RSET_SIZE(set) set_table_size(RSET_TABLE(set))
115#define RSET_EMPTY(set) (RSET_SIZE(set) == 0)
116#define RSET_SIZE_NUM(set) SIZET2NUM(RSET_SIZE(set))
117#define RSET_IS_MEMBER(sobj, item) set_lookup(RSET_TABLE(set), (st_data_t)(item))
118#define RSET_COMPARE_BY_IDENTITY(set) (RSET_TABLE(set)->type == &identhash)
119
121 set_table table;
122};
123
124static int
125mark_key(st_data_t key, st_data_t data)
126{
127 rb_gc_mark_movable((VALUE)key);
128
129 return ST_CONTINUE;
130}
131
132static void
133set_mark(void *ptr)
134{
135 struct set_object *sobj = ptr;
136 if (sobj->table.entries) set_foreach(&sobj->table, mark_key, 0);
137}
138
139static void
140set_free_embedded(struct set_object *sobj)
141{
142 free((&sobj->table)->bins);
143 free((&sobj->table)->entries);
144}
145
146static void
147set_free(void *ptr)
148{
149 struct set_object *sobj = ptr;
150 set_free_embedded(sobj);
151 memset(&sobj->table, 0, sizeof(sobj->table));
152}
153
154static size_t
155set_size(const void *ptr)
156{
157 const struct set_object *sobj = ptr;
158 /* Do not count the table size twice, as it is embedded */
159 return (unsigned long)set_memsize(&sobj->table) - sizeof(sobj->table);
160}
161
162static int
163set_foreach_replace(st_data_t key, st_data_t argp, int error)
164{
165 if (rb_gc_location((VALUE)key) != (VALUE)key) {
166 return ST_REPLACE;
167 }
168
169 return ST_CONTINUE;
170}
171
172static int
173set_replace_ref(st_data_t *key, st_data_t argp, int existing)
174{
175 if (rb_gc_location((VALUE)*key) != (VALUE)*key) {
176 *key = rb_gc_location((VALUE)*key);
177 }
178
179 return ST_CONTINUE;
180}
181
182static void
183set_update_references(void *ptr)
184{
185 struct set_object *sobj = ptr;
186 set_foreach_with_replace(&sobj->table, set_foreach_replace, set_replace_ref, 0);
187}
188
189static const rb_data_type_t set_data_type = {
190 .wrap_struct_name = "set",
191 .function = {
192 .dmark = set_mark,
193 .dfree = set_free,
194 .dsize = set_size,
195 .dcompact = set_update_references,
196 },
197 .flags = RUBY_TYPED_EMBEDDABLE | RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_WB_PROTECTED | RUBY_TYPED_FROZEN_SHAREABLE
198};
199
200static inline set_table *
201RSET_TABLE(VALUE set)
202{
203 struct set_object *sobj;
204 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
205 return &sobj->table;
206}
207
208static unsigned long
209iter_lev_in_ivar(VALUE set)
210{
211 VALUE levval = rb_ivar_get(set, id_set_iter_lev);
212 SET_ASSERT(FIXNUM_P(levval));
213 long lev = FIX2LONG(levval);
214 SET_ASSERT(lev >= 0);
215 return (unsigned long)lev;
216}
217
218void rb_ivar_set_internal(VALUE obj, ID id, VALUE val);
219
220static void
221iter_lev_in_ivar_set(VALUE set, unsigned long lev)
222{
223 SET_ASSERT(lev >= RSET_LEV_MAX);
224 SET_ASSERT(POSFIXABLE(lev)); /* POSFIXABLE means fitting to long */
225 rb_ivar_set_internal(set, id_set_iter_lev, LONG2FIX((long)lev));
226}
227
228static inline unsigned long
229iter_lev_in_flags(VALUE set)
230{
231 return (unsigned long)((RBASIC(set)->flags >> RSET_LEV_SHIFT) & RSET_LEV_MAX);
232}
233
234static inline void
235iter_lev_in_flags_set(VALUE set, unsigned long lev)
236{
237 SET_ASSERT(lev <= RSET_LEV_MAX);
238 RBASIC(set)->flags = ((RBASIC(set)->flags & ~RSET_LEV_MASK) | ((VALUE)lev << RSET_LEV_SHIFT));
239}
240
241static inline bool
242set_iterating_p(VALUE set)
243{
244 return iter_lev_in_flags(set) > 0;
245}
246
247static void
248set_iter_lev_inc(VALUE set)
249{
250 unsigned long lev = iter_lev_in_flags(set);
251 if (lev == RSET_LEV_MAX) {
252 lev = iter_lev_in_ivar(set) + 1;
253 if (!POSFIXABLE(lev)) { /* paranoiac check */
254 rb_raise(rb_eRuntimeError, "too much nested iterations");
255 }
256 }
257 else {
258 lev += 1;
259 iter_lev_in_flags_set(set, lev);
260 if (lev < RSET_LEV_MAX) return;
261 }
262 iter_lev_in_ivar_set(set, lev);
263}
264
265static void
266set_iter_lev_dec(VALUE set)
267{
268 unsigned long lev = iter_lev_in_flags(set);
269 if (lev == RSET_LEV_MAX) {
270 lev = iter_lev_in_ivar(set);
271 if (lev > RSET_LEV_MAX) {
272 iter_lev_in_ivar_set(set, lev-1);
273 return;
274 }
275 rb_attr_delete(set, id_set_iter_lev);
276 }
277 else if (lev == 0) {
278 rb_raise(rb_eRuntimeError, "iteration level underflow");
279 }
280 iter_lev_in_flags_set(set, lev - 1);
281}
282
283static VALUE
284set_foreach_ensure(VALUE set)
285{
286 set_iter_lev_dec(set);
287 return 0;
288}
289
290typedef int set_foreach_func(VALUE, VALUE);
291
293 VALUE set;
294 set_foreach_func *func;
295 VALUE arg;
296};
297
298static int
299set_iter_status_check(int status)
300{
301 if (status == ST_CONTINUE) {
302 return ST_CHECK;
303 }
304
305 return status;
306}
307
308static int
309set_foreach_iter(st_data_t key, st_data_t argp, int error)
310{
311 struct set_foreach_arg *arg = (struct set_foreach_arg *)argp;
312
313 if (error) return ST_STOP;
314
315 set_table *tbl = RSET_TABLE(arg->set);
316 int status = (*arg->func)((VALUE)key, arg->arg);
317
318 if (RSET_TABLE(arg->set) != tbl) {
319 rb_raise(rb_eRuntimeError, "reset occurred during iteration");
320 }
321
322 return set_iter_status_check(status);
323}
324
325static VALUE
326set_foreach_call(VALUE arg)
327{
328 VALUE set = ((struct set_foreach_arg *)arg)->set;
329 int ret = 0;
330 ret = set_foreach_check(RSET_TABLE(set), set_foreach_iter,
331 (st_data_t)arg, (st_data_t)Qundef);
332 if (ret) {
333 rb_raise(rb_eRuntimeError, "ret: %d, set modified during iteration", ret);
334 }
335 return Qnil;
336}
337
338static void
339set_iter(VALUE set, set_foreach_func *func, VALUE farg)
340{
341 struct set_foreach_arg arg;
342
343 if (RSET_EMPTY(set))
344 return;
345 arg.set = set;
346 arg.func = func;
347 arg.arg = farg;
348 if (RB_OBJ_FROZEN(set)) {
349 set_foreach_call((VALUE)&arg);
350 }
351 else {
352 set_iter_lev_inc(set);
353 rb_ensure(set_foreach_call, (VALUE)&arg, set_foreach_ensure, set);
354 }
355}
356
357NORETURN(static void no_new_item(void));
358static void
359no_new_item(void)
360{
361 rb_raise(rb_eRuntimeError, "can't add a new item into set during iteration");
362}
363
364static void
365set_compact_after_delete(VALUE set)
366{
367 if (!set_iterating_p(set)) {
368 set_compact_table(RSET_TABLE(set));
369 }
370}
371
372static int
373set_table_insert_wb(set_table *tab, VALUE set, VALUE key, VALUE *key_addr)
374{
375 if (tab->type != &identhash && rb_obj_class(key) == rb_cString && !RB_OBJ_FROZEN(key)) {
376 key = rb_hash_key_str(key);
377 if (key_addr) *key_addr = key;
378 }
379 int ret = set_insert(tab, (st_data_t)key);
380 if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
381 return ret;
382}
383
384static int
385set_insert_wb(VALUE set, VALUE key, VALUE *key_addr)
386{
387 return set_table_insert_wb(RSET_TABLE(set), set, key, key_addr);
388}
389
390static VALUE
391set_alloc_with_size(VALUE klass, st_index_t size)
392{
393 VALUE set;
394 struct set_object *sobj;
395
396 set = TypedData_Make_Struct(klass, struct set_object, &set_data_type, sobj);
397 set_init_table_with_size(&sobj->table, &objhash, size);
398
399 return set;
400}
401
402
403static VALUE
404set_s_alloc(VALUE klass)
405{
406 return set_alloc_with_size(klass, 0);
407}
408
409static VALUE
410set_s_create(int argc, VALUE *argv, VALUE klass)
411{
412 VALUE set = set_alloc_with_size(klass, argc);
413 set_table *table = RSET_TABLE(set);
414 int i;
415
416 for (i=0; i < argc; i++) {
417 set_table_insert_wb(table, set, argv[i], NULL);
418 }
419
420 return set;
421}
422
423static void
424check_set(VALUE arg)
425{
426 if (!rb_obj_is_kind_of(arg, rb_cSet)) {
427 rb_raise(rb_eArgError, "value must be a set");
428 }
429}
430
431static ID
432enum_method_id(VALUE other)
433{
434 if (rb_respond_to(other, id_each_entry)) {
435 return id_each_entry;
436 }
437 else if (rb_respond_to(other, id_each)) {
438 return id_each;
439 }
440 else {
441 rb_raise(rb_eArgError, "value must be enumerable");
442 }
443}
444
445static VALUE
446set_enum_size(VALUE set, VALUE args, VALUE eobj)
447{
448 return RSET_SIZE_NUM(set);
449}
450
451static VALUE
452set_initialize_without_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set))
453{
454 VALUE element = i;
455 set_insert_wb(set, element, &element);
456 return element;
457}
458
459static VALUE
460set_initialize_with_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set))
461{
462 VALUE element = rb_yield(i);
463 set_insert_wb(set, element, &element);
464 return element;
465}
466
467/*
468 * call-seq:
469 * Set.new -> new_set
470 * Set.new(enum) -> new_set
471 * Set.new(enum) { |elem| ... } -> new_set
472 *
473 * Creates a new set containing the elements of the given enumerable
474 * object.
475 *
476 * If a block is given, the elements of enum are preprocessed by the
477 * given block.
478 *
479 * Set.new([1, 2]) #=> #<Set: {1, 2}>
480 * Set.new([1, 2, 1]) #=> #<Set: {1, 2}>
481 * Set.new([1, 'c', :s]) #=> #<Set: {1, "c", :s}>
482 * Set.new(1..5) #=> #<Set: {1, 2, 3, 4, 5}>
483 * Set.new([1, 2, 3]) { |x| x * x } #=> #<Set: {1, 4, 9}>
484 */
485static VALUE
486set_i_initialize(int argc, VALUE *argv, VALUE set)
487{
488 if (RBASIC(set)->flags & RSET_INITIALIZED) {
489 rb_raise(rb_eRuntimeError, "cannot reinitialize set");
490 }
491 RBASIC(set)->flags |= RSET_INITIALIZED;
492
493 VALUE other;
494 rb_check_arity(argc, 0, 1);
495
496 if (argc > 0 && (other = argv[0]) != Qnil) {
497 if (RB_TYPE_P(other, T_ARRAY)) {
498 long i;
499 int block_given = rb_block_given_p();
500 set_table *into = RSET_TABLE(set);
501 for (i=0; i<RARRAY_LEN(other); i++) {
502 VALUE key = RARRAY_AREF(other, i);
503 if (block_given) key = rb_yield(key);
504 set_table_insert_wb(into, set, key, NULL);
505 }
506 }
507 else {
508 rb_block_call(other, enum_method_id(other), 0, 0,
509 rb_block_given_p() ? set_initialize_with_block : set_initialize_without_block,
510 set);
511 }
512 }
513
514 return set;
515}
516
517static VALUE
518set_i_initialize_copy(VALUE set, VALUE other)
519{
520 if (set == other) return set;
521
522 if (set_iterating_p(set)) {
523 rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
524 }
525
526 struct set_object *sobj;
527 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
528
529 set_free_embedded(sobj);
530 set_copy(&sobj->table, RSET_TABLE(other));
531 rb_gc_writebarrier_remember(set);
532
533 return set;
534}
535
536static int
537set_inspect_i(st_data_t key, st_data_t arg)
538{
539 VALUE *args = (VALUE*)arg;
540 VALUE str = args[0];
541 if (args[1] == Qtrue) {
542 rb_str_buf_cat_ascii(str, ", ");
543 }
544 else {
545 args[1] = Qtrue;
546 }
548
549 return ST_CONTINUE;
550}
551
552static VALUE
553set_inspect(VALUE set, VALUE dummy, int recur)
554{
555 VALUE str;
556 VALUE klass_name = rb_class_path(CLASS_OF(set));
557
558 if (recur) {
559 str = rb_sprintf("%"PRIsVALUE"[...]", klass_name);
560 return rb_str_export_to_enc(str, rb_usascii_encoding());
561 }
562
563 str = rb_sprintf("%"PRIsVALUE"[", klass_name);
564 VALUE args[2] = {str, Qfalse};
565 set_iter(set, set_inspect_i, (st_data_t)args);
566 rb_str_buf_cat2(str, "]");
567
568 return str;
569}
570
571/*
572 * call-seq:
573 * inspect -> new_string
574 *
575 * Returns a new string containing the set entries:
576 *
577 * s = Set.new
578 * s.inspect # => "#<Set: {}>"
579 * s.add(1)
580 * s.inspect # => "#<Set: {1}>"
581 * s.add(2)
582 * s.inspect # => "#<Set: {1, 2}>"
583 *
584 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
585 */
586static VALUE
587set_i_inspect(VALUE set)
588{
589 return rb_exec_recursive(set_inspect, set, 0);
590}
591
592static int
593set_to_a_i(st_data_t key, st_data_t arg)
594{
595 rb_ary_push((VALUE)arg, (VALUE)key);
596 return ST_CONTINUE;
597}
598
599/*
600 * call-seq:
601 * to_a -> array
602 *
603 * Returns an array containing all elements in the set.
604 *
605 * Set[1, 2].to_a #=> [1, 2]
606 * Set[1, 'c', :s].to_a #=> [1, "c", :s]
607 */
608static VALUE
609set_i_to_a(VALUE set)
610{
611 st_index_t size = RSET_SIZE(set);
612 VALUE ary = rb_ary_new_capa(size);
613
614 if (size == 0) return ary;
615
616 if (ST_DATA_COMPATIBLE_P(VALUE)) {
617 RARRAY_PTR_USE(ary, ptr, {
618 size = set_keys(RSET_TABLE(set), ptr, size);
619 });
620 rb_gc_writebarrier_remember(ary);
621 rb_ary_set_len(ary, size);
622 }
623 else {
624 set_iter(set, set_to_a_i, (st_data_t)ary);
625 }
626 return ary;
627}
628
629/*
630 * call-seq:
631 * to_set(klass = Set, *args, &block) -> self or new_set
632 *
633 * Returns self if receiver is an instance of +Set+ and no arguments or
634 * block are given. Otherwise, converts the set to another with
635 * <tt>klass.new(self, *args, &block)</tt>.
636 *
637 * In subclasses, returns `klass.new(self, *args, &block)` unless overridden.
638 */
639static VALUE
640set_i_to_set(int argc, VALUE *argv, VALUE set)
641{
642 VALUE klass;
643
644 if (argc == 0) {
645 klass = rb_cSet;
646 argv = &set;
647 argc = 1;
648 }
649 else {
650 rb_warn_deprecated("passing arguments to Set#to_set", NULL);
651 klass = argv[0];
652 argv[0] = set;
653 }
654
655 if (klass == rb_cSet && rb_obj_is_instance_of(set, rb_cSet) &&
656 argc == 1 && !rb_block_given_p()) {
657 return set;
658 }
659
660 return rb_funcall_passing_block(klass, id_new, argc, argv);
661}
662
663/*
664 * call-seq:
665 * join(separator=nil)-> new_string
666 *
667 * Returns a string created by converting each element of the set to a string.
668 */
669static VALUE
670set_i_join(int argc, VALUE *argv, VALUE set)
671{
672 rb_check_arity(argc, 0, 1);
673 return rb_ary_join(set_i_to_a(set), argc == 0 ? Qnil : argv[0]);
674}
675
676/*
677 * call-seq:
678 * add(obj) -> self
679 *
680 * Adds the given object to the set and returns self. Use `merge` to
681 * add many elements at once.
682 *
683 * Set[1, 2].add(3) #=> #<Set: {1, 2, 3}>
684 * Set[1, 2].add([3, 4]) #=> #<Set: {1, 2, [3, 4]}>
685 * Set[1, 2].add(2) #=> #<Set: {1, 2}>
686 */
687static VALUE
688set_i_add(VALUE set, VALUE item)
689{
690 rb_check_frozen(set);
691 if (set_iterating_p(set)) {
692 if (!set_lookup(RSET_TABLE(set), (st_data_t)item)) {
693 no_new_item();
694 }
695 }
696 else {
697 set_insert_wb(set, item, NULL);
698 }
699 return set;
700}
701
702/*
703 * call-seq:
704 * add?(obj) -> self or nil
705 *
706 * Adds the given object to the set and returns self. If the object is
707 * already in the set, returns nil.
708 *
709 * Set[1, 2].add?(3) #=> #<Set: {1, 2, 3}>
710 * Set[1, 2].add?([3, 4]) #=> #<Set: {1, 2, [3, 4]}>
711 * Set[1, 2].add?(2) #=> nil
712 */
713static VALUE
714set_i_add_p(VALUE set, VALUE item)
715{
716 rb_check_frozen(set);
717 if (set_iterating_p(set)) {
718 if (!set_lookup(RSET_TABLE(set), (st_data_t)item)) {
719 no_new_item();
720 }
721 return Qnil;
722 }
723 else {
724 return set_insert_wb(set, item, NULL) ? Qnil : set;
725 }
726}
727
728/*
729 * call-seq:
730 * delete(obj) -> self
731 *
732 * Deletes the given object from the set and returns self. Use subtract
733 * to delete many items at once.
734 */
735static VALUE
736set_i_delete(VALUE set, VALUE item)
737{
738 rb_check_frozen(set);
739 if (set_delete(RSET_TABLE(set), (st_data_t *)&item)) {
740 set_compact_after_delete(set);
741 }
742 return set;
743}
744
745/*
746 * call-seq:
747 * delete?(obj) -> self or nil
748 *
749 * Deletes the given object from the set and returns self. If the
750 * object is not in the set, returns nil.
751 */
752static VALUE
753set_i_delete_p(VALUE set, VALUE item)
754{
755 rb_check_frozen(set);
756 if (set_delete(RSET_TABLE(set), (st_data_t *)&item)) {
757 set_compact_after_delete(set);
758 return set;
759 }
760 return Qnil;
761}
762
763static int
764set_delete_if_i(st_data_t key, st_data_t dummy)
765{
766 return RTEST(rb_yield((VALUE)key)) ? ST_DELETE : ST_CONTINUE;
767}
768
769/*
770 * call-seq:
771 * delete_if { |o| ... } -> self
772 * delete_if -> enumerator
773 *
774 * Deletes every element of the set for which block evaluates to
775 * true, and returns self. Returns an enumerator if no block is given.
776 */
777static VALUE
778set_i_delete_if(VALUE set)
779{
780 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
781 rb_check_frozen(set);
782 set_iter(set, set_delete_if_i, 0);
783 set_compact_after_delete(set);
784 return set;
785}
786
787/*
788 * call-seq:
789 * reject! { |o| ... } -> self
790 * reject! -> enumerator
791 *
792 * Equivalent to Set#delete_if, but returns nil if no changes were made.
793 * Returns an enumerator if no block is given.
794 */
795static VALUE
796set_i_reject(VALUE set)
797{
798 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
799 rb_check_frozen(set);
800
801 set_table *table = RSET_TABLE(set);
802 size_t n = set_table_size(table);
803 set_iter(set, set_delete_if_i, 0);
804
805 if (n == set_table_size(table)) return Qnil;
806
807 set_compact_after_delete(set);
808 return set;
809}
810
811static int
812set_classify_i(st_data_t key, st_data_t tmp)
813{
814 VALUE* args = (VALUE*)tmp;
815 VALUE hash = args[0];
816 VALUE hash_key = rb_yield(key);
817 VALUE set = rb_hash_lookup2(hash, hash_key, Qundef);
818 if (set == Qundef) {
819 set = set_s_alloc(args[1]);
820 rb_hash_aset(hash, hash_key, set);
821 }
822 set_i_add(set, key);
823
824 return ST_CONTINUE;
825}
826
827/*
828 * call-seq:
829 * classify { |o| ... } -> hash
830 * classify -> enumerator
831 *
832 * Classifies the set by the return value of the given block and
833 * returns a hash of {value => set of elements} pairs. The block is
834 * called once for each element of the set, passing the element as
835 * parameter.
836 *
837 * files = Set.new(Dir.glob("*.rb"))
838 * hash = files.classify { |f| File.mtime(f).year }
839 * hash #=> {2000 => #<Set: {"a.rb", "b.rb"}>,
840 * # 2001 => #<Set: {"c.rb", "d.rb", "e.rb"}>,
841 * # 2002 => #<Set: {"f.rb"}>}
842 *
843 * Returns an enumerator if no block is given.
844 */
845static VALUE
846set_i_classify(VALUE set)
847{
848 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
849 VALUE args[2];
850 args[0] = rb_hash_new();
851 args[1] = rb_obj_class(set);
852 set_iter(set, set_classify_i, (st_data_t)args);
853 return args[0];
854}
855
856// Union-find with path compression
857static long
858set_divide_union_find_root(long *uf_parents, long index, long *tmp_array)
859{
860 long root = uf_parents[index];
861 long update_size = 0;
862 while (root != index) {
863 tmp_array[update_size++] = index;
864 index = root;
865 root = uf_parents[index];
866 }
867 for (long j = 0; j < update_size; j++) {
868 long idx = tmp_array[j];
869 uf_parents[idx] = root;
870 }
871 return root;
872}
873
874static void
875set_divide_union_find_merge(long *uf_parents, long i, long j, long *tmp_array)
876{
877 long root_i = set_divide_union_find_root(uf_parents, i, tmp_array);
878 long root_j = set_divide_union_find_root(uf_parents, j, tmp_array);
879 if (root_i != root_j) uf_parents[root_j] = root_i;
880}
881
882static VALUE
883set_divide_arity2(VALUE set)
884{
885 VALUE tmp, uf;
886 long size, *uf_parents, *tmp_array;
887 VALUE set_class = rb_obj_class(set);
888 VALUE items = set_i_to_a(set);
889 rb_ary_freeze(items);
890 size = RARRAY_LEN(items);
891 tmp_array = ALLOCV_N(long, tmp, size);
892 uf_parents = ALLOCV_N(long, uf, size);
893 for (long i = 0; i < size; i++) {
894 uf_parents[i] = i;
895 }
896 for (long i = 0; i < size - 1; i++) {
897 VALUE item1 = RARRAY_AREF(items, i);
898 for (long j = i + 1; j < size; j++) {
899 VALUE item2 = RARRAY_AREF(items, j);
900 if (RTEST(rb_yield_values(2, item1, item2)) &&
901 RTEST(rb_yield_values(2, item2, item1))) {
902 set_divide_union_find_merge(uf_parents, i, j, tmp_array);
903 }
904 }
905 }
906 VALUE final_set = set_s_create(0, 0, rb_cSet);
907 VALUE hash = rb_hash_new();
908 for (long i = 0; i < size; i++) {
909 VALUE v = RARRAY_AREF(items, i);
910 long root = set_divide_union_find_root(uf_parents, i, tmp_array);
911 VALUE set = rb_hash_aref(hash, LONG2FIX(root));
912 if (set == Qnil) {
913 set = set_s_create(0, 0, set_class);
914 rb_hash_aset(hash, LONG2FIX(root), set);
915 set_i_add(final_set, set);
916 }
917 set_i_add(set, v);
918 }
919 ALLOCV_END(tmp);
920 ALLOCV_END(uf);
921 return final_set;
922}
923
924static void set_merge_enum_into(VALUE set, VALUE arg);
925
926/*
927 * call-seq:
928 * divide { |o1, o2| ... } -> set
929 * divide { |o| ... } -> set
930 * divide -> enumerator
931 *
932 * Divides the set into a set of subsets according to the commonality
933 * defined by the given block.
934 *
935 * If the arity of the block is 2, elements o1 and o2 are in common
936 * if both block.call(o1, o2) and block.call(o2, o1) are true.
937 * Otherwise, elements o1 and o2 are in common if
938 * block.call(o1) == block.call(o2).
939 *
940 * numbers = Set[1, 3, 4, 6, 9, 10, 11]
941 * set = numbers.divide { |i,j| (i - j).abs == 1 }
942 * set #=> #<Set: {#<Set: {1}>,
943 * # #<Set: {3, 4}>,
944 * # #<Set: {6}>}>
945 * # #<Set: {9, 10, 11}>,
946 *
947 * Returns an enumerator if no block is given.
948 */
949static VALUE
950set_i_divide(VALUE set)
951{
952 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
953
954 if (rb_block_arity() == 2) {
955 return set_divide_arity2(set);
956 }
957
958 VALUE values = rb_hash_values(set_i_classify(set));
959 set = set_alloc_with_size(rb_cSet, RARRAY_LEN(values));
960 set_merge_enum_into(set, values);
961 return set;
962}
963
964static int
965set_clear_i(st_data_t key, st_data_t dummy)
966{
967 return ST_DELETE;
968}
969
970/*
971 * call-seq:
972 * clear -> self
973 *
974 * Removes all elements and returns self.
975 *
976 * set = Set[1, 'c', :s] #=> #<Set: {1, "c", :s}>
977 * set.clear #=> #<Set: {}>
978 * set #=> #<Set: {}>
979 */
980static VALUE
981set_i_clear(VALUE set)
982{
983 rb_check_frozen(set);
984 if (RSET_SIZE(set) == 0) return set;
985 if (set_iterating_p(set)) {
986 set_iter(set, set_clear_i, 0);
987 }
988 else {
989 set_clear(RSET_TABLE(set));
990 set_compact_after_delete(set);
991 }
992 return set;
993}
994
996 VALUE set;
997 set_table *into;
998 set_table *other;
999};
1000
1001static int
1002set_intersection_i(st_data_t key, st_data_t tmp)
1003{
1004 struct set_intersection_data *data = (struct set_intersection_data *)tmp;
1005 if (set_lookup(data->other, key)) {
1006 set_table_insert_wb(data->into, data->set, key, NULL);
1007 }
1008
1009 return ST_CONTINUE;
1010}
1011
1012static VALUE
1013set_intersection_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, data))
1014{
1015 set_intersection_i((st_data_t)i, (st_data_t)data);
1016 return i;
1017}
1018
1019/*
1020 * call-seq:
1021 * set & enum -> new_set
1022 *
1023 * Returns a new set containing elements common to the set and the given
1024 * enumerable object.
1025 *
1026 * Set[1, 3, 5] & Set[3, 2, 1] #=> #<Set: {3, 1}>
1027 * Set['a', 'b', 'z'] & ['a', 'b', 'c'] #=> #<Set: {"a", "b"}>
1028 */
1029static VALUE
1030set_i_intersection(VALUE set, VALUE other)
1031{
1032 VALUE new_set = set_s_alloc(rb_obj_class(set));
1033 set_table *stable = RSET_TABLE(set);
1034 set_table *ntable = RSET_TABLE(new_set);
1035
1036 if (rb_obj_is_kind_of(other, rb_cSet)) {
1037 set_table *otable = RSET_TABLE(other);
1038 if (set_table_size(stable) >= set_table_size(otable)) {
1039 /* Swap so we iterate over the smaller set */
1040 otable = stable;
1041 set = other;
1042 }
1043
1044 struct set_intersection_data data = {
1045 .set = new_set,
1046 .into = ntable,
1047 .other = otable
1048 };
1049 set_iter(set, set_intersection_i, (st_data_t)&data);
1050 }
1051 else {
1052 struct set_intersection_data data = {
1053 .set = new_set,
1054 .into = ntable,
1055 .other = stable
1056 };
1057 rb_block_call(other, enum_method_id(other), 0, 0, set_intersection_block, (VALUE)&data);
1058 }
1059
1060 return new_set;
1061}
1062
1063/*
1064 * call-seq:
1065 * include?(item) -> true or false
1066 *
1067 * Returns true if the set contains the given object:
1068 *
1069 * Set[1, 2, 3].include? 2 #=> true
1070 * Set[1, 2, 3].include? 4 #=> false
1071 *
1072 * Note that <code>include?</code> and <code>member?</code> do not test member
1073 * equality using <code>==</code> as do other Enumerables.
1074 *
1075 * This is aliased to #===, so it is usable in +case+ expressions:
1076 *
1077 * case :apple
1078 * when Set[:potato, :carrot]
1079 * "vegetable"
1080 * when Set[:apple, :banana]
1081 * "fruit"
1082 * end
1083 * # => "fruit"
1084 *
1085 * See also Enumerable#include?
1086 */
1087static VALUE
1088set_i_include(VALUE set, VALUE item)
1089{
1090 return RBOOL(RSET_IS_MEMBER(set, item));
1091}
1092
1094 VALUE set;
1095 set_table *into;
1096};
1097
1098static int
1099set_merge_i(st_data_t key, st_data_t data)
1100{
1101 struct set_merge_args *args = (struct set_merge_args *)data;
1102 set_table_insert_wb(args->into, args->set, key, NULL);
1103 return ST_CONTINUE;
1104}
1105
1106static VALUE
1107set_merge_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set))
1108{
1109 VALUE element = key;
1110 set_insert_wb(set, element, &element);
1111 return element;
1112}
1113
1114static void
1115set_merge_enum_into(VALUE set, VALUE arg)
1116{
1117 if (rb_obj_is_kind_of(arg, rb_cSet)) {
1118 struct set_merge_args args = {
1119 .set = set,
1120 .into = RSET_TABLE(set)
1121 };
1122 set_iter(arg, set_merge_i, (st_data_t)&args);
1123 }
1124 else if (RB_TYPE_P(arg, T_ARRAY)) {
1125 long i;
1126 set_table *into = RSET_TABLE(set);
1127 for (i=0; i<RARRAY_LEN(arg); i++) {
1128 set_table_insert_wb(into, set, RARRAY_AREF(arg, i), NULL);
1129 }
1130 }
1131 else {
1132 rb_block_call(arg, enum_method_id(arg), 0, 0, set_merge_block, (VALUE)set);
1133 }
1134}
1135
1136/*
1137 * call-seq:
1138 * merge(*enums, **nil) -> self
1139 *
1140 * Merges the elements of the given enumerable objects to the set and
1141 * returns self.
1142 */
1143static VALUE
1144set_i_merge(int argc, VALUE *argv, VALUE set)
1145{
1146 if (rb_keyword_given_p()) {
1147 rb_raise(rb_eArgError, "no keywords accepted");
1148 }
1149
1150 if (set_iterating_p(set)) {
1151 rb_raise(rb_eRuntimeError, "cannot add to set during iteration");
1152 }
1153
1154 rb_check_frozen(set);
1155
1156 int i;
1157
1158 for (i=0; i < argc; i++) {
1159 set_merge_enum_into(set, argv[i]);
1160 }
1161
1162 return set;
1163}
1164
1165static VALUE
1166set_reset_table_with_type(VALUE set, const struct st_hash_type *type)
1167{
1168 rb_check_frozen(set);
1169
1170 struct set_object *sobj;
1171 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
1172 set_table *old = &sobj->table;
1173
1174 size_t size = set_table_size(old);
1175 if (size > 0) {
1176 set_table *new = set_init_table_with_size(NULL, type, size);
1177 struct set_merge_args args = {
1178 .set = set,
1179 .into = new
1180 };
1181 set_iter(set, set_merge_i, (st_data_t)&args);
1182 set_free_embedded(sobj);
1183 memcpy(&sobj->table, new, sizeof(*new));
1184 free(new);
1185 }
1186 else {
1187 sobj->table.type = type;
1188 }
1189
1190 return set;
1191}
1192
1193/*
1194 * call-seq:
1195 * compare_by_identity -> self
1196 *
1197 * Makes the set compare its elements by their identity and returns self.
1198 */
1199static VALUE
1200set_i_compare_by_identity(VALUE set)
1201{
1202 if (RSET_COMPARE_BY_IDENTITY(set)) return set;
1203
1204 if (set_iterating_p(set)) {
1205 rb_raise(rb_eRuntimeError, "compare_by_identity during iteration");
1206 }
1207
1208 return set_reset_table_with_type(set, &identhash);
1209}
1210
1211/*
1212 * call-seq:
1213 * compare_by_identity? -> true or false
1214 *
1215 * Returns true if the set will compare its elements by their
1216 * identity. Also see Set#compare_by_identity.
1217 */
1218static VALUE
1219set_i_compare_by_identity_p(VALUE set)
1220{
1221 return RBOOL(RSET_COMPARE_BY_IDENTITY(set));
1222}
1223
1224/*
1225 * call-seq:
1226 * size -> integer
1227 *
1228 * Returns the number of elements.
1229 */
1230static VALUE
1231set_i_size(VALUE set)
1232{
1233 return RSET_SIZE_NUM(set);
1234}
1235
1236/*
1237 * call-seq:
1238 * empty? -> true or false
1239 *
1240 * Returns true if the set contains no elements.
1241 */
1242static VALUE
1243set_i_empty(VALUE set)
1244{
1245 return RBOOL(RSET_EMPTY(set));
1246}
1247
1248static int
1249set_xor_i(st_data_t key, st_data_t data)
1250{
1251 VALUE element = (VALUE)key;
1252 VALUE set = (VALUE)data;
1253 set_table *table = RSET_TABLE(set);
1254 if (set_table_insert_wb(table, set, element, &element)) {
1255 set_delete(table, &element);
1256 }
1257 return ST_CONTINUE;
1258}
1259
1260/*
1261 * call-seq:
1262 * set ^ enum -> new_set
1263 *
1264 * Returns a new set containing elements exclusive between the set and the
1265 * given enumerable object. <tt>(set ^ enum)</tt> is equivalent to
1266 * <tt>((set | enum) - (set & enum))</tt>.
1267 *
1268 * Set[1, 2] ^ Set[2, 3] #=> #<Set: {3, 1}>
1269 * Set[1, 'b', 'c'] ^ ['b', 'd'] #=> #<Set: {"d", 1, "c"}>
1270 */
1271static VALUE
1272set_i_xor(VALUE set, VALUE other)
1273{
1274 VALUE new_set;
1275 if (rb_obj_is_kind_of(other, rb_cSet)) {
1276 new_set = other;
1277 }
1278 else {
1279 new_set = set_s_alloc(rb_obj_class(set));
1280 set_merge_enum_into(new_set, other);
1281 }
1282 set_iter(set, set_xor_i, (st_data_t)new_set);
1283 return new_set;
1284}
1285
1286/*
1287 * call-seq:
1288 * set | enum -> new_set
1289 *
1290 * Returns a new set built by merging the set and the elements of the
1291 * given enumerable object.
1292 *
1293 * Set[1, 2, 3] | Set[2, 4, 5] #=> #<Set: {1, 2, 3, 4, 5}>
1294 * Set[1, 5, 'z'] | (1..6) #=> #<Set: {1, 5, "z", 2, 3, 4, 6}>
1295 */
1296static VALUE
1297set_i_union(VALUE set, VALUE other)
1298{
1299 set = rb_obj_dup(set);
1300 set_merge_enum_into(set, other);
1301 return set;
1302}
1303
1304static int
1305set_remove_i(st_data_t key, st_data_t from)
1306{
1307 set_delete((struct set_table *)from, (st_data_t *)&key);
1308 return ST_CONTINUE;
1309}
1310
1311static VALUE
1312set_remove_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set))
1313{
1314 rb_check_frozen(set);
1315 set_delete(RSET_TABLE(set), (st_data_t *)&key);
1316 return key;
1317}
1318
1319static void
1320set_remove_enum_from(VALUE set, VALUE arg)
1321{
1322 if (rb_obj_is_kind_of(arg, rb_cSet)) {
1323 set_iter(arg, set_remove_i, (st_data_t)RSET_TABLE(set));
1324 }
1325 else {
1326 rb_block_call(arg, enum_method_id(arg), 0, 0, set_remove_block, (VALUE)set);
1327 }
1328}
1329
1330/*
1331 * call-seq:
1332 * subtract(enum) -> self
1333 *
1334 * Deletes every element that appears in the given enumerable object
1335 * and returns self.
1336 */
1337static VALUE
1338set_i_subtract(VALUE set, VALUE other)
1339{
1340 rb_check_frozen(set);
1341 set_remove_enum_from(set, other);
1342 return set;
1343}
1344
1345/*
1346 * call-seq:
1347 * set - enum -> new_set
1348 *
1349 * Returns a new set built by duplicating the set, removing every
1350 * element that appears in the given enumerable object.
1351 *
1352 * Set[1, 3, 5] - Set[1, 5] #=> #<Set: {3}>
1353 * Set['a', 'b', 'z'] - ['a', 'c'] #=> #<Set: {"b", "z"}>
1354 */
1355static VALUE
1356set_i_difference(VALUE set, VALUE other)
1357{
1358 return set_i_subtract(rb_obj_dup(set), other);
1359}
1360
1361static int
1362set_each_i(st_data_t key, st_data_t dummy)
1363{
1364 rb_yield(key);
1365 return ST_CONTINUE;
1366}
1367
1368/*
1369 * call-seq:
1370 * each { |o| ... } -> self
1371 * each -> enumerator
1372 *
1373 * Calls the given block once for each element in the set, passing
1374 * the element as parameter. Returns an enumerator if no block is
1375 * given.
1376 */
1377static VALUE
1378set_i_each(VALUE set)
1379{
1380 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1381 set_iter(set, set_each_i, 0);
1382 return set;
1383}
1384
1385static int
1386set_collect_i(st_data_t key, st_data_t data)
1387{
1388 set_insert_wb((VALUE)data, rb_yield((VALUE)key), NULL);
1389 return ST_CONTINUE;
1390}
1391
1392/*
1393 * call-seq:
1394 * collect! { |o| ... } -> self
1395 * collect! -> enumerator
1396 *
1397 * Replaces the elements with ones returned by +collect+.
1398 * Returns an enumerator if no block is given.
1399 */
1400static VALUE
1401set_i_collect(VALUE set)
1402{
1403 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1404 rb_check_frozen(set);
1405
1406 VALUE new_set = set_s_alloc(rb_obj_class(set));
1407 set_iter(set, set_collect_i, (st_data_t)new_set);
1408 set_i_initialize_copy(set, new_set);
1409
1410 return set;
1411}
1412
1413static int
1414set_keep_if_i(st_data_t key, st_data_t into)
1415{
1416 if (!RTEST(rb_yield((VALUE)key))) {
1417 set_delete((set_table *)into, &key);
1418 }
1419 return ST_CONTINUE;
1420}
1421
1422/*
1423 * call-seq:
1424 * keep_if { |o| ... } -> self
1425 * keep_if -> enumerator
1426 *
1427 * Deletes every element of the set for which block evaluates to false, and
1428 * returns self. Returns an enumerator if no block is given.
1429 */
1430static VALUE
1431set_i_keep_if(VALUE set)
1432{
1433 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1434 rb_check_frozen(set);
1435
1436 set_iter(set, set_keep_if_i, (st_data_t)RSET_TABLE(set));
1437
1438 return set;
1439}
1440
1441/*
1442 * call-seq:
1443 * select! { |o| ... } -> self
1444 * select! -> enumerator
1445 *
1446 * Equivalent to Set#keep_if, but returns nil if no changes were made.
1447 * Returns an enumerator if no block is given.
1448 */
1449static VALUE
1450set_i_select(VALUE set)
1451{
1452 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1453 rb_check_frozen(set);
1454
1455 set_table *table = RSET_TABLE(set);
1456 size_t n = set_table_size(table);
1457 set_iter(set, set_keep_if_i, (st_data_t)table);
1458
1459 return (n == set_table_size(table)) ? Qnil : set;
1460}
1461
1462/*
1463 * call-seq:
1464 * replace(enum) -> self
1465 *
1466 * Replaces the contents of the set with the contents of the given
1467 * enumerable object and returns self.
1468 *
1469 * set = Set[1, 'c', :s] #=> #<Set: {1, "c", :s}>
1470 * set.replace([1, 2]) #=> #<Set: {1, 2}>
1471 * set #=> #<Set: {1, 2}>
1472 */
1473static VALUE
1474set_i_replace(VALUE set, VALUE other)
1475{
1476 rb_check_frozen(set);
1477
1478 if (rb_obj_is_kind_of(other, rb_cSet)) {
1479 set_i_initialize_copy(set, other);
1480 }
1481 else {
1482 if (set_iterating_p(set)) {
1483 rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
1484 }
1485
1486 // make sure enum is enumerable before calling clear
1487 enum_method_id(other);
1488
1489 set_clear(RSET_TABLE(set));
1490 set_merge_enum_into(set, other);
1491 }
1492
1493 return set;
1494}
1495
1496/*
1497 * call-seq:
1498 * reset -> self
1499 *
1500 * Resets the internal state after modification to existing elements
1501 * and returns self. Elements will be reindexed and deduplicated.
1502 */
1503static VALUE
1504set_i_reset(VALUE set)
1505{
1506 if (set_iterating_p(set)) {
1507 rb_raise(rb_eRuntimeError, "reset during iteration");
1508 }
1509
1510 return set_reset_table_with_type(set, RSET_TABLE(set)->type);
1511}
1512
1513static void set_flatten_merge(VALUE set, VALUE from, VALUE seen);
1514
1515static int
1516set_flatten_merge_i(st_data_t item, st_data_t arg)
1517{
1518 VALUE *args = (VALUE *)arg;
1519 VALUE set = args[0];
1520 if (rb_obj_is_kind_of(item, rb_cSet)) {
1521 VALUE e_id = rb_obj_id(item);
1522 VALUE hash = args[2];
1523 switch(rb_hash_aref(hash, e_id)) {
1524 case Qfalse:
1525 return ST_CONTINUE;
1526 case Qtrue:
1527 rb_raise(rb_eArgError, "tried to flatten recursive Set");
1528 default:
1529 break;
1530 }
1531
1532 rb_hash_aset(hash, e_id, Qtrue);
1533 set_flatten_merge(set, item, hash);
1534 rb_hash_aset(hash, e_id, Qfalse);
1535 }
1536 else {
1537 set_i_add(set, item);
1538 }
1539 return ST_CONTINUE;
1540}
1541
1542static void
1543set_flatten_merge(VALUE set, VALUE from, VALUE hash)
1544{
1545 VALUE args[3] = {set, from, hash};
1546 set_iter(from, set_flatten_merge_i, (st_data_t)args);
1547}
1548
1549/*
1550 * call-seq:
1551 * flatten -> set
1552 *
1553 * Returns a new set that is a copy of the set, flattening each
1554 * containing set recursively.
1555 */
1556static VALUE
1557set_i_flatten(VALUE set)
1558{
1559 VALUE new_set = set_s_alloc(rb_obj_class(set));
1560 set_flatten_merge(new_set, set, rb_hash_new());
1561 return new_set;
1562}
1563
1564static int
1565set_contains_set_i(st_data_t item, st_data_t arg)
1566{
1567 if (rb_obj_is_kind_of(item, rb_cSet)) {
1568 *(bool *)arg = true;
1569 return ST_STOP;
1570 }
1571 return ST_CONTINUE;
1572}
1573
1574/*
1575 * call-seq:
1576 * flatten! -> self
1577 *
1578 * Equivalent to Set#flatten, but replaces the receiver with the
1579 * result in place. Returns nil if no modifications were made.
1580 */
1581static VALUE
1582set_i_flatten_bang(VALUE set)
1583{
1584 bool contains_set = false;
1585 set_iter(set, set_contains_set_i, (st_data_t)&contains_set);
1586 if (!contains_set) return Qnil;
1587 rb_check_frozen(set);
1588 return set_i_replace(set, set_i_flatten(set));
1589}
1590
1592 set_table *table;
1593 VALUE result;
1594};
1595
1596static int
1597set_le_i(st_data_t key, st_data_t arg)
1598{
1599 struct set_subset_data *data = (struct set_subset_data *)arg;
1600 if (set_lookup(data->table, key)) return ST_CONTINUE;
1601 data->result = Qfalse;
1602 return ST_STOP;
1603}
1604
1605static VALUE
1606set_le(VALUE set, VALUE other)
1607{
1608 struct set_subset_data data = {
1609 .table = RSET_TABLE(other),
1610 .result = Qtrue
1611 };
1612 set_iter(set, set_le_i, (st_data_t)&data);
1613 return data.result;
1614}
1615
1616/*
1617 * call-seq:
1618 * proper_subset?(set) -> true or false
1619 *
1620 * Returns true if the set is a proper subset of the given set.
1621 */
1622static VALUE
1623set_i_proper_subset(VALUE set, VALUE other)
1624{
1625 check_set(other);
1626 if (RSET_SIZE(set) >= RSET_SIZE(other)) return Qfalse;
1627 return set_le(set, other);
1628}
1629
1630/*
1631 * call-seq:
1632 * subset?(set) -> true or false
1633 *
1634 * Returns true if the set is a subset of the given set.
1635 */
1636static VALUE
1637set_i_subset(VALUE set, VALUE other)
1638{
1639 check_set(other);
1640 if (RSET_SIZE(set) > RSET_SIZE(other)) return Qfalse;
1641 return set_le(set, other);
1642}
1643
1644/*
1645 * call-seq:
1646 * proper_superset?(set) -> true or false
1647 *
1648 * Returns true if the set is a proper superset of the given set.
1649 */
1650static VALUE
1651set_i_proper_superset(VALUE set, VALUE other)
1652{
1653 check_set(other);
1654 if (RSET_SIZE(set) <= RSET_SIZE(other)) return Qfalse;
1655 return set_le(other, set);
1656}
1657
1658/*
1659 * call-seq:
1660 * superset?(set) -> true or false
1661 *
1662 * Returns true if the set is a superset of the given set.
1663 */
1664static VALUE
1665set_i_superset(VALUE set, VALUE other)
1666{
1667 check_set(other);
1668 if (RSET_SIZE(set) < RSET_SIZE(other)) return Qfalse;
1669 return set_le(other, set);
1670}
1671
1672static int
1673set_intersect_i(st_data_t key, st_data_t arg)
1674{
1675 VALUE *args = (VALUE *)arg;
1676 if (set_lookup((set_table *)args[0], key)) {
1677 args[1] = Qtrue;
1678 return ST_STOP;
1679 }
1680 return ST_CONTINUE;
1681}
1682
1683/*
1684 * call-seq:
1685 * intersect?(set) -> true or false
1686 *
1687 * Returns true if the set and the given enumerable have at least one
1688 * element in common.
1689 *
1690 * Set[1, 2, 3].intersect? Set[4, 5] #=> false
1691 * Set[1, 2, 3].intersect? Set[3, 4] #=> true
1692 * Set[1, 2, 3].intersect? 4..5 #=> false
1693 * Set[1, 2, 3].intersect? [3, 4] #=> true
1694 */
1695static VALUE
1696set_i_intersect(VALUE set, VALUE other)
1697{
1698 if (rb_obj_is_kind_of(other, rb_cSet)) {
1699 size_t set_size = RSET_SIZE(set);
1700 size_t other_size = RSET_SIZE(other);
1701 VALUE args[2];
1702 args[1] = Qfalse;
1703 VALUE iter_arg;
1704
1705 if (set_size < other_size) {
1706 iter_arg = set;
1707 args[0] = (VALUE)RSET_TABLE(other);
1708 }
1709 else {
1710 iter_arg = other;
1711 args[0] = (VALUE)RSET_TABLE(set);
1712 }
1713 set_iter(iter_arg, set_intersect_i, (st_data_t)args);
1714 return args[1];
1715 }
1716 else if (rb_obj_is_kind_of(other, rb_mEnumerable)) {
1717 return rb_funcall(other, id_any_p, 1, set);
1718 }
1719 else {
1720 rb_raise(rb_eArgError, "value must be enumerable");
1721 }
1722}
1723
1724/*
1725 * call-seq:
1726 * disjoint?(set) -> true or false
1727 *
1728 * Returns true if the set and the given enumerable have no
1729 * element in common. This method is the opposite of +intersect?+.
1730 *
1731 * Set[1, 2, 3].disjoint? Set[3, 4] #=> false
1732 * Set[1, 2, 3].disjoint? Set[4, 5] #=> true
1733 * Set[1, 2, 3].disjoint? [3, 4] #=> false
1734 * Set[1, 2, 3].disjoint? 4..5 #=> true
1735 */
1736static VALUE
1737set_i_disjoint(VALUE set, VALUE other)
1738{
1739 return RBOOL(!RTEST(set_i_intersect(set, other)));
1740}
1741
1742/*
1743 * call-seq:
1744 * set <=> other -> -1, 0, 1, or nil
1745 *
1746 * Returns 0 if the set are equal, -1 / 1 if the set is a
1747 * proper subset / superset of the given set, or or nil if
1748 * they both have unique elements.
1749 */
1750static VALUE
1751set_i_compare(VALUE set, VALUE other)
1752{
1753 if (rb_obj_is_kind_of(other, rb_cSet)) {
1754 size_t set_size = RSET_SIZE(set);
1755 size_t other_size = RSET_SIZE(other);
1756
1757 if (set_size < other_size) {
1758 if (set_le(set, other) == Qtrue) {
1759 return INT2NUM(-1);
1760 }
1761 }
1762 else if (set_size > other_size) {
1763 if (set_le(other, set) == Qtrue) {
1764 return INT2NUM(1);
1765 }
1766 }
1767 else if (set_le(set, other) == Qtrue) {
1768 return INT2NUM(0);
1769 }
1770 }
1771
1772 return Qnil;
1773}
1774
1776 VALUE result;
1777 VALUE set;
1778};
1779
1780static int
1781set_eql_i(st_data_t item, st_data_t arg)
1782{
1783 struct set_equal_data *data = (struct set_equal_data *)arg;
1784
1785 if (!set_lookup(RSET_TABLE(data->set), item)) {
1786 data->result = Qfalse;
1787 return ST_STOP;
1788 }
1789 return ST_CONTINUE;
1790}
1791
1792static VALUE
1793set_recursive_eql(VALUE set, VALUE dt, int recur)
1794{
1795 if (recur) return Qtrue;
1796 struct set_equal_data *data = (struct set_equal_data*)dt;
1797 data->result = Qtrue;
1798 set_iter(set, set_eql_i, dt);
1799 return data->result;
1800}
1801
1802/*
1803 * call-seq:
1804 * set == other -> true or false
1805 *
1806 * Returns true if two sets are equal.
1807 */
1808static VALUE
1809set_i_eq(VALUE set, VALUE other)
1810{
1811 if (!rb_obj_is_kind_of(other, rb_cSet)) return Qfalse;
1812 if (set == other) return Qtrue;
1813
1814 set_table *stable = RSET_TABLE(set);
1815 set_table *otable = RSET_TABLE(other);
1816 size_t ssize = set_table_size(stable);
1817 size_t osize = set_table_size(otable);
1818
1819 if (ssize != osize) return Qfalse;
1820 if (ssize == 0 && osize == 0) return Qtrue;
1821 if (stable->type != otable->type) return Qfalse;
1822
1823 struct set_equal_data data;
1824 data.set = other;
1825 return rb_exec_recursive_paired(set_recursive_eql, set, other, (VALUE)&data);
1826}
1827
1828static int
1829set_hash_i(st_data_t item, st_data_t(arg))
1830{
1831 st_index_t *hval = (st_index_t *)arg;
1832 st_index_t ival = rb_hash(item);
1833 *hval ^= rb_st_hash(&ival, sizeof(st_index_t), 0);
1834 return ST_CONTINUE;
1835}
1836
1837/*
1838 * call-seq:
1839 * hash -> integer
1840 *
1841 * Returns hash code for set.
1842 */
1843static VALUE
1844set_i_hash(VALUE set)
1845{
1846 st_index_t size = RSET_SIZE(set);
1847 st_index_t hval = rb_st_hash_start(size);
1848 hval = rb_hash_uint(hval, (st_index_t)set_i_hash);
1849 if (size) {
1850 set_iter(set, set_hash_i, (VALUE)&hval);
1851 }
1852 hval = rb_st_hash_end(hval);
1853 return ST2FIX(hval);
1854}
1855
1856/* :nodoc: */
1857static int
1858set_to_hash_i(st_data_t key, st_data_t arg)
1859{
1860 rb_hash_aset((VALUE)arg, (VALUE)key, Qtrue);
1861 return ST_CONTINUE;
1862}
1863
1864static VALUE
1865set_i_to_h(VALUE set)
1866{
1867 st_index_t size = RSET_SIZE(set);
1868 VALUE hash;
1869 if (RSET_COMPARE_BY_IDENTITY(set)) {
1870 hash = rb_ident_hash_new_with_size(size);
1871 }
1872 else {
1873 hash = rb_hash_new_with_size(size);
1874 }
1875 rb_hash_set_default(hash, Qfalse);
1876
1877 if (size == 0) return hash;
1878
1879 set_iter(set, set_to_hash_i, (st_data_t)hash);
1880 return hash;
1881}
1882
1883static VALUE
1884compat_dumper(VALUE set)
1885{
1886 VALUE dumper = rb_class_new_instance(0, 0, rb_cObject);
1887 rb_ivar_set(dumper, id_i_hash, set_i_to_h(set));
1888 return dumper;
1889}
1890
1891static int
1892set_i_from_hash_i(st_data_t key, st_data_t val, st_data_t set)
1893{
1894 if ((VALUE)val != Qtrue) {
1895 rb_raise(rb_eRuntimeError, "expect true as Set value: %"PRIsVALUE, rb_obj_class((VALUE)val));
1896 }
1897 set_i_add((VALUE)set, (VALUE)key);
1898 return ST_CONTINUE;
1899}
1900
1901static VALUE
1902set_i_from_hash(VALUE set, VALUE hash)
1903{
1904 Check_Type(hash, T_HASH);
1905 if (rb_hash_compare_by_id_p(hash)) set_i_compare_by_identity(set);
1906 rb_hash_stlike_foreach(hash, set_i_from_hash_i, (st_data_t)set);
1907 return set;
1908}
1909
1910static VALUE
1911compat_loader(VALUE self, VALUE a)
1912{
1913 return set_i_from_hash(self, rb_ivar_get(a, id_i_hash));
1914}
1915
1916/*
1917 * Document-class: Set
1918 *
1919 * Copyright (c) 2002-2024 Akinori MUSHA <knu@iDaemons.org>
1920 *
1921 * Documentation by Akinori MUSHA and Gavin Sinclair.
1922 *
1923 * All rights reserved. You can redistribute and/or modify it under the same
1924 * terms as Ruby.
1925 *
1926 * The Set class implements a collection of unordered values with no
1927 * duplicates. It is a hybrid of Array's intuitive inter-operation
1928 * facilities and Hash's fast lookup.
1929 *
1930 * Set is easy to use with Enumerable objects (implementing `each`).
1931 * Most of the initializer methods and binary operators accept generic
1932 * Enumerable objects besides sets and arrays. An Enumerable object
1933 * can be converted to Set using the `to_set` method.
1934 *
1935 * Set uses a data structure similar to Hash for storage, except that
1936 * it only has keys and no values.
1937 *
1938 * * Equality of elements is determined according to Object#eql? and
1939 * Object#hash. Use Set#compare_by_identity to make a set compare
1940 * its elements by their identity.
1941 * * Set assumes that the identity of each element does not change
1942 * while it is stored. Modifying an element of a set will render the
1943 * set to an unreliable state.
1944 * * When a string is to be stored, a frozen copy of the string is
1945 * stored instead unless the original string is already frozen.
1946 *
1947 * == Comparison
1948 *
1949 * The comparison operators <tt><</tt>, <tt>></tt>, <tt><=</tt>, and
1950 * <tt>>=</tt> are implemented as shorthand for the
1951 * {proper_,}{subset?,superset?} methods. The <tt><=></tt>
1952 * operator reflects this order, or returns +nil+ for sets that both
1953 * have distinct elements (<tt>{x, y}</tt> vs. <tt>{x, z}</tt> for example).
1954 *
1955 * == Example
1956 *
1957 * s1 = Set[1, 2] #=> #<Set: {1, 2}>
1958 * s2 = [1, 2].to_set #=> #<Set: {1, 2}>
1959 * s1 == s2 #=> true
1960 * s1.add("foo") #=> #<Set: {1, 2, "foo"}>
1961 * s1.merge([2, 6]) #=> #<Set: {1, 2, "foo", 6}>
1962 * s1.subset?(s2) #=> false
1963 * s2.subset?(s1) #=> true
1964 *
1965 * == Contact
1966 *
1967 * - Akinori MUSHA <knu@iDaemons.org> (current maintainer)
1968 *
1969 * == What's Here
1970 *
1971 * First, what's elsewhere. \Class \Set:
1972 *
1973 * - Inherits from {class Object}[rdoc-ref:Object@What-27s+Here].
1974 * - Includes {module Enumerable}[rdoc-ref:Enumerable@What-27s+Here],
1975 * which provides dozens of additional methods.
1976 *
1977 * In particular, class \Set does not have many methods of its own
1978 * for fetching or for iterating.
1979 * Instead, it relies on those in \Enumerable.
1980 *
1981 * Here, class \Set provides methods that are useful for:
1982 *
1983 * - {Creating an Array}[rdoc-ref:Array@Methods+for+Creating+an+Array]
1984 * - {Creating a Set}[rdoc-ref:Array@Methods+for+Creating+a+Set]
1985 * - {Set Operations}[rdoc-ref:Array@Methods+for+Set+Operations]
1986 * - {Comparing}[rdoc-ref:Array@Methods+for+Comparing]
1987 * - {Querying}[rdoc-ref:Array@Methods+for+Querying]
1988 * - {Assigning}[rdoc-ref:Array@Methods+for+Assigning]
1989 * - {Deleting}[rdoc-ref:Array@Methods+for+Deleting]
1990 * - {Converting}[rdoc-ref:Array@Methods+for+Converting]
1991 * - {Iterating}[rdoc-ref:Array@Methods+for+Iterating]
1992 * - {And more....}[rdoc-ref:Array@Other+Methods]
1993 *
1994 * === Methods for Creating a \Set
1995 *
1996 * - ::[]:
1997 * Returns a new set containing the given objects.
1998 * - ::new:
1999 * Returns a new set containing either the given objects
2000 * (if no block given) or the return values from the called block
2001 * (if a block given).
2002 *
2003 * === Methods for \Set Operations
2004 *
2005 * - #| (aliased as #union and #+):
2006 * Returns a new set containing all elements from +self+
2007 * and all elements from a given enumerable (no duplicates).
2008 * - #& (aliased as #intersection):
2009 * Returns a new set containing all elements common to +self+
2010 * and a given enumerable.
2011 * - #- (aliased as #difference):
2012 * Returns a copy of +self+ with all elements
2013 * in a given enumerable removed.
2014 * - #^: Returns a new set containing all elements from +self+
2015 * and a given enumerable except those common to both.
2016 *
2017 * === Methods for Comparing
2018 *
2019 * - #<=>: Returns -1, 0, or 1 as +self+ is less than, equal to,
2020 * or greater than a given object.
2021 * - #==: Returns whether +self+ and a given enumerable are equal,
2022 * as determined by Object#eql?.
2023 * - #compare_by_identity?:
2024 * Returns whether the set considers only identity
2025 * when comparing elements.
2026 *
2027 * === Methods for Querying
2028 *
2029 * - #length (aliased as #size):
2030 * Returns the count of elements.
2031 * - #empty?:
2032 * Returns whether the set has no elements.
2033 * - #include? (aliased as #member? and #===):
2034 * Returns whether a given object is an element in the set.
2035 * - #subset? (aliased as #<=):
2036 * Returns whether a given object is a subset of the set.
2037 * - #proper_subset? (aliased as #<):
2038 * Returns whether a given enumerable is a proper subset of the set.
2039 * - #superset? (aliased as #>=):
2040 * Returns whether a given enumerable is a superset of the set.
2041 * - #proper_superset? (aliased as #>):
2042 * Returns whether a given enumerable is a proper superset of the set.
2043 * - #disjoint?:
2044 * Returns +true+ if the set and a given enumerable
2045 * have no common elements, +false+ otherwise.
2046 * - #intersect?:
2047 * Returns +true+ if the set and a given enumerable:
2048 * have any common elements, +false+ otherwise.
2049 * - #compare_by_identity?:
2050 * Returns whether the set considers only identity
2051 * when comparing elements.
2052 *
2053 * === Methods for Assigning
2054 *
2055 * - #add (aliased as #<<):
2056 * Adds a given object to the set; returns +self+.
2057 * - #add?:
2058 * If the given object is not an element in the set,
2059 * adds it and returns +self+; otherwise, returns +nil+.
2060 * - #merge:
2061 * Merges the elements of each given enumerable object to the set; returns +self+.
2062 * - #replace:
2063 * Replaces the contents of the set with the contents
2064 * of a given enumerable.
2065 *
2066 * === Methods for Deleting
2067 *
2068 * - #clear:
2069 * Removes all elements in the set; returns +self+.
2070 * - #delete:
2071 * Removes a given object from the set; returns +self+.
2072 * - #delete?:
2073 * If the given object is an element in the set,
2074 * removes it and returns +self+; otherwise, returns +nil+.
2075 * - #subtract:
2076 * Removes each given object from the set; returns +self+.
2077 * - #delete_if - Removes elements specified by a given block.
2078 * - #select! (aliased as #filter!):
2079 * Removes elements not specified by a given block.
2080 * - #keep_if:
2081 * Removes elements not specified by a given block.
2082 * - #reject!
2083 * Removes elements specified by a given block.
2084 *
2085 * === Methods for Converting
2086 *
2087 * - #classify:
2088 * Returns a hash that classifies the elements,
2089 * as determined by the given block.
2090 * - #collect! (aliased as #map!):
2091 * Replaces each element with a block return-value.
2092 * - #divide:
2093 * Returns a hash that classifies the elements,
2094 * as determined by the given block;
2095 * differs from #classify in that the block may accept
2096 * either one or two arguments.
2097 * - #flatten:
2098 * Returns a new set that is a recursive flattening of +self+.
2099 * - #flatten!:
2100 * Replaces each nested set in +self+ with the elements from that set.
2101 * - #inspect (aliased as #to_s):
2102 * Returns a string displaying the elements.
2103 * - #join:
2104 * Returns a string containing all elements, converted to strings
2105 * as needed, and joined by the given record separator.
2106 * - #to_a:
2107 * Returns an array containing all set elements.
2108 * - #to_set:
2109 * Returns +self+ if given no arguments and no block;
2110 * with a block given, returns a new set consisting of block
2111 * return values.
2112 *
2113 * === Methods for Iterating
2114 *
2115 * - #each:
2116 * Calls the block with each successive element; returns +self+.
2117 *
2118 * === Other Methods
2119 *
2120 * - #reset:
2121 * Resets the internal state; useful if an object
2122 * has been modified while an element in the set.
2123 *
2124 */
2125void
2126Init_Set(void)
2127{
2128 rb_cSet = rb_define_class("Set", rb_cObject);
2130
2131 id_each_entry = rb_intern_const("each_entry");
2132 id_any_p = rb_intern_const("any?");
2133 id_new = rb_intern_const("new");
2134 id_i_hash = rb_intern_const("@hash");
2135 id_set_iter_lev = rb_make_internal_id();
2136
2137 rb_define_alloc_func(rb_cSet, set_s_alloc);
2138 rb_define_singleton_method(rb_cSet, "[]", set_s_create, -1);
2139
2140 rb_define_method(rb_cSet, "initialize", set_i_initialize, -1);
2141 rb_define_method(rb_cSet, "initialize_copy", set_i_initialize_copy, 1);
2142
2143 rb_define_method(rb_cSet, "&", set_i_intersection, 1);
2144 rb_define_alias(rb_cSet, "intersection", "&");
2145 rb_define_method(rb_cSet, "-", set_i_difference, 1);
2146 rb_define_alias(rb_cSet, "difference", "-");
2147 rb_define_method(rb_cSet, "^", set_i_xor, 1);
2148 rb_define_method(rb_cSet, "|", set_i_union, 1);
2149 rb_define_alias(rb_cSet, "+", "|");
2150 rb_define_alias(rb_cSet, "union", "|");
2151 rb_define_method(rb_cSet, "<=>", set_i_compare, 1);
2152 rb_define_method(rb_cSet, "==", set_i_eq, 1);
2153 rb_define_alias(rb_cSet, "eql?", "==");
2154 rb_define_method(rb_cSet, "add", set_i_add, 1);
2155 rb_define_alias(rb_cSet, "<<", "add");
2156 rb_define_method(rb_cSet, "add?", set_i_add_p, 1);
2157 rb_define_method(rb_cSet, "classify", set_i_classify, 0);
2158 rb_define_method(rb_cSet, "clear", set_i_clear, 0);
2159 rb_define_method(rb_cSet, "collect!", set_i_collect, 0);
2160 rb_define_alias(rb_cSet, "map!", "collect!");
2161 rb_define_method(rb_cSet, "compare_by_identity", set_i_compare_by_identity, 0);
2162 rb_define_method(rb_cSet, "compare_by_identity?", set_i_compare_by_identity_p, 0);
2163 rb_define_method(rb_cSet, "delete", set_i_delete, 1);
2164 rb_define_method(rb_cSet, "delete?", set_i_delete_p, 1);
2165 rb_define_method(rb_cSet, "delete_if", set_i_delete_if, 0);
2166 rb_define_method(rb_cSet, "disjoint?", set_i_disjoint, 1);
2167 rb_define_method(rb_cSet, "divide", set_i_divide, 0);
2168 rb_define_method(rb_cSet, "each", set_i_each, 0);
2169 rb_define_method(rb_cSet, "empty?", set_i_empty, 0);
2170 rb_define_method(rb_cSet, "flatten", set_i_flatten, 0);
2171 rb_define_method(rb_cSet, "flatten!", set_i_flatten_bang, 0);
2172 rb_define_method(rb_cSet, "hash", set_i_hash, 0);
2173 rb_define_method(rb_cSet, "include?", set_i_include, 1);
2174 rb_define_alias(rb_cSet, "member?", "include?");
2175 rb_define_alias(rb_cSet, "===", "include?");
2176 rb_define_method(rb_cSet, "inspect", set_i_inspect, 0);
2177 rb_define_alias(rb_cSet, "to_s", "inspect");
2178 rb_define_method(rb_cSet, "intersect?", set_i_intersect, 1);
2179 rb_define_method(rb_cSet, "join", set_i_join, -1);
2180 rb_define_method(rb_cSet, "keep_if", set_i_keep_if, 0);
2181 rb_define_method(rb_cSet, "merge", set_i_merge, -1);
2182 rb_define_method(rb_cSet, "proper_subset?", set_i_proper_subset, 1);
2183 rb_define_alias(rb_cSet, "<", "proper_subset?");
2184 rb_define_method(rb_cSet, "proper_superset?", set_i_proper_superset, 1);
2185 rb_define_alias(rb_cSet, ">", "proper_superset?");
2186 rb_define_method(rb_cSet, "reject!", set_i_reject, 0);
2187 rb_define_method(rb_cSet, "replace", set_i_replace, 1);
2188 rb_define_method(rb_cSet, "reset", set_i_reset, 0);
2189 rb_define_method(rb_cSet, "size", set_i_size, 0);
2190 rb_define_alias(rb_cSet, "length", "size");
2191 rb_define_method(rb_cSet, "select!", set_i_select, 0);
2192 rb_define_alias(rb_cSet, "filter!", "select!");
2193 rb_define_method(rb_cSet, "subset?", set_i_subset, 1);
2194 rb_define_alias(rb_cSet, "<=", "subset?");
2195 rb_define_method(rb_cSet, "subtract", set_i_subtract, 1);
2196 rb_define_method(rb_cSet, "superset?", set_i_superset, 1);
2197 rb_define_alias(rb_cSet, ">=", "superset?");
2198 rb_define_method(rb_cSet, "to_a", set_i_to_a, 0);
2199 rb_define_method(rb_cSet, "to_set", set_i_to_set, -1);
2200
2201 /* :nodoc: */
2202 VALUE compat = rb_define_class_under(rb_cSet, "compatible", rb_cObject);
2203 rb_marshal_define_compat(rb_cSet, compat, compat_dumper, compat_loader);
2204
2205 rb_provide("set.rb");
2206}
#define rb_define_method(klass, mid, func, arity)
Defines klass#mid.
#define rb_define_singleton_method(klass, mid, func, arity)
Defines klass.mid.
static bool RB_OBJ_FROZEN(VALUE obj)
Checks if an object is frozen.
Definition fl_type.h:892
void rb_include_module(VALUE klass, VALUE module)
Includes a module to a class.
Definition class.c:1701
VALUE rb_define_class(const char *name, VALUE super)
Defines a top-level class.
Definition class.c:1484
VALUE rb_define_class_under(VALUE outer, const char *name, VALUE super)
Defines a class under the namespace of outer.
Definition class.c:1520
void rb_define_alias(VALUE klass, const char *name1, const char *name2)
Defines an alias of a method.
Definition class.c:2848
int rb_keyword_given_p(void)
Determines if the current method is given a keyword argument.
Definition eval.c:956
int rb_block_given_p(void)
Determines if the current method is given a block.
Definition eval.c:943
#define rb_str_buf_cat2
Old name of rb_usascii_str_new_cstr.
Definition string.h:1682
#define Qundef
Old name of RUBY_Qundef.
#define CLASS_OF
Old name of rb_class_of.
Definition globals.h:205
#define LONG2FIX
Old name of RB_INT2FIX.
Definition long.h:49
#define T_HASH
Old name of RUBY_T_HASH.
Definition value_type.h:65
#define FLONUM_P
Old name of RB_FLONUM_P.
#define Qtrue
Old name of RUBY_Qtrue.
#define ST2FIX
Old name of RB_ST2FIX.
Definition st_data_t.h:33
#define INT2NUM
Old name of RB_INT2NUM.
Definition int.h:43
#define Qnil
Old name of RUBY_Qnil.
#define Qfalse
Old name of RUBY_Qfalse.
#define FIX2LONG
Old name of RB_FIX2LONG.
Definition long.h:46
#define T_ARRAY
Old name of RUBY_T_ARRAY.
Definition value_type.h:56
#define ALLOCV_N
Old name of RB_ALLOCV_N.
Definition memory.h:405
#define POSFIXABLE
Old name of RB_POSFIXABLE.
Definition fixnum.h:29
#define FIXNUM_P
Old name of RB_FIXNUM_P.
#define ALLOCV_END
Old name of RB_ALLOCV_END.
Definition memory.h:406
VALUE rb_eRuntimeError
RuntimeError exception.
Definition error.c:1428
VALUE rb_class_new_instance(int argc, const VALUE *argv, VALUE klass)
Allocates, then initialises an instance of the given class.
Definition object.c:2166
VALUE rb_mEnumerable
Enumerable module.
Definition enum.c:27
VALUE rb_obj_class(VALUE obj)
Queries the class of an object.
Definition object.c:243
VALUE rb_obj_dup(VALUE obj)
Duplicates the given object.
Definition object.c:553
VALUE rb_inspect(VALUE obj)
Generates a human-readable textual representation of the given object.
Definition object.c:657
VALUE rb_obj_is_instance_of(VALUE obj, VALUE klass)
Queries if the given object is a direct instance of the given class.
Definition object.c:824
VALUE rb_obj_is_kind_of(VALUE obj, VALUE klass)
Queries if the given object is an instance (of possibly descendants) of the given class.
Definition object.c:880
VALUE rb_cString
String class.
Definition string.c:83
#define RB_OBJ_WRITTEN(old, oldv, young)
Identical to RB_OBJ_WRITE(), except it doesn't write any values, but only a WB declaration.
Definition gc.h:615
VALUE rb_str_export_to_enc(VALUE obj, rb_encoding *enc)
Identical to rb_str_export(), except it additionally takes an encoding.
Definition string.c:1421
VALUE rb_funcall_passing_block(VALUE recv, ID mid, int argc, const VALUE *argv)
Identical to rb_funcallv_public(), except you can pass the passed block.
Definition vm_eval.c:1180
VALUE rb_funcall(VALUE recv, ID mid, int n,...)
Calls a method.
Definition vm_eval.c:1117
VALUE rb_ary_new_capa(long capa)
Identical to rb_ary_new(), except it additionally specifies how many rooms of objects it should alloc...
VALUE rb_ary_push(VALUE ary, VALUE elem)
Special case of rb_ary_cat() that it adds only one element.
VALUE rb_ary_freeze(VALUE obj)
Freeze an array, preventing further modifications.
VALUE rb_ary_join(VALUE ary, VALUE sep)
Recursively stringises the elements of the passed array, flattens that result, then joins the sequenc...
#define RETURN_SIZED_ENUMERATOR(obj, argc, argv, size_fn)
This roughly resembles return enum_for(__callee__) unless block_given?.
Definition enumerator.h:206
static int rb_check_arity(int argc, int min, int max)
Ensures that the passed integer is in the passed range.
Definition error.h:284
void rb_provide(const char *feature)
Declares that the given feature is already provided by someone else.
Definition load.c:765
#define rb_hash_uint(h, i)
Just another name of st_hash_uint.
Definition string.h:942
VALUE rb_str_buf_append(VALUE dst, VALUE src)
Identical to rb_str_cat_cstr(), except it takes Ruby's string instead of C's.
Definition string.c:3721
VALUE rb_str_buf_cat_ascii(VALUE dst, const char *src)
Identical to rb_str_cat_cstr(), except it additionally assumes the source string be a NUL terminated ...
Definition string.c:3697
VALUE rb_exec_recursive(VALUE(*f)(VALUE g, VALUE h, int r), VALUE g, VALUE h)
"Recursion" API entry point.
VALUE rb_exec_recursive_paired(VALUE(*f)(VALUE g, VALUE h, int r), VALUE g, VALUE p, VALUE h)
Identical to rb_exec_recursive(), except it checks for the recursion on the ordered pair of { g,...
VALUE rb_ivar_set(VALUE obj, ID name, VALUE val)
Identical to rb_iv_set(), except it accepts the name as an ID instead of a C string.
Definition variable.c:2087
VALUE rb_ivar_get(VALUE obj, ID name)
Identical to rb_iv_get(), except it accepts the name as an ID instead of a C string.
Definition variable.c:1443
VALUE rb_class_path(VALUE mod)
Identical to rb_mod_name(), except it returns #<Class: ...> style inspection for anonymous modules.
Definition variable.c:374
int rb_respond_to(VALUE obj, ID mid)
Queries if the object responds to the method.
Definition vm_method.c:3094
void rb_define_alloc_func(VALUE klass, rb_alloc_func_t func)
Sets the allocator function of a class.
static ID rb_intern_const(const char *str)
This is a "tiny optimisation" over rb_intern().
Definition symbol.h:284
#define RB_BLOCK_CALL_FUNC_ARGLIST(yielded_arg, callback_arg)
Shim for block function parameters.
Definition iterator.h:58
VALUE rb_yield_values(int n,...)
Identical to rb_yield(), except it takes variadic number of parameters and pass them to the block.
Definition vm_eval.c:1384
VALUE rb_yield(VALUE val)
Yields the block.
Definition vm_eval.c:1372
void rb_marshal_define_compat(VALUE newclass, VALUE oldclass, VALUE(*dumper)(VALUE), VALUE(*loader)(VALUE, VALUE))
Marshal format compatibility layer.
Definition marshal.c:137
VALUE rb_block_call(VALUE q, ID w, int e, const VALUE *r, type *t, VALUE y)
Call a method with a block.
VALUE type(ANYARGS)
ANYARGS-ed function type.
VALUE rb_ensure(type *q, VALUE w, type *e, VALUE r)
An equivalent of ensure clause.
#define RARRAY_LEN
Just another name of rb_array_len.
Definition rarray.h:51
#define RARRAY_PTR_USE(ary, ptr_name, expr)
Declares a section of code where raw pointers are used.
Definition rarray.h:348
#define RARRAY_AREF(a, i)
Definition rarray.h:403
#define RBASIC(obj)
Convenient casting macro.
Definition rbasic.h:40
#define TypedData_Get_Struct(obj, type, data_type, sval)
Obtains a C struct from inside of a wrapper Ruby object.
Definition rtypeddata.h:515
#define TypedData_Make_Struct(klass, type, data_type, sval)
Identical to TypedData_Wrap_Struct, except it allocates a new data region internally instead of takin...
Definition rtypeddata.h:497
#define RTEST
This is an old name of RB_TEST.
This is the struct that holds necessary info for a struct.
Definition rtypeddata.h:203
const char * wrap_struct_name
Name of structs of this kind.
Definition rtypeddata.h:210
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
Definition value.h:52
uintptr_t VALUE
Type that represents a Ruby object.
Definition value.h:40
static void Check_Type(VALUE v, enum ruby_value_type t)
Identical to RB_TYPE_P(), except it raises exceptions on predication failure.
Definition value_type.h:433
static bool RB_TYPE_P(VALUE obj, enum ruby_value_type t)
Queries if the given object is of given type.
Definition value_type.h:376