Ruby 4.1.0dev (2026-11-19 revision 2e6b197f6849401b2c25894b5b8ac39ac3c2558e)
set.c (2e6b197f6849401b2c25894b5b8ac39ac3c2558e)
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/object.h"
13#include "internal/proc.h"
14#include "internal/sanitizers.h"
15#include "internal/set.h"
16#include "internal/set_table.h"
17#include "internal/symbol.h"
18#include "internal/variable.h"
19#include "ruby_assert.h"
20
21#include <stdio.h>
22#ifdef HAVE_STDLIB_H
23#include <stdlib.h>
24#endif
25#include <string.h>
26
27#ifndef SET_DEBUG
28#define SET_DEBUG 0
29#endif
30
31#if SET_DEBUG
32#include "internal/gc.h"
33#endif
34
35static st_index_t
36dbl_to_index(double d)
37{
38 union {double d; st_index_t i;} u;
39 u.d = d;
40 return u.i;
41}
42
43static const uint64_t prime1 = ((uint64_t)0x2e0bb864 << 32) | 0xe9ea7df5;
44static const uint32_t prime2 = 0x830fcab9;
45
46static inline uint64_t
47mult_and_mix(uint64_t m1, uint64_t m2)
48{
49#if defined HAVE_UINT128_T
50 uint128_t r = (uint128_t) m1 * (uint128_t) m2;
51 return (uint64_t) (r >> 64) ^ (uint64_t) r;
52#else
53 uint64_t hm1 = m1 >> 32, hm2 = m2 >> 32;
54 uint64_t lm1 = m1, lm2 = m2;
55 uint64_t v64_128 = hm1 * hm2;
56 uint64_t v32_96 = hm1 * lm2 + lm1 * hm2;
57 uint64_t v1_32 = lm1 * lm2;
58
59 return (v64_128 + (v32_96 >> 32)) ^ ((v32_96 << 32) + v1_32);
60#endif
61}
62
63static inline uint64_t
64key64_hash(uint64_t key, uint32_t seed)
65{
66 return mult_and_mix(key + seed, prime1);
67}
68
69/* Should cast down the result for each purpose */
70#define set_index_hash(index) key64_hash(rb_hash_start(index), prime2)
71
72static st_index_t
73set_ident_hash(st_data_t n)
74{
75#ifdef USE_FLONUM /* RUBY */
76 /*
77 * - flonum (on 64-bit) is pathologically bad, mix the actual
78 * float value in, but do not use the float value as-is since
79 * many integers get interpreted as 2.0 or -2.0 [Bug #10761]
80 */
81 if (FLONUM_P(n)) {
82 n ^= dbl_to_index(rb_float_value(n));
83 }
84#endif
85
86 return (st_index_t)set_index_hash((st_index_t)n);
87}
88
89static const struct st_hash_type identhash = {
90 rb_st_numcmp,
91 set_ident_hash,
92};
93
94static const struct st_hash_type objhash = {
95 rb_any_cmp,
96 rb_any_hash,
97};
98
100static VALUE set_i_compare_by_identity(VALUE set);
101
102#define id_each idEach
103static ID id_each_entry;
104static ID id_any_p;
105static ID id_new;
106static ID id_i_hash;
107static ID id_set_iter_lev;
108static ID id_subclass_compatible;
109static ID id_class_methods;
110
111#define RSET_INITIALIZED FL_USER1
112#define RSET_LEV_MASK (FL_USER13 | FL_USER14 | FL_USER15 | /* FL 13..19 */ \
113 FL_USER16 | FL_USER17 | FL_USER18 | FL_USER19)
114#define RSET_LEV_SHIFT (FL_USHIFT + 13)
115#define RSET_LEV_MAX 127 /* 7 bits */
116
117#define SET_ASSERT(expr) RUBY_ASSERT_MESG_WHEN(SET_DEBUG, expr, #expr)
118
119#define RSET_SIZE(set) set_table_size(RSET_TABLE(set))
120#define RSET_EMPTY(set) (RSET_SIZE(set) == 0)
121#define RSET_SIZE_NUM(set) SIZET2NUM(RSET_SIZE(set))
122#define RSET_IS_MEMBER(set, item) set_table_lookup(RSET_TABLE(set), (st_data_t)(item))
123#define RSET_COMPARE_BY_IDENTITY(set) (RSET_TABLE(set)->type == &identhash)
124
126 set_table table;
127};
128
129static int
130mark_and_pin_key(st_data_t key, st_data_t data)
131{
132 rb_gc_mark((VALUE)key);
133
134 return ST_CONTINUE;
135}
136
137static int
138mark_key(st_data_t key, st_data_t data)
139{
140 rb_gc_mark_movable((VALUE)key);
141
142 return ST_CONTINUE;
143}
144
145static void
146set_mark(void *ptr)
147{
148 struct set_object *sobj = ptr;
149 if (sobj->table.entries) {
150 if (sobj->table.type == &identhash) {
151 set_table_foreach(&sobj->table, mark_and_pin_key, 0);
152 }
153 else {
154 set_table_foreach(&sobj->table, mark_key, 0);
155 }
156 }
157}
158
159static void
160set_free(void *ptr)
161{
162 struct set_object *sobj = ptr;
163 set_free_embedded_table(&sobj->table);
164}
165
166static size_t
167set_size(const void *ptr)
168{
169 const struct set_object *sobj = ptr;
170 /* Do not count the table size twice, as it is embedded */
171 return (unsigned long)set_memsize(&sobj->table) - sizeof(sobj->table);
172}
173
174static int
175set_foreach_replace(st_data_t key, st_data_t argp, int error)
176{
177 if (rb_gc_location((VALUE)key) != (VALUE)key) {
178 return ST_REPLACE;
179 }
180
181 return ST_CONTINUE;
182}
183
184static int
185set_replace_ref(st_data_t *key, st_data_t argp, int existing)
186{
187 rb_gc_mark_and_move((VALUE *)key);
188
189 return ST_CONTINUE;
190}
191
192static void
193set_update_references(void *ptr)
194{
195 struct set_object *sobj = ptr;
196 set_foreach_with_replace(&sobj->table, set_foreach_replace, set_replace_ref, 0);
197}
198
199static const rb_data_type_t set_data_type = {
200 .wrap_struct_name = "set",
201 .function = {
202 .dmark = set_mark,
203 .dfree = set_free,
204 .dsize = set_size,
205 .dcompact = set_update_references,
206 },
207 .flags = RUBY_TYPED_EMBEDDABLE | RUBY_TYPED_THREAD_SAFE_FREE | RUBY_TYPED_WB_PROTECTED | RUBY_TYPED_FROZEN_SHAREABLE
208};
209
210static inline set_table *
211RSET_TABLE(VALUE set)
212{
213 struct set_object *sobj;
214 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
215 return &sobj->table;
216}
217
218static unsigned long
219iter_lev_in_ivar(VALUE set)
220{
221 VALUE levval = rb_ivar_get(set, id_set_iter_lev);
222 SET_ASSERT(FIXNUM_P(levval));
223 long lev = FIX2LONG(levval);
224 SET_ASSERT(lev >= 0);
225 return (unsigned long)lev;
226}
227
228void rb_ivar_set_internal(VALUE obj, ID id, VALUE val);
229
230static void
231iter_lev_in_ivar_set(VALUE set, unsigned long lev)
232{
233 SET_ASSERT(lev >= RSET_LEV_MAX);
234 SET_ASSERT(POSFIXABLE(lev)); /* POSFIXABLE means fitting to long */
235 rb_ivar_set_internal(set, id_set_iter_lev, LONG2FIX((long)lev));
236}
237
238static inline unsigned long
239iter_lev_in_flags(VALUE set)
240{
241 return (unsigned long)((RBASIC(set)->flags >> RSET_LEV_SHIFT) & RSET_LEV_MAX);
242}
243
244static inline void
245iter_lev_in_flags_set(VALUE set, unsigned long lev)
246{
247 SET_ASSERT(lev <= RSET_LEV_MAX);
248 RBASIC(set)->flags = ((RBASIC(set)->flags & ~RSET_LEV_MASK) | ((VALUE)lev << RSET_LEV_SHIFT));
249}
250
251static inline bool
252set_iterating_p(VALUE set)
253{
254 return iter_lev_in_flags(set) > 0;
255}
256
257static void
258set_iter_lev_inc(VALUE set)
259{
260 unsigned long lev = iter_lev_in_flags(set);
261 if (lev == RSET_LEV_MAX) {
262 lev = iter_lev_in_ivar(set) + 1;
263 if (!POSFIXABLE(lev)) { /* paranoiac check */
264 rb_raise(rb_eRuntimeError, "too much nested iterations");
265 }
266 }
267 else {
268 lev += 1;
269 iter_lev_in_flags_set(set, lev);
270 if (lev < RSET_LEV_MAX) return;
271 }
272 iter_lev_in_ivar_set(set, lev);
273}
274
275static void
276set_iter_lev_dec(VALUE set)
277{
278 unsigned long lev = iter_lev_in_flags(set);
279 if (lev == RSET_LEV_MAX) {
280 lev = iter_lev_in_ivar(set);
281 if (lev > RSET_LEV_MAX) {
282 iter_lev_in_ivar_set(set, lev-1);
283 return;
284 }
285 rb_attr_delete(set, id_set_iter_lev);
286 }
287 else if (lev == 0) {
288 rb_raise(rb_eRuntimeError, "iteration level underflow");
289 }
290 iter_lev_in_flags_set(set, lev - 1);
291}
292
293static VALUE
294set_foreach_ensure(VALUE set)
295{
296 set_iter_lev_dec(set);
297 return 0;
298}
299
300typedef int set_foreach_func(VALUE, VALUE);
301
303 VALUE set;
304 set_foreach_func *func;
305 VALUE arg;
306};
307
308static int
309set_iter_status_check(int status)
310{
311 if (status == ST_CONTINUE) {
312 return ST_CHECK;
313 }
314
315 return status;
316}
317
318static int
319set_foreach_iter(st_data_t key, st_data_t argp, int error)
320{
321 struct set_foreach_arg *arg = (struct set_foreach_arg *)argp;
322
323 if (error) return ST_STOP;
324
325 set_table *tbl = RSET_TABLE(arg->set);
326 int status = (*arg->func)((VALUE)key, arg->arg);
327
328 if (RSET_TABLE(arg->set) != tbl) {
329 rb_raise(rb_eRuntimeError, "reset occurred during iteration");
330 }
331
332 return set_iter_status_check(status);
333}
334
335static VALUE
336set_foreach_call(VALUE arg)
337{
338 VALUE set = ((struct set_foreach_arg *)arg)->set;
339 int ret = 0;
340 ret = set_foreach_check(RSET_TABLE(set), set_foreach_iter,
341 (st_data_t)arg, (st_data_t)Qundef);
342 if (ret) {
343 rb_raise(rb_eRuntimeError, "ret: %d, set modified during iteration", ret);
344 }
345 return Qnil;
346}
347
348static void
349set_iter(VALUE set, set_foreach_func *func, VALUE farg)
350{
351 struct set_foreach_arg arg;
352
353 if (RSET_EMPTY(set))
354 return;
355 arg.set = set;
356 arg.func = func;
357 arg.arg = farg;
358 if (RB_OBJ_FROZEN(set)) {
359 set_foreach_call((VALUE)&arg);
360 }
361 else {
362 set_iter_lev_inc(set);
363 rb_ensure(set_foreach_call, (VALUE)&arg, set_foreach_ensure, set);
364 }
365}
366
367NORETURN(static void no_new_item(void));
368static void
369no_new_item(void)
370{
371 rb_raise(rb_eRuntimeError, "can't add a new item into set during iteration");
372}
373
374static void
375set_compact_after_delete(VALUE set)
376{
377 if (!set_iterating_p(set)) {
378 set_compact_table(RSET_TABLE(set));
379 }
380}
381
382static int
383set_table_insert_wb(set_table *tab, VALUE set, VALUE key)
384{
385 if (tab->type != &identhash && rb_obj_class(key) == rb_cString && !RB_OBJ_FROZEN(key)) {
386 key = rb_hash_key_str(key);
387 }
388 int ret = set_insert(tab, (st_data_t)key);
389 if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
390 return ret;
391}
392
393static int
394set_insert_wb(VALUE set, VALUE key)
395{
396 return set_table_insert_wb(RSET_TABLE(set), set, key);
397}
398
399static VALUE
400set_alloc_with_size_and_type(VALUE klass, st_index_t size, const struct st_hash_type *type)
401{
402 VALUE set;
403 struct set_object *sobj;
404
405 set = TypedData_Make_Struct(klass, struct set_object, &set_data_type, sobj);
406 set_init_table_with_size(&sobj->table, type, size);
407
408 return set;
409}
410
411static VALUE
412set_alloc_with_size(VALUE klass, st_index_t size)
413{
414 return set_alloc_with_size_and_type(klass, size, &objhash);
415}
416
417static VALUE
418set_s_alloc(VALUE klass)
419{
420 return set_alloc_with_size(klass, 0);
421}
422
423bool
424rb_set_p(VALUE obj)
425{
426 return rb_typeddata_is_instance_of(obj, &set_data_type);
427}
428
429/*
430 * call-seq:
431 * Set[*objects] -> new_set
432 *
433 * Returns a new set populated with the given +objects+:
434 *
435 * Set[1, 'one', :one, 1.0, %w[a b c], {foo: 0, bar: 1}]
436 * # => Set[1, "one", :one, 1.0, ["a", "b", "c"], {foo: 0, bar: 1}]
437 * Set[Set[0, 1, 2], Set[%w[a b c]]]
438 * # => Set[Set[0, 1, 2], Set[["a", "b", "c"]]]
439 * Set[] # => Set[]
440 *
441 * Related: see {Methods for Creating a Set}[rdoc-ref:Set@Methods+for+Creating+a+Set].
442 *
443 */
444static VALUE
445set_s_create(int argc, VALUE *argv, VALUE klass)
446{
447 VALUE set = set_alloc_with_size(klass, argc);
448 set_table *table = RSET_TABLE(set);
449 int i;
450
451 for (i=0; i < argc; i++) {
452 set_table_insert_wb(table, set, argv[i]);
453 }
454
455 return set;
456}
457
458static VALUE
459set_s_inherited(VALUE klass, VALUE subclass)
460{
461 if (klass == rb_cSet) {
462 // When subclassing directly from Set, include the compatibility layer
463 rb_require("set/subclass_compatible.rb");
464 VALUE subclass_compatible = rb_const_get(klass, id_subclass_compatible);
465 rb_include_module(subclass, subclass_compatible);
466 rb_extend_object(subclass, rb_const_get(subclass_compatible, id_class_methods));
467 }
468 return Qnil;
469}
470
471static void
472check_set(VALUE arg)
473{
474 if (!rb_obj_is_kind_of(arg, rb_cSet)) {
475 rb_raise(rb_eArgError, "value must be a set");
476 }
477}
478
479static ID
480enum_method_id(VALUE other)
481{
482 if (rb_respond_to(other, id_each_entry)) {
483 return id_each_entry;
484 }
485 else if (rb_respond_to(other, id_each)) {
486 return id_each;
487 }
488 else {
489 rb_raise(rb_eArgError, "value must be enumerable");
490 }
491}
492
493static VALUE
494set_enum_size(VALUE set, VALUE args, VALUE eobj)
495{
496 return RSET_SIZE_NUM(set);
497}
498
499static VALUE
500set_initialize_without_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set))
501{
502 VALUE element = i;
503 set_insert_wb(set, element);
504 return element;
505}
506
507static VALUE
508set_initialize_with_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set))
509{
510 VALUE element = rb_yield(i);
511 set_insert_wb(set, element);
512 return element;
513}
514
515/*
516 * call-seq:
517 * Set.new(object = nil) -> new_set
518 * Set.new(object = nil) {|element| ... } -> new_set
519 *
520 * Returns a new set based on the given +object+,
521 * which must be an Enumerable or +nil+.
522 *
523 * With argument +object+ given as +nil+,
524 * returns a new empty set:
525 *
526 * Set.new # => Set[]
527 * Set.new { fail 'Cannot happen' } # => Set[] # Block not called.
528 *
529 * With no block given and enumerable argument +object+ given,
530 * populates the new set with the elements of +object+:
531 *
532 * Set.new(%w[ a b c ]) # => Set["a", "b", "c"]
533 * Set.new({foo: 0, bar: 1}) # => Set[[:foo, 0], [:bar, 1]]
534 * Set.new(4..10) # => Set[4, 5, 6, 7, 8, 9, 10]
535 * Set.new(Dir.new('lib')).take(5)
536 * # => [".", "..", "bundled_gems.rb", "bundler", "bundler.rb"]
537 * Set.new(File.new('doc/NEWS/NEWS-4.0.0.md')).take(3)
538 * # => ["# NEWS for Ruby 4.0.0\n", "\n", "This document is a list of user-visible feature changes\n"]
539 *
540 * With a block given and enumerable argument +object+ given,
541 * calls the block with each element of +object+;
542 * adds the block's return value to the new set:
543 *
544 * Set.new(4..10) {|i| i * 2 } # => Set[8, 10, 12, 14, 16, 18, 20]
545 *
546 * Related: see {Methods for Creating a Set}[rdoc-ref:Set@Methods+for+Creating+a+Set].
547 *
548 */
549static VALUE
550set_i_initialize(int argc, VALUE *argv, VALUE set)
551{
552 if (RBASIC(set)->flags & RSET_INITIALIZED) {
553 rb_raise(rb_eRuntimeError, "cannot reinitialize set");
554 }
555 RBASIC(set)->flags |= RSET_INITIALIZED;
556
557 VALUE other;
558 rb_check_arity(argc, 0, 1);
559
560 if (argc > 0 && (other = argv[0]) != Qnil) {
561 if (RB_TYPE_P(other, T_ARRAY)) {
562 rb_len_t i;
563 int block_given = rb_block_given_p();
564 set_table *into = RSET_TABLE(set);
565 for (i=0; i<RARRAY_LEN(other); i++) {
566 VALUE key = RARRAY_AREF(other, i);
567 if (block_given) key = rb_yield(key);
568 set_table_insert_wb(into, set, key);
569 }
570 }
571 else {
572 rb_block_call(other, enum_method_id(other), 0, 0,
573 rb_block_given_p() ? set_initialize_with_block : set_initialize_without_block,
574 set);
575 }
576 }
577
578 return set;
579}
580
581/* :nodoc: */
582static VALUE
583set_i_initialize_copy(VALUE set, VALUE other)
584{
585 if (set == other) return set;
586
587 if (set_iterating_p(set)) {
588 rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
589 }
590
591 struct set_object *sobj;
592 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
593
594 set_free_embedded_table(&sobj->table);
595 set_copy(&sobj->table, RSET_TABLE(other));
596 rb_gc_writebarrier_remember(set);
597
598 return set;
599}
600
601static int
602set_inspect_i(st_data_t key, st_data_t arg)
603{
604 VALUE *args = (VALUE*)arg;
605 VALUE str = args[0];
606 if (args[1] == Qtrue) {
607 rb_str_buf_cat_ascii(str, ", ");
608 }
609 else {
610 args[1] = Qtrue;
611 }
613
614 return ST_CONTINUE;
615}
616
617static VALUE
618set_inspect(VALUE set, VALUE dummy, int recur)
619{
620 VALUE str;
621 VALUE klass_name = rb_class_path(CLASS_OF(set));
622
623 if (recur) {
624 str = rb_sprintf("%"PRIsVALUE"[...]", klass_name);
626 }
627
628 str = rb_sprintf("%"PRIsVALUE"[", klass_name);
629 VALUE args[2] = {str, Qfalse};
630 set_iter(set, set_inspect_i, (st_data_t)args);
631 rb_str_buf_cat2(str, "]");
632
633 return str;
634}
635
636/*
637 * call-seq:
638 * inspect -> string
639 *
640 * Returns a string representation of +self+:
641 *
642 * Set[*%w[foo bar], {foo: 0, bar: 1}].inspect
643 * # => "Set[\"foo\", \"bar\", {foo: 0, bar: 1}]"
644 *
645 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
646 */
647static VALUE
648set_i_inspect(VALUE set)
649{
650 return rb_exec_recursive(set_inspect, set, 0);
651}
652
653static int
654set_to_a_i(st_data_t key, st_data_t arg)
655{
656 rb_ary_push((VALUE)arg, (VALUE)key);
657 return ST_CONTINUE;
658}
659
660/*
661 * call-seq:
662 * to_a -> array
663 *
664 * Returns an array containing the elements of +self+:
665 *
666 * Set[1, 2].to_a # => [1, 2]
667 * Set[1, 'c', :s].to_a # => [1, "c", :s]
668 *
669 * Related: {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
670 */
671static VALUE
672set_i_to_a(VALUE set)
673{
674 st_index_t size = RSET_SIZE(set);
675 VALUE ary = rb_ary_new_capa(size);
676
677 if (size == 0) return ary;
678
679 if (ST_DATA_COMPATIBLE_P(VALUE)) {
680 RARRAY_PTR_USE(ary, ptr, {
681 size = set_keys(RSET_TABLE(set), ptr, size);
682 });
683 rb_gc_writebarrier_remember(ary);
684 rb_ary_set_len(ary, size);
685 }
686 else {
687 set_iter(set, set_to_a_i, (st_data_t)ary);
688 }
689 return ary;
690}
691
692/*
693 * call-seq:
694 * to_set {|element| ... } -> new_set
695 * to_set -> new_set
696 *
697 * Returns a new set containing the elements of +self+;
698 * with a block given, the set contains the block's return values instead:
699 *
700 * [3, 1, 2, 1].to_set # => Set[3, 1, 2]
701 * [3, 1, 2, 1].to_set {|i| -i } # => Set[-3, -1, -2]
702 */
703static VALUE
704enum_to_set(VALUE obj)
705{
706 return rb_funcall_passing_block(rb_cSet, id_new, 1, &obj);
707}
708
709/*
710 * call-seq:
711 * to_set {|element| ... } -> new_set
712 * to_set -> self or new_set
713 *
714 * With a block given, creates and returns a new set;
715 * calls the block with each element of +self+,
716 * and adds the block's returns value to the new set:
717 *
718 * set = Set[*0..9] # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
719 * set.to_set {|i| i * 2 } # => Set[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
720 *
721 * With no block given, when +self+ is an instance of +Set+,
722 * returns +self+:
723 *
724 * set = Set[*0..9]
725 * set.to_set
726 * set.to_set.equal?(set) # => true
727 *
728 * With no block given, when +self+ is an instance of a subclass of +Set+,
729 * returns a set containing the elements of +self+:
730 *
731 * class MySet < Set; end
732 * my_set = MySet[*0..9] # => #<MySet: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}>
733 * set = my_set.to_set # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
734 *
735 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
736 */
737static VALUE
738set_i_to_set(VALUE set)
739{
741 return set;
742 }
743
744 return enum_to_set(set);
745}
746
747/*
748 * call-seq:
749 * join(separator = $,) -> string
750 *
751 * Returns the string formed by joining the string-converted elements of +self+
752 * with the given +separator+ (defaults to <tt>$,</tt>):
753 *
754 * $, # => nil
755 * Set[*%w[foo bar baz]].join
756 * # => "foobarbaz"
757 * Set[*%w[foo bar baz]].join(', ')
758 * # => "foo, bar, baz"
759 *
760 * Flattens nested arrays:
761 *
762 * Set[[:foo, [:bar, [:baz, :bat]]]].join
763 * # => "foobarbazbat"
764 *
765 * Does not flatten nested sets:
766 *
767 * Set[Set[:foo, Set[:bar, Set[:baz, :bat]]]].join
768 * # => "Set[:foo, Set[:bar, Set[:baz, :bat]]]"
769 *
770 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
771 */
772static VALUE
773set_i_join(int argc, VALUE *argv, VALUE set)
774{
775 rb_check_arity(argc, 0, 1);
776 return rb_ary_join(set_i_to_a(set), argc == 0 ? Qnil : argv[0]);
777}
778
779/*
780 * call-seq:
781 * add(object) -> self
782 *
783 * Adds the given +object+ to +self+; returns +self+:
784 *
785 * set = Set[0, 1, 2]
786 * set.add(%w[a b c]) # => Set[0, 1, 2, ["a", "b", "c"]]
787 * set.add(0) # => Set[0, 1, 2, ["a", "b", "c"]]
788 *
789 * Related: see {Methods for Assigning}[rdoc-ref:Set@Methods+for+Assigning].
790 */
791static VALUE
792set_i_add(VALUE set, VALUE item)
793{
794 rb_check_frozen(set);
795 if (set_iterating_p(set)) {
796 if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
797 no_new_item();
798 }
799 }
800 else {
801 set_insert_wb(set, item);
802 }
803 return set;
804}
805
806/*
807 * call-seq:
808 * add?(object) -> self or nil
809 *
810 * Like #add, but returns +nil+ if the given +object+ is already in +self+:
811 *
812 * set = Set[0, 1, 2]
813 * set.add?(:foo) # => Set[0, 1, 2, :foo]
814 * set.add?(0..9) # => Set[0, 1, 2, :foo, 0..9]
815 * set.add?(2) # => nil
816 *
817 * Related: see {Methods for Assigning}[rdoc-ref:Set@Methods+for+Assigning].
818 */
819static VALUE
820set_i_add_p(VALUE set, VALUE item)
821{
822 rb_check_frozen(set);
823 if (set_iterating_p(set)) {
824 if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
825 no_new_item();
826 }
827 return Qnil;
828 }
829 else {
830 return set_insert_wb(set, item) ? Qnil : set;
831 }
832}
833
834/*
835 * call-seq:
836 * delete(object) -> self
837 *
838 * Removes the given +object+ from +self+ if +self+ includes the object;
839 * returns +self+:
840 *
841 * set = Set[0, 'zero', :zero]
842 * set.delete(0) # => Set["zero", :zero]
843 * set.delete(:nosuch) # => Set["zero", :zero]
844 *
845 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
846 */
847static VALUE
848set_i_delete(VALUE set, VALUE item)
849{
850 st_data_t item_data = (st_data_t)item;
851 rb_check_frozen(set);
852 if (set_table_delete(RSET_TABLE(set), &item_data)) {
853 set_compact_after_delete(set);
854 }
855 return set;
856}
857
858/*
859 * call-seq:
860 * delete?(object) -> self or nil
861 *
862 * Like #delete, but returns +nil+ if the object is not in +self+:
863 *
864 * set = Set[0, 'zero', :zero]
865 * set.delete?(0) # => Set["zero", :zero]
866 * set.delete?(0) # => nil
867 *
868 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
869 */
870static VALUE
871set_i_delete_p(VALUE set, VALUE item)
872{
873 st_data_t item_data = (st_data_t)item;
874 rb_check_frozen(set);
875 if (set_table_delete(RSET_TABLE(set), &item_data)) {
876 set_compact_after_delete(set);
877 return set;
878 }
879 return Qnil;
880}
881
882static int
883set_delete_if_i(st_data_t key, st_data_t dummy)
884{
885 return RTEST(rb_yield((VALUE)key)) ? ST_DELETE : ST_CONTINUE;
886}
887
888/*
889 * call-seq:
890 * delete_if {|element| ... } -> self
891 * delete_if -> enumerator
892 *
893 * With a block given, calls the block with each element in +self+;
894 * removes the element if the block returns a truthy value:
895 *
896 * set = Set[*0..9]
897 * # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
898 * set.delete_if {|element| element.even? }
899 * # => Set[1, 3, 5, 7, 9]
900 *
901 * With no block given, returns an Enumerator.
902 *
903 * Related: {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
904 */
905static VALUE
906set_i_delete_if(VALUE set)
907{
908 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
909 rb_check_frozen(set);
910 set_iter(set, set_delete_if_i, 0);
911 set_compact_after_delete(set);
912 return set;
913}
914
915/*
916 * call-seq:
917 * reject! {|element| ... } -> self or nil
918 * reject! -> enumerator
919 *
920 * With a block given, like #delete_if, but returns +nil+ if no changes were made:
921 *
922 * set = Set[*0..9] # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
923 * set.reject! {|element| element.even? } # => Set[1, 3, 5, 7, 9]
924 * set.reject! {|element| element.even? } # => nil
925 * set.reject! {|element| element.odd? } # => Set[]
926 *
927 * With no block given, returns an Enumerator.
928 *
929 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
930 */
931static VALUE
932set_i_reject(VALUE set)
933{
934 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
935 rb_check_frozen(set);
936
937 set_table *table = RSET_TABLE(set);
938 size_t n = set_table_size(table);
939 set_iter(set, set_delete_if_i, 0);
940
941 if (n == set_table_size(table)) return Qnil;
942
943 set_compact_after_delete(set);
944 return set;
945}
946
947static int
948set_classify_i(st_data_t key, st_data_t tmp)
949{
950 VALUE* args = (VALUE*)tmp;
951 VALUE hash = args[0];
952 VALUE hash_key = rb_yield(key);
953 VALUE set = rb_hash_lookup2(hash, hash_key, Qundef);
954 if (set == Qundef) {
955 set = set_s_alloc(args[1]);
956 if (RTEST(args[2])) {
957 set_i_compare_by_identity(set);
958 }
959 rb_hash_aset(hash, hash_key, set);
960 }
961 set_i_add(set, key);
962
963 return ST_CONTINUE;
964}
965
966/*
967 * call-seq:
968 * classify {|element| ... } -> hash
969 * classify -> enumerator
970 *
971 * With a block given, calls the block with each element of +self+;
972 * returns a hash whose keys are the block's return values.
973 * The value for each key is a set containing the elements
974 * for which the block returned that key.
975 *
976 * This example classifies elements by their classes:
977 *
978 * set = Set[*(5..7), *%w[foo bar]] # => Set[5, 6, 7, "foo", "bar"]
979 * set.classify {|element| element.class }
980 * # => {Integer => Set[5, 6, 7], String => Set["foo", "bar"]}
981 *
982 * With no block given, returns an Enumerator.
983 *
984 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
985 */
986static VALUE
987set_i_classify(VALUE set)
988{
989 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
990 VALUE args[3];
991 args[0] = rb_hash_new();
992 args[1] = rb_obj_class(set);
993 args[2] = RBOOL(RSET_COMPARE_BY_IDENTITY(set));
994 set_iter(set, set_classify_i, (st_data_t)args);
995 return args[0];
996}
997
998// Union-find with path compression
999static rb_len_t
1000set_divide_union_find_root(rb_len_t *uf_parents, rb_len_t index, rb_len_t *tmp_array)
1001{
1002 rb_len_t root = uf_parents[index];
1003 rb_len_t update_size = 0;
1004 while (root != index) {
1005 tmp_array[update_size++] = index;
1006 index = root;
1007 root = uf_parents[index];
1008 }
1009 for (rb_len_t j = 0; j < update_size; j++) {
1010 rb_len_t idx = tmp_array[j];
1011 uf_parents[idx] = root;
1012 }
1013 return root;
1014}
1015
1016static void
1017set_divide_union_find_merge(rb_len_t *uf_parents, rb_len_t i, rb_len_t j, rb_len_t *tmp_array)
1018{
1019 rb_len_t root_i = set_divide_union_find_root(uf_parents, i, tmp_array);
1020 rb_len_t root_j = set_divide_union_find_root(uf_parents, j, tmp_array);
1021 if (root_i != root_j) uf_parents[root_j] = root_i;
1022}
1023
1024static VALUE
1025set_divide_arity2(VALUE set)
1026{
1027 VALUE tmp, uf;
1028 rb_len_t size, *uf_parents, *tmp_array;
1029 VALUE set_class = rb_obj_class(set);
1030 VALUE items = set_i_to_a(set);
1031 rb_ary_freeze(items);
1032 size = RARRAY_LEN(items);
1033 tmp_array = ALLOCV_N(rb_len_t, tmp, size);
1034 uf_parents = ALLOCV_N(rb_len_t, uf, size);
1035 for (rb_len_t i = 0; i < size; i++) {
1036 uf_parents[i] = i;
1037 }
1038 for (rb_len_t i = 0; i < size - 1; i++) {
1039 VALUE item1 = RARRAY_AREF(items, i);
1040 for (rb_len_t j = i + 1; j < size; j++) {
1041 VALUE item2 = RARRAY_AREF(items, j);
1042 if (RTEST(rb_yield_values(2, item1, item2)) &&
1043 RTEST(rb_yield_values(2, item2, item1))) {
1044 set_divide_union_find_merge(uf_parents, i, j, tmp_array);
1045 }
1046 }
1047 }
1048 VALUE final_set = set_s_create(0, 0, rb_cSet);
1049 VALUE hash = rb_hash_new();
1050 for (rb_len_t i = 0; i < size; i++) {
1051 VALUE v = RARRAY_AREF(items, i);
1052 rb_len_t root = set_divide_union_find_root(uf_parents, i, tmp_array);
1053 VALUE subset = rb_hash_aref(hash, LEN2NUM(root));
1054 if (subset == Qnil) {
1055 subset = set_s_alloc(set_class);
1056 if (RSET_COMPARE_BY_IDENTITY(set)) {
1057 set_i_compare_by_identity(subset);
1058 }
1059 rb_hash_aset(hash, LEN2NUM(root), subset);
1060 set_i_add(final_set, subset);
1061 }
1062 set_i_add(subset, v);
1063 }
1064 ALLOCV_END(tmp);
1065 ALLOCV_END(uf);
1066 return final_set;
1067}
1068
1069static void set_merge_enum_into(VALUE set, VALUE arg);
1070
1071/*
1072 * call-seq:
1073 * divide {|ele| ... } -> new_set
1074 * divide {|ele0, ele1| ... } -> new_set
1075 * divide -> enumerator
1076 *
1077 * With a block given, returns a set of sets.
1078 *
1079 * For a block that accepts one argument,
1080 * calls the block with each element;
1081 * creates a set for each distinct block return value:
1082 *
1083 * set = Set[*0..9]
1084 * # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1085 * # Divide into mod 3 sets.
1086 * set.divide {|ele| ele % 3 }
1087 * # => Set[Set[0, 3, 6, 9], Set[1, 4, 7], Set[2, 5, 8]]
1088 * # Divide into mod 5 sets.
1089 * set.divide {|ele| ele % 5 }
1090 * # => Set[Set[0, 5], Set[1, 6], Set[2, 7], Set[3, 8], Set[4, 9]]
1091 *
1092 * Set[0].divide {|ele| anything } # => Set[Set[0]]
1093 * Set[].divide {|ele| not called } # => Set[]
1094 *
1095 * For a block that accepts two arguments,
1096 * divides +self+ into connected components based on the binary
1097 * relation defined by the block, calling the block with each 2-element
1098 * permutation of the elements of +self+:
1099 *
1100 * set = Set[*0..9]
1101 * # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1102 * # Divide into mod 2 sets.
1103 * set.divide {|i, j| (i - j) % 2 == 0 }
1104 * # => Set[Set[0, 2, 4, 6, 8], Set[1, 3, 5, 7, 9]]
1105 * # Divide into mod 3 sets.
1106 * set.divide {|i, j| (i - j) % 3 == 0 }
1107 * # => Set[Set[0, 3, 6, 9], Set[1, 4, 7], Set[2, 5, 8]]
1108 *
1109 * Set[0].divide {|i, j| not called } # => Set[Set[0]]
1110 * Set[].divide {|i, j| not called } # => Set[]
1111 *
1112 * With no block given, returns an Enumerator.
1113 *
1114 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
1115 */
1116static VALUE
1117set_i_divide(VALUE set)
1118{
1119 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1120
1121 if (rb_block_arity() == 2) {
1122 return set_divide_arity2(set);
1123 }
1124
1125 VALUE values = rb_hash_values(set_i_classify(set));
1126 set = set_alloc_with_size(rb_cSet, RARRAY_LEN(values));
1127 set_merge_enum_into(set, values);
1128 return set;
1129}
1130
1131static int
1132set_clear_i(st_data_t key, st_data_t dummy)
1133{
1134 return ST_DELETE;
1135}
1136
1137/*
1138 * call-seq:
1139 * clear -> self
1140 *
1141 * Returns +self+ with all elements removed:
1142 *
1143 * Set[1, :one, 'one', 1.0].clear # => Set[]
1144 *
1145 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
1146 */
1147static VALUE
1148set_i_clear(VALUE set)
1149{
1150 rb_check_frozen(set);
1151 if (RSET_SIZE(set) == 0) return set;
1152 if (set_iterating_p(set)) {
1153 set_iter(set, set_clear_i, 0);
1154 }
1155 else {
1156 set_table_clear(RSET_TABLE(set));
1157 set_compact_after_delete(set);
1158 }
1159 return set;
1160}
1161
1163 VALUE set;
1164 VALUE other_set;
1165 VALUE new_set;
1166 set_table *into;
1167 set_table *other;
1168};
1169
1170static int
1171set_intersection_i(st_data_t key, st_data_t tmp)
1172{
1173 struct set_intersection_data *data = MEMO_FOR(struct set_intersection_data, tmp);
1174 if (set_table_lookup(data->other, key)) {
1175 set_table_insert_wb(data->into, data->set, key);
1176 }
1177
1178 return ST_CONTINUE;
1179}
1180
1181static VALUE
1182set_intersection_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, data))
1183{
1184 set_intersection_i((st_data_t)i, (st_data_t)data);
1185 return i;
1186}
1187
1188/*
1189 * call-seq:
1190 * self & enumerable -> new_set
1191 *
1192 * Returns a new set containing the {intersection}[https://en.wikipedia.org/wiki/Intersection_(set_theory)]
1193 * of +self+ and +enumerable+;
1194 * that is, containing all elements common to both, with no duplicates.
1195 * Argument +enumerable+ must be an Enumerable object:
1196 *
1197 * set = Set[*(0..6), *%w[ a b c]] # => Set[0, 1, 2, 3, 4, 5, 6, "a", "b", "c"]
1198 * set & ['c', 6, 8, 4] # => Set["c", 6, 4]
1199 * set & [:foo, :bar] # => Set[] # No elements in common.
1200 *
1201 * Related: see {Methods for Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations].
1202 */
1203static VALUE
1204set_i_intersection(VALUE set, VALUE other)
1205{
1206 VALUE new_set = set_s_alloc(rb_obj_class(set));
1207 if (RSET_COMPARE_BY_IDENTITY(set)) {
1208 set_i_compare_by_identity(new_set);
1209 }
1210 set_table *stable = RSET_TABLE(set);
1211 set_table *ntable = RSET_TABLE(new_set);
1212 VALUE data;
1213
1214 if (rb_obj_is_kind_of(other, rb_cSet)) {
1215 set_table *otable = RSET_TABLE(other);
1216 if (set_table_size(stable) >= set_table_size(otable)) {
1217 /* Swap so we iterate over the smaller set */
1218 otable = stable;
1219 set = other;
1220 }
1221
1222 *NEW_PARTIAL_MEMO_FOR(struct set_intersection_data, data, into) = (struct set_intersection_data) {
1223 .set = new_set,
1224 .other_set = other,
1225 .new_set = new_set,
1226 .into = ntable,
1227 .other = otable,
1228 };
1229 set_iter(set, set_intersection_i, (st_data_t)data);
1230 }
1231 else {
1232 *NEW_PARTIAL_MEMO_FOR(struct set_intersection_data, data, into) = (struct set_intersection_data) {
1233 .set = new_set,
1234 .other_set = other,
1235 .new_set = new_set,
1236 .into = ntable,
1237 .other = stable,
1238 };
1239 rb_block_call(other, enum_method_id(other), 0, 0, set_intersection_block, data);
1240 }
1241 RB_GC_GUARD(data);
1242
1243 return new_set;
1244}
1245
1246/*
1247 * call-seq:
1248 * include?(object) -> true or false
1249 *
1250 * Returns whether the given +object+ is an element of +self+:
1251 *
1252 * set = Set[0, :zero, '0']
1253 * set.include?('0') # => true
1254 * set.include?('zero') # => false
1255 *
1256 * Tests equality using `hash` and `eql?`.
1257 *
1258 * Aliased as #===, which means that sets may be used in +case+ expressions:
1259 *
1260 * case :apple
1261 * when Set[:potato, :carrot]
1262 * 'vegetable'
1263 * when Set[:apple, :banana]
1264 * 'fruit'
1265 * else
1266 * 'unknown'
1267 * end
1268 * # => "fruit"
1269 *
1270 * Related: see {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
1271 */
1272static VALUE
1273set_i_include(VALUE set, VALUE item)
1274{
1275 return RBOOL(RSET_IS_MEMBER(set, item));
1276}
1277
1279 VALUE set;
1280 set_table *into;
1281};
1282
1283static int
1284set_merge_i(st_data_t key, st_data_t data)
1285{
1286 struct set_merge_args *args = (struct set_merge_args *)data;
1287 set_table_insert_wb(args->into, args->set, key);
1288 return ST_CONTINUE;
1289}
1290
1291static VALUE
1292set_merge_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set))
1293{
1294 VALUE element = key;
1295 set_insert_wb(set, element);
1296 return element;
1297}
1298
1299static void
1300set_merge_enum_into(VALUE set, VALUE arg)
1301{
1302 if (rb_obj_is_kind_of(arg, rb_cSet)) {
1303 struct set_merge_args args = {
1304 .set = set,
1305 .into = RSET_TABLE(set)
1306 };
1307 set_iter(arg, set_merge_i, (st_data_t)&args);
1308 }
1309 else if (RB_TYPE_P(arg, T_ARRAY)) {
1310 rb_len_t i;
1311 set_table *into = RSET_TABLE(set);
1312 for (i=0; i<RARRAY_LEN(arg); i++) {
1313 set_table_insert_wb(into, set, RARRAY_AREF(arg, i));
1314 }
1315 RB_GC_GUARD(arg);
1316 }
1317 else {
1318 rb_block_call(arg, enum_method_id(arg), 0, 0, set_merge_block, set);
1319 }
1320}
1321
1322/*
1323 * call-seq:
1324 * merge(*enumerables, **nil) -> self
1325 *
1326 * Adds each element of each of the given +enumerables+ to +self+;
1327 * returns +self+:
1328 *
1329 * set = Set[*0..2] # => Set[0, 1, 2]
1330 * set.merge('a'..'c', %w[foo bar]) # => Set[0, 1, 2, "a", "b", "c", "foo", "bar"]
1331 * set.merge('a'..'c', %w[foo bar]) # => Set[0, 1, 2, "a", "b", "c", "foo", "bar"]
1332 *
1333 * Related: see {Methods for Assigning}[rdoc-ref:Set@Methods+for+Assigning].
1334 *
1335 */
1336static VALUE
1337set_i_merge(int argc, VALUE *argv, VALUE set)
1338{
1339 if (rb_keyword_given_p()) {
1340 rb_raise(rb_eArgError, "no keywords accepted");
1341 }
1342
1343 if (set_iterating_p(set)) {
1344 rb_raise(rb_eRuntimeError, "cannot add to set during iteration");
1345 }
1346
1347 rb_check_frozen(set);
1348
1349 int i;
1350
1351 for (i=0; i < argc; i++) {
1352 set_merge_enum_into(set, argv[i]);
1353 }
1354
1355 return set;
1356}
1357
1358static VALUE
1359set_reset_table_with_type(VALUE set, const struct st_hash_type *type)
1360{
1361 rb_check_frozen(set);
1362
1363 struct set_object *sobj;
1364 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
1365 set_table *old = &sobj->table;
1366
1367 size_t size = set_table_size(old);
1368 if (size > 0) {
1369 set_table *new = set_init_table_with_size(NULL, type, size);
1370 struct set_merge_args args = {
1371 .set = set,
1372 .into = new
1373 };
1374 set_iter(set, set_merge_i, (st_data_t)&args);
1375 set_free_embedded_table(&sobj->table);
1376 memcpy(&sobj->table, new, sizeof(*new));
1377 SIZED_FREE(new);
1378 }
1379 else {
1380 sobj->table.type = type;
1381 }
1382
1383 return set;
1384}
1385
1386/*
1387 * call-seq:
1388 * compare_by_identity -> self
1389 *
1390 * Sets +self+ to compare by object identity
1391 * (rather than by object content, which is the initial setting);
1392 * returns +self+:
1393 *
1394 * set = Set.new
1395 * set.compare_by_identity
1396 * str = +"foo"
1397 * set.add(str)
1398 * # => Set["foo"]
1399 * set.include?(str)
1400 * # => true
1401 * set.add(str)
1402 * # => Set["foo"])
1403 * set.include?(+"foo")
1404 * # => false
1405 * set.add(+"foo")
1406 * # => Set["foo", "foo"])
1407 *
1408 * Once set, the compare-by-identity property may not be unset.
1409 *
1410 * Related: #compare_by_identity?.
1411 */
1412static VALUE
1413set_i_compare_by_identity(VALUE set)
1414{
1415 if (RSET_COMPARE_BY_IDENTITY(set)) return set;
1416
1417 if (set_iterating_p(set)) {
1418 rb_raise(rb_eRuntimeError, "compare_by_identity during iteration");
1419 }
1420
1421 return set_reset_table_with_type(set, &identhash);
1422}
1423
1424/*
1425 * call-seq:
1426 * compare_by_identity? -> true or false
1427 *
1428 * Returns whether +self+ compares elements by object identity
1429 * (rather than by content):
1430 *
1431 * set = Set[]
1432 * set.compare_by_identity? # => false
1433 * set.compare_by_identity
1434 * set.compare_by_identity? # => true
1435 *
1436 * Related: #compare_by_identity;
1437 * see also {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
1438 */
1439static VALUE
1440set_i_compare_by_identity_p(VALUE set)
1441{
1442 return RBOOL(RSET_COMPARE_BY_IDENTITY(set));
1443}
1444
1445/*
1446 * call-seq:
1447 * size -> integer
1448 *
1449 * Returns the number of elements in +self+:
1450 *
1451 * Set[*0..9].size # => 10
1452 *
1453 * Related: see {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
1454 */
1455static VALUE
1456set_i_size(VALUE set)
1457{
1458 return RSET_SIZE_NUM(set);
1459}
1460
1461/*
1462 * call-seq:
1463 * empty? -> true or false
1464 *
1465 * Returns whether +self+ contains no elements:
1466 *
1467 * Set[].empty? # => true
1468 * Set[0].empty? # => false
1469 *
1470 * Related: see {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
1471 */
1472static VALUE
1473set_i_empty(VALUE set)
1474{
1475 return RBOOL(RSET_EMPTY(set));
1476}
1477
1478static int
1479set_xor_i(st_data_t key, st_data_t data)
1480{
1481 VALUE element = (VALUE)key;
1482 VALUE set = (VALUE)data;
1483 set_table *table = RSET_TABLE(set);
1484 if (set_table_insert_wb(table, set, element)) {
1485 set_table_delete(table, &element);
1486 }
1487 return ST_CONTINUE;
1488}
1489
1490/*
1491 * call-seq:
1492 * self ^ enumerable -> new_set
1493 *
1494 * Returns a new set containing
1495 * the {exclusive OR}[https://en.wikipedia.org/wiki/Exclusive_or]
1496 * of +self+ and the given +enumerable+;
1497 * that is, containing each element that is in either +self+ or +enumerable+,
1498 * but not in both:
1499 *
1500 * set = Set[0, 1, 2]
1501 * set ^ Set[1, 2, 3] # => Set[0, 3]
1502 * set ^ Set[2, 1] # => Set[0]
1503 * set ^ Set[2, *('a'..'c')] # => Set[0, 1, "a", "b", "c"]
1504 * set ^ Set[2, 1, 0] # => Set[]
1505 *
1506 * For \Set +set+ and \Enumerable +enumerable+, these expressions are equivalent:
1507 *
1508 * set ^ enumerable
1509 * ((set | enumerable) - (set & enumerable))
1510 *
1511 * Related: see {Methods for Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations].
1512 */
1513static VALUE
1514set_i_xor(VALUE set, VALUE other)
1515{
1516 VALUE new_set = rb_obj_dup(set);
1517
1518 if (rb_obj_is_kind_of(other, rb_cSet)) {
1519 set_iter(other, set_xor_i, (st_data_t)new_set);
1520 }
1521 else {
1522 VALUE tmp = set_s_alloc(rb_obj_class(new_set));
1523 if (RSET_COMPARE_BY_IDENTITY(new_set)) {
1524 set_i_compare_by_identity(tmp);
1525 }
1526 set_merge_enum_into(tmp, other);
1527 set_iter(tmp, set_xor_i, (st_data_t)new_set);
1528 }
1529 set_compact_after_delete(set);
1530
1531 return new_set;
1532}
1533
1534/*
1535 * call-seq:
1536 * self | enumerable -> new_set
1537 *
1538 * Returns a new set containing
1539 * the {union}[https://en.wikipedia.org/wiki/Union_(set_theory)]
1540 * of +self+ and the given +enumerable+;
1541 * that is, containing the elements of both +self+ and +enumerable+.
1542 *
1543 * set = Set[0, 1, 2]
1544 * set | Set[2, 1, 'a'] # => Set[0, 1, 2, "a"]
1545 * set | set # => Set[0, 1, 2]
1546 *
1547 * Related: see {Methods for Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations].
1548 */
1549static VALUE
1550set_i_union(VALUE set, VALUE other)
1551{
1552 set = rb_obj_dup(set);
1553 set_merge_enum_into(set, other);
1554 return set;
1555}
1556
1557static int
1558set_remove_i(st_data_t key, st_data_t from)
1559{
1560 st_data_t key_data = (st_data_t)key;
1561 set_table_delete((struct set_table *)from, &key_data);
1562 return ST_CONTINUE;
1563}
1564
1565static VALUE
1566set_remove_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set))
1567{
1568 st_data_t key_data = (st_data_t)key;
1569 rb_check_frozen(set);
1570 set_table_delete(RSET_TABLE(set), &key_data);
1571 return (VALUE)key_data;
1572}
1573
1574static void
1575set_remove_enum_from(VALUE set, VALUE arg)
1576{
1577 if (rb_obj_is_kind_of(arg, rb_cSet)) {
1578 set_iter(arg, set_remove_i, (st_data_t)RSET_TABLE(set));
1579 }
1580 else {
1581 rb_block_call(arg, enum_method_id(arg), 0, 0, set_remove_block, set);
1582 }
1583 set_compact_after_delete(set);
1584}
1585
1586/*
1587 * call-seq:
1588 * subtract(enumerable) -> self
1589 *
1590 * Deletes from +self+ every element found in the given +enumerable+;
1591 * returns +self+:
1592 *
1593 * set = Set[*0..9] # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1594 * set.subtract(5..14) # => Set[0, 1, 2, 3, 4]
1595 * set.subtract(Set[6, 2]) # => Set[0, 1, 3, 4]
1596 *
1597 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
1598 */
1599static VALUE
1600set_i_subtract(VALUE set, VALUE other)
1601{
1602 rb_check_frozen(set);
1603 set_remove_enum_from(set, other);
1604 return set;
1605}
1606
1607/*
1608 * call-seq:
1609 * self - enumerable -> new_set
1610 *
1611 * Returns a new set containing the
1612 * {difference}[https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement]
1613 * of +self+ and argument +enumerable+;
1614 * that is, containing all elements in +self+ that are not in +enumerable+.
1615 *
1616 *
1617 * set = Set[*(0..6), *%w[ a b c]] # => Set[0, 1, 2, 3, 4, 5, 6, "a", "b", "c"]
1618 * set - ['b', 6, 4, 1] # => Set[0, 2, 3, 5, "a", "c"]
1619 * set - ['d', 7, 9] # => Set[0, 1, 2, 3, 4, 5, 6, "a", "b", "c"]
1620 *
1621 * Related: see {Methods for Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations].
1622 */
1623static VALUE
1624set_i_difference(VALUE set, VALUE other)
1625{
1626 return set_i_subtract(rb_obj_dup(set), other);
1627}
1628
1629static int
1630set_each_i(st_data_t key, st_data_t dummy)
1631{
1632 rb_yield(key);
1633 return ST_CONTINUE;
1634}
1635
1636/*
1637 * call-seq:
1638 * each {|element| ... } -> self
1639 * each -> enumerator
1640 *
1641 * With a block given, calls the block once for each element in the set,
1642 * passing the element as a parameter;
1643 * returns +self+:
1644 *
1645 * sum = 0
1646 * Set[1, 2, 3].each {|i| sum += i }
1647 * sum # => 6
1648 *
1649 * With no block given, returns an Enumerator.
1650 */
1651static VALUE
1652set_i_each(VALUE set)
1653{
1654 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1655 set_iter(set, set_each_i, 0);
1656 return set;
1657}
1658
1659static int
1660set_collect_i(st_data_t key, st_data_t data)
1661{
1662 set_insert_wb((VALUE)data, rb_yield((VALUE)key));
1663 return ST_CONTINUE;
1664}
1665
1666/*
1667 * call-seq:
1668 * collect! {|element| ... } -> self
1669 * collect! -> enumerator
1670 *
1671 * With a block given, calls the block with each element in +self+;
1672 * replaces the element with the block's return value:
1673 *
1674 * Set[1, :one, 'one', 1.0].collect! {|element| element.class }
1675 * # => Set[Integer, Symbol, String, Float]
1676 *
1677 * With no block given, returns an Enumerator.
1678 *
1679 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
1680 */
1681static VALUE
1682set_i_collect(VALUE set)
1683{
1684 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1685 rb_check_frozen(set);
1686
1687 VALUE new_set = set_s_alloc(rb_obj_class(set));
1688 if (RSET_COMPARE_BY_IDENTITY(set)) {
1689 set_i_compare_by_identity(new_set);
1690 }
1691 set_iter(set, set_collect_i, (st_data_t)new_set);
1692 set_i_initialize_copy(set, new_set);
1693
1694 return set;
1695}
1696
1697static int
1698set_keep_if_i(st_data_t key, st_data_t into)
1699{
1700 if (!RTEST(rb_yield((VALUE)key))) {
1701 set_table_delete((set_table *)into, &key);
1702 }
1703 return ST_CONTINUE;
1704}
1705
1706/*
1707 * call-seq:
1708 * keep_if {|element| ... } -> self
1709 * keep_if -> enumerator
1710 *
1711 * With a block given,
1712 * calls the block with each element in +self+,
1713 * deleting the element if the block returns +false+ or +nil+;
1714 * returns +self+:
1715 *
1716 * set = Set[*0..9] # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1717 * set.keep_if {|i| i.even? } # => Set[0, 2, 4, 6, 8]
1718 * set.keep_if {|i| i.odd? } # => Set[]
1719 *
1720 * With no block given, returns an Enumerator.
1721 *
1722 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
1723 */
1724static VALUE
1725set_i_keep_if(VALUE set)
1726{
1727 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1728 rb_check_frozen(set);
1729
1730 set_iter(set, set_keep_if_i, (st_data_t)RSET_TABLE(set));
1731 set_compact_after_delete(set);
1732
1733 return set;
1734}
1735
1736/*
1737 * call-seq:
1738 * select! {|element| ... } -> self or nil
1739 * select! -> enumerator
1740 *
1741 * With a block given, like #keep_if, but returns +nil+ if no changes were made:
1742 *
1743 * set = Set[*0..9] # => Set[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1744 * set.select! {|i| i.even? } # => Set[0, 2, 4, 6, 8]
1745 * set.select! {|i| i.even? } # => nil
1746 * set.select! {|i| i.odd? } # => Set[]
1747 *
1748 * With no block given, returns an Enumerator.
1749 *
1750 * Related: see {Methods for Deleting}[rdoc-ref:Set@Methods+for+Deleting].
1751 */
1752static VALUE
1753set_i_select(VALUE set)
1754{
1755 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1756 rb_check_frozen(set);
1757
1758 set_table *table = RSET_TABLE(set);
1759 size_t n = set_table_size(table);
1760 set_iter(set, set_keep_if_i, (st_data_t)table);
1761 set_compact_after_delete(set);
1762
1763 return (n == set_table_size(table)) ? Qnil : set;
1764}
1765
1766/*
1767 * call-seq:
1768 * replace(enumerable) -> self
1769 *
1770 * Replaces the contents +self+ with the contents of the given +enumerable+;
1771 * returns +self+:
1772 *
1773 * set = Set[1, 'c', :s] # => Set[1, "c", :s]
1774 * set.replace([1, 2]) # => Set[1, 2]
1775 *
1776 * Related: see {Methods for Assigning}[rdoc-ref:Set@Methods+for+Assigning].
1777 */
1778static VALUE
1779set_i_replace(VALUE set, VALUE other)
1780{
1781 rb_check_frozen(set);
1782
1783 if (rb_obj_is_kind_of(other, rb_cSet)) {
1784 set_i_initialize_copy(set, other);
1785 }
1786 else {
1787 if (set_iterating_p(set)) {
1788 rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
1789 }
1790
1791 // make sure enum is enumerable before calling clear
1792 enum_method_id(other);
1793
1794 set_table_clear(RSET_TABLE(set));
1795 set_merge_enum_into(set, other);
1796 }
1797 set_compact_after_delete(set);
1798
1799 return set;
1800}
1801
1802/*
1803 * call-seq:
1804 * reset -> self
1805 *
1806 * Resets the internal state of +self+; returns +self+.
1807 *
1808 * A set relies on the #hash results of each element being consistent.
1809 * Modifying an element in a way that changes the results of #hash
1810 * may allow duplicate elements in the set:
1811 *
1812 * array = [1]
1813 * set = Set[array] # => Set[[1]]
1814 * array << 2
1815 * set.add(array) # => Set[[1, 2], [1, 2]]
1816 *
1817 * Calling #reset will recalculate all of the hash values and remove
1818 * duplicate elements:
1819 *
1820 * set.reset # => Set[[1, 2]]
1821 *
1822 */
1823static VALUE
1824set_i_reset(VALUE set)
1825{
1826 if (set_iterating_p(set)) {
1827 rb_raise(rb_eRuntimeError, "reset during iteration");
1828 }
1829
1830 return set_reset_table_with_type(set, RSET_TABLE(set)->type);
1831}
1832
1833static void set_flatten_merge(VALUE set, VALUE from, VALUE seen);
1834
1835static int
1836set_flatten_merge_i(st_data_t item, st_data_t arg)
1837{
1838 VALUE *args = (VALUE *)arg;
1839 VALUE set = args[0];
1840 if (rb_obj_is_kind_of(item, rb_cSet)) {
1841 VALUE e_id = rb_obj_id(item);
1842 VALUE hash = args[2];
1843 switch(rb_hash_aref(hash, e_id)) {
1844 case Qfalse:
1845 return ST_CONTINUE;
1846 case Qtrue:
1847 rb_raise(rb_eArgError, "tried to flatten recursive Set");
1848 default:
1849 break;
1850 }
1851
1852 rb_hash_aset(hash, e_id, Qtrue);
1853 set_flatten_merge(set, item, hash);
1854 rb_hash_aset(hash, e_id, Qfalse);
1855 }
1856 else {
1857 set_i_add(set, item);
1858 }
1859 return ST_CONTINUE;
1860}
1861
1862static void
1863set_flatten_merge(VALUE set, VALUE from, VALUE hash)
1864{
1865 VALUE args[3] = {set, from, hash};
1866 set_iter(from, set_flatten_merge_i, (st_data_t)args);
1867}
1868
1869/*
1870 * call-seq:
1871 * flatten -> new_set
1872 *
1873 * Returns a new set that is a copy of +self+,
1874 * but with +self+ and its nested sets flattened;
1875 * that is, their elements become elements of +self+:
1876 *
1877 * Set[Set[0, 1], Set[2, 3]].flatten
1878 * # => Set[0, 1, 2, 3]
1879 * Set[Set[0, 1], Set[Set[2, 3], Set[3, 4]]].flatten
1880 * # => Set[0, 1, 2, 3, 4]
1881 *
1882 * Does not flatten nested arrays or hashes:
1883 *
1884 * Set[%w[foo bar]].flatten # => Set[["foo", "bar"]]
1885 * Set[{foo: 0, bar: 1}].flatten # => Set[{foo: 0, bar: 1}]
1886 *
1887 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
1888 */
1889static VALUE
1890set_i_flatten(VALUE set)
1891{
1892 VALUE new_set = set_s_alloc(rb_obj_class(set));
1893 if (RSET_COMPARE_BY_IDENTITY(set)) {
1894 set_i_compare_by_identity(new_set);
1895 }
1896 set_flatten_merge(new_set, set, rb_hash_new());
1897 return new_set;
1898}
1899
1900static int
1901set_contains_set_i(st_data_t item, st_data_t arg)
1902{
1903 if (rb_obj_is_kind_of(item, rb_cSet)) {
1904 *(bool *)arg = true;
1905 return ST_STOP;
1906 }
1907 return ST_CONTINUE;
1908}
1909
1910/*
1911 * call-seq:
1912 * flatten! -> self or nil
1913 *
1914 * Like #flatten, but if any changes were made
1915 * replaces +self+ with the result and returns +self+:
1916 *
1917 * Set[Set[0, 1], Set[2, 3]].flatten!
1918 * # => Set[0, 1, 2, 3]
1919 * Set[Set[0, 1], Set[Set[2, 3], Set[3, 4]]].flatten!
1920 * # => Set[0, 1, 2, 3, 4]
1921 *
1922 * Returns +nil+ if no changes were made:
1923 *
1924 * Set[0, 1, 2].flatten! # => nil
1925 *
1926 * Related: see {Methods for Assigning}[rdoc-ref:Set@Methods+for+Assigning].
1927 */
1928static VALUE
1929set_i_flatten_bang(VALUE set)
1930{
1931 bool contains_set = false;
1932 set_iter(set, set_contains_set_i, (st_data_t)&contains_set);
1933 if (!contains_set) return Qnil;
1934 rb_check_frozen(set);
1935 return set_i_replace(set, set_i_flatten(set));
1936}
1937
1939 set_table *table;
1940 VALUE result;
1941};
1942
1943static int
1944set_le_i(st_data_t key, st_data_t arg)
1945{
1946 struct set_subset_data *data = (struct set_subset_data *)arg;
1947 if (set_table_lookup(data->table, key)) return ST_CONTINUE;
1948 data->result = Qfalse;
1949 return ST_STOP;
1950}
1951
1952static VALUE
1953set_le(VALUE set, VALUE other)
1954{
1955 struct set_subset_data data = {
1956 .table = RSET_TABLE(other),
1957 .result = Qtrue
1958 };
1959 set_iter(set, set_le_i, (st_data_t)&data);
1960 return data.result;
1961}
1962
1963/*
1964 * call-seq:
1965 * proper_subset?(other_set) -> true or false
1966 *
1967 * Returns whether +self+ is
1968 * a {proper subset}[https://en.wikipedia.org/wiki/Subset]
1969 * of the given +other_set+:
1970 *
1971 * set = Set[*'b'..'e']
1972 * set.proper_subset?(set) # => false
1973 * set.proper_subset?(Set[*'a'..'f']) # => true
1974 *
1975 * Related: {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
1976 */
1977static VALUE
1978set_i_proper_subset(VALUE set, VALUE other)
1979{
1980 check_set(other);
1981 if (RSET_SIZE(set) >= RSET_SIZE(other)) return Qfalse;
1982 return set_le(set, other);
1983}
1984
1985/*
1986 * call-seq:
1987 * subset?(other_set) -> true or false
1988 *
1989 * Returns whether +self+ is a {subset}[https://en.wikipedia.org/wiki/Subset]
1990 * of the given +other_set+:
1991 *
1992 * set = Set[*'b'..'e']
1993 * set.subset?(set) # => true
1994 * set.subset?(Set[*'a'..'f']) # => true
1995 * set.subset?(Set[*'c'..'e']) # => false
1996 *
1997 * Related: {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
1998 */
1999static VALUE
2000set_i_subset(VALUE set, VALUE other)
2001{
2002 check_set(other);
2003 if (RSET_SIZE(set) > RSET_SIZE(other)) return Qfalse;
2004 return set_le(set, other);
2005}
2006
2007/*
2008 * call-seq:
2009 * proper_superset?(other_set) -> true or false
2010 *
2011 * Returns whether +self+ is
2012 * a {proper superset}[https://en.wikipedia.org/wiki/Subset]
2013 * of the given +other_set+:
2014 *
2015 * set = Set[*'a'..'f']
2016 * set.proper_superset?(set) # => false
2017 * set.proper_superset?(Set[*'b'..'e']) # => true
2018 *
2019 * Related: {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
2020 */
2021static VALUE
2022set_i_proper_superset(VALUE set, VALUE other)
2023{
2024 check_set(other);
2025 if (RSET_SIZE(set) <= RSET_SIZE(other)) return Qfalse;
2026 return set_le(other, set);
2027}
2028
2029/*
2030 * call-seq:
2031 * superset?(other_set) -> true or false
2032 *
2033 * Returns whether +self+ is a {superset}[https://en.wikipedia.org/wiki/Subset]
2034 * of the given +other_set+:
2035 *
2036 * set = Set[*'a'..'f'] # => Set["a", "b", "c", "d", "e", "f"]
2037 * set.superset?(set) # => true
2038 * set.superset?(Set[*'b'..'e']) # => true
2039 * set.superset?(Set[*'b'..'x']) # => false
2040 *
2041 * Related: {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
2042 */
2043static VALUE
2044set_i_superset(VALUE set, VALUE other)
2045{
2046 check_set(other);
2047 if (RSET_SIZE(set) < RSET_SIZE(other)) return Qfalse;
2048 return set_le(other, set);
2049}
2050
2051static int
2052set_intersect_i(st_data_t key, st_data_t arg)
2053{
2054 VALUE *args = (VALUE *)arg;
2055 if (set_table_lookup((set_table *)args[0], key)) {
2056 args[1] = Qtrue;
2057 return ST_STOP;
2058 }
2059 return ST_CONTINUE;
2060}
2061
2062/*
2063 * call-seq:
2064 * intersect?(enumerable) -> true or false
2065 *
2066 * Returns whether +self+ and +enumerable+ have any elements in common:
2067 *
2068 * set = Set[0, 'zero', :zero]
2069 * set.intersect?([0, 1, 2]) # => true
2070 * set.intersect?(%w[zero one two]) # => true
2071 * set.intersect?(Set[3]) # => false
2072 *
2073 * Related: see {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
2074 */
2075static VALUE
2076set_i_intersect(VALUE set, VALUE other)
2077{
2078 if (rb_obj_is_kind_of(other, rb_cSet)) {
2079 size_t set_size = RSET_SIZE(set);
2080 size_t other_size = RSET_SIZE(other);
2081 VALUE args[2];
2082 args[1] = Qfalse;
2083 VALUE iter_arg;
2084
2085 if (set_size < other_size) {
2086 iter_arg = set;
2087 args[0] = (VALUE)RSET_TABLE(other);
2088 }
2089 else {
2090 iter_arg = other;
2091 args[0] = (VALUE)RSET_TABLE(set);
2092 }
2093 set_iter(iter_arg, set_intersect_i, (st_data_t)args);
2094 return args[1];
2095 }
2096 else if (rb_obj_is_kind_of(other, rb_mEnumerable)) {
2097 return rb_funcall(other, id_any_p, 1, set);
2098 }
2099 else {
2100 rb_raise(rb_eArgError, "value must be enumerable");
2101 }
2102}
2103
2104/*
2105 * call-seq:
2106 * disjoint?(enumerable) -> true or false
2107 *
2108 * Returns whether no element of +enumerable+ is present in +self+:
2109 *
2110 * set = Set[0, 'zero', :zero]
2111 * set.disjoint?([1, 2, 3]) # => true
2112 * set.disjoint?([0, 1, 2, 3]) # => false
2113 *
2114 * Related: see {Methods for Querying}[rdoc-ref:Set@Methods+for+Querying].
2115 */
2116static VALUE
2117set_i_disjoint(VALUE set, VALUE other)
2118{
2119 return RBOOL(!RTEST(set_i_intersect(set, other)));
2120}
2121
2122/*
2123 * call-seq:
2124 * self <=> object -> -1, 0, 1, or nil
2125 *
2126 * Compares +self+ and +object+.
2127 *
2128 * If +object+ is another set, returns:
2129 *
2130 * - +-1+, if +self+ is a proper subset of +object+.
2131 * - +0+, if +self+ and +object+ have the same elements.
2132 * - +1+, if +self+ is a proper superset of +object+.
2133 * - +nil+, if none of the above;
2134 * that is, if +self+ and +object+ each have one or more elements
2135 * not included in the other.
2136 *
2137 * Examples:
2138 *
2139 * set = Set[0, 1, 2]
2140 * set <=> Set[3, 2, 1, 0] # => -1
2141 * set <=> Set[2, 1, 0] # => 0
2142 * set <=> Set[1, 0] # => 1
2143 * set <=> Set[1, 0, 3] # => nil
2144 *
2145 * Returns +nil+ if +object+ is not a set:
2146 *
2147 * set <=> [2, 1, 0] # => nil # Array, not Set.
2148 *
2149 * Related: see {Methods for Comparing}[rdoc-ref:Set@Methods+for+Comparing].
2150 */
2151static VALUE
2152set_i_compare(VALUE set, VALUE other)
2153{
2154 if (rb_obj_is_kind_of(other, rb_cSet)) {
2155 size_t set_size = RSET_SIZE(set);
2156 size_t other_size = RSET_SIZE(other);
2157
2158 if (set_size < other_size) {
2159 if (set_le(set, other) == Qtrue) {
2160 return INT2NUM(-1);
2161 }
2162 }
2163 else if (set_size > other_size) {
2164 if (set_le(other, set) == Qtrue) {
2165 return INT2NUM(1);
2166 }
2167 }
2168 else if (set_le(set, other) == Qtrue) {
2169 return INT2NUM(0);
2170 }
2171 }
2172
2173 return Qnil;
2174}
2175
2177 VALUE result;
2178 VALUE set;
2179};
2180
2181static int
2182set_eql_i(st_data_t item, st_data_t arg)
2183{
2184 struct set_equal_data *data = (struct set_equal_data *)arg;
2185
2186 if (!set_table_lookup(RSET_TABLE(data->set), item)) {
2187 data->result = Qfalse;
2188 return ST_STOP;
2189 }
2190 return ST_CONTINUE;
2191}
2192
2193static VALUE
2194set_recursive_eql(VALUE set, VALUE dt, int recur)
2195{
2196 if (recur) return Qtrue;
2197 struct set_equal_data *data = (struct set_equal_data*)dt;
2198 data->result = Qtrue;
2199 set_iter(set, set_eql_i, dt);
2200 return data->result;
2201}
2202
2203/*
2204 * call-seq:
2205 * self == object -> true or false
2206 *
2207 * Returns whether +object+ is a set, and has the same elements as +self+:
2208 *
2209 * set = Set[0, 1, 2]
2210 * set == Set[1, 2, 0] # => true
2211 * set == [1, 2, 3] # => false
2212 * set == Set[1, 2, '3'] # => false
2213 *
2214 * Related: see {Methods for Comparing}[rdoc-ref:Set@Methods+for+Comparing].
2215 */
2216static VALUE
2217set_i_eq(VALUE set, VALUE other)
2218{
2219 if (!rb_obj_is_kind_of(other, rb_cSet)) return Qfalse;
2220 if (set == other) return Qtrue;
2221
2222 set_table *stable = RSET_TABLE(set);
2223 set_table *otable = RSET_TABLE(other);
2224 size_t ssize = set_table_size(stable);
2225 size_t osize = set_table_size(otable);
2226
2227 if (ssize != osize) return Qfalse;
2228 if (ssize == 0 && osize == 0) return Qtrue;
2229 if (stable->type != otable->type) return Qfalse;
2230
2231 struct set_equal_data data;
2232 data.set = other;
2233 return rb_exec_recursive_paired(set_recursive_eql, set, other, (VALUE)&data);
2234}
2235
2236static int
2237set_hash_i(st_data_t item, st_data_t(arg))
2238{
2239 st_index_t *hval = (st_index_t *)arg;
2240 st_index_t ival = rb_hash(item);
2241 *hval ^= rb_st_hash(&ival, sizeof(st_index_t), 0);
2242 return ST_CONTINUE;
2243}
2244
2245/*
2246 * call-seq:
2247 * hash -> integer
2248 *
2249 * Returns the integer hash value for +self+.
2250 *
2251 * Two sets with the same content have the same hash value.
2252 *
2253 * Set[0, 1].hash == Set[1, 0].hash # => true
2254 * Set[0, 1].hash == Set[0].hash # => false
2255 */
2256static VALUE
2257set_i_hash(VALUE set)
2258{
2259 st_index_t size = RSET_SIZE(set);
2260 st_index_t hval = rb_st_hash_start(size);
2261 hval = rb_hash_uint(hval, (st_index_t)set_i_hash);
2262 if (size) {
2263 set_iter(set, set_hash_i, (VALUE)&hval);
2264 }
2265 hval = rb_st_hash_end(hval);
2266 return ST2FIX(hval);
2267}
2268
2269/* :nodoc: */
2270static int
2271set_to_hash_i(st_data_t key, st_data_t arg)
2272{
2273 rb_hash_aset((VALUE)arg, (VALUE)key, Qtrue);
2274 return ST_CONTINUE;
2275}
2276
2277static VALUE
2278set_i_to_h(VALUE set)
2279{
2280 rb_len_t size = RSET_SIZE(set);
2281 VALUE hash;
2282 if (RSET_COMPARE_BY_IDENTITY(set)) {
2283 hash = rb_ident_hash_new_capa(size);
2284 }
2285 else {
2286 hash = rb_hash_new_capa(size);
2287 }
2288 rb_hash_set_default(hash, Qfalse);
2289
2290 if (size == 0) return hash;
2291
2292 set_iter(set, set_to_hash_i, (st_data_t)hash);
2293 return hash;
2294}
2295
2296static VALUE
2297compat_dumper(VALUE set)
2298{
2299 VALUE dumper = rb_class_allocate_instance_capa(rb_cObject, 1);
2300 rb_ivar_set(dumper, id_i_hash, set_i_to_h(set));
2301 return dumper;
2302}
2303
2304static int
2305set_i_from_hash_i(st_data_t key, st_data_t val, st_data_t set)
2306{
2307 if ((VALUE)val != Qtrue) {
2308 rb_raise(rb_eRuntimeError, "expect true as Set value: %"PRIsVALUE, rb_obj_class((VALUE)val));
2309 }
2310 set_i_add((VALUE)set, (VALUE)key);
2311 return ST_CONTINUE;
2312}
2313
2314static VALUE
2315set_i_from_hash(VALUE set, VALUE hash)
2316{
2317 Check_Type(hash, T_HASH);
2318 if (rb_hash_compare_by_id_p(hash)) set_i_compare_by_identity(set);
2319 rb_hash_stlike_foreach(hash, set_i_from_hash_i, (st_data_t)set);
2320 return set;
2321}
2322
2323static VALUE
2324compat_loader(VALUE self, VALUE a)
2325{
2326 return set_i_from_hash(self, rb_ivar_get(a, id_i_hash));
2327}
2328
2329/* Internal C-API functions */
2330
2331VALUE
2332rb_ident_set_new(void)
2333{
2334 return set_alloc_with_size_and_type(rb_cSet, 0, &identhash);
2335}
2336
2337bool
2338rb_set_add_no_check(VALUE set, VALUE element)
2339{
2340 if (set_insert(RSET_TABLE(set), (st_data_t)element) == 0) {
2341 RB_OBJ_WRITTEN(set, Qundef, element);
2342 return true;
2343 }
2344 return false;
2345}
2346
2347bool
2348rb_set_delete_no_check(VALUE set, VALUE element)
2349{
2350 st_data_t element_data = (st_data_t)element;
2351 return set_table_delete(RSET_TABLE(set), &element_data) != 0;
2352}
2353
2354VALUE
2355rb_set_to_a(VALUE set)
2356{
2357 return set_i_to_a(set);
2358}
2359
2360/* C-API functions */
2361
2362void
2363rb_set_foreach(VALUE set, int (*func)(VALUE element, VALUE arg), VALUE arg)
2364{
2365 set_iter(set, func, arg);
2366}
2367
2368VALUE
2370{
2371 return set_alloc_with_size(rb_cSet, 0);
2372}
2373
2374VALUE
2376{
2377 return set_alloc_with_size(rb_cSet, (st_index_t)capa);
2378}
2379
2380bool
2382{
2383 return RSET_IS_MEMBER(set, element);
2384}
2385
2386bool
2388{
2389 return set_i_add_p(set, element) != Qnil;
2390}
2391
2392VALUE
2394{
2395 return set_i_clear(set);
2396}
2397
2398bool
2400{
2401 return set_i_delete_p(set, element) != Qnil;
2402}
2403
2404size_t
2406{
2407 return RSET_SIZE(set);
2408}
2409
2410/*
2411 * Document-class: Set
2412 *
2413 * An instance of class \Set contains a collection
2414 * of objects (elements), with no duplicates.
2415 *
2416 * By default:
2417 *
2418 * - Set determines equality via Object#eql? and Object#hash,
2419 * and assumes that these values do not change for a stored element.
2420 * If these values do change, the set enters an unreliable state;
2421 * see #reset.
2422 * - A String instance added to a set is stored as a frozen copy of the string,
2423 * unless it is already frozen.
2424 *
2425 * Calling #compare_by_identity causes:
2426 *
2427 * - All following determinations of equality
2428 * to use object identity instead of the methods mentioned above.
2429 * - A String added to a set is stored "as is", whether or not frozen.
2430 *
2431 * \Set includes module Enumerable, and is easy to use with other enumerable objects.
2432 * Many of its methods accept enumerable objects as arguments;
2433 * any enumerable object may be converted to a set via {#to_set}[rdoc-ref:Enumerable#to_set].
2434 *
2435 * == Contact
2436 *
2437 * - Akinori MUSHA <knu@iDaemons.org> (current maintainer)
2438 *
2439 * == Inheriting from \Set
2440 *
2441 * Before Ruby 4.0 (released in December, 2025),
2442 * class \Set had a different, less efficient implementation.
2443 * In Ruby 4.0, the class was reimplemented in C,
2444 * and the behaviors of some methods were adjusted.
2445 *
2446 * When compatibility with the older implementation is needed,
2447 * a \Set subclass should inherit directly from class +Set+;
2448 * this automatically includes module +Set::SubclassCompatible+,
2449 * which makes behaviors closer to those in the older implementation.
2450 *
2451 * A difference may be seen as follows:
2452 *
2453 * Set[[1, 2, 3]] # => Set[[1, 2, 3]]
2454 * class MySet < Set; end
2455 * MySet[[1, 2, 3]] # => #<MySet: {[1, 2, 3]}> # Same as in Ruby 3.4.
2456 *
2457 * When backward compatibility is not needed,
2458 * a \Set subclass should inherit from +Set::CoreSet+,
2459 * which avoids including the compatibility layer:
2460 *
2461 * class MyCoreSet < Set::CoreSet; end
2462 * MyCoreSet[[1, 2, 3]] # => MyCoreSet[[1, 2, 3]]
2463 *
2464 * == What's Here
2465 *
2466 * First, what's elsewhere. \Class \Set:
2467 *
2468 * - Inherits from {class Object}[rdoc-ref:Object@Whats+Here].
2469 * - Includes {module Enumerable}[rdoc-ref:Enumerable@Whats+Here],
2470 * which provides dozens of additional methods.
2471 *
2472 * In particular, class \Set does not have many methods of its own
2473 * for fetching or for iterating.
2474 * Instead, it relies on those in \Enumerable.
2475 *
2476 * Here, class \Set provides methods that are useful for:
2477 *
2478 * - {Creating a Set}[rdoc-ref:Set@Methods+for+Creating+a+Set]
2479 * - {Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations]
2480 * - {Comparing}[rdoc-ref:Set@Methods+for+Comparing]
2481 * - {Querying}[rdoc-ref:Set@Methods+for+Querying]
2482 * - {Assigning}[rdoc-ref:Set@Methods+for+Assigning]
2483 * - {Deleting}[rdoc-ref:Set@Methods+for+Deleting]
2484 * - {Converting}[rdoc-ref:Set@Methods+for+Converting]
2485 * - {And more....}[rdoc-ref:Set@Other+Methods]
2486 *
2487 * === Methods for Creating a \Set
2488 *
2489 * - ::[]:
2490 * Returns a new set populated with the given objects.
2491 * - ::new:
2492 * Returns a new set based on the given object (if no block given),
2493 * or on the return values from the called block (if a block given).
2494 *
2495 * === Methods for \Set Operations
2496 *
2497 * - #& (aliased as #intersection):
2498 * Returns a new set containing the intersection of +self+ and the given enumerable.
2499 * - #- (aliased as #difference):
2500 * Returns a new set containing the difference of +self+ and the given enumerable.
2501 * - #^: Returns a new set containing the exclusive OR of +self+ and the given enumerable.
2502 * - #| (aliased as #union and #+):
2503 * Returns a new set containing the union of +self+ and the given enumerable.
2504 *
2505 * === Methods for Comparing
2506 *
2507 * - #<=>: Returns -1, 0, or 1 as +self+ is less than, equal to,
2508 * or greater than a given object.
2509 * - #==: Returns whether +self+ and a given enumerable are equal,
2510 * as determined by Object#eql?.
2511 * - #compare_by_identity?:
2512 * Returns whether +self+ considers only identity
2513 * when comparing elements.
2514 * - #proper_subset? (aliased as #<):
2515 * Returns whether the given enumerable is a proper subset of +self+.
2516 * - #proper_superset? (aliased as #>):
2517 * Returns whether the given enumerable is a proper superset of +self+.
2518 * - #subset? (aliased as #<=):
2519 * Returns whether the given object is a subset of +self+.
2520 * - #superset? (aliased as #>=):
2521 * Returns whether the given enumerable is a superset of +self+.
2522 *
2523 * === Methods for Querying
2524 *
2525 * - #disjoint?:
2526 * Returns whether no element of the given enumerable is present in +self+.
2527 * - #empty?:
2528 * Returns whether +self+ contains no elements.
2529 * - #include? (aliased as #member? and #===):
2530 * Returns whether the given object is an element of +self+.
2531 * - #intersect?:
2532 * Returns whether +self+ and the given enumerable have any elements in common.
2533 * - #size (aliased as #length):
2534 * Returns the number of elements in +self+.
2535 *
2536 * === Methods for Assigning
2537 *
2538 * - #add (aliased as #<<):
2539 * Adds the given object to +self+; returns +self+.
2540 * - #add?:
2541 * Like #add, but returns +nil+ if the given object is already in +self+.
2542 * - #merge:
2543 * Adds each element of each of the given enumerables to +self+; returns +self+.
2544 * - #replace:
2545 * Replaces the contents of +self+ with the contents of the given enumerable;
2546 * returns +self+.
2547 *
2548 * === Methods for Deleting
2549 *
2550 * - #clear:
2551 * Removes all elements from +self+; returns +self+.
2552 * - #delete:
2553 * Removes the given object from +self+ if +self+ includes the object; returns +self+.
2554 * - #delete?:
2555 * Like #delete, but returns +nil+ if the object is not in +self+.
2556 * - #delete_if:
2557 * Calls the block with each element in +self+;
2558 * removes the element if the block returns a truthy value.
2559 * - #keep_if:
2560 * Calls the block with each element in +self+,
2561 * deleting the element if the block returns +false+ or +nil+; returns +self+.
2562 * - #reject!
2563 * Like #delete_if, but returns +nil+ if no changes were made.
2564 * - #select! (aliased as #filter!):
2565 * Like #keep_if, but returns +nil+ if no changes were made.
2566 * - #subtract:
2567 * Deletes from +self+ every element found in the given enumerable; returns +self+:
2568 *
2569 * === Methods for Converting
2570 *
2571 * - #classify:
2572 * Returns a hash that partitions the elements,
2573 * as determined by the given block.
2574 * - #collect! (aliased as #map!):
2575 * Replaces each element with a block return-value.
2576 * - #divide:
2577 * Returns a set of sets that partition the elements,
2578 * as determined by the given block.
2579 * - #flatten:
2580 * Returns a new set that is a recursive flattening of +self+.
2581 * - #flatten!: Like #flatten, but if any changes were made
2582 * replaces +self+ with the result and returns +self+.
2583 * - #inspect (aliased as #to_s):
2584 * Returns a string representation of +self+.
2585 * - #join:
2586 * Returns the string formed by joining the string-converted elements of +self+
2587 * with the given separator.
2588 * - #to_a:
2589 * Returns an array containing the elements of +self+.
2590 * - #to_set:
2591 * With a block given, creates and returns a new set;
2592 * calls the block with each element of +self+,
2593 * and adds the block's returns value to the new set.
2594 *
2595 * === Other Methods
2596 *
2597 * - #compare_by_identity:
2598 * Sets +self+ to compare by object identity (rather than by object content).
2599 * - #each:
2600 * Calls the block with each successive element of +self+; returns +self+.
2601 * - #reset:
2602 * Resets the internal state of +self+; returns +self+.
2603 * Useful if an element has been modified while an element in the set.
2604 *
2605 */
2606void
2607Init_Set(void)
2608{
2609 rb_cSet = rb_define_class("Set", rb_cObject);
2611
2612 id_each_entry = rb_intern_const("each_entry");
2613 id_any_p = rb_intern_const("any?");
2614 id_new = rb_intern_const("new");
2615 id_i_hash = rb_intern_const("@hash");
2616 id_subclass_compatible = rb_intern_const("SubclassCompatible");
2617 id_class_methods = rb_intern_const("ClassMethods");
2618 id_set_iter_lev = rb_make_internal_id();
2619
2620 rb_define_alloc_func(rb_cSet, set_s_alloc);
2621 rb_define_singleton_method(rb_cSet, "[]", set_s_create, -1);
2622
2623 rb_define_method(rb_cSet, "initialize", set_i_initialize, -1);
2624 rb_define_method(rb_cSet, "initialize_copy", set_i_initialize_copy, 1);
2625
2626 rb_define_method(rb_cSet, "&", set_i_intersection, 1);
2627 rb_define_alias(rb_cSet, "intersection", "&");
2628 rb_define_method(rb_cSet, "-", set_i_difference, 1);
2629 rb_define_alias(rb_cSet, "difference", "-");
2630 rb_define_method(rb_cSet, "^", set_i_xor, 1);
2631 rb_define_method(rb_cSet, "|", set_i_union, 1);
2632 rb_define_alias(rb_cSet, "+", "|");
2633 rb_define_alias(rb_cSet, "union", "|");
2634 rb_define_method(rb_cSet, "<=>", set_i_compare, 1);
2635 rb_define_method(rb_cSet, "==", set_i_eq, 1);
2636 rb_define_alias(rb_cSet, "eql?", "==");
2637 rb_define_method(rb_cSet, "add", set_i_add, 1);
2638 rb_define_alias(rb_cSet, "<<", "add");
2639 rb_define_method(rb_cSet, "add?", set_i_add_p, 1);
2640 rb_define_method(rb_cSet, "classify", set_i_classify, 0);
2641 rb_define_method(rb_cSet, "clear", set_i_clear, 0);
2642 rb_define_method(rb_cSet, "collect!", set_i_collect, 0);
2643 rb_define_alias(rb_cSet, "map!", "collect!");
2644 rb_define_method(rb_cSet, "compare_by_identity", set_i_compare_by_identity, 0);
2645 rb_define_method(rb_cSet, "compare_by_identity?", set_i_compare_by_identity_p, 0);
2646 rb_define_method(rb_cSet, "delete", set_i_delete, 1);
2647 rb_define_method(rb_cSet, "delete?", set_i_delete_p, 1);
2648 rb_define_method(rb_cSet, "delete_if", set_i_delete_if, 0);
2649 rb_define_method(rb_cSet, "disjoint?", set_i_disjoint, 1);
2650 rb_define_method(rb_cSet, "divide", set_i_divide, 0);
2651 rb_define_method(rb_cSet, "each", set_i_each, 0);
2652 rb_define_method(rb_cSet, "empty?", set_i_empty, 0);
2653 rb_define_method(rb_cSet, "flatten", set_i_flatten, 0);
2654 rb_define_method(rb_cSet, "flatten!", set_i_flatten_bang, 0);
2655 rb_define_method(rb_cSet, "hash", set_i_hash, 0);
2656 rb_define_method(rb_cSet, "include?", set_i_include, 1);
2657 rb_define_alias(rb_cSet, "member?", "include?");
2658 rb_define_alias(rb_cSet, "===", "include?");
2659 rb_define_method(rb_cSet, "inspect", set_i_inspect, 0);
2660 rb_define_alias(rb_cSet, "to_s", "inspect");
2661 rb_define_method(rb_cSet, "intersect?", set_i_intersect, 1);
2662 rb_define_method(rb_cSet, "join", set_i_join, -1);
2663 rb_define_method(rb_cSet, "keep_if", set_i_keep_if, 0);
2664 rb_define_method(rb_cSet, "merge", set_i_merge, -1);
2665 rb_define_method(rb_cSet, "proper_subset?", set_i_proper_subset, 1);
2666 rb_define_alias(rb_cSet, "<", "proper_subset?");
2667 rb_define_method(rb_cSet, "proper_superset?", set_i_proper_superset, 1);
2668 rb_define_alias(rb_cSet, ">", "proper_superset?");
2669 rb_define_method(rb_cSet, "reject!", set_i_reject, 0);
2670 rb_define_method(rb_cSet, "replace", set_i_replace, 1);
2671 rb_define_method(rb_cSet, "reset", set_i_reset, 0);
2672 rb_define_method(rb_cSet, "size", set_i_size, 0);
2673 rb_define_alias(rb_cSet, "length", "size");
2674 rb_define_method(rb_cSet, "select!", set_i_select, 0);
2675 rb_define_alias(rb_cSet, "filter!", "select!");
2676 rb_define_method(rb_cSet, "subset?", set_i_subset, 1);
2677 rb_define_alias(rb_cSet, "<=", "subset?");
2678 rb_define_method(rb_cSet, "subtract", set_i_subtract, 1);
2679 rb_define_method(rb_cSet, "superset?", set_i_superset, 1);
2680 rb_define_alias(rb_cSet, ">=", "superset?");
2681 rb_define_method(rb_cSet, "to_a", set_i_to_a, 0);
2682 rb_define_method(rb_cSet, "to_set", set_i_to_set, 0);
2683
2684 rb_define_method(rb_mEnumerable, "to_set", enum_to_set, 0);
2685
2686 /* :nodoc: */
2687 VALUE compat = rb_define_class_under(rb_cSet, "compatible", rb_cObject);
2688 rb_marshal_define_compat(rb_cSet, compat, compat_dumper, compat_loader);
2689
2690 // Create Set::CoreSet before defining inherited, so it does not include
2691 // the backwards compatibility layer.
2692 rb_define_class_under(rb_cSet, "CoreSet", rb_cSet);
2693 rb_define_private_method(rb_singleton_class(rb_cSet), "inherited", set_s_inherited, 1);
2694
2695 rb_provide("set.rb");
2696}
#define rb_define_method(klass, mid, func, arity)
Defines klass#mid.
#define rb_define_singleton_method(klass, mid, func, arity)
Defines klass.mid.
#define rb_define_private_method(klass, mid, func, arity)
Defines klass#mid and makes it private.
static bool RB_OBJ_FROZEN(VALUE obj)
Checks if an object is frozen.
Definition fl_type.h:714
void rb_include_module(VALUE klass, VALUE module)
Includes a module to a class.
Definition class.c:1737
void rb_extend_object(VALUE obj, VALUE module)
Extend the object with the module.
Definition eval.c:1946
VALUE rb_singleton_class(VALUE obj)
Finds or creates the singleton class of the passed object.
Definition class.c:3025
void rb_define_alias(VALUE klass, const char *name1, const char *name2)
Defines an alias of a method.
Definition class.c:3068
int rb_keyword_given_p(void)
Determines if the current method is given a keyword argument.
Definition eval.c:1054
int rb_block_given_p(void)
Determines if the current method is given a block.
Definition eval.c:1041
#define rb_str_buf_cat2
Old name of rb_usascii_str_new_cstr.
Definition string.h:1707
#define Qundef
Old name of RUBY_Qundef.
#define LEN2NUM
Old name of RB_LEN2NUM.
Definition len_t.h:33
#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:408
#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:409
VALUE rb_eRuntimeError
RuntimeError exception.
Definition error.c:1455
VALUE rb_cSet
Set class.
Definition set.c:99
VALUE rb_cObject
Object class.
Definition object.c:60
VALUE rb_mEnumerable
Enumerable module.
Definition enum.c:28
VALUE rb_obj_class(VALUE obj)
Queries the class of an object.
Definition object.c:230
VALUE rb_obj_dup(VALUE obj)
Duplicates the given object.
Definition object.c:552
VALUE rb_inspect(VALUE obj)
Generates a human-readable textual representation of the given object.
Definition object.c:665
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:846
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:902
VALUE rb_cString
String class.
Definition string.c:85
#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:504
rb_encoding * rb_usascii_encoding(void)
Queries the encoding that represents US-ASCII.
Definition encoding.c:1590
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:1498
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:1212
VALUE rb_funcall(VALUE recv, ID mid, int n,...)
Calls a method.
Definition vm_eval.c:1149
VALUE rb_ary_new_capa(rb_len_t 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:208
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
VALUE rb_hash_new(void)
Creates a new, empty hash object.
Definition hash.c:1646
void rb_provide(const char *feature)
Declares that the given feature is already provided by someone else.
Definition load.c:963
void rb_marshal_define_compat(VALUE newclass, VALUE oldclass, VALUE(*dumper)(VALUE), VALUE(*loader)(VALUE, VALUE))
Marshal format compatibility layer.
Definition marshal.c:139
size_t rb_set_size(VALUE set)
Returns the number of elements in the set.
Definition set.c:2405
VALUE rb_set_clear(VALUE set)
Removes all entries from set.
Definition set.c:2393
bool rb_set_delete(VALUE set, VALUE element)
Removes the element from from set.
Definition set.c:2399
bool rb_set_add(VALUE set, VALUE element)
Adds element to set.
Definition set.c:2387
void rb_set_foreach(VALUE set, int(*func)(VALUE element, VALUE arg), VALUE arg)
Iterates over a set.
Definition set.c:2363
bool rb_set_lookup(VALUE set, VALUE element)
Whether the set contains the given element.
Definition set.c:2381
VALUE rb_set_new(void)
Creates a new, empty set object.
Definition set.c:2369
VALUE rb_set_new_capa(size_t capa)
Identical to rb_set_new(), except it additionally specifies how many elements it is expected to conta...
Definition set.c:2375
#define rb_hash_uint(h, i)
Just another name of st_hash_uint.
Definition string.h:967
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:3904
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:3880
VALUE rb_exec_recursive(VALUE(*f)(VALUE g, VALUE h, int r), VALUE g, VALUE h)
"Recursion" API entry point.
Definition thread.c:5959
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,...
Definition thread.c:5970
VALUE rb_const_get(VALUE space, ID name)
Identical to rb_const_defined(), except it returns the actual defined value.
Definition variable.c:3535
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:2168
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:1651
VALUE rb_class_path(VALUE mod)
Identical to rb_mod_name(), except it returns #<Class: ...> style inspection for anonymous modules.
Definition variable.c:397
int rb_respond_to(VALUE obj, ID mid)
Queries if the object responds to the method.
Definition vm_method.c:3752
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:285
int capa
Designed capacity of the buffer.
Definition io.h:11
#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:1419
VALUE rb_yield(VALUE val)
Yields the block.
Definition vm_eval.c:1396
#define RB_GC_GUARD(v)
Prevents premature destruction of local objects.
Definition memory.h:170
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:50
#define RARRAY_PTR_USE(ary, ptr_name, expr)
Declares a section of code where raw pointers are used.
Definition rarray.h:347
#define RARRAY_AREF(a, i)
References an object in an array.
Definition rarray.h:422
#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:773
struct rb_data_type_struct rb_data_type_t
This is the struct that holds necessary info for a struct.
Definition rtypeddata.h:239
#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:604
VALUE rb_require(const char *feature)
Identical to rb_require_string(), except it takes C's string instead of Ruby's.
Definition load.c:1781
#define RTEST
This is an old name of RB_TEST.
set_table_entry * entries
Array of size 2^entry_power.
Definition set_table.h:31
long rb_len_t
A signed integer type for lengths and indices of objects such as String and Array.
Definition value.h:142
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:425
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