1 /**********************************************************************
2
3 array.c -
4
5 $Author: nagachika $
6 created at: Fri Aug 6 09:46:12 JST 1993
7
8 Copyright (C) 1993-2007 Yukihiro Matsumoto
9 Copyright (C) 2000 Network Applied Communication Laboratory, Inc.
10 Copyright (C) 2000 Information-technology Promotion Agency, Japan
11
12 **********************************************************************/
13
14 #include "ruby/encoding.h"
15 #include "ruby/util.h"
16 #include "ruby/st.h"
17 #include "probes.h"
18 #include "id.h"
19 #include "debug_counter.h"
20 #include "gc.h"
21 #include "transient_heap.h"
22 #include "internal.h"
23
24 #if !ARRAY_DEBUG
25 # define NDEBUG
26 #endif
27 #include "ruby_assert.h"
28
29 VALUE rb_cArray;
30
31 /* for OPTIMIZED_CMP: */
32 #define id_cmp idCmp
33
34 #define ARY_DEFAULT_SIZE 16
35 #define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
36 #define SMALL_ARRAY_LEN 16
37
38 # define ARY_SHARED_P(ary) \
39 (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
40 FL_TEST((ary),ELTS_SHARED)!=0)
41 # define ARY_EMBED_P(ary) \
42 (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
43 FL_TEST((ary), RARRAY_EMBED_FLAG)!=0)
44
45 #define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
46 #define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
47 #define ARY_HEAP_CAPA(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.aux.capa)
48
49 #define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
50 #define ARY_EMBED_LEN(a) \
51 (assert(ARY_EMBED_P(a)), \
52 (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
53 (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
54 #define ARY_HEAP_SIZE(a) (assert(!ARY_EMBED_P(a)), assert(ARY_OWNS_HEAP_P(a)), ARY_HEAP_CAPA(a) * sizeof(VALUE))
55
56 #define ARY_OWNS_HEAP_P(a) (!FL_TEST((a), ELTS_SHARED|RARRAY_EMBED_FLAG))
57 #define FL_SET_EMBED(a) do { \
58 assert(!ARY_SHARED_P(a)); \
59 FL_SET((a), RARRAY_EMBED_FLAG); \
60 RARY_TRANSIENT_UNSET(a); \
61 ary_verify(a); \
62 } while (0)
63 #define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
64 #define FL_SET_SHARED(ary) do { \
65 assert(!ARY_EMBED_P(ary)); \
66 FL_SET((ary), ELTS_SHARED); \
67 } while (0)
68 #define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)
69
70 #define ARY_SET_PTR(ary, p) do { \
71 assert(!ARY_EMBED_P(ary)); \
72 assert(!OBJ_FROZEN(ary)); \
73 RARRAY(ary)->as.heap.ptr = (p); \
74 } while (0)
75 #define ARY_SET_EMBED_LEN(ary, n) do { \
76 long tmp_n = (n); \
77 assert(ARY_EMBED_P(ary)); \
78 assert(!OBJ_FROZEN(ary)); \
79 RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
80 RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
81 } while (0)
82 #define ARY_SET_HEAP_LEN(ary, n) do { \
83 assert(!ARY_EMBED_P(ary)); \
84 RARRAY(ary)->as.heap.len = (n); \
85 } while (0)
86 #define ARY_SET_LEN(ary, n) do { \
87 if (ARY_EMBED_P(ary)) { \
88 ARY_SET_EMBED_LEN((ary), (n)); \
89 } \
90 else { \
91 ARY_SET_HEAP_LEN((ary), (n)); \
92 } \
93 assert(RARRAY_LEN(ary) == (n)); \
94 } while (0)
95 #define ARY_INCREASE_PTR(ary, n) do { \
96 assert(!ARY_EMBED_P(ary)); \
97 assert(!OBJ_FROZEN(ary)); \
98 RARRAY(ary)->as.heap.ptr += (n); \
99 } while (0)
100 #define ARY_INCREASE_LEN(ary, n) do { \
101 assert(!OBJ_FROZEN(ary)); \
102 if (ARY_EMBED_P(ary)) { \
103 ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
104 } \
105 else { \
106 RARRAY(ary)->as.heap.len += (n); \
107 } \
108 } while (0)
109
110 #define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
111 ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : ARY_HEAP_CAPA(ary))
112 #define ARY_SET_CAPA(ary, n) do { \
113 assert(!ARY_EMBED_P(ary)); \
114 assert(!ARY_SHARED_P(ary)); \
115 assert(!OBJ_FROZEN(ary)); \
116 RARRAY(ary)->as.heap.aux.capa = (n); \
117 } while (0)
118
119 #define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
120 #define ARY_SET_SHARED(ary, value) do { \
121 const VALUE _ary_ = (ary); \
122 const VALUE _value_ = (value); \
123 assert(!ARY_EMBED_P(_ary_)); \
124 assert(ARY_SHARED_P(_ary_)); \
125 assert(ARY_SHARED_ROOT_P(_value_)); \
126 RB_OBJ_WRITE(_ary_, &RARRAY(_ary_)->as.heap.aux.shared, _value_); \
127 } while (0)
128 #define RARRAY_SHARED_ROOT_FLAG FL_USER5
129 #define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))
130 #define ARY_SHARED_NUM(ary) \
131 (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
132 #define ARY_SHARED_OCCUPIED(ary) (ARY_SHARED_NUM(ary) == 1)
133 #define ARY_SET_SHARED_NUM(ary, value) do { \
134 assert(ARY_SHARED_ROOT_P(ary)); \
135 RARRAY(ary)->as.heap.aux.capa = (value); \
136 } while (0)
137 #define FL_SET_SHARED_ROOT(ary) do { \
138 assert(!ARY_EMBED_P(ary)); \
139 assert(!RARRAY_TRANSIENT_P(ary)); \
140 FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
141 } while (0)
142
143 #define ARY_SET(a, i, v) RARRAY_ASET((assert(!ARY_SHARED_P(a)), (a)), (i), (v))
144
145
146 #if ARRAY_DEBUG
147 #define ary_verify(ary) ary_verify_(ary, __FILE__, __LINE__)
148
149 static VALUE
ary_verify_(VALUE ary,const char * file,int line)150 ary_verify_(VALUE ary, const char *file, int line)
151 {
152 assert(RB_TYPE_P(ary, T_ARRAY));
153
154 if (FL_TEST(ary, ELTS_SHARED)) {
155 VALUE root = RARRAY(ary)->as.heap.aux.shared;
156 const VALUE *ptr = ARY_HEAP_PTR(ary);
157 const VALUE *root_ptr = RARRAY_CONST_PTR_TRANSIENT(root);
158 long len = ARY_HEAP_LEN(ary), root_len = RARRAY_LEN(root);
159 assert(FL_TEST(root, RARRAY_SHARED_ROOT_FLAG));
160 assert(root_ptr <= ptr && ptr + len <= root_ptr + root_len);
161 ary_verify(root);
162 }
163 else if (ARY_EMBED_P(ary)) {
164 assert(!RARRAY_TRANSIENT_P(ary));
165 assert(!ARY_SHARED_P(ary));
166 assert(RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX);
167 }
168 else {
169 #if 1
170 const VALUE *ptr = RARRAY_CONST_PTR_TRANSIENT(ary);
171 long i, len = RARRAY_LEN(ary);
172 volatile VALUE v;
173 if (len > 1) len = 1; /* check only HEAD */
174 for (i=0; i<len; i++) {
175 v = ptr[i]; /* access check */
176 }
177 v = v;
178 #endif
179 }
180
181 if (RARRAY_TRANSIENT_P(ary)) {
182 assert(rb_transient_heap_managed_ptr_p(RARRAY_CONST_PTR_TRANSIENT(ary)));
183 }
184
185 rb_transient_heap_verify();
186
187 return ary;
188 }
189
190 void
rb_ary_verify(VALUE ary)191 rb_ary_verify(VALUE ary){
192 ary_verify(ary);
193 }
194 #else
195 #define ary_verify(ary) ((void)0)
196 #endif
197
198 VALUE *
rb_ary_ptr_use_start(VALUE ary)199 rb_ary_ptr_use_start(VALUE ary)
200 {
201 #if ARRAY_DEBUG
202 FL_SET_RAW(ary, RARRAY_PTR_IN_USE_FLAG);
203 #endif
204 return (VALUE *)RARRAY_CONST_PTR_TRANSIENT(ary);
205 }
206
207 void
rb_ary_ptr_use_end(VALUE ary)208 rb_ary_ptr_use_end(VALUE ary)
209 {
210 #if ARRAY_DEBUG
211 FL_UNSET_RAW(ary, RARRAY_PTR_IN_USE_FLAG);
212 #endif
213 }
214
215 void
rb_mem_clear(register VALUE * mem,register long size)216 rb_mem_clear(register VALUE *mem, register long size)
217 {
218 while (size--) {
219 *mem++ = Qnil;
220 }
221 }
222
223 static void
ary_mem_clear(VALUE ary,long beg,long size)224 ary_mem_clear(VALUE ary, long beg, long size)
225 {
226 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
227 rb_mem_clear(ptr + beg, size);
228 });
229 }
230
231 static inline void
memfill(register VALUE * mem,register long size,register VALUE val)232 memfill(register VALUE *mem, register long size, register VALUE val)
233 {
234 while (size--) {
235 *mem++ = val;
236 }
237 }
238
239 static void
ary_memfill(VALUE ary,long beg,long size,VALUE val)240 ary_memfill(VALUE ary, long beg, long size, VALUE val)
241 {
242 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
243 memfill(ptr + beg, size, val);
244 RB_OBJ_WRITTEN(ary, Qundef, val);
245 });
246 }
247
248 static void
ary_memcpy0(VALUE ary,long beg,long argc,const VALUE * argv,VALUE buff_owner_ary)249 ary_memcpy0(VALUE ary, long beg, long argc, const VALUE *argv, VALUE buff_owner_ary)
250 {
251 assert(!ARY_SHARED_P(buff_owner_ary));
252
253 if (argc > (int)(128/sizeof(VALUE)) /* is magic number (cache line size) */) {
254 rb_gc_writebarrier_remember(buff_owner_ary);
255 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
256 MEMCPY(ptr+beg, argv, VALUE, argc);
257 });
258 }
259 else {
260 int i;
261 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
262 for (i=0; i<argc; i++) {
263 RB_OBJ_WRITE(buff_owner_ary, &ptr[i+beg], argv[i]);
264 }
265 });
266 }
267 }
268
269 static void
ary_memcpy(VALUE ary,long beg,long argc,const VALUE * argv)270 ary_memcpy(VALUE ary, long beg, long argc, const VALUE *argv)
271 {
272 ary_memcpy0(ary, beg, argc, argv, ary);
273 }
274
275 static VALUE *
ary_heap_alloc(VALUE ary,size_t capa)276 ary_heap_alloc(VALUE ary, size_t capa)
277 {
278 VALUE *ptr = rb_transient_heap_alloc(ary, sizeof(VALUE) * capa);
279
280 if (ptr != NULL) {
281 RARY_TRANSIENT_SET(ary);
282 }
283 else {
284 RARY_TRANSIENT_UNSET(ary);
285 ptr = ALLOC_N(VALUE, capa);
286 }
287
288 return ptr;
289 }
290
291 static void
ary_heap_free_ptr(VALUE ary,const VALUE * ptr,long size)292 ary_heap_free_ptr(VALUE ary, const VALUE *ptr, long size)
293 {
294 if (RARRAY_TRANSIENT_P(ary)) {
295 /* ignore it */
296 }
297 else {
298 ruby_sized_xfree((void *)ptr, size);
299 }
300 }
301
302 static void
ary_heap_free(VALUE ary)303 ary_heap_free(VALUE ary)
304 {
305 if (RARRAY_TRANSIENT_P(ary)) {
306 RARY_TRANSIENT_UNSET(ary);
307 }
308 else {
309 ary_heap_free_ptr(ary, ARY_HEAP_PTR(ary), ARY_HEAP_SIZE(ary));
310 }
311 }
312
313 static void
ary_heap_realloc(VALUE ary,size_t new_capa)314 ary_heap_realloc(VALUE ary, size_t new_capa)
315 {
316 size_t old_capa = ARY_HEAP_CAPA(ary);
317
318 if (RARRAY_TRANSIENT_P(ary)) {
319 if (new_capa <= old_capa) {
320 /* do nothing */
321 }
322 else {
323 VALUE *new_ptr = rb_transient_heap_alloc(ary, sizeof(VALUE) * new_capa);
324
325 if (new_ptr == NULL) {
326 new_ptr = ALLOC_N(VALUE, new_capa);
327 RARY_TRANSIENT_UNSET(ary);
328 }
329
330 MEMCPY(new_ptr, ARY_HEAP_PTR(ary), VALUE, old_capa);
331 ARY_SET_PTR(ary, new_ptr);
332 }
333 }
334 else {
335 SIZED_REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, new_capa, old_capa);
336 }
337 ary_verify(ary);
338 }
339
340 #if USE_TRANSIENT_HEAP
341 static inline void
rb_ary_transient_heap_evacuate_(VALUE ary,int transient,int promote)342 rb_ary_transient_heap_evacuate_(VALUE ary, int transient, int promote)
343 {
344 if (transient) {
345 VALUE *new_ptr;
346 const VALUE *old_ptr = ARY_HEAP_PTR(ary);
347 long capa = ARY_HEAP_CAPA(ary);
348 long len = ARY_HEAP_LEN(ary);
349
350 if (ARY_SHARED_ROOT_P(ary)) {
351 capa = len;
352 }
353
354 assert(ARY_OWNS_HEAP_P(ary));
355 assert(RARRAY_TRANSIENT_P(ary));
356 assert(!ARY_PTR_USING_P(ary));
357
358 if (promote) {
359 new_ptr = ALLOC_N(VALUE, capa);
360 RARY_TRANSIENT_UNSET(ary);
361 }
362 else {
363 new_ptr = ary_heap_alloc(ary, capa);
364 }
365
366 MEMCPY(new_ptr, old_ptr, VALUE, capa);
367 /* do not use ARY_SET_PTR() because they assert !frozen */
368 RARRAY(ary)->as.heap.ptr = new_ptr;
369 }
370
371 ary_verify(ary);
372 }
373
374 void
rb_ary_transient_heap_evacuate(VALUE ary,int promote)375 rb_ary_transient_heap_evacuate(VALUE ary, int promote)
376 {
377 rb_ary_transient_heap_evacuate_(ary, RARRAY_TRANSIENT_P(ary), promote);
378 }
379
380 void
rb_ary_detransient(VALUE ary)381 rb_ary_detransient(VALUE ary)
382 {
383 assert(RARRAY_TRANSIENT_P(ary));
384 rb_ary_transient_heap_evacuate_(ary, TRUE, TRUE);
385 }
386 #else
387 void
rb_ary_detransient(VALUE ary)388 rb_ary_detransient(VALUE ary)
389 {
390 /* do nothing */
391 }
392 #endif
393
394 static void
ary_resize_capa(VALUE ary,long capacity)395 ary_resize_capa(VALUE ary, long capacity)
396 {
397 assert(RARRAY_LEN(ary) <= capacity);
398 assert(!OBJ_FROZEN(ary));
399 assert(!ARY_SHARED_P(ary));
400
401 if (capacity > RARRAY_EMBED_LEN_MAX) {
402 if (ARY_EMBED_P(ary)) {
403 long len = ARY_EMBED_LEN(ary);
404 VALUE *ptr = ary_heap_alloc(ary, capacity);
405
406 MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
407 FL_UNSET_EMBED(ary);
408 ARY_SET_PTR(ary, ptr);
409 ARY_SET_HEAP_LEN(ary, len);
410 }
411 else {
412 ary_heap_realloc(ary, capacity);
413 }
414 ARY_SET_CAPA(ary, capacity);
415 }
416 else {
417 if (!ARY_EMBED_P(ary)) {
418 long len = ARY_HEAP_LEN(ary);
419 long old_capa = ARY_HEAP_CAPA(ary);
420 const VALUE *ptr = ARY_HEAP_PTR(ary);
421
422 if (len > capacity) len = capacity;
423 MEMCPY((VALUE *)RARRAY(ary)->as.ary, ptr, VALUE, len);
424 ary_heap_free_ptr(ary, ptr, old_capa);
425
426 FL_SET_EMBED(ary);
427 ARY_SET_LEN(ary, len);
428 }
429 }
430
431 ary_verify(ary);
432 }
433
434 static inline void
ary_shrink_capa(VALUE ary)435 ary_shrink_capa(VALUE ary)
436 {
437 long capacity = ARY_HEAP_LEN(ary);
438 long old_capa = ARY_HEAP_CAPA(ary);
439 assert(!ARY_SHARED_P(ary));
440 assert(old_capa >= capacity);
441 if (old_capa > capacity) ary_heap_realloc(ary, capacity);
442
443 ary_verify(ary);
444 }
445
446 static void
ary_double_capa(VALUE ary,long min)447 ary_double_capa(VALUE ary, long min)
448 {
449 long new_capa = ARY_CAPA(ary) / 2;
450
451 if (new_capa < ARY_DEFAULT_SIZE) {
452 new_capa = ARY_DEFAULT_SIZE;
453 }
454 if (new_capa >= ARY_MAX_SIZE - min) {
455 new_capa = (ARY_MAX_SIZE - min) / 2;
456 }
457 new_capa += min;
458 ary_resize_capa(ary, new_capa);
459
460 ary_verify(ary);
461 }
462
463 static void
rb_ary_decrement_share(VALUE shared)464 rb_ary_decrement_share(VALUE shared)
465 {
466 if (shared) {
467 long num = ARY_SHARED_NUM(shared) - 1;
468 if (num == 0) {
469 rb_ary_free(shared);
470 rb_gc_force_recycle(shared);
471 }
472 else if (num > 0) {
473 ARY_SET_SHARED_NUM(shared, num);
474 }
475 }
476 }
477
478 static void
rb_ary_unshare(VALUE ary)479 rb_ary_unshare(VALUE ary)
480 {
481 VALUE shared = RARRAY(ary)->as.heap.aux.shared;
482 rb_ary_decrement_share(shared);
483 FL_UNSET_SHARED(ary);
484 }
485
486 static inline void
rb_ary_unshare_safe(VALUE ary)487 rb_ary_unshare_safe(VALUE ary)
488 {
489 if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
490 rb_ary_unshare(ary);
491 }
492 }
493
494 static VALUE
rb_ary_increment_share(VALUE shared)495 rb_ary_increment_share(VALUE shared)
496 {
497 long num = ARY_SHARED_NUM(shared);
498 if (num >= 0) {
499 ARY_SET_SHARED_NUM(shared, num + 1);
500 }
501 return shared;
502 }
503
504 static void
rb_ary_set_shared(VALUE ary,VALUE shared)505 rb_ary_set_shared(VALUE ary, VALUE shared)
506 {
507 rb_ary_increment_share(shared);
508 FL_SET_SHARED(ary);
509 ARY_SET_SHARED(ary, shared);
510 }
511
512 static inline void
rb_ary_modify_check(VALUE ary)513 rb_ary_modify_check(VALUE ary)
514 {
515 rb_check_frozen(ary);
516 ary_verify(ary);
517 }
518
519 void
rb_ary_modify(VALUE ary)520 rb_ary_modify(VALUE ary)
521 {
522 rb_ary_modify_check(ary);
523 if (ARY_SHARED_P(ary)) {
524 long shared_len, len = RARRAY_LEN(ary);
525 VALUE shared = ARY_SHARED(ary);
526
527 ary_verify(shared);
528
529 if (len <= RARRAY_EMBED_LEN_MAX) {
530 const VALUE *ptr = ARY_HEAP_PTR(ary);
531 FL_UNSET_SHARED(ary);
532 FL_SET_EMBED(ary);
533 MEMCPY((VALUE *)ARY_EMBED_PTR(ary), ptr, VALUE, len);
534 rb_ary_decrement_share(shared);
535 ARY_SET_EMBED_LEN(ary, len);
536 }
537 else if (ARY_SHARED_OCCUPIED(shared) && len > ((shared_len = RARRAY_LEN(shared))>>1)) {
538 long shift = RARRAY_CONST_PTR_TRANSIENT(ary) - RARRAY_CONST_PTR_TRANSIENT(shared);
539 FL_UNSET_SHARED(ary);
540 ARY_SET_PTR(ary, RARRAY_CONST_PTR_TRANSIENT(shared));
541 ARY_SET_CAPA(ary, shared_len);
542 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
543 MEMMOVE(ptr, ptr+shift, VALUE, len);
544 });
545 FL_SET_EMBED(shared);
546 rb_ary_decrement_share(shared);
547 }
548 else {
549 VALUE *ptr = ary_heap_alloc(ary, len);
550 MEMCPY(ptr, ARY_HEAP_PTR(ary), VALUE, len);
551 rb_ary_unshare(ary);
552 ARY_SET_CAPA(ary, len);
553 ARY_SET_PTR(ary, ptr);
554 }
555
556 rb_gc_writebarrier_remember(ary);
557 }
558 ary_verify(ary);
559 }
560
561 static VALUE
ary_ensure_room_for_push(VALUE ary,long add_len)562 ary_ensure_room_for_push(VALUE ary, long add_len)
563 {
564 long old_len = RARRAY_LEN(ary);
565 long new_len = old_len + add_len;
566 long capa;
567
568 if (old_len > ARY_MAX_SIZE - add_len) {
569 rb_raise(rb_eIndexError, "index %ld too big", new_len);
570 }
571 if (ARY_SHARED_P(ary)) {
572 if (new_len > RARRAY_EMBED_LEN_MAX) {
573 VALUE shared = ARY_SHARED(ary);
574 if (ARY_SHARED_OCCUPIED(shared)) {
575 if (ARY_HEAP_PTR(ary) - RARRAY_CONST_PTR_TRANSIENT(shared) + new_len <= RARRAY_LEN(shared)) {
576 rb_ary_modify_check(ary);
577
578 ary_verify(ary);
579 ary_verify(shared);
580 return shared;
581 }
582 else {
583 /* if array is shared, then it is likely it participate in push/shift pattern */
584 rb_ary_modify(ary);
585 capa = ARY_CAPA(ary);
586 if (new_len > capa - (capa >> 6)) {
587 ary_double_capa(ary, new_len);
588 }
589 ary_verify(ary);
590 return ary;
591 }
592 }
593 }
594 ary_verify(ary);
595 rb_ary_modify(ary);
596 }
597 else {
598 rb_ary_modify_check(ary);
599 }
600 capa = ARY_CAPA(ary);
601 if (new_len > capa) {
602 ary_double_capa(ary, new_len);
603 }
604
605 ary_verify(ary);
606 return ary;
607 }
608
609 /*
610 * call-seq:
611 * ary.freeze -> ary
612 *
613 * Calls Object#freeze on +ary+ to prevent any further
614 * modification. A RuntimeError will be raised if a modification
615 * attempt is made.
616 *
617 */
618
619 VALUE
rb_ary_freeze(VALUE ary)620 rb_ary_freeze(VALUE ary)
621 {
622 return rb_obj_freeze(ary);
623 }
624
625 /* This can be used to take a snapshot of an array (with
626 e.g. rb_ary_replace) and check later whether the array has been
627 modified from the snapshot. The snapshot is cheap, though if
628 something does modify the array it will pay the cost of copying
629 it. If Array#pop or Array#shift has been called, the array will
630 be still shared with the snapshot, but the array length will
631 differ. */
632 VALUE
rb_ary_shared_with_p(VALUE ary1,VALUE ary2)633 rb_ary_shared_with_p(VALUE ary1, VALUE ary2)
634 {
635 if (!ARY_EMBED_P(ary1) && ARY_SHARED_P(ary1) &&
636 !ARY_EMBED_P(ary2) && ARY_SHARED_P(ary2) &&
637 RARRAY(ary1)->as.heap.aux.shared == RARRAY(ary2)->as.heap.aux.shared &&
638 RARRAY(ary1)->as.heap.len == RARRAY(ary2)->as.heap.len) {
639 return Qtrue;
640 }
641 return Qfalse;
642 }
643
644 static VALUE
ary_alloc(VALUE klass)645 ary_alloc(VALUE klass)
646 {
647 NEWOBJ_OF(ary, struct RArray, klass, T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
648 /* Created array is:
649 * FL_SET_EMBED((VALUE)ary);
650 * ARY_SET_EMBED_LEN((VALUE)ary, 0);
651 */
652 return (VALUE)ary;
653 }
654
655 static VALUE
empty_ary_alloc(VALUE klass)656 empty_ary_alloc(VALUE klass)
657 {
658 RUBY_DTRACE_CREATE_HOOK(ARRAY, 0);
659 return ary_alloc(klass);
660 }
661
662 static VALUE
ary_new(VALUE klass,long capa)663 ary_new(VALUE klass, long capa)
664 {
665 VALUE ary,*ptr;
666
667 if (capa < 0) {
668 rb_raise(rb_eArgError, "negative array size (or size too big)");
669 }
670 if (capa > ARY_MAX_SIZE) {
671 rb_raise(rb_eArgError, "array size too big");
672 }
673
674 RUBY_DTRACE_CREATE_HOOK(ARRAY, capa);
675
676 ary = ary_alloc(klass);
677 if (capa > RARRAY_EMBED_LEN_MAX) {
678 ptr = ary_heap_alloc(ary, capa);
679 FL_UNSET_EMBED(ary);
680 ARY_SET_PTR(ary, ptr);
681 ARY_SET_CAPA(ary, capa);
682 ARY_SET_HEAP_LEN(ary, 0);
683 }
684
685 return ary;
686 }
687
688 VALUE
rb_ary_new_capa(long capa)689 rb_ary_new_capa(long capa)
690 {
691 return ary_new(rb_cArray, capa);
692 }
693
694 VALUE
rb_ary_new(void)695 rb_ary_new(void)
696 {
697 return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
698 }
699
VALUE(rb_ary_new_from_args)700 VALUE
701 (rb_ary_new_from_args)(long n, ...)
702 {
703 va_list ar;
704 VALUE ary;
705 long i;
706
707 ary = rb_ary_new2(n);
708
709 va_start(ar, n);
710 for (i=0; i<n; i++) {
711 ARY_SET(ary, i, va_arg(ar, VALUE));
712 }
713 va_end(ar);
714
715 ARY_SET_LEN(ary, n);
716 return ary;
717 }
718
719 MJIT_FUNC_EXPORTED VALUE
rb_ary_tmp_new_from_values(VALUE klass,long n,const VALUE * elts)720 rb_ary_tmp_new_from_values(VALUE klass, long n, const VALUE *elts)
721 {
722 VALUE ary;
723
724 ary = ary_new(klass, n);
725 if (n > 0 && elts) {
726 ary_memcpy(ary, 0, n, elts);
727 ARY_SET_LEN(ary, n);
728 }
729
730 return ary;
731 }
732
733 VALUE
rb_ary_new_from_values(long n,const VALUE * elts)734 rb_ary_new_from_values(long n, const VALUE *elts)
735 {
736 return rb_ary_tmp_new_from_values(rb_cArray, n, elts);
737 }
738
739 VALUE
rb_ary_tmp_new(long capa)740 rb_ary_tmp_new(long capa)
741 {
742 VALUE ary = ary_new(0, capa);
743 rb_ary_transient_heap_evacuate(ary, TRUE);
744 return ary;
745 }
746
747 VALUE
rb_ary_tmp_new_fill(long capa)748 rb_ary_tmp_new_fill(long capa)
749 {
750 VALUE ary = ary_new(0, capa);
751 ary_memfill(ary, 0, capa, Qnil);
752 ARY_SET_LEN(ary, capa);
753 rb_ary_transient_heap_evacuate(ary, TRUE);
754 return ary;
755 }
756
757 void
rb_ary_free(VALUE ary)758 rb_ary_free(VALUE ary)
759 {
760 if (ARY_OWNS_HEAP_P(ary)) {
761 if (RARRAY_TRANSIENT_P(ary)) {
762 RB_DEBUG_COUNTER_INC(obj_ary_transient);
763 }
764 else {
765 RB_DEBUG_COUNTER_INC(obj_ary_ptr);
766 ary_heap_free(ary);
767 }
768 }
769 else {
770 RB_DEBUG_COUNTER_INC(obj_ary_embed);
771 }
772 }
773
774 RUBY_FUNC_EXPORTED size_t
rb_ary_memsize(VALUE ary)775 rb_ary_memsize(VALUE ary)
776 {
777 if (ARY_OWNS_HEAP_P(ary)) {
778 return ARY_CAPA(ary) * sizeof(VALUE);
779 }
780 else {
781 return 0;
782 }
783 }
784
785 static inline void
ary_discard(VALUE ary)786 ary_discard(VALUE ary)
787 {
788 rb_ary_free(ary);
789 RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
790 RBASIC(ary)->flags &= ~(RARRAY_EMBED_LEN_MASK | RARRAY_TRANSIENT_FLAG);
791 }
792
793 static VALUE
ary_make_shared(VALUE ary)794 ary_make_shared(VALUE ary)
795 {
796 assert(!ARY_EMBED_P(ary));
797 ary_verify(ary);
798
799 if (ARY_SHARED_P(ary)) {
800 return ARY_SHARED(ary);
801 }
802 else if (ARY_SHARED_ROOT_P(ary)) {
803 return ary;
804 }
805 else if (OBJ_FROZEN(ary)) {
806 rb_ary_transient_heap_evacuate(ary, TRUE);
807 ary_shrink_capa(ary);
808 FL_SET_SHARED_ROOT(ary);
809 ARY_SET_SHARED_NUM(ary, 1);
810 return ary;
811 }
812 else {
813 long capa = ARY_CAPA(ary), len = RARRAY_LEN(ary);
814 const VALUE *ptr;
815 NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
816
817 rb_ary_transient_heap_evacuate(ary, TRUE);
818 ptr = ARY_HEAP_PTR(ary);
819
820 FL_UNSET_EMBED(shared);
821 ARY_SET_LEN((VALUE)shared, capa);
822 ARY_SET_PTR((VALUE)shared, ptr);
823 ary_mem_clear((VALUE)shared, len, capa - len);
824 FL_SET_SHARED_ROOT(shared);
825 ARY_SET_SHARED_NUM((VALUE)shared, 1);
826 FL_SET_SHARED(ary);
827 ARY_SET_SHARED(ary, (VALUE)shared);
828 OBJ_FREEZE(shared);
829
830 ary_verify((VALUE)shared);
831 ary_verify(ary);
832 return (VALUE)shared;
833 }
834 }
835
836 static VALUE
ary_make_substitution(VALUE ary)837 ary_make_substitution(VALUE ary)
838 {
839 long len = RARRAY_LEN(ary);
840
841 if (len <= RARRAY_EMBED_LEN_MAX) {
842 VALUE subst = rb_ary_new2(len);
843 ary_memcpy(subst, 0, len, RARRAY_CONST_PTR_TRANSIENT(ary));
844 ARY_SET_EMBED_LEN(subst, len);
845 return subst;
846 }
847 else {
848 return rb_ary_increment_share(ary_make_shared(ary));
849 }
850 }
851
852 VALUE
rb_assoc_new(VALUE car,VALUE cdr)853 rb_assoc_new(VALUE car, VALUE cdr)
854 {
855 return rb_ary_new3(2, car, cdr);
856 }
857
858 VALUE
rb_to_array_type(VALUE ary)859 rb_to_array_type(VALUE ary)
860 {
861 return rb_convert_type_with_id(ary, T_ARRAY, "Array", idTo_ary);
862 }
863 #define to_ary rb_to_array_type
864
865 VALUE
rb_check_array_type(VALUE ary)866 rb_check_array_type(VALUE ary)
867 {
868 return rb_check_convert_type_with_id(ary, T_ARRAY, "Array", idTo_ary);
869 }
870
871 MJIT_FUNC_EXPORTED VALUE
rb_check_to_array(VALUE ary)872 rb_check_to_array(VALUE ary)
873 {
874 return rb_check_convert_type_with_id(ary, T_ARRAY, "Array", idTo_a);
875 }
876
877 /*
878 * call-seq:
879 * Array.try_convert(obj) -> array or nil
880 *
881 * Tries to convert +obj+ into an array, using +to_ary+ method. Returns the
882 * converted array or +nil+ if +obj+ cannot be converted for any reason.
883 * This method can be used to check if an argument is an array.
884 *
885 * Array.try_convert([1]) #=> [1]
886 * Array.try_convert("1") #=> nil
887 *
888 * if tmp = Array.try_convert(arg)
889 * # the argument is an array
890 * elsif tmp = String.try_convert(arg)
891 * # the argument is a string
892 * end
893 *
894 */
895
896 static VALUE
rb_ary_s_try_convert(VALUE dummy,VALUE ary)897 rb_ary_s_try_convert(VALUE dummy, VALUE ary)
898 {
899 return rb_check_array_type(ary);
900 }
901
902 /*
903 * call-seq:
904 * Array.new(size=0, default=nil)
905 * Array.new(array)
906 * Array.new(size) {|index| block }
907 *
908 * Returns a new array.
909 *
910 * In the first form, if no arguments are sent, the new array will be empty.
911 * When a +size+ and an optional +default+ are sent, an array is created with
912 * +size+ copies of +default+. Take notice that all elements will reference the
913 * same object +default+.
914 *
915 * The second form creates a copy of the array passed as a parameter (the
916 * array is generated by calling to_ary on the parameter).
917 *
918 * first_array = ["Matz", "Guido"]
919 *
920 * second_array = Array.new(first_array) #=> ["Matz", "Guido"]
921 *
922 * first_array.equal? second_array #=> false
923 *
924 * In the last form, an array of the given size is created. Each element in
925 * this array is created by passing the element's index to the given block
926 * and storing the return value.
927 *
928 * Array.new(3) {|index| index ** 2}
929 * # => [0, 1, 4]
930 *
931 * == Common gotchas
932 *
933 * When sending the second parameter, the same object will be used as the
934 * value for all the array elements:
935 *
936 * a = Array.new(2, Hash.new)
937 * # => [{}, {}]
938 *
939 * a[0]['cat'] = 'feline'
940 * a # => [{"cat"=>"feline"}, {"cat"=>"feline"}]
941 *
942 * a[1]['cat'] = 'Felix'
943 * a # => [{"cat"=>"Felix"}, {"cat"=>"Felix"}]
944 *
945 * Since all the Array elements store the same hash, changes to one of them
946 * will affect them all.
947 *
948 * If multiple copies are what you want, you should use the block
949 * version which uses the result of that block each time an element
950 * of the array needs to be initialized:
951 *
952 * a = Array.new(2) {Hash.new}
953 * a[0]['cat'] = 'feline'
954 * a # => [{"cat"=>"feline"}, {}]
955 *
956 */
957
958 static VALUE
rb_ary_initialize(int argc,VALUE * argv,VALUE ary)959 rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
960 {
961 long len;
962 VALUE size, val;
963
964 rb_ary_modify(ary);
965 if (argc == 0) {
966 if (ARY_OWNS_HEAP_P(ary) && ARY_HEAP_PTR(ary) != NULL) {
967 ary_heap_free(ary);
968 }
969 rb_ary_unshare_safe(ary);
970 FL_SET_EMBED(ary);
971 ARY_SET_EMBED_LEN(ary, 0);
972 if (rb_block_given_p()) {
973 rb_warning("given block not used");
974 }
975 return ary;
976 }
977 rb_scan_args(argc, argv, "02", &size, &val);
978 if (argc == 1 && !FIXNUM_P(size)) {
979 val = rb_check_array_type(size);
980 if (!NIL_P(val)) {
981 rb_ary_replace(ary, val);
982 return ary;
983 }
984 }
985
986 len = NUM2LONG(size);
987 /* NUM2LONG() may call size.to_int, ary can be frozen, modified, etc */
988 if (len < 0) {
989 rb_raise(rb_eArgError, "negative array size");
990 }
991 if (len > ARY_MAX_SIZE) {
992 rb_raise(rb_eArgError, "array size too big");
993 }
994 /* recheck after argument conversion */
995 rb_ary_modify(ary);
996 ary_resize_capa(ary, len);
997 if (rb_block_given_p()) {
998 long i;
999
1000 if (argc == 2) {
1001 rb_warn("block supersedes default value argument");
1002 }
1003 for (i=0; i<len; i++) {
1004 rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
1005 ARY_SET_LEN(ary, i + 1);
1006 }
1007 }
1008 else {
1009 ary_memfill(ary, 0, len, val);
1010 ARY_SET_LEN(ary, len);
1011 }
1012 return ary;
1013 }
1014
1015 /*
1016 * Returns a new array populated with the given objects.
1017 *
1018 * Array.[]( 1, 'a', /^A/) # => [1, "a", /^A/]
1019 * Array[ 1, 'a', /^A/ ] # => [1, "a", /^A/]
1020 * [ 1, 'a', /^A/ ] # => [1, "a", /^A/]
1021 */
1022
1023 static VALUE
rb_ary_s_create(int argc,VALUE * argv,VALUE klass)1024 rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
1025 {
1026 VALUE ary = ary_new(klass, argc);
1027 if (argc > 0 && argv) {
1028 ary_memcpy(ary, 0, argc, argv);
1029 ARY_SET_LEN(ary, argc);
1030 }
1031
1032 return ary;
1033 }
1034
1035 void
rb_ary_store(VALUE ary,long idx,VALUE val)1036 rb_ary_store(VALUE ary, long idx, VALUE val)
1037 {
1038 long len = RARRAY_LEN(ary);
1039
1040 if (idx < 0) {
1041 idx += len;
1042 if (idx < 0) {
1043 rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
1044 idx - len, -len);
1045 }
1046 }
1047 else if (idx >= ARY_MAX_SIZE) {
1048 rb_raise(rb_eIndexError, "index %ld too big", idx);
1049 }
1050
1051 rb_ary_modify(ary);
1052 if (idx >= ARY_CAPA(ary)) {
1053 ary_double_capa(ary, idx);
1054 }
1055 if (idx > len) {
1056 ary_mem_clear(ary, len, idx - len + 1);
1057 }
1058
1059 if (idx >= len) {
1060 ARY_SET_LEN(ary, idx + 1);
1061 }
1062 ARY_SET(ary, idx, val);
1063 }
1064
1065 static VALUE
ary_make_partial(VALUE ary,VALUE klass,long offset,long len)1066 ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
1067 {
1068 assert(offset >= 0);
1069 assert(len >= 0);
1070 assert(offset+len <= RARRAY_LEN(ary));
1071
1072 if (len <= RARRAY_EMBED_LEN_MAX) {
1073 VALUE result = ary_alloc(klass);
1074 ary_memcpy(result, 0, len, RARRAY_CONST_PTR_TRANSIENT(ary) + offset);
1075 ARY_SET_EMBED_LEN(result, len);
1076 return result;
1077 }
1078 else {
1079 VALUE shared, result = ary_alloc(klass);
1080 FL_UNSET_EMBED(result);
1081
1082 shared = ary_make_shared(ary);
1083 ARY_SET_PTR(result, RARRAY_CONST_PTR_TRANSIENT(ary));
1084 ARY_SET_LEN(result, RARRAY_LEN(ary));
1085 rb_ary_set_shared(result, shared);
1086
1087 ARY_INCREASE_PTR(result, offset);
1088 ARY_SET_LEN(result, len);
1089
1090 ary_verify(shared);
1091 ary_verify(result);
1092 return result;
1093 }
1094 }
1095
1096 static VALUE
ary_make_shared_copy(VALUE ary)1097 ary_make_shared_copy(VALUE ary)
1098 {
1099 return ary_make_partial(ary, rb_obj_class(ary), 0, RARRAY_LEN(ary));
1100 }
1101
1102 enum ary_take_pos_flags
1103 {
1104 ARY_TAKE_FIRST = 0,
1105 ARY_TAKE_LAST = 1
1106 };
1107
1108 static VALUE
ary_take_first_or_last(int argc,const VALUE * argv,VALUE ary,enum ary_take_pos_flags last)1109 ary_take_first_or_last(int argc, const VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
1110 {
1111 long n;
1112 long len;
1113 long offset = 0;
1114
1115 argc = rb_check_arity(argc, 0, 1);
1116 /* the case optional argument is ommited should be handled in
1117 * callers of this function. if another arity case is added,
1118 * this arity check needs to rewrite. */
1119 RUBY_ASSERT_WHEN(TRUE, argc == 1);
1120
1121 n = NUM2LONG(argv[0]);
1122 len = RARRAY_LEN(ary);
1123 if (n > len) {
1124 n = len;
1125 }
1126 else if (n < 0) {
1127 rb_raise(rb_eArgError, "negative array size");
1128 }
1129 if (last) {
1130 offset = len - n;
1131 }
1132 return ary_make_partial(ary, rb_cArray, offset, n);
1133 }
1134
1135 /*
1136 * call-seq:
1137 * ary << obj -> ary
1138 *
1139 * Append---Pushes the given object on to the end of this array. This
1140 * expression returns the array itself, so several appends
1141 * may be chained together.
1142 *
1143 * a = [ 1, 2 ]
1144 * a << "c" << "d" << [ 3, 4 ]
1145 * #=> [ 1, 2, "c", "d", [ 3, 4 ] ]
1146 * a
1147 * #=> [ 1, 2, "c", "d", [ 3, 4 ] ]
1148 *
1149 */
1150
1151 VALUE
rb_ary_push(VALUE ary,VALUE item)1152 rb_ary_push(VALUE ary, VALUE item)
1153 {
1154 long idx = RARRAY_LEN((ary_verify(ary), ary));
1155 VALUE target_ary = ary_ensure_room_for_push(ary, 1);
1156 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
1157 RB_OBJ_WRITE(target_ary, &ptr[idx], item);
1158 });
1159 ARY_SET_LEN(ary, idx + 1);
1160 ary_verify(ary);
1161 return ary;
1162 }
1163
1164 VALUE
rb_ary_cat(VALUE ary,const VALUE * argv,long len)1165 rb_ary_cat(VALUE ary, const VALUE *argv, long len)
1166 {
1167 long oldlen = RARRAY_LEN(ary);
1168 VALUE target_ary = ary_ensure_room_for_push(ary, len);
1169 ary_memcpy0(ary, oldlen, len, argv, target_ary);
1170 ARY_SET_LEN(ary, oldlen + len);
1171 return ary;
1172 }
1173
1174 /*
1175 * call-seq:
1176 * ary.push(obj, ...) -> ary
1177 * ary.append(obj, ...) -> ary
1178 *
1179 * Append --- Pushes the given object(s) on to the end of this array. This
1180 * expression returns the array itself, so several appends
1181 * may be chained together. See also Array#pop for the opposite
1182 * effect.
1183 *
1184 * a = [ "a", "b", "c" ]
1185 * a.push("d", "e", "f")
1186 * #=> ["a", "b", "c", "d", "e", "f"]
1187 * [1, 2, 3].push(4).push(5)
1188 * #=> [1, 2, 3, 4, 5]
1189 */
1190
1191 static VALUE
rb_ary_push_m(int argc,VALUE * argv,VALUE ary)1192 rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
1193 {
1194 return rb_ary_cat(ary, argv, argc);
1195 }
1196
1197 VALUE
rb_ary_pop(VALUE ary)1198 rb_ary_pop(VALUE ary)
1199 {
1200 long n;
1201 rb_ary_modify_check(ary);
1202 n = RARRAY_LEN(ary);
1203 if (n == 0) return Qnil;
1204 if (ARY_OWNS_HEAP_P(ary) &&
1205 n * 3 < ARY_CAPA(ary) &&
1206 ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
1207 {
1208 ary_resize_capa(ary, n * 2);
1209 }
1210 --n;
1211 ARY_SET_LEN(ary, n);
1212 ary_verify(ary);
1213 return RARRAY_AREF(ary, n);
1214 }
1215
1216 /*
1217 * call-seq:
1218 * ary.pop -> obj or nil
1219 * ary.pop(n) -> new_ary
1220 *
1221 * Removes the last element from +self+ and returns it, or
1222 * +nil+ if the array is empty.
1223 *
1224 * If a number +n+ is given, returns an array of the last +n+ elements
1225 * (or less) just like <code>array.slice!(-n, n)</code> does. See also
1226 * Array#push for the opposite effect.
1227 *
1228 * a = [ "a", "b", "c", "d" ]
1229 * a.pop #=> "d"
1230 * a.pop(2) #=> ["b", "c"]
1231 * a #=> ["a"]
1232 */
1233
1234 static VALUE
rb_ary_pop_m(int argc,VALUE * argv,VALUE ary)1235 rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
1236 {
1237 VALUE result;
1238
1239 if (argc == 0) {
1240 return rb_ary_pop(ary);
1241 }
1242
1243 rb_ary_modify_check(ary);
1244 result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
1245 ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
1246 ary_verify(ary);
1247 return result;
1248 }
1249
1250 VALUE
rb_ary_shift(VALUE ary)1251 rb_ary_shift(VALUE ary)
1252 {
1253 VALUE top;
1254 long len = RARRAY_LEN(ary);
1255
1256 rb_ary_modify_check(ary);
1257 if (len == 0) return Qnil;
1258 top = RARRAY_AREF(ary, 0);
1259 if (!ARY_SHARED_P(ary)) {
1260 if (len < ARY_DEFAULT_SIZE) {
1261 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
1262 MEMMOVE(ptr, ptr+1, VALUE, len-1);
1263 }); /* WB: no new reference */
1264 ARY_INCREASE_LEN(ary, -1);
1265 ary_verify(ary);
1266 return top;
1267 }
1268 assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */
1269
1270 ARY_SET(ary, 0, Qnil);
1271 ary_make_shared(ary);
1272 }
1273 else if (ARY_SHARED_OCCUPIED(ARY_SHARED(ary))) {
1274 RARRAY_PTR_USE_TRANSIENT(ary, ptr, ptr[0] = Qnil);
1275 }
1276 ARY_INCREASE_PTR(ary, 1); /* shift ptr */
1277 ARY_INCREASE_LEN(ary, -1);
1278
1279 ary_verify(ary);
1280
1281 return top;
1282 }
1283
1284 /*
1285 * call-seq:
1286 * ary.shift -> obj or nil
1287 * ary.shift(n) -> new_ary
1288 *
1289 * Removes the first element of +self+ and returns it (shifting all
1290 * other elements down by one). Returns +nil+ if the array
1291 * is empty.
1292 *
1293 * If a number +n+ is given, returns an array of the first +n+ elements
1294 * (or less) just like <code>array.slice!(0, n)</code> does. With +ary+
1295 * containing only the remainder elements, not including what was shifted to
1296 * +new_ary+. See also Array#unshift for the opposite effect.
1297 *
1298 * args = [ "-m", "-q", "filename" ]
1299 * args.shift #=> "-m"
1300 * args #=> ["-q", "filename"]
1301 *
1302 * args = [ "-m", "-q", "filename" ]
1303 * args.shift(2) #=> ["-m", "-q"]
1304 * args #=> ["filename"]
1305 */
1306
1307 static VALUE
rb_ary_shift_m(int argc,VALUE * argv,VALUE ary)1308 rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
1309 {
1310 VALUE result;
1311 long n;
1312
1313 if (argc == 0) {
1314 return rb_ary_shift(ary);
1315 }
1316
1317 rb_ary_modify_check(ary);
1318 result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
1319 n = RARRAY_LEN(result);
1320 rb_ary_behead(ary,n);
1321
1322 return result;
1323 }
1324
1325 MJIT_FUNC_EXPORTED VALUE
rb_ary_behead(VALUE ary,long n)1326 rb_ary_behead(VALUE ary, long n)
1327 {
1328 if(n<=0) return ary;
1329
1330 rb_ary_modify_check(ary);
1331 if (ARY_SHARED_P(ary)) {
1332 if (ARY_SHARED_OCCUPIED(ARY_SHARED(ary))) {
1333 setup_occupied_shared:
1334 ary_mem_clear(ary, 0, n);
1335 }
1336 ARY_INCREASE_PTR(ary, n);
1337 }
1338 else {
1339 if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
1340 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
1341 MEMMOVE(ptr, ptr+n, VALUE, RARRAY_LEN(ary)-n);
1342 }); /* WB: no new reference */
1343 }
1344 else {
1345 ary_make_shared(ary);
1346 goto setup_occupied_shared;
1347 }
1348 }
1349 ARY_INCREASE_LEN(ary, -n);
1350
1351 ary_verify(ary);
1352 return ary;
1353 }
1354
1355 static VALUE
ary_ensure_room_for_unshift(VALUE ary,int argc)1356 ary_ensure_room_for_unshift(VALUE ary, int argc)
1357 {
1358 long len = RARRAY_LEN(ary);
1359 long new_len = len + argc;
1360 long capa;
1361 const VALUE *head, *sharedp;
1362
1363 if (len > ARY_MAX_SIZE - argc) {
1364 rb_raise(rb_eIndexError, "index %ld too big", new_len);
1365 }
1366
1367 if (ARY_SHARED_P(ary)) {
1368 VALUE shared = ARY_SHARED(ary);
1369 capa = RARRAY_LEN(shared);
1370 if (ARY_SHARED_OCCUPIED(shared) && capa > new_len) {
1371 rb_ary_modify_check(ary);
1372 head = RARRAY_CONST_PTR_TRANSIENT(ary);
1373 sharedp = RARRAY_CONST_PTR_TRANSIENT(shared);
1374 goto makeroom_if_need;
1375 }
1376 }
1377
1378 rb_ary_modify(ary);
1379 capa = ARY_CAPA(ary);
1380 if (capa - (capa >> 6) <= new_len) {
1381 ary_double_capa(ary, new_len);
1382 }
1383
1384 /* use shared array for big "queues" */
1385 if (new_len > ARY_DEFAULT_SIZE * 4) {
1386 ary_verify(ary);
1387
1388 /* make a room for unshifted items */
1389 capa = ARY_CAPA(ary);
1390 ary_make_shared(ary);
1391
1392 head = sharedp = RARRAY_CONST_PTR_TRANSIENT(ary);
1393 goto makeroom;
1394 makeroom_if_need:
1395 if (head - sharedp < argc) {
1396 long room;
1397 makeroom:
1398 room = capa - new_len;
1399 room -= room >> 4;
1400 MEMMOVE((VALUE *)sharedp + argc + room, head, VALUE, len);
1401 head = sharedp + argc + room;
1402 }
1403 ARY_SET_PTR(ary, head - argc);
1404 assert(ARY_SHARED_OCCUPIED(ARY_SHARED(ary)));
1405
1406 ary_verify(ary);
1407 return ARY_SHARED(ary);
1408 }
1409 else {
1410 /* sliding items */
1411 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
1412 MEMMOVE(ptr + argc, ptr, VALUE, len);
1413 });
1414
1415 ary_verify(ary);
1416 return ary;
1417 }
1418 }
1419
1420 /*
1421 * call-seq:
1422 * ary.unshift(obj, ...) -> ary
1423 * ary.prepend(obj, ...) -> ary
1424 *
1425 * Prepends objects to the front of +self+, moving other elements upwards.
1426 * See also Array#shift for the opposite effect.
1427 *
1428 * a = [ "b", "c", "d" ]
1429 * a.unshift("a") #=> ["a", "b", "c", "d"]
1430 * a.unshift(1, 2) #=> [ 1, 2, "a", "b", "c", "d"]
1431 */
1432
1433 static VALUE
rb_ary_unshift_m(int argc,VALUE * argv,VALUE ary)1434 rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
1435 {
1436 long len = RARRAY_LEN(ary);
1437 VALUE target_ary;
1438
1439 if (argc == 0) {
1440 rb_ary_modify_check(ary);
1441 return ary;
1442 }
1443
1444 target_ary = ary_ensure_room_for_unshift(ary, argc);
1445 ary_memcpy0(ary, 0, argc, argv, target_ary);
1446 ARY_SET_LEN(ary, len + argc);
1447 return ary;
1448 }
1449
1450 VALUE
rb_ary_unshift(VALUE ary,VALUE item)1451 rb_ary_unshift(VALUE ary, VALUE item)
1452 {
1453 return rb_ary_unshift_m(1,&item,ary);
1454 }
1455
1456 /* faster version - use this if you don't need to treat negative offset */
1457 static inline VALUE
rb_ary_elt(VALUE ary,long offset)1458 rb_ary_elt(VALUE ary, long offset)
1459 {
1460 long len = RARRAY_LEN(ary);
1461 if (len == 0) return Qnil;
1462 if (offset < 0 || len <= offset) {
1463 return Qnil;
1464 }
1465 return RARRAY_AREF(ary, offset);
1466 }
1467
1468 VALUE
rb_ary_entry(VALUE ary,long offset)1469 rb_ary_entry(VALUE ary, long offset)
1470 {
1471 return rb_ary_entry_internal(ary, offset);
1472 }
1473
1474 VALUE
rb_ary_subseq(VALUE ary,long beg,long len)1475 rb_ary_subseq(VALUE ary, long beg, long len)
1476 {
1477 VALUE klass;
1478 long alen = RARRAY_LEN(ary);
1479
1480 if (beg > alen) return Qnil;
1481 if (beg < 0 || len < 0) return Qnil;
1482
1483 if (alen < len || alen < beg + len) {
1484 len = alen - beg;
1485 }
1486 klass = rb_obj_class(ary);
1487 if (len == 0) return ary_new(klass, 0);
1488
1489 return ary_make_partial(ary, klass, beg, len);
1490 }
1491
1492 /*
1493 * call-seq:
1494 * ary[index] -> obj or nil
1495 * ary[start, length] -> new_ary or nil
1496 * ary[range] -> new_ary or nil
1497 * ary.slice(index) -> obj or nil
1498 * ary.slice(start, length) -> new_ary or nil
1499 * ary.slice(range) -> new_ary or nil
1500 *
1501 * Element Reference --- Returns the element at +index+, or returns a
1502 * subarray starting at the +start+ index and continuing for +length+
1503 * elements, or returns a subarray specified by +range+ of indices.
1504 *
1505 * Negative indices count backward from the end of the array (-1 is the last
1506 * element). For +start+ and +range+ cases the starting index is just before
1507 * an element. Additionally, an empty array is returned when the starting
1508 * index for an element range is at the end of the array.
1509 *
1510 * Returns +nil+ if the index (or starting index) are out of range.
1511 *
1512 * a = [ "a", "b", "c", "d", "e" ]
1513 * a[2] + a[0] + a[1] #=> "cab"
1514 * a[6] #=> nil
1515 * a[1, 2] #=> [ "b", "c" ]
1516 * a[1..3] #=> [ "b", "c", "d" ]
1517 * a[4..7] #=> [ "e" ]
1518 * a[6..10] #=> nil
1519 * a[-3, 3] #=> [ "c", "d", "e" ]
1520 * # special cases
1521 * a[5] #=> nil
1522 * a[6, 1] #=> nil
1523 * a[5, 1] #=> []
1524 * a[5..10] #=> []
1525 *
1526 */
1527
1528 VALUE
rb_ary_aref(int argc,const VALUE * argv,VALUE ary)1529 rb_ary_aref(int argc, const VALUE *argv, VALUE ary)
1530 {
1531 rb_check_arity(argc, 1, 2);
1532 if (argc == 2) {
1533 return rb_ary_aref2(ary, argv[0], argv[1]);
1534 }
1535 return rb_ary_aref1(ary, argv[0]);
1536 }
1537
1538 VALUE
rb_ary_aref2(VALUE ary,VALUE b,VALUE e)1539 rb_ary_aref2(VALUE ary, VALUE b, VALUE e)
1540 {
1541 long beg = NUM2LONG(b);
1542 long len = NUM2LONG(e);
1543 if (beg < 0) {
1544 beg += RARRAY_LEN(ary);
1545 }
1546 return rb_ary_subseq(ary, beg, len);
1547 }
1548
1549 MJIT_FUNC_EXPORTED VALUE
rb_ary_aref1(VALUE ary,VALUE arg)1550 rb_ary_aref1(VALUE ary, VALUE arg)
1551 {
1552 long beg, len;
1553
1554 /* special case - speeding up */
1555 if (FIXNUM_P(arg)) {
1556 return rb_ary_entry(ary, FIX2LONG(arg));
1557 }
1558 /* check if idx is Range */
1559 switch (rb_range_beg_len(arg, &beg, &len, RARRAY_LEN(ary), 0)) {
1560 case Qfalse:
1561 break;
1562 case Qnil:
1563 return Qnil;
1564 default:
1565 return rb_ary_subseq(ary, beg, len);
1566 }
1567 return rb_ary_entry(ary, NUM2LONG(arg));
1568 }
1569
1570 /*
1571 * call-seq:
1572 * ary.at(index) -> obj or nil
1573 *
1574 * Returns the element at +index+. A negative index counts from the end of
1575 * +self+. Returns +nil+ if the index is out of range. See also
1576 * Array#[].
1577 *
1578 * a = [ "a", "b", "c", "d", "e" ]
1579 * a.at(0) #=> "a"
1580 * a.at(-1) #=> "e"
1581 */
1582
1583 VALUE
rb_ary_at(VALUE ary,VALUE pos)1584 rb_ary_at(VALUE ary, VALUE pos)
1585 {
1586 return rb_ary_entry(ary, NUM2LONG(pos));
1587 }
1588
1589 /*
1590 * call-seq:
1591 * ary.first -> obj or nil
1592 * ary.first(n) -> new_ary
1593 *
1594 * Returns the first element, or the first +n+ elements, of the array.
1595 * If the array is empty, the first form returns +nil+, and the
1596 * second form returns an empty array. See also Array#last for
1597 * the opposite effect.
1598 *
1599 * a = [ "q", "r", "s", "t" ]
1600 * a.first #=> "q"
1601 * a.first(2) #=> ["q", "r"]
1602 */
1603
1604 static VALUE
rb_ary_first(int argc,VALUE * argv,VALUE ary)1605 rb_ary_first(int argc, VALUE *argv, VALUE ary)
1606 {
1607 if (argc == 0) {
1608 if (RARRAY_LEN(ary) == 0) return Qnil;
1609 return RARRAY_AREF(ary, 0);
1610 }
1611 else {
1612 return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
1613 }
1614 }
1615
1616 /*
1617 * call-seq:
1618 * ary.last -> obj or nil
1619 * ary.last(n) -> new_ary
1620 *
1621 * Returns the last element(s) of +self+. If the array is empty,
1622 * the first form returns +nil+.
1623 *
1624 * See also Array#first for the opposite effect.
1625 *
1626 * a = [ "w", "x", "y", "z" ]
1627 * a.last #=> "z"
1628 * a.last(2) #=> ["y", "z"]
1629 */
1630
1631 VALUE
rb_ary_last(int argc,const VALUE * argv,VALUE ary)1632 rb_ary_last(int argc, const VALUE *argv, VALUE ary)
1633 {
1634 if (argc == 0) {
1635 long len = RARRAY_LEN(ary);
1636 if (len == 0) return Qnil;
1637 return RARRAY_AREF(ary, len-1);
1638 }
1639 else {
1640 return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
1641 }
1642 }
1643
1644 /*
1645 * call-seq:
1646 * ary.fetch(index) -> obj
1647 * ary.fetch(index, default) -> obj
1648 * ary.fetch(index) {|index| block} -> obj
1649 *
1650 * Tries to return the element at position +index+, but throws an IndexError
1651 * exception if the referenced +index+ lies outside of the array bounds. This
1652 * error can be prevented by supplying a second argument, which will act as a
1653 * +default+ value.
1654 *
1655 * Alternatively, if a block is given it will only be executed when an
1656 * invalid +index+ is referenced.
1657 *
1658 * Negative values of +index+ count from the end of the array.
1659 *
1660 * a = [ 11, 22, 33, 44 ]
1661 * a.fetch(1) #=> 22
1662 * a.fetch(-1) #=> 44
1663 * a.fetch(4, 'cat') #=> "cat"
1664 * a.fetch(100) {|i| puts "#{i} is out of bounds"}
1665 * #=> "100 is out of bounds"
1666 */
1667
1668 static VALUE
rb_ary_fetch(int argc,VALUE * argv,VALUE ary)1669 rb_ary_fetch(int argc, VALUE *argv, VALUE ary)
1670 {
1671 VALUE pos, ifnone;
1672 long block_given;
1673 long idx;
1674
1675 rb_scan_args(argc, argv, "11", &pos, &ifnone);
1676 block_given = rb_block_given_p();
1677 if (block_given && argc == 2) {
1678 rb_warn("block supersedes default value argument");
1679 }
1680 idx = NUM2LONG(pos);
1681
1682 if (idx < 0) {
1683 idx += RARRAY_LEN(ary);
1684 }
1685 if (idx < 0 || RARRAY_LEN(ary) <= idx) {
1686 if (block_given) return rb_yield(pos);
1687 if (argc == 1) {
1688 rb_raise(rb_eIndexError, "index %ld outside of array bounds: %ld...%ld",
1689 idx - (idx < 0 ? RARRAY_LEN(ary) : 0), -RARRAY_LEN(ary), RARRAY_LEN(ary));
1690 }
1691 return ifnone;
1692 }
1693 return RARRAY_AREF(ary, idx);
1694 }
1695
1696 /*
1697 * call-seq:
1698 * ary.find_index(obj) -> int or nil
1699 * ary.find_index {|item| block} -> int or nil
1700 * ary.find_index -> Enumerator
1701 * ary.index(obj) -> int or nil
1702 * ary.index {|item| block} -> int or nil
1703 * ary.index -> Enumerator
1704 *
1705 * Returns the _index_ of the first object in +ary+ such that the object is
1706 * <code>==</code> to +obj+.
1707 *
1708 * If a block is given instead of an argument, returns the _index_ of the
1709 * first object for which the block returns +true+. Returns +nil+ if no
1710 * match is found.
1711 *
1712 * See also Array#rindex.
1713 *
1714 * An Enumerator is returned if neither a block nor argument is given.
1715 *
1716 * a = [ "a", "b", "c" ]
1717 * a.index("b") #=> 1
1718 * a.index("z") #=> nil
1719 * a.index {|x| x == "b"} #=> 1
1720 */
1721
1722 static VALUE
rb_ary_index(int argc,VALUE * argv,VALUE ary)1723 rb_ary_index(int argc, VALUE *argv, VALUE ary)
1724 {
1725 VALUE val;
1726 long i;
1727
1728 if (argc == 0) {
1729 RETURN_ENUMERATOR(ary, 0, 0);
1730 for (i=0; i<RARRAY_LEN(ary); i++) {
1731 if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) {
1732 return LONG2NUM(i);
1733 }
1734 }
1735 return Qnil;
1736 }
1737 rb_check_arity(argc, 0, 1);
1738 val = argv[0];
1739 if (rb_block_given_p())
1740 rb_warn("given block not used");
1741 for (i=0; i<RARRAY_LEN(ary); i++) {
1742 VALUE e = RARRAY_AREF(ary, i);
1743 if (rb_equal(e, val)) {
1744 return LONG2NUM(i);
1745 }
1746 }
1747 return Qnil;
1748 }
1749
1750 /*
1751 * call-seq:
1752 * ary.rindex(obj) -> int or nil
1753 * ary.rindex {|item| block} -> int or nil
1754 * ary.rindex -> Enumerator
1755 *
1756 * Returns the _index_ of the last object in +self+ <code>==</code> to +obj+.
1757 *
1758 * If a block is given instead of an argument, returns the _index_ of the
1759 * first object for which the block returns +true+, starting from the last
1760 * object.
1761 *
1762 * Returns +nil+ if no match is found.
1763 *
1764 * See also Array#index.
1765 *
1766 * If neither block nor argument is given, an Enumerator is returned instead.
1767 *
1768 * a = [ "a", "b", "b", "b", "c" ]
1769 * a.rindex("b") #=> 3
1770 * a.rindex("z") #=> nil
1771 * a.rindex {|x| x == "b"} #=> 3
1772 */
1773
1774 static VALUE
rb_ary_rindex(int argc,VALUE * argv,VALUE ary)1775 rb_ary_rindex(int argc, VALUE *argv, VALUE ary)
1776 {
1777 VALUE val;
1778 long i = RARRAY_LEN(ary), len;
1779
1780 if (argc == 0) {
1781 RETURN_ENUMERATOR(ary, 0, 0);
1782 while (i--) {
1783 if (RTEST(rb_yield(RARRAY_AREF(ary, i))))
1784 return LONG2NUM(i);
1785 if (i > (len = RARRAY_LEN(ary))) {
1786 i = len;
1787 }
1788 }
1789 return Qnil;
1790 }
1791 rb_check_arity(argc, 0, 1);
1792 val = argv[0];
1793 if (rb_block_given_p())
1794 rb_warn("given block not used");
1795 while (i--) {
1796 VALUE e = RARRAY_AREF(ary, i);
1797 if (rb_equal(e, val)) {
1798 return LONG2NUM(i);
1799 }
1800 }
1801 return Qnil;
1802 }
1803
1804 VALUE
rb_ary_to_ary(VALUE obj)1805 rb_ary_to_ary(VALUE obj)
1806 {
1807 VALUE tmp = rb_check_array_type(obj);
1808
1809 if (!NIL_P(tmp)) return tmp;
1810 return rb_ary_new3(1, obj);
1811 }
1812
1813 static void
rb_ary_splice(VALUE ary,long beg,long len,const VALUE * rptr,long rlen)1814 rb_ary_splice(VALUE ary, long beg, long len, const VALUE *rptr, long rlen)
1815 {
1816 long olen;
1817 long rofs;
1818
1819 if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
1820 olen = RARRAY_LEN(ary);
1821 if (beg < 0) {
1822 beg += olen;
1823 if (beg < 0) {
1824 rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
1825 beg - olen, -olen);
1826 }
1827 }
1828 if (olen < len || olen < beg + len) {
1829 len = olen - beg;
1830 }
1831
1832 {
1833 const VALUE *optr = RARRAY_CONST_PTR_TRANSIENT(ary);
1834 rofs = (rptr >= optr && rptr < optr + olen) ? rptr - optr : -1;
1835 }
1836
1837 if (beg >= olen) {
1838 VALUE target_ary;
1839 if (beg > ARY_MAX_SIZE - rlen) {
1840 rb_raise(rb_eIndexError, "index %ld too big", beg);
1841 }
1842 target_ary = ary_ensure_room_for_push(ary, rlen-len); /* len is 0 or negative */
1843 len = beg + rlen;
1844 ary_mem_clear(ary, olen, beg - olen);
1845 if (rlen > 0) {
1846 if (rofs != -1) rptr = RARRAY_CONST_PTR_TRANSIENT(ary) + rofs;
1847 ary_memcpy0(ary, beg, rlen, rptr, target_ary);
1848 }
1849 ARY_SET_LEN(ary, len);
1850 }
1851 else {
1852 long alen;
1853
1854 if (olen - len > ARY_MAX_SIZE - rlen) {
1855 rb_raise(rb_eIndexError, "index %ld too big", olen + rlen - len);
1856 }
1857 rb_ary_modify(ary);
1858 alen = olen + rlen - len;
1859 if (alen >= ARY_CAPA(ary)) {
1860 ary_double_capa(ary, alen);
1861 }
1862
1863 if (len != rlen) {
1864 RARRAY_PTR_USE_TRANSIENT(ary, ptr,
1865 MEMMOVE(ptr + beg + rlen, ptr + beg + len,
1866 VALUE, olen - (beg + len)));
1867 ARY_SET_LEN(ary, alen);
1868 }
1869 if (rlen > 0) {
1870 if (rofs != -1) rptr = RARRAY_CONST_PTR_TRANSIENT(ary) + rofs;
1871 /* give up wb-protected ary */
1872 RB_OBJ_WB_UNPROTECT_FOR(ARRAY, ary);
1873
1874 /* do not use RARRAY_PTR() because it can causes GC.
1875 * ary can contain T_NONE object because it is not cleared.
1876 */
1877 RARRAY_PTR_USE_TRANSIENT(ary, ptr,
1878 MEMMOVE(ptr + beg, rptr, VALUE, rlen));
1879 }
1880 }
1881 }
1882
1883 void
rb_ary_set_len(VALUE ary,long len)1884 rb_ary_set_len(VALUE ary, long len)
1885 {
1886 long capa;
1887
1888 rb_ary_modify_check(ary);
1889 if (ARY_SHARED_P(ary)) {
1890 rb_raise(rb_eRuntimeError, "can't set length of shared ");
1891 }
1892 if (len > (capa = (long)ARY_CAPA(ary))) {
1893 rb_bug("probable buffer overflow: %ld for %ld", len, capa);
1894 }
1895 ARY_SET_LEN(ary, len);
1896 }
1897
1898 /*!
1899 * expands or shrinks \a ary to \a len elements.
1900 * expanded region will be filled with Qnil.
1901 * \param ary an array
1902 * \param len new size
1903 * \return \a ary
1904 * \post the size of \a ary is \a len.
1905 */
1906 VALUE
rb_ary_resize(VALUE ary,long len)1907 rb_ary_resize(VALUE ary, long len)
1908 {
1909 long olen;
1910
1911 rb_ary_modify(ary);
1912 olen = RARRAY_LEN(ary);
1913 if (len == olen) return ary;
1914 if (len > ARY_MAX_SIZE) {
1915 rb_raise(rb_eIndexError, "index %ld too big", len);
1916 }
1917 if (len > olen) {
1918 if (len >= ARY_CAPA(ary)) {
1919 ary_double_capa(ary, len);
1920 }
1921 ary_mem_clear(ary, olen, len - olen);
1922 ARY_SET_LEN(ary, len);
1923 }
1924 else if (ARY_EMBED_P(ary)) {
1925 ARY_SET_EMBED_LEN(ary, len);
1926 }
1927 else if (len <= RARRAY_EMBED_LEN_MAX) {
1928 VALUE tmp[RARRAY_EMBED_LEN_MAX];
1929 MEMCPY(tmp, ARY_HEAP_PTR(ary), VALUE, len);
1930 ary_discard(ary);
1931 MEMCPY((VALUE *)ARY_EMBED_PTR(ary), tmp, VALUE, len); /* WB: no new reference */
1932 ARY_SET_EMBED_LEN(ary, len);
1933 }
1934 else {
1935 if (olen > len + ARY_DEFAULT_SIZE) {
1936 ary_heap_realloc(ary, len);
1937 ARY_SET_CAPA(ary, len);
1938 }
1939 ARY_SET_HEAP_LEN(ary, len);
1940 }
1941 ary_verify(ary);
1942 return ary;
1943 }
1944
1945 /*
1946 * call-seq:
1947 * ary[index] = obj -> obj
1948 * ary[start, length] = obj or other_ary or nil -> obj or other_ary or nil
1949 * ary[range] = obj or other_ary or nil -> obj or other_ary or nil
1950 *
1951 * Element Assignment --- Sets the element at +index+, or replaces a subarray
1952 * from the +start+ index for +length+ elements, or replaces a subarray
1953 * specified by the +range+ of indices.
1954 *
1955 * If indices are greater than the current capacity of the array, the array
1956 * grows automatically. Elements are inserted into the array at +start+ if
1957 * +length+ is zero.
1958 *
1959 * Negative indices will count backward from the end of the array. For
1960 * +start+ and +range+ cases the starting index is just before an element.
1961 *
1962 * An IndexError is raised if a negative index points past the beginning of
1963 * the array.
1964 *
1965 * See also Array#push, and Array#unshift.
1966 *
1967 * a = Array.new
1968 * a[4] = "4"; #=> [nil, nil, nil, nil, "4"]
1969 * a[0, 3] = [ 'a', 'b', 'c' ] #=> ["a", "b", "c", nil, "4"]
1970 * a[1..2] = [ 1, 2 ] #=> ["a", 1, 2, nil, "4"]
1971 * a[0, 2] = "?" #=> ["?", 2, nil, "4"]
1972 * a[0..2] = "A" #=> ["A", "4"]
1973 * a[-1] = "Z" #=> ["A", "Z"]
1974 * a[1..-1] = nil #=> ["A", nil]
1975 * a[1..-1] = [] #=> ["A"]
1976 * a[0, 0] = [ 1, 2 ] #=> [1, 2, "A"]
1977 * a[3, 0] = "B" #=> [1, 2, "A", "B"]
1978 */
1979
1980 static VALUE
rb_ary_aset(int argc,VALUE * argv,VALUE ary)1981 rb_ary_aset(int argc, VALUE *argv, VALUE ary)
1982 {
1983 long offset, beg, len;
1984 VALUE rpl;
1985
1986 if (argc == 3) {
1987 rb_ary_modify_check(ary);
1988 beg = NUM2LONG(argv[0]);
1989 len = NUM2LONG(argv[1]);
1990 goto range;
1991 }
1992 rb_check_arity(argc, 2, 2);
1993 rb_ary_modify_check(ary);
1994 if (FIXNUM_P(argv[0])) {
1995 offset = FIX2LONG(argv[0]);
1996 goto fixnum;
1997 }
1998 if (rb_range_beg_len(argv[0], &beg, &len, RARRAY_LEN(ary), 1)) {
1999 /* check if idx is Range */
2000 range:
2001 rpl = rb_ary_to_ary(argv[argc-1]);
2002 rb_ary_splice(ary, beg, len, RARRAY_CONST_PTR_TRANSIENT(rpl), RARRAY_LEN(rpl));
2003 RB_GC_GUARD(rpl);
2004 return argv[argc-1];
2005 }
2006
2007 offset = NUM2LONG(argv[0]);
2008 fixnum:
2009 rb_ary_store(ary, offset, argv[1]);
2010 return argv[1];
2011 }
2012
2013 /*
2014 * call-seq:
2015 * ary.insert(index, obj...) -> ary
2016 *
2017 * Inserts the given values before the element with the given +index+.
2018 *
2019 * Negative indices count backwards from the end of the array, where +-1+ is
2020 * the last element. If a negative index is used, the given values will be
2021 * inserted after that element, so using an index of +-1+ will insert the
2022 * values at the end of the array.
2023 *
2024 * a = %w{ a b c d }
2025 * a.insert(2, 99) #=> ["a", "b", 99, "c", "d"]
2026 * a.insert(-2, 1, 2, 3) #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
2027 */
2028
2029 static VALUE
rb_ary_insert(int argc,VALUE * argv,VALUE ary)2030 rb_ary_insert(int argc, VALUE *argv, VALUE ary)
2031 {
2032 long pos;
2033
2034 rb_check_arity(argc, 1, UNLIMITED_ARGUMENTS);
2035 rb_ary_modify_check(ary);
2036 pos = NUM2LONG(argv[0]);
2037 if (argc == 1) return ary;
2038 if (pos == -1) {
2039 pos = RARRAY_LEN(ary);
2040 }
2041 else if (pos < 0) {
2042 long minpos = -RARRAY_LEN(ary) - 1;
2043 if (pos < minpos) {
2044 rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
2045 pos, minpos);
2046 }
2047 pos++;
2048 }
2049 rb_ary_splice(ary, pos, 0, argv + 1, argc - 1);
2050 return ary;
2051 }
2052
2053 static VALUE
2054 rb_ary_length(VALUE ary);
2055
2056 static VALUE
ary_enum_length(VALUE ary,VALUE args,VALUE eobj)2057 ary_enum_length(VALUE ary, VALUE args, VALUE eobj)
2058 {
2059 return rb_ary_length(ary);
2060 }
2061
2062 /*
2063 * call-seq:
2064 * ary.each {|item| block} -> ary
2065 * ary.each -> Enumerator
2066 *
2067 * Calls the given block once for each element in +self+, passing that element
2068 * as a parameter. Returns the array itself.
2069 *
2070 * If no block is given, an Enumerator is returned.
2071 *
2072 * a = [ "a", "b", "c" ]
2073 * a.each {|x| print x, " -- " }
2074 *
2075 * produces:
2076 *
2077 * a -- b -- c --
2078 */
2079
2080 VALUE
rb_ary_each(VALUE ary)2081 rb_ary_each(VALUE ary)
2082 {
2083 long i;
2084 ary_verify(ary);
2085 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2086 for (i=0; i<RARRAY_LEN(ary); i++) {
2087 rb_yield(RARRAY_AREF(ary, i));
2088 }
2089 return ary;
2090 }
2091
2092 /*
2093 * call-seq:
2094 * ary.each_index {|index| block} -> ary
2095 * ary.each_index -> Enumerator
2096 *
2097 * Same as Array#each, but passes the +index+ of the element instead of the
2098 * element itself.
2099 *
2100 * An Enumerator is returned if no block is given.
2101 *
2102 * a = [ "a", "b", "c" ]
2103 * a.each_index {|x| print x, " -- " }
2104 *
2105 * produces:
2106 *
2107 * 0 -- 1 -- 2 --
2108 */
2109
2110 static VALUE
rb_ary_each_index(VALUE ary)2111 rb_ary_each_index(VALUE ary)
2112 {
2113 long i;
2114 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2115
2116 for (i=0; i<RARRAY_LEN(ary); i++) {
2117 rb_yield(LONG2NUM(i));
2118 }
2119 return ary;
2120 }
2121
2122 /*
2123 * call-seq:
2124 * ary.reverse_each {|item| block} -> ary
2125 * ary.reverse_each -> Enumerator
2126 *
2127 * Same as Array#each, but traverses +self+ in reverse order.
2128 *
2129 * a = [ "a", "b", "c" ]
2130 * a.reverse_each {|x| print x, " " }
2131 *
2132 * produces:
2133 *
2134 * c b a
2135 */
2136
2137 static VALUE
rb_ary_reverse_each(VALUE ary)2138 rb_ary_reverse_each(VALUE ary)
2139 {
2140 long len;
2141
2142 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2143 len = RARRAY_LEN(ary);
2144 while (len--) {
2145 long nlen;
2146 rb_yield(RARRAY_AREF(ary, len));
2147 nlen = RARRAY_LEN(ary);
2148 if (nlen < len) {
2149 len = nlen;
2150 }
2151 }
2152 return ary;
2153 }
2154
2155 /*
2156 * call-seq:
2157 * ary.length -> int
2158 *
2159 * Returns the number of elements in +self+. May be zero.
2160 *
2161 * [ 1, 2, 3, 4, 5 ].length #=> 5
2162 * [].length #=> 0
2163 */
2164
2165 static VALUE
rb_ary_length(VALUE ary)2166 rb_ary_length(VALUE ary)
2167 {
2168 long len = RARRAY_LEN(ary);
2169 return LONG2NUM(len);
2170 }
2171
2172 /*
2173 * call-seq:
2174 * ary.empty? -> true or false
2175 *
2176 * Returns +true+ if +self+ contains no elements.
2177 *
2178 * [].empty? #=> true
2179 */
2180
2181 static VALUE
rb_ary_empty_p(VALUE ary)2182 rb_ary_empty_p(VALUE ary)
2183 {
2184 if (RARRAY_LEN(ary) == 0)
2185 return Qtrue;
2186 return Qfalse;
2187 }
2188
2189 VALUE
rb_ary_dup(VALUE ary)2190 rb_ary_dup(VALUE ary)
2191 {
2192 long len = RARRAY_LEN(ary);
2193 VALUE dup = rb_ary_new2(len);
2194 ary_memcpy(dup, 0, len, RARRAY_CONST_PTR_TRANSIENT(ary));
2195 ARY_SET_LEN(dup, len);
2196
2197 ary_verify(ary);
2198 ary_verify(dup);
2199 return dup;
2200 }
2201
2202 VALUE
rb_ary_resurrect(VALUE ary)2203 rb_ary_resurrect(VALUE ary)
2204 {
2205 return ary_make_partial(ary, rb_cArray, 0, RARRAY_LEN(ary));
2206 }
2207
2208 extern VALUE rb_output_fs;
2209
2210 static void ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first);
2211
2212 static VALUE
recursive_join(VALUE obj,VALUE argp,int recur)2213 recursive_join(VALUE obj, VALUE argp, int recur)
2214 {
2215 VALUE *arg = (VALUE *)argp;
2216 VALUE ary = arg[0];
2217 VALUE sep = arg[1];
2218 VALUE result = arg[2];
2219 int *first = (int *)arg[3];
2220
2221 if (recur) {
2222 rb_raise(rb_eArgError, "recursive array join");
2223 }
2224 else {
2225 ary_join_1(obj, ary, sep, 0, result, first);
2226 }
2227 return Qnil;
2228 }
2229
2230 static void
ary_join_0(VALUE ary,VALUE sep,long max,VALUE result)2231 ary_join_0(VALUE ary, VALUE sep, long max, VALUE result)
2232 {
2233 long i;
2234 VALUE val;
2235
2236 if (max > 0) rb_enc_copy(result, RARRAY_AREF(ary, 0));
2237 for (i=0; i<max; i++) {
2238 val = RARRAY_AREF(ary, i);
2239 if (i > 0 && !NIL_P(sep))
2240 rb_str_buf_append(result, sep);
2241 rb_str_buf_append(result, val);
2242 if (OBJ_TAINTED(val)) OBJ_TAINT(result);
2243 }
2244 }
2245
2246 static void
ary_join_1(VALUE obj,VALUE ary,VALUE sep,long i,VALUE result,int * first)2247 ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first)
2248 {
2249 VALUE val, tmp;
2250
2251 for (; i<RARRAY_LEN(ary); i++) {
2252 if (i > 0 && !NIL_P(sep))
2253 rb_str_buf_append(result, sep);
2254
2255 val = RARRAY_AREF(ary, i);
2256 if (RB_TYPE_P(val, T_STRING)) {
2257 str_join:
2258 rb_str_buf_append(result, val);
2259 if (*first) {
2260 rb_enc_copy(result, val);
2261 *first = FALSE;
2262 }
2263 }
2264 else if (RB_TYPE_P(val, T_ARRAY)) {
2265 obj = val;
2266 ary_join:
2267 if (val == ary) {
2268 rb_raise(rb_eArgError, "recursive array join");
2269 }
2270 else {
2271 VALUE args[4];
2272
2273 *first = FALSE;
2274 args[0] = val;
2275 args[1] = sep;
2276 args[2] = result;
2277 args[3] = (VALUE)first;
2278 rb_exec_recursive(recursive_join, obj, (VALUE)args);
2279 }
2280 }
2281 else {
2282 tmp = rb_check_string_type(val);
2283 if (!NIL_P(tmp)) {
2284 val = tmp;
2285 goto str_join;
2286 }
2287 tmp = rb_check_array_type(val);
2288 if (!NIL_P(tmp)) {
2289 obj = val;
2290 val = tmp;
2291 goto ary_join;
2292 }
2293 val = rb_obj_as_string(val);
2294 goto str_join;
2295 }
2296 }
2297 }
2298
2299 VALUE
rb_ary_join(VALUE ary,VALUE sep)2300 rb_ary_join(VALUE ary, VALUE sep)
2301 {
2302 long len = 1, i;
2303 int taint = FALSE;
2304 VALUE val, tmp, result;
2305
2306 if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new(0, 0);
2307 if (OBJ_TAINTED(ary)) taint = TRUE;
2308
2309 if (!NIL_P(sep)) {
2310 StringValue(sep);
2311 len += RSTRING_LEN(sep) * (RARRAY_LEN(ary) - 1);
2312 }
2313 for (i=0; i<RARRAY_LEN(ary); i++) {
2314 val = RARRAY_AREF(ary, i);
2315 tmp = rb_check_string_type(val);
2316
2317 if (NIL_P(tmp) || tmp != val) {
2318 int first;
2319 result = rb_str_buf_new(len + (RARRAY_LEN(ary)-i)*10);
2320 rb_enc_associate(result, rb_usascii_encoding());
2321 if (taint) OBJ_TAINT(result);
2322 ary_join_0(ary, sep, i, result);
2323 first = i == 0;
2324 ary_join_1(ary, ary, sep, i, result, &first);
2325 return result;
2326 }
2327
2328 len += RSTRING_LEN(tmp);
2329 }
2330
2331 result = rb_str_buf_new(len);
2332 if (taint) OBJ_TAINT(result);
2333 ary_join_0(ary, sep, RARRAY_LEN(ary), result);
2334
2335 return result;
2336 }
2337
2338 /*
2339 * call-seq:
2340 * ary.join(separator=$,) -> str
2341 *
2342 * Returns a string created by converting each element of the array to
2343 * a string, separated by the given +separator+.
2344 * If the +separator+ is +nil+, it uses current <code>$,</code>.
2345 * If both the +separator+ and <code>$,</code> are +nil+,
2346 * it uses an empty string.
2347 *
2348 * [ "a", "b", "c" ].join #=> "abc"
2349 * [ "a", "b", "c" ].join("-") #=> "a-b-c"
2350 *
2351 * For nested arrays, join is applied recursively:
2352 *
2353 * [ "a", [1, 2, [:x, :y]], "b" ].join("-") #=> "a-1-2-x-y-b"
2354 */
2355
2356 static VALUE
rb_ary_join_m(int argc,VALUE * argv,VALUE ary)2357 rb_ary_join_m(int argc, VALUE *argv, VALUE ary)
2358 {
2359 VALUE sep;
2360
2361 if (rb_check_arity(argc, 0, 1) == 0) {
2362 sep = rb_output_fs;
2363 }
2364 else if (NIL_P(sep = argv[0])) {
2365 sep = rb_output_fs;
2366 }
2367
2368 return rb_ary_join(ary, sep);
2369 }
2370
2371 static VALUE
inspect_ary(VALUE ary,VALUE dummy,int recur)2372 inspect_ary(VALUE ary, VALUE dummy, int recur)
2373 {
2374 int tainted = OBJ_TAINTED(ary);
2375 long i;
2376 VALUE s, str;
2377
2378 if (recur) return rb_usascii_str_new_cstr("[...]");
2379 str = rb_str_buf_new2("[");
2380 for (i=0; i<RARRAY_LEN(ary); i++) {
2381 s = rb_inspect(RARRAY_AREF(ary, i));
2382 if (OBJ_TAINTED(s)) tainted = TRUE;
2383 if (i > 0) rb_str_buf_cat2(str, ", ");
2384 else rb_enc_copy(str, s);
2385 rb_str_buf_append(str, s);
2386 }
2387 rb_str_buf_cat2(str, "]");
2388 if (tainted) OBJ_TAINT(str);
2389 return str;
2390 }
2391
2392 /*
2393 * call-seq:
2394 * ary.inspect -> string
2395 * ary.to_s -> string
2396 *
2397 * Creates a string representation of +self+.
2398 *
2399 * [ "a", "b", "c" ].to_s #=> "[\"a\", \"b\", \"c\"]"
2400 */
2401
2402 static VALUE
rb_ary_inspect(VALUE ary)2403 rb_ary_inspect(VALUE ary)
2404 {
2405 if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new2("[]");
2406 return rb_exec_recursive(inspect_ary, ary, 0);
2407 }
2408
2409 VALUE
rb_ary_to_s(VALUE ary)2410 rb_ary_to_s(VALUE ary)
2411 {
2412 return rb_ary_inspect(ary);
2413 }
2414
2415 /*
2416 * call-seq:
2417 * ary.to_a -> ary
2418 *
2419 * Returns +self+.
2420 *
2421 * If called on a subclass of Array, converts the receiver to an Array object.
2422 */
2423
2424 static VALUE
rb_ary_to_a(VALUE ary)2425 rb_ary_to_a(VALUE ary)
2426 {
2427 if (rb_obj_class(ary) != rb_cArray) {
2428 VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
2429 rb_ary_replace(dup, ary);
2430 return dup;
2431 }
2432 return ary;
2433 }
2434
2435 /*
2436 * call-seq:
2437 * ary.to_h -> hash
2438 * ary.to_h { block } -> hash
2439 *
2440 * Returns the result of interpreting <i>ary</i> as an array of
2441 * <tt>[key, value]</tt> pairs.
2442 *
2443 * [[:foo, :bar], [1, 2]].to_h
2444 * # => {:foo => :bar, 1 => 2}
2445 *
2446 * If a block is given, the results of the block on each element of
2447 * the array will be used as pairs.
2448 *
2449 * ["foo", "bar"].to_h {|s| [s.ord, s]}
2450 * # => {102=>"foo", 98=>"bar"}
2451 */
2452
2453 static VALUE
rb_ary_to_h(VALUE ary)2454 rb_ary_to_h(VALUE ary)
2455 {
2456 long i;
2457 VALUE hash = rb_hash_new_with_size(RARRAY_LEN(ary));
2458 int block_given = rb_block_given_p();
2459
2460 for (i=0; i<RARRAY_LEN(ary); i++) {
2461 const VALUE e = rb_ary_elt(ary, i);
2462 const VALUE elt = block_given ? rb_yield_force_blockarg(e) : e;
2463 const VALUE key_value_pair = rb_check_array_type(elt);
2464 if (NIL_P(key_value_pair)) {
2465 rb_raise(rb_eTypeError, "wrong element type %"PRIsVALUE" at %ld (expected array)",
2466 rb_obj_class(elt), i);
2467 }
2468 if (RARRAY_LEN(key_value_pair) != 2) {
2469 rb_raise(rb_eArgError, "wrong array length at %ld (expected 2, was %ld)",
2470 i, RARRAY_LEN(key_value_pair));
2471 }
2472 rb_hash_aset(hash, RARRAY_AREF(key_value_pair, 0), RARRAY_AREF(key_value_pair, 1));
2473 }
2474 return hash;
2475 }
2476
2477 /*
2478 * call-seq:
2479 * ary.to_ary -> ary
2480 *
2481 * Returns +self+.
2482 */
2483
2484 static VALUE
rb_ary_to_ary_m(VALUE ary)2485 rb_ary_to_ary_m(VALUE ary)
2486 {
2487 return ary;
2488 }
2489
2490 static void
ary_reverse(VALUE * p1,VALUE * p2)2491 ary_reverse(VALUE *p1, VALUE *p2)
2492 {
2493 while (p1 < p2) {
2494 VALUE tmp = *p1;
2495 *p1++ = *p2;
2496 *p2-- = tmp;
2497 }
2498 }
2499
2500 VALUE
rb_ary_reverse(VALUE ary)2501 rb_ary_reverse(VALUE ary)
2502 {
2503 VALUE *p2;
2504 long len = RARRAY_LEN(ary);
2505
2506 rb_ary_modify(ary);
2507 if (len > 1) {
2508 RARRAY_PTR_USE_TRANSIENT(ary, p1, {
2509 p2 = p1 + len - 1; /* points last item */
2510 ary_reverse(p1, p2);
2511 }); /* WB: no new reference */
2512 }
2513 return ary;
2514 }
2515
2516 /*
2517 * call-seq:
2518 * ary.reverse! -> ary
2519 *
2520 * Reverses +self+ in place.
2521 *
2522 * a = [ "a", "b", "c" ]
2523 * a.reverse! #=> ["c", "b", "a"]
2524 * a #=> ["c", "b", "a"]
2525 */
2526
2527 static VALUE
rb_ary_reverse_bang(VALUE ary)2528 rb_ary_reverse_bang(VALUE ary)
2529 {
2530 return rb_ary_reverse(ary);
2531 }
2532
2533 /*
2534 * call-seq:
2535 * ary.reverse -> new_ary
2536 *
2537 * Returns a new array containing +self+'s elements in reverse order.
2538 *
2539 * [ "a", "b", "c" ].reverse #=> ["c", "b", "a"]
2540 * [ 1 ].reverse #=> [1]
2541 */
2542
2543 static VALUE
rb_ary_reverse_m(VALUE ary)2544 rb_ary_reverse_m(VALUE ary)
2545 {
2546 long len = RARRAY_LEN(ary);
2547 VALUE dup = rb_ary_new2(len);
2548
2549 if (len > 0) {
2550 const VALUE *p1 = RARRAY_CONST_PTR_TRANSIENT(ary);
2551 VALUE *p2 = (VALUE *)RARRAY_CONST_PTR_TRANSIENT(dup) + len - 1;
2552 do *p2-- = *p1++; while (--len > 0);
2553 }
2554 ARY_SET_LEN(dup, RARRAY_LEN(ary));
2555 return dup;
2556 }
2557
2558 static inline long
rotate_count(long cnt,long len)2559 rotate_count(long cnt, long len)
2560 {
2561 return (cnt < 0) ? (len - (~cnt % len) - 1) : (cnt % len);
2562 }
2563
2564 static void
ary_rotate_ptr(VALUE * ptr,long len,long cnt)2565 ary_rotate_ptr(VALUE *ptr, long len, long cnt)
2566 {
2567 --len;
2568 if (cnt < len) ary_reverse(ptr + cnt, ptr + len);
2569 if (--cnt > 0) ary_reverse(ptr, ptr + cnt);
2570 if (len > 0) ary_reverse(ptr, ptr + len);
2571 }
2572
2573 VALUE
rb_ary_rotate(VALUE ary,long cnt)2574 rb_ary_rotate(VALUE ary, long cnt)
2575 {
2576 rb_ary_modify(ary);
2577
2578 if (cnt != 0) {
2579 long len = RARRAY_LEN(ary);
2580 if (len > 0 && (cnt = rotate_count(cnt, len)) > 0) {
2581 RARRAY_PTR_USE_TRANSIENT(ary, ptr, ary_rotate_ptr(ptr, len, cnt));
2582 return ary;
2583 }
2584 }
2585 return Qnil;
2586 }
2587
2588 /*
2589 * call-seq:
2590 * ary.rotate!(count=1) -> ary
2591 *
2592 * Rotates +self+ in place so that the element at +count+ comes first, and
2593 * returns +self+.
2594 *
2595 * If +count+ is negative then it rotates in the opposite direction, starting
2596 * from the end of the array where +-1+ is the last element.
2597 *
2598 * a = [ "a", "b", "c", "d" ]
2599 * a.rotate! #=> ["b", "c", "d", "a"]
2600 * a #=> ["b", "c", "d", "a"]
2601 * a.rotate!(2) #=> ["d", "a", "b", "c"]
2602 * a.rotate!(-3) #=> ["a", "b", "c", "d"]
2603 */
2604
2605 static VALUE
rb_ary_rotate_bang(int argc,VALUE * argv,VALUE ary)2606 rb_ary_rotate_bang(int argc, VALUE *argv, VALUE ary)
2607 {
2608 long n = (rb_check_arity(argc, 0, 1) ? NUM2LONG(argv[0]) : 1);
2609 rb_ary_rotate(ary, n);
2610 return ary;
2611 }
2612
2613 /*
2614 * call-seq:
2615 * ary.rotate(count=1) -> new_ary
2616 *
2617 * Returns a new array by rotating +self+ so that the element at +count+ is
2618 * the first element of the new array.
2619 *
2620 * If +count+ is negative then it rotates in the opposite direction, starting
2621 * from the end of +self+ where +-1+ is the last element.
2622 *
2623 * a = [ "a", "b", "c", "d" ]
2624 * a.rotate #=> ["b", "c", "d", "a"]
2625 * a #=> ["a", "b", "c", "d"]
2626 * a.rotate(2) #=> ["c", "d", "a", "b"]
2627 * a.rotate(-3) #=> ["b", "c", "d", "a"]
2628 */
2629
2630 static VALUE
rb_ary_rotate_m(int argc,VALUE * argv,VALUE ary)2631 rb_ary_rotate_m(int argc, VALUE *argv, VALUE ary)
2632 {
2633 VALUE rotated;
2634 const VALUE *ptr;
2635 long len;
2636 long cnt = (rb_check_arity(argc, 0, 1) ? NUM2LONG(argv[0]) : 1);
2637
2638 len = RARRAY_LEN(ary);
2639 rotated = rb_ary_new2(len);
2640 if (len > 0) {
2641 cnt = rotate_count(cnt, len);
2642 ptr = RARRAY_CONST_PTR_TRANSIENT(ary);
2643 len -= cnt;
2644 ary_memcpy(rotated, 0, len, ptr + cnt);
2645 ary_memcpy(rotated, len, cnt, ptr);
2646 }
2647 ARY_SET_LEN(rotated, RARRAY_LEN(ary));
2648 return rotated;
2649 }
2650
2651 struct ary_sort_data {
2652 VALUE ary;
2653 struct cmp_opt_data cmp_opt;
2654 };
2655
2656 static VALUE
sort_reentered(VALUE ary)2657 sort_reentered(VALUE ary)
2658 {
2659 if (RBASIC(ary)->klass) {
2660 rb_raise(rb_eRuntimeError, "sort reentered");
2661 }
2662 return Qnil;
2663 }
2664
2665 static int
sort_1(const void * ap,const void * bp,void * dummy)2666 sort_1(const void *ap, const void *bp, void *dummy)
2667 {
2668 struct ary_sort_data *data = dummy;
2669 VALUE retval = sort_reentered(data->ary);
2670 VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2671 VALUE args[2];
2672 int n;
2673
2674 args[0] = a;
2675 args[1] = b;
2676 retval = rb_yield_values2(2, args);
2677 n = rb_cmpint(retval, a, b);
2678 sort_reentered(data->ary);
2679 return n;
2680 }
2681
2682 static int
sort_2(const void * ap,const void * bp,void * dummy)2683 sort_2(const void *ap, const void *bp, void *dummy)
2684 {
2685 struct ary_sort_data *data = dummy;
2686 VALUE retval = sort_reentered(data->ary);
2687 VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2688 int n;
2689
2690 if (FIXNUM_P(a) && FIXNUM_P(b) && CMP_OPTIMIZABLE(data->cmp_opt, Fixnum)) {
2691 if ((long)a > (long)b) return 1;
2692 if ((long)a < (long)b) return -1;
2693 return 0;
2694 }
2695 if (STRING_P(a) && STRING_P(b) && CMP_OPTIMIZABLE(data->cmp_opt, String)) {
2696 return rb_str_cmp(a, b);
2697 }
2698 if (RB_FLOAT_TYPE_P(a) && CMP_OPTIMIZABLE(data->cmp_opt, Float)) {
2699 return rb_float_cmp(a, b);
2700 }
2701
2702 retval = rb_funcallv(a, id_cmp, 1, &b);
2703 n = rb_cmpint(retval, a, b);
2704 sort_reentered(data->ary);
2705
2706 return n;
2707 }
2708
2709 /*
2710 * call-seq:
2711 * ary.sort! -> ary
2712 * ary.sort! {|a, b| block} -> ary
2713 *
2714 * Sorts +self+ in place.
2715 *
2716 * Comparisons for the sort will be done using the <code><=></code> operator
2717 * or using an optional code block.
2718 *
2719 * The block must implement a comparison between +a+ and +b+ and return
2720 * an integer less than 0 when +b+ follows +a+, +0+ when +a+ and +b+
2721 * are equivalent, or an integer greater than 0 when +a+ follows +b+.
2722 *
2723 * The result is not guaranteed to be stable. When the comparison of two
2724 * elements returns +0+, the order of the elements is unpredictable.
2725 *
2726 * ary = [ "d", "a", "e", "c", "b" ]
2727 * ary.sort! #=> ["a", "b", "c", "d", "e"]
2728 * ary.sort! {|a, b| b <=> a} #=> ["e", "d", "c", "b", "a"]
2729 *
2730 * See also Enumerable#sort_by.
2731 */
2732
2733 VALUE
rb_ary_sort_bang(VALUE ary)2734 rb_ary_sort_bang(VALUE ary)
2735 {
2736 rb_ary_modify(ary);
2737 assert(!ARY_SHARED_P(ary));
2738 if (RARRAY_LEN(ary) > 1) {
2739 VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
2740 struct ary_sort_data data;
2741 long len = RARRAY_LEN(ary);
2742 RBASIC_CLEAR_CLASS(tmp);
2743 data.ary = tmp;
2744 data.cmp_opt.opt_methods = 0;
2745 data.cmp_opt.opt_inited = 0;
2746 RARRAY_PTR_USE(tmp, ptr, {
2747 ruby_qsort(ptr, len, sizeof(VALUE),
2748 rb_block_given_p()?sort_1:sort_2, &data);
2749 }); /* WB: no new reference */
2750 rb_ary_modify(ary);
2751 if (ARY_EMBED_P(tmp)) {
2752 if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */
2753 rb_ary_unshare(ary);
2754 FL_SET_EMBED(ary);
2755 }
2756 ary_memcpy(ary, 0, ARY_EMBED_LEN(tmp), ARY_EMBED_PTR(tmp));
2757 ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
2758 }
2759 else {
2760 if (!ARY_EMBED_P(ary) && ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
2761 FL_UNSET_SHARED(ary);
2762 ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2763 }
2764 else {
2765 assert(!ARY_SHARED_P(tmp));
2766 if (ARY_EMBED_P(ary)) {
2767 FL_UNSET_EMBED(ary);
2768 }
2769 else if (ARY_SHARED_P(ary)) {
2770 /* ary might be destructively operated in the given block */
2771 rb_ary_unshare(ary);
2772 }
2773 else {
2774 ary_heap_free(ary);
2775 }
2776 ARY_SET_PTR(ary, ARY_HEAP_PTR(tmp));
2777 ARY_SET_HEAP_LEN(ary, len);
2778 ARY_SET_CAPA(ary, ARY_HEAP_LEN(tmp));
2779 }
2780 /* tmp was lost ownership for the ptr */
2781 FL_UNSET(tmp, FL_FREEZE);
2782 FL_SET_EMBED(tmp);
2783 ARY_SET_EMBED_LEN(tmp, 0);
2784 FL_SET(tmp, FL_FREEZE);
2785 }
2786 /* tmp will be GC'ed. */
2787 RBASIC_SET_CLASS_RAW(tmp, rb_cArray); /* rb_cArray must be marked */
2788 }
2789 ary_verify(ary);
2790 return ary;
2791 }
2792
2793 /*
2794 * call-seq:
2795 * ary.sort -> new_ary
2796 * ary.sort {|a, b| block} -> new_ary
2797 *
2798 * Returns a new array created by sorting +self+.
2799 *
2800 * Comparisons for the sort will be done using the <code><=></code> operator
2801 * or using an optional code block.
2802 *
2803 * The block must implement a comparison between +a+ and +b+ and return
2804 * an integer less than 0 when +b+ follows +a+, +0+ when +a+ and +b+
2805 * are equivalent, or an integer greater than 0 when +a+ follows +b+.
2806 *
2807 * The result is not guaranteed to be stable. When the comparison of two
2808 * elements returns +0+, the order of the elements is unpredictable.
2809 *
2810 * ary = [ "d", "a", "e", "c", "b" ]
2811 * ary.sort #=> ["a", "b", "c", "d", "e"]
2812 * ary.sort {|a, b| b <=> a} #=> ["e", "d", "c", "b", "a"]
2813 *
2814 * See also Enumerable#sort_by.
2815 */
2816
2817 VALUE
rb_ary_sort(VALUE ary)2818 rb_ary_sort(VALUE ary)
2819 {
2820 ary = rb_ary_dup(ary);
2821 rb_ary_sort_bang(ary);
2822 return ary;
2823 }
2824
2825 static VALUE rb_ary_bsearch_index(VALUE ary);
2826
2827 /*
2828 * call-seq:
2829 * ary.bsearch {|x| block } -> elem
2830 *
2831 * By using binary search, finds a value from this array which meets
2832 * the given condition in O(log n) where n is the size of the array.
2833 *
2834 * You can use this method in two modes: a find-minimum mode and
2835 * a find-any mode. In either case, the elements of the array must be
2836 * monotone (or sorted) with respect to the block.
2837 *
2838 * In find-minimum mode (this is a good choice for typical use cases),
2839 * the block must always return true or false, and there must be an index i
2840 * (0 <= i <= ary.size) so that:
2841 *
2842 * - the block returns false for any element whose index is less than
2843 * i, and
2844 * - the block returns true for any element whose index is greater
2845 * than or equal to i.
2846 *
2847 * This method returns the i-th element. If i is equal to ary.size,
2848 * it returns nil.
2849 *
2850 * ary = [0, 4, 7, 10, 12]
2851 * ary.bsearch {|x| x >= 4 } #=> 4
2852 * ary.bsearch {|x| x >= 6 } #=> 7
2853 * ary.bsearch {|x| x >= -1 } #=> 0
2854 * ary.bsearch {|x| x >= 100 } #=> nil
2855 *
2856 * In find-any mode (this behaves like libc's bsearch(3)), the block
2857 * must always return a number, and there must be two indices i and j
2858 * (0 <= i <= j <= ary.size) so that:
2859 *
2860 * - the block returns a positive number for ary[k] if 0 <= k < i,
2861 * - the block returns zero for ary[k] if i <= k < j, and
2862 * - the block returns a negative number for ary[k] if
2863 * j <= k < ary.size.
2864 *
2865 * Under this condition, this method returns any element whose index
2866 * is within i...j. If i is equal to j (i.e., there is no element
2867 * that satisfies the block), this method returns nil.
2868 *
2869 * ary = [0, 4, 7, 10, 12]
2870 * # try to find v such that 4 <= v < 8
2871 * ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7
2872 * # try to find v such that 8 <= v < 10
2873 * ary.bsearch {|x| 4 - x / 2 } #=> nil
2874 *
2875 * You must not mix the two modes at a time; the block must always
2876 * return either true/false, or always return a number. It is
2877 * undefined which value is actually picked up at each iteration.
2878 */
2879
2880 static VALUE
rb_ary_bsearch(VALUE ary)2881 rb_ary_bsearch(VALUE ary)
2882 {
2883 VALUE index_result = rb_ary_bsearch_index(ary);
2884
2885 if (FIXNUM_P(index_result)) {
2886 return rb_ary_entry(ary, FIX2LONG(index_result));
2887 }
2888 return index_result;
2889 }
2890
2891 /*
2892 * call-seq:
2893 * ary.bsearch_index {|x| block } -> int or nil
2894 *
2895 * By using binary search, finds an index of a value from this array which
2896 * meets the given condition in O(log n) where n is the size of the array.
2897 *
2898 * It supports two modes, depending on the nature of the block. They are
2899 * exactly the same as in the case of the #bsearch method, with the only difference
2900 * being that this method returns the index of the element instead of the
2901 * element itself. For more details consult the documentation for #bsearch.
2902 */
2903
2904 static VALUE
rb_ary_bsearch_index(VALUE ary)2905 rb_ary_bsearch_index(VALUE ary)
2906 {
2907 long low = 0, high = RARRAY_LEN(ary), mid;
2908 int smaller = 0, satisfied = 0;
2909 VALUE v, val;
2910
2911 RETURN_ENUMERATOR(ary, 0, 0);
2912 while (low < high) {
2913 mid = low + ((high - low) / 2);
2914 val = rb_ary_entry(ary, mid);
2915 v = rb_yield(val);
2916 if (FIXNUM_P(v)) {
2917 if (v == INT2FIX(0)) return INT2FIX(mid);
2918 smaller = (SIGNED_VALUE)v < 0; /* Fixnum preserves its sign-bit */
2919 }
2920 else if (v == Qtrue) {
2921 satisfied = 1;
2922 smaller = 1;
2923 }
2924 else if (v == Qfalse || v == Qnil) {
2925 smaller = 0;
2926 }
2927 else if (rb_obj_is_kind_of(v, rb_cNumeric)) {
2928 const VALUE zero = INT2FIX(0);
2929 switch (rb_cmpint(rb_funcallv(v, id_cmp, 1, &zero), v, zero)) {
2930 case 0: return INT2FIX(mid);
2931 case 1: smaller = 1; break;
2932 case -1: smaller = 0;
2933 }
2934 }
2935 else {
2936 rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE
2937 " (must be numeric, true, false or nil)",
2938 rb_obj_class(v));
2939 }
2940 if (smaller) {
2941 high = mid;
2942 }
2943 else {
2944 low = mid + 1;
2945 }
2946 }
2947 if (!satisfied) return Qnil;
2948 return INT2FIX(low);
2949 }
2950
2951
2952 static VALUE
sort_by_i(RB_BLOCK_CALL_FUNC_ARGLIST (i,dummy))2953 sort_by_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, dummy))
2954 {
2955 return rb_yield(i);
2956 }
2957
2958 /*
2959 * call-seq:
2960 * ary.sort_by! {|obj| block} -> ary
2961 * ary.sort_by! -> Enumerator
2962 *
2963 * Sorts +self+ in place using a set of keys generated by mapping the
2964 * values in +self+ through the given block.
2965 *
2966 * The result is not guaranteed to be stable. When two keys are equal,
2967 * the order of the corresponding elements is unpredictable.
2968 *
2969 * If no block is given, an Enumerator is returned instead.
2970 *
2971 * See also Enumerable#sort_by.
2972 */
2973
2974 static VALUE
rb_ary_sort_by_bang(VALUE ary)2975 rb_ary_sort_by_bang(VALUE ary)
2976 {
2977 VALUE sorted;
2978
2979 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2980 rb_ary_modify(ary);
2981 sorted = rb_block_call(ary, rb_intern("sort_by"), 0, 0, sort_by_i, 0);
2982 rb_ary_replace(ary, sorted);
2983 return ary;
2984 }
2985
2986
2987 /*
2988 * call-seq:
2989 * ary.collect {|item| block} -> new_ary
2990 * ary.map {|item| block} -> new_ary
2991 * ary.collect -> Enumerator
2992 * ary.map -> Enumerator
2993 *
2994 * Invokes the given block once for each element of +self+.
2995 *
2996 * Creates a new array containing the values returned by the block.
2997 *
2998 * See also Enumerable#collect.
2999 *
3000 * If no block is given, an Enumerator is returned instead.
3001 *
3002 * a = [ "a", "b", "c", "d" ]
3003 * a.collect {|x| x + "!"} #=> ["a!", "b!", "c!", "d!"]
3004 * a.map.with_index {|x, i| x * i} #=> ["", "b", "cc", "ddd"]
3005 * a #=> ["a", "b", "c", "d"]
3006 */
3007
3008 static VALUE
rb_ary_collect(VALUE ary)3009 rb_ary_collect(VALUE ary)
3010 {
3011 long i;
3012 VALUE collect;
3013
3014 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3015 collect = rb_ary_new2(RARRAY_LEN(ary));
3016 for (i = 0; i < RARRAY_LEN(ary); i++) {
3017 rb_ary_push(collect, rb_yield(RARRAY_AREF(ary, i)));
3018 }
3019 return collect;
3020 }
3021
3022
3023 /*
3024 * call-seq:
3025 * ary.collect! {|item| block } -> ary
3026 * ary.map! {|item| block } -> ary
3027 * ary.collect! -> Enumerator
3028 * ary.map! -> Enumerator
3029 *
3030 * Invokes the given block once for each element of +self+, replacing the
3031 * element with the value returned by the block.
3032 *
3033 * See also Enumerable#collect.
3034 *
3035 * If no block is given, an Enumerator is returned instead.
3036 *
3037 * a = [ "a", "b", "c", "d" ]
3038 * a.map! {|x| x + "!" }
3039 * a #=> [ "a!", "b!", "c!", "d!" ]
3040 * a.collect!.with_index {|x, i| x[0...i] }
3041 * a #=> ["", "b", "c!", "d!"]
3042 */
3043
3044 static VALUE
rb_ary_collect_bang(VALUE ary)3045 rb_ary_collect_bang(VALUE ary)
3046 {
3047 long i;
3048
3049 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3050 rb_ary_modify(ary);
3051 for (i = 0; i < RARRAY_LEN(ary); i++) {
3052 rb_ary_store(ary, i, rb_yield(RARRAY_AREF(ary, i)));
3053 }
3054 return ary;
3055 }
3056
3057 VALUE
rb_get_values_at(VALUE obj,long olen,int argc,const VALUE * argv,VALUE (* func)(VALUE,long))3058 rb_get_values_at(VALUE obj, long olen, int argc, const VALUE *argv, VALUE (*func) (VALUE, long))
3059 {
3060 VALUE result = rb_ary_new2(argc);
3061 long beg, len, i, j;
3062
3063 for (i=0; i<argc; i++) {
3064 if (FIXNUM_P(argv[i])) {
3065 rb_ary_push(result, (*func)(obj, FIX2LONG(argv[i])));
3066 continue;
3067 }
3068 /* check if idx is Range */
3069 if (rb_range_beg_len(argv[i], &beg, &len, olen, 1)) {
3070 long end = olen < beg+len ? olen : beg+len;
3071 for (j = beg; j < end; j++) {
3072 rb_ary_push(result, (*func)(obj, j));
3073 }
3074 if (beg + len > j)
3075 rb_ary_resize(result, RARRAY_LEN(result) + (beg + len) - j);
3076 continue;
3077 }
3078 rb_ary_push(result, (*func)(obj, NUM2LONG(argv[i])));
3079 }
3080 return result;
3081 }
3082
3083 static VALUE
append_values_at_single(VALUE result,VALUE ary,long olen,VALUE idx)3084 append_values_at_single(VALUE result, VALUE ary, long olen, VALUE idx)
3085 {
3086 long beg, len;
3087 if (FIXNUM_P(idx)) {
3088 beg = FIX2LONG(idx);
3089 }
3090 /* check if idx is Range */
3091 else if (rb_range_beg_len(idx, &beg, &len, olen, 1)) {
3092 if (len > 0) {
3093 const VALUE *const src = RARRAY_CONST_PTR_TRANSIENT(ary);
3094 const long end = beg + len;
3095 const long prevlen = RARRAY_LEN(result);
3096 if (beg < olen) {
3097 rb_ary_cat(result, src + beg, end > olen ? olen-beg : len);
3098 }
3099 if (end > olen) {
3100 rb_ary_store(result, prevlen + len - 1, Qnil);
3101 }
3102 }
3103 return result;
3104 }
3105 else {
3106 beg = NUM2LONG(idx);
3107 }
3108 return rb_ary_push(result, rb_ary_entry(ary, beg));
3109 }
3110
3111 /*
3112 * call-seq:
3113 * ary.values_at(selector, ...) -> new_ary
3114 *
3115 * Returns an array containing the elements in +self+ corresponding to the
3116 * given +selector+(s).
3117 *
3118 * The selectors may be either integer indices or ranges.
3119 *
3120 * See also Array#select.
3121 *
3122 * a = %w{ a b c d e f }
3123 * a.values_at(1, 3, 5) # => ["b", "d", "f"]
3124 * a.values_at(1, 3, 5, 7) # => ["b", "d", "f", nil]
3125 * a.values_at(-1, -2, -2, -7) # => ["f", "e", "e", nil]
3126 * a.values_at(4..6, 3...6) # => ["e", "f", nil, "d", "e", "f"]
3127 */
3128
3129 static VALUE
rb_ary_values_at(int argc,VALUE * argv,VALUE ary)3130 rb_ary_values_at(int argc, VALUE *argv, VALUE ary)
3131 {
3132 long i, olen = RARRAY_LEN(ary);
3133 VALUE result = rb_ary_new_capa(argc);
3134 for (i = 0; i < argc; ++i) {
3135 append_values_at_single(result, ary, olen, argv[i]);
3136 }
3137 RB_GC_GUARD(ary);
3138 return result;
3139 }
3140
3141
3142 /*
3143 * call-seq:
3144 * ary.select {|item| block} -> new_ary
3145 * ary.select -> Enumerator
3146 * ary.filter {|item| block} -> new_ary
3147 * ary.filter -> Enumerator
3148 *
3149 * Returns a new array containing all elements of +ary+
3150 * for which the given +block+ returns a true value.
3151 *
3152 * If no block is given, an Enumerator is returned instead.
3153 *
3154 * [1,2,3,4,5].select {|num| num.even? } #=> [2, 4]
3155 *
3156 * a = %w[ a b c d e f ]
3157 * a.select {|v| v =~ /[aeiou]/ } #=> ["a", "e"]
3158 *
3159 * See also Enumerable#select.
3160 *
3161 * Array#filter is an alias for Array#select.
3162 */
3163
3164 static VALUE
rb_ary_select(VALUE ary)3165 rb_ary_select(VALUE ary)
3166 {
3167 VALUE result;
3168 long i;
3169
3170 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3171 result = rb_ary_new2(RARRAY_LEN(ary));
3172 for (i = 0; i < RARRAY_LEN(ary); i++) {
3173 if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) {
3174 rb_ary_push(result, rb_ary_elt(ary, i));
3175 }
3176 }
3177 return result;
3178 }
3179
3180 struct select_bang_arg {
3181 VALUE ary;
3182 long len[2];
3183 };
3184
3185 static VALUE
select_bang_i(VALUE a)3186 select_bang_i(VALUE a)
3187 {
3188 volatile struct select_bang_arg *arg = (void *)a;
3189 VALUE ary = arg->ary;
3190 long i1, i2;
3191
3192 for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); arg->len[0] = ++i1) {
3193 VALUE v = RARRAY_AREF(ary, i1);
3194 if (!RTEST(rb_yield(v))) continue;
3195 if (i1 != i2) {
3196 rb_ary_store(ary, i2, v);
3197 }
3198 arg->len[1] = ++i2;
3199 }
3200 return (i1 == i2) ? Qnil : ary;
3201 }
3202
3203 static VALUE
select_bang_ensure(VALUE a)3204 select_bang_ensure(VALUE a)
3205 {
3206 volatile struct select_bang_arg *arg = (void *)a;
3207 VALUE ary = arg->ary;
3208 long len = RARRAY_LEN(ary);
3209 long i1 = arg->len[0], i2 = arg->len[1];
3210
3211 if (i2 < len && i2 < i1) {
3212 long tail = 0;
3213 if (i1 < len) {
3214 tail = len - i1;
3215 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
3216 MEMMOVE(ptr + i2, ptr + i1, VALUE, tail);
3217 });
3218 }
3219 ARY_SET_LEN(ary, i2 + tail);
3220 }
3221 return ary;
3222 }
3223
3224 /*
3225 * call-seq:
3226 * ary.select! {|item| block } -> ary or nil
3227 * ary.select! -> Enumerator
3228 * ary.filter! {|item| block } -> ary or nil
3229 * ary.filter! -> Enumerator
3230 *
3231 * Invokes the given block passing in successive elements from +self+,
3232 * deleting elements for which the block returns a +false+ value.
3233 *
3234 * The array may not be changed instantly every time the block is called.
3235 *
3236 * If changes were made, it will return +self+, otherwise it returns +nil+.
3237 *
3238 * If no block is given, an Enumerator is returned instead.
3239 *
3240 * See also Array#keep_if.
3241 *
3242 * Array#filter! is an alias for Array#select!.
3243 */
3244
3245 static VALUE
rb_ary_select_bang(VALUE ary)3246 rb_ary_select_bang(VALUE ary)
3247 {
3248 struct select_bang_arg args;
3249
3250 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3251 rb_ary_modify(ary);
3252
3253 args.ary = ary;
3254 args.len[0] = args.len[1] = 0;
3255 return rb_ensure(select_bang_i, (VALUE)&args, select_bang_ensure, (VALUE)&args);
3256 }
3257
3258 /*
3259 * call-seq:
3260 * ary.keep_if {|item| block} -> ary
3261 * ary.keep_if -> Enumerator
3262 *
3263 * Deletes every element of +self+ for which the given block evaluates to
3264 * +false+, and returns +self+.
3265 *
3266 * If no block is given, an Enumerator is returned instead.
3267 *
3268 * a = %w[ a b c d e f ]
3269 * a.keep_if {|v| v =~ /[aeiou]/ } #=> ["a", "e"]
3270 * a #=> ["a", "e"]
3271 *
3272 * See also Array#select!.
3273 */
3274
3275 static VALUE
rb_ary_keep_if(VALUE ary)3276 rb_ary_keep_if(VALUE ary)
3277 {
3278 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3279 rb_ary_select_bang(ary);
3280 return ary;
3281 }
3282
3283 static void
ary_resize_smaller(VALUE ary,long len)3284 ary_resize_smaller(VALUE ary, long len)
3285 {
3286 rb_ary_modify(ary);
3287 if (RARRAY_LEN(ary) > len) {
3288 ARY_SET_LEN(ary, len);
3289 if (len * 2 < ARY_CAPA(ary) &&
3290 ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
3291 ary_resize_capa(ary, len * 2);
3292 }
3293 }
3294 }
3295
3296 /*
3297 * call-seq:
3298 * ary.delete(obj) -> item or nil
3299 * ary.delete(obj) {block} -> item or result of block
3300 *
3301 * Deletes all items from +self+ that are equal to +obj+.
3302 *
3303 * Returns the last deleted item, or +nil+ if no matching item is found.
3304 *
3305 * If the optional code block is given, the result of the block is returned if
3306 * the item is not found. (To remove +nil+ elements and get an informative
3307 * return value, use Array#compact!)
3308 *
3309 * a = [ "a", "b", "b", "b", "c" ]
3310 * a.delete("b") #=> "b"
3311 * a #=> ["a", "c"]
3312 * a.delete("z") #=> nil
3313 * a.delete("z") {"not found"} #=> "not found"
3314 */
3315
3316 VALUE
rb_ary_delete(VALUE ary,VALUE item)3317 rb_ary_delete(VALUE ary, VALUE item)
3318 {
3319 VALUE v = item;
3320 long i1, i2;
3321
3322 for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
3323 VALUE e = RARRAY_AREF(ary, i1);
3324
3325 if (rb_equal(e, item)) {
3326 v = e;
3327 continue;
3328 }
3329 if (i1 != i2) {
3330 rb_ary_store(ary, i2, e);
3331 }
3332 i2++;
3333 }
3334 if (RARRAY_LEN(ary) == i2) {
3335 if (rb_block_given_p()) {
3336 return rb_yield(item);
3337 }
3338 return Qnil;
3339 }
3340
3341 ary_resize_smaller(ary, i2);
3342
3343 ary_verify(ary);
3344 return v;
3345 }
3346
3347 void
rb_ary_delete_same(VALUE ary,VALUE item)3348 rb_ary_delete_same(VALUE ary, VALUE item)
3349 {
3350 long i1, i2;
3351
3352 for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
3353 VALUE e = RARRAY_AREF(ary, i1);
3354
3355 if (e == item) {
3356 continue;
3357 }
3358 if (i1 != i2) {
3359 rb_ary_store(ary, i2, e);
3360 }
3361 i2++;
3362 }
3363 if (RARRAY_LEN(ary) == i2) {
3364 return;
3365 }
3366
3367 ary_resize_smaller(ary, i2);
3368 }
3369
3370 VALUE
rb_ary_delete_at(VALUE ary,long pos)3371 rb_ary_delete_at(VALUE ary, long pos)
3372 {
3373 long len = RARRAY_LEN(ary);
3374 VALUE del;
3375
3376 if (pos >= len) return Qnil;
3377 if (pos < 0) {
3378 pos += len;
3379 if (pos < 0) return Qnil;
3380 }
3381
3382 rb_ary_modify(ary);
3383 del = RARRAY_AREF(ary, pos);
3384 RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
3385 MEMMOVE(ptr+pos, ptr+pos+1, VALUE, len-pos-1);
3386 });
3387 ARY_INCREASE_LEN(ary, -1);
3388 ary_verify(ary);
3389 return del;
3390 }
3391
3392 /*
3393 * call-seq:
3394 * ary.delete_at(index) -> obj or nil
3395 *
3396 * Deletes the element at the specified +index+, returning that element, or
3397 * +nil+ if the +index+ is out of range.
3398 *
3399 * See also Array#slice!
3400 *
3401 * a = ["ant", "bat", "cat", "dog"]
3402 * a.delete_at(2) #=> "cat"
3403 * a #=> ["ant", "bat", "dog"]
3404 * a.delete_at(99) #=> nil
3405 */
3406
3407 static VALUE
rb_ary_delete_at_m(VALUE ary,VALUE pos)3408 rb_ary_delete_at_m(VALUE ary, VALUE pos)
3409 {
3410 return rb_ary_delete_at(ary, NUM2LONG(pos));
3411 }
3412
3413 /*
3414 * call-seq:
3415 * ary.slice!(index) -> obj or nil
3416 * ary.slice!(start, length) -> new_ary or nil
3417 * ary.slice!(range) -> new_ary or nil
3418 *
3419 * Deletes the element(s) given by an +index+ (optionally up to +length+
3420 * elements) or by a +range+.
3421 *
3422 * Returns the deleted object (or objects), or +nil+ if the +index+ is out of
3423 * range.
3424 *
3425 * a = [ "a", "b", "c" ]
3426 * a.slice!(1) #=> "b"
3427 * a #=> ["a", "c"]
3428 * a.slice!(-1) #=> "c"
3429 * a #=> ["a"]
3430 * a.slice!(100) #=> nil
3431 * a #=> ["a"]
3432 */
3433
3434 static VALUE
rb_ary_slice_bang(int argc,VALUE * argv,VALUE ary)3435 rb_ary_slice_bang(int argc, VALUE *argv, VALUE ary)
3436 {
3437 VALUE arg1, arg2;
3438 long pos, len, orig_len;
3439
3440 rb_ary_modify_check(ary);
3441 if (argc == 2) {
3442 pos = NUM2LONG(argv[0]);
3443 len = NUM2LONG(argv[1]);
3444 delete_pos_len:
3445 if (len < 0) return Qnil;
3446 orig_len = RARRAY_LEN(ary);
3447 if (pos < 0) {
3448 pos += orig_len;
3449 if (pos < 0) return Qnil;
3450 }
3451 else if (orig_len < pos) return Qnil;
3452 if (orig_len < pos + len) {
3453 len = orig_len - pos;
3454 }
3455 if (len == 0) return rb_ary_new2(0);
3456 arg2 = rb_ary_new4(len, RARRAY_CONST_PTR_TRANSIENT(ary)+pos);
3457 RBASIC_SET_CLASS(arg2, rb_obj_class(ary));
3458 rb_ary_splice(ary, pos, len, 0, 0);
3459 return arg2;
3460 }
3461
3462 rb_check_arity(argc, 1, 2);
3463 arg1 = argv[0];
3464
3465 if (!FIXNUM_P(arg1)) {
3466 switch (rb_range_beg_len(arg1, &pos, &len, RARRAY_LEN(ary), 0)) {
3467 case Qtrue:
3468 /* valid range */
3469 goto delete_pos_len;
3470 case Qnil:
3471 /* invalid range */
3472 return Qnil;
3473 default:
3474 /* not a range */
3475 break;
3476 }
3477 }
3478
3479 return rb_ary_delete_at(ary, NUM2LONG(arg1));
3480 }
3481
3482 static VALUE
ary_reject(VALUE orig,VALUE result)3483 ary_reject(VALUE orig, VALUE result)
3484 {
3485 long i;
3486
3487 for (i = 0; i < RARRAY_LEN(orig); i++) {
3488 VALUE v = RARRAY_AREF(orig, i);
3489
3490 if (!RTEST(rb_yield(v))) {
3491 rb_ary_push(result, v);
3492 }
3493 }
3494 return result;
3495 }
3496
3497 static VALUE
reject_bang_i(VALUE a)3498 reject_bang_i(VALUE a)
3499 {
3500 volatile struct select_bang_arg *arg = (void *)a;
3501 VALUE ary = arg->ary;
3502 long i1, i2;
3503
3504 for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); arg->len[0] = ++i1) {
3505 VALUE v = RARRAY_AREF(ary, i1);
3506 if (RTEST(rb_yield(v))) continue;
3507 if (i1 != i2) {
3508 rb_ary_store(ary, i2, v);
3509 }
3510 arg->len[1] = ++i2;
3511 }
3512 return (i1 == i2) ? Qnil : ary;
3513 }
3514
3515 static VALUE
ary_reject_bang(VALUE ary)3516 ary_reject_bang(VALUE ary)
3517 {
3518 struct select_bang_arg args;
3519 rb_ary_modify_check(ary);
3520 args.ary = ary;
3521 args.len[0] = args.len[1] = 0;
3522 return rb_ensure(reject_bang_i, (VALUE)&args, select_bang_ensure, (VALUE)&args);
3523 }
3524
3525 /*
3526 * call-seq:
3527 * ary.reject! {|item| block} -> ary or nil
3528 * ary.reject! -> Enumerator
3529 *
3530 * Deletes every element of +self+ for which the block evaluates to +true+,
3531 * if no changes were made returns +nil+.
3532 *
3533 * The array may not be changed instantly every time the block is called.
3534 *
3535 * See also Enumerable#reject and Array#delete_if.
3536 *
3537 * If no block is given, an Enumerator is returned instead.
3538 */
3539
3540 static VALUE
rb_ary_reject_bang(VALUE ary)3541 rb_ary_reject_bang(VALUE ary)
3542 {
3543 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3544 rb_ary_modify(ary);
3545 return ary_reject_bang(ary);
3546 }
3547
3548 /*
3549 * call-seq:
3550 * ary.reject {|item| block } -> new_ary
3551 * ary.reject -> Enumerator
3552 *
3553 * Returns a new array containing the items in +self+ for which the given
3554 * block is not +true+. The ordering of non-rejected elements is maintained.
3555 *
3556 * See also Array#delete_if
3557 *
3558 * If no block is given, an Enumerator is returned instead.
3559 */
3560
3561 static VALUE
rb_ary_reject(VALUE ary)3562 rb_ary_reject(VALUE ary)
3563 {
3564 VALUE rejected_ary;
3565
3566 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3567 rejected_ary = rb_ary_new();
3568 ary_reject(ary, rejected_ary);
3569 return rejected_ary;
3570 }
3571
3572 /*
3573 * call-seq:
3574 * ary.delete_if {|item| block} -> ary
3575 * ary.delete_if -> Enumerator
3576 *
3577 * Deletes every element of +self+ for which block evaluates to +true+.
3578 *
3579 * The array is changed instantly every time the block is called, not after
3580 * the iteration is over.
3581 *
3582 * See also Array#reject!
3583 *
3584 * If no block is given, an Enumerator is returned instead.
3585 *
3586 * scores = [ 97, 42, 75 ]
3587 * scores.delete_if {|score| score < 80 } #=> [97]
3588 */
3589
3590 static VALUE
rb_ary_delete_if(VALUE ary)3591 rb_ary_delete_if(VALUE ary)
3592 {
3593 ary_verify(ary);
3594 RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3595 ary_reject_bang(ary);
3596 return ary;
3597 }
3598
3599 static VALUE
take_i(RB_BLOCK_CALL_FUNC_ARGLIST (val,cbarg))3600 take_i(RB_BLOCK_CALL_FUNC_ARGLIST(val, cbarg))
3601 {
3602 VALUE *args = (VALUE *)cbarg;
3603 if (args[1] == 0) rb_iter_break();
3604 else args[1]--;
3605 if (argc > 1) val = rb_ary_new4(argc, argv);
3606 rb_ary_push(args[0], val);
3607 return Qnil;
3608 }
3609
3610 static VALUE
take_items(VALUE obj,long n)3611 take_items(VALUE obj, long n)
3612 {
3613 VALUE result = rb_check_array_type(obj);
3614 VALUE args[2];
3615
3616 if (!NIL_P(result)) return rb_ary_subseq(result, 0, n);
3617 result = rb_ary_new2(n);
3618 args[0] = result; args[1] = (VALUE)n;
3619 if (rb_check_block_call(obj, idEach, 0, 0, take_i, (VALUE)args) == Qundef)
3620 rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE" (must respond to :each)",
3621 rb_obj_class(obj));
3622 return result;
3623 }
3624
3625
3626 /*
3627 * call-seq:
3628 * ary.zip(arg, ...) -> new_ary
3629 * ary.zip(arg, ...) {|arr| block} -> nil
3630 *
3631 * Converts any arguments to arrays, then merges elements of +self+ with
3632 * corresponding elements from each argument.
3633 *
3634 * This generates a sequence of <code>ary.size</code> _n_-element arrays,
3635 * where _n_ is one more than the count of arguments.
3636 *
3637 * If the size of any argument is less than the size of the initial array,
3638 * +nil+ values are supplied.
3639 *
3640 * If a block is given, it is invoked for each output +array+, otherwise an
3641 * array of arrays is returned.
3642 *
3643 * a = [ 4, 5, 6 ]
3644 * b = [ 7, 8, 9 ]
3645 * [1, 2, 3].zip(a, b) #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
3646 * [1, 2].zip(a, b) #=> [[1, 4, 7], [2, 5, 8]]
3647 * a.zip([1, 2], [8]) #=> [[4, 1, 8], [5, 2, nil], [6, nil, nil]]
3648 */
3649
3650 static VALUE
rb_ary_zip(int argc,VALUE * argv,VALUE ary)3651 rb_ary_zip(int argc, VALUE *argv, VALUE ary)
3652 {
3653 int i, j;
3654 long len = RARRAY_LEN(ary);
3655 VALUE result = Qnil;
3656
3657 for (i=0; i<argc; i++) {
3658 argv[i] = take_items(argv[i], len);
3659 }
3660
3661 if (rb_block_given_p()) {
3662 int arity = rb_block_arity();
3663
3664 if (arity > 1) {
3665 VALUE work, *tmp;
3666
3667 tmp = ALLOCV_N(VALUE, work, argc+1);
3668
3669 for (i=0; i<RARRAY_LEN(ary); i++) {
3670 tmp[0] = RARRAY_AREF(ary, i);
3671 for (j=0; j<argc; j++) {
3672 tmp[j+1] = rb_ary_elt(argv[j], i);
3673 }
3674 rb_yield_values2(argc+1, tmp);
3675 }
3676
3677 if (work) ALLOCV_END(work);
3678 }
3679 else {
3680 for (i=0; i<RARRAY_LEN(ary); i++) {
3681 VALUE tmp = rb_ary_new2(argc+1);
3682
3683 rb_ary_push(tmp, RARRAY_AREF(ary, i));
3684 for (j=0; j<argc; j++) {
3685 rb_ary_push(tmp, rb_ary_elt(argv[j], i));
3686 }
3687 rb_yield(tmp);
3688 }
3689 }
3690 }
3691 else {
3692 result = rb_ary_new_capa(len);
3693
3694 for (i=0; i<len; i++) {
3695 VALUE tmp = rb_ary_new_capa(argc+1);
3696
3697 rb_ary_push(tmp, RARRAY_AREF(ary, i));
3698 for (j=0; j<argc; j++) {
3699 rb_ary_push(tmp, rb_ary_elt(argv[j], i));
3700 }
3701 rb_ary_push(result, tmp);
3702 }
3703 }
3704
3705 return result;
3706 }
3707
3708 /*
3709 * call-seq:
3710 * ary.transpose -> new_ary
3711 *
3712 * Assumes that +self+ is an array of arrays and transposes the rows and
3713 * columns.
3714 *
3715 * a = [[1,2], [3,4], [5,6]]
3716 * a.transpose #=> [[1, 3, 5], [2, 4, 6]]
3717 *
3718 * If the length of the subarrays don't match, an IndexError is raised.
3719 */
3720
3721 static VALUE
rb_ary_transpose(VALUE ary)3722 rb_ary_transpose(VALUE ary)
3723 {
3724 long elen = -1, alen, i, j;
3725 VALUE tmp, result = 0;
3726
3727 alen = RARRAY_LEN(ary);
3728 if (alen == 0) return rb_ary_dup(ary);
3729 for (i=0; i<alen; i++) {
3730 tmp = to_ary(rb_ary_elt(ary, i));
3731 if (elen < 0) { /* first element */
3732 elen = RARRAY_LEN(tmp);
3733 result = rb_ary_new2(elen);
3734 for (j=0; j<elen; j++) {
3735 rb_ary_store(result, j, rb_ary_new2(alen));
3736 }
3737 }
3738 else if (elen != RARRAY_LEN(tmp)) {
3739 rb_raise(rb_eIndexError, "element size differs (%ld should be %ld)",
3740 RARRAY_LEN(tmp), elen);
3741 }
3742 for (j=0; j<elen; j++) {
3743 rb_ary_store(rb_ary_elt(result, j), i, rb_ary_elt(tmp, j));
3744 }
3745 }
3746 return result;
3747 }
3748
3749 /*
3750 * call-seq:
3751 * ary.replace(other_ary) -> ary
3752 * ary.initialize_copy(other_ary) -> ary
3753 *
3754 * Replaces the contents of +self+ with the contents of +other_ary+,
3755 * truncating or expanding if necessary.
3756 *
3757 * a = [ "a", "b", "c", "d", "e" ]
3758 * a.replace([ "x", "y", "z" ]) #=> ["x", "y", "z"]
3759 * a #=> ["x", "y", "z"]
3760 */
3761
3762 VALUE
rb_ary_replace(VALUE copy,VALUE orig)3763 rb_ary_replace(VALUE copy, VALUE orig)
3764 {
3765 rb_ary_modify_check(copy);
3766 orig = to_ary(orig);
3767 if (copy == orig) return copy;
3768
3769 if (RARRAY_LEN(orig) <= RARRAY_EMBED_LEN_MAX) {
3770 VALUE shared = 0;
3771
3772 if (ARY_OWNS_HEAP_P(copy)) {
3773 ary_heap_free(copy);
3774 }
3775 else if (ARY_SHARED_P(copy)) {
3776 shared = ARY_SHARED(copy);
3777 FL_UNSET_SHARED(copy);
3778 }
3779 FL_SET_EMBED(copy);
3780 ary_memcpy(copy, 0, RARRAY_LEN(orig), RARRAY_CONST_PTR_TRANSIENT(orig));
3781 if (shared) {
3782 rb_ary_decrement_share(shared);
3783 }
3784 ARY_SET_LEN(copy, RARRAY_LEN(orig));
3785 }
3786 else {
3787 VALUE shared = ary_make_shared(orig);
3788 if (ARY_OWNS_HEAP_P(copy)) {
3789 ary_heap_free(copy);
3790 }
3791 else {
3792 rb_ary_unshare_safe(copy);
3793 }
3794 FL_UNSET_EMBED(copy);
3795 ARY_SET_PTR(copy, ARY_HEAP_PTR(orig));
3796 ARY_SET_LEN(copy, ARY_HEAP_LEN(orig));
3797 rb_ary_set_shared(copy, shared);
3798 }
3799 ary_verify(copy);
3800 return copy;
3801 }
3802
3803 /*
3804 * call-seq:
3805 * ary.clear -> ary
3806 *
3807 * Removes all elements from +self+.
3808 *
3809 * a = [ "a", "b", "c", "d", "e" ]
3810 * a.clear #=> [ ]
3811 */
3812
3813 VALUE
rb_ary_clear(VALUE ary)3814 rb_ary_clear(VALUE ary)
3815 {
3816 rb_ary_modify_check(ary);
3817 if (ARY_SHARED_P(ary)) {
3818 if (!ARY_EMBED_P(ary)) {
3819 rb_ary_unshare(ary);
3820 FL_SET_EMBED(ary);
3821 ARY_SET_EMBED_LEN(ary, 0);
3822 }
3823 }
3824 else {
3825 ARY_SET_LEN(ary, 0);
3826 if (ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
3827 ary_resize_capa(ary, ARY_DEFAULT_SIZE * 2);
3828 }
3829 }
3830 ary_verify(ary);
3831 return ary;
3832 }
3833
3834 /*
3835 * call-seq:
3836 * ary.fill(obj) -> ary
3837 * ary.fill(obj, start [, length]) -> ary
3838 * ary.fill(obj, range) -> ary
3839 * ary.fill {|index| block} -> ary
3840 * ary.fill(start [, length]) {|index| block} -> ary
3841 * ary.fill(range) {|index| block} -> ary
3842 *
3843 * The first three forms set the selected elements of +self+ (which
3844 * may be the entire array) to +obj+.
3845 *
3846 * A +start+ of +nil+ is equivalent to zero.
3847 *
3848 * A +length+ of +nil+ is equivalent to the length of the array.
3849 *
3850 * The last three forms fill the array with the value of the given block,
3851 * which is passed the absolute index of each element to be filled.
3852 *
3853 * Negative values of +start+ count from the end of the array, where +-1+ is
3854 * the last element.
3855 *
3856 * a = [ "a", "b", "c", "d" ]
3857 * a.fill("x") #=> ["x", "x", "x", "x"]
3858 * a.fill("z", 2, 2) #=> ["x", "x", "z", "z"]
3859 * a.fill("y", 0..1) #=> ["y", "y", "z", "z"]
3860 * a.fill {|i| i*i} #=> [0, 1, 4, 9]
3861 * a.fill(-2) {|i| i*i*i} #=> [0, 1, 8, 27]
3862 */
3863
3864 static VALUE
rb_ary_fill(int argc,VALUE * argv,VALUE ary)3865 rb_ary_fill(int argc, VALUE *argv, VALUE ary)
3866 {
3867 VALUE item = Qundef, arg1, arg2;
3868 long beg = 0, end = 0, len = 0;
3869
3870 if (rb_block_given_p()) {
3871 rb_scan_args(argc, argv, "02", &arg1, &arg2);
3872 argc += 1; /* hackish */
3873 }
3874 else {
3875 rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
3876 }
3877 switch (argc) {
3878 case 1:
3879 beg = 0;
3880 len = RARRAY_LEN(ary);
3881 break;
3882 case 2:
3883 if (rb_range_beg_len(arg1, &beg, &len, RARRAY_LEN(ary), 1)) {
3884 break;
3885 }
3886 /* fall through */
3887 case 3:
3888 beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
3889 if (beg < 0) {
3890 beg = RARRAY_LEN(ary) + beg;
3891 if (beg < 0) beg = 0;
3892 }
3893 len = NIL_P(arg2) ? RARRAY_LEN(ary) - beg : NUM2LONG(arg2);
3894 break;
3895 }
3896 rb_ary_modify(ary);
3897 if (len < 0) {
3898 return ary;
3899 }
3900 if (beg >= ARY_MAX_SIZE || len > ARY_MAX_SIZE - beg) {
3901 rb_raise(rb_eArgError, "argument too big");
3902 }
3903 end = beg + len;
3904 if (RARRAY_LEN(ary) < end) {
3905 if (end >= ARY_CAPA(ary)) {
3906 ary_resize_capa(ary, end);
3907 }
3908 ary_mem_clear(ary, RARRAY_LEN(ary), end - RARRAY_LEN(ary));
3909 ARY_SET_LEN(ary, end);
3910 }
3911
3912 if (item == Qundef) {
3913 VALUE v;
3914 long i;
3915
3916 for (i=beg; i<end; i++) {
3917 v = rb_yield(LONG2NUM(i));
3918 if (i>=RARRAY_LEN(ary)) break;
3919 ARY_SET(ary, i, v);
3920 }
3921 }
3922 else {
3923 ary_memfill(ary, beg, len, item);
3924 }
3925 return ary;
3926 }
3927
3928 /*
3929 * call-seq:
3930 * ary + other_ary -> new_ary
3931 *
3932 * Concatenation --- Returns a new array built by concatenating the
3933 * two arrays together to produce a third array.
3934 *
3935 * [ 1, 2, 3 ] + [ 4, 5 ] #=> [ 1, 2, 3, 4, 5 ]
3936 * a = [ "a", "b", "c" ]
3937 * c = a + [ "d", "e", "f" ]
3938 * c #=> [ "a", "b", "c", "d", "e", "f" ]
3939 * a #=> [ "a", "b", "c" ]
3940 *
3941 * Note that
3942 * x += y
3943 * is the same as
3944 * x = x + y
3945 * This means that it produces a new array. As a consequence,
3946 * repeated use of <code>+=</code> on arrays can be quite inefficient.
3947 *
3948 * See also Array#concat.
3949 */
3950
3951 VALUE
rb_ary_plus(VALUE x,VALUE y)3952 rb_ary_plus(VALUE x, VALUE y)
3953 {
3954 VALUE z;
3955 long len, xlen, ylen;
3956
3957 y = to_ary(y);
3958 xlen = RARRAY_LEN(x);
3959 ylen = RARRAY_LEN(y);
3960 len = xlen + ylen;
3961 z = rb_ary_new2(len);
3962
3963 ary_memcpy(z, 0, xlen, RARRAY_CONST_PTR_TRANSIENT(x));
3964 ary_memcpy(z, xlen, ylen, RARRAY_CONST_PTR_TRANSIENT(y));
3965 ARY_SET_LEN(z, len);
3966 return z;
3967 }
3968
3969 static VALUE
ary_append(VALUE x,VALUE y)3970 ary_append(VALUE x, VALUE y)
3971 {
3972 long n = RARRAY_LEN(y);
3973 if (n > 0) {
3974 rb_ary_splice(x, RARRAY_LEN(x), 0, RARRAY_CONST_PTR_TRANSIENT(y), n);
3975 }
3976 return x;
3977 }
3978
3979 /*
3980 * call-seq:
3981 * ary.concat(other_ary1, other_ary2, ...) -> ary
3982 *
3983 * Appends the elements of <code>other_ary</code>s to +self+.
3984 *
3985 * [ "a", "b" ].concat( ["c", "d"]) #=> [ "a", "b", "c", "d" ]
3986 * [ "a" ].concat( ["b"], ["c", "d"]) #=> [ "a", "b", "c", "d" ]
3987 * [ "a" ].concat #=> [ "a" ]
3988 *
3989 * a = [ 1, 2, 3 ]
3990 * a.concat( [ 4, 5 ])
3991 * a #=> [ 1, 2, 3, 4, 5 ]
3992 *
3993 * a = [ 1, 2 ]
3994 * a.concat(a, a) #=> [1, 2, 1, 2, 1, 2]
3995 *
3996 * See also Array#+.
3997 */
3998
3999 static VALUE
rb_ary_concat_multi(int argc,VALUE * argv,VALUE ary)4000 rb_ary_concat_multi(int argc, VALUE *argv, VALUE ary)
4001 {
4002 rb_ary_modify_check(ary);
4003
4004 if (argc == 1) {
4005 rb_ary_concat(ary, argv[0]);
4006 }
4007 else if (argc > 1) {
4008 int i;
4009 VALUE args = rb_ary_tmp_new(argc);
4010 for (i = 0; i < argc; i++) {
4011 rb_ary_concat(args, argv[i]);
4012 }
4013 ary_append(ary, args);
4014 }
4015
4016 ary_verify(ary);
4017 return ary;
4018 }
4019
4020 VALUE
rb_ary_concat(VALUE x,VALUE y)4021 rb_ary_concat(VALUE x, VALUE y)
4022 {
4023 return ary_append(x, to_ary(y));
4024 }
4025
4026 /*
4027 * call-seq:
4028 * ary * int -> new_ary
4029 * ary * str -> new_string
4030 *
4031 * Repetition --- With a String argument, equivalent to
4032 * <code>ary.join(str)</code>.
4033 *
4034 * Otherwise, returns a new array built by concatenating the +int+ copies of
4035 * +self+.
4036 *
4037 *
4038 * [ 1, 2, 3 ] * 3 #=> [ 1, 2, 3, 1, 2, 3, 1, 2, 3 ]
4039 * [ 1, 2, 3 ] * "," #=> "1,2,3"
4040 *
4041 */
4042
4043 static VALUE
rb_ary_times(VALUE ary,VALUE times)4044 rb_ary_times(VALUE ary, VALUE times)
4045 {
4046 VALUE ary2, tmp;
4047 const VALUE *ptr;
4048 long t, len;
4049
4050 tmp = rb_check_string_type(times);
4051 if (!NIL_P(tmp)) {
4052 return rb_ary_join(ary, tmp);
4053 }
4054
4055 len = NUM2LONG(times);
4056 if (len == 0) {
4057 ary2 = ary_new(rb_obj_class(ary), 0);
4058 goto out;
4059 }
4060 if (len < 0) {
4061 rb_raise(rb_eArgError, "negative argument");
4062 }
4063 if (ARY_MAX_SIZE/len < RARRAY_LEN(ary)) {
4064 rb_raise(rb_eArgError, "argument too big");
4065 }
4066 len *= RARRAY_LEN(ary);
4067
4068 ary2 = ary_new(rb_obj_class(ary), len);
4069 ARY_SET_LEN(ary2, len);
4070
4071 ptr = RARRAY_CONST_PTR_TRANSIENT(ary);
4072 t = RARRAY_LEN(ary);
4073 if (0 < t) {
4074 ary_memcpy(ary2, 0, t, ptr);
4075 while (t <= len/2) {
4076 ary_memcpy(ary2, t, t, RARRAY_CONST_PTR_TRANSIENT(ary2));
4077 t *= 2;
4078 }
4079 if (t < len) {
4080 ary_memcpy(ary2, t, len-t, RARRAY_CONST_PTR_TRANSIENT(ary2));
4081 }
4082 }
4083 out:
4084 OBJ_INFECT(ary2, ary);
4085
4086 return ary2;
4087 }
4088
4089 /*
4090 * call-seq:
4091 * ary.assoc(obj) -> element_ary or nil
4092 *
4093 * Searches through an array whose elements are also arrays comparing +obj+
4094 * with the first element of each contained array using <code>obj.==</code>.
4095 *
4096 * Returns the first contained array that matches (that is, the first
4097 * associated array), or +nil+ if no match is found.
4098 *
4099 * See also Array#rassoc
4100 *
4101 * s1 = [ "colors", "red", "blue", "green" ]
4102 * s2 = [ "letters", "a", "b", "c" ]
4103 * s3 = "foo"
4104 * a = [ s1, s2, s3 ]
4105 * a.assoc("letters") #=> [ "letters", "a", "b", "c" ]
4106 * a.assoc("foo") #=> nil
4107 */
4108
4109 VALUE
rb_ary_assoc(VALUE ary,VALUE key)4110 rb_ary_assoc(VALUE ary, VALUE key)
4111 {
4112 long i;
4113 VALUE v;
4114
4115 for (i = 0; i < RARRAY_LEN(ary); ++i) {
4116 v = rb_check_array_type(RARRAY_AREF(ary, i));
4117 if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
4118 rb_equal(RARRAY_AREF(v, 0), key))
4119 return v;
4120 }
4121 return Qnil;
4122 }
4123
4124 /*
4125 * call-seq:
4126 * ary.rassoc(obj) -> element_ary or nil
4127 *
4128 * Searches through the array whose elements are also arrays.
4129 *
4130 * Compares +obj+ with the second element of each contained array using
4131 * <code>obj.==</code>.
4132 *
4133 * Returns the first contained array that matches +obj+.
4134 *
4135 * See also Array#assoc.
4136 *
4137 * a = [ [ 1, "one"], [2, "two"], [3, "three"], ["ii", "two"] ]
4138 * a.rassoc("two") #=> [2, "two"]
4139 * a.rassoc("four") #=> nil
4140 */
4141
4142 VALUE
rb_ary_rassoc(VALUE ary,VALUE value)4143 rb_ary_rassoc(VALUE ary, VALUE value)
4144 {
4145 long i;
4146 VALUE v;
4147
4148 for (i = 0; i < RARRAY_LEN(ary); ++i) {
4149 v = RARRAY_AREF(ary, i);
4150 if (RB_TYPE_P(v, T_ARRAY) &&
4151 RARRAY_LEN(v) > 1 &&
4152 rb_equal(RARRAY_AREF(v, 1), value))
4153 return v;
4154 }
4155 return Qnil;
4156 }
4157
4158 static VALUE
recursive_equal(VALUE ary1,VALUE ary2,int recur)4159 recursive_equal(VALUE ary1, VALUE ary2, int recur)
4160 {
4161 long i, len1;
4162 const VALUE *p1, *p2;
4163
4164 if (recur) return Qtrue; /* Subtle! */
4165
4166 /* rb_equal() can evacuate ptrs */
4167 p1 = RARRAY_CONST_PTR(ary1);
4168 p2 = RARRAY_CONST_PTR(ary2);
4169 len1 = RARRAY_LEN(ary1);
4170
4171 for (i = 0; i < len1; i++) {
4172 if (*p1 != *p2) {
4173 if (rb_equal(*p1, *p2)) {
4174 len1 = RARRAY_LEN(ary1);
4175 if (len1 != RARRAY_LEN(ary2))
4176 return Qfalse;
4177 if (len1 < i)
4178 return Qtrue;
4179 p1 = RARRAY_CONST_PTR(ary1) + i;
4180 p2 = RARRAY_CONST_PTR(ary2) + i;
4181 }
4182 else {
4183 return Qfalse;
4184 }
4185 }
4186 p1++;
4187 p2++;
4188 }
4189 return Qtrue;
4190 }
4191
4192 /*
4193 * call-seq:
4194 * ary == other_ary -> bool
4195 *
4196 * Equality --- Two arrays are equal if they contain the same number of
4197 * elements and if each element is equal to (according to Object#==) the
4198 * corresponding element in +other_ary+.
4199 *
4200 * [ "a", "c" ] == [ "a", "c", 7 ] #=> false
4201 * [ "a", "c", 7 ] == [ "a", "c", 7 ] #=> true
4202 * [ "a", "c", 7 ] == [ "a", "d", "f" ] #=> false
4203 *
4204 */
4205
4206 static VALUE
rb_ary_equal(VALUE ary1,VALUE ary2)4207 rb_ary_equal(VALUE ary1, VALUE ary2)
4208 {
4209 if (ary1 == ary2) return Qtrue;
4210 if (!RB_TYPE_P(ary2, T_ARRAY)) {
4211 if (!rb_respond_to(ary2, idTo_ary)) {
4212 return Qfalse;
4213 }
4214 return rb_equal(ary2, ary1);
4215 }
4216 if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
4217 if (RARRAY_CONST_PTR_TRANSIENT(ary1) == RARRAY_CONST_PTR_TRANSIENT(ary2)) return Qtrue;
4218 return rb_exec_recursive_paired(recursive_equal, ary1, ary2, ary2);
4219 }
4220
4221 static VALUE
recursive_eql(VALUE ary1,VALUE ary2,int recur)4222 recursive_eql(VALUE ary1, VALUE ary2, int recur)
4223 {
4224 long i;
4225
4226 if (recur) return Qtrue; /* Subtle! */
4227 for (i=0; i<RARRAY_LEN(ary1); i++) {
4228 if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
4229 return Qfalse;
4230 }
4231 return Qtrue;
4232 }
4233
4234 /*
4235 * call-seq:
4236 * ary.eql?(other) -> true or false
4237 *
4238 * Returns +true+ if +self+ and +other+ are the same object,
4239 * or are both arrays with the same content (according to Object#eql?).
4240 */
4241
4242 static VALUE
rb_ary_eql(VALUE ary1,VALUE ary2)4243 rb_ary_eql(VALUE ary1, VALUE ary2)
4244 {
4245 if (ary1 == ary2) return Qtrue;
4246 if (!RB_TYPE_P(ary2, T_ARRAY)) return Qfalse;
4247 if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
4248 if (RARRAY_CONST_PTR_TRANSIENT(ary1) == RARRAY_CONST_PTR_TRANSIENT(ary2)) return Qtrue;
4249 return rb_exec_recursive_paired(recursive_eql, ary1, ary2, ary2);
4250 }
4251
4252 /*
4253 * call-seq:
4254 * ary.hash -> integer
4255 *
4256 * Compute a hash-code for this array.
4257 *
4258 * Two arrays with the same content will have the same hash code (and will
4259 * compare using #eql?).
4260 *
4261 * See also Object#hash.
4262 */
4263
4264 static VALUE
rb_ary_hash(VALUE ary)4265 rb_ary_hash(VALUE ary)
4266 {
4267 long i;
4268 st_index_t h;
4269 VALUE n;
4270
4271 h = rb_hash_start(RARRAY_LEN(ary));
4272 h = rb_hash_uint(h, (st_index_t)rb_ary_hash);
4273 for (i=0; i<RARRAY_LEN(ary); i++) {
4274 n = rb_hash(RARRAY_AREF(ary, i));
4275 h = rb_hash_uint(h, NUM2LONG(n));
4276 }
4277 h = rb_hash_end(h);
4278 return ST2FIX(h);
4279 }
4280
4281 /*
4282 * call-seq:
4283 * ary.include?(object) -> true or false
4284 *
4285 * Returns +true+ if the given +object+ is present in +self+ (that is, if any
4286 * element <code>==</code> +object+), otherwise returns +false+.
4287 *
4288 * a = [ "a", "b", "c" ]
4289 * a.include?("b") #=> true
4290 * a.include?("z") #=> false
4291 */
4292
4293 VALUE
rb_ary_includes(VALUE ary,VALUE item)4294 rb_ary_includes(VALUE ary, VALUE item)
4295 {
4296 long i;
4297 VALUE e;
4298
4299 for (i=0; i<RARRAY_LEN(ary); i++) {
4300 e = RARRAY_AREF(ary, i);
4301 if (rb_equal(e, item)) {
4302 return Qtrue;
4303 }
4304 }
4305 return Qfalse;
4306 }
4307
4308 static VALUE
rb_ary_includes_by_eql(VALUE ary,VALUE item)4309 rb_ary_includes_by_eql(VALUE ary, VALUE item)
4310 {
4311 long i;
4312 VALUE e;
4313
4314 for (i=0; i<RARRAY_LEN(ary); i++) {
4315 e = RARRAY_AREF(ary, i);
4316 if (rb_eql(item, e)) {
4317 return Qtrue;
4318 }
4319 }
4320 return Qfalse;
4321 }
4322
4323 static VALUE
recursive_cmp(VALUE ary1,VALUE ary2,int recur)4324 recursive_cmp(VALUE ary1, VALUE ary2, int recur)
4325 {
4326 long i, len;
4327
4328 if (recur) return Qundef; /* Subtle! */
4329 len = RARRAY_LEN(ary1);
4330 if (len > RARRAY_LEN(ary2)) {
4331 len = RARRAY_LEN(ary2);
4332 }
4333 for (i=0; i<len; i++) {
4334 VALUE e1 = rb_ary_elt(ary1, i), e2 = rb_ary_elt(ary2, i);
4335 VALUE v = rb_funcallv(e1, id_cmp, 1, &e2);
4336 if (v != INT2FIX(0)) {
4337 return v;
4338 }
4339 }
4340 return Qundef;
4341 }
4342
4343 /*
4344 * call-seq:
4345 * ary <=> other_ary -> -1, 0, +1 or nil
4346 *
4347 * Comparison --- Returns an integer (+-1+, +0+, or <code>+1</code>) if this
4348 * array is less than, equal to, or greater than +other_ary+.
4349 *
4350 * Each object in each array is compared (using the <=> operator).
4351 *
4352 * Arrays are compared in an "element-wise" manner; the first element of +ary+
4353 * is compared with the first one of +other_ary+ using the <=> operator, then
4354 * each of the second elements, etc...
4355 * As soon as the result of any such comparison is non zero (i.e. the two
4356 * corresponding elements are not equal), that result is returned for the
4357 * whole array comparison.
4358 *
4359 * If all the elements are equal, then the result is based on a comparison of
4360 * the array lengths. Thus, two arrays are "equal" according to Array#<=> if,
4361 * and only if, they have the same length and the value of each element is
4362 * equal to the value of the corresponding element in the other array.
4363 *
4364 * +nil+ is returned if the +other_ary+ is not an array or if the comparison
4365 * of two elements returned +nil+.
4366 *
4367 * [ "a", "a", "c" ] <=> [ "a", "b", "c" ] #=> -1
4368 * [ 1, 2, 3, 4, 5, 6 ] <=> [ 1, 2 ] #=> +1
4369 * [ 1, 2 ] <=> [ 1, :two ] #=> nil
4370 *
4371 */
4372
4373 VALUE
rb_ary_cmp(VALUE ary1,VALUE ary2)4374 rb_ary_cmp(VALUE ary1, VALUE ary2)
4375 {
4376 long len;
4377 VALUE v;
4378
4379 ary2 = rb_check_array_type(ary2);
4380 if (NIL_P(ary2)) return Qnil;
4381 if (ary1 == ary2) return INT2FIX(0);
4382 v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
4383 if (v != Qundef) return v;
4384 len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
4385 if (len == 0) return INT2FIX(0);
4386 if (len > 0) return INT2FIX(1);
4387 return INT2FIX(-1);
4388 }
4389
4390 static VALUE
ary_add_hash(VALUE hash,VALUE ary)4391 ary_add_hash(VALUE hash, VALUE ary)
4392 {
4393 long i;
4394
4395 for (i=0; i<RARRAY_LEN(ary); i++) {
4396 VALUE elt = RARRAY_AREF(ary, i);
4397 rb_hash_add_new_element(hash, elt, elt);
4398 }
4399 return hash;
4400 }
4401
4402 static inline VALUE
ary_tmp_hash_new(VALUE ary)4403 ary_tmp_hash_new(VALUE ary)
4404 {
4405 long size = RARRAY_LEN(ary);
4406 VALUE hash = rb_hash_new_with_size(size);
4407
4408 RBASIC_CLEAR_CLASS(hash);
4409 return hash;
4410 }
4411
4412 static VALUE
ary_make_hash(VALUE ary)4413 ary_make_hash(VALUE ary)
4414 {
4415 VALUE hash = ary_tmp_hash_new(ary);
4416 return ary_add_hash(hash, ary);
4417 }
4418
4419 static VALUE
ary_add_hash_by(VALUE hash,VALUE ary)4420 ary_add_hash_by(VALUE hash, VALUE ary)
4421 {
4422 long i;
4423
4424 for (i = 0; i < RARRAY_LEN(ary); ++i) {
4425 VALUE v = rb_ary_elt(ary, i), k = rb_yield(v);
4426 rb_hash_add_new_element(hash, k, v);
4427 }
4428 return hash;
4429 }
4430
4431 static VALUE
ary_make_hash_by(VALUE ary)4432 ary_make_hash_by(VALUE ary)
4433 {
4434 VALUE hash = ary_tmp_hash_new(ary);
4435 return ary_add_hash_by(hash, ary);
4436 }
4437
4438 static inline void
ary_recycle_hash(VALUE hash)4439 ary_recycle_hash(VALUE hash)
4440 {
4441 assert(RBASIC_CLASS(hash) == 0);
4442 if (RHASH_ST_TABLE_P(hash)) {
4443 st_table *tbl = RHASH_ST_TABLE(hash);
4444 st_free_table(tbl);
4445 RHASH_ST_CLEAR(hash);
4446 }
4447 }
4448
4449 /*
4450 * call-seq:
4451 * ary - other_ary -> new_ary
4452 *
4453 * Array Difference
4454 *
4455 * Returns a new array that is a copy of the original array, removing any
4456 * items that also appear in +other_ary+. The order is preserved from the
4457 * original array.
4458 *
4459 * It compares elements using their #hash and #eql? methods for efficiency.
4460 *
4461 * [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ] #=> [ 3, 3, 5 ]
4462 *
4463 * If you need set-like behavior, see the library class Set.
4464 *
4465 * See also Array#difference.
4466 */
4467
4468 static VALUE
rb_ary_diff(VALUE ary1,VALUE ary2)4469 rb_ary_diff(VALUE ary1, VALUE ary2)
4470 {
4471 VALUE ary3;
4472 VALUE hash;
4473 long i;
4474
4475 ary2 = to_ary(ary2);
4476 ary3 = rb_ary_new();
4477
4478 if (RARRAY_LEN(ary1) <= SMALL_ARRAY_LEN || RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
4479 for (i=0; i<RARRAY_LEN(ary1); i++) {
4480 VALUE elt = rb_ary_elt(ary1, i);
4481 if (rb_ary_includes_by_eql(ary2, elt)) continue;
4482 rb_ary_push(ary3, elt);
4483 }
4484 return ary3;
4485 }
4486
4487 hash = ary_make_hash(ary2);
4488 for (i=0; i<RARRAY_LEN(ary1); i++) {
4489 if (rb_hash_stlike_lookup(hash, RARRAY_AREF(ary1, i), NULL)) continue;
4490 rb_ary_push(ary3, rb_ary_elt(ary1, i));
4491 }
4492 ary_recycle_hash(hash);
4493 return ary3;
4494 }
4495
4496 /*
4497 * call-seq:
4498 * ary.difference(other_ary1, other_ary2, ...) -> ary
4499 *
4500 * Array Difference
4501 *
4502 * Returns a new array that is a copy of the receiver, removing any items
4503 * that also appear in any of the arrays given as arguments.
4504 * The order is preserved from the original array.
4505 *
4506 * It compares elements using their #hash and #eql? methods for efficiency.
4507 *
4508 * [ 1, 1, 2, 2, 3, 3, 4, 5 ].difference([ 1, 2, 4 ]) #=> [ 3, 3, 5 ]
4509 * [ 1, 'c', :s, 'yep' ].difference([ 1 ], [ 'a', 'c' ]) #=> [ :s, "yep" ]
4510 *
4511 * If you need set-like behavior, see the library class Set.
4512 *
4513 * See also Array#-.
4514 */
4515
4516 static VALUE
rb_ary_difference_multi(int argc,VALUE * argv,VALUE ary)4517 rb_ary_difference_multi(int argc, VALUE *argv, VALUE ary)
4518 {
4519 VALUE ary_diff;
4520 long i, length;
4521 volatile VALUE t0;
4522 bool *is_hash = ALLOCV_N(bool, t0, argc);
4523 ary_diff = rb_ary_new();
4524 length = RARRAY_LEN(ary);
4525
4526 for (i = 0; i < argc; i++) {
4527 argv[i] = to_ary(argv[i]);
4528 is_hash[i] = (length > SMALL_ARRAY_LEN && RARRAY_LEN(argv[i]) > SMALL_ARRAY_LEN);
4529 if (is_hash[i]) argv[i] = ary_make_hash(argv[i]);
4530 }
4531
4532 for (i = 0; i < RARRAY_LEN(ary); i++) {
4533 int j;
4534 VALUE elt = rb_ary_elt(ary, i);
4535 for (j = 0; j < argc; j++){
4536 if (is_hash[j]) {
4537 if (rb_hash_stlike_lookup(argv[j], RARRAY_AREF(ary, i), NULL))
4538 break;
4539 }
4540 else {
4541 if (rb_ary_includes_by_eql(argv[j], elt)) break;
4542 }
4543 }
4544 if (j == argc) rb_ary_push(ary_diff, elt);
4545 }
4546
4547 ALLOCV_END(t0);
4548
4549 return ary_diff;
4550 }
4551
4552
4553 /*
4554 * call-seq:
4555 * ary & other_ary -> new_ary
4556 *
4557 * Set Intersection --- Returns a new array containing unique elements common to the
4558 * two arrays. The order is preserved from the original array.
4559 *
4560 * It compares elements using their #hash and #eql? methods for efficiency.
4561 *
4562 * [ 1, 1, 3, 5 ] & [ 3, 2, 1 ] #=> [ 1, 3 ]
4563 * [ 'a', 'b', 'b', 'z' ] & [ 'a', 'b', 'c' ] #=> [ 'a', 'b' ]
4564 *
4565 * See also Array#uniq.
4566 */
4567
4568
4569 static VALUE
rb_ary_and(VALUE ary1,VALUE ary2)4570 rb_ary_and(VALUE ary1, VALUE ary2)
4571 {
4572 VALUE hash, ary3, v;
4573 st_data_t vv;
4574 long i;
4575
4576 ary2 = to_ary(ary2);
4577 ary3 = rb_ary_new();
4578 if (RARRAY_LEN(ary1) == 0 || RARRAY_LEN(ary2) == 0) return ary3;
4579
4580 if (RARRAY_LEN(ary1) <= SMALL_ARRAY_LEN && RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
4581 for (i=0; i<RARRAY_LEN(ary1); i++) {
4582 v = RARRAY_AREF(ary1, i);
4583 if (!rb_ary_includes_by_eql(ary2, v)) continue;
4584 if (rb_ary_includes_by_eql(ary3, v)) continue;
4585 rb_ary_push(ary3, v);
4586 }
4587 return ary3;
4588 }
4589
4590 hash = ary_make_hash(ary2);
4591
4592 for (i=0; i<RARRAY_LEN(ary1); i++) {
4593 v = RARRAY_AREF(ary1, i);
4594 vv = (st_data_t)v;
4595 if (rb_hash_stlike_delete(hash, &vv, 0)) {
4596 rb_ary_push(ary3, v);
4597 }
4598 }
4599 ary_recycle_hash(hash);
4600
4601 return ary3;
4602 }
4603
4604 static int
ary_hash_orset(st_data_t * key,st_data_t * value,st_data_t arg,int existing)4605 ary_hash_orset(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
4606 {
4607 if (existing) return ST_STOP;
4608 *key = *value = (VALUE)arg;
4609 return ST_CONTINUE;
4610 }
4611
4612 static void
rb_ary_union(VALUE ary_union,VALUE ary)4613 rb_ary_union(VALUE ary_union, VALUE ary)
4614 {
4615 long i;
4616 for (i = 0; i < RARRAY_LEN(ary); i++) {
4617 VALUE elt = rb_ary_elt(ary, i);
4618 if (rb_ary_includes_by_eql(ary_union, elt)) continue;
4619 rb_ary_push(ary_union, elt);
4620 }
4621 }
4622
4623 static void
rb_ary_union_hash(VALUE hash,VALUE ary2)4624 rb_ary_union_hash(VALUE hash, VALUE ary2)
4625 {
4626 long i;
4627 for (i = 0; i < RARRAY_LEN(ary2); i++) {
4628 VALUE elt = RARRAY_AREF(ary2, i);
4629 if (!rb_hash_stlike_update(hash, (st_data_t)elt, ary_hash_orset, (st_data_t)elt)) {
4630 RB_OBJ_WRITTEN(hash, Qundef, elt);
4631 }
4632 }
4633 }
4634
4635 /*
4636 * call-seq:
4637 * ary | other_ary -> new_ary
4638 *
4639 * Set Union --- Returns a new array by joining +ary+ with +other_ary+,
4640 * excluding any duplicates and preserving the order from the given arrays.
4641 *
4642 * It compares elements using their #hash and #eql? methods for efficiency.
4643 *
4644 * [ "a", "b", "c" ] | [ "c", "d", "a" ] #=> [ "a", "b", "c", "d" ]
4645 * [ "c", "d", "a" ] | [ "a", "b", "c" ] #=> [ "c", "d", "a", "b" ]
4646 *
4647 * See also Array#union.
4648 */
4649
4650 static VALUE
rb_ary_or(VALUE ary1,VALUE ary2)4651 rb_ary_or(VALUE ary1, VALUE ary2)
4652 {
4653 VALUE hash, ary3;
4654
4655 ary2 = to_ary(ary2);
4656 if (RARRAY_LEN(ary1) + RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
4657 ary3 = rb_ary_new();
4658 rb_ary_union(ary3, ary1);
4659 rb_ary_union(ary3, ary2);
4660 return ary3;
4661 }
4662
4663 hash = ary_make_hash(ary1);
4664 rb_ary_union_hash(hash, ary2);
4665
4666 ary3 = rb_hash_values(hash);
4667 ary_recycle_hash(hash);
4668 return ary3;
4669 }
4670
4671 /*
4672 * call-seq:
4673 * ary.union(other_ary1, other_ary2, ...) -> ary
4674 *
4675 * Set Union --- Returns a new array by joining <code>other_ary</code>s with +self+,
4676 * excluding any duplicates and preserving the order from the given arrays.
4677 *
4678 * It compares elements using their #hash and #eql? methods for efficiency.
4679 *
4680 * [ "a", "b", "c" ].union( [ "c", "d", "a" ] ) #=> [ "a", "b", "c", "d" ]
4681 * [ "a" ].union( ["e", "b"], ["a", "c", "b"] ) #=> [ "a", "e", "b", "c" ]
4682 * [ "a" ].union #=> [ "a" ]
4683 *
4684 * See also Array#|.
4685 */
4686
4687 static VALUE
rb_ary_union_multi(int argc,VALUE * argv,VALUE ary)4688 rb_ary_union_multi(int argc, VALUE *argv, VALUE ary)
4689 {
4690 int i;
4691 long sum;
4692 VALUE hash, ary_union;
4693
4694 sum = RARRAY_LEN(ary);
4695 for (i = 0; i < argc; i++){
4696 argv[i] = to_ary(argv[i]);
4697 sum += RARRAY_LEN(argv[i]);
4698 }
4699
4700 if (sum <= SMALL_ARRAY_LEN) {
4701 ary_union = rb_ary_new();
4702
4703 rb_ary_union(ary_union, ary);
4704 for (i = 0; i < argc; i++) rb_ary_union(ary_union, argv[i]);
4705
4706 return ary_union;
4707 }
4708
4709 hash = ary_make_hash(ary);
4710 for (i = 0; i < argc; i++) rb_ary_union_hash(hash, argv[i]);
4711
4712 ary_union = rb_hash_values(hash);
4713 ary_recycle_hash(hash);
4714 return ary_union;
4715 }
4716
4717 /*
4718 * call-seq:
4719 * ary.max -> obj
4720 * ary.max {|a, b| block} -> obj
4721 * ary.max(n) -> array
4722 * ary.max(n) {|a, b| block} -> array
4723 *
4724 * Returns the object in _ary_ with the maximum value. The
4725 * first form assumes all objects implement <code>Comparable</code>;
4726 * the second uses the block to return <em>a <=> b</em>.
4727 *
4728 * ary = %w(albatross dog horse)
4729 * ary.max #=> "horse"
4730 * ary.max {|a, b| a.length <=> b.length} #=> "albatross"
4731 *
4732 * If the +n+ argument is given, maximum +n+ elements are returned
4733 * as an array.
4734 *
4735 * ary = %w[albatross dog horse]
4736 * ary.max(2) #=> ["horse", "dog"]
4737 * ary.max(2) {|a, b| a.length <=> b.length } #=> ["albatross", "horse"]
4738 */
4739 static VALUE
rb_ary_max(int argc,VALUE * argv,VALUE ary)4740 rb_ary_max(int argc, VALUE *argv, VALUE ary)
4741 {
4742 struct cmp_opt_data cmp_opt = { 0, 0 };
4743 VALUE result = Qundef, v;
4744 VALUE num;
4745 long i;
4746
4747 if (rb_check_arity(argc, 0, 1) && !NIL_P(num = argv[0]))
4748 return rb_nmin_run(ary, num, 0, 1, 1);
4749
4750 if (rb_block_given_p()) {
4751 for (i = 0; i < RARRAY_LEN(ary); i++) {
4752 v = RARRAY_AREF(ary, i);
4753 if (result == Qundef || rb_cmpint(rb_yield_values(2, v, result), v, result) > 0) {
4754 result = v;
4755 }
4756 }
4757 }
4758 else {
4759 for (i = 0; i < RARRAY_LEN(ary); i++) {
4760 v = RARRAY_AREF(ary, i);
4761 if (result == Qundef || OPTIMIZED_CMP(v, result, cmp_opt) > 0) {
4762 result = v;
4763 }
4764 }
4765 }
4766 if (result == Qundef) return Qnil;
4767 return result;
4768 }
4769
4770 /*
4771 * call-seq:
4772 * ary.min -> obj
4773 * ary.min {| a,b | block } -> obj
4774 * ary.min(n) -> array
4775 * ary.min(n) {| a,b | block } -> array
4776 *
4777 * Returns the object in _ary_ with the minimum value. The
4778 * first form assumes all objects implement <code>Comparable</code>;
4779 * the second uses the block to return <em>a <=> b</em>.
4780 *
4781 * ary = %w(albatross dog horse)
4782 * ary.min #=> "albatross"
4783 * ary.min {|a, b| a.length <=> b.length} #=> "dog"
4784 *
4785 * If the +n+ argument is given, minimum +n+ elements are returned
4786 * as an array.
4787 *
4788 * ary = %w[albatross dog horse]
4789 * ary.min(2) #=> ["albatross", "dog"]
4790 * ary.min(2) {|a, b| a.length <=> b.length } #=> ["dog", "horse"]
4791 */
4792 static VALUE
rb_ary_min(int argc,VALUE * argv,VALUE ary)4793 rb_ary_min(int argc, VALUE *argv, VALUE ary)
4794 {
4795 struct cmp_opt_data cmp_opt = { 0, 0 };
4796 VALUE result = Qundef, v;
4797 VALUE num;
4798 long i;
4799
4800 if (rb_check_arity(argc, 0, 1) && !NIL_P(num = argv[0]))
4801 return rb_nmin_run(ary, num, 0, 0, 1);
4802
4803 if (rb_block_given_p()) {
4804 for (i = 0; i < RARRAY_LEN(ary); i++) {
4805 v = RARRAY_AREF(ary, i);
4806 if (result == Qundef || rb_cmpint(rb_yield_values(2, v, result), v, result) < 0) {
4807 result = v;
4808 }
4809 }
4810 }
4811 else {
4812 for (i = 0; i < RARRAY_LEN(ary); i++) {
4813 v = RARRAY_AREF(ary, i);
4814 if (result == Qundef || OPTIMIZED_CMP(v, result, cmp_opt) < 0) {
4815 result = v;
4816 }
4817 }
4818 }
4819 if (result == Qundef) return Qnil;
4820 return result;
4821 }
4822
4823 static int
push_value(st_data_t key,st_data_t val,st_data_t ary)4824 push_value(st_data_t key, st_data_t val, st_data_t ary)
4825 {
4826 rb_ary_push((VALUE)ary, (VALUE)val);
4827 return ST_CONTINUE;
4828 }
4829
4830 /*
4831 * call-seq:
4832 * ary.uniq! -> ary or nil
4833 * ary.uniq! {|item| ...} -> ary or nil
4834 *
4835 * Removes duplicate elements from +self+.
4836 *
4837 * If a block is given, it will use the return value of the block for
4838 * comparison.
4839 *
4840 * It compares values using their #hash and #eql? methods for efficiency.
4841 *
4842 * +self+ is traversed in order, and the first occurrence is kept.
4843 *
4844 * Returns +nil+ if no changes are made (that is, no duplicates are found).
4845 *
4846 * a = [ "a", "a", "b", "b", "c" ]
4847 * a.uniq! # => ["a", "b", "c"]
4848 *
4849 * b = [ "a", "b", "c" ]
4850 * b.uniq! # => nil
4851 *
4852 * c = [["student","sam"], ["student","george"], ["teacher","matz"]]
4853 * c.uniq! {|s| s.first} # => [["student", "sam"], ["teacher", "matz"]]
4854 *
4855 */
4856
4857 static VALUE
rb_ary_uniq_bang(VALUE ary)4858 rb_ary_uniq_bang(VALUE ary)
4859 {
4860 VALUE hash;
4861 long hash_size;
4862
4863 rb_ary_modify_check(ary);
4864 if (RARRAY_LEN(ary) <= 1)
4865 return Qnil;
4866 if (rb_block_given_p())
4867 hash = ary_make_hash_by(ary);
4868 else
4869 hash = ary_make_hash(ary);
4870
4871 hash_size = RHASH_SIZE(hash);
4872 if (RARRAY_LEN(ary) == hash_size) {
4873 return Qnil;
4874 }
4875 rb_ary_modify_check(ary);
4876 ARY_SET_LEN(ary, 0);
4877 if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
4878 rb_ary_unshare(ary);
4879 FL_SET_EMBED(ary);
4880 }
4881 ary_resize_capa(ary, hash_size);
4882 rb_hash_foreach(hash, push_value, ary);
4883 ary_recycle_hash(hash);
4884
4885 return ary;
4886 }
4887
4888 /*
4889 * call-seq:
4890 * ary.uniq -> new_ary
4891 * ary.uniq {|item| ...} -> new_ary
4892 *
4893 * Returns a new array by removing duplicate values in +self+.
4894 *
4895 * If a block is given, it will use the return value of the block for comparison.
4896 *
4897 * It compares values using their #hash and #eql? methods for efficiency.
4898 *
4899 * +self+ is traversed in order, and the first occurrence is kept.
4900 *
4901 * a = [ "a", "a", "b", "b", "c" ]
4902 * a.uniq # => ["a", "b", "c"]
4903 *
4904 * b = [["student","sam"], ["student","george"], ["teacher","matz"]]
4905 * b.uniq {|s| s.first} # => [["student", "sam"], ["teacher", "matz"]]
4906 *
4907 */
4908
4909 static VALUE
rb_ary_uniq(VALUE ary)4910 rb_ary_uniq(VALUE ary)
4911 {
4912 VALUE hash, uniq;
4913
4914 if (RARRAY_LEN(ary) <= 1)
4915 return rb_ary_dup(ary);
4916 if (rb_block_given_p()) {
4917 hash = ary_make_hash_by(ary);
4918 uniq = rb_hash_values(hash);
4919 }
4920 else {
4921 hash = ary_make_hash(ary);
4922 uniq = rb_hash_values(hash);
4923 }
4924 RBASIC_SET_CLASS(uniq, rb_obj_class(ary));
4925 ary_recycle_hash(hash);
4926
4927 return uniq;
4928 }
4929
4930 /*
4931 * call-seq:
4932 * ary.compact! -> ary or nil
4933 *
4934 * Removes +nil+ elements from the array.
4935 *
4936 * Returns +nil+ if no changes were made, otherwise returns the array.
4937 *
4938 * [ "a", nil, "b", nil, "c" ].compact! #=> [ "a", "b", "c" ]
4939 * [ "a", "b", "c" ].compact! #=> nil
4940 */
4941
4942 static VALUE
rb_ary_compact_bang(VALUE ary)4943 rb_ary_compact_bang(VALUE ary)
4944 {
4945 VALUE *p, *t, *end;
4946 long n;
4947
4948 rb_ary_modify(ary);
4949 p = t = (VALUE *)RARRAY_CONST_PTR_TRANSIENT(ary); /* WB: no new reference */
4950 end = p + RARRAY_LEN(ary);
4951
4952 while (t < end) {
4953 if (NIL_P(*t)) t++;
4954 else *p++ = *t++;
4955 }
4956 n = p - RARRAY_CONST_PTR_TRANSIENT(ary);
4957 if (RARRAY_LEN(ary) == n) {
4958 return Qnil;
4959 }
4960 ary_resize_smaller(ary, n);
4961
4962 return ary;
4963 }
4964
4965 /*
4966 * call-seq:
4967 * ary.compact -> new_ary
4968 *
4969 * Returns a copy of +self+ with all +nil+ elements removed.
4970 *
4971 * [ "a", nil, "b", nil, "c", nil ].compact
4972 * #=> [ "a", "b", "c" ]
4973 */
4974
4975 static VALUE
rb_ary_compact(VALUE ary)4976 rb_ary_compact(VALUE ary)
4977 {
4978 ary = rb_ary_dup(ary);
4979 rb_ary_compact_bang(ary);
4980 return ary;
4981 }
4982
4983 /*
4984 * call-seq:
4985 * ary.count -> int
4986 * ary.count(obj) -> int
4987 * ary.count {|item| block} -> int
4988 *
4989 * Returns the number of elements.
4990 *
4991 * If an argument is given, counts the number of elements which equal +obj+
4992 * using <code>==</code>.
4993 *
4994 * If a block is given, counts the number of elements for which the block
4995 * returns a true value.
4996 *
4997 * ary = [1, 2, 4, 2]
4998 * ary.count #=> 4
4999 * ary.count(2) #=> 2
5000 * ary.count {|x| x%2 == 0} #=> 3
5001 *
5002 */
5003
5004 static VALUE
rb_ary_count(int argc,VALUE * argv,VALUE ary)5005 rb_ary_count(int argc, VALUE *argv, VALUE ary)
5006 {
5007 long i, n = 0;
5008
5009 if (rb_check_arity(argc, 0, 1) == 0) {
5010 VALUE v;
5011
5012 if (!rb_block_given_p())
5013 return LONG2NUM(RARRAY_LEN(ary));
5014
5015 for (i = 0; i < RARRAY_LEN(ary); i++) {
5016 v = RARRAY_AREF(ary, i);
5017 if (RTEST(rb_yield(v))) n++;
5018 }
5019 }
5020 else {
5021 VALUE obj = argv[0];
5022
5023 if (rb_block_given_p()) {
5024 rb_warn("given block not used");
5025 }
5026 for (i = 0; i < RARRAY_LEN(ary); i++) {
5027 if (rb_equal(RARRAY_AREF(ary, i), obj)) n++;
5028 }
5029 }
5030
5031 return LONG2NUM(n);
5032 }
5033
5034 static VALUE
flatten(VALUE ary,int level,int * modified)5035 flatten(VALUE ary, int level, int *modified)
5036 {
5037 long i = 0;
5038 VALUE stack, result, tmp, elt;
5039 st_table *memo;
5040 st_data_t id;
5041
5042 stack = ary_new(0, ARY_DEFAULT_SIZE);
5043 result = ary_new(0, RARRAY_LEN(ary));
5044 memo = st_init_numtable();
5045 st_insert(memo, (st_data_t)ary, (st_data_t)Qtrue);
5046 *modified = 0;
5047
5048 while (1) {
5049 while (i < RARRAY_LEN(ary)) {
5050 elt = RARRAY_AREF(ary, i++);
5051 if (level >= 0 && RARRAY_LEN(stack) / 2 >= level) {
5052 rb_ary_push(result, elt);
5053 continue;
5054 }
5055 tmp = rb_check_array_type(elt);
5056 if (RBASIC(result)->klass) {
5057 rb_raise(rb_eRuntimeError, "flatten reentered");
5058 }
5059 if (NIL_P(tmp)) {
5060 rb_ary_push(result, elt);
5061 }
5062 else {
5063 *modified = 1;
5064 id = (st_data_t)tmp;
5065 if (st_lookup(memo, id, 0)) {
5066 st_free_table(memo);
5067 rb_raise(rb_eArgError, "tried to flatten recursive array");
5068 }
5069 st_insert(memo, id, (st_data_t)Qtrue);
5070 rb_ary_push(stack, ary);
5071 rb_ary_push(stack, LONG2NUM(i));
5072 ary = tmp;
5073 i = 0;
5074 }
5075 }
5076 if (RARRAY_LEN(stack) == 0) {
5077 break;
5078 }
5079 id = (st_data_t)ary;
5080 st_delete(memo, &id, 0);
5081 tmp = rb_ary_pop(stack);
5082 i = NUM2LONG(tmp);
5083 ary = rb_ary_pop(stack);
5084 }
5085
5086 st_free_table(memo);
5087
5088 RBASIC_SET_CLASS(result, rb_obj_class(ary));
5089 return result;
5090 }
5091
5092 /*
5093 * call-seq:
5094 * ary.flatten! -> ary or nil
5095 * ary.flatten!(level) -> ary or nil
5096 *
5097 * Flattens +self+ in place.
5098 *
5099 * Returns +nil+ if no modifications were made (i.e., the array contains no
5100 * subarrays.)
5101 *
5102 * The optional +level+ argument determines the level of recursion to flatten.
5103 *
5104 * a = [ 1, 2, [3, [4, 5] ] ]
5105 * a.flatten! #=> [1, 2, 3, 4, 5]
5106 * a.flatten! #=> nil
5107 * a #=> [1, 2, 3, 4, 5]
5108 * a = [ 1, 2, [3, [4, 5] ] ]
5109 * a.flatten!(1) #=> [1, 2, 3, [4, 5]]
5110 */
5111
5112 static VALUE
rb_ary_flatten_bang(int argc,VALUE * argv,VALUE ary)5113 rb_ary_flatten_bang(int argc, VALUE *argv, VALUE ary)
5114 {
5115 int mod = 0, level = -1;
5116 VALUE result, lv;
5117
5118 lv = (rb_check_arity(argc, 0, 1) ? argv[0] : Qnil);
5119 rb_ary_modify_check(ary);
5120 if (!NIL_P(lv)) level = NUM2INT(lv);
5121 if (level == 0) return Qnil;
5122
5123 result = flatten(ary, level, &mod);
5124 if (mod == 0) {
5125 ary_discard(result);
5126 return Qnil;
5127 }
5128 if (!(mod = ARY_EMBED_P(result))) rb_obj_freeze(result);
5129 rb_ary_replace(ary, result);
5130 if (mod) ARY_SET_EMBED_LEN(result, 0);
5131
5132 return ary;
5133 }
5134
5135 /*
5136 * call-seq:
5137 * ary.flatten -> new_ary
5138 * ary.flatten(level) -> new_ary
5139 *
5140 * Returns a new array that is a one-dimensional flattening of +self+
5141 * (recursively).
5142 *
5143 * That is, for every element that is an array, extract its elements into
5144 * the new array.
5145 *
5146 * The optional +level+ argument determines the level of recursion to
5147 * flatten.
5148 *
5149 * s = [ 1, 2, 3 ] #=> [1, 2, 3]
5150 * t = [ 4, 5, 6, [7, 8] ] #=> [4, 5, 6, [7, 8]]
5151 * a = [ s, t, 9, 10 ] #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
5152 * a.flatten #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
5153 * a = [ 1, 2, [3, [4, 5] ] ]
5154 * a.flatten(1) #=> [1, 2, 3, [4, 5]]
5155 */
5156
5157 static VALUE
rb_ary_flatten(int argc,VALUE * argv,VALUE ary)5158 rb_ary_flatten(int argc, VALUE *argv, VALUE ary)
5159 {
5160 int mod = 0, level = -1;
5161 VALUE result;
5162
5163 if (rb_check_arity(argc, 0, 1) && !NIL_P(argv[0])) {
5164 level = NUM2INT(argv[0]);
5165 if (level == 0) return ary_make_shared_copy(ary);
5166 }
5167
5168 result = flatten(ary, level, &mod);
5169 OBJ_INFECT(result, ary);
5170
5171 return result;
5172 }
5173
5174 #define OPTHASH_GIVEN_P(opts) \
5175 (argc > 0 && !NIL_P((opts) = rb_check_hash_type(argv[argc-1])) && (--argc, 1))
5176 static ID id_random;
5177
5178 #define RAND_UPTO(max) (long)rb_random_ulong_limited((randgen), (max)-1)
5179
5180 /*
5181 * call-seq:
5182 * ary.shuffle! -> ary
5183 * ary.shuffle!(random: rng) -> ary
5184 *
5185 * Shuffles elements in +self+ in place.
5186 *
5187 * a = [ 1, 2, 3 ] #=> [1, 2, 3]
5188 * a.shuffle! #=> [2, 3, 1]
5189 * a #=> [2, 3, 1]
5190 *
5191 * The optional +rng+ argument will be used as the random number generator.
5192 *
5193 * a.shuffle!(random: Random.new(1)) #=> [1, 3, 2]
5194 */
5195
5196 static VALUE
rb_ary_shuffle_bang(int argc,VALUE * argv,VALUE ary)5197 rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
5198 {
5199 VALUE opts, randgen = rb_cRandom;
5200 long i, len;
5201
5202 if (OPTHASH_GIVEN_P(opts)) {
5203 VALUE rnd;
5204 ID keyword_ids[1];
5205
5206 keyword_ids[0] = id_random;
5207 rb_get_kwargs(opts, keyword_ids, 0, 1, &rnd);
5208 if (rnd != Qundef) {
5209 randgen = rnd;
5210 }
5211 }
5212 rb_check_arity(argc, 0, 0);
5213 rb_ary_modify(ary);
5214 i = len = RARRAY_LEN(ary);
5215 RARRAY_PTR_USE(ary, ptr, {
5216 while (i) {
5217 long j = RAND_UPTO(i);
5218 VALUE tmp;
5219 if (len != RARRAY_LEN(ary) || ptr != RARRAY_CONST_PTR_TRANSIENT(ary)) {
5220 rb_raise(rb_eRuntimeError, "modified during shuffle");
5221 }
5222 tmp = ptr[--i];
5223 ptr[i] = ptr[j];
5224 ptr[j] = tmp;
5225 }
5226 }); /* WB: no new reference */
5227 return ary;
5228 }
5229
5230
5231 /*
5232 * call-seq:
5233 * ary.shuffle -> new_ary
5234 * ary.shuffle(random: rng) -> new_ary
5235 *
5236 * Returns a new array with elements of +self+ shuffled.
5237 *
5238 * a = [ 1, 2, 3 ] #=> [1, 2, 3]
5239 * a.shuffle #=> [2, 3, 1]
5240 * a #=> [1, 2, 3]
5241 *
5242 * The optional +rng+ argument will be used as the random number generator.
5243 *
5244 * a.shuffle(random: Random.new(1)) #=> [1, 3, 2]
5245 */
5246
5247 static VALUE
rb_ary_shuffle(int argc,VALUE * argv,VALUE ary)5248 rb_ary_shuffle(int argc, VALUE *argv, VALUE ary)
5249 {
5250 ary = rb_ary_dup(ary);
5251 rb_ary_shuffle_bang(argc, argv, ary);
5252 return ary;
5253 }
5254
5255
5256 /*
5257 * call-seq:
5258 * ary.sample -> obj
5259 * ary.sample(random: rng) -> obj
5260 * ary.sample(n) -> new_ary
5261 * ary.sample(n, random: rng) -> new_ary
5262 *
5263 * Choose a random element or +n+ random elements from the array.
5264 *
5265 * The elements are chosen by using random and unique indices into the array
5266 * in order to ensure that an element doesn't repeat itself unless the array
5267 * already contained duplicate elements.
5268 *
5269 * If the array is empty the first form returns +nil+ and the second form
5270 * returns an empty array.
5271 *
5272 * a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
5273 * a.sample #=> 7
5274 * a.sample(4) #=> [6, 4, 2, 5]
5275 *
5276 * The optional +rng+ argument will be used as the random number generator.
5277 *
5278 * a.sample(random: Random.new(1)) #=> 6
5279 * a.sample(4, random: Random.new(1)) #=> [6, 10, 9, 2]
5280 */
5281
5282
5283 static VALUE
rb_ary_sample(int argc,VALUE * argv,VALUE ary)5284 rb_ary_sample(int argc, VALUE *argv, VALUE ary)
5285 {
5286 VALUE nv, result;
5287 VALUE opts, randgen = rb_cRandom;
5288 long n, len, i, j, k, idx[10];
5289 long rnds[numberof(idx)];
5290 long memo_threshold;
5291
5292 if (OPTHASH_GIVEN_P(opts)) {
5293 VALUE rnd;
5294 ID keyword_ids[1];
5295
5296 keyword_ids[0] = id_random;
5297 rb_get_kwargs(opts, keyword_ids, 0, 1, &rnd);
5298 if (rnd != Qundef) {
5299 randgen = rnd;
5300 }
5301 }
5302 len = RARRAY_LEN(ary);
5303 if (rb_check_arity(argc, 0, 1) == 0) {
5304 if (len < 2)
5305 i = 0;
5306 else
5307 i = RAND_UPTO(len);
5308
5309 return rb_ary_elt(ary, i);
5310 }
5311 nv = argv[0];
5312 n = NUM2LONG(nv);
5313 if (n < 0) rb_raise(rb_eArgError, "negative sample number");
5314 if (n > len) n = len;
5315 if (n <= numberof(idx)) {
5316 for (i = 0; i < n; ++i) {
5317 rnds[i] = RAND_UPTO(len - i);
5318 }
5319 }
5320 k = len;
5321 len = RARRAY_LEN(ary);
5322 if (len < k && n <= numberof(idx)) {
5323 for (i = 0; i < n; ++i) {
5324 if (rnds[i] >= len) return rb_ary_new_capa(0);
5325 }
5326 }
5327 if (n > len) n = len;
5328 switch (n) {
5329 case 0:
5330 return rb_ary_new_capa(0);
5331 case 1:
5332 i = rnds[0];
5333 return rb_ary_new_from_values(1, &RARRAY_AREF(ary, i));
5334 case 2:
5335 i = rnds[0];
5336 j = rnds[1];
5337 if (j >= i) j++;
5338 return rb_ary_new_from_args(2, RARRAY_AREF(ary, i), RARRAY_AREF(ary, j));
5339 case 3:
5340 i = rnds[0];
5341 j = rnds[1];
5342 k = rnds[2];
5343 {
5344 long l = j, g = i;
5345 if (j >= i) l = i, g = ++j;
5346 if (k >= l && (++k >= g)) ++k;
5347 }
5348 return rb_ary_new_from_args(3, RARRAY_AREF(ary, i), RARRAY_AREF(ary, j), RARRAY_AREF(ary, k));
5349 }
5350 memo_threshold =
5351 len < 2560 ? len / 128 :
5352 len < 5120 ? len / 64 :
5353 len < 10240 ? len / 32 :
5354 len / 16;
5355 if (n <= numberof(idx)) {
5356 long sorted[numberof(idx)];
5357 sorted[0] = idx[0] = rnds[0];
5358 for (i=1; i<n; i++) {
5359 k = rnds[i];
5360 for (j = 0; j < i; ++j) {
5361 if (k < sorted[j]) break;
5362 ++k;
5363 }
5364 memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
5365 sorted[j] = idx[i] = k;
5366 }
5367 result = rb_ary_new_capa(n);
5368 RARRAY_PTR_USE_TRANSIENT(result, ptr_result, {
5369 for (i=0; i<n; i++) {
5370 ptr_result[i] = RARRAY_AREF(ary, idx[i]);
5371 }
5372 });
5373 }
5374 else if (n <= memo_threshold / 2) {
5375 long max_idx = 0;
5376 #undef RUBY_UNTYPED_DATA_WARNING
5377 #define RUBY_UNTYPED_DATA_WARNING 0
5378 VALUE vmemo = Data_Wrap_Struct(0, 0, st_free_table, 0);
5379 st_table *memo = st_init_numtable_with_size(n);
5380 DATA_PTR(vmemo) = memo;
5381 result = rb_ary_new_capa(n);
5382 RARRAY_PTR_USE(result, ptr_result, {
5383 for (i=0; i<n; i++) {
5384 long r = RAND_UPTO(len-i) + i;
5385 ptr_result[i] = r;
5386 if (r > max_idx) max_idx = r;
5387 }
5388 len = RARRAY_LEN(ary);
5389 if (len <= max_idx) n = 0;
5390 else if (n > len) n = len;
5391 RARRAY_PTR_USE_TRANSIENT(ary, ptr_ary, {
5392 for (i=0; i<n; i++) {
5393 long j2 = j = ptr_result[i];
5394 long i2 = i;
5395 st_data_t value;
5396 if (st_lookup(memo, (st_data_t)i, &value)) i2 = (long)value;
5397 if (st_lookup(memo, (st_data_t)j, &value)) j2 = (long)value;
5398 st_insert(memo, (st_data_t)j, (st_data_t)i2);
5399 ptr_result[i] = ptr_ary[j2];
5400 }
5401 });
5402 });
5403 DATA_PTR(vmemo) = 0;
5404 st_free_table(memo);
5405 }
5406 else {
5407 result = rb_ary_dup(ary);
5408 RBASIC_CLEAR_CLASS(result);
5409 RB_GC_GUARD(ary);
5410 RARRAY_PTR_USE(result, ptr_result, {
5411 for (i=0; i<n; i++) {
5412 j = RAND_UPTO(len-i) + i;
5413 nv = ptr_result[j];
5414 ptr_result[j] = ptr_result[i];
5415 ptr_result[i] = nv;
5416 }
5417 });
5418 RBASIC_SET_CLASS_RAW(result, rb_cArray);
5419 }
5420 ARY_SET_LEN(result, n);
5421
5422 return result;
5423 }
5424
5425 static VALUE
rb_ary_cycle_size(VALUE self,VALUE args,VALUE eobj)5426 rb_ary_cycle_size(VALUE self, VALUE args, VALUE eobj)
5427 {
5428 long mul;
5429 VALUE n = Qnil;
5430 if (args && (RARRAY_LEN(args) > 0)) {
5431 n = RARRAY_AREF(args, 0);
5432 }
5433 if (RARRAY_LEN(self) == 0) return INT2FIX(0);
5434 if (n == Qnil) return DBL2NUM(HUGE_VAL);
5435 mul = NUM2LONG(n);
5436 if (mul <= 0) return INT2FIX(0);
5437 n = LONG2FIX(mul);
5438 return rb_fix_mul_fix(rb_ary_length(self), n);
5439 }
5440
5441 /*
5442 * call-seq:
5443 * ary.cycle(n=nil) {|obj| block} -> nil
5444 * ary.cycle(n=nil) -> Enumerator
5445 *
5446 * Calls the given block for each element +n+ times or forever if +nil+ is
5447 * given.
5448 *
5449 * Does nothing if a non-positive number is given or the array is empty.
5450 *
5451 * Returns +nil+ if the loop has finished without getting interrupted.
5452 *
5453 * If no block is given, an Enumerator is returned instead.
5454 *
5455 * a = ["a", "b", "c"]
5456 * a.cycle {|x| puts x} # print, a, b, c, a, b, c,.. forever.
5457 * a.cycle(2) {|x| puts x} # print, a, b, c, a, b, c.
5458 *
5459 */
5460
5461 static VALUE
rb_ary_cycle(int argc,VALUE * argv,VALUE ary)5462 rb_ary_cycle(int argc, VALUE *argv, VALUE ary)
5463 {
5464 long n, i;
5465
5466 rb_check_arity(argc, 0, 1);
5467
5468 RETURN_SIZED_ENUMERATOR(ary, argc, argv, rb_ary_cycle_size);
5469 if (argc == 0 || NIL_P(argv[0])) {
5470 n = -1;
5471 }
5472 else {
5473 n = NUM2LONG(argv[0]);
5474 if (n <= 0) return Qnil;
5475 }
5476
5477 while (RARRAY_LEN(ary) > 0 && (n < 0 || 0 < n--)) {
5478 for (i=0; i<RARRAY_LEN(ary); i++) {
5479 rb_yield(RARRAY_AREF(ary, i));
5480 }
5481 }
5482 return Qnil;
5483 }
5484
5485 #define tmpary(n) rb_ary_tmp_new(n)
5486 #define tmpary_discard(a) (ary_discard(a), RBASIC_SET_CLASS_RAW(a, rb_cArray))
5487
5488 /*
5489 * Build a ruby array of the corresponding values and yield it to the
5490 * associated block.
5491 * Return the class of +values+ for reentry check.
5492 */
5493 static int
yield_indexed_values(const VALUE values,const long r,const long * const p)5494 yield_indexed_values(const VALUE values, const long r, const long *const p)
5495 {
5496 const VALUE result = rb_ary_new2(r);
5497 long i;
5498
5499 for (i = 0; i < r; i++) RARRAY_ASET(result, i, RARRAY_AREF(values, p[i]));
5500 ARY_SET_LEN(result, r);
5501 rb_yield(result);
5502 return !RBASIC(values)->klass;
5503 }
5504
5505 /*
5506 * Compute permutations of +r+ elements of the set <code>[0..n-1]</code>.
5507 *
5508 * When we have a complete permutation of array indices, copy the values
5509 * at those indices into a new array and yield that array.
5510 *
5511 * n: the size of the set
5512 * r: the number of elements in each permutation
5513 * p: the array (of size r) that we're filling in
5514 * used: an array of booleans: whether a given index is already used
5515 * values: the Ruby array that holds the actual values to permute
5516 */
5517 static void
permute0(const long n,const long r,long * const p,char * const used,const VALUE values)5518 permute0(const long n, const long r, long *const p, char *const used, const VALUE values)
5519 {
5520 long i = 0, index = 0;
5521
5522 for (;;) {
5523 const char *const unused = memchr(&used[i], 0, n-i);
5524 if (!unused) {
5525 if (!index) break;
5526 i = p[--index]; /* pop index */
5527 used[i++] = 0; /* index unused */
5528 }
5529 else {
5530 i = unused - used;
5531 p[index] = i;
5532 used[i] = 1; /* mark index used */
5533 ++index;
5534 if (index < r-1) { /* if not done yet */
5535 p[index] = i = 0;
5536 continue;
5537 }
5538 for (i = 0; i < n; ++i) {
5539 if (used[i]) continue;
5540 p[index] = i;
5541 if (!yield_indexed_values(values, r, p)) {
5542 rb_raise(rb_eRuntimeError, "permute reentered");
5543 }
5544 }
5545 i = p[--index]; /* pop index */
5546 used[i] = 0; /* index unused */
5547 p[index] = ++i;
5548 }
5549 }
5550 }
5551
5552 /*
5553 * Returns the product of from, from-1, ..., from - how_many + 1.
5554 * http://en.wikipedia.org/wiki/Pochhammer_symbol
5555 */
5556 static VALUE
descending_factorial(long from,long how_many)5557 descending_factorial(long from, long how_many)
5558 {
5559 VALUE cnt;
5560 if (how_many > 0) {
5561 cnt = LONG2FIX(from);
5562 while (--how_many > 0) {
5563 long v = --from;
5564 cnt = rb_int_mul(cnt, LONG2FIX(v));
5565 }
5566 }
5567 else {
5568 cnt = LONG2FIX(how_many == 0);
5569 }
5570 return cnt;
5571 }
5572
5573 static VALUE
binomial_coefficient(long comb,long size)5574 binomial_coefficient(long comb, long size)
5575 {
5576 VALUE r;
5577 long i;
5578 if (comb > size-comb) {
5579 comb = size-comb;
5580 }
5581 if (comb < 0) {
5582 return LONG2FIX(0);
5583 }
5584 else if (comb == 0) {
5585 return LONG2FIX(1);
5586 }
5587 r = LONG2FIX(size);
5588 for (i = 1; i < comb; ++i) {
5589 r = rb_int_mul(r, LONG2FIX(size - i));
5590 r = rb_int_idiv(r, LONG2FIX(i + 1));
5591 }
5592 return r;
5593 }
5594
5595 static VALUE
rb_ary_permutation_size(VALUE ary,VALUE args,VALUE eobj)5596 rb_ary_permutation_size(VALUE ary, VALUE args, VALUE eobj)
5597 {
5598 long n = RARRAY_LEN(ary);
5599 long k = (args && (RARRAY_LEN(args) > 0)) ? NUM2LONG(RARRAY_AREF(args, 0)) : n;
5600
5601 return descending_factorial(n, k);
5602 }
5603
5604 /*
5605 * call-seq:
5606 * ary.permutation {|p| block} -> ary
5607 * ary.permutation -> Enumerator
5608 * ary.permutation(n) {|p| block} -> ary
5609 * ary.permutation(n) -> Enumerator
5610 *
5611 * When invoked with a block, yield all permutations of length +n+ of the
5612 * elements of the array, then return the array itself.
5613 *
5614 * If +n+ is not specified, yield all permutations of all elements.
5615 *
5616 * The implementation makes no guarantees about the order in which the
5617 * permutations are yielded.
5618 *
5619 * If no block is given, an Enumerator is returned instead.
5620 *
5621 * Examples:
5622 *
5623 * a = [1, 2, 3]
5624 * a.permutation.to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
5625 * a.permutation(1).to_a #=> [[1],[2],[3]]
5626 * a.permutation(2).to_a #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
5627 * a.permutation(3).to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
5628 * a.permutation(0).to_a #=> [[]] # one permutation of length 0
5629 * a.permutation(4).to_a #=> [] # no permutations of length 4
5630 */
5631
5632 static VALUE
rb_ary_permutation(int argc,VALUE * argv,VALUE ary)5633 rb_ary_permutation(int argc, VALUE *argv, VALUE ary)
5634 {
5635 long r, n, i;
5636
5637 n = RARRAY_LEN(ary); /* Array length */
5638 RETURN_SIZED_ENUMERATOR(ary, argc, argv, rb_ary_permutation_size); /* Return enumerator if no block */
5639 r = n;
5640 if (rb_check_arity(argc, 0, 1) && !NIL_P(argv[0]))
5641 r = NUM2LONG(argv[0]); /* Permutation size from argument */
5642
5643 if (r < 0 || n < r) {
5644 /* no permutations: yield nothing */
5645 }
5646 else if (r == 0) { /* exactly one permutation: the zero-length array */
5647 rb_yield(rb_ary_new2(0));
5648 }
5649 else if (r == 1) { /* this is a special, easy case */
5650 for (i = 0; i < RARRAY_LEN(ary); i++) {
5651 rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
5652 }
5653 }
5654 else { /* this is the general case */
5655 volatile VALUE t0;
5656 long *p = ALLOCV_N(long, t0, r+roomof(n, sizeof(long)));
5657 char *used = (char*)(p + r);
5658 VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
5659 RBASIC_CLEAR_CLASS(ary0);
5660
5661 MEMZERO(used, char, n); /* initialize array */
5662
5663 permute0(n, r, p, used, ary0); /* compute and yield permutations */
5664 ALLOCV_END(t0);
5665 RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
5666 }
5667 return ary;
5668 }
5669
5670 static void
combinate0(const long len,const long n,long * const stack,const VALUE values)5671 combinate0(const long len, const long n, long *const stack, const VALUE values)
5672 {
5673 long lev = 0;
5674
5675 MEMZERO(stack+1, long, n);
5676 stack[0] = -1;
5677 for (;;) {
5678 for (lev++; lev < n; lev++) {
5679 stack[lev+1] = stack[lev]+1;
5680 }
5681 if (!yield_indexed_values(values, n, stack+1)) {
5682 rb_raise(rb_eRuntimeError, "combination reentered");
5683 }
5684 do {
5685 if (lev == 0) return;
5686 stack[lev--]++;
5687 } while (stack[lev+1]+n == len+lev+1);
5688 }
5689 }
5690
5691 static VALUE
rb_ary_combination_size(VALUE ary,VALUE args,VALUE eobj)5692 rb_ary_combination_size(VALUE ary, VALUE args, VALUE eobj)
5693 {
5694 long n = RARRAY_LEN(ary);
5695 long k = NUM2LONG(RARRAY_AREF(args, 0));
5696
5697 return binomial_coefficient(k, n);
5698 }
5699
5700 /*
5701 * call-seq:
5702 * ary.combination(n) {|c| block} -> ary
5703 * ary.combination(n) -> Enumerator
5704 *
5705 * When invoked with a block, yields all combinations of length +n+ of elements
5706 * from the array and then returns the array itself.
5707 *
5708 * The implementation makes no guarantees about the order in which the
5709 * combinations are yielded.
5710 *
5711 * If no block is given, an Enumerator is returned instead.
5712 *
5713 * Examples:
5714 *
5715 * a = [1, 2, 3, 4]
5716 * a.combination(1).to_a #=> [[1],[2],[3],[4]]
5717 * a.combination(2).to_a #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
5718 * a.combination(3).to_a #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
5719 * a.combination(4).to_a #=> [[1,2,3,4]]
5720 * a.combination(0).to_a #=> [[]] # one combination of length 0
5721 * a.combination(5).to_a #=> [] # no combinations of length 5
5722 *
5723 */
5724
5725 static VALUE
rb_ary_combination(VALUE ary,VALUE num)5726 rb_ary_combination(VALUE ary, VALUE num)
5727 {
5728 long i, n, len;
5729
5730 n = NUM2LONG(num);
5731 RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_combination_size);
5732 len = RARRAY_LEN(ary);
5733 if (n < 0 || len < n) {
5734 /* yield nothing */
5735 }
5736 else if (n == 0) {
5737 rb_yield(rb_ary_new2(0));
5738 }
5739 else if (n == 1) {
5740 for (i = 0; i < RARRAY_LEN(ary); i++) {
5741 rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
5742 }
5743 }
5744 else {
5745 VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
5746 volatile VALUE t0;
5747 long *stack = ALLOCV_N(long, t0, n+1);
5748
5749 RBASIC_CLEAR_CLASS(ary0);
5750 combinate0(len, n, stack, ary0);
5751 ALLOCV_END(t0);
5752 RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
5753 }
5754 return ary;
5755 }
5756
5757 /*
5758 * Compute repeated permutations of +r+ elements of the set
5759 * <code>[0..n-1]</code>.
5760 *
5761 * When we have a complete repeated permutation of array indices, copy the
5762 * values at those indices into a new array and yield that array.
5763 *
5764 * n: the size of the set
5765 * r: the number of elements in each permutation
5766 * p: the array (of size r) that we're filling in
5767 * values: the Ruby array that holds the actual values to permute
5768 */
5769 static void
rpermute0(const long n,const long r,long * const p,const VALUE values)5770 rpermute0(const long n, const long r, long *const p, const VALUE values)
5771 {
5772 long i = 0, index = 0;
5773
5774 p[index] = i;
5775 for (;;) {
5776 if (++index < r-1) {
5777 p[index] = i = 0;
5778 continue;
5779 }
5780 for (i = 0; i < n; ++i) {
5781 p[index] = i;
5782 if (!yield_indexed_values(values, r, p)) {
5783 rb_raise(rb_eRuntimeError, "repeated permute reentered");
5784 }
5785 }
5786 do {
5787 if (index <= 0) return;
5788 } while ((i = ++p[--index]) >= n);
5789 }
5790 }
5791
5792 static VALUE
rb_ary_repeated_permutation_size(VALUE ary,VALUE args,VALUE eobj)5793 rb_ary_repeated_permutation_size(VALUE ary, VALUE args, VALUE eobj)
5794 {
5795 long n = RARRAY_LEN(ary);
5796 long k = NUM2LONG(RARRAY_AREF(args, 0));
5797
5798 if (k < 0) {
5799 return LONG2FIX(0);
5800 }
5801 if (n <= 0) {
5802 return LONG2FIX(!k);
5803 }
5804 return rb_int_positive_pow(n, (unsigned long)k);
5805 }
5806
5807 /*
5808 * call-seq:
5809 * ary.repeated_permutation(n) {|p| block} -> ary
5810 * ary.repeated_permutation(n) -> Enumerator
5811 *
5812 * When invoked with a block, yield all repeated permutations of length +n+ of
5813 * the elements of the array, then return the array itself.
5814 *
5815 * The implementation makes no guarantees about the order in which the repeated
5816 * permutations are yielded.
5817 *
5818 * If no block is given, an Enumerator is returned instead.
5819 *
5820 * Examples:
5821 *
5822 * a = [1, 2]
5823 * a.repeated_permutation(1).to_a #=> [[1], [2]]
5824 * a.repeated_permutation(2).to_a #=> [[1,1],[1,2],[2,1],[2,2]]
5825 * a.repeated_permutation(3).to_a #=> [[1,1,1],[1,1,2],[1,2,1],[1,2,2],
5826 * # [2,1,1],[2,1,2],[2,2,1],[2,2,2]]
5827 * a.repeated_permutation(0).to_a #=> [[]] # one permutation of length 0
5828 */
5829
5830 static VALUE
rb_ary_repeated_permutation(VALUE ary,VALUE num)5831 rb_ary_repeated_permutation(VALUE ary, VALUE num)
5832 {
5833 long r, n, i;
5834
5835 n = RARRAY_LEN(ary); /* Array length */
5836 RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_repeated_permutation_size); /* Return Enumerator if no block */
5837 r = NUM2LONG(num); /* Permutation size from argument */
5838
5839 if (r < 0) {
5840 /* no permutations: yield nothing */
5841 }
5842 else if (r == 0) { /* exactly one permutation: the zero-length array */
5843 rb_yield(rb_ary_new2(0));
5844 }
5845 else if (r == 1) { /* this is a special, easy case */
5846 for (i = 0; i < RARRAY_LEN(ary); i++) {
5847 rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
5848 }
5849 }
5850 else { /* this is the general case */
5851 volatile VALUE t0;
5852 long *p = ALLOCV_N(long, t0, r);
5853 VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
5854 RBASIC_CLEAR_CLASS(ary0);
5855
5856 rpermute0(n, r, p, ary0); /* compute and yield repeated permutations */
5857 ALLOCV_END(t0);
5858 RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
5859 }
5860 return ary;
5861 }
5862
5863 static void
rcombinate0(const long n,const long r,long * const p,const long rest,const VALUE values)5864 rcombinate0(const long n, const long r, long *const p, const long rest, const VALUE values)
5865 {
5866 long i = 0, index = 0;
5867
5868 p[index] = i;
5869 for (;;) {
5870 if (++index < r-1) {
5871 p[index] = i;
5872 continue;
5873 }
5874 for (; i < n; ++i) {
5875 p[index] = i;
5876 if (!yield_indexed_values(values, r, p)) {
5877 rb_raise(rb_eRuntimeError, "repeated combination reentered");
5878 }
5879 }
5880 do {
5881 if (index <= 0) return;
5882 } while ((i = ++p[--index]) >= n);
5883 }
5884 }
5885
5886 static VALUE
rb_ary_repeated_combination_size(VALUE ary,VALUE args,VALUE eobj)5887 rb_ary_repeated_combination_size(VALUE ary, VALUE args, VALUE eobj)
5888 {
5889 long n = RARRAY_LEN(ary);
5890 long k = NUM2LONG(RARRAY_AREF(args, 0));
5891 if (k == 0) {
5892 return LONG2FIX(1);
5893 }
5894 return binomial_coefficient(k, n + k - 1);
5895 }
5896
5897 /*
5898 * call-seq:
5899 * ary.repeated_combination(n) {|c| block} -> ary
5900 * ary.repeated_combination(n) -> Enumerator
5901 *
5902 * When invoked with a block, yields all repeated combinations of length +n+ of
5903 * elements from the array and then returns the array itself.
5904 *
5905 * The implementation makes no guarantees about the order in which the repeated
5906 * combinations are yielded.
5907 *
5908 * If no block is given, an Enumerator is returned instead.
5909 *
5910 * Examples:
5911 *
5912 * a = [1, 2, 3]
5913 * a.repeated_combination(1).to_a #=> [[1], [2], [3]]
5914 * a.repeated_combination(2).to_a #=> [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
5915 * a.repeated_combination(3).to_a #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
5916 * # [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
5917 * a.repeated_combination(4).to_a #=> [[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,2,3],
5918 * # [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
5919 * # [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]]
5920 * a.repeated_combination(0).to_a #=> [[]] # one combination of length 0
5921 *
5922 */
5923
5924 static VALUE
rb_ary_repeated_combination(VALUE ary,VALUE num)5925 rb_ary_repeated_combination(VALUE ary, VALUE num)
5926 {
5927 long n, i, len;
5928
5929 n = NUM2LONG(num); /* Combination size from argument */
5930 RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_repeated_combination_size); /* Return enumerator if no block */
5931 len = RARRAY_LEN(ary);
5932 if (n < 0) {
5933 /* yield nothing */
5934 }
5935 else if (n == 0) {
5936 rb_yield(rb_ary_new2(0));
5937 }
5938 else if (n == 1) {
5939 for (i = 0; i < RARRAY_LEN(ary); i++) {
5940 rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
5941 }
5942 }
5943 else if (len == 0) {
5944 /* yield nothing */
5945 }
5946 else {
5947 volatile VALUE t0;
5948 long *p = ALLOCV_N(long, t0, n);
5949 VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
5950 RBASIC_CLEAR_CLASS(ary0);
5951
5952 rcombinate0(len, n, p, n, ary0); /* compute and yield repeated combinations */
5953 ALLOCV_END(t0);
5954 RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
5955 }
5956 return ary;
5957 }
5958
5959 /*
5960 * call-seq:
5961 * ary.product(other_ary, ...) -> new_ary
5962 * ary.product(other_ary, ...) {|p| block} -> ary
5963 *
5964 * Returns an array of all combinations of elements from all arrays.
5965 *
5966 * The length of the returned array is the product of the length of +self+ and
5967 * the argument arrays.
5968 *
5969 * If given a block, #product will yield all combinations and return +self+
5970 * instead.
5971 *
5972 * [1,2,3].product([4,5]) #=> [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]
5973 * [1,2].product([1,2]) #=> [[1,1],[1,2],[2,1],[2,2]]
5974 * [1,2].product([3,4],[5,6]) #=> [[1,3,5],[1,3,6],[1,4,5],[1,4,6],
5975 * # [2,3,5],[2,3,6],[2,4,5],[2,4,6]]
5976 * [1,2].product() #=> [[1],[2]]
5977 * [1,2].product([]) #=> []
5978 */
5979
5980 static VALUE
rb_ary_product(int argc,VALUE * argv,VALUE ary)5981 rb_ary_product(int argc, VALUE *argv, VALUE ary)
5982 {
5983 int n = argc+1; /* How many arrays we're operating on */
5984 volatile VALUE t0 = tmpary(n);
5985 volatile VALUE t1 = Qundef;
5986 VALUE *arrays = RARRAY_PTR(t0); /* The arrays we're computing the product of */
5987 int *counters = ALLOCV_N(int, t1, n); /* The current position in each one */
5988 VALUE result = Qnil; /* The array we'll be returning, when no block given */
5989 long i,j;
5990 long resultlen = 1;
5991
5992 RBASIC_CLEAR_CLASS(t0);
5993
5994 /* initialize the arrays of arrays */
5995 ARY_SET_LEN(t0, n);
5996 arrays[0] = ary;
5997 for (i = 1; i < n; i++) arrays[i] = Qnil;
5998 for (i = 1; i < n; i++) arrays[i] = to_ary(argv[i-1]);
5999
6000 /* initialize the counters for the arrays */
6001 for (i = 0; i < n; i++) counters[i] = 0;
6002
6003 /* Otherwise, allocate and fill in an array of results */
6004 if (rb_block_given_p()) {
6005 /* Make defensive copies of arrays; exit if any is empty */
6006 for (i = 0; i < n; i++) {
6007 if (RARRAY_LEN(arrays[i]) == 0) goto done;
6008 arrays[i] = ary_make_shared_copy(arrays[i]);
6009 }
6010 }
6011 else {
6012 /* Compute the length of the result array; return [] if any is empty */
6013 for (i = 0; i < n; i++) {
6014 long k = RARRAY_LEN(arrays[i]);
6015 if (k == 0) {
6016 result = rb_ary_new2(0);
6017 goto done;
6018 }
6019 if (MUL_OVERFLOW_LONG_P(resultlen, k))
6020 rb_raise(rb_eRangeError, "too big to product");
6021 resultlen *= k;
6022 }
6023 result = rb_ary_new2(resultlen);
6024 }
6025 for (;;) {
6026 int m;
6027 /* fill in one subarray */
6028 VALUE subarray = rb_ary_new2(n);
6029 for (j = 0; j < n; j++) {
6030 rb_ary_push(subarray, rb_ary_entry(arrays[j], counters[j]));
6031 }
6032
6033 /* put it on the result array */
6034 if (NIL_P(result)) {
6035 FL_SET(t0, FL_USER5);
6036 rb_yield(subarray);
6037 if (! FL_TEST(t0, FL_USER5)) {
6038 rb_raise(rb_eRuntimeError, "product reentered");
6039 }
6040 else {
6041 FL_UNSET(t0, FL_USER5);
6042 }
6043 }
6044 else {
6045 rb_ary_push(result, subarray);
6046 }
6047
6048 /*
6049 * Increment the last counter. If it overflows, reset to 0
6050 * and increment the one before it.
6051 */
6052 m = n-1;
6053 counters[m]++;
6054 while (counters[m] == RARRAY_LEN(arrays[m])) {
6055 counters[m] = 0;
6056 /* If the first counter overflows, we are done */
6057 if (--m < 0) goto done;
6058 counters[m]++;
6059 }
6060 }
6061 done:
6062 tmpary_discard(t0);
6063 ALLOCV_END(t1);
6064
6065 return NIL_P(result) ? ary : result;
6066 }
6067
6068 /*
6069 * call-seq:
6070 * ary.take(n) -> new_ary
6071 *
6072 * Returns first +n+ elements from the array.
6073 *
6074 * If a negative number is given, raises an ArgumentError.
6075 *
6076 * See also Array#drop
6077 *
6078 * a = [1, 2, 3, 4, 5, 0]
6079 * a.take(3) #=> [1, 2, 3]
6080 *
6081 */
6082
6083 static VALUE
rb_ary_take(VALUE obj,VALUE n)6084 rb_ary_take(VALUE obj, VALUE n)
6085 {
6086 long len = NUM2LONG(n);
6087 if (len < 0) {
6088 rb_raise(rb_eArgError, "attempt to take negative size");
6089 }
6090 return rb_ary_subseq(obj, 0, len);
6091 }
6092
6093 /*
6094 * call-seq:
6095 * ary.take_while {|obj| block} -> new_ary
6096 * ary.take_while -> Enumerator
6097 *
6098 * Passes elements to the block until the block returns +nil+ or +false+, then
6099 * stops iterating and returns an array of all prior elements.
6100 *
6101 * If no block is given, an Enumerator is returned instead.
6102 *
6103 * See also Array#drop_while
6104 *
6105 * a = [1, 2, 3, 4, 5, 0]
6106 * a.take_while {|i| i < 3} #=> [1, 2]
6107 *
6108 */
6109
6110 static VALUE
rb_ary_take_while(VALUE ary)6111 rb_ary_take_while(VALUE ary)
6112 {
6113 long i;
6114
6115 RETURN_ENUMERATOR(ary, 0, 0);
6116 for (i = 0; i < RARRAY_LEN(ary); i++) {
6117 if (!RTEST(rb_yield(RARRAY_AREF(ary, i)))) break;
6118 }
6119 return rb_ary_take(ary, LONG2FIX(i));
6120 }
6121
6122 /*
6123 * call-seq:
6124 * ary.drop(n) -> new_ary
6125 *
6126 * Drops first +n+ elements from +ary+ and returns the rest of the elements in
6127 * an array.
6128 *
6129 * If a negative number is given, raises an ArgumentError.
6130 *
6131 * See also Array#take
6132 *
6133 * a = [1, 2, 3, 4, 5, 0]
6134 * a.drop(3) #=> [4, 5, 0]
6135 *
6136 */
6137
6138 static VALUE
rb_ary_drop(VALUE ary,VALUE n)6139 rb_ary_drop(VALUE ary, VALUE n)
6140 {
6141 VALUE result;
6142 long pos = NUM2LONG(n);
6143 if (pos < 0) {
6144 rb_raise(rb_eArgError, "attempt to drop negative size");
6145 }
6146
6147 result = rb_ary_subseq(ary, pos, RARRAY_LEN(ary));
6148 if (result == Qnil) result = rb_ary_new();
6149 return result;
6150 }
6151
6152 /*
6153 * call-seq:
6154 * ary.drop_while {|obj| block} -> new_ary
6155 * ary.drop_while -> Enumerator
6156 *
6157 * Drops elements up to, but not including, the first element for which the
6158 * block returns +nil+ or +false+ and returns an array containing the
6159 * remaining elements.
6160 *
6161 * If no block is given, an Enumerator is returned instead.
6162 *
6163 * See also Array#take_while
6164 *
6165 * a = [1, 2, 3, 4, 5, 0]
6166 * a.drop_while {|i| i < 3 } #=> [3, 4, 5, 0]
6167 *
6168 */
6169
6170 static VALUE
rb_ary_drop_while(VALUE ary)6171 rb_ary_drop_while(VALUE ary)
6172 {
6173 long i;
6174
6175 RETURN_ENUMERATOR(ary, 0, 0);
6176 for (i = 0; i < RARRAY_LEN(ary); i++) {
6177 if (!RTEST(rb_yield(RARRAY_AREF(ary, i)))) break;
6178 }
6179 return rb_ary_drop(ary, LONG2FIX(i));
6180 }
6181
6182 /*
6183 * call-seq:
6184 * ary.any? [{|obj| block} ] -> true or false
6185 * ary.any?(pattern) -> true or false
6186 *
6187 * See also Enumerable#any?
6188 */
6189
6190 static VALUE
rb_ary_any_p(int argc,VALUE * argv,VALUE ary)6191 rb_ary_any_p(int argc, VALUE *argv, VALUE ary)
6192 {
6193 long i, len = RARRAY_LEN(ary);
6194
6195 rb_check_arity(argc, 0, 1);
6196 if (!len) return Qfalse;
6197 if (argc) {
6198 if (rb_block_given_p()) {
6199 rb_warn("given block not used");
6200 }
6201 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6202 if (RTEST(rb_funcall(argv[0], idEqq, 1, RARRAY_AREF(ary, i)))) return Qtrue;
6203 }
6204 }
6205 else if (!rb_block_given_p()) {
6206 for (i = 0; i < len; ++i) {
6207 if (RTEST(RARRAY_AREF(ary, i))) return Qtrue;
6208 }
6209 }
6210 else {
6211 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6212 if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) return Qtrue;
6213 }
6214 }
6215 return Qfalse;
6216 }
6217
6218 /*
6219 * call-seq:
6220 * ary.all? [{|obj| block} ] -> true or false
6221 * ary.all?(pattern) -> true or false
6222 *
6223 * See also Enumerable#all?
6224 */
6225
6226 static VALUE
rb_ary_all_p(int argc,VALUE * argv,VALUE ary)6227 rb_ary_all_p(int argc, VALUE *argv, VALUE ary)
6228 {
6229 long i, len = RARRAY_LEN(ary);
6230
6231 rb_check_arity(argc, 0, 1);
6232 if (!len) return Qtrue;
6233 if (argc) {
6234 if (rb_block_given_p()) {
6235 rb_warn("given block not used");
6236 }
6237 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6238 if (!RTEST(rb_funcall(argv[0], idEqq, 1, RARRAY_AREF(ary, i)))) return Qfalse;
6239 }
6240 }
6241 else if (!rb_block_given_p()) {
6242 for (i = 0; i < len; ++i) {
6243 if (!RTEST(RARRAY_AREF(ary, i))) return Qfalse;
6244 }
6245 }
6246 else {
6247 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6248 if (!RTEST(rb_yield(RARRAY_AREF(ary, i)))) return Qfalse;
6249 }
6250 }
6251 return Qtrue;
6252 }
6253
6254 /*
6255 * call-seq:
6256 * ary.none? [{|obj| block} ] -> true or false
6257 * ary.none?(pattern) -> true or false
6258 *
6259 * See also Enumerable#none?
6260 */
6261
6262 static VALUE
rb_ary_none_p(int argc,VALUE * argv,VALUE ary)6263 rb_ary_none_p(int argc, VALUE *argv, VALUE ary)
6264 {
6265 long i, len = RARRAY_LEN(ary);
6266
6267 rb_check_arity(argc, 0, 1);
6268 if (!len) return Qtrue;
6269 if (argc) {
6270 if (rb_block_given_p()) {
6271 rb_warn("given block not used");
6272 }
6273 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6274 if (RTEST(rb_funcall(argv[0], idEqq, 1, RARRAY_AREF(ary, i)))) return Qfalse;
6275 }
6276 }
6277 else if (!rb_block_given_p()) {
6278 for (i = 0; i < len; ++i) {
6279 if (RTEST(RARRAY_AREF(ary, i))) return Qfalse;
6280 }
6281 }
6282 else {
6283 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6284 if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) return Qfalse;
6285 }
6286 }
6287 return Qtrue;
6288 }
6289
6290 /*
6291 * call-seq:
6292 * ary.one? [{|obj| block} ] -> true or false
6293 * ary.one?(pattern) -> true or false
6294 *
6295 * See also Enumerable#one?
6296 */
6297
6298 static VALUE
rb_ary_one_p(int argc,VALUE * argv,VALUE ary)6299 rb_ary_one_p(int argc, VALUE *argv, VALUE ary)
6300 {
6301 long i, len = RARRAY_LEN(ary);
6302 VALUE result = Qfalse;
6303
6304 rb_check_arity(argc, 0, 1);
6305 if (!len) return Qfalse;
6306 if (argc) {
6307 if (rb_block_given_p()) {
6308 rb_warn("given block not used");
6309 }
6310 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6311 if (RTEST(rb_funcall(argv[0], idEqq, 1, RARRAY_AREF(ary, i)))) {
6312 if (result) return Qfalse;
6313 result = Qtrue;
6314 }
6315 }
6316 }
6317 else if (!rb_block_given_p()) {
6318 for (i = 0; i < len; ++i) {
6319 if (RTEST(RARRAY_AREF(ary, i))) {
6320 if (result) return Qfalse;
6321 result = Qtrue;
6322 }
6323 }
6324 }
6325 else {
6326 for (i = 0; i < RARRAY_LEN(ary); ++i) {
6327 if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) {
6328 if (result) return Qfalse;
6329 result = Qtrue;
6330 }
6331 }
6332 }
6333 return result;
6334 }
6335
6336 /*
6337 * call-seq:
6338 * ary.dig(idx, ...) -> object
6339 *
6340 * Extracts the nested value specified by the sequence of <i>idx</i>
6341 * objects by calling +dig+ at each step, returning +nil+ if any
6342 * intermediate step is +nil+.
6343 *
6344 * a = [[1, [2, 3]]]
6345 *
6346 * a.dig(0, 1, 1) #=> 3
6347 * a.dig(1, 2, 3) #=> nil
6348 * a.dig(0, 0, 0) #=> TypeError: Integer does not have #dig method
6349 * [42, {foo: :bar}].dig(1, :foo) #=> :bar
6350 */
6351
6352 static VALUE
rb_ary_dig(int argc,VALUE * argv,VALUE self)6353 rb_ary_dig(int argc, VALUE *argv, VALUE self)
6354 {
6355 rb_check_arity(argc, 1, UNLIMITED_ARGUMENTS);
6356 self = rb_ary_at(self, *argv);
6357 if (!--argc) return self;
6358 ++argv;
6359 return rb_obj_dig(argc, argv, self, Qnil);
6360 }
6361
6362 static inline VALUE
finish_exact_sum(long n,VALUE r,VALUE v,int z)6363 finish_exact_sum(long n, VALUE r, VALUE v, int z)
6364 {
6365 if (n != 0)
6366 v = rb_fix_plus(LONG2FIX(n), v);
6367 if (r != Qundef) {
6368 /* r can be an Integer when mathn is loaded */
6369 if (FIXNUM_P(r))
6370 v = rb_fix_plus(r, v);
6371 else if (RB_TYPE_P(r, T_BIGNUM))
6372 v = rb_big_plus(r, v);
6373 else
6374 v = rb_rational_plus(r, v);
6375 }
6376 else if (!n && z) {
6377 v = rb_fix_plus(LONG2FIX(0), v);
6378 }
6379 return v;
6380 }
6381
6382 /*
6383 * call-seq:
6384 * ary.sum(init=0) -> number
6385 * ary.sum(init=0) {|e| expr } -> number
6386 *
6387 * Returns the sum of elements.
6388 * For example, [e1, e2, e3].sum returns init + e1 + e2 + e3.
6389 *
6390 * If a block is given, the block is applied to each element
6391 * before addition.
6392 *
6393 * If <i>ary</i> is empty, it returns <i>init</i>.
6394 *
6395 * [].sum #=> 0
6396 * [].sum(0.0) #=> 0.0
6397 * [1, 2, 3].sum #=> 6
6398 * [3, 5.5].sum #=> 8.5
6399 * [2.5, 3.0].sum(0.0) {|e| e * e } #=> 15.25
6400 * [Object.new].sum #=> TypeError
6401 *
6402 * The (arithmetic) mean value of an array can be obtained as follows.
6403 *
6404 * mean = ary.sum(0.0) / ary.length
6405 *
6406 * This method can be used for non-numeric objects by
6407 * explicit <i>init</i> argument.
6408 *
6409 * ["a", "b", "c"].sum("") #=> "abc"
6410 * [[1], [[2]], [3]].sum([]) #=> [1, [2], 3]
6411 *
6412 * However, Array#join and Array#flatten is faster than Array#sum for
6413 * array of strings and array of arrays.
6414 *
6415 * ["a", "b", "c"].join #=> "abc"
6416 * [[1], [[2]], [3]].flatten(1) #=> [1, [2], 3]
6417 *
6418 *
6419 * Array#sum method may not respect method redefinition of "+" methods
6420 * such as Integer#+.
6421 *
6422 */
6423
6424 static VALUE
rb_ary_sum(int argc,VALUE * argv,VALUE ary)6425 rb_ary_sum(int argc, VALUE *argv, VALUE ary)
6426 {
6427 VALUE e, v, r;
6428 long i, n;
6429 int block_given;
6430
6431 v = (rb_check_arity(argc, 0, 1) ? argv[0] : LONG2FIX(0));
6432
6433 block_given = rb_block_given_p();
6434
6435 if (RARRAY_LEN(ary) == 0)
6436 return v;
6437
6438 n = 0;
6439 r = Qundef;
6440 for (i = 0; i < RARRAY_LEN(ary); i++) {
6441 e = RARRAY_AREF(ary, i);
6442 if (block_given)
6443 e = rb_yield(e);
6444 if (FIXNUM_P(e)) {
6445 n += FIX2LONG(e); /* should not overflow long type */
6446 if (!FIXABLE(n)) {
6447 v = rb_big_plus(LONG2NUM(n), v);
6448 n = 0;
6449 }
6450 }
6451 else if (RB_TYPE_P(e, T_BIGNUM))
6452 v = rb_big_plus(e, v);
6453 else if (RB_TYPE_P(e, T_RATIONAL)) {
6454 if (r == Qundef)
6455 r = e;
6456 else
6457 r = rb_rational_plus(r, e);
6458 }
6459 else
6460 goto not_exact;
6461 }
6462 v = finish_exact_sum(n, r, v, argc!=0);
6463 return v;
6464
6465 not_exact:
6466 v = finish_exact_sum(n, r, v, i!=0);
6467
6468 if (RB_FLOAT_TYPE_P(e)) {
6469 /*
6470 * Kahan-Babuska balancing compensated summation algorithm
6471 * See http://link.springer.com/article/10.1007/s00607-005-0139-x
6472 */
6473 double f, c;
6474
6475 f = NUM2DBL(v);
6476 c = 0.0;
6477 goto has_float_value;
6478 for (; i < RARRAY_LEN(ary); i++) {
6479 double x, t;
6480 e = RARRAY_AREF(ary, i);
6481 if (block_given)
6482 e = rb_yield(e);
6483 if (RB_FLOAT_TYPE_P(e))
6484 has_float_value:
6485 x = RFLOAT_VALUE(e);
6486 else if (FIXNUM_P(e))
6487 x = FIX2LONG(e);
6488 else if (RB_TYPE_P(e, T_BIGNUM))
6489 x = rb_big2dbl(e);
6490 else if (RB_TYPE_P(e, T_RATIONAL))
6491 x = rb_num2dbl(e);
6492 else
6493 goto not_float;
6494
6495 if (isnan(f)) continue;
6496 if (isnan(x)) {
6497 f = x;
6498 continue;
6499 }
6500 if (isinf(x)) {
6501 if (isinf(f) && signbit(x) != signbit(f))
6502 f = NAN;
6503 else
6504 f = x;
6505 continue;
6506 }
6507 if (isinf(f)) continue;
6508
6509 t = f + x;
6510 if (fabs(f) >= fabs(x))
6511 c += ((f - t) + x);
6512 else
6513 c += ((x - t) + f);
6514 f = t;
6515 }
6516 f += c;
6517 return DBL2NUM(f);
6518
6519 not_float:
6520 v = DBL2NUM(f);
6521 }
6522
6523 goto has_some_value;
6524 for (; i < RARRAY_LEN(ary); i++) {
6525 e = RARRAY_AREF(ary, i);
6526 if (block_given)
6527 e = rb_yield(e);
6528 has_some_value:
6529 v = rb_funcall(v, idPLUS, 1, e);
6530 }
6531 return v;
6532 }
6533
6534 /*
6535 * Arrays are ordered, integer-indexed collections of any object.
6536 *
6537 * Array indexing starts at 0, as in C or Java. A negative index is assumed
6538 * to be relative to the end of the array---that is, an index of -1 indicates
6539 * the last element of the array, -2 is the next to last element in the
6540 * array, and so on.
6541 *
6542 * == Creating Arrays
6543 *
6544 * A new array can be created by using the literal constructor
6545 * <code>[]</code>. Arrays can contain different types of objects. For
6546 * example, the array below contains an Integer, a String and a Float:
6547 *
6548 * ary = [1, "two", 3.0] #=> [1, "two", 3.0]
6549 *
6550 * An array can also be created by explicitly calling Array.new with zero, one
6551 * (the initial size of the Array) or two arguments (the initial size and a
6552 * default object).
6553 *
6554 * ary = Array.new #=> []
6555 * Array.new(3) #=> [nil, nil, nil]
6556 * Array.new(3, true) #=> [true, true, true]
6557 *
6558 * Note that the second argument populates the array with references to the
6559 * same object. Therefore, it is only recommended in cases when you need to
6560 * instantiate arrays with natively immutable objects such as Symbols,
6561 * numbers, true or false.
6562 *
6563 * To create an array with separate objects a block can be passed instead.
6564 * This method is safe to use with mutable objects such as hashes, strings or
6565 * other arrays:
6566 *
6567 * Array.new(4) {Hash.new} #=> [{}, {}, {}, {}]
6568 * Array.new(4) {|i| i.to_s } #=> ["0", "1", "2", "3"]
6569 *
6570 * This is also a quick way to build up multi-dimensional arrays:
6571 *
6572 * empty_table = Array.new(3) {Array.new(3)}
6573 * #=> [[nil, nil, nil], [nil, nil, nil], [nil, nil, nil]]
6574 *
6575 * An array can also be created by using the Array() method, provided by
6576 * Kernel, which tries to call #to_ary, then #to_a on its argument.
6577 *
6578 * Array({:a => "a", :b => "b"}) #=> [[:a, "a"], [:b, "b"]]
6579 *
6580 * == Example Usage
6581 *
6582 * In addition to the methods it mixes in through the Enumerable module, the
6583 * Array class has proprietary methods for accessing, searching and otherwise
6584 * manipulating arrays.
6585 *
6586 * Some of the more common ones are illustrated below.
6587 *
6588 * == Accessing Elements
6589 *
6590 * Elements in an array can be retrieved using the Array#[] method. It can
6591 * take a single integer argument (a numeric index), a pair of arguments
6592 * (start and length) or a range. Negative indices start counting from the end,
6593 * with -1 being the last element.
6594 *
6595 * arr = [1, 2, 3, 4, 5, 6]
6596 * arr[2] #=> 3
6597 * arr[100] #=> nil
6598 * arr[-3] #=> 4
6599 * arr[2, 3] #=> [3, 4, 5]
6600 * arr[1..4] #=> [2, 3, 4, 5]
6601 * arr[1..-3] #=> [2, 3, 4]
6602 *
6603 * Another way to access a particular array element is by using the #at method
6604 *
6605 * arr.at(0) #=> 1
6606 *
6607 * The #slice method works in an identical manner to Array#[].
6608 *
6609 * To raise an error for indices outside of the array bounds or else to
6610 * provide a default value when that happens, you can use #fetch.
6611 *
6612 * arr = ['a', 'b', 'c', 'd', 'e', 'f']
6613 * arr.fetch(100) #=> IndexError: index 100 outside of array bounds: -6...6
6614 * arr.fetch(100, "oops") #=> "oops"
6615 *
6616 * The special methods #first and #last will return the first and last
6617 * elements of an array, respectively.
6618 *
6619 * arr.first #=> 1
6620 * arr.last #=> 6
6621 *
6622 * To return the first +n+ elements of an array, use #take
6623 *
6624 * arr.take(3) #=> [1, 2, 3]
6625 *
6626 * #drop does the opposite of #take, by returning the elements after +n+
6627 * elements have been dropped:
6628 *
6629 * arr.drop(3) #=> [4, 5, 6]
6630 *
6631 * == Obtaining Information about an Array
6632 *
6633 * Arrays keep track of their own length at all times. To query an array
6634 * about the number of elements it contains, use #length, #count or #size.
6635 *
6636 * browsers = ['Chrome', 'Firefox', 'Safari', 'Opera', 'IE']
6637 * browsers.length #=> 5
6638 * browsers.count #=> 5
6639 *
6640 * To check whether an array contains any elements at all
6641 *
6642 * browsers.empty? #=> false
6643 *
6644 * To check whether a particular item is included in the array
6645 *
6646 * browsers.include?('Konqueror') #=> false
6647 *
6648 * == Adding Items to Arrays
6649 *
6650 * Items can be added to the end of an array by using either #push or #<<
6651 *
6652 * arr = [1, 2, 3, 4]
6653 * arr.push(5) #=> [1, 2, 3, 4, 5]
6654 * arr << 6 #=> [1, 2, 3, 4, 5, 6]
6655 *
6656 * #unshift will add a new item to the beginning of an array.
6657 *
6658 * arr.unshift(0) #=> [0, 1, 2, 3, 4, 5, 6]
6659 *
6660 * With #insert you can add a new element to an array at any position.
6661 *
6662 * arr.insert(3, 'apple') #=> [0, 1, 2, 'apple', 3, 4, 5, 6]
6663 *
6664 * Using the #insert method, you can also insert multiple values at once:
6665 *
6666 * arr.insert(3, 'orange', 'pear', 'grapefruit')
6667 * #=> [0, 1, 2, "orange", "pear", "grapefruit", "apple", 3, 4, 5, 6]
6668 *
6669 * == Removing Items from an Array
6670 *
6671 * The method #pop removes the last element in an array and returns it:
6672 *
6673 * arr = [1, 2, 3, 4, 5, 6]
6674 * arr.pop #=> 6
6675 * arr #=> [1, 2, 3, 4, 5]
6676 *
6677 * To retrieve and at the same time remove the first item, use #shift:
6678 *
6679 * arr.shift #=> 1
6680 * arr #=> [2, 3, 4, 5]
6681 *
6682 * To delete an element at a particular index:
6683 *
6684 * arr.delete_at(2) #=> 4
6685 * arr #=> [2, 3, 5]
6686 *
6687 * To delete a particular element anywhere in an array, use #delete:
6688 *
6689 * arr = [1, 2, 2, 3]
6690 * arr.delete(2) #=> 2
6691 * arr #=> [1,3]
6692 *
6693 * A useful method if you need to remove +nil+ values from an array is
6694 * #compact:
6695 *
6696 * arr = ['foo', 0, nil, 'bar', 7, 'baz', nil]
6697 * arr.compact #=> ['foo', 0, 'bar', 7, 'baz']
6698 * arr #=> ['foo', 0, nil, 'bar', 7, 'baz', nil]
6699 * arr.compact! #=> ['foo', 0, 'bar', 7, 'baz']
6700 * arr #=> ['foo', 0, 'bar', 7, 'baz']
6701 *
6702 * Another common need is to remove duplicate elements from an array.
6703 *
6704 * It has the non-destructive #uniq, and destructive method #uniq!
6705 *
6706 * arr = [2, 5, 6, 556, 6, 6, 8, 9, 0, 123, 556]
6707 * arr.uniq #=> [2, 5, 6, 556, 8, 9, 0, 123]
6708 *
6709 * == Iterating over Arrays
6710 *
6711 * Like all classes that include the Enumerable module, Array has an each
6712 * method, which defines what elements should be iterated over and how. In
6713 * case of Array's #each, all elements in the Array instance are yielded to
6714 * the supplied block in sequence.
6715 *
6716 * Note that this operation leaves the array unchanged.
6717 *
6718 * arr = [1, 2, 3, 4, 5]
6719 * arr.each {|a| print a -= 10, " "}
6720 * # prints: -9 -8 -7 -6 -5
6721 * #=> [1, 2, 3, 4, 5]
6722 *
6723 * Another sometimes useful iterator is #reverse_each which will iterate over
6724 * the elements in the array in reverse order.
6725 *
6726 * words = %w[first second third fourth fifth sixth]
6727 * str = ""
6728 * words.reverse_each {|word| str += "#{word} "}
6729 * p str #=> "sixth fifth fourth third second first "
6730 *
6731 * The #map method can be used to create a new array based on the original
6732 * array, but with the values modified by the supplied block:
6733 *
6734 * arr.map {|a| 2*a} #=> [2, 4, 6, 8, 10]
6735 * arr #=> [1, 2, 3, 4, 5]
6736 * arr.map! {|a| a**2} #=> [1, 4, 9, 16, 25]
6737 * arr #=> [1, 4, 9, 16, 25]
6738 *
6739 * == Selecting Items from an Array
6740 *
6741 * Elements can be selected from an array according to criteria defined in a
6742 * block. The selection can happen in a destructive or a non-destructive
6743 * manner. While the destructive operations will modify the array they were
6744 * called on, the non-destructive methods usually return a new array with the
6745 * selected elements, but leave the original array unchanged.
6746 *
6747 * === Non-destructive Selection
6748 *
6749 * arr = [1, 2, 3, 4, 5, 6]
6750 * arr.select {|a| a > 3} #=> [4, 5, 6]
6751 * arr.reject {|a| a < 3} #=> [3, 4, 5, 6]
6752 * arr.drop_while {|a| a < 4} #=> [4, 5, 6]
6753 * arr #=> [1, 2, 3, 4, 5, 6]
6754 *
6755 * === Destructive Selection
6756 *
6757 * #select! and #reject! are the corresponding destructive methods to #select
6758 * and #reject
6759 *
6760 * Similar to #select vs. #reject, #delete_if and #keep_if have the exact
6761 * opposite result when supplied with the same block:
6762 *
6763 * arr.delete_if {|a| a < 4} #=> [4, 5, 6]
6764 * arr #=> [4, 5, 6]
6765 *
6766 * arr = [1, 2, 3, 4, 5, 6]
6767 * arr.keep_if {|a| a < 4} #=> [1, 2, 3]
6768 * arr #=> [1, 2, 3]
6769 *
6770 */
6771
6772 void
Init_Array(void)6773 Init_Array(void)
6774 {
6775 #undef rb_intern
6776 #define rb_intern(str) rb_intern_const(str)
6777
6778 rb_cArray = rb_define_class("Array", rb_cObject);
6779 rb_include_module(rb_cArray, rb_mEnumerable);
6780
6781 rb_define_alloc_func(rb_cArray, empty_ary_alloc);
6782 rb_define_singleton_method(rb_cArray, "[]", rb_ary_s_create, -1);
6783 rb_define_singleton_method(rb_cArray, "try_convert", rb_ary_s_try_convert, 1);
6784 rb_define_method(rb_cArray, "initialize", rb_ary_initialize, -1);
6785 rb_define_method(rb_cArray, "initialize_copy", rb_ary_replace, 1);
6786
6787 rb_define_method(rb_cArray, "inspect", rb_ary_inspect, 0);
6788 rb_define_alias(rb_cArray, "to_s", "inspect");
6789 rb_define_method(rb_cArray, "to_a", rb_ary_to_a, 0);
6790 rb_define_method(rb_cArray, "to_h", rb_ary_to_h, 0);
6791 rb_define_method(rb_cArray, "to_ary", rb_ary_to_ary_m, 0);
6792
6793 rb_define_method(rb_cArray, "==", rb_ary_equal, 1);
6794 rb_define_method(rb_cArray, "eql?", rb_ary_eql, 1);
6795 rb_define_method(rb_cArray, "hash", rb_ary_hash, 0);
6796
6797 rb_define_method(rb_cArray, "[]", rb_ary_aref, -1);
6798 rb_define_method(rb_cArray, "[]=", rb_ary_aset, -1);
6799 rb_define_method(rb_cArray, "at", rb_ary_at, 1);
6800 rb_define_method(rb_cArray, "fetch", rb_ary_fetch, -1);
6801 rb_define_method(rb_cArray, "first", rb_ary_first, -1);
6802 rb_define_method(rb_cArray, "last", rb_ary_last, -1);
6803 rb_define_method(rb_cArray, "concat", rb_ary_concat_multi, -1);
6804 rb_define_method(rb_cArray, "union", rb_ary_union_multi, -1);
6805 rb_define_method(rb_cArray, "difference", rb_ary_difference_multi, -1);
6806 rb_define_method(rb_cArray, "<<", rb_ary_push, 1);
6807 rb_define_method(rb_cArray, "push", rb_ary_push_m, -1);
6808 rb_define_alias(rb_cArray, "append", "push");
6809 rb_define_method(rb_cArray, "pop", rb_ary_pop_m, -1);
6810 rb_define_method(rb_cArray, "shift", rb_ary_shift_m, -1);
6811 rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
6812 rb_define_alias(rb_cArray, "prepend", "unshift");
6813 rb_define_method(rb_cArray, "insert", rb_ary_insert, -1);
6814 rb_define_method(rb_cArray, "each", rb_ary_each, 0);
6815 rb_define_method(rb_cArray, "each_index", rb_ary_each_index, 0);
6816 rb_define_method(rb_cArray, "reverse_each", rb_ary_reverse_each, 0);
6817 rb_define_method(rb_cArray, "length", rb_ary_length, 0);
6818 rb_define_alias(rb_cArray, "size", "length");
6819 rb_define_method(rb_cArray, "empty?", rb_ary_empty_p, 0);
6820 rb_define_method(rb_cArray, "find_index", rb_ary_index, -1);
6821 rb_define_method(rb_cArray, "index", rb_ary_index, -1);
6822 rb_define_method(rb_cArray, "rindex", rb_ary_rindex, -1);
6823 rb_define_method(rb_cArray, "join", rb_ary_join_m, -1);
6824 rb_define_method(rb_cArray, "reverse", rb_ary_reverse_m, 0);
6825 rb_define_method(rb_cArray, "reverse!", rb_ary_reverse_bang, 0);
6826 rb_define_method(rb_cArray, "rotate", rb_ary_rotate_m, -1);
6827 rb_define_method(rb_cArray, "rotate!", rb_ary_rotate_bang, -1);
6828 rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
6829 rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);
6830 rb_define_method(rb_cArray, "sort_by!", rb_ary_sort_by_bang, 0);
6831 rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
6832 rb_define_method(rb_cArray, "collect!", rb_ary_collect_bang, 0);
6833 rb_define_method(rb_cArray, "map", rb_ary_collect, 0);
6834 rb_define_method(rb_cArray, "map!", rb_ary_collect_bang, 0);
6835 rb_define_method(rb_cArray, "select", rb_ary_select, 0);
6836 rb_define_method(rb_cArray, "select!", rb_ary_select_bang, 0);
6837 rb_define_method(rb_cArray, "filter", rb_ary_select, 0);
6838 rb_define_method(rb_cArray, "filter!", rb_ary_select_bang, 0);
6839 rb_define_method(rb_cArray, "keep_if", rb_ary_keep_if, 0);
6840 rb_define_method(rb_cArray, "values_at", rb_ary_values_at, -1);
6841 rb_define_method(rb_cArray, "delete", rb_ary_delete, 1);
6842 rb_define_method(rb_cArray, "delete_at", rb_ary_delete_at_m, 1);
6843 rb_define_method(rb_cArray, "delete_if", rb_ary_delete_if, 0);
6844 rb_define_method(rb_cArray, "reject", rb_ary_reject, 0);
6845 rb_define_method(rb_cArray, "reject!", rb_ary_reject_bang, 0);
6846 rb_define_method(rb_cArray, "zip", rb_ary_zip, -1);
6847 rb_define_method(rb_cArray, "transpose", rb_ary_transpose, 0);
6848 rb_define_method(rb_cArray, "replace", rb_ary_replace, 1);
6849 rb_define_method(rb_cArray, "clear", rb_ary_clear, 0);
6850 rb_define_method(rb_cArray, "fill", rb_ary_fill, -1);
6851 rb_define_method(rb_cArray, "include?", rb_ary_includes, 1);
6852 rb_define_method(rb_cArray, "<=>", rb_ary_cmp, 1);
6853
6854 rb_define_method(rb_cArray, "slice", rb_ary_aref, -1);
6855 rb_define_method(rb_cArray, "slice!", rb_ary_slice_bang, -1);
6856
6857 rb_define_method(rb_cArray, "assoc", rb_ary_assoc, 1);
6858 rb_define_method(rb_cArray, "rassoc", rb_ary_rassoc, 1);
6859
6860 rb_define_method(rb_cArray, "+", rb_ary_plus, 1);
6861 rb_define_method(rb_cArray, "*", rb_ary_times, 1);
6862
6863 rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
6864 rb_define_method(rb_cArray, "&", rb_ary_and, 1);
6865 rb_define_method(rb_cArray, "|", rb_ary_or, 1);
6866
6867 rb_define_method(rb_cArray, "max", rb_ary_max, -1);
6868 rb_define_method(rb_cArray, "min", rb_ary_min, -1);
6869
6870 rb_define_method(rb_cArray, "uniq", rb_ary_uniq, 0);
6871 rb_define_method(rb_cArray, "uniq!", rb_ary_uniq_bang, 0);
6872 rb_define_method(rb_cArray, "compact", rb_ary_compact, 0);
6873 rb_define_method(rb_cArray, "compact!", rb_ary_compact_bang, 0);
6874 rb_define_method(rb_cArray, "flatten", rb_ary_flatten, -1);
6875 rb_define_method(rb_cArray, "flatten!", rb_ary_flatten_bang, -1);
6876 rb_define_method(rb_cArray, "count", rb_ary_count, -1);
6877 rb_define_method(rb_cArray, "shuffle!", rb_ary_shuffle_bang, -1);
6878 rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, -1);
6879 rb_define_method(rb_cArray, "sample", rb_ary_sample, -1);
6880 rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1);
6881 rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1);
6882 rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
6883 rb_define_method(rb_cArray, "repeated_permutation", rb_ary_repeated_permutation, 1);
6884 rb_define_method(rb_cArray, "repeated_combination", rb_ary_repeated_combination, 1);
6885 rb_define_method(rb_cArray, "product", rb_ary_product, -1);
6886
6887 rb_define_method(rb_cArray, "take", rb_ary_take, 1);
6888 rb_define_method(rb_cArray, "take_while", rb_ary_take_while, 0);
6889 rb_define_method(rb_cArray, "drop", rb_ary_drop, 1);
6890 rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0);
6891 rb_define_method(rb_cArray, "bsearch", rb_ary_bsearch, 0);
6892 rb_define_method(rb_cArray, "bsearch_index", rb_ary_bsearch_index, 0);
6893 rb_define_method(rb_cArray, "any?", rb_ary_any_p, -1);
6894 rb_define_method(rb_cArray, "all?", rb_ary_all_p, -1);
6895 rb_define_method(rb_cArray, "none?", rb_ary_none_p, -1);
6896 rb_define_method(rb_cArray, "one?", rb_ary_one_p, -1);
6897 rb_define_method(rb_cArray, "dig", rb_ary_dig, -1);
6898 rb_define_method(rb_cArray, "sum", rb_ary_sum, -1);
6899
6900 id_random = rb_intern("random");
6901 }
6902