Ruby  2.0.0p598(2014-11-13revision48408)
array.c
Go to the documentation of this file.
1 /**********************************************************************
2 
3  array.c -
4 
5  $Author: usa $
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/ruby.h"
15 #include "ruby/util.h"
16 #include "ruby/st.h"
17 #include "ruby/encoding.h"
18 #include "internal.h"
19 #include "probes.h"
20 #include "id.h"
21 
22 #ifndef ARRAY_DEBUG
23 # define NDEBUG
24 #endif
25 #include <assert.h>
26 
27 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
28 
30 
32 
33 #define ARY_DEFAULT_SIZE 16
34 #define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
35 
36 void
37 rb_mem_clear(register VALUE *mem, register long size)
38 {
39  while (size--) {
40  *mem++ = Qnil;
41  }
42 }
43 
44 static inline void
45 memfill(register VALUE *mem, register long size, register VALUE val)
46 {
47  while (size--) {
48  *mem++ = val;
49  }
50 }
51 
52 # define ARY_SHARED_P(ary) \
53  (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
54  FL_TEST((ary),ELTS_SHARED)!=0)
55 # define ARY_EMBED_P(ary) \
56  (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
57  FL_TEST((ary), RARRAY_EMBED_FLAG)!=0)
58 
59 #define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
60 #define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
61 #define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
62 #define ARY_EMBED_LEN(a) \
63  (assert(ARY_EMBED_P(a)), \
64  (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
65  (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
66 
67 #define ARY_OWNS_HEAP_P(a) (!FL_TEST((a), ELTS_SHARED|RARRAY_EMBED_FLAG))
68 #define FL_SET_EMBED(a) do { \
69  assert(!ARY_SHARED_P(a)); \
70  FL_SET((a), RARRAY_EMBED_FLAG); \
71 } while (0)
72 #define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
73 #define FL_SET_SHARED(ary) do { \
74  assert(!ARY_EMBED_P(ary)); \
75  FL_SET((ary), ELTS_SHARED); \
76 } while (0)
77 #define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)
78 
79 #define ARY_SET_PTR(ary, p) do { \
80  assert(!ARY_EMBED_P(ary)); \
81  assert(!OBJ_FROZEN(ary)); \
82  RARRAY(ary)->as.heap.ptr = (p); \
83 } while (0)
84 #define ARY_SET_EMBED_LEN(ary, n) do { \
85  long tmp_n = (n); \
86  assert(ARY_EMBED_P(ary)); \
87  assert(!OBJ_FROZEN(ary)); \
88  RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
89  RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
90 } while (0)
91 #define ARY_SET_HEAP_LEN(ary, n) do { \
92  assert(!ARY_EMBED_P(ary)); \
93  RARRAY(ary)->as.heap.len = (n); \
94 } while (0)
95 #define ARY_SET_LEN(ary, n) do { \
96  if (ARY_EMBED_P(ary)) { \
97  ARY_SET_EMBED_LEN((ary), (n)); \
98  } \
99  else { \
100  ARY_SET_HEAP_LEN((ary), (n)); \
101  } \
102  assert(RARRAY_LEN(ary) == (n)); \
103 } while (0)
104 #define ARY_INCREASE_PTR(ary, n) do { \
105  assert(!ARY_EMBED_P(ary)); \
106  assert(!OBJ_FROZEN(ary)); \
107  RARRAY(ary)->as.heap.ptr += (n); \
108 } while (0)
109 #define ARY_INCREASE_LEN(ary, n) do { \
110  assert(!OBJ_FROZEN(ary)); \
111  if (ARY_EMBED_P(ary)) { \
112  ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
113  } \
114  else { \
115  RARRAY(ary)->as.heap.len += (n); \
116  } \
117 } while (0)
118 
119 #define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
120  ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : RARRAY(ary)->as.heap.aux.capa)
121 #define ARY_SET_CAPA(ary, n) do { \
122  assert(!ARY_EMBED_P(ary)); \
123  assert(!ARY_SHARED_P(ary)); \
124  assert(!OBJ_FROZEN(ary)); \
125  RARRAY(ary)->as.heap.aux.capa = (n); \
126 } while (0)
127 
128 #define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
129 #define ARY_SET_SHARED(ary, value) do { \
130  assert(!ARY_EMBED_P(ary)); \
131  assert(ARY_SHARED_P(ary)); \
132  assert(ARY_SHARED_ROOT_P(value)); \
133  RARRAY(ary)->as.heap.aux.shared = (value); \
134 } while (0)
135 #define RARRAY_SHARED_ROOT_FLAG FL_USER5
136 #define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))
137 #define ARY_SHARED_NUM(ary) \
138  (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
139 #define ARY_SET_SHARED_NUM(ary, value) do { \
140  assert(ARY_SHARED_ROOT_P(ary)); \
141  RARRAY(ary)->as.heap.aux.capa = (value); \
142 } while (0)
143 #define FL_SET_SHARED_ROOT(ary) do { \
144  assert(!ARY_EMBED_P(ary)); \
145  FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
146 } while (0)
147 
148 static void
149 ary_resize_capa(VALUE ary, long capacity)
150 {
151  assert(RARRAY_LEN(ary) <= capacity);
152  assert(!OBJ_FROZEN(ary));
153  assert(!ARY_SHARED_P(ary));
154  if (capacity > RARRAY_EMBED_LEN_MAX) {
155  if (ARY_EMBED_P(ary)) {
156  long len = ARY_EMBED_LEN(ary);
157  VALUE *ptr = ALLOC_N(VALUE, (capacity));
158  MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
159  FL_UNSET_EMBED(ary);
160  ARY_SET_PTR(ary, ptr);
161  ARY_SET_HEAP_LEN(ary, len);
162  }
163  else {
164  REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));
165  }
166  ARY_SET_CAPA(ary, (capacity));
167  }
168  else {
169  if (!ARY_EMBED_P(ary)) {
170  long len = RARRAY_LEN(ary);
171  VALUE *ptr = RARRAY_PTR(ary);
172  if (len > capacity) len = capacity;
173  MEMCPY(RARRAY(ary)->as.ary, ptr, VALUE, len);
174  FL_SET_EMBED(ary);
175  ARY_SET_LEN(ary, len);
176  xfree(ptr);
177  }
178  }
179 }
180 
181 static void
183 {
184  long new_capa = ARY_CAPA(ary) / 2;
185 
186  if (new_capa < ARY_DEFAULT_SIZE) {
187  new_capa = ARY_DEFAULT_SIZE;
188  }
189  if (new_capa >= ARY_MAX_SIZE - min) {
190  new_capa = (ARY_MAX_SIZE - min) / 2;
191  }
192  new_capa += min;
193  ary_resize_capa(ary, new_capa);
194 }
195 
196 static void
198 {
199  if (shared) {
200  long num = ARY_SHARED_NUM(shared) - 1;
201  if (num == 0) {
202  rb_ary_free(shared);
203  rb_gc_force_recycle(shared);
204  }
205  else if (num > 0) {
206  ARY_SET_SHARED_NUM(shared, num);
207  }
208  }
209 }
210 
211 static void
213 {
214  VALUE shared = RARRAY(ary)->as.heap.aux.shared;
215  rb_ary_decrement_share(shared);
216  FL_UNSET_SHARED(ary);
217 }
218 
219 static inline void
221 {
222  if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
223  rb_ary_unshare(ary);
224  }
225 }
226 
227 static VALUE
229 {
230  long num = ARY_SHARED_NUM(shared);
231  if (num >= 0) {
232  ARY_SET_SHARED_NUM(shared, num + 1);
233  }
234  return shared;
235 }
236 
237 static void
239 {
240  rb_ary_increment_share(shared);
241  FL_SET_SHARED(ary);
242  ARY_SET_SHARED(ary, shared);
243 }
244 
245 static inline void
247 {
248  rb_check_frozen(ary);
249  if (!OBJ_UNTRUSTED(ary) && rb_safe_level() >= 4)
250  rb_raise(rb_eSecurityError, "Insecure: can't modify array");
251 }
252 
253 void
255 {
256  rb_ary_modify_check(ary);
257  if (ARY_SHARED_P(ary)) {
258  long len = RARRAY_LEN(ary);
259  VALUE shared = ARY_SHARED(ary);
260  if (len <= RARRAY_EMBED_LEN_MAX) {
261  VALUE *ptr = ARY_HEAP_PTR(ary);
262  FL_UNSET_SHARED(ary);
263  FL_SET_EMBED(ary);
264  MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
265  rb_ary_decrement_share(shared);
266  ARY_SET_EMBED_LEN(ary, len);
267  }
268  else if (ARY_SHARED_NUM(shared) == 1 && len > (RARRAY_LEN(shared)>>1)) {
269  long shift = RARRAY_PTR(ary) - RARRAY_PTR(shared);
270  FL_UNSET_SHARED(ary);
271  ARY_SET_PTR(ary, RARRAY_PTR(shared));
272  ARY_SET_CAPA(ary, RARRAY_LEN(shared));
273  MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+shift, VALUE, len);
274  FL_SET_EMBED(shared);
275  rb_ary_decrement_share(shared);
276  }
277  else {
278  VALUE *ptr = ALLOC_N(VALUE, len);
279  MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
280  rb_ary_unshare(ary);
281  ARY_SET_CAPA(ary, len);
282  ARY_SET_PTR(ary, ptr);
283  }
284  }
285 }
286 
287 static void
289 {
290  long new_len = RARRAY_LEN(ary) + add_len;
291  long capa;
292 
293  if (ARY_SHARED_P(ary)) {
294  if (new_len > RARRAY_EMBED_LEN_MAX) {
295  VALUE shared = ARY_SHARED(ary);
296  if (ARY_SHARED_NUM(shared) == 1) {
297  if (RARRAY_PTR(ary) - RARRAY_PTR(shared) + new_len <= RARRAY_LEN(shared)) {
298  rb_ary_modify_check(ary);
299  }
300  else {
301  /* if array is shared, than it is likely it participate in push/shift pattern */
302  rb_ary_modify(ary);
303  capa = ARY_CAPA(ary);
304  if (new_len > capa - (capa >> 6)) {
305  ary_double_capa(ary, new_len);
306  }
307  }
308  return;
309  }
310  }
311  }
312  rb_ary_modify(ary);
313  capa = ARY_CAPA(ary);
314  if (new_len > capa) {
315  ary_double_capa(ary, new_len);
316  }
317 }
318 
319 /*
320  * call-seq:
321  * ary.freeze -> ary
322  *
323  * Calls Object#freeze on +ary+ to prevent any further
324  * modification. A RuntimeError will be raised if a modification
325  * attempt is made.
326  *
327  */
328 
329 VALUE
331 {
332  return rb_obj_freeze(ary);
333 }
334 
335 /*
336  * call-seq:
337  * ary.frozen? -> true or false
338  *
339  * Return +true+ if this array is frozen (or temporarily frozen
340  * while being sorted). See also Object#frozen?
341  */
342 
343 static VALUE
345 {
346  if (OBJ_FROZEN(ary)) return Qtrue;
347  return Qfalse;
348 }
349 
350 /* This can be used to take a snapshot of an array (with
351  e.g. rb_ary_replace) and check later whether the array has been
352  modified from the snapshot. The snapshot is cheap, though if
353  something does modify the array it will pay the cost of copying
354  it. If Array#pop or Array#shift has been called, the array will
355  be still shared with the snapshot, but the array length will
356  differ. */
357 VALUE
359 {
360  if (!ARY_EMBED_P(ary1) && ARY_SHARED_P(ary1) &&
361  !ARY_EMBED_P(ary2) && ARY_SHARED_P(ary2) &&
362  RARRAY(ary1)->as.heap.aux.shared == RARRAY(ary2)->as.heap.aux.shared &&
363  RARRAY(ary1)->as.heap.len == RARRAY(ary2)->as.heap.len) {
364  return Qtrue;
365  }
366  return Qfalse;
367 }
368 
369 static VALUE
371 {
372  NEWOBJ_OF(ary, struct RArray, klass, T_ARRAY);
374  ARY_SET_EMBED_LEN((VALUE)ary, 0);
375 
376  return (VALUE)ary;
377 }
378 
379 static VALUE
381 {
384  }
385 
386  return ary_alloc(klass);
387 }
388 
389 static VALUE
390 ary_new(VALUE klass, long capa)
391 {
392  VALUE ary;
393 
394  if (capa < 0) {
395  rb_raise(rb_eArgError, "negative array size (or size too big)");
396  }
397  if (capa > ARY_MAX_SIZE) {
398  rb_raise(rb_eArgError, "array size too big");
399  }
400 
403  }
404 
405  ary = ary_alloc(klass);
406  if (capa > RARRAY_EMBED_LEN_MAX) {
407  FL_UNSET_EMBED(ary);
408  ARY_SET_PTR(ary, ALLOC_N(VALUE, capa));
409  ARY_SET_CAPA(ary, capa);
410  ARY_SET_HEAP_LEN(ary, 0);
411  }
412 
413  return ary;
414 }
415 
416 VALUE
417 rb_ary_new2(long capa)
418 {
419  return ary_new(rb_cArray, capa);
420 }
421 
422 
423 VALUE
425 {
427 }
428 
429 #include <stdarg.h>
430 
431 VALUE
432 rb_ary_new3(long n, ...)
433 {
434  va_list ar;
435  VALUE ary;
436  long i;
437 
438  ary = rb_ary_new2(n);
439 
440  va_start(ar, n);
441  for (i=0; i<n; i++) {
442  RARRAY_PTR(ary)[i] = va_arg(ar, VALUE);
443  }
444  va_end(ar);
445 
446  ARY_SET_LEN(ary, n);
447  return ary;
448 }
449 
450 VALUE
451 rb_ary_new4(long n, const VALUE *elts)
452 {
453  VALUE ary;
454 
455  ary = rb_ary_new2(n);
456  if (n > 0 && elts) {
457  MEMCPY(RARRAY_PTR(ary), elts, VALUE, n);
458  ARY_SET_LEN(ary, n);
459  }
460 
461  return ary;
462 }
463 
464 VALUE
465 rb_ary_tmp_new(long capa)
466 {
467  return ary_new(0, capa);
468 }
469 
470 void
472 {
473  if (ARY_OWNS_HEAP_P(ary)) {
474  xfree(ARY_HEAP_PTR(ary));
475  }
476 }
477 
478 RUBY_FUNC_EXPORTED size_t
480 {
481  if (ARY_OWNS_HEAP_P(ary)) {
482  return RARRAY(ary)->as.heap.aux.capa * sizeof(VALUE);
483  }
484  else {
485  return 0;
486  }
487 }
488 
489 static inline void
491 {
492  rb_ary_free(ary);
493  RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
494  RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK;
495 }
496 
497 static VALUE
499 {
500  assert(!ARY_EMBED_P(ary));
501  if (ARY_SHARED_P(ary)) {
502  return ARY_SHARED(ary);
503  }
504  else if (ARY_SHARED_ROOT_P(ary)) {
505  return ary;
506  }
507  else if (OBJ_FROZEN(ary)) {
508  ary_resize_capa(ary, ARY_HEAP_LEN(ary));
509  FL_SET_SHARED_ROOT(ary);
510  ARY_SET_SHARED_NUM(ary, 1);
511  return ary;
512  }
513  else {
514  NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY);
515  FL_UNSET_EMBED(shared);
516 
517  ARY_SET_LEN((VALUE)shared, ARY_CAPA(ary));
518  ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
519  rb_mem_clear(RARRAY_PTR(shared) + RARRAY_LEN(ary), ARY_CAPA(ary) - RARRAY_LEN(ary));
520  FL_SET_SHARED_ROOT(shared);
521  ARY_SET_SHARED_NUM((VALUE)shared, 1);
522  FL_SET_SHARED(ary);
523  ARY_SET_SHARED(ary, (VALUE)shared);
524  OBJ_FREEZE(shared);
525  return (VALUE)shared;
526  }
527 }
528 
529 
530 static VALUE
532 {
533  if (RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX) {
534  VALUE subst = rb_ary_new2(RARRAY_LEN(ary));
535  MEMCPY(ARY_EMBED_PTR(subst), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
536  ARY_SET_EMBED_LEN(subst, RARRAY_LEN(ary));
537  return subst;
538  }
539  else {
541  }
542 }
543 
544 VALUE
546 {
547  return rb_ary_new3(2, car, cdr);
548 }
549 
550 static VALUE
552 {
553  return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
554 }
555 
556 VALUE
558 {
559  return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
560 }
561 
562 /*
563  * call-seq:
564  * Array.try_convert(obj) -> array or nil
565  *
566  * Tries to convert +obj+ into an array, using +to_ary+ method. Returns the
567  * converted array or +nil+ if +obj+ cannot be converted for any reason.
568  * This method can be used to check if an argument is an array.
569  *
570  * Array.try_convert([1]) #=> [1]
571  * Array.try_convert("1") #=> nil
572  *
573  * if tmp = Array.try_convert(arg)
574  * # the argument is an array
575  * elsif tmp = String.try_convert(arg)
576  * # the argument is a string
577  * end
578  *
579  */
580 
581 static VALUE
583 {
584  return rb_check_array_type(ary);
585 }
586 
587 /*
588  * call-seq:
589  * Array.new(size=0, obj=nil)
590  * Array.new(array)
591  * Array.new(size) {|index| block }
592  *
593  * Returns a new array.
594  *
595  * In the first form, if no arguments are sent, the new array will be empty.
596  * When a +size+ and an optional +obj+ are sent, an array is created with
597  * +size+ copies of +obj+. Take notice that all elements will reference the
598  * same object +obj+.
599  *
600  * The second form creates a copy of the array passed as a parameter (the
601  * array is generated by calling to_ary on the parameter).
602  *
603  * first_array = ["Matz", "Guido"]
604  *
605  * second_array = Array.new(first_array) #=> ["Matz", "Guido"]
606  *
607  * first_array.equal? second_array #=> false
608  *
609  * In the last form, an array of the given size is created. Each element in
610  * this array is created by passing the element's index to the given block
611  * and storing the return value.
612  *
613  * Array.new(3){ |index| index ** 2 }
614  * # => [0, 1, 4]
615  *
616  * == Common gotchas
617  *
618  * When sending the second parameter, the same object will be used as the
619  * value for all the array elements:
620  *
621  * a = Array.new(2, Hash.new)
622  * # => [{}, {}]
623  *
624  * a[0]['cat'] = 'feline'
625  * a # => [{"cat"=>"feline"}, {"cat"=>"feline"}]
626  *
627  * a[1]['cat'] = 'Felix'
628  * a # => [{"cat"=>"Felix"}, {"cat"=>"Felix"}]
629  *
630  * Since all the Array elements store the same hash, changes to one of them
631  * will affect them all.
632  *
633  * If multiple copies are what you want, you should use the block
634  * version which uses the result of that block each time an element
635  * of the array needs to be initialized:
636  *
637  * a = Array.new(2) { Hash.new }
638  * a[0]['cat'] = 'feline'
639  * a # => [{"cat"=>"feline"}, {}]
640  *
641  */
642 
643 static VALUE
645 {
646  long len;
647  VALUE size, val;
648 
649  rb_ary_modify(ary);
650  if (argc == 0) {
651  if (ARY_OWNS_HEAP_P(ary) && RARRAY_PTR(ary)) {
652  xfree(RARRAY_PTR(ary));
653  }
654  rb_ary_unshare_safe(ary);
655  FL_SET_EMBED(ary);
656  ARY_SET_EMBED_LEN(ary, 0);
657  if (rb_block_given_p()) {
658  rb_warning("given block not used");
659  }
660  return ary;
661  }
662  rb_scan_args(argc, argv, "02", &size, &val);
663  if (argc == 1 && !FIXNUM_P(size)) {
664  val = rb_check_array_type(size);
665  if (!NIL_P(val)) {
666  rb_ary_replace(ary, val);
667  return ary;
668  }
669  }
670 
671  len = NUM2LONG(size);
672  if (len < 0) {
673  rb_raise(rb_eArgError, "negative array size");
674  }
675  if (len > ARY_MAX_SIZE) {
676  rb_raise(rb_eArgError, "array size too big");
677  }
678  rb_ary_modify(ary);
679  ary_resize_capa(ary, len);
680  if (rb_block_given_p()) {
681  long i;
682 
683  if (argc == 2) {
684  rb_warn("block supersedes default value argument");
685  }
686  for (i=0; i<len; i++) {
687  rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
688  ARY_SET_LEN(ary, i + 1);
689  }
690  }
691  else {
692  memfill(RARRAY_PTR(ary), len, val);
693  ARY_SET_LEN(ary, len);
694  }
695  return ary;
696 }
697 
698 /*
699  * Returns a new array populated with the given objects.
700  *
701  * Array.[]( 1, 'a', /^A/ ) # => [1, "a", /^A/]
702  * Array[ 1, 'a', /^A/ ] # => [1, "a", /^A/]
703  * [ 1, 'a', /^A/ ] # => [1, "a", /^A/]
704  */
705 
706 static VALUE
708 {
709  VALUE ary = ary_new(klass, argc);
710  if (argc > 0 && argv) {
711  MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
712  ARY_SET_LEN(ary, argc);
713  }
714 
715  return ary;
716 }
717 
718 void
720 {
721  if (idx < 0) {
722  idx += RARRAY_LEN(ary);
723  if (idx < 0) {
724  rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
725  idx - RARRAY_LEN(ary), -RARRAY_LEN(ary));
726  }
727  }
728  else if (idx >= ARY_MAX_SIZE) {
729  rb_raise(rb_eIndexError, "index %ld too big", idx);
730  }
731 
732  rb_ary_modify(ary);
733  if (idx >= ARY_CAPA(ary)) {
734  ary_double_capa(ary, idx);
735  }
736  if (idx > RARRAY_LEN(ary)) {
737  rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary),
738  idx-RARRAY_LEN(ary) + 1);
739  }
740 
741  if (idx >= RARRAY_LEN(ary)) {
742  ARY_SET_LEN(ary, idx + 1);
743  }
744  RARRAY_PTR(ary)[idx] = val;
745 }
746 
747 static VALUE
748 ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
749 {
750  assert(offset >= 0);
751  assert(len >= 0);
752  assert(offset+len <= RARRAY_LEN(ary));
753 
754  if (len <= RARRAY_EMBED_LEN_MAX) {
755  VALUE result = ary_alloc(klass);
756  MEMCPY(ARY_EMBED_PTR(result), RARRAY_PTR(ary) + offset, VALUE, len);
757  ARY_SET_EMBED_LEN(result, len);
758  return result;
759  }
760  else {
761  VALUE shared, result = ary_alloc(klass);
762  FL_UNSET_EMBED(result);
763 
764  shared = ary_make_shared(ary);
765  ARY_SET_PTR(result, RARRAY_PTR(ary));
766  ARY_SET_LEN(result, RARRAY_LEN(ary));
767  rb_ary_set_shared(result, shared);
768 
769  ARY_INCREASE_PTR(result, offset);
770  ARY_SET_LEN(result, len);
771  return result;
772  }
773 }
774 
775 static VALUE
777 {
778  return ary_make_partial(ary, rb_obj_class(ary), 0, RARRAY_LEN(ary));
779 }
780 
782 {
785 };
786 
787 static VALUE
789 {
790  VALUE nv;
791  long n;
792  long offset = 0;
793 
794  rb_scan_args(argc, argv, "1", &nv);
795  n = NUM2LONG(nv);
796  if (n > RARRAY_LEN(ary)) {
797  n = RARRAY_LEN(ary);
798  }
799  else if (n < 0) {
800  rb_raise(rb_eArgError, "negative array size");
801  }
802  if (last) {
803  offset = RARRAY_LEN(ary) - n;
804  }
805  return ary_make_partial(ary, rb_cArray, offset, n);
806 }
807 
808 /*
809  * call-seq:
810  * ary << obj -> ary
811  *
812  * Append---Pushes the given object on to the end of this array. This
813  * expression returns the array itself, so several appends
814  * may be chained together.
815  *
816  * [ 1, 2 ] << "c" << "d" << [ 3, 4 ]
817  * #=> [ 1, 2, "c", "d", [ 3, 4 ] ]
818  *
819  */
820 
821 VALUE
823 {
824  long idx = RARRAY_LEN(ary);
825 
826  ary_ensure_room_for_push(ary, 1);
827  RARRAY_PTR(ary)[idx] = item;
828  ARY_SET_LEN(ary, idx + 1);
829  return ary;
830 }
831 
832 VALUE
833 rb_ary_cat(VALUE ary, const VALUE *ptr, long len)
834 {
835  long oldlen = RARRAY_LEN(ary);
836 
837  ary_ensure_room_for_push(ary, len);
838  MEMCPY(RARRAY_PTR(ary) + oldlen, ptr, VALUE, len);
839  ARY_SET_LEN(ary, oldlen + len);
840  return ary;
841 }
842 
843 /*
844  * call-seq:
845  * ary.push(obj, ... ) -> ary
846  *
847  * Append --- Pushes the given object(s) on to the end of this array. This
848  * expression returns the array itself, so several appends
849  * may be chained together. See also Array#pop for the opposite
850  * effect.
851  *
852  * a = [ "a", "b", "c" ]
853  * a.push("d", "e", "f")
854  * #=> ["a", "b", "c", "d", "e", "f"]
855  * [1, 2, 3,].push(4).push(5)
856  * #=> [1, 2, 3, 4, 5]
857  */
858 
859 static VALUE
861 {
862  return rb_ary_cat(ary, argv, argc);
863 }
864 
865 VALUE
867 {
868  long n;
869  rb_ary_modify_check(ary);
870  if (RARRAY_LEN(ary) == 0) return Qnil;
871  if (ARY_OWNS_HEAP_P(ary) &&
872  RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
873  ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
874  {
875  ary_resize_capa(ary, RARRAY_LEN(ary) * 2);
876  }
877  n = RARRAY_LEN(ary)-1;
878  ARY_SET_LEN(ary, n);
879  return RARRAY_PTR(ary)[n];
880 }
881 
882 /*
883  * call-seq:
884  * ary.pop -> obj or nil
885  * ary.pop(n) -> new_ary
886  *
887  * Removes the last element from +self+ and returns it, or
888  * +nil+ if the array is empty.
889  *
890  * If a number +n+ is given, returns an array of the last +n+ elements
891  * (or less) just like <code>array.slice!(-n, n)</code> does. See also
892  * Array#push for the opposite effect.
893  *
894  * a = [ "a", "b", "c", "d" ]
895  * a.pop #=> "d"
896  * a.pop(2) #=> ["b", "c"]
897  * a #=> ["a"]
898  */
899 
900 static VALUE
902 {
903  VALUE result;
904 
905  if (argc == 0) {
906  return rb_ary_pop(ary);
907  }
908 
909  rb_ary_modify_check(ary);
910  result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
911  ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
912  return result;
913 }
914 
915 VALUE
917 {
918  VALUE top;
919 
920  rb_ary_modify_check(ary);
921  if (RARRAY_LEN(ary) == 0) return Qnil;
922  top = RARRAY_PTR(ary)[0];
923  if (!ARY_SHARED_P(ary)) {
924  if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
925  MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
926  ARY_INCREASE_LEN(ary, -1);
927  return top;
928  }
929  assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */
930 
931  RARRAY_PTR(ary)[0] = Qnil;
932  ary_make_shared(ary);
933  }
934  else if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
935  RARRAY_PTR(ary)[0] = Qnil;
936  }
937  ARY_INCREASE_PTR(ary, 1); /* shift ptr */
938  ARY_INCREASE_LEN(ary, -1);
939 
940  return top;
941 }
942 
943 /*
944  * call-seq:
945  * ary.shift -> obj or nil
946  * ary.shift(n) -> new_ary
947  *
948  * Removes the first element of +self+ and returns it (shifting all
949  * other elements down by one). Returns +nil+ if the array
950  * is empty.
951  *
952  * If a number +n+ is given, returns an array of the first +n+ elements
953  * (or less) just like <code>array.slice!(0, n)</code> does. With +ary+
954  * containing only the remainder elements, not including what was shifted to
955  * +new_ary+. See also Array#unshift for the opposite effect.
956  *
957  * args = [ "-m", "-q", "filename" ]
958  * args.shift #=> "-m"
959  * args #=> ["-q", "filename"]
960  *
961  * args = [ "-m", "-q", "filename" ]
962  * args.shift(2) #=> ["-m", "-q"]
963  * args #=> ["filename"]
964  */
965 
966 static VALUE
968 {
969  VALUE result;
970  long n;
971 
972  if (argc == 0) {
973  return rb_ary_shift(ary);
974  }
975 
976  rb_ary_modify_check(ary);
977  result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
978  n = RARRAY_LEN(result);
979  if (ARY_SHARED_P(ary)) {
980  if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
981  rb_mem_clear(RARRAY_PTR(ary), n);
982  }
983  ARY_INCREASE_PTR(ary, n);
984  }
985  else {
986  MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
987  }
988  ARY_INCREASE_LEN(ary, -n);
989 
990  return result;
991 }
992 
993 static void
995 {
996  long len = RARRAY_LEN(ary);
997  long new_len = len + argc;
998  long capa;
999  VALUE *head, *sharedp;
1000 
1001  if (ARY_SHARED_P(ary)) {
1002  VALUE shared = ARY_SHARED(ary);
1003  capa = RARRAY_LEN(shared);
1004  if (ARY_SHARED_NUM(shared) == 1 && capa > new_len) {
1005  head = RARRAY_PTR(ary);
1006  sharedp = RARRAY_PTR(shared);
1007  goto makeroom_if_need;
1008  }
1009  }
1010 
1011  rb_ary_modify(ary);
1012  capa = ARY_CAPA(ary);
1013  if (capa - (capa >> 6) <= new_len) {
1014  ary_double_capa(ary, new_len);
1015  }
1016 
1017  /* use shared array for big "queues" */
1018  if (new_len > ARY_DEFAULT_SIZE * 4) {
1019  /* make a room for unshifted items */
1020  capa = ARY_CAPA(ary);
1021  ary_make_shared(ary);
1022 
1023  head = sharedp = RARRAY_PTR(ary);
1024  goto makeroom;
1025  makeroom_if_need:
1026  if (head - sharedp < argc) {
1027  long room;
1028  makeroom:
1029  room = capa - new_len;
1030  room -= room >> 4;
1031  MEMMOVE(sharedp + argc + room, head, VALUE, len);
1032  head = sharedp + argc + room;
1033  }
1034  ARY_SET_PTR(ary, head - argc);
1035  }
1036  else {
1037  /* sliding items */
1038  MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
1039  }
1040 }
1041 
1042 /*
1043  * call-seq:
1044  * ary.unshift(obj, ...) -> ary
1045  *
1046  * Prepends objects to the front of +self+, moving other elements upwards.
1047  * See also Array#shift for the opposite effect.
1048  *
1049  * a = [ "b", "c", "d" ]
1050  * a.unshift("a") #=> ["a", "b", "c", "d"]
1051  * a.unshift(1, 2) #=> [ 1, 2, "a", "b", "c", "d"]
1052  */
1053 
1054 static VALUE
1056 {
1057  long len = RARRAY_LEN(ary);
1058 
1059  if (argc == 0) {
1060  rb_ary_modify_check(ary);
1061  return ary;
1062  }
1063 
1064  ary_ensure_room_for_unshift(ary, argc);
1065  MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
1066  ARY_SET_LEN(ary, len + argc);
1067  return ary;
1068 }
1069 
1070 VALUE
1072 {
1073  return rb_ary_unshift_m(1,&item,ary);
1074 }
1075 
1076 /* faster version - use this if you don't need to treat negative offset */
1077 static inline VALUE
1078 rb_ary_elt(VALUE ary, long offset)
1079 {
1080  if (RARRAY_LEN(ary) == 0) return Qnil;
1081  if (offset < 0 || RARRAY_LEN(ary) <= offset) {
1082  return Qnil;
1083  }
1084  return RARRAY_PTR(ary)[offset];
1085 }
1086 
1087 VALUE
1088 rb_ary_entry(VALUE ary, long offset)
1089 {
1090  if (offset < 0) {
1091  offset += RARRAY_LEN(ary);
1092  }
1093  return rb_ary_elt(ary, offset);
1094 }
1095 
1096 VALUE
1097 rb_ary_subseq(VALUE ary, long beg, long len)
1098 {
1099  VALUE klass;
1100 
1101  if (beg > RARRAY_LEN(ary)) return Qnil;
1102  if (beg < 0 || len < 0) return Qnil;
1103 
1104  if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
1105  len = RARRAY_LEN(ary) - beg;
1106  }
1107  klass = rb_obj_class(ary);
1108  if (len == 0) return ary_new(klass, 0);
1109 
1110  return ary_make_partial(ary, klass, beg, len);
1111 }
1112 
1113 /*
1114  * call-seq:
1115  * ary[index] -> obj or nil
1116  * ary[start, length] -> new_ary or nil
1117  * ary[range] -> new_ary or nil
1118  * ary.slice(index) -> obj or nil
1119  * ary.slice(start, length) -> new_ary or nil
1120  * ary.slice(range) -> new_ary or nil
1121  *
1122  * Element Reference --- Returns the element at +index+, or returns a
1123  * subarray starting at the +start+ index and continuing for +length+
1124  * elements, or returns a subarray specified by +range+ of indices.
1125  *
1126  * Negative indices count backward from the end of the array (-1 is the last
1127  * element). For +start+ and +range+ cases the starting index is just before
1128  * an element. Additionally, an empty array is returned when the starting
1129  * index for an element range is at the end of the array.
1130  *
1131  * Returns +nil+ if the index (or starting index) are out of range.
1132  *
1133  * a = [ "a", "b", "c", "d", "e" ]
1134  * a[2] + a[0] + a[1] #=> "cab"
1135  * a[6] #=> nil
1136  * a[1, 2] #=> [ "b", "c" ]
1137  * a[1..3] #=> [ "b", "c", "d" ]
1138  * a[4..7] #=> [ "e" ]
1139  * a[6..10] #=> nil
1140  * a[-3, 3] #=> [ "c", "d", "e" ]
1141  * # special cases
1142  * a[5] #=> nil
1143  * a[6, 1] #=> nil
1144  * a[5, 1] #=> []
1145  * a[5..10] #=> []
1146  *
1147  */
1148 
1149 VALUE
1151 {
1152  VALUE arg;
1153  long beg, len;
1154 
1155  if (argc == 2) {
1156  beg = NUM2LONG(argv[0]);
1157  len = NUM2LONG(argv[1]);
1158  if (beg < 0) {
1159  beg += RARRAY_LEN(ary);
1160  }
1161  return rb_ary_subseq(ary, beg, len);
1162  }
1163  if (argc != 1) {
1164  rb_scan_args(argc, argv, "11", NULL, NULL);
1165  }
1166  arg = argv[0];
1167  /* special case - speeding up */
1168  if (FIXNUM_P(arg)) {
1169  return rb_ary_entry(ary, FIX2LONG(arg));
1170  }
1171  /* check if idx is Range */
1172  switch (rb_range_beg_len(arg, &beg, &len, RARRAY_LEN(ary), 0)) {
1173  case Qfalse:
1174  break;
1175  case Qnil:
1176  return Qnil;
1177  default:
1178  return rb_ary_subseq(ary, beg, len);
1179  }
1180  return rb_ary_entry(ary, NUM2LONG(arg));
1181 }
1182 
1183 /*
1184  * call-seq:
1185  * ary.at(index) -> obj or nil
1186  *
1187  * Returns the element at +index+. A negative index counts from the end of
1188  * +self+. Returns +nil+ if the index is out of range. See also
1189  * Array#[].
1190  *
1191  * a = [ "a", "b", "c", "d", "e" ]
1192  * a.at(0) #=> "a"
1193  * a.at(-1) #=> "e"
1194  */
1195 
1196 static VALUE
1198 {
1199  return rb_ary_entry(ary, NUM2LONG(pos));
1200 }
1201 
1202 /*
1203  * call-seq:
1204  * ary.first -> obj or nil
1205  * ary.first(n) -> new_ary
1206  *
1207  * Returns the first element, or the first +n+ elements, of the array.
1208  * If the array is empty, the first form returns +nil+, and the
1209  * second form returns an empty array. See also Array#last for
1210  * the opposite effect.
1211  *
1212  * a = [ "q", "r", "s", "t" ]
1213  * a.first #=> "q"
1214  * a.first(2) #=> ["q", "r"]
1215  */
1216 
1217 static VALUE
1219 {
1220  if (argc == 0) {
1221  if (RARRAY_LEN(ary) == 0) return Qnil;
1222  return RARRAY_PTR(ary)[0];
1223  }
1224  else {
1225  return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
1226  }
1227 }
1228 
1229 /*
1230  * call-seq:
1231  * ary.last -> obj or nil
1232  * ary.last(n) -> new_ary
1233  *
1234  * Returns the last element(s) of +self+. If the array is empty,
1235  * the first form returns +nil+.
1236  *
1237  * See also Array#first for the opposite effect.
1238  *
1239  * a = [ "w", "x", "y", "z" ]
1240  * a.last #=> "z"
1241  * a.last(2) #=> ["y", "z"]
1242  */
1243 
1244 VALUE
1246 {
1247  if (argc == 0) {
1248  if (RARRAY_LEN(ary) == 0) return Qnil;
1249  return RARRAY_PTR(ary)[RARRAY_LEN(ary)-1];
1250  }
1251  else {
1252  return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
1253  }
1254 }
1255 
1256 /*
1257  * call-seq:
1258  * ary.fetch(index) -> obj
1259  * ary.fetch(index, default) -> obj
1260  * ary.fetch(index) { |index| block } -> obj
1261  *
1262  * Tries to return the element at position +index+, but throws an IndexError
1263  * exception if the referenced +index+ lies outside of the array bounds. This
1264  * error can be prevented by supplying a second argument, which will act as a
1265  * +default+ value.
1266  *
1267  * Alternatively, if a block is given it will only be executed when an
1268  * invalid +index+ is referenced. Negative values of +index+ count from the
1269  * end of the array.
1270  *
1271  * a = [ 11, 22, 33, 44 ]
1272  * a.fetch(1) #=> 22
1273  * a.fetch(-1) #=> 44
1274  * a.fetch(4, 'cat') #=> "cat"
1275  * a.fetch(100) { |i| puts "#{i} is out of bounds" }
1276  * #=> "100 is out of bounds"
1277  */
1278 
1279 static VALUE
1281 {
1282  VALUE pos, ifnone;
1283  long block_given;
1284  long idx;
1285 
1286  rb_scan_args(argc, argv, "11", &pos, &ifnone);
1287  block_given = rb_block_given_p();
1288  if (block_given && argc == 2) {
1289  rb_warn("block supersedes default value argument");
1290  }
1291  idx = NUM2LONG(pos);
1292 
1293  if (idx < 0) {
1294  idx += RARRAY_LEN(ary);
1295  }
1296  if (idx < 0 || RARRAY_LEN(ary) <= idx) {
1297  if (block_given) return rb_yield(pos);
1298  if (argc == 1) {
1299  rb_raise(rb_eIndexError, "index %ld outside of array bounds: %ld...%ld",
1300  idx - (idx < 0 ? RARRAY_LEN(ary) : 0), -RARRAY_LEN(ary), RARRAY_LEN(ary));
1301  }
1302  return ifnone;
1303  }
1304  return RARRAY_PTR(ary)[idx];
1305 }
1306 
1307 /*
1308  * call-seq:
1309  * ary.index(obj) -> int or nil
1310  * ary.index { |item| block } -> int or nil
1311  * ary.index -> Enumerator
1312  *
1313  * Returns the _index_ of the first object in +ary+ such that the object is
1314  * <code>==</code> to +obj+.
1315  *
1316  * If a block is given instead of an argument, returns the _index_ of the
1317  * first object for which the block returns +true+. Returns +nil+ if no
1318  * match is found.
1319  *
1320  * See also Array#rindex.
1321  *
1322  * An Enumerator is returned if neither a block nor argument is given.
1323  *
1324  * a = [ "a", "b", "c" ]
1325  * a.index("b") #=> 1
1326  * a.index("z") #=> nil
1327  * a.index { |x| x == "b" } #=> 1
1328  *
1329  * This is an alias of Array#find_index.
1330  */
1331 
1332 static VALUE
1334 {
1335  VALUE val;
1336  long i;
1337 
1338  if (argc == 0) {
1339  RETURN_ENUMERATOR(ary, 0, 0);
1340  for (i=0; i<RARRAY_LEN(ary); i++) {
1341  if (RTEST(rb_yield(RARRAY_PTR(ary)[i]))) {
1342  return LONG2NUM(i);
1343  }
1344  }
1345  return Qnil;
1346  }
1347  rb_scan_args(argc, argv, "1", &val);
1348  if (rb_block_given_p())
1349  rb_warn("given block not used");
1350  for (i=0; i<RARRAY_LEN(ary); i++) {
1351  if (rb_equal(RARRAY_PTR(ary)[i], val))
1352  return LONG2NUM(i);
1353  }
1354  return Qnil;
1355 }
1356 
1357 /*
1358  * call-seq:
1359  * ary.rindex(obj) -> int or nil
1360  * ary.rindex { |item| block } -> int or nil
1361  * ary.rindex -> Enumerator
1362  *
1363  * Returns the _index_ of the last object in +self+ <code>==</code> to +obj+.
1364  *
1365  * If a block is given instead of an argument, returns the _index_ of the
1366  * first object for which the block returns +true+, starting from the last
1367  * object.
1368  *
1369  * Returns +nil+ if no match is found.
1370  *
1371  * See also Array#index.
1372  *
1373  * If neither block nor argument is given, an Enumerator is returned instead.
1374  *
1375  * a = [ "a", "b", "b", "b", "c" ]
1376  * a.rindex("b") #=> 3
1377  * a.rindex("z") #=> nil
1378  * a.rindex { |x| x == "b" } #=> 3
1379  */
1380 
1381 static VALUE
1383 {
1384  VALUE val;
1385  long i = RARRAY_LEN(ary);
1386 
1387  if (argc == 0) {
1388  RETURN_ENUMERATOR(ary, 0, 0);
1389  while (i--) {
1390  if (RTEST(rb_yield(RARRAY_PTR(ary)[i])))
1391  return LONG2NUM(i);
1392  if (i > RARRAY_LEN(ary)) {
1393  i = RARRAY_LEN(ary);
1394  }
1395  }
1396  return Qnil;
1397  }
1398  rb_scan_args(argc, argv, "1", &val);
1399  if (rb_block_given_p())
1400  rb_warn("given block not used");
1401  while (i--) {
1402  if (rb_equal(RARRAY_PTR(ary)[i], val))
1403  return LONG2NUM(i);
1404  if (i > RARRAY_LEN(ary)) {
1405  i = RARRAY_LEN(ary);
1406  }
1407  }
1408  return Qnil;
1409 }
1410 
1411 VALUE
1413 {
1414  VALUE tmp = rb_check_array_type(obj);
1415 
1416  if (!NIL_P(tmp)) return tmp;
1417  return rb_ary_new3(1, obj);
1418 }
1419 
1420 static void
1421 rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
1422 {
1423  long rlen;
1424 
1425  if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
1426  if (beg < 0) {
1427  beg += RARRAY_LEN(ary);
1428  if (beg < 0) {
1429  rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
1430  beg - RARRAY_LEN(ary), -RARRAY_LEN(ary));
1431  }
1432  }
1433  if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
1434  len = RARRAY_LEN(ary) - beg;
1435  }
1436 
1437  if (rpl == Qundef) {
1438  rlen = 0;
1439  }
1440  else {
1441  rpl = rb_ary_to_ary(rpl);
1442  rlen = RARRAY_LEN(rpl);
1443  }
1444  if (beg >= RARRAY_LEN(ary)) {
1445  if (beg > ARY_MAX_SIZE - rlen) {
1446  rb_raise(rb_eIndexError, "index %ld too big", beg);
1447  }
1448  ary_ensure_room_for_push(ary, rlen-len); /* len is 0 or negative */
1449  len = beg + rlen;
1450  rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), beg - RARRAY_LEN(ary));
1451  if (rlen > 0) {
1452  MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
1453  }
1454  ARY_SET_LEN(ary, len);
1455  }
1456  else {
1457  long alen;
1458 
1459  rb_ary_modify(ary);
1460  alen = RARRAY_LEN(ary) + rlen - len;
1461  if (alen >= ARY_CAPA(ary)) {
1462  ary_double_capa(ary, alen);
1463  }
1464 
1465  if (len != rlen) {
1466  MEMMOVE(RARRAY_PTR(ary) + beg + rlen, RARRAY_PTR(ary) + beg + len,
1467  VALUE, RARRAY_LEN(ary) - (beg + len));
1468  ARY_SET_LEN(ary, alen);
1469  }
1470  if (rlen > 0) {
1471  MEMMOVE(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
1472  }
1473  }
1474  RB_GC_GUARD(rpl);
1475 }
1476 
1477 void
1479 {
1480  long capa;
1481 
1482  rb_ary_modify_check(ary);
1483  if (ARY_SHARED_P(ary)) {
1484  rb_raise(rb_eRuntimeError, "can't set length of shared ");
1485  }
1486  if (len > (capa = (long)ARY_CAPA(ary))) {
1487  rb_bug("probable buffer overflow: %ld for %ld", len, capa);
1488  }
1489  ARY_SET_LEN(ary, len);
1490 }
1491 
1500 VALUE
1502 {
1503  long olen;
1504 
1505  rb_ary_modify(ary);
1506  olen = RARRAY_LEN(ary);
1507  if (len == olen) return ary;
1508  if (len > ARY_MAX_SIZE) {
1509  rb_raise(rb_eIndexError, "index %ld too big", len);
1510  }
1511  if (len > olen) {
1512  if (len >= ARY_CAPA(ary)) {
1513  ary_double_capa(ary, len);
1514  }
1515  rb_mem_clear(RARRAY_PTR(ary) + olen, len - olen);
1516  ARY_SET_LEN(ary, len);
1517  }
1518  else if (ARY_EMBED_P(ary)) {
1519  ARY_SET_EMBED_LEN(ary, len);
1520  }
1521  else if (len <= RARRAY_EMBED_LEN_MAX) {
1523  MEMCPY(tmp, ARY_HEAP_PTR(ary), VALUE, len);
1524  ary_discard(ary);
1525  MEMCPY(ARY_EMBED_PTR(ary), tmp, VALUE, len);
1526  ARY_SET_EMBED_LEN(ary, len);
1527  }
1528  else {
1529  if (olen > len + ARY_DEFAULT_SIZE) {
1530  REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, len);
1531  ARY_SET_CAPA(ary, len);
1532  }
1533  ARY_SET_HEAP_LEN(ary, len);
1534  }
1535  return ary;
1536 }
1537 
1538 /*
1539  * call-seq:
1540  * ary[index] = obj -> obj
1541  * ary[start, length] = obj or other_ary or nil -> obj or other_ary or nil
1542  * ary[range] = obj or other_ary or nil -> obj or other_ary or nil
1543  *
1544  * Element Assignment --- Sets the element at +index+, or replaces a subarray
1545  * from the +start+ index for +length+ elements, or replaces a subarray
1546  * specified by the +range+ of indices.
1547  *
1548  * If indices are greater than the current capacity of the array, the array
1549  * grows automatically. Elements are inserted into the array at +start+ if
1550  * +length+ is zero.
1551  *
1552  * Negative indices will count backward from the end of the array. For
1553  * +start+ and +range+ cases the starting index is just before an element.
1554  *
1555  * An IndexError is raised if a negative index points past the beginning of
1556  * the array.
1557  *
1558  * See also Array#push, and Array#unshift.
1559  *
1560  * a = Array.new
1561  * a[4] = "4"; #=> [nil, nil, nil, nil, "4"]
1562  * a[0, 3] = [ 'a', 'b', 'c' ] #=> ["a", "b", "c", nil, "4"]
1563  * a[1..2] = [ 1, 2 ] #=> ["a", 1, 2, nil, "4"]
1564  * a[0, 2] = "?" #=> ["?", 2, nil, "4"]
1565  * a[0..2] = "A" #=> ["A", "4"]
1566  * a[-1] = "Z" #=> ["A", "Z"]
1567  * a[1..-1] = nil #=> ["A", nil]
1568  * a[1..-1] = [] #=> ["A"]
1569  * a[0, 0] = [ 1, 2 ] #=> [1, 2, "A"]
1570  * a[3, 0] = "B" #=> [1, 2, "A", "B"]
1571  */
1572 
1573 static VALUE
1575 {
1576  long offset, beg, len;
1577 
1578  if (argc == 3) {
1579  rb_ary_modify_check(ary);
1580  beg = NUM2LONG(argv[0]);
1581  len = NUM2LONG(argv[1]);
1582  rb_ary_splice(ary, beg, len, argv[2]);
1583  return argv[2];
1584  }
1585  rb_check_arity(argc, 2, 2);
1586  rb_ary_modify_check(ary);
1587  if (FIXNUM_P(argv[0])) {
1588  offset = FIX2LONG(argv[0]);
1589  goto fixnum;
1590  }
1591  if (rb_range_beg_len(argv[0], &beg, &len, RARRAY_LEN(ary), 1)) {
1592  /* check if idx is Range */
1593  rb_ary_splice(ary, beg, len, argv[1]);
1594  return argv[1];
1595  }
1596 
1597  offset = NUM2LONG(argv[0]);
1598 fixnum:
1599  rb_ary_store(ary, offset, argv[1]);
1600  return argv[1];
1601 }
1602 
1603 /*
1604  * call-seq:
1605  * ary.insert(index, obj...) -> ary
1606  *
1607  * Inserts the given values before the element with the given +index+.
1608  *
1609  * Negative indices count backwards from the end of the array, where +-1+ is
1610  * the last element.
1611  *
1612  * a = %w{ a b c d }
1613  * a.insert(2, 99) #=> ["a", "b", 99, "c", "d"]
1614  * a.insert(-2, 1, 2, 3) #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
1615  */
1616 
1617 static VALUE
1619 {
1620  long pos;
1621 
1623  rb_ary_modify_check(ary);
1624  if (argc == 1) return ary;
1625  pos = NUM2LONG(argv[0]);
1626  if (pos == -1) {
1627  pos = RARRAY_LEN(ary);
1628  }
1629  if (pos < 0) {
1630  pos++;
1631  }
1632  rb_ary_splice(ary, pos, 0, rb_ary_new4(argc - 1, argv + 1));
1633  return ary;
1634 }
1635 
1636 static VALUE
1638 
1639 /*
1640  * call-seq:
1641  * ary.each { |item| block } -> ary
1642  * ary.each -> Enumerator
1643  *
1644  * Calls the given block once for each element in +self+, passing that element
1645  * as a parameter.
1646  *
1647  * An Enumerator is returned if no block is given.
1648  *
1649  * a = [ "a", "b", "c" ]
1650  * a.each {|x| print x, " -- " }
1651  *
1652  * produces:
1653  *
1654  * a -- b -- c --
1655  */
1656 
1657 VALUE
1659 {
1660  long i;
1661  volatile VALUE ary = array;
1662 
1664  for (i=0; i<RARRAY_LEN(ary); i++) {
1665  rb_yield(RARRAY_PTR(ary)[i]);
1666  }
1667  return ary;
1668 }
1669 
1670 /*
1671  * call-seq:
1672  * ary.each_index { |index| block } -> ary
1673  * ary.each_index -> Enumerator
1674  *
1675  * Same as Array#each, but passes the +index+ of the element instead of the
1676  * element itself.
1677  *
1678  * An Enumerator is returned if no block is given.
1679  *
1680  * a = [ "a", "b", "c" ]
1681  * a.each_index {|x| print x, " -- " }
1682  *
1683  * produces:
1684  *
1685  * 0 -- 1 -- 2 --
1686  */
1687 
1688 static VALUE
1690 {
1691  long i;
1693 
1694  for (i=0; i<RARRAY_LEN(ary); i++) {
1695  rb_yield(LONG2NUM(i));
1696  }
1697  return ary;
1698 }
1699 
1700 /*
1701  * call-seq:
1702  * ary.reverse_each { |item| block } -> ary
1703  * ary.reverse_each -> Enumerator
1704  *
1705  * Same as Array#each, but traverses +self+ in reverse order.
1706  *
1707  * a = [ "a", "b", "c" ]
1708  * a.reverse_each {|x| print x, " " }
1709  *
1710  * produces:
1711  *
1712  * c b a
1713  */
1714 
1715 static VALUE
1717 {
1718  long len;
1719 
1721  len = RARRAY_LEN(ary);
1722  while (len--) {
1723  rb_yield(RARRAY_PTR(ary)[len]);
1724  if (RARRAY_LEN(ary) < len) {
1725  len = RARRAY_LEN(ary);
1726  }
1727  }
1728  return ary;
1729 }
1730 
1731 /*
1732  * call-seq:
1733  * ary.length -> int
1734  *
1735  * Returns the number of elements in +self+. May be zero.
1736  *
1737  * [ 1, 2, 3, 4, 5 ].length #=> 5
1738  * [].length #=> 0
1739  */
1740 
1741 static VALUE
1743 {
1744  long len = RARRAY_LEN(ary);
1745  return LONG2NUM(len);
1746 }
1747 
1748 /*
1749  * call-seq:
1750  * ary.empty? -> true or false
1751  *
1752  * Returns +true+ if +self+ contains no elements.
1753  *
1754  * [].empty? #=> true
1755  */
1756 
1757 static VALUE
1759 {
1760  if (RARRAY_LEN(ary) == 0)
1761  return Qtrue;
1762  return Qfalse;
1763 }
1764 
1765 VALUE
1767 {
1768  VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
1769  MEMCPY(RARRAY_PTR(dup), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
1770  ARY_SET_LEN(dup, RARRAY_LEN(ary));
1771  return dup;
1772 }
1773 
1774 VALUE
1776 {
1777  return rb_ary_new4(RARRAY_LEN(ary), RARRAY_PTR(ary));
1778 }
1779 
1780 extern VALUE rb_output_fs;
1781 
1782 static void ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first);
1783 
1784 static VALUE
1786 {
1787  VALUE *arg = (VALUE *)argp;
1788  VALUE ary = arg[0];
1789  VALUE sep = arg[1];
1790  VALUE result = arg[2];
1791  int *first = (int *)arg[3];
1792 
1793  if (recur) {
1794  rb_raise(rb_eArgError, "recursive array join");
1795  }
1796  else {
1797  ary_join_1(obj, ary, sep, 0, result, first);
1798  }
1799  return Qnil;
1800 }
1801 
1802 static void
1804 {
1805  long i;
1806  VALUE val;
1807 
1808  if (max > 0) rb_enc_copy(result, RARRAY_PTR(ary)[0]);
1809  for (i=0; i<max; i++) {
1810  val = RARRAY_PTR(ary)[i];
1811  if (i > 0 && !NIL_P(sep))
1812  rb_str_buf_append(result, sep);
1813  rb_str_buf_append(result, val);
1814  if (OBJ_TAINTED(val)) OBJ_TAINT(result);
1815  if (OBJ_UNTRUSTED(val)) OBJ_TAINT(result);
1816  }
1817 }
1818 
1819 static void
1820 ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first)
1821 {
1822  VALUE val, tmp;
1823 
1824  for (; i<RARRAY_LEN(ary); i++) {
1825  if (i > 0 && !NIL_P(sep))
1826  rb_str_buf_append(result, sep);
1827 
1828  val = RARRAY_PTR(ary)[i];
1829  switch (TYPE(val)) {
1830  case T_STRING:
1831  str_join:
1832  rb_str_buf_append(result, val);
1833  *first = FALSE;
1834  break;
1835  case T_ARRAY:
1836  obj = val;
1837  ary_join:
1838  if (val == ary) {
1839  rb_raise(rb_eArgError, "recursive array join");
1840  }
1841  else {
1842  VALUE args[4];
1843 
1844  args[0] = val;
1845  args[1] = sep;
1846  args[2] = result;
1847  args[3] = (VALUE)first;
1848  rb_exec_recursive(recursive_join, obj, (VALUE)args);
1849  }
1850  break;
1851  default:
1852  tmp = rb_check_string_type(val);
1853  if (!NIL_P(tmp)) {
1854  val = tmp;
1855  goto str_join;
1856  }
1857  tmp = rb_check_convert_type(val, T_ARRAY, "Array", "to_ary");
1858  if (!NIL_P(tmp)) {
1859  obj = val;
1860  val = tmp;
1861  goto ary_join;
1862  }
1863  val = rb_obj_as_string(val);
1864  if (*first) {
1865  rb_enc_copy(result, val);
1866  *first = FALSE;
1867  }
1868  goto str_join;
1869  }
1870  }
1871 }
1872 
1873 VALUE
1875 {
1876  long len = 1, i;
1877  int taint = FALSE;
1878  int untrust = FALSE;
1879  VALUE val, tmp, result;
1880 
1881  if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new(0, 0);
1882  if (OBJ_TAINTED(ary)) taint = TRUE;
1883  if (OBJ_UNTRUSTED(ary)) untrust = TRUE;
1884 
1885  if (!NIL_P(sep)) {
1886  StringValue(sep);
1887  len += RSTRING_LEN(sep) * (RARRAY_LEN(ary) - 1);
1888  }
1889  for (i=0; i<RARRAY_LEN(ary); i++) {
1890  val = RARRAY_PTR(ary)[i];
1891  tmp = rb_check_string_type(val);
1892 
1893  if (NIL_P(tmp) || tmp != val) {
1894  int first;
1895  result = rb_str_buf_new(len + (RARRAY_LEN(ary)-i)*10);
1897  if (taint) OBJ_TAINT(result);
1898  if (untrust) OBJ_UNTRUST(result);
1899  ary_join_0(ary, sep, i, result);
1900  first = i == 0;
1901  ary_join_1(ary, ary, sep, i, result, &first);
1902  return result;
1903  }
1904 
1905  len += RSTRING_LEN(tmp);
1906  }
1907 
1908  result = rb_str_buf_new(len);
1909  if (taint) OBJ_TAINT(result);
1910  if (untrust) OBJ_UNTRUST(result);
1911  ary_join_0(ary, sep, RARRAY_LEN(ary), result);
1912 
1913  return result;
1914 }
1915 
1916 /*
1917  * call-seq:
1918  * ary.join(separator=$,) -> str
1919  *
1920  * Returns a string created by converting each element of the array to
1921  * a string, separated by the given +separator+.
1922  * If the +separator+ is +nil+, it uses current $,.
1923  * If both the +separator+ and $, are nil, it uses empty string.
1924  *
1925  * [ "a", "b", "c" ].join #=> "abc"
1926  * [ "a", "b", "c" ].join("-") #=> "a-b-c"
1927  */
1928 
1929 static VALUE
1931 {
1932  VALUE sep;
1933 
1934  rb_scan_args(argc, argv, "01", &sep);
1935  if (NIL_P(sep)) sep = rb_output_fs;
1936 
1937  return rb_ary_join(ary, sep);
1938 }
1939 
1940 static VALUE
1942 {
1943  int tainted = OBJ_TAINTED(ary);
1944  int untrust = OBJ_UNTRUSTED(ary);
1945  long i;
1946  VALUE s, str;
1947 
1948  if (recur) return rb_usascii_str_new_cstr("[...]");
1949  str = rb_str_buf_new2("[");
1950  for (i=0; i<RARRAY_LEN(ary); i++) {
1951  s = rb_inspect(RARRAY_PTR(ary)[i]);
1952  if (OBJ_TAINTED(s)) tainted = TRUE;
1953  if (OBJ_UNTRUSTED(s)) untrust = TRUE;
1954  if (i > 0) rb_str_buf_cat2(str, ", ");
1955  else rb_enc_copy(str, s);
1956  rb_str_buf_append(str, s);
1957  }
1958  rb_str_buf_cat2(str, "]");
1959  if (tainted) OBJ_TAINT(str);
1960  if (untrust) OBJ_UNTRUST(str);
1961  return str;
1962 }
1963 
1964 /*
1965  * call-seq:
1966  * ary.inspect -> string
1967  * ary.to_s -> string
1968  *
1969  * Creates a string representation of +self+.
1970  *
1971  * [ "a", "b", "c" ].to_s #=> "[\"a\", \"b\", \"c\"]"
1972  */
1973 
1974 static VALUE
1976 {
1977  if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new2("[]");
1978  return rb_exec_recursive(inspect_ary, ary, 0);
1979 }
1980 
1981 VALUE
1983 {
1984  return rb_ary_inspect(ary);
1985 }
1986 
1987 /*
1988  * call-seq:
1989  * ary.to_a -> ary
1990  *
1991  * Returns +self+.
1992  *
1993  * If called on a subclass of Array, converts the receiver to an Array object.
1994  */
1995 
1996 static VALUE
1998 {
1999  if (rb_obj_class(ary) != rb_cArray) {
2000  VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
2001  rb_ary_replace(dup, ary);
2002  return dup;
2003  }
2004  return ary;
2005 }
2006 
2007 /*
2008  * call-seq:
2009  * ary.to_ary -> ary
2010  *
2011  * Returns +self+.
2012  */
2013 
2014 static VALUE
2016 {
2017  return ary;
2018 }
2019 
2020 static void
2022 {
2023  while (p1 < p2) {
2024  VALUE tmp = *p1;
2025  *p1++ = *p2;
2026  *p2-- = tmp;
2027  }
2028 }
2029 
2030 VALUE
2032 {
2033  VALUE *p1, *p2;
2034 
2035  rb_ary_modify(ary);
2036  if (RARRAY_LEN(ary) > 1) {
2037  p1 = RARRAY_PTR(ary);
2038  p2 = p1 + RARRAY_LEN(ary) - 1; /* points last item */
2039  ary_reverse(p1, p2);
2040  }
2041  return ary;
2042 }
2043 
2044 /*
2045  * call-seq:
2046  * ary.reverse! -> ary
2047  *
2048  * Reverses +self+ in place.
2049  *
2050  * a = [ "a", "b", "c" ]
2051  * a.reverse! #=> ["c", "b", "a"]
2052  * a #=> ["c", "b", "a"]
2053  */
2054 
2055 static VALUE
2057 {
2058  return rb_ary_reverse(ary);
2059 }
2060 
2061 /*
2062  * call-seq:
2063  * ary.reverse -> new_ary
2064  *
2065  * Returns a new array containing +self+'s elements in reverse order.
2066  *
2067  * [ "a", "b", "c" ].reverse #=> ["c", "b", "a"]
2068  * [ 1 ].reverse #=> [1]
2069  */
2070 
2071 static VALUE
2073 {
2074  long len = RARRAY_LEN(ary);
2075  VALUE dup = rb_ary_new2(len);
2076 
2077  if (len > 0) {
2078  VALUE *p1 = RARRAY_PTR(ary);
2079  VALUE *p2 = RARRAY_PTR(dup) + len - 1;
2080  do *p2-- = *p1++; while (--len > 0);
2081  }
2082  ARY_SET_LEN(dup, RARRAY_LEN(ary));
2083  return dup;
2084 }
2085 
2086 static inline long
2087 rotate_count(long cnt, long len)
2088 {
2089  return (cnt < 0) ? (len - (~cnt % len) - 1) : (cnt % len);
2090 }
2091 
2092 VALUE
2094 {
2095  rb_ary_modify(ary);
2096 
2097  if (cnt != 0) {
2098  VALUE *ptr = RARRAY_PTR(ary);
2099  long len = RARRAY_LEN(ary);
2100 
2101  if (len > 0 && (cnt = rotate_count(cnt, len)) > 0) {
2102  --len;
2103  if (cnt < len) ary_reverse(ptr + cnt, ptr + len);
2104  if (--cnt > 0) ary_reverse(ptr, ptr + cnt);
2105  if (len > 0) ary_reverse(ptr, ptr + len);
2106  return ary;
2107  }
2108  }
2109 
2110  return Qnil;
2111 }
2112 
2113 /*
2114  * call-seq:
2115  * ary.rotate!(count=1) -> ary
2116  *
2117  * Rotates +self+ in place so that the element at +count+ comes first, and
2118  * returns +self+.
2119  *
2120  * If +count+ is negative then it rotates in the opposite direction, starting
2121  * from the end of the array where +-1+ is the last element.
2122  *
2123  * a = [ "a", "b", "c", "d" ]
2124  * a.rotate! #=> ["b", "c", "d", "a"]
2125  * a #=> ["b", "c", "d", "a"]
2126  * a.rotate!(2) #=> ["d", "a", "b", "c"]
2127  * a.rotate!(-3) #=> ["a", "b", "c", "d"]
2128  */
2129 
2130 static VALUE
2132 {
2133  long n = 1;
2134 
2135  switch (argc) {
2136  case 1: n = NUM2LONG(argv[0]);
2137  case 0: break;
2138  default: rb_scan_args(argc, argv, "01", NULL);
2139  }
2140  rb_ary_rotate(ary, n);
2141  return ary;
2142 }
2143 
2144 /*
2145  * call-seq:
2146  * ary.rotate(count=1) -> new_ary
2147  *
2148  * Returns a new array by rotating +self+ so that the element at +count+ is
2149  * the first element of the new array.
2150  *
2151  * If +count+ is negative then it rotates in the opposite direction, starting
2152  * from the end of +self+ where +-1+ is the last element.
2153  *
2154  * a = [ "a", "b", "c", "d" ]
2155  * a.rotate #=> ["b", "c", "d", "a"]
2156  * a #=> ["a", "b", "c", "d"]
2157  * a.rotate(2) #=> ["c", "d", "a", "b"]
2158  * a.rotate(-3) #=> ["b", "c", "d", "a"]
2159  */
2160 
2161 static VALUE
2163 {
2164  VALUE rotated, *ptr, *ptr2;
2165  long len, cnt = 1;
2166 
2167  switch (argc) {
2168  case 1: cnt = NUM2LONG(argv[0]);
2169  case 0: break;
2170  default: rb_scan_args(argc, argv, "01", NULL);
2171  }
2172 
2173  len = RARRAY_LEN(ary);
2174  rotated = rb_ary_new2(len);
2175  if (len > 0) {
2176  cnt = rotate_count(cnt, len);
2177  ptr = RARRAY_PTR(ary);
2178  ptr2 = RARRAY_PTR(rotated);
2179  len -= cnt;
2180  MEMCPY(ptr2, ptr + cnt, VALUE, len);
2181  MEMCPY(ptr2 + len, ptr, VALUE, cnt);
2182  }
2183  ARY_SET_LEN(rotated, RARRAY_LEN(ary));
2184  return rotated;
2185 }
2186 
2191 };
2192 
2193 enum {
2197 };
2198 
2199 #define STRING_P(s) (RB_TYPE_P((s), T_STRING) && CLASS_OF(s) == rb_cString)
2200 
2201 #define SORT_OPTIMIZABLE_BIT(type) (1U << TOKEN_PASTE(sort_opt_,type))
2202 #define SORT_OPTIMIZABLE(data, type) \
2203  (((data)->opt_inited & SORT_OPTIMIZABLE_BIT(type)) ? \
2204  ((data)->opt_methods & SORT_OPTIMIZABLE_BIT(type)) : \
2205  (((data)->opt_inited |= SORT_OPTIMIZABLE_BIT(type)), \
2206  rb_method_basic_definition_p(TOKEN_PASTE(rb_c,type), id_cmp) && \
2207  ((data)->opt_methods |= SORT_OPTIMIZABLE_BIT(type))))
2208 
2209 static VALUE
2211 {
2212  if (RBASIC(ary)->klass) {
2213  rb_raise(rb_eRuntimeError, "sort reentered");
2214  }
2215  return Qnil;
2216 }
2217 
2218 static int
2219 sort_1(const void *ap, const void *bp, void *dummy)
2220 {
2221  struct ary_sort_data *data = dummy;
2222  VALUE retval = sort_reentered(data->ary);
2223  VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2224  int n;
2225 
2226  retval = rb_yield_values(2, a, b);
2227  n = rb_cmpint(retval, a, b);
2228  sort_reentered(data->ary);
2229  return n;
2230 }
2231 
2232 static int
2233 sort_2(const void *ap, const void *bp, void *dummy)
2234 {
2235  struct ary_sort_data *data = dummy;
2236  VALUE retval = sort_reentered(data->ary);
2237  VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2238  int n;
2239 
2240  if (FIXNUM_P(a) && FIXNUM_P(b) && SORT_OPTIMIZABLE(data, Fixnum)) {
2241  if ((long)a > (long)b) return 1;
2242  if ((long)a < (long)b) return -1;
2243  return 0;
2244  }
2245  if (STRING_P(a) && STRING_P(b) && SORT_OPTIMIZABLE(data, String)) {
2246  return rb_str_cmp(a, b);
2247  }
2248 
2249  retval = rb_funcall(a, id_cmp, 1, b);
2250  n = rb_cmpint(retval, a, b);
2251  sort_reentered(data->ary);
2252 
2253  return n;
2254 }
2255 
2256 /*
2257  * call-seq:
2258  * ary.sort! -> ary
2259  * ary.sort! { |a, b| block } -> ary
2260  *
2261  * Sorts +self+ in place.
2262  *
2263  * Comparisons for the sort will be done using the <code><=></code> operator
2264  * or using an optional code block.
2265  *
2266  * The block must implement a comparison between +a+ and +b+, and return
2267  * +-1+, when +a+ follows +b+, +0+ when +a+ and +b+ are equivalent, or ++1+
2268  * if +b+ follows +a+.
2269  *
2270  * See also Enumerable#sort_by.
2271  *
2272  * a = [ "d", "a", "e", "c", "b" ]
2273  * a.sort! #=> ["a", "b", "c", "d", "e"]
2274  * a.sort! { |x,y| y <=> x } #=> ["e", "d", "c", "b", "a"]
2275  */
2276 
2277 VALUE
2279 {
2280  rb_ary_modify(ary);
2281  assert(!ARY_SHARED_P(ary));
2282  if (RARRAY_LEN(ary) > 1) {
2283  VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
2284  struct ary_sort_data data;
2285  long len = RARRAY_LEN(ary);
2286 
2287  RBASIC(tmp)->klass = 0;
2288  data.ary = tmp;
2289  data.opt_methods = 0;
2290  data.opt_inited = 0;
2291  ruby_qsort(RARRAY_PTR(tmp), len, sizeof(VALUE),
2292  rb_block_given_p()?sort_1:sort_2, &data);
2293 
2294  if (ARY_EMBED_P(tmp)) {
2295  assert(ARY_EMBED_P(tmp));
2296  if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */
2297  rb_ary_unshare(ary);
2298  }
2299  FL_SET_EMBED(ary);
2300  MEMCPY(RARRAY_PTR(ary), ARY_EMBED_PTR(tmp), VALUE, ARY_EMBED_LEN(tmp));
2301  ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
2302  }
2303  else {
2304  assert(!ARY_EMBED_P(tmp));
2305  if (ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
2306  assert(!ARY_EMBED_P(ary));
2307  FL_UNSET_SHARED(ary);
2308  ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2309  }
2310  else {
2311  assert(!ARY_SHARED_P(tmp));
2312  if (ARY_EMBED_P(ary)) {
2313  FL_UNSET_EMBED(ary);
2314  }
2315  else if (ARY_SHARED_P(ary)) {
2316  /* ary might be destructively operated in the given block */
2317  rb_ary_unshare(ary);
2318  }
2319  else {
2320  xfree(ARY_HEAP_PTR(ary));
2321  }
2322  ARY_SET_PTR(ary, RARRAY_PTR(tmp));
2323  ARY_SET_HEAP_LEN(ary, len);
2324  ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2325  }
2326  /* tmp was lost ownership for the ptr */
2327  FL_UNSET(tmp, FL_FREEZE);
2328  FL_SET_EMBED(tmp);
2329  ARY_SET_EMBED_LEN(tmp, 0);
2330  FL_SET(tmp, FL_FREEZE);
2331  }
2332  /* tmp will be GC'ed. */
2333  RBASIC(tmp)->klass = rb_cArray;
2334  }
2335  return ary;
2336 }
2337 
2338 /*
2339  * call-seq:
2340  * ary.sort -> new_ary
2341  * ary.sort { |a, b| block } -> new_ary
2342  *
2343  * Returns a new array created by sorting +self+.
2344  *
2345  * Comparisons for the sort will be done using the <code><=></code> operator
2346  * or using an optional code block.
2347  *
2348  * The block must implement a comparison between +a+ and +b+, and return
2349  * +-1+, when +a+ follows +b+, +0+ when +a+ and +b+ are equivalent, or ++1+
2350  * if +b+ follows +a+.
2351  *
2352  *
2353  * See also Enumerable#sort_by.
2354  *
2355  * a = [ "d", "a", "e", "c", "b" ]
2356  * a.sort #=> ["a", "b", "c", "d", "e"]
2357  * a.sort { |x,y| y <=> x } #=> ["e", "d", "c", "b", "a"]
2358  */
2359 
2360 VALUE
2362 {
2363  ary = rb_ary_dup(ary);
2364  rb_ary_sort_bang(ary);
2365  return ary;
2366 }
2367 
2368 /*
2369  * call-seq:
2370  * ary.bsearch {|x| block } -> elem
2371  *
2372  * By using binary search, finds a value from this array which meets
2373  * the given condition in O(log n) where n is the size of the array.
2374  *
2375  * You can use this method in two use cases: a find-minimum mode and
2376  * a find-any mode. In either case, the elements of the array must be
2377  * monotone (or sorted) with respect to the block.
2378  *
2379  * In find-minimum mode (this is a good choice for typical use case),
2380  * the block must return true or false, and there must be an index i
2381  * (0 <= i <= ary.size) so that:
2382  *
2383  * - the block returns false for any element whose index is less than
2384  * i, and
2385  * - the block returns true for any element whose index is greater
2386  * than or equal to i.
2387  *
2388  * This method returns the i-th element. If i is equal to ary.size,
2389  * it returns nil.
2390  *
2391  * ary = [0, 4, 7, 10, 12]
2392  * ary.bsearch {|x| x >= 4 } #=> 4
2393  * ary.bsearch {|x| x >= 6 } #=> 7
2394  * ary.bsearch {|x| x >= -1 } #=> 0
2395  * ary.bsearch {|x| x >= 100 } #=> nil
2396  *
2397  * In find-any mode (this behaves like libc's bsearch(3)), the block
2398  * must return a number, and there must be two indices i and j
2399  * (0 <= i <= j <= ary.size) so that:
2400  *
2401  * - the block returns a positive number for ary[k] if 0 <= k < i,
2402  * - the block returns zero for ary[k] if i <= k < j, and
2403  * - the block returns a negative number for ary[k] if
2404  * j <= k < ary.size.
2405  *
2406  * Under this condition, this method returns any element whose index
2407  * is within i...j. If i is equal to j (i.e., there is no element
2408  * that satisfies the block), this method returns nil.
2409  *
2410  * ary = [0, 4, 7, 10, 12]
2411  * # try to find v such that 4 <= v < 8
2412  * ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7
2413  * # try to find v such that 8 <= v < 10
2414  * ary.bsearch {|x| 4 - x / 2 } #=> nil
2415  *
2416  * You must not mix the two modes at a time; the block must always
2417  * return either true/false, or always return a number. It is
2418  * undefined which value is actually picked up at each iteration.
2419  */
2420 
2421 static VALUE
2423 {
2424  long low = 0, high = RARRAY_LEN(ary), mid;
2425  int smaller = 0, satisfied = 0;
2426  VALUE v, val;
2427 
2428  RETURN_ENUMERATOR(ary, 0, 0);
2429  while (low < high) {
2430  mid = low + ((high - low) / 2);
2431  val = rb_ary_entry(ary, mid);
2432  v = rb_yield(val);
2433  if (FIXNUM_P(v)) {
2434  if (FIX2INT(v) == 0) return val;
2435  smaller = FIX2INT(v) < 0;
2436  }
2437  else if (v == Qtrue) {
2438  satisfied = 1;
2439  smaller = 1;
2440  }
2441  else if (v == Qfalse || v == Qnil) {
2442  smaller = 0;
2443  }
2444  else if (rb_obj_is_kind_of(v, rb_cNumeric)) {
2445  switch (rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0))) {
2446  case 0: return val;
2447  case 1: smaller = 1; break;
2448  case -1: smaller = 0;
2449  }
2450  }
2451  else {
2452  rb_raise(rb_eTypeError, "wrong argument type %s"
2453  " (must be numeric, true, false or nil)",
2454  rb_obj_classname(v));
2455  }
2456  if (smaller) {
2457  high = mid;
2458  }
2459  else {
2460  low = mid + 1;
2461  }
2462  }
2463  if (low == RARRAY_LEN(ary)) return Qnil;
2464  if (!satisfied) return Qnil;
2465  return rb_ary_entry(ary, low);
2466 }
2467 
2468 
2469 static VALUE
2471 {
2472  return rb_yield(i);
2473 }
2474 
2475 /*
2476  * call-seq:
2477  * ary.sort_by! { |obj| block } -> ary
2478  * ary.sort_by! -> Enumerator
2479  *
2480  * Sorts +self+ in place using a set of keys generated by mapping the
2481  * values in +self+ through the given block.
2482  *
2483  * If no block is given, an Enumerator is returned instead.
2484  *
2485  */
2486 
2487 static VALUE
2489 {
2490  VALUE sorted;
2491 
2493  rb_ary_modify(ary);
2494  sorted = rb_block_call(ary, rb_intern("sort_by"), 0, 0, sort_by_i, 0);
2495  rb_ary_replace(ary, sorted);
2496  return ary;
2497 }
2498 
2499 
2500 /*
2501  * call-seq:
2502  * ary.collect { |item| block } -> new_ary
2503  * ary.map { |item| block } -> new_ary
2504  * ary.collect -> Enumerator
2505  * ary.map -> Enumerator
2506  *
2507  * Invokes the given block once for each element of +self+.
2508  *
2509  * Creates a new array containing the values returned by the block.
2510  *
2511  * See also Enumerable#collect.
2512  *
2513  * If no block is given, an Enumerator is returned instead.
2514  *
2515  * a = [ "a", "b", "c", "d" ]
2516  * a.map { |x| x + "!" } #=> ["a!", "b!", "c!", "d!"]
2517  * a #=> ["a", "b", "c", "d"]
2518  */
2519 
2520 static VALUE
2522 {
2523  long i;
2524  VALUE collect;
2525 
2527  collect = rb_ary_new2(RARRAY_LEN(ary));
2528  for (i = 0; i < RARRAY_LEN(ary); i++) {
2529  rb_ary_push(collect, rb_yield(RARRAY_PTR(ary)[i]));
2530  }
2531  return collect;
2532 }
2533 
2534 
2535 /*
2536  * call-seq:
2537  * ary.collect! {|item| block } -> ary
2538  * ary.map! {|item| block } -> ary
2539  * ary.collect! -> Enumerator
2540  * ary.map! -> Enumerator
2541  *
2542  * Invokes the given block once for each element of +self+, replacing the
2543  * element with the value returned by the block.
2544  *
2545  * See also Enumerable#collect.
2546  *
2547  * If no block is given, an Enumerator is returned instead.
2548  *
2549  * a = [ "a", "b", "c", "d" ]
2550  * a.map! {|x| x + "!" }
2551  * a #=> [ "a!", "b!", "c!", "d!" ]
2552  */
2553 
2554 static VALUE
2556 {
2557  long i;
2558 
2560  rb_ary_modify(ary);
2561  for (i = 0; i < RARRAY_LEN(ary); i++) {
2562  rb_ary_store(ary, i, rb_yield(RARRAY_PTR(ary)[i]));
2563  }
2564  return ary;
2565 }
2566 
2567 VALUE
2568 rb_get_values_at(VALUE obj, long olen, int argc, VALUE *argv, VALUE (*func) (VALUE, long))
2569 {
2570  VALUE result = rb_ary_new2(argc);
2571  long beg, len, i, j;
2572 
2573  for (i=0; i<argc; i++) {
2574  if (FIXNUM_P(argv[i])) {
2575  rb_ary_push(result, (*func)(obj, FIX2LONG(argv[i])));
2576  continue;
2577  }
2578  /* check if idx is Range */
2579  if (rb_range_beg_len(argv[i], &beg, &len, olen, 1)) {
2580  long end = olen < beg+len ? olen : beg+len;
2581  for (j = beg; j < end; j++) {
2582  rb_ary_push(result, (*func)(obj, j));
2583  }
2584  if (beg + len > j)
2585  rb_ary_resize(result, RARRAY_LEN(result) + (beg + len) - j);
2586  continue;
2587  }
2588  rb_ary_push(result, (*func)(obj, NUM2LONG(argv[i])));
2589  }
2590  return result;
2591 }
2592 
2593 /*
2594  * call-seq:
2595  * ary.values_at(selector, ...) -> new_ary
2596  *
2597  * Returns an array containing the elements in +self+ corresponding to the
2598  * given +selector+(s).
2599  *
2600  * The selectors may be either integer indices or ranges.
2601  *
2602  * See also Array#select.
2603  *
2604  * a = %w{ a b c d e f }
2605  * a.values_at(1, 3, 5) # => ["b", "d", "f"]
2606  * a.values_at(1, 3, 5, 7) # => ["b", "d", "f", nil]
2607  * a.values_at(-1, -2, -2, -7) # => ["f", "e", "e", nil]
2608  * a.values_at(4..6, 3...6) # => ["e", "f", nil, "d", "e", "f"]
2609  */
2610 
2611 static VALUE
2612 rb_ary_values_at(int argc, VALUE *argv, VALUE ary)
2613 {
2614  return rb_get_values_at(ary, RARRAY_LEN(ary), argc, argv, rb_ary_entry);
2615 }
2616 
2617 
2618 /*
2619  * call-seq:
2620  * ary.select { |item| block } -> new_ary
2621  * ary.select -> Enumerator
2622  *
2623  * Returns a new array containing all elements of +ary+
2624  * for which the given +block+ returns a true value.
2625  *
2626  * If no block is given, an Enumerator is returned instead.
2627  *
2628  * [1,2,3,4,5].select { |num| num.even? } #=> [2, 4]
2629  *
2630  * a = %w{ a b c d e f }
2631  * a.select { |v| v =~ /[aeiou]/ } #=> ["a", "e"]
2632  *
2633  * See also Enumerable#select.
2634  */
2635 
2636 static VALUE
2638 {
2639  VALUE result;
2640  long i;
2641 
2643  result = rb_ary_new2(RARRAY_LEN(ary));
2644  for (i = 0; i < RARRAY_LEN(ary); i++) {
2645  if (RTEST(rb_yield(RARRAY_PTR(ary)[i]))) {
2646  rb_ary_push(result, rb_ary_elt(ary, i));
2647  }
2648  }
2649  return result;
2650 }
2651 
2652 /*
2653  * call-seq:
2654  * ary.select! {|item| block } -> ary or nil
2655  * ary.select! -> Enumerator
2656  *
2657  * Invokes the given block passing in successive elements from +self+,
2658  * deleting elements for which the block returns a +false+ value.
2659  *
2660  * If changes were made, it will return +self+, otherwise it returns +nil+.
2661  *
2662  * See also Array#keep_if
2663  *
2664  * If no block is given, an Enumerator is returned instead.
2665  *
2666  */
2667 
2668 static VALUE
2670 {
2671  long i1, i2;
2672 
2674  rb_ary_modify(ary);
2675  for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2676  VALUE v = RARRAY_PTR(ary)[i1];
2677  if (!RTEST(rb_yield(v))) continue;
2678  if (i1 != i2) {
2679  rb_ary_store(ary, i2, v);
2680  }
2681  i2++;
2682  }
2683 
2684  if (RARRAY_LEN(ary) == i2) return Qnil;
2685  if (i2 < RARRAY_LEN(ary))
2686  ARY_SET_LEN(ary, i2);
2687  return ary;
2688 }
2689 
2690 /*
2691  * call-seq:
2692  * ary.keep_if { |item| block } -> ary
2693  * ary.keep_if -> Enumerator
2694  *
2695  * Deletes every element of +self+ for which the given block evaluates to
2696  * +false+.
2697  *
2698  * See also Array#select!
2699  *
2700  * If no block is given, an Enumerator is returned instead.
2701  *
2702  * a = %w{ a b c d e f }
2703  * a.keep_if { |v| v =~ /[aeiou]/ } #=> ["a", "e"]
2704  */
2705 
2706 static VALUE
2708 {
2710  rb_ary_select_bang(ary);
2711  return ary;
2712 }
2713 
2714 static void
2716 {
2717  rb_ary_modify(ary);
2718  if (RARRAY_LEN(ary) > len) {
2719  ARY_SET_LEN(ary, len);
2720  if (len * 2 < ARY_CAPA(ary) &&
2721  ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
2722  ary_resize_capa(ary, len * 2);
2723  }
2724  }
2725 }
2726 
2727 /*
2728  * call-seq:
2729  * ary.delete(obj) -> item or nil
2730  * ary.delete(obj) { block } -> item or result of block
2731  *
2732  * Deletes all items from +self+ that are equal to +obj+.
2733  *
2734  * Returns the last deleted item, or +nil+ if no matching item is found.
2735  *
2736  * If the optional code block is given, the result of the block is returned if
2737  * the item is not found. (To remove +nil+ elements and get an informative
2738  * return value, use Array#compact!)
2739  *
2740  * a = [ "a", "b", "b", "b", "c" ]
2741  * a.delete("b") #=> "b"
2742  * a #=> ["a", "c"]
2743  * a.delete("z") #=> nil
2744  * a.delete("z") { "not found" } #=> "not found"
2745  */
2746 
2747 VALUE
2749 {
2750  VALUE v = item;
2751  long i1, i2;
2752 
2753  for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2754  VALUE e = RARRAY_PTR(ary)[i1];
2755 
2756  if (rb_equal(e, item)) {
2757  v = e;
2758  continue;
2759  }
2760  if (i1 != i2) {
2761  rb_ary_store(ary, i2, e);
2762  }
2763  i2++;
2764  }
2765  if (RARRAY_LEN(ary) == i2) {
2766  if (rb_block_given_p()) {
2767  return rb_yield(item);
2768  }
2769  return Qnil;
2770  }
2771 
2772  ary_resize_smaller(ary, i2);
2773 
2774  return v;
2775 }
2776 
2777 void
2779 {
2780  long i1, i2;
2781 
2782  for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2783  VALUE e = RARRAY_PTR(ary)[i1];
2784 
2785  if (e == item) {
2786  continue;
2787  }
2788  if (i1 != i2) {
2789  rb_ary_store(ary, i2, e);
2790  }
2791  i2++;
2792  }
2793  if (RARRAY_LEN(ary) == i2) {
2794  return;
2795  }
2796 
2797  ary_resize_smaller(ary, i2);
2798 }
2799 
2800 VALUE
2802 {
2803  long len = RARRAY_LEN(ary);
2804  VALUE del;
2805 
2806  if (pos >= len) return Qnil;
2807  if (pos < 0) {
2808  pos += len;
2809  if (pos < 0) return Qnil;
2810  }
2811 
2812  rb_ary_modify(ary);
2813  del = RARRAY_PTR(ary)[pos];
2814  MEMMOVE(RARRAY_PTR(ary)+pos, RARRAY_PTR(ary)+pos+1, VALUE,
2815  RARRAY_LEN(ary)-pos-1);
2816  ARY_INCREASE_LEN(ary, -1);
2817 
2818  return del;
2819 }
2820 
2821 /*
2822  * call-seq:
2823  * ary.delete_at(index) -> obj or nil
2824  *
2825  * Deletes the element at the specified +index+, returning that element, or
2826  * +nil+ if the +index+ is out of range.
2827  *
2828  * See also Array#slice!
2829  *
2830  * a = ["ant", "bat", "cat", "dog"]
2831  * a.delete_at(2) #=> "cat"
2832  * a #=> ["ant", "bat", "dog"]
2833  * a.delete_at(99) #=> nil
2834  */
2835 
2836 static VALUE
2838 {
2839  return rb_ary_delete_at(ary, NUM2LONG(pos));
2840 }
2841 
2842 /*
2843  * call-seq:
2844  * ary.slice!(index) -> obj or nil
2845  * ary.slice!(start, length) -> new_ary or nil
2846  * ary.slice!(range) -> new_ary or nil
2847  *
2848  * Deletes the element(s) given by an +index+ (optionally up to +length+
2849  * elements) or by a +range+.
2850  *
2851  * Returns the deleted object (or objects), or +nil+ if the +index+ is out of
2852  * range.
2853  *
2854  * a = [ "a", "b", "c" ]
2855  * a.slice!(1) #=> "b"
2856  * a #=> ["a", "c"]
2857  * a.slice!(-1) #=> "c"
2858  * a #=> ["a"]
2859  * a.slice!(100) #=> nil
2860  * a #=> ["a"]
2861  */
2862 
2863 static VALUE
2865 {
2866  VALUE arg1, arg2;
2867  long pos, len, orig_len;
2868 
2869  rb_ary_modify_check(ary);
2870  if (argc == 2) {
2871  pos = NUM2LONG(argv[0]);
2872  len = NUM2LONG(argv[1]);
2873  delete_pos_len:
2874  if (len < 0) return Qnil;
2875  orig_len = RARRAY_LEN(ary);
2876  if (pos < 0) {
2877  pos += orig_len;
2878  if (pos < 0) return Qnil;
2879  }
2880  else if (orig_len < pos) return Qnil;
2881  if (orig_len < pos + len) {
2882  len = orig_len - pos;
2883  }
2884  if (len == 0) return rb_ary_new2(0);
2885  arg2 = rb_ary_new4(len, RARRAY_PTR(ary)+pos);
2886  RBASIC(arg2)->klass = rb_obj_class(ary);
2887  rb_ary_splice(ary, pos, len, Qundef);
2888  return arg2;
2889  }
2890 
2891  if (argc != 1) {
2892  /* error report */
2893  rb_scan_args(argc, argv, "11", NULL, NULL);
2894  }
2895  arg1 = argv[0];
2896 
2897  if (!FIXNUM_P(arg1)) {
2898  switch (rb_range_beg_len(arg1, &pos, &len, RARRAY_LEN(ary), 0)) {
2899  case Qtrue:
2900  /* valid range */
2901  goto delete_pos_len;
2902  case Qnil:
2903  /* invalid range */
2904  return Qnil;
2905  default:
2906  /* not a range */
2907  break;
2908  }
2909  }
2910 
2911  return rb_ary_delete_at(ary, NUM2LONG(arg1));
2912 }
2913 
2914 static VALUE
2916 {
2917  long i;
2918 
2919  for (i = 0; i < RARRAY_LEN(orig); i++) {
2920  VALUE v = RARRAY_PTR(orig)[i];
2921  if (!RTEST(rb_yield(v))) {
2922  rb_ary_push(result, v);
2923  }
2924  }
2925  return result;
2926 }
2927 
2928 static VALUE
2930 {
2931  long i;
2932  VALUE result = Qnil;
2933 
2934  rb_ary_modify_check(ary);
2935  for (i = 0; i < RARRAY_LEN(ary); ) {
2936  VALUE v = RARRAY_PTR(ary)[i];
2937  if (RTEST(rb_yield(v))) {
2938  rb_ary_delete_at(ary, i);
2939  result = ary;
2940  }
2941  else {
2942  i++;
2943  }
2944  }
2945  return result;
2946 }
2947 
2948 /*
2949  * call-seq:
2950  * ary.reject! { |item| block } -> ary or nil
2951  * ary.reject! -> Enumerator
2952  *
2953  * Equivalent to Array#delete_if, deleting elements from +self+ for which the
2954  * block evaluates to +true+, but returns +nil+ if no changes were made.
2955  *
2956  * The array is changed instantly every time the block is called, not after
2957  * the iteration is over.
2958  *
2959  * See also Enumerable#reject and Array#delete_if.
2960  *
2961  * If no block is given, an Enumerator is returned instead.
2962  */
2963 
2964 static VALUE
2966 {
2968  return ary_reject_bang(ary);
2969 }
2970 
2971 /*
2972  * call-seq:
2973  * ary.reject {|item| block } -> new_ary
2974  * ary.reject -> Enumerator
2975  *
2976  * Returns a new array containing the items in +self+ for which the given
2977  * block is not +true+.
2978  *
2979  * See also Array#delete_if
2980  *
2981  * If no block is given, an Enumerator is returned instead.
2982  */
2983 
2984 static VALUE
2986 {
2987  VALUE rejected_ary;
2988 
2990  rejected_ary = rb_ary_new();
2991  ary_reject(ary, rejected_ary);
2992  return rejected_ary;
2993 }
2994 
2995 /*
2996  * call-seq:
2997  * ary.delete_if { |item| block } -> ary
2998  * ary.delete_if -> Enumerator
2999  *
3000  * Deletes every element of +self+ for which block evaluates to +true+.
3001  *
3002  * The array is changed instantly every time the block is called, not after
3003  * the iteration is over.
3004  *
3005  * See also Array#reject!
3006  *
3007  * If no block is given, an Enumerator is returned instead.
3008  *
3009  * a = [ "a", "b", "c" ]
3010  * a.delete_if {|x| x >= "b" } #=> ["a"]
3011  */
3012 
3013 static VALUE
3015 {
3017  ary_reject_bang(ary);
3018  return ary;
3019 }
3020 
3021 static VALUE
3022 take_i(VALUE val, VALUE *args, int argc, VALUE *argv)
3023 {
3024  if (args[1]-- == 0) rb_iter_break();
3025  if (argc > 1) val = rb_ary_new4(argc, argv);
3026  rb_ary_push(args[0], val);
3027  return Qnil;
3028 }
3029 
3030 static VALUE
3031 take_items(VALUE obj, long n)
3032 {
3034  VALUE args[2];
3035 
3036  if (!NIL_P(result)) return rb_ary_subseq(result, 0, n);
3037  result = rb_ary_new2(n);
3038  args[0] = result; args[1] = (VALUE)n;
3039  if (rb_check_block_call(obj, idEach, 0, 0, take_i, (VALUE)args) == Qundef)
3040  rb_raise(rb_eTypeError, "wrong argument type %s (must respond to :each)",
3041  rb_obj_classname(obj));
3042  return result;
3043 }
3044 
3045 
3046 /*
3047  * call-seq:
3048  * ary.zip(arg, ...) -> new_ary
3049  * ary.zip(arg, ...) { |arr| block } -> nil
3050  *
3051  * Converts any arguments to arrays, then merges elements of +self+ with
3052  * corresponding elements from each argument.
3053  *
3054  * This generates a sequence of <code>ary.size</code> _n_-element arrays,
3055  * where _n_ is one more than the count of arguments.
3056  *
3057  * If the size of any argument is less than the size of the initial array,
3058  * +nil+ values are supplied.
3059  *
3060  * If a block is given, it is invoked for each output +array+, otherwise an
3061  * array of arrays is returned.
3062  *
3063  * a = [ 4, 5, 6 ]
3064  * b = [ 7, 8, 9 ]
3065  * [1, 2, 3].zip(a, b) #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
3066  * [1, 2].zip(a, b) #=> [[1, 4, 7], [2, 5, 8]]
3067  * a.zip([1, 2], [8]) #=> [[4, 1, 8], [5, 2, nil], [6, nil, nil]]
3068  */
3069 
3070 static VALUE
3071 rb_ary_zip(int argc, VALUE *argv, VALUE ary)
3072 {
3073  int i, j;
3074  long len;
3075  VALUE result = Qnil;
3076 
3077  len = RARRAY_LEN(ary);
3078  for (i=0; i<argc; i++) {
3079  argv[i] = take_items(argv[i], len);
3080  }
3081  if (!rb_block_given_p()) {
3082  result = rb_ary_new2(len);
3083  }
3084 
3085  for (i=0; i<RARRAY_LEN(ary); i++) {
3086  VALUE tmp = rb_ary_new2(argc+1);
3087 
3088  rb_ary_push(tmp, rb_ary_elt(ary, i));
3089  for (j=0; j<argc; j++) {
3090  rb_ary_push(tmp, rb_ary_elt(argv[j], i));
3091  }
3092  if (NIL_P(result)) {
3093  rb_yield(tmp);
3094  }
3095  else {
3096  rb_ary_push(result, tmp);
3097  }
3098  }
3099  return result;
3100 }
3101 
3102 /*
3103  * call-seq:
3104  * ary.transpose -> new_ary
3105  *
3106  * Assumes that +self+ is an array of arrays and transposes the rows and
3107  * columns.
3108  *
3109  * a = [[1,2], [3,4], [5,6]]
3110  * a.transpose #=> [[1, 3, 5], [2, 4, 6]]
3111  *
3112  * If the length of the subarrays don't match, an IndexError is raised.
3113  */
3114 
3115 static VALUE
3117 {
3118  long elen = -1, alen, i, j;
3119  VALUE tmp, result = 0;
3120 
3121  alen = RARRAY_LEN(ary);
3122  if (alen == 0) return rb_ary_dup(ary);
3123  for (i=0; i<alen; i++) {
3124  tmp = to_ary(rb_ary_elt(ary, i));
3125  if (elen < 0) { /* first element */
3126  elen = RARRAY_LEN(tmp);
3127  result = rb_ary_new2(elen);
3128  for (j=0; j<elen; j++) {
3129  rb_ary_store(result, j, rb_ary_new2(alen));
3130  }
3131  }
3132  else if (elen != RARRAY_LEN(tmp)) {
3133  rb_raise(rb_eIndexError, "element size differs (%ld should be %ld)",
3134  RARRAY_LEN(tmp), elen);
3135  }
3136  for (j=0; j<elen; j++) {
3137  rb_ary_store(rb_ary_elt(result, j), i, rb_ary_elt(tmp, j));
3138  }
3139  }
3140  return result;
3141 }
3142 
3143 /*
3144  * call-seq:
3145  * ary.replace(other_ary) -> ary
3146  *
3147  * Replaces the contents of +self+ with the contents of +other_ary+,
3148  * truncating or expanding if necessary.
3149  *
3150  * a = [ "a", "b", "c", "d", "e" ]
3151  * a.replace([ "x", "y", "z" ]) #=> ["x", "y", "z"]
3152  * a #=> ["x", "y", "z"]
3153  */
3154 
3155 VALUE
3157 {
3158  rb_ary_modify_check(copy);
3159  orig = to_ary(orig);
3160  if (copy == orig) return copy;
3161 
3162  if (RARRAY_LEN(orig) <= RARRAY_EMBED_LEN_MAX) {
3163  VALUE *ptr;
3164  VALUE shared = 0;
3165 
3166  if (ARY_OWNS_HEAP_P(copy)) {
3167  xfree(RARRAY_PTR(copy));
3168  }
3169  else if (ARY_SHARED_P(copy)) {
3170  shared = ARY_SHARED(copy);
3171  FL_UNSET_SHARED(copy);
3172  }
3173  FL_SET_EMBED(copy);
3174  ptr = RARRAY_PTR(orig);
3175  MEMCPY(RARRAY_PTR(copy), ptr, VALUE, RARRAY_LEN(orig));
3176  if (shared) {
3177  rb_ary_decrement_share(shared);
3178  }
3179  ARY_SET_LEN(copy, RARRAY_LEN(orig));
3180  }
3181  else {
3182  VALUE shared = ary_make_shared(orig);
3183  if (ARY_OWNS_HEAP_P(copy)) {
3184  xfree(RARRAY_PTR(copy));
3185  }
3186  else {
3187  rb_ary_unshare_safe(copy);
3188  }
3189  FL_UNSET_EMBED(copy);
3190  ARY_SET_PTR(copy, RARRAY_PTR(orig));
3191  ARY_SET_LEN(copy, RARRAY_LEN(orig));
3192  rb_ary_set_shared(copy, shared);
3193  }
3194  return copy;
3195 }
3196 
3197 /*
3198  * call-seq:
3199  * ary.clear -> ary
3200  *
3201  * Removes all elements from +self+.
3202  *
3203  * a = [ "a", "b", "c", "d", "e" ]
3204  * a.clear #=> [ ]
3205  */
3206 
3207 VALUE
3209 {
3210  rb_ary_modify_check(ary);
3211  ARY_SET_LEN(ary, 0);
3212  if (ARY_SHARED_P(ary)) {
3213  if (!ARY_EMBED_P(ary)) {
3214  rb_ary_unshare(ary);
3215  FL_SET_EMBED(ary);
3216  }
3217  }
3218  else if (ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
3220  }
3221  return ary;
3222 }
3223 
3224 /*
3225  * call-seq:
3226  * ary.fill(obj) -> ary
3227  * ary.fill(obj, start [, length]) -> ary
3228  * ary.fill(obj, range ) -> ary
3229  * ary.fill { |index| block } -> ary
3230  * ary.fill(start [, length] ) { |index| block } -> ary
3231  * ary.fill(range) { |index| block } -> ary
3232  *
3233  * The first three forms set the selected elements of +self+ (which
3234  * may be the entire array) to +obj+.
3235  *
3236  * A +start+ of +nil+ is equivalent to zero.
3237  *
3238  * A +length+ of +nil+ is equivalent to the length of the array.
3239  *
3240  * The last three forms fill the array with the value of the given block,
3241  * which is passed the absolute index of each element to be filled.
3242  *
3243  * Negative values of +start+ count from the end of the array, where +-1+ is
3244  * the last element.
3245  *
3246  * a = [ "a", "b", "c", "d" ]
3247  * a.fill("x") #=> ["x", "x", "x", "x"]
3248  * a.fill("z", 2, 2) #=> ["x", "x", "z", "z"]
3249  * a.fill("y", 0..1) #=> ["y", "y", "z", "z"]
3250  * a.fill { |i| i*i } #=> [0, 1, 4, 9]
3251  * a.fill(-2) { |i| i*i*i } #=> [0, 1, 8, 27]
3252  */
3253 
3254 static VALUE
3255 rb_ary_fill(int argc, VALUE *argv, VALUE ary)
3256 {
3257  VALUE item, arg1, arg2;
3258  long beg = 0, end = 0, len = 0;
3259  VALUE *p, *pend;
3260  int block_p = FALSE;
3261 
3262  if (rb_block_given_p()) {
3263  block_p = TRUE;
3264  rb_scan_args(argc, argv, "02", &arg1, &arg2);
3265  argc += 1; /* hackish */
3266  }
3267  else {
3268  rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
3269  }
3270  switch (argc) {
3271  case 1:
3272  beg = 0;
3273  len = RARRAY_LEN(ary);
3274  break;
3275  case 2:
3276  if (rb_range_beg_len(arg1, &beg, &len, RARRAY_LEN(ary), 1)) {
3277  break;
3278  }
3279  /* fall through */
3280  case 3:
3281  beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
3282  if (beg < 0) {
3283  beg = RARRAY_LEN(ary) + beg;
3284  if (beg < 0) beg = 0;
3285  }
3286  len = NIL_P(arg2) ? RARRAY_LEN(ary) - beg : NUM2LONG(arg2);
3287  break;
3288  }
3289  rb_ary_modify(ary);
3290  if (len < 0) {
3291  return ary;
3292  }
3293  if (beg >= ARY_MAX_SIZE || len > ARY_MAX_SIZE - beg) {
3294  rb_raise(rb_eArgError, "argument too big");
3295  }
3296  end = beg + len;
3297  if (RARRAY_LEN(ary) < end) {
3298  if (end >= ARY_CAPA(ary)) {
3299  ary_resize_capa(ary, end);
3300  }
3301  rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), end - RARRAY_LEN(ary));
3302  ARY_SET_LEN(ary, end);
3303  }
3304 
3305  if (block_p) {
3306  VALUE v;
3307  long i;
3308 
3309  for (i=beg; i<end; i++) {
3310  v = rb_yield(LONG2NUM(i));
3311  if (i>=RARRAY_LEN(ary)) break;
3312  RARRAY_PTR(ary)[i] = v;
3313  }
3314  }
3315  else {
3316  p = RARRAY_PTR(ary) + beg;
3317  pend = p + len;
3318  while (p < pend) {
3319  *p++ = item;
3320  }
3321  }
3322  return ary;
3323 }
3324 
3325 /*
3326  * call-seq:
3327  * ary + other_ary -> new_ary
3328  *
3329  * Concatenation --- Returns a new array built by concatenating the
3330  * two arrays together to produce a third array.
3331  *
3332  * [ 1, 2, 3 ] + [ 4, 5 ] #=> [ 1, 2, 3, 4, 5 ]
3333  * a = [ "a", "b", "c" ]
3334  * a + [ "d", "e", "f" ]
3335  * a #=> [ "a", "b", "c", "d", "e", "f" ]
3336  *
3337  * See also Array#concat.
3338  */
3339 
3340 VALUE
3342 {
3343  VALUE z;
3344  long len;
3345 
3346  y = to_ary(y);
3347  len = RARRAY_LEN(x) + RARRAY_LEN(y);
3348  z = rb_ary_new2(len);
3351  ARY_SET_LEN(z, len);
3352  return z;
3353 }
3354 
3355 /*
3356  * call-seq:
3357  * ary.concat(other_ary) -> ary
3358  *
3359  * Appends the elements of +other_ary+ to +self+.
3360  *
3361  * [ "a", "b" ].concat( ["c", "d"] ) #=> [ "a", "b", "c", "d" ]
3362  * a = [ 1, 2, 3 ]
3363  * a.concat( [ 4, 5 ] )
3364  * a #=> [ 1, 2, 3, 4, 5 ]
3365  *
3366  * See also Array#+.
3367  */
3368 
3369 VALUE
3371 {
3373  y = to_ary(y);
3374  if (RARRAY_LEN(y) > 0) {
3375  rb_ary_splice(x, RARRAY_LEN(x), 0, y);
3376  }
3377  return x;
3378 }
3379 
3380 
3381 /*
3382  * call-seq:
3383  * ary * int -> new_ary
3384  * ary * str -> new_string
3385  *
3386  * Repetition --- With a String argument, equivalent to
3387  * <code>ary.join(str)</code>.
3388  *
3389  * Otherwise, returns a new array built by concatenating the +int+ copies of
3390  * +self+.
3391  *
3392  *
3393  * [ 1, 2, 3 ] * 3 #=> [ 1, 2, 3, 1, 2, 3, 1, 2, 3 ]
3394  * [ 1, 2, 3 ] * "," #=> "1,2,3"
3395  *
3396  */
3397 
3398 static VALUE
3400 {
3401  VALUE ary2, tmp, *ptr, *ptr2;
3402  long t, len;
3403 
3404  tmp = rb_check_string_type(times);
3405  if (!NIL_P(tmp)) {
3406  return rb_ary_join(ary, tmp);
3407  }
3408 
3409  len = NUM2LONG(times);
3410  if (len == 0) {
3411  ary2 = ary_new(rb_obj_class(ary), 0);
3412  goto out;
3413  }
3414  if (len < 0) {
3415  rb_raise(rb_eArgError, "negative argument");
3416  }
3417  if (ARY_MAX_SIZE/len < RARRAY_LEN(ary)) {
3418  rb_raise(rb_eArgError, "argument too big");
3419  }
3420  len *= RARRAY_LEN(ary);
3421 
3422  ary2 = ary_new(rb_obj_class(ary), len);
3423  ARY_SET_LEN(ary2, len);
3424 
3425  ptr = RARRAY_PTR(ary);
3426  ptr2 = RARRAY_PTR(ary2);
3427  t = RARRAY_LEN(ary);
3428  if (0 < t) {
3429  MEMCPY(ptr2, ptr, VALUE, t);
3430  while (t <= len/2) {
3431  MEMCPY(ptr2+t, ptr2, VALUE, t);
3432  t *= 2;
3433  }
3434  if (t < len) {
3435  MEMCPY(ptr2+t, ptr2, VALUE, len-t);
3436  }
3437  }
3438  out:
3439  OBJ_INFECT(ary2, ary);
3440 
3441  return ary2;
3442 }
3443 
3444 /*
3445  * call-seq:
3446  * ary.assoc(obj) -> new_ary or nil
3447  *
3448  * Searches through an array whose elements are also arrays comparing +obj+
3449  * with the first element of each contained array using <code>obj.==</code>.
3450  *
3451  * Returns the first contained array that matches (that is, the first
3452  * associated array), or +nil+ if no match is found.
3453  *
3454  * See also Array#rassoc
3455  *
3456  * s1 = [ "colors", "red", "blue", "green" ]
3457  * s2 = [ "letters", "a", "b", "c" ]
3458  * s3 = "foo"
3459  * a = [ s1, s2, s3 ]
3460  * a.assoc("letters") #=> [ "letters", "a", "b", "c" ]
3461  * a.assoc("foo") #=> nil
3462  */
3463 
3464 VALUE
3466 {
3467  long i;
3468  VALUE v;
3469 
3470  for (i = 0; i < RARRAY_LEN(ary); ++i) {
3471  v = rb_check_array_type(RARRAY_PTR(ary)[i]);
3472  if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
3473  rb_equal(RARRAY_PTR(v)[0], key))
3474  return v;
3475  }
3476  return Qnil;
3477 }
3478 
3479 /*
3480  * call-seq:
3481  * ary.rassoc(obj) -> new_ary or nil
3482  *
3483  * Searches through the array whose elements are also arrays.
3484  *
3485  * Compares +obj+ with the second element of each contained array using
3486  * <code>obj.==</code>.
3487  *
3488  * Returns the first contained array that matches +obj+.
3489  *
3490  * See also Array#assoc.
3491  *
3492  * a = [ [ 1, "one"], [2, "two"], [3, "three"], ["ii", "two"] ]
3493  * a.rassoc("two") #=> [2, "two"]
3494  * a.rassoc("four") #=> nil
3495  */
3496 
3497 VALUE
3499 {
3500  long i;
3501  VALUE v;
3502 
3503  for (i = 0; i < RARRAY_LEN(ary); ++i) {
3504  v = RARRAY_PTR(ary)[i];
3505  if (RB_TYPE_P(v, T_ARRAY) &&
3506  RARRAY_LEN(v) > 1 &&
3507  rb_equal(RARRAY_PTR(v)[1], value))
3508  return v;
3509  }
3510  return Qnil;
3511 }
3512 
3513 static VALUE
3515 {
3516  long i, len1;
3517  VALUE *p1, *p2;
3518 
3519  if (recur) return Qtrue; /* Subtle! */
3520 
3521  p1 = RARRAY_PTR(ary1);
3522  p2 = RARRAY_PTR(ary2);
3523  len1 = RARRAY_LEN(ary1);
3524 
3525  for (i = 0; i < len1; i++) {
3526  if (*p1 != *p2) {
3527  if (rb_equal(*p1, *p2)) {
3528  len1 = RARRAY_LEN(ary1);
3529  if (len1 != RARRAY_LEN(ary2))
3530  return Qfalse;
3531  if (len1 < i)
3532  return Qtrue;
3533  p1 = RARRAY_PTR(ary1) + i;
3534  p2 = RARRAY_PTR(ary2) + i;
3535  }
3536  else {
3537  return Qfalse;
3538  }
3539  }
3540  p1++;
3541  p2++;
3542  }
3543  return Qtrue;
3544 }
3545 
3546 /*
3547  * call-seq:
3548  * ary == other_ary -> bool
3549  *
3550  * Equality --- Two arrays are equal if they contain the same number of
3551  * elements and if each element is equal to (according to Object#==) the
3552  * corresponding element in +other_ary+.
3553  *
3554  * [ "a", "c" ] == [ "a", "c", 7 ] #=> false
3555  * [ "a", "c", 7 ] == [ "a", "c", 7 ] #=> true
3556  * [ "a", "c", 7 ] == [ "a", "d", "f" ] #=> false
3557  *
3558  */
3559 
3560 static VALUE
3562 {
3563  if (ary1 == ary2) return Qtrue;
3564  if (!RB_TYPE_P(ary2, T_ARRAY)) {
3565  if (!rb_respond_to(ary2, rb_intern("to_ary"))) {
3566  return Qfalse;
3567  }
3568  return rb_equal(ary2, ary1);
3569  }
3570  if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
3571  return rb_exec_recursive_paired(recursive_equal, ary1, ary2, ary2);
3572 }
3573 
3574 static VALUE
3575 recursive_eql(VALUE ary1, VALUE ary2, int recur)
3576 {
3577  long i;
3578 
3579  if (recur) return Qtrue; /* Subtle! */
3580  for (i=0; i<RARRAY_LEN(ary1); i++) {
3581  if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
3582  return Qfalse;
3583  }
3584  return Qtrue;
3585 }
3586 
3587 /*
3588  * call-seq:
3589  * ary.eql?(other) -> true or false
3590  *
3591  * Returns +true+ if +self+ and +other+ are the same object,
3592  * or are both arrays with the same content (according to Object#eql?).
3593  */
3594 
3595 static VALUE
3597 {
3598  if (ary1 == ary2) return Qtrue;
3599  if (!RB_TYPE_P(ary2, T_ARRAY)) return Qfalse;
3600  if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
3601  return rb_exec_recursive_paired(recursive_eql, ary1, ary2, ary2);
3602 }
3603 
3604 static VALUE
3606 {
3607  long i;
3608  st_index_t h;
3609  VALUE n;
3610 
3611  h = rb_hash_start(RARRAY_LEN(ary));
3612  if (recur) {
3614  }
3615  else {
3616  for (i=0; i<RARRAY_LEN(ary); i++) {
3617  n = rb_hash(RARRAY_PTR(ary)[i]);
3618  h = rb_hash_uint(h, NUM2LONG(n));
3619  }
3620  }
3621  h = rb_hash_end(h);
3622  return LONG2FIX(h);
3623 }
3624 
3625 /*
3626  * call-seq:
3627  * ary.hash -> fixnum
3628  *
3629  * Compute a hash-code for this array.
3630  *
3631  * Two arrays with the same content will have the same hash code (and will
3632  * compare using #eql?).
3633  */
3634 
3635 static VALUE
3637 {
3638  return rb_exec_recursive_outer(recursive_hash, ary, 0);
3639 }
3640 
3641 /*
3642  * call-seq:
3643  * ary.include?(object) -> true or false
3644  *
3645  * Returns +true+ if the given +object+ is present in +self+ (that is, if any
3646  * element <code>==</code> +object+), otherwise returns +false+.
3647  *
3648  * a = [ "a", "b", "c" ]
3649  * a.include?("b") #=> true
3650  * a.include?("z") #=> false
3651  */
3652 
3653 VALUE
3655 {
3656  long i;
3657 
3658  for (i=0; i<RARRAY_LEN(ary); i++) {
3659  if (rb_equal(RARRAY_PTR(ary)[i], item)) {
3660  return Qtrue;
3661  }
3662  }
3663  return Qfalse;
3664 }
3665 
3666 
3667 static VALUE
3668 recursive_cmp(VALUE ary1, VALUE ary2, int recur)
3669 {
3670  long i, len;
3671 
3672  if (recur) return Qundef; /* Subtle! */
3673  len = RARRAY_LEN(ary1);
3674  if (len > RARRAY_LEN(ary2)) {
3675  len = RARRAY_LEN(ary2);
3676  }
3677  for (i=0; i<len; i++) {
3678  VALUE v = rb_funcall(rb_ary_elt(ary1, i), id_cmp, 1, rb_ary_elt(ary2, i));
3679  if (v != INT2FIX(0)) {
3680  return v;
3681  }
3682  }
3683  return Qundef;
3684 }
3685 
3686 /*
3687  * call-seq:
3688  * ary <=> other_ary -> -1, 0, +1 or nil
3689  *
3690  * Comparison --- Returns an integer (+-1+, +0+, or <code>+1</code>) if this
3691  * array is less than, equal to, or greater than +other_ary+.
3692  *
3693  * +nil+ is returned if the two values are incomparable.
3694  *
3695  * Each object in each array is compared (using the <=> operator).
3696  *
3697  * Arrays are compared in an "element-wise" manner; the first two elements
3698  * that are not equal will determine the return value for the whole
3699  * comparison.
3700  *
3701  * If all the values are equal, then the return is based on a comparison of
3702  * the array lengths. Thus, two arrays are "equal" according to Array#<=> if,
3703  * and only if, they have the same length and the value of each element is
3704  * equal to the value of the corresponding element in the other array.
3705  *
3706  * [ "a", "a", "c" ] <=> [ "a", "b", "c" ] #=> -1
3707  * [ 1, 2, 3, 4, 5, 6 ] <=> [ 1, 2 ] #=> +1
3708  *
3709  */
3710 
3711 VALUE
3713 {
3714  long len;
3715  VALUE v;
3716 
3717  ary2 = rb_check_array_type(ary2);
3718  if (NIL_P(ary2)) return Qnil;
3719  if (ary1 == ary2) return INT2FIX(0);
3720  v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
3721  if (v != Qundef) return v;
3722  len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
3723  if (len == 0) return INT2FIX(0);
3724  if (len > 0) return INT2FIX(1);
3725  return INT2FIX(-1);
3726 }
3727 
3728 static VALUE
3730 {
3731  long i;
3732 
3733  for (i=0; i<RARRAY_LEN(ary); i++) {
3734  rb_hash_aset(hash, RARRAY_PTR(ary)[i], Qtrue);
3735  }
3736  return hash;
3737 }
3738 
3739 static inline VALUE
3741 {
3742  VALUE hash = rb_hash_new();
3743 
3744  RBASIC(hash)->klass = 0;
3745  return hash;
3746 }
3747 
3748 static VALUE
3750 {
3752  return ary_add_hash(hash, ary);
3753 }
3754 
3755 static VALUE
3757 {
3758  long i;
3759 
3760  for (i = 0; i < RARRAY_LEN(ary); ++i) {
3761  VALUE v = rb_ary_elt(ary, i), k = rb_yield(v);
3762  if (rb_hash_lookup2(hash, k, Qundef) == Qundef) {
3763  rb_hash_aset(hash, k, v);
3764  }
3765  }
3766  return hash;
3767 }
3768 
3769 static VALUE
3771 {
3773  return ary_add_hash_by(hash, ary);
3774 }
3775 
3776 static inline void
3778 {
3779  if (RHASH(hash)->ntbl) {
3780  st_table *tbl = RHASH(hash)->ntbl;
3781  RHASH(hash)->ntbl = 0;
3782  st_free_table(tbl);
3783  }
3784  RB_GC_GUARD(hash);
3785 }
3786 
3787 /*
3788  * call-seq:
3789  * ary - other_ary -> new_ary
3790  *
3791  * Array Difference
3792  *
3793  * Returns a new array that is a copy of the original array, removing any
3794  * items that also appear in +other_ary+. The order is preserved from the
3795  * original array.
3796  *
3797  * It compares elements using their #hash and #eql? methods for efficiency.
3798  *
3799  * [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ] #=> [ 3, 3, 5 ]
3800  *
3801  * If you need set-like behavior, see the library class Set.
3802  */
3803 
3804 static VALUE
3806 {
3807  VALUE ary3;
3808  VALUE hash;
3809  long i;
3810 
3811  hash = ary_make_hash(to_ary(ary2));
3812  ary3 = rb_ary_new();
3813 
3814  for (i=0; i<RARRAY_LEN(ary1); i++) {
3815  if (st_lookup(RHASH_TBL(hash), RARRAY_PTR(ary1)[i], 0)) continue;
3816  rb_ary_push(ary3, rb_ary_elt(ary1, i));
3817  }
3818  ary_recycle_hash(hash);
3819  return ary3;
3820 }
3821 
3822 /*
3823  * call-seq:
3824  * ary & other_ary -> new_ary
3825  *
3826  * Set Intersection --- Returns a new array containing elements common to the
3827  * two arrays, excluding any duplicates. The order is preserved from the
3828  * original array.
3829  *
3830  * It compares elements using their #hash and #eql? methods for efficiency.
3831  *
3832  * [ 1, 1, 3, 5 ] & [ 1, 2, 3 ] #=> [ 1, 3 ]
3833  * [ 'a', 'b', 'b', 'z' ] & [ 'a', 'b', 'c' ] #=> [ 'a', 'b' ]
3834  *
3835  * See also Array#uniq.
3836  */
3837 
3838 
3839 static VALUE
3841 {
3842  VALUE hash, ary3, v;
3843  st_data_t vv;
3844  long i;
3845 
3846  ary2 = to_ary(ary2);
3847  ary3 = rb_ary_new2(RARRAY_LEN(ary1) < RARRAY_LEN(ary2) ?
3848  RARRAY_LEN(ary1) : RARRAY_LEN(ary2));
3849  hash = ary_make_hash(ary2);
3850 
3851  if (RHASH_EMPTY_P(hash))
3852  return ary3;
3853 
3854  for (i=0; i<RARRAY_LEN(ary1); i++) {
3855  vv = (st_data_t)(v = rb_ary_elt(ary1, i));
3856  if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3857  rb_ary_push(ary3, v);
3858  }
3859  }
3860  ary_recycle_hash(hash);
3861 
3862  return ary3;
3863 }
3864 
3865 /*
3866  * call-seq:
3867  * ary | other_ary -> new_ary
3868  *
3869  * Set Union --- Returns a new array by joining +ary+ with +other_ary+,
3870  * excluding any duplicates and preserving the order from the original array.
3871  *
3872  * It compares elements using their #hash and #eql? methods for efficiency.
3873  *
3874  * [ "a", "b", "c" ] | [ "c", "d", "a" ] #=> [ "a", "b", "c", "d" ]
3875  *
3876  * See also Array#uniq.
3877  */
3878 
3879 static VALUE
3880 rb_ary_or(VALUE ary1, VALUE ary2)
3881 {
3882  VALUE hash, ary3, v;
3883  st_data_t vv;
3884  long i;
3885 
3886  ary2 = to_ary(ary2);
3887  ary3 = rb_ary_new2(RARRAY_LEN(ary1)+RARRAY_LEN(ary2));
3888  hash = ary_add_hash(ary_make_hash(ary1), ary2);
3889 
3890  for (i=0; i<RARRAY_LEN(ary1); i++) {
3891  vv = (st_data_t)(v = rb_ary_elt(ary1, i));
3892  if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3893  rb_ary_push(ary3, v);
3894  }
3895  }
3896  for (i=0; i<RARRAY_LEN(ary2); i++) {
3897  vv = (st_data_t)(v = rb_ary_elt(ary2, i));
3898  if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3899  rb_ary_push(ary3, v);
3900  }
3901  }
3902  ary_recycle_hash(hash);
3903  return ary3;
3904 }
3905 
3906 static int
3908 {
3909  rb_ary_push((VALUE)ary, (VALUE)val);
3910  return ST_CONTINUE;
3911 }
3912 
3913 /*
3914  * call-seq:
3915  * ary.uniq! -> ary or nil
3916  * ary.uniq! { |item| ... } -> ary or nil
3917  *
3918  * Removes duplicate elements from +self+.
3919  *
3920  * If a block is given, it will use the return value of the block for
3921  * comparison.
3922  *
3923  * It compares values using their #hash and #eql? methods for efficiency.
3924  *
3925  * Returns +nil+ if no changes are made (that is, no duplicates are found).
3926  *
3927  * a = [ "a", "a", "b", "b", "c" ]
3928  * a.uniq! # => ["a", "b", "c"]
3929  *
3930  * b = [ "a", "b", "c" ]
3931  * b.uniq! # => nil
3932  *
3933  * c = [["student","sam"], ["student","george"], ["teacher","matz"]]
3934  * c.uniq! { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
3935  *
3936  */
3937 
3938 static VALUE
3940 {
3941  VALUE hash, v;
3942  long i, j;
3943 
3944  rb_ary_modify_check(ary);
3945  if (RARRAY_LEN(ary) <= 1)
3946  return Qnil;
3947  if (rb_block_given_p()) {
3948  hash = ary_make_hash_by(ary);
3949  if (RARRAY_LEN(ary) == (i = RHASH_SIZE(hash))) {
3950  return Qnil;
3951  }
3952  ARY_SET_LEN(ary, 0);
3953  if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
3954  rb_ary_unshare(ary);
3955  FL_SET_EMBED(ary);
3956  }
3957  ary_resize_capa(ary, i);
3958  st_foreach(RHASH_TBL(hash), push_value, ary);
3959  }
3960  else {
3961  hash = ary_make_hash(ary);
3962  if (RARRAY_LEN(ary) == (long)RHASH_SIZE(hash)) {
3963  return Qnil;
3964  }
3965  for (i=j=0; i<RARRAY_LEN(ary); i++) {
3966  st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
3967  if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3968  rb_ary_store(ary, j++, v);
3969  }
3970  }
3971  ARY_SET_LEN(ary, j);
3972  }
3973  ary_recycle_hash(hash);
3974 
3975  return ary;
3976 }
3977 
3978 /*
3979  * call-seq:
3980  * ary.uniq -> new_ary
3981  * ary.uniq { |item| ... } -> new_ary
3982  *
3983  * Returns a new array by removing duplicate values in +self+.
3984  *
3985  * If a block is given, it will use the return value of the block for comparison.
3986  *
3987  * It compares values using their #hash and #eql? methods for efficiency.
3988  *
3989  * a = [ "a", "a", "b", "b", "c" ]
3990  * a.uniq # => ["a", "b", "c"]
3991  *
3992  * b = [["student","sam"], ["student","george"], ["teacher","matz"]]
3993  * b.uniq { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
3994  *
3995  */
3996 
3997 static VALUE
3999 {
4000  VALUE hash, uniq, v;
4001  long i;
4002 
4003  if (RARRAY_LEN(ary) <= 1)
4004  return rb_ary_dup(ary);
4005  if (rb_block_given_p()) {
4006  hash = ary_make_hash_by(ary);
4007  uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
4008  st_foreach(RHASH_TBL(hash), push_value, uniq);
4009  }
4010  else {
4011  hash = ary_make_hash(ary);
4012  uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
4013  for (i=0; i<RARRAY_LEN(ary); i++) {
4014  st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
4015  if (st_delete(RHASH_TBL(hash), &vv, 0)) {
4016  rb_ary_push(uniq, v);
4017  }
4018  }
4019  }
4020  ary_recycle_hash(hash);
4021 
4022  return uniq;
4023 }
4024 
4025 /*
4026  * call-seq:
4027  * ary.compact! -> ary or nil
4028  *
4029  * Removes +nil+ elements from the array.
4030  *
4031  * Returns +nil+ if no changes were made, otherwise returns the array.
4032  *
4033  * [ "a", nil, "b", nil, "c" ].compact! #=> [ "a", "b", "c" ]
4034  * [ "a", "b", "c" ].compact! #=> nil
4035  */
4036 
4037 static VALUE
4039 {
4040  VALUE *p, *t, *end;
4041  long n;
4042 
4043  rb_ary_modify(ary);
4044  p = t = RARRAY_PTR(ary);
4045  end = p + RARRAY_LEN(ary);
4046 
4047  while (t < end) {
4048  if (NIL_P(*t)) t++;
4049  else *p++ = *t++;
4050  }
4051  n = p - RARRAY_PTR(ary);
4052  if (RARRAY_LEN(ary) == n) {
4053  return Qnil;
4054  }
4055  ARY_SET_LEN(ary, n);
4056  if (n * 2 < ARY_CAPA(ary) && ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
4057  ary_resize_capa(ary, n * 2);
4058  }
4059 
4060  return ary;
4061 }
4062 
4063 /*
4064  * call-seq:
4065  * ary.compact -> new_ary
4066  *
4067  * Returns a copy of +self+ with all +nil+ elements removed.
4068  *
4069  * [ "a", nil, "b", nil, "c", nil ].compact
4070  * #=> [ "a", "b", "c" ]
4071  */
4072 
4073 static VALUE
4075 {
4076  ary = rb_ary_dup(ary);
4077  rb_ary_compact_bang(ary);
4078  return ary;
4079 }
4080 
4081 /*
4082  * call-seq:
4083  * ary.count -> int
4084  * ary.count(obj) -> int
4085  * ary.count { |item| block } -> int
4086  *
4087  * Returns the number of elements.
4088  *
4089  * If an argument is given, counts the number of elements which equal +obj+
4090  * using <code>===</code>.
4091  *
4092  * If a block is given, counts the number of elements for which the block
4093  * returns a true value.
4094  *
4095  * ary = [1, 2, 4, 2]
4096  * ary.count #=> 4
4097  * ary.count(2) #=> 2
4098  * ary.count { |x| x%2 == 0 } #=> 3
4099  *
4100  */
4101 
4102 static VALUE
4103 rb_ary_count(int argc, VALUE *argv, VALUE ary)
4104 {
4105  long i, n = 0;
4106 
4107  if (argc == 0) {
4108  VALUE v;
4109 
4110  if (!rb_block_given_p())
4111  return LONG2NUM(RARRAY_LEN(ary));
4112 
4113  for (i = 0; i < RARRAY_LEN(ary); i++) {
4114  v = RARRAY_PTR(ary)[i];
4115  if (RTEST(rb_yield(v))) n++;
4116  }
4117  }
4118  else {
4119  VALUE obj;
4120 
4121  rb_scan_args(argc, argv, "1", &obj);
4122  if (rb_block_given_p()) {
4123  rb_warn("given block not used");
4124  }
4125  for (i = 0; i < RARRAY_LEN(ary); i++) {
4126  if (rb_equal(RARRAY_PTR(ary)[i], obj)) n++;
4127  }
4128  }
4129 
4130  return LONG2NUM(n);
4131 }
4132 
4133 static VALUE
4134 flatten(VALUE ary, int level, int *modified)
4135 {
4136  long i = 0;
4137  VALUE stack, result, tmp, elt;
4138  st_table *memo;
4139  st_data_t id;
4140 
4141  stack = ary_new(0, ARY_DEFAULT_SIZE);
4142  result = ary_new(0, RARRAY_LEN(ary));
4143  memo = st_init_numtable();
4144  st_insert(memo, (st_data_t)ary, (st_data_t)Qtrue);
4145  *modified = 0;
4146 
4147  while (1) {
4148  while (i < RARRAY_LEN(ary)) {
4149  elt = RARRAY_PTR(ary)[i++];
4150  tmp = rb_check_array_type(elt);
4151  if (RBASIC(result)->klass) {
4152  rb_raise(rb_eRuntimeError, "flatten reentered");
4153  }
4154  if (NIL_P(tmp) || (level >= 0 && RARRAY_LEN(stack) / 2 >= level)) {
4155  rb_ary_push(result, elt);
4156  }
4157  else {
4158  *modified = 1;
4159  id = (st_data_t)tmp;
4160  if (st_lookup(memo, id, 0)) {
4161  st_free_table(memo);
4162  rb_raise(rb_eArgError, "tried to flatten recursive array");
4163  }
4164  st_insert(memo, id, (st_data_t)Qtrue);
4165  rb_ary_push(stack, ary);
4166  rb_ary_push(stack, LONG2NUM(i));
4167  ary = tmp;
4168  i = 0;
4169  }
4170  }
4171  if (RARRAY_LEN(stack) == 0) {
4172  break;
4173  }
4174  id = (st_data_t)ary;
4175  st_delete(memo, &id, 0);
4176  tmp = rb_ary_pop(stack);
4177  i = NUM2LONG(tmp);
4178  ary = rb_ary_pop(stack);
4179  }
4180 
4181  st_free_table(memo);
4182 
4183  RBASIC(result)->klass = rb_class_of(ary);
4184  return result;
4185 }
4186 
4187 /*
4188  * call-seq:
4189  * ary.flatten! -> ary or nil
4190  * ary.flatten!(level) -> ary or nil
4191  *
4192  * Flattens +self+ in place.
4193  *
4194  * Returns +nil+ if no modifications were made (i.e., the array contains no
4195  * subarrays.)
4196  *
4197  * The optional +level+ argument determines the level of recursion to flatten.
4198  *
4199  * a = [ 1, 2, [3, [4, 5] ] ]
4200  * a.flatten! #=> [1, 2, 3, 4, 5]
4201  * a.flatten! #=> nil
4202  * a #=> [1, 2, 3, 4, 5]
4203  * a = [ 1, 2, [3, [4, 5] ] ]
4204  * a.flatten!(1) #=> [1, 2, 3, [4, 5]]
4205  */
4206 
4207 static VALUE
4209 {
4210  int mod = 0, level = -1;
4211  VALUE result, lv;
4212 
4213  rb_scan_args(argc, argv, "01", &lv);
4214  rb_ary_modify_check(ary);
4215  if (!NIL_P(lv)) level = NUM2INT(lv);
4216  if (level == 0) return Qnil;
4217 
4218  result = flatten(ary, level, &mod);
4219  if (mod == 0) {
4220  ary_discard(result);
4221  return Qnil;
4222  }
4223  if (!(mod = ARY_EMBED_P(result))) rb_obj_freeze(result);
4224  rb_ary_replace(ary, result);
4225  if (mod) ARY_SET_EMBED_LEN(result, 0);
4226 
4227  return ary;
4228 }
4229 
4230 /*
4231  * call-seq:
4232  * ary.flatten -> new_ary
4233  * ary.flatten(level) -> new_ary
4234  *
4235  * Returns a new array that is a one-dimensional flattening of +self+
4236  * (recursively).
4237  *
4238  * That is, for every element that is an array, extract its elements into
4239  * the new array.
4240  *
4241  * The optional +level+ argument determines the level of recursion to
4242  * flatten.
4243  *
4244  * s = [ 1, 2, 3 ] #=> [1, 2, 3]
4245  * t = [ 4, 5, 6, [7, 8] ] #=> [4, 5, 6, [7, 8]]
4246  * a = [ s, t, 9, 10 ] #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
4247  * a.flatten #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
4248  * a = [ 1, 2, [3, [4, 5] ] ]
4249  * a.flatten(1) #=> [1, 2, 3, [4, 5]]
4250  */
4251 
4252 static VALUE
4253 rb_ary_flatten(int argc, VALUE *argv, VALUE ary)
4254 {
4255  int mod = 0, level = -1;
4256  VALUE result, lv;
4257 
4258  rb_scan_args(argc, argv, "01", &lv);
4259  if (!NIL_P(lv)) level = NUM2INT(lv);
4260  if (level == 0) return ary_make_shared_copy(ary);
4261 
4262  result = flatten(ary, level, &mod);
4263  OBJ_INFECT(result, ary);
4264 
4265  return result;
4266 }
4267 
4268 #define OPTHASH_GIVEN_P(opts) \
4269  (argc > 0 && !NIL_P((opts) = rb_check_hash_type(argv[argc-1])) && (--argc, 1))
4271 
4272 #define RAND_UPTO(max) (long)rb_random_ulong_limited((randgen), (max)-1)
4273 
4274 /*
4275  * call-seq:
4276  * ary.shuffle! -> ary
4277  * ary.shuffle!(random: rng) -> ary
4278  *
4279  * Shuffles elements in +self+ in place.
4280  *
4281  * The optional +rng+ argument will be used as the random number generator.
4282  */
4283 
4284 static VALUE
4286 {
4287  VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
4288  long i, snap_len;
4289 
4290  if (OPTHASH_GIVEN_P(opts)) {
4291  randgen = rb_hash_lookup2(opts, sym_random, randgen);
4292  }
4293  rb_check_arity(argc, 0, 0);
4294  rb_ary_modify(ary);
4295  i = RARRAY_LEN(ary);
4296  ptr = RARRAY_PTR(ary);
4297  snap_len = i;
4298  snap_ptr = ptr;
4299  while (i) {
4300  long j = RAND_UPTO(i);
4301  VALUE tmp;
4302  if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
4303  rb_raise(rb_eRuntimeError, "modified during shuffle");
4304  }
4305  tmp = ptr[--i];
4306  ptr[i] = ptr[j];
4307  ptr[j] = tmp;
4308  }
4309  return ary;
4310 }
4311 
4312 
4313 /*
4314  * call-seq:
4315  * ary.shuffle -> new_ary
4316  * ary.shuffle(random: rng) -> new_ary
4317  *
4318  * Returns a new array with elements of +self+ shuffled.
4319  *
4320  * a = [ 1, 2, 3 ] #=> [1, 2, 3]
4321  * a.shuffle #=> [2, 3, 1]
4322  *
4323  * The optional +rng+ argument will be used as the random number generator.
4324  *
4325  * a.shuffle(random: Random.new(1)) #=> [1, 3, 2]
4326  */
4327 
4328 static VALUE
4329 rb_ary_shuffle(int argc, VALUE *argv, VALUE ary)
4330 {
4331  ary = rb_ary_dup(ary);
4332  rb_ary_shuffle_bang(argc, argv, ary);
4333  return ary;
4334 }
4335 
4336 
4337 /*
4338  * call-seq:
4339  * ary.sample -> obj
4340  * ary.sample(random: rng) -> obj
4341  * ary.sample(n) -> new_ary
4342  * ary.sample(n, random: rng) -> new_ary
4343  *
4344  * Choose a random element or +n+ random elements from the array.
4345  *
4346  * The elements are chosen by using random and unique indices into the array
4347  * in order to ensure that an element doesn't repeat itself unless the array
4348  * already contained duplicate elements.
4349  *
4350  * If the array is empty the first form returns +nil+ and the second form
4351  * returns an empty array.
4352  *
4353  * The optional +rng+ argument will be used as the random number generator.
4354  *
4355  * a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
4356  * a.sample #=> 7
4357  * a.sample(4) #=> [6, 4, 2, 5]
4358  */
4359 
4360 
4361 static VALUE
4362 rb_ary_sample(int argc, VALUE *argv, VALUE ary)
4363 {
4364  VALUE nv, result, *ptr;
4365  VALUE opts, randgen = rb_cRandom;
4366  long n, len, i, j, k, idx[10];
4367  long rnds[numberof(idx)];
4368 
4369  if (OPTHASH_GIVEN_P(opts)) {
4370  randgen = rb_hash_lookup2(opts, sym_random, randgen);
4371  }
4372  ptr = RARRAY_PTR(ary);
4373  len = RARRAY_LEN(ary);
4374  if (argc == 0) {
4375  if (len == 0) return Qnil;
4376  if (len == 1) {
4377  i = 0;
4378  }
4379  else {
4380  i = RAND_UPTO(len);
4381  if ((len = RARRAY_LEN(ary)) <= i) return Qnil;
4382  ptr = RARRAY_PTR(ary);
4383  }
4384  return ptr[i];
4385  }
4386  rb_scan_args(argc, argv, "1", &nv);
4387  n = NUM2LONG(nv);
4388  if (n < 0) rb_raise(rb_eArgError, "negative sample number");
4389  if (n > len) n = len;
4390  if (n <= numberof(idx)) {
4391  for (i = 0; i < n; ++i) {
4392  rnds[i] = RAND_UPTO(len - i);
4393  }
4394  }
4395  k = len;
4396  len = RARRAY_LEN(ary);
4397  ptr = RARRAY_PTR(ary);
4398  if (len < k) {
4399  if (n <= numberof(idx)) {
4400  for (i = 0; i < n; ++i) {
4401  if (rnds[i] >= len) {
4402  return rb_ary_new2(0);
4403  }
4404  }
4405  }
4406  }
4407  if (n > len) n = len;
4408  switch (n) {
4409  case 0:
4410  return rb_ary_new2(0);
4411  case 1:
4412  i = rnds[0];
4413  return rb_ary_new4(1, &ptr[i]);
4414  case 2:
4415  i = rnds[0];
4416  j = rnds[1];
4417  if (j >= i) j++;
4418  return rb_ary_new3(2, ptr[i], ptr[j]);
4419  case 3:
4420  i = rnds[0];
4421  j = rnds[1];
4422  k = rnds[2];
4423  {
4424  long l = j, g = i;
4425  if (j >= i) l = i, g = ++j;
4426  if (k >= l && (++k >= g)) ++k;
4427  }
4428  return rb_ary_new3(3, ptr[i], ptr[j], ptr[k]);
4429  }
4430  if (n <= numberof(idx)) {
4431  VALUE *ptr_result;
4432  long sorted[numberof(idx)];
4433  sorted[0] = idx[0] = rnds[0];
4434  for (i=1; i<n; i++) {
4435  k = rnds[i];
4436  for (j = 0; j < i; ++j) {
4437  if (k < sorted[j]) break;
4438  ++k;
4439  }
4440  memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
4441  sorted[j] = idx[i] = k;
4442  }
4443  result = rb_ary_new2(n);
4444  ptr_result = RARRAY_PTR(result);
4445  for (i=0; i<n; i++) {
4446  ptr_result[i] = ptr[idx[i]];
4447  }
4448  }
4449  else {
4450  VALUE *ptr_result;
4451  result = rb_ary_new4(len, ptr);
4452  RBASIC(result)->klass = 0;
4453  ptr_result = RARRAY_PTR(result);
4454  RB_GC_GUARD(ary);
4455  for (i=0; i<n; i++) {
4456  j = RAND_UPTO(len-i) + i;
4457  nv = ptr_result[j];
4458  ptr_result[j] = ptr_result[i];
4459  ptr_result[i] = nv;
4460  }
4461  RBASIC(result)->klass = rb_cArray;
4462  }
4463  ARY_SET_LEN(result, n);
4464 
4465  return result;
4466 }
4467 
4468 static VALUE
4470 {
4471  long mul;
4472  VALUE n = Qnil;
4473  if (args && (RARRAY_LEN(args) > 0)) {
4474  n = RARRAY_PTR(args)[0];
4475  }
4476  if (RARRAY_LEN(self) == 0) return INT2FIX(0);
4477  if (n == Qnil) return DBL2NUM(INFINITY);
4478  mul = NUM2LONG(n);
4479  if (mul <= 0) return INT2FIX(0);
4480  return rb_funcall(rb_ary_length(self), '*', 1, LONG2FIX(mul));
4481 }
4482 
4483 /*
4484  * call-seq:
4485  * ary.cycle(n=nil) { |obj| block } -> nil
4486  * ary.cycle(n=nil) -> Enumerator
4487  *
4488  * Calls the given block for each element +n+ times or forever if +nil+ is
4489  * given.
4490  *
4491  * Does nothing if a non-positive number is given or the array is empty.
4492  *
4493  * Returns +nil+ if the loop has finished without getting interrupted.
4494  *
4495  * If no block is given, an Enumerator is returned instead.
4496  *
4497  * a = ["a", "b", "c"]
4498  * a.cycle { |x| puts x } # print, a, b, c, a, b, c,.. forever.
4499  * a.cycle(2) { |x| puts x } # print, a, b, c, a, b, c.
4500  *
4501  */
4502 
4503 static VALUE
4504 rb_ary_cycle(int argc, VALUE *argv, VALUE ary)
4505 {
4506  long n, i;
4507  VALUE nv = Qnil;
4508 
4509  rb_scan_args(argc, argv, "01", &nv);
4510 
4511  RETURN_SIZED_ENUMERATOR(ary, argc, argv, rb_ary_cycle_size);
4512  if (NIL_P(nv)) {
4513  n = -1;
4514  }
4515  else {
4516  n = NUM2LONG(nv);
4517  if (n <= 0) return Qnil;
4518  }
4519 
4520  while (RARRAY_LEN(ary) > 0 && (n < 0 || 0 < n--)) {
4521  for (i=0; i<RARRAY_LEN(ary); i++) {
4522  rb_yield(RARRAY_PTR(ary)[i]);
4523  }
4524  }
4525  return Qnil;
4526 }
4527 
4528 #define tmpbuf(n, size) rb_str_tmp_new((n)*(size))
4529 #define tmpbuf_discard(s) (rb_str_resize((s), 0L), RBASIC(s)->klass = rb_cString)
4530 #define tmpary(n) rb_ary_tmp_new(n)
4531 #define tmpary_discard(a) (ary_discard(a), RBASIC(a)->klass = rb_cArray)
4532 
4533 /*
4534  * Build a ruby array of the corresponding values and yield it to the
4535  * associated block.
4536  * Return the class of +values+ for reentry check.
4537  */
4538 static int
4539 yield_indexed_values(const VALUE values, const long r, const long *const p)
4540 {
4541  const VALUE result = rb_ary_new2(r);
4542  VALUE *const result_array = RARRAY_PTR(result);
4543  const VALUE *const values_array = RARRAY_PTR(values);
4544  long i;
4545 
4546  for (i = 0; i < r; i++) result_array[i] = values_array[p[i]];
4547  ARY_SET_LEN(result, r);
4548  rb_yield(result);
4549  return !RBASIC(values)->klass;
4550 }
4551 
4552 /*
4553  * Recursively compute permutations of +r+ elements of the set
4554  * <code>[0..n-1]</code>.
4555  *
4556  * When we have a complete permutation of array indexes, copy the values
4557  * at those indexes into a new array and yield that array.
4558  *
4559  * n: the size of the set
4560  * r: the number of elements in each permutation
4561  * p: the array (of size r) that we're filling in
4562  * index: what index we're filling in now
4563  * used: an array of booleans: whether a given index is already used
4564  * values: the Ruby array that holds the actual values to permute
4565  */
4566 static void
4567 permute0(long n, long r, long *p, long index, char *used, VALUE values)
4568 {
4569  long i;
4570  for (i = 0; i < n; i++) {
4571  if (used[i] == 0) {
4572  p[index] = i;
4573  if (index < r-1) { /* if not done yet */
4574  used[i] = 1; /* mark index used */
4575  permute0(n, r, p, index+1, /* recurse */
4576  used, values);
4577  used[i] = 0; /* index unused */
4578  }
4579  else {
4580  if (!yield_indexed_values(values, r, p)) {
4581  rb_raise(rb_eRuntimeError, "permute reentered");
4582  }
4583  }
4584  }
4585  }
4586 }
4587 
4588 /*
4589  * Returns the product of from, from-1, ..., from - how_many + 1.
4590  * http://en.wikipedia.org/wiki/Pochhammer_symbol
4591  */
4592 static VALUE
4593 descending_factorial(long from, long how_many)
4594 {
4595  VALUE cnt = LONG2FIX(how_many >= 0);
4596  while (how_many-- > 0) {
4597  cnt = rb_funcall(cnt, '*', 1, LONG2FIX(from--));
4598  }
4599  return cnt;
4600 }
4601 
4602 static VALUE
4603 binomial_coefficient(long comb, long size)
4604 {
4605  if (comb > size-comb) {
4606  comb = size-comb;
4607  }
4608  if (comb < 0) {
4609  return LONG2FIX(0);
4610  }
4611  return rb_funcall(descending_factorial(size, comb), id_div, 1, descending_factorial(comb, comb));
4612 }
4613 
4614 static VALUE
4616 {
4617  long n = RARRAY_LEN(ary);
4618  long k = (args && (RARRAY_LEN(args) > 0)) ? NUM2LONG(RARRAY_PTR(args)[0]) : n;
4619 
4620  return descending_factorial(n, k);
4621 }
4622 
4623 /*
4624  * call-seq:
4625  * ary.permutation { |p| block } -> ary
4626  * ary.permutation -> Enumerator
4627  * ary.permutation(n) { |p| block } -> ary
4628  * ary.permutation(n) -> Enumerator
4629  *
4630  * When invoked with a block, yield all permutations of length +n+ of the
4631  * elements of the array, then return the array itself.
4632  *
4633  * If +n+ is not specified, yield all permutations of all elements.
4634  *
4635  * The implementation makes no guarantees about the order in which the
4636  * permutations are yielded.
4637  *
4638  * If no block is given, an Enumerator is returned instead.
4639  *
4640  * Examples:
4641  *
4642  * a = [1, 2, 3]
4643  * a.permutation.to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
4644  * a.permutation(1).to_a #=> [[1],[2],[3]]
4645  * a.permutation(2).to_a #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
4646  * a.permutation(3).to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
4647  * a.permutation(0).to_a #=> [[]] # one permutation of length 0
4648  * a.permutation(4).to_a #=> [] # no permutations of length 4
4649  */
4650 
4651 static VALUE
4653 {
4654  VALUE num;
4655  long r, n, i;
4656 
4657  n = RARRAY_LEN(ary); /* Array length */
4658  RETURN_SIZED_ENUMERATOR(ary, argc, argv, rb_ary_permutation_size); /* Return enumerator if no block */
4659  rb_scan_args(argc, argv, "01", &num);
4660  r = NIL_P(num) ? n : NUM2LONG(num); /* Permutation size from argument */
4661 
4662  if (r < 0 || n < r) {
4663  /* no permutations: yield nothing */
4664  }
4665  else if (r == 0) { /* exactly one permutation: the zero-length array */
4666  rb_yield(rb_ary_new2(0));
4667  }
4668  else if (r == 1) { /* this is a special, easy case */
4669  for (i = 0; i < RARRAY_LEN(ary); i++) {
4670  rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
4671  }
4672  }
4673  else { /* this is the general case */
4674  volatile VALUE t0 = tmpbuf(r,sizeof(long));
4675  long *p = (long*)RSTRING_PTR(t0);
4676  volatile VALUE t1 = tmpbuf(n,sizeof(char));
4677  char *used = (char*)RSTRING_PTR(t1);
4678  VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4679  RBASIC(ary0)->klass = 0;
4680 
4681  MEMZERO(used, char, n); /* initialize array */
4682 
4683  permute0(n, r, p, 0, used, ary0); /* compute and yield permutations */
4684  tmpbuf_discard(t0);
4685  tmpbuf_discard(t1);
4686  RBASIC(ary0)->klass = rb_cArray;
4687  }
4688  return ary;
4689 }
4690 
4691 static VALUE
4693 {
4694  long n = RARRAY_LEN(ary);
4695  long k = NUM2LONG(RARRAY_PTR(args)[0]);
4696 
4697  return binomial_coefficient(k, n);
4698 }
4699 
4700 /*
4701  * call-seq:
4702  * ary.combination(n) { |c| block } -> ary
4703  * ary.combination(n) -> Enumerator
4704  *
4705  * When invoked with a block, yields all combinations of length +n+ of elements
4706  * from the array and then returns the array itself.
4707  *
4708  * The implementation makes no guarantees about the order in which the
4709  * combinations are yielded.
4710  *
4711  * If no block is given, an Enumerator is returned instead.
4712  *
4713  * Examples:
4714  *
4715  * a = [1, 2, 3, 4]
4716  * a.combination(1).to_a #=> [[1],[2],[3],[4]]
4717  * a.combination(2).to_a #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
4718  * a.combination(3).to_a #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
4719  * a.combination(4).to_a #=> [[1,2,3,4]]
4720  * a.combination(0).to_a #=> [[]] # one combination of length 0
4721  * a.combination(5).to_a #=> [] # no combinations of length 5
4722  *
4723  */
4724 
4725 static VALUE
4727 {
4728  long n, i, len;
4729 
4730  n = NUM2LONG(num);
4732  len = RARRAY_LEN(ary);
4733  if (n < 0 || len < n) {
4734  /* yield nothing */
4735  }
4736  else if (n == 0) {
4737  rb_yield(rb_ary_new2(0));
4738  }
4739  else if (n == 1) {
4740  for (i = 0; i < len; i++) {
4741  rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
4742  }
4743  }
4744  else {
4745  VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4746  volatile VALUE t0;
4747  long *stack = ALLOCV_N(long, t0, n+1);
4748  long lev = 0;
4749 
4750  RBASIC(ary0)->klass = 0;
4751  MEMZERO(stack+1, long, n);
4752  stack[0] = -1;
4753  for (;;) {
4754  for (lev++; lev < n; lev++) {
4755  stack[lev+1] = stack[lev]+1;
4756  }
4757  if (!yield_indexed_values(ary0, n, stack+1)) {
4758  rb_raise(rb_eRuntimeError, "combination reentered");
4759  }
4760  do {
4761  if (lev == 0) goto done;
4762  stack[lev--]++;
4763  } while (stack[lev+1]+n == len+lev+1);
4764  }
4765  done:
4766  ALLOCV_END(t0);
4767  RBASIC(ary0)->klass = rb_cArray;
4768  }
4769  return ary;
4770 }
4771 
4772 /*
4773  * Recursively compute repeated permutations of +r+ elements of the set
4774  * <code>[0..n-1]</code>.
4775  *
4776  * When we have a complete repeated permutation of array indexes, copy the
4777  * values at those indexes into a new array and yield that array.
4778  *
4779  * n: the size of the set
4780  * r: the number of elements in each permutation
4781  * p: the array (of size r) that we're filling in
4782  * index: what index we're filling in now
4783  * values: the Ruby array that holds the actual values to permute
4784  */
4785 static void
4786 rpermute0(long n, long r, long *p, long index, VALUE values)
4787 {
4788  long i;
4789  for (i = 0; i < n; i++) {
4790  p[index] = i;
4791  if (index < r-1) { /* if not done yet */
4792  rpermute0(n, r, p, index+1, values); /* recurse */
4793  }
4794  else {
4795  if (!yield_indexed_values(values, r, p)) {
4796  rb_raise(rb_eRuntimeError, "repeated permute reentered");
4797  }
4798  }
4799  }
4800 }
4801 
4802 static VALUE
4804 {
4805  long n = RARRAY_LEN(ary);
4806  long k = NUM2LONG(RARRAY_PTR(args)[0]);
4807 
4808  if (k < 0) {
4809  return LONG2FIX(0);
4810  }
4811 
4812  return rb_funcall(LONG2NUM(n), id_power, 1, LONG2NUM(k));
4813 }
4814 
4815 /*
4816  * call-seq:
4817  * ary.repeated_permutation(n) { |p| block } -> ary
4818  * ary.repeated_permutation(n) -> Enumerator
4819  *
4820  * When invoked with a block, yield all repeated permutations of length +n+ of
4821  * the elements of the array, then return the array itself.
4822  *
4823  * The implementation makes no guarantees about the order in which the repeated
4824  * permutations are yielded.
4825  *
4826  * If no block is given, an Enumerator is returned instead.
4827  *
4828  * Examples:
4829  *
4830  * a = [1, 2]
4831  * a.repeated_permutation(1).to_a #=> [[1], [2]]
4832  * a.repeated_permutation(2).to_a #=> [[1,1],[1,2],[2,1],[2,2]]
4833  * a.repeated_permutation(3).to_a #=> [[1,1,1],[1,1,2],[1,2,1],[1,2,2],
4834  * # [2,1,1],[2,1,2],[2,2,1],[2,2,2]]
4835  * a.repeated_permutation(0).to_a #=> [[]] # one permutation of length 0
4836  */
4837 
4838 static VALUE
4840 {
4841  long r, n, i;
4842 
4843  n = RARRAY_LEN(ary); /* Array length */
4844  RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_repeated_permutation_size); /* Return Enumerator if no block */
4845  r = NUM2LONG(num); /* Permutation size from argument */
4846 
4847  if (r < 0) {
4848  /* no permutations: yield nothing */
4849  }
4850  else if (r == 0) { /* exactly one permutation: the zero-length array */
4851  rb_yield(rb_ary_new2(0));
4852  }
4853  else if (r == 1) { /* this is a special, easy case */
4854  for (i = 0; i < RARRAY_LEN(ary); i++) {
4855  rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
4856  }
4857  }
4858  else { /* this is the general case */
4859  volatile VALUE t0 = tmpbuf(r, sizeof(long));
4860  long *p = (long*)RSTRING_PTR(t0);
4861  VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4862  RBASIC(ary0)->klass = 0;
4863 
4864  rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
4865  tmpbuf_discard(t0);
4866  RBASIC(ary0)->klass = rb_cArray;
4867  }
4868  return ary;
4869 }
4870 
4871 static void
4872 rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
4873 {
4874  if (rest > 0) {
4875  for (; index < n; ++index) {
4876  p[r-rest] = index;
4877  rcombinate0(n, r, p, index, rest-1, values);
4878  }
4879  }
4880  else {
4881  if (!yield_indexed_values(values, r, p)) {
4882  rb_raise(rb_eRuntimeError, "repeated combination reentered");
4883  }
4884  }
4885 }
4886 
4887 static VALUE
4889 {
4890  long n = RARRAY_LEN(ary);
4891  long k = NUM2LONG(RARRAY_PTR(args)[0]);
4892  if (k == 0) {
4893  return LONG2FIX(1);
4894  }
4895  return binomial_coefficient(k, n + k - 1);
4896 }
4897 
4898 /*
4899  * call-seq:
4900  * ary.repeated_combination(n) { |c| block } -> ary
4901  * ary.repeated_combination(n) -> Enumerator
4902  *
4903  * When invoked with a block, yields all repeated combinations of length +n+ of
4904  * elements from the array and then returns the array itself.
4905  *
4906  * The implementation makes no guarantees about the order in which the repeated
4907  * combinations are yielded.
4908  *
4909  * If no block is given, an Enumerator is returned instead.
4910  *
4911  * Examples:
4912  *
4913  * a = [1, 2, 3]
4914  * a.repeated_combination(1).to_a #=> [[1], [2], [3]]
4915  * a.repeated_combination(2).to_a #=> [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
4916  * a.repeated_combination(3).to_a #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
4917  * # [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
4918  * 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],
4919  * # [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
4920  * # [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]]
4921  * a.repeated_combination(0).to_a #=> [[]] # one combination of length 0
4922  *
4923  */
4924 
4925 static VALUE
4927 {
4928  long n, i, len;
4929 
4930  n = NUM2LONG(num); /* Combination size from argument */
4931  RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_repeated_combination_size); /* Return enumerator if no block */
4932  len = RARRAY_LEN(ary);
4933  if (n < 0) {
4934  /* yield nothing */
4935  }
4936  else if (n == 0) {
4937  rb_yield(rb_ary_new2(0));
4938  }
4939  else if (n == 1) {
4940  for (i = 0; i < len; i++) {
4941  rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
4942  }
4943  }
4944  else if (len == 0) {
4945  /* yield nothing */
4946  }
4947  else {
4948  volatile VALUE t0 = tmpbuf(n, sizeof(long));
4949  long *p = (long*)RSTRING_PTR(t0);
4950  VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4951  RBASIC(ary0)->klass = 0;
4952 
4953  rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
4954  tmpbuf_discard(t0);
4955  RBASIC(ary0)->klass = rb_cArray;
4956  }
4957  return ary;
4958 }
4959 
4960 /*
4961  * call-seq:
4962  * ary.product(other_ary, ...) -> new_ary
4963  * ary.product(other_ary, ...) { |p| block } -> ary
4964  *
4965  * Returns an array of all combinations of elements from all arrays.
4966  *
4967  * The length of the returned array is the product of the length of +self+ and
4968  * the argument arrays.
4969  *
4970  * If given a block, #product will yield all combinations and return +self+
4971  * instead.
4972  *
4973  * [1,2,3].product([4,5]) #=> [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]
4974  * [1,2].product([1,2]) #=> [[1,1],[1,2],[2,1],[2,2]]
4975  * [1,2].product([3,4],[5,6]) #=> [[1,3,5],[1,3,6],[1,4,5],[1,4,6],
4976  * # [2,3,5],[2,3,6],[2,4,5],[2,4,6]]
4977  * [1,2].product() #=> [[1],[2]]
4978  * [1,2].product([]) #=> []
4979  */
4980 
4981 static VALUE
4982 rb_ary_product(int argc, VALUE *argv, VALUE ary)
4983 {
4984  int n = argc+1; /* How many arrays we're operating on */
4985  volatile VALUE t0 = tmpary(n);
4986  volatile VALUE t1 = tmpbuf(n, sizeof(int));
4987  VALUE *arrays = RARRAY_PTR(t0); /* The arrays we're computing the product of */
4988  int *counters = (int*)RSTRING_PTR(t1); /* The current position in each one */
4989  VALUE result = Qnil; /* The array we'll be returning, when no block given */
4990  long i,j;
4991  long resultlen = 1;
4992 
4993  RBASIC(t0)->klass = 0;
4994  RBASIC(t1)->klass = 0;
4995 
4996  /* initialize the arrays of arrays */
4997  ARY_SET_LEN(t0, n);
4998  arrays[0] = ary;
4999  for (i = 1; i < n; i++) arrays[i] = Qnil;
5000  for (i = 1; i < n; i++) arrays[i] = to_ary(argv[i-1]);
5001 
5002  /* initialize the counters for the arrays */
5003  for (i = 0; i < n; i++) counters[i] = 0;
5004 
5005  /* Otherwise, allocate and fill in an array of results */
5006  if (rb_block_given_p()) {
5007  /* Make defensive copies of arrays; exit if any is empty */
5008  for (i = 0; i < n; i++) {
5009  if (RARRAY_LEN(arrays[i]) == 0) goto done;
5010  arrays[i] = ary_make_shared_copy(arrays[i]);
5011  }
5012  }
5013  else {
5014  /* Compute the length of the result array; return [] if any is empty */
5015  for (i = 0; i < n; i++) {
5016  long k = RARRAY_LEN(arrays[i]);
5017  if (k == 0) {
5018  result = rb_ary_new2(0);
5019  goto done;
5020  }
5021  if (MUL_OVERFLOW_LONG_P(resultlen, k))
5022  rb_raise(rb_eRangeError, "too big to product");
5023  resultlen *= k;
5024  }
5025  result = rb_ary_new2(resultlen);
5026  }
5027  for (;;) {
5028  int m;
5029  /* fill in one subarray */
5030  VALUE subarray = rb_ary_new2(n);
5031  for (j = 0; j < n; j++) {
5032  rb_ary_push(subarray, rb_ary_entry(arrays[j], counters[j]));
5033  }
5034 
5035  /* put it on the result array */
5036  if (NIL_P(result)) {
5037  FL_SET(t0, FL_USER5);
5038  rb_yield(subarray);
5039  if (! FL_TEST(t0, FL_USER5)) {
5040  rb_raise(rb_eRuntimeError, "product reentered");
5041  }
5042  else {
5043  FL_UNSET(t0, FL_USER5);
5044  }
5045  }
5046  else {
5047  rb_ary_push(result, subarray);
5048  }
5049 
5050  /*
5051  * Increment the last counter. If it overflows, reset to 0
5052  * and increment the one before it.
5053  */
5054  m = n-1;
5055  counters[m]++;
5056  while (counters[m] == RARRAY_LEN(arrays[m])) {
5057  counters[m] = 0;
5058  /* If the first counter overflows, we are done */
5059  if (--m < 0) goto done;
5060  counters[m]++;
5061  }
5062  }
5063 done:
5064  tmpary_discard(t0);
5065  tmpbuf_discard(t1);
5066 
5067  return NIL_P(result) ? ary : result;
5068 }
5069 
5070 /*
5071  * call-seq:
5072  * ary.take(n) -> new_ary
5073  *
5074  * Returns first +n+ elements from the array.
5075  *
5076  * If a negative number is given, raises an ArgumentError.
5077  *
5078  * See also Array#drop
5079  *
5080  * a = [1, 2, 3, 4, 5, 0]
5081  * a.take(3) #=> [1, 2, 3]
5082  *
5083  */
5084 
5085 static VALUE
5087 {
5088  long len = NUM2LONG(n);
5089  if (len < 0) {
5090  rb_raise(rb_eArgError, "attempt to take negative size");
5091  }
5092  return rb_ary_subseq(obj, 0, len);
5093 }
5094 
5095 /*
5096  * call-seq:
5097  * ary.take_while { |arr| block } -> new_ary
5098  * ary.take_while -> Enumerator
5099  *
5100  * Passes elements to the block until the block returns +nil+ or +false+, then
5101  * stops iterating and returns an array of all prior elements.
5102  *
5103  * If no block is given, an Enumerator is returned instead.
5104  *
5105  * See also Array#drop_while
5106  *
5107  * a = [1, 2, 3, 4, 5, 0]
5108  * a.take_while { |i| i < 3 } #=> [1, 2]
5109  *
5110  */
5111 
5112 static VALUE
5114 {
5115  long i;
5116 
5117  RETURN_ENUMERATOR(ary, 0, 0);
5118  for (i = 0; i < RARRAY_LEN(ary); i++) {
5119  if (!RTEST(rb_yield(RARRAY_PTR(ary)[i]))) break;
5120  }
5121  return rb_ary_take(ary, LONG2FIX(i));
5122 }
5123 
5124 /*
5125  * call-seq:
5126  * ary.drop(n) -> new_ary
5127  *
5128  * Drops first +n+ elements from +ary+ and returns the rest of the elements in
5129  * an array.
5130  *
5131  * If a negative number is given, raises an ArgumentError.
5132  *
5133  * See also Array#take
5134  *
5135  * a = [1, 2, 3, 4, 5, 0]
5136  * a.drop(3) #=> [4, 5, 0]
5137  *
5138  */
5139 
5140 static VALUE
5142 {
5143  VALUE result;
5144  long pos = NUM2LONG(n);
5145  if (pos < 0) {
5146  rb_raise(rb_eArgError, "attempt to drop negative size");
5147  }
5148 
5149  result = rb_ary_subseq(ary, pos, RARRAY_LEN(ary));
5150  if (result == Qnil) result = rb_ary_new();
5151  return result;
5152 }
5153 
5154 /*
5155  * call-seq:
5156  * ary.drop_while { |arr| block } -> new_ary
5157  * ary.drop_while -> Enumerator
5158  *
5159  * Drops elements up to, but not including, the first element for which the
5160  * block returns +nil+ or +false+ and returns an array containing the
5161  * remaining elements.
5162  *
5163  * If no block is given, an Enumerator is returned instead.
5164  *
5165  * See also Array#take_while
5166  *
5167  * a = [1, 2, 3, 4, 5, 0]
5168  * a.drop_while {|i| i < 3 } #=> [3, 4, 5, 0]
5169  *
5170  */
5171 
5172 static VALUE
5174 {
5175  long i;
5176 
5177  RETURN_ENUMERATOR(ary, 0, 0);
5178  for (i = 0; i < RARRAY_LEN(ary); i++) {
5179  if (!RTEST(rb_yield(RARRAY_PTR(ary)[i]))) break;
5180  }
5181  return rb_ary_drop(ary, LONG2FIX(i));
5182 }
5183 
5184 /*
5185  * Arrays are ordered, integer-indexed collections of any object.
5186  *
5187  * Array indexing starts at 0, as in C or Java. A negative index is assumed
5188  * to be relative to the end of the array---that is, an index of -1 indicates
5189  * the last element of the array, -2 is the next to last element in the
5190  * array, and so on.
5191  *
5192  * == Creating Arrays
5193  *
5194  * A new array can be created by using the literal constructor
5195  * <code>[]</code>. Arrays can contain different types of objects. For
5196  * example, the array below contains an Integer, a String and a Float:
5197  *
5198  * ary = [1, "two", 3.0] #=> [1, "two", 3.0]
5199  *
5200  * An array can also be created by explicitly calling Array.new with zero, one
5201  * (the initial size of the Array) or two arguments (the initial size and a
5202  * default object).
5203  *
5204  * ary = Array.new #=> []
5205  * Array.new(3) #=> [nil, nil, nil]
5206  * Array.new(3, true) #=> [true, true, true]
5207  *
5208  * Note that the second argument populates the array with references to the
5209  * same object. Therefore, it is only recommended in cases when you need to
5210  * instantiate arrays with natively immutable objects such as Symbols,
5211  * numbers, true or false.
5212  *
5213  * To create an array with separate objects a block can be passed instead.
5214  * This method is safe to use with mutable objects such as hashes, strings or
5215  * other arrays:
5216  *
5217  * Array.new(4) { Hash.new } #=> [{}, {}, {}, {}]
5218  *
5219  * This is also a quick way to build up multi-dimensional arrays:
5220  *
5221  * empty_table = Array.new(3) { Array.new(3) }
5222  * #=> [[nil, nil, nil], [nil, nil, nil], [nil, nil, nil]]
5223  *
5224  * An array can also be created by using the Array() method, provided by
5225  * Kernel, which tries to call #to_ary, then #to_a on its argument.
5226  *
5227  * Array({:a => "a", :b => "b"}) #=> [[:a, "a"], [:b, "b"]]
5228  *
5229  * == Example Usage
5230  *
5231  * In addition to the methods it mixes in through the Enumerable module, the
5232  * Array class has proprietary methods for accessing, searching and otherwise
5233  * manipulating arrays.
5234  *
5235  * Some of the more common ones are illustrated below.
5236  *
5237  * == Accessing Elements
5238  *
5239  * Elements in an array can be retrieved using the Array#[] method. It can
5240  * take a single integer argument (a numeric index), a pair of arguments
5241  * (start and length) or a range.
5242  *
5243  * arr = [1, 2, 3, 4, 5, 6]
5244  * arr[2] #=> 3
5245  * arr[100] #=> nil
5246  * arr[-3] #=> 4
5247  * arr[2, 3] #=> [3, 4, 5]
5248  * arr[1..4] #=> [2, 3, 4, 5]
5249  *
5250  * Another way to access a particular array element is by using the #at method
5251  *
5252  * arr.at(0) #=> 1
5253  *
5254  * The #slice method works in an identical manner to Array#[].
5255  *
5256  * To raise an error for indices outside of the array bounds or else to
5257  * provide a default value when that happens, you can use #fetch.
5258  *
5259  * arr = ['a', 'b', 'c', 'd', 'e', 'f']
5260  * arr.fetch(100) #=> IndexError: index 100 outside of array bounds: -6...6
5261  * arr.fetch(100, "oops") #=> "oops"
5262  *
5263  * The special methods #first and #last will return the first and last
5264  * elements of an array, respectively.
5265  *
5266  * arr.first #=> 1
5267  * arr.last #=> 6
5268  *
5269  * To return the first +n+ elements of an array, use #take
5270  *
5271  * arr.take(3) #=> [1, 2, 3]
5272  *
5273  * #drop does the opposite of #take, by returning the elements after +n+
5274  * elements have been dropped:
5275  *
5276  * arr.drop(3) #=> [4, 5, 6]
5277  *
5278  * == Obtaining Information about an Array
5279  *
5280  * Arrays keep track of their own length at all times. To query an array
5281  * about the number of elements it contains, use #length, #count or #size.
5282  *
5283  * browsers = ['Chrome', 'Firefox', 'Safari', 'Opera', 'IE']
5284  * browsers.length #=> 5
5285  * browsers.count #=> 5
5286  *
5287  * To check whether an array contains any elements at all
5288  *
5289  * browsers.empty? #=> false
5290  *
5291  * To check whether a particular item is included in the array
5292  *
5293  * browsers.include?('Konqueror') #=> false
5294  *
5295  * == Adding Items to Arrays
5296  *
5297  * Items can be added to the end of an array by using either #push or #<<
5298  *
5299  * arr = [1, 2, 3, 4]
5300  * arr.push(5) #=> [1, 2, 3, 4, 5]
5301  * arr << 6 #=> [1, 2, 3, 4, 5, 6]
5302  *
5303  * #unshift will add a new item to the beginning of an array.
5304  *
5305  * arr.unshift(0) #=> [0, 1, 2, 3, 4, 5, 6]
5306  *
5307  * With #insert you can add a new element to an array at any position.
5308  *
5309  * arr.insert(3, 'apple') #=> [0, 1, 2, 'apple', 3, 4, 5, 6]
5310  *
5311  * Using the #insert method, you can also insert multiple values at once:
5312  *
5313  * arr.insert(3, 'orange', 'pear', 'grapefruit')
5314  * #=> [0, 1, 2, "orange", "pear", "grapefruit", "apple", 3, 4, 5, 6]
5315  *
5316  * == Removing Items from an Array
5317  *
5318  * The method #pop removes the last element in an array and returns it:
5319  *
5320  * arr = [1, 2, 3, 4, 5, 6]
5321  * arr.pop #=> 6
5322  * arr #=> [1, 2, 3, 4, 5]
5323  *
5324  * To retrieve and at the same time remove the first item, use #shift:
5325  *
5326  * arr.shift #=> 1
5327  * arr #=> [2, 3, 4, 5]
5328  *
5329  * To delete an element at a particular index:
5330  *
5331  * arr.delete_at(2) #=> 4
5332  * arr #=> [2, 3, 5]
5333  *
5334  * To delete a particular element anywhere in an array, use #delete:
5335  *
5336  * arr = [1, 2, 2, 3]
5337  * arr.delete(2) #=> [1, 3]
5338  *
5339  * A useful method if you need to remove +nil+ values from an array is
5340  * #compact:
5341  *
5342  * arr = ['foo', 0, nil, 'bar', 7, 'baz', nil]
5343  * arr.compact #=> ['foo', 0, 'bar', 7, 'baz']
5344  * arr #=> ['foo', 0, nil, 'bar', 7, 'baz', nil]
5345  * arr.compact! #=> ['foo', 0, 'bar', 7, 'baz']
5346  * arr #=> ['foo', 0, 'bar', 7, 'baz']
5347  *
5348  * Another common need is to remove duplicate elements from an array.
5349  *
5350  * It has the non-destructive #uniq, and destructive method #uniq!
5351  *
5352  * arr = [2, 5, 6, 556, 6, 6, 8, 9, 0, 123, 556]
5353  * arr.uniq #=> [2, 5, 6, 556, 8, 9, 0, 123]
5354  *
5355  * == Iterating over Arrays
5356  *
5357  * Like all classes that include the Enumerable module, Array has an each
5358  * method, which defines what elements should be iterated over and how. In
5359  * case of Array's #each, all elements in the Array instance are yielded to
5360  * the supplied block in sequence.
5361  *
5362  * Note that this operation leaves the array unchanged.
5363  *
5364  * arr = [1, 2, 3, 4, 5]
5365  * arr.each { |a| print a -= 10, " " }
5366  * # prints: -9 -8 -7 -6 -5
5367  * #=> [1, 2, 3, 4, 5]
5368  *
5369  * Another sometimes useful iterator is #reverse_each which will iterate over
5370  * the elements in the array in reverse order.
5371  *
5372  * words = %w[rats live on no evil star]
5373  * str = ""
5374  * words.reverse_each { |word| str += "#{word.reverse} " }
5375  * str #=> "rats live on no evil star "
5376  *
5377  * The #map method can be used to create a new array based on the original
5378  * array, but with the values modified by the supplied block:
5379  *
5380  * arr.map { |a| 2*a } #=> [2, 4, 6, 8, 10]
5381  * arr #=> [1, 2, 3, 4, 5]
5382  * arr.map! { |a| a**2 } #=> [1, 4, 9, 16, 25]
5383  * arr #=> [1, 4, 9, 16, 25]
5384  *
5385  * == Selecting Items from an Array
5386  *
5387  * Elements can be selected from an array according to criteria defined in a
5388  * block. The selection can happen in a destructive or a non-destructive
5389  * manner. While the destructive operations will modify the array they were
5390  * called on, the non-destructive methods usually return a new array with the
5391  * selected elements, but leave the original array unchanged.
5392  *
5393  * === Non-destructive Selection
5394  *
5395  * arr = [1, 2, 3, 4, 5, 6]
5396  * arr.select { |a| a > 3 } #=> [4, 5, 6]
5397  * arr.reject { |a| a < 3 } #=> [3, 4, 5, 6]
5398  * arr.drop_while { |a| a < 4 } #=> [4, 5, 6]
5399  * arr #=> [1, 2, 3, 4, 5, 6]
5400  *
5401  * === Destructive Selection
5402  *
5403  * #select! and #reject! are the corresponding destructive methods to #select
5404  * and #reject
5405  *
5406  * Similar to #select vs. #reject, #delete_if and #keep_if have the exact
5407  * opposite result when supplied with the same block:
5408  *
5409  * arr.delete_if { |a| a < 4 } #=> [4, 5, 6]
5410  * arr #=> [4, 5, 6]
5411  *
5412  * arr = [1, 2, 3, 4, 5, 6]
5413  * arr.keep_if { |a| a < 4 } #=> [1, 2, 3]
5414  * arr #=> [1, 2, 3]
5415  *
5416  */
5417 
5418 void
5420 {
5421 #undef rb_intern
5422 #define rb_intern(str) rb_intern_const(str)
5423 
5424  rb_cArray = rb_define_class("Array", rb_cObject);
5426 
5430  rb_define_method(rb_cArray, "initialize", rb_ary_initialize, -1);
5431  rb_define_method(rb_cArray, "initialize_copy", rb_ary_replace, 1);
5432 
5433  rb_define_method(rb_cArray, "inspect", rb_ary_inspect, 0);
5434  rb_define_alias(rb_cArray, "to_s", "inspect");
5435  rb_define_method(rb_cArray, "to_a", rb_ary_to_a, 0);
5437  rb_define_method(rb_cArray, "frozen?", rb_ary_frozen_p, 0);
5438 
5440  rb_define_method(rb_cArray, "eql?", rb_ary_eql, 1);
5441  rb_define_method(rb_cArray, "hash", rb_ary_hash, 0);
5442 
5444  rb_define_method(rb_cArray, "[]=", rb_ary_aset, -1);
5446  rb_define_method(rb_cArray, "fetch", rb_ary_fetch, -1);
5447  rb_define_method(rb_cArray, "first", rb_ary_first, -1);
5448  rb_define_method(rb_cArray, "last", rb_ary_last, -1);
5449  rb_define_method(rb_cArray, "concat", rb_ary_concat, 1);
5453  rb_define_method(rb_cArray, "shift", rb_ary_shift_m, -1);
5454  rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
5455  rb_define_method(rb_cArray, "insert", rb_ary_insert, -1);
5456  rb_define_method(rb_cArray, "each", rb_ary_each, 0);
5457  rb_define_method(rb_cArray, "each_index", rb_ary_each_index, 0);
5458  rb_define_method(rb_cArray, "reverse_each", rb_ary_reverse_each, 0);
5459  rb_define_method(rb_cArray, "length", rb_ary_length, 0);
5460  rb_define_alias(rb_cArray, "size", "length");
5461  rb_define_method(rb_cArray, "empty?", rb_ary_empty_p, 0);
5462  rb_define_method(rb_cArray, "find_index", rb_ary_index, -1);
5463  rb_define_method(rb_cArray, "index", rb_ary_index, -1);
5464  rb_define_method(rb_cArray, "rindex", rb_ary_rindex, -1);
5468  rb_define_method(rb_cArray, "rotate", rb_ary_rotate_m, -1);
5470  rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
5473  rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
5477  rb_define_method(rb_cArray, "select", rb_ary_select, 0);
5479  rb_define_method(rb_cArray, "keep_if", rb_ary_keep_if, 0);
5480  rb_define_method(rb_cArray, "values_at", rb_ary_values_at, -1);
5481  rb_define_method(rb_cArray, "delete", rb_ary_delete, 1);
5482  rb_define_method(rb_cArray, "delete_at", rb_ary_delete_at_m, 1);
5483  rb_define_method(rb_cArray, "delete_if", rb_ary_delete_if, 0);
5484  rb_define_method(rb_cArray, "reject", rb_ary_reject, 0);
5486  rb_define_method(rb_cArray, "zip", rb_ary_zip, -1);
5487  rb_define_method(rb_cArray, "transpose", rb_ary_transpose, 0);
5488  rb_define_method(rb_cArray, "replace", rb_ary_replace, 1);
5489  rb_define_method(rb_cArray, "clear", rb_ary_clear, 0);
5490  rb_define_method(rb_cArray, "fill", rb_ary_fill, -1);
5491  rb_define_method(rb_cArray, "include?", rb_ary_includes, 1);
5493 
5494  rb_define_method(rb_cArray, "slice", rb_ary_aref, -1);
5496 
5497  rb_define_method(rb_cArray, "assoc", rb_ary_assoc, 1);
5498  rb_define_method(rb_cArray, "rassoc", rb_ary_rassoc, 1);
5499 
5502 
5506 
5507  rb_define_method(rb_cArray, "uniq", rb_ary_uniq, 0);
5509  rb_define_method(rb_cArray, "compact", rb_ary_compact, 0);
5511  rb_define_method(rb_cArray, "flatten", rb_ary_flatten, -1);
5513  rb_define_method(rb_cArray, "count", rb_ary_count, -1);
5515  rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, -1);
5516  rb_define_method(rb_cArray, "sample", rb_ary_sample, -1);
5517  rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1);
5518  rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1);
5519  rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
5520  rb_define_method(rb_cArray, "repeated_permutation", rb_ary_repeated_permutation, 1);
5521  rb_define_method(rb_cArray, "repeated_combination", rb_ary_repeated_combination, 1);
5522  rb_define_method(rb_cArray, "product", rb_ary_product, -1);
5523 
5524  rb_define_method(rb_cArray, "take", rb_ary_take, 1);
5525  rb_define_method(rb_cArray, "take_while", rb_ary_take_while, 0);
5526  rb_define_method(rb_cArray, "drop", rb_ary_drop, 1);
5527  rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0);
5528  rb_define_method(rb_cArray, "bsearch", rb_ary_bsearch, 0);
5529 
5530  id_cmp = rb_intern("<=>");
5531  sym_random = ID2SYM(rb_intern("random"));
5532  id_div = rb_intern("div");
5533  id_power = rb_intern("**");
5534 }
VALUE data
Definition: tcltklib.c:3367
static VALUE rb_ary_transpose(VALUE ary)
Definition: array.c:3116
static ID id_cmp
Definition: array.c:31
#define RB_TYPE_P(obj, type)
static void ary_reverse(VALUE *p1, VALUE *p2)
Definition: array.c:2021
RARRAY_PTR(q->result)[0]
volatile VALUE tmp
Definition: tcltklib.c:10208
#define RUBY_DTRACE_ARRAY_CREATE(arg0, arg1, arg2)
Definition: probes.h:56
static VALUE recursive_cmp(VALUE ary1, VALUE ary2, int recur)
Definition: array.c:3668
VALUE rb_ary_unshift(VALUE ary, VALUE item)
Definition: array.c:1071
static void ary_ensure_room_for_push(VALUE ary, long add_len)
Definition: array.c:288
static void ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first)
Definition: array.c:1820
ssize_t n
Definition: bigdecimal.c:5676
volatile VALUE ary
Definition: tcltklib.c:9712
static VALUE ary_reject(VALUE orig, VALUE result)
Definition: array.c:2915
VALUE rb_ary_pop(VALUE ary)
Definition: array.c:866
VALUE rb_ary_new4(long n, const VALUE *elts)
Definition: array.c:451
VALUE rb_ary_entry(VALUE ary, long offset)
Definition: array.c:1088
ary_take_pos_flags
Definition: array.c:781
int rb_eql(VALUE, VALUE)
Definition: object.c:67
#define MUL_OVERFLOW_LONG_P(a, b)
void rb_bug(const char *fmt,...)
Definition: error.c:295
static VALUE rb_ary_keep_if(VALUE ary)
Definition: array.c:2707
#define FALSE
Definition: nkf.h:174
void rb_enc_copy(VALUE obj1, VALUE obj2)
Definition: encoding.c:856
static VALUE rb_ary_cycle_size(VALUE self, VALUE args)
Definition: array.c:4469
#define OBJ_INFECT(x, s)
VALUE rb_ary_freeze(VALUE ary)
Definition: array.c:330
static VALUE rb_ary_times(VALUE ary, VALUE times)
Definition: array.c:3399
const char * rb_obj_classname(VALUE)
Definition: variable.c:396
Win32OLEIDispatch * p
Definition: win32ole.c:786
static VALUE rb_ary_drop_while(VALUE ary)
Definition: array.c:5173
static VALUE rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
Definition: array.c:707
#define UNLIMITED_ARGUMENTS
static VALUE rb_ary_at(VALUE ary, VALUE pos)
Definition: array.c:1197
#define FL_TEST(x, f)
#define ARY_SET_EMBED_LEN(ary, n)
Definition: array.c:84
static void rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
Definition: array.c:1421
static int max(int a, int b)
Definition: strftime.c:141
int st_lookup(st_table *, st_data_t, st_data_t *)
void rb_define_singleton_method(VALUE obj, const char *name, VALUE(*func)(ANYARGS), int argc)
Defines a singleton method for obj.
Definition: class.c:1501
VALUE rb_str_buf_append(VALUE, VALUE)
Definition: string.c:2109
#define ARY_MAX_SIZE
Definition: array.c:34
static VALUE rb_ary_combination(VALUE ary, VALUE num)
Definition: array.c:4726
C_block * out
Definition: crypt.c:308
VALUE rb_ary_sort(VALUE ary)
Definition: array.c:2361
#define FL_SET(x, f)
st_table * st_init_numtable(void)
Definition: st.c:272
VALUE rb_ary_subseq(VALUE ary, long beg, long len)
Definition: array.c:1097
static VALUE rb_ary_sample(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4362
#define FL_SET_EMBED(a)
Definition: array.c:68
static VALUE rb_ary_compact(VALUE ary)
Definition: array.c:4074
VALUE rb_ary_delete_at(VALUE ary, long pos)
Definition: array.c:2801
SSL_METHOD *(* func)(void)
Definition: ossl_ssl.c:108
#define rb_usascii_str_new2
int rb_str_cmp(VALUE, VALUE)
Definition: string.c:2312
void rb_gc_force_recycle(VALUE)
Definition: gc.c:2963
ssize_t i
Definition: bigdecimal.c:5676
static VALUE take_items(VALUE obj, long n)
Definition: array.c:3031
#define rb_check_frozen(obj)
RUBY_EXTERN void * memmove(void *, const void *, size_t)
Definition: memmove.c:7
VALUE rb_ary_shift(VALUE ary)
Definition: array.c:916
static VALUE rb_ary_reverse_each(VALUE ary)
Definition: array.c:1716
#define FL_UNSET_SHARED(ary)
Definition: array.c:77
VALUE rb_ary_each(VALUE array)
Definition: array.c:1658
VALUE rb_hash_lookup2(VALUE, VALUE, VALUE)
Definition: hash.c:581
static VALUE rb_ary_frozen_p(VALUE ary)
Definition: array.c:344
#define RAND_UPTO(max)
Definition: array.c:4272
#define RHASH(obj)
Real * a
Definition: bigdecimal.c:1196
VALUE rb_obj_freeze(VALUE)
Definition: object.c:1012
VALUE rb_eTypeError
Definition: error.c:516
VALUE rb_ary_last(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1245
static VALUE rb_ary_reverse_m(VALUE ary)
Definition: array.c:2072
#define ARY_SET_CAPA(ary, n)
Definition: array.c:121
void rb_mem_clear(register VALUE *mem, register long size)
Definition: array.c:37
#define OBJ_FREEZE(x)
static void permute0(long n, long r, long *p, long index, char *used, VALUE values)
Definition: array.c:4567
void rb_define_alloc_func(VALUE, rb_alloc_func_t)
#define OBJ_TAINTED(x)
VALUE rb_ary_push(VALUE ary, VALUE item)
Definition: array.c:822
static VALUE ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
Definition: array.c:748
#define ARY_OWNS_HEAP_P(a)
Definition: array.c:67
#define TYPE(x)
VALUE rb_ary_rassoc(VALUE ary, VALUE value)
Definition: array.c:3498
VALUE rb_yield_values(int n,...)
Definition: vm_eval.c:944
VALUE rb_ary_tmp_new(long capa)
Definition: array.c:465
static VALUE rb_ary_take_while(VALUE ary)
Definition: array.c:5113
#define RHASH_TBL(h)
#define RSTRING_PTR(str)
NIL_P(eventloop_thread)
Definition: tcltklib.c:4067
#define T_ARRAY
VALUE rb_ary_shared_with_p(VALUE ary1, VALUE ary2)
Definition: array.c:358
VALUE rb_str_buf_cat2(VALUE, const char *)
Definition: string.c:1961
static void ary_ensure_room_for_unshift(VALUE ary, int argc)
Definition: array.c:994
#define xfree
VALUE rb_funcall(VALUE, ID, int,...)
Calls a method.
Definition: vm_eval.c:773
static void ary_join_0(VALUE ary, VALUE sep, long max, VALUE result)
Definition: array.c:1803
#define MEMMOVE(p1, p2, type, n)
void rb_raise(VALUE exc, const char *fmt,...)
Definition: error.c:1788
static VALUE rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1055
return Qtrue
Definition: tcltklib.c:9609
static VALUE rb_ary_reject_bang(VALUE ary)
Definition: array.c:2965
static VALUE rb_ary_repeated_combination_size(VALUE ary, VALUE args)
Definition: array.c:4888
VALUE rb_enc_associate(VALUE obj, rb_encoding *enc)
Definition: encoding.c:766
VALUE rb_obj_class(VALUE)
Definition: object.c:194
#define RETURN_ENUMERATOR(obj, argc, argv)
VALUE rb_ary_clear(VALUE ary)
Definition: array.c:3208
#define FL_SET_SHARED_ROOT(ary)
Definition: array.c:143
static int sort_2(const void *ap, const void *bp, void *dummy)
Definition: array.c:2233
int index
Definition: tcltklib.c:4477
VALUE rb_ary_new3(long n,...)
Definition: array.c:432
int opt_inited
Definition: array.c:2190
VALUE rb_eSecurityError
Definition: error.c:525
void rb_include_module(VALUE klass, VALUE module)
Definition: class.c:699
#define ARY_SHARED_ROOT_P(ary)
Definition: array.c:136
#define ARY_SHARED_NUM(ary)
Definition: array.c:137
r
Definition: bigdecimal.c:1210
static VALUE take_i(VALUE val, VALUE *args, int argc, VALUE *argv)
Definition: array.c:3022
static VALUE rb_ary_slice_bang(int argc, VALUE *argv, VALUE ary)
Definition: array.c:2864
static VALUE rb_ary_reject(VALUE ary)
Definition: array.c:2985
VALUE rb_ary_rotate(VALUE ary, long cnt)
Definition: array.c:2093
unsigned int last
Definition: nkf.c:4310
#define ID2SYM(x)
VALUE tbl
Definition: tkutil.c:1279
#define ARY_SHARED_P(ary)
Definition: array.c:52
VALUE VALUE args
Definition: tcltklib.c:2560
static VALUE rb_ary_each_index(VALUE ary)
Definition: array.c:1689
#define RHASH_SIZE(h)
int rb_cmpint(VALUE val, VALUE a, VALUE b)
Definition: bignum.c:97
static VALUE rb_ary_fetch(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1280
#define LONG2NUM(x)
static VALUE rb_ary_reverse_bang(VALUE ary)
Definition: array.c:2056
VALUE rb_equal(VALUE, VALUE)
Definition: object.c:56
VALUE rb_eRangeError
Definition: error.c:520
static VALUE rb_ary_delete_at_m(VALUE ary, VALUE pos)
Definition: array.c:2837
#define head
Definition: st.c:107
static void rb_ary_unshare(VALUE ary)
Definition: array.c:212
static VALUE rb_ary_join_m(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1930
static VALUE rb_ary_first(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1218
st_index_t rb_hash_start(st_index_t)
Definition: random.c:1416
#define MEMZERO(p, type, n)
static VALUE rb_ary_count(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4103
#define ARY_DEFAULT_SIZE
Definition: array.c:33
static VALUE rb_ary_sort_by_bang(VALUE ary)
Definition: array.c:2488
#define ARY_HEAP_PTR(a)
Definition: array.c:59
unsigned long st_data_t
Definition: ripper.y:35
VALUE rb_usascii_str_new(const char *, long)
Definition: string.c:431
#define OPTHASH_GIVEN_P(opts)
Definition: array.c:4268
int st_delete(st_table *, st_data_t *, st_data_t *)
static VALUE rb_class_of(VALUE obj)
Definition: ripper.y:1503
#define RUBY_DTRACE_ARRAY_CREATE_ENABLED()
Definition: probes.h:55
static VALUE rb_ary_aset(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1574
VALUE rb_ary_assoc(VALUE ary, VALUE key)
Definition: array.c:3465
#define FL_USER5
static VALUE rb_ary_repeated_permutation_size(VALUE ary, VALUE args)
Definition: array.c:4803
static VALUE rb_ary_elt(VALUE ary, long offset)
Definition: array.c:1078
VALUE hash
Definition: tkutil.c:267
*q done
Definition: tcltklib.c:2928
void rb_iter_break(void)
Definition: vm.c:1028
static VALUE rb_ary_inspect(VALUE ary)
Definition: array.c:1975
static VALUE rb_ary_compact_bang(VALUE ary)
Definition: array.c:4038
static VALUE rb_ary_select(VALUE ary)
Definition: array.c:2637
BDIGIT m
Definition: bigdecimal.c:5106
#define tmpbuf_discard(s)
Definition: array.c:4529
void rb_ary_free(VALUE ary)
Definition: array.c:471
#define FIXNUM_P(f)
return Qfalse
Definition: tcltklib.c:6778
int rb_block_given_p(void)
Definition: eval.c:672
#define tmpary(n)
Definition: array.c:4530
#define RARRAY_LEN(a)
static VALUE ary_make_shared_copy(VALUE ary)
Definition: array.c:776
VALUE rb_ary_cat(VALUE ary, const VALUE *ptr, long len)
Definition: array.c:833
#define Qnil
Definition: tcltklib.c:1895
static VALUE sort_by_i(VALUE i)
Definition: array.c:2470
#define val
Definition: tcltklib.c:1948
static VALUE rb_ary_or(VALUE ary1, VALUE ary2)
Definition: array.c:3880
VALUE rb_eRuntimeError
Definition: error.c:515
#define RARRAY(obj)
static VALUE char * str
Definition: tcltklib.c:3546
static VALUE ary_alloc(VALUE klass)
Definition: array.c:370
#define tmpary_discard(a)
Definition: array.c:4531
VALUE rb_ary_replace(VALUE copy, VALUE orig)
Definition: array.c:3156
VALUE rb_ary_new(void)
Definition: array.c:424
unsigned long ID
Definition: ripper.y:105
va_end(args)
static VALUE rb_ary_zip(int argc, VALUE *argv, VALUE ary)
Definition: array.c:3071
Definition: ripper.y:881
static VALUE to_ary(VALUE ary)
Definition: array.c:551
VALUE rb_ary_to_s(VALUE ary)
Definition: array.c:1982
static VALUE binomial_coefficient(long comb, long size)
Definition: array.c:4603
VALUE rb_define_class(const char *name, VALUE super)
Defines a top-level class.
Definition: class.c:503
static VALUE VALUE obj
Definition: tcltklib.c:3157
#define RSTRING_LEN(str)
#define FL_SET_SHARED(ary)
Definition: array.c:73
#define FIX2INT(x)
#define INT2FIX(i)
static VALUE rb_ary_product(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4982
static VALUE rb_ary_insert(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1618
int idx
Definition: tcltklib.c:9715
void rb_ary_store(VALUE ary, long idx, VALUE val)
Definition: array.c:719
static VALUE rb_ary_permutation(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4652
#define FIX2LONG(x)
static void ary_resize_smaller(VALUE ary, long len)
Definition: array.c:2715
#define T_STRING
static VALUE rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4285
static void ary_discard(VALUE ary)
Definition: array.c:490
static void rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
Definition: array.c:4872
static VALUE rb_ary_uniq_bang(VALUE ary)
Definition: array.c:3939
#define rb_sourcefile()
Definition: tcltklib.c:97
static VALUE ary_take_first_or_last(int argc, VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
Definition: array.c:788
#define rb_hash_end(h)
static VALUE recursive_join(VALUE obj, VALUE argp, int recur)
Definition: array.c:1785
static VALUE rb_ary_take(VALUE obj, VALUE n)
Definition: array.c:5086
static VALUE rb_ary_select_bang(VALUE ary)
Definition: array.c:2669
#define RUBY_FUNC_EXPORTED
Definition: defines.h:184
static VALUE inspect_ary(VALUE ary, VALUE dummy, int recur)
Definition: array.c:1941
#define DBL2NUM(dbl)
VALUE ary
Definition: array.c:2188
VALUE rb_eIndexError
Definition: error.c:518
static int VALUE key
Definition: tkutil.c:265
static VALUE descending_factorial(long from, long how_many)
Definition: array.c:4593
static VALUE rb_ary_collect(VALUE ary)
Definition: array.c:2521
static VALUE rb_ary_hash(VALUE ary)
Definition: array.c:3636
static ID id_power
Definition: array.c:31
gz level
Definition: zlib.c:2262
VALUE rb_obj_as_string(VALUE)
Definition: string.c:895
VALUE rb_ary_to_ary(VALUE obj)
Definition: array.c:1412
VALUE * argv
Definition: tcltklib.c:1970
VALUE rb_hash_aset(VALUE, VALUE, VALUE)
void rb_define_alias(VALUE klass, const char *name1, const char *name2)
Defines an alias of a method.
Definition: class.c:1543
VALUE rb_yield(VALUE)
Definition: vm_eval.c:933
#define RTEST(v)
const int id
Definition: nkf.c:209
int st_foreach(st_table *, int(*)(ANYARGS), st_data_t)
Definition: st.c:1006
#define TRUE
Definition: nkf.h:175
q result
Definition: tcltklib.c:7069
VALUE rb_mEnumerable
Definition: enum.c:20
volatile VALUE value
Definition: tcltklib.c:9441
#define StringValue(v)
static VALUE rb_ary_rindex(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1382
static void ary_resize_capa(VALUE ary, long capacity)
Definition: array.c:149
void rb_ary_modify(VALUE ary)
Definition: array.c:254
register char * s
Definition: os2.c:56
VALUE rb_ary_delete(VALUE ary, VALUE item)
Definition: array.c:2748
static int sort_1(const void *ap, const void *bp, void *dummy)
Definition: array.c:2219
int rb_scan_args(int argc, const VALUE *argv, const char *fmt,...)
Definition: class.c:1574
static VALUE rb_ary_to_ary_m(VALUE ary)
Definition: array.c:2015
VALUE rb_block_call(VALUE, ID, int, VALUE *, VALUE(*)(ANYARGS), VALUE)
Definition: vm_eval.c:1119
VALUE retval
Definition: tcltklib.c:7829
static int min(int a, int b)
Definition: strftime.c:131
VALUE rb_assoc_new(VALUE car, VALUE cdr)
Definition: array.c:545
VALUE rb_get_values_at(VALUE obj, long olen, int argc, VALUE *argv, VALUE(*func)(VALUE, long))
Definition: array.c:2568
rb_encoding * rb_usascii_encoding(void)
Definition: encoding.c:1181
static VALUE ary_make_hash(VALUE ary)
Definition: array.c:3749
static VALUE rb_ary_delete_if(VALUE ary)
Definition: array.c:3014
#define OBJ_FROZEN(x)
#define RB_GC_GUARD(v)
#define ARY_SET_LEN(ary, n)
Definition: array.c:95
int argc
Definition: tcltklib.c:1969
#define FL_FREEZE
void ruby_qsort(void *, const size_t, const size_t, int(*)(const void *, const void *, void *), void *)
VALUE rb_str_buf_new(long)
Definition: string.c:777
#define ARY_SET_PTR(ary, p)
Definition: array.c:79
#define FL_UNSET_EMBED(ary)
Definition: array.c:72
int opt_methods
Definition: array.c:2189
static VALUE ary_make_substitution(VALUE ary)
Definition: array.c:531
static VALUE rb_ary_values_at(int argc, VALUE *argv, VALUE ary)
Definition: array.c:2612
static VALUE empty_ary_alloc(VALUE klass)
Definition: array.c:380
static VALUE rb_ary_drop(VALUE ary, VALUE n)
Definition: array.c:5141
VALUE rb_check_block_call(VALUE, ID, int, VALUE *, VALUE(*)(ANYARGS), VALUE)
Definition: vm_eval.c:1141
static VALUE rb_ary_collect_bang(VALUE ary)
Definition: array.c:2555
RUBY_FUNC_EXPORTED size_t rb_ary_memsize(VALUE ary)
Definition: array.c:479
static void memfill(register VALUE *mem, register long size, register VALUE val)
Definition: array.c:45
VALUE rb_exec_recursive_outer(VALUE(*)(VALUE, VALUE, int), VALUE, VALUE)
Definition: thread.c:4898
#define RARRAY_EMBED_LEN_MAX
#define INFINITY
Definition: missing.h:138
int rb_sourceline(void)
Definition: vm.c:884
Real * b
Definition: bigdecimal.c:1196
struct timeval t0 t1
Definition: tcltklib.c:2797
static VALUE rb_ary_increment_share(VALUE shared)
Definition: array.c:228
static VALUE ary_add_hash(VALUE hash, VALUE ary)
Definition: array.c:3729
return ptr
Definition: tcltklib.c:784
static void rpermute0(long n, long r, long *p, long index, VALUE values)
Definition: array.c:4786
static VALUE rb_ary_diff(VALUE ary1, VALUE ary2)
Definition: array.c:3805
static VALUE ary_tmp_hash_new(void)
Definition: array.c:3740
static VALUE rb_ary_index(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1333
#define MEMCPY(p1, p2, type, n)
static VALUE rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
Definition: array.c:967
#define SORT_OPTIMIZABLE(data, type)
Definition: array.c:2202
gz end
Definition: zlib.c:2270
static VALUE flatten(VALUE ary, int level, int *modified)
Definition: array.c:4134
#define recur(fmt)
unsigned int top
Definition: nkf.c:4309
static VALUE rb_ary_combination_size(VALUE ary, VALUE args)
Definition: array.c:4692
#define ARY_EMBED_LEN(a)
Definition: array.c:62
arg
Definition: ripper.y:1317
VALUE rb_ary_resize(VALUE ary, long len)
expands or shrinks ary to len elements.
Definition: array.c:1501
#define rb_str_buf_new2
#define NEWOBJ_OF(obj, type, klass, flags)
static VALUE rb_ary_flatten_bang(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4208
#define ARY_EMBED_P(ary)
Definition: array.c:55
#define ARY_SET_HEAP_LEN(ary, n)
Definition: array.c:91
static int yield_indexed_values(const VALUE values, const long r, const long *const p)
Definition: array.c:4539
#define RETURN_SIZED_ENUMERATOR(obj, argc, argv, size_fn)
int size
Definition: encoding.c:52
static VALUE rb_ary_fill(int argc, VALUE *argv, VALUE ary)
Definition: array.c:3255
#define NUM2LONG(x)
#define ARY_SHARED(ary)
Definition: array.c:128
static VALUE recursive_equal(VALUE ary1, VALUE ary2, int recur)
Definition: array.c:3514
static void rb_ary_modify_check(VALUE ary)
Definition: array.c:246
#define Qundef
VALUE rb_obj_is_kind_of(VALUE, VALUE)
Definition: object.c:593
#define mul(x, y)
Definition: date_strftime.c:25
VALUE rb_ary_plus(VALUE x, VALUE y)
Definition: array.c:3341
static VALUE rb_ary_s_try_convert(VALUE dummy, VALUE ary)
Definition: array.c:582
VALUE rb_hash(VALUE)
Definition: hash.c:66
int t
Definition: ripper.c:14654
static void ary_double_capa(VALUE ary, long min)
Definition: array.c:182
static VALUE rb_ary_rotate_m(int argc, VALUE *argv, VALUE ary)
Definition: array.c:2162
static ID id_div
Definition: array.c:31
VALUE rb_check_array_type(VALUE ary)
Definition: array.c:557
static VALUE rb_ary_permutation_size(VALUE ary, VALUE args)
Definition: array.c:4615
static VALUE rb_ary_to_a(VALUE ary)
Definition: array.c:1997
VALUE rb_exec_recursive_paired(VALUE(*)(VALUE, VALUE, int), VALUE, VALUE, VALUE)
Definition: thread.c:4886
#define RARRAY_EMBED_LEN_MASK
BDIGIT shift
Definition: bigdecimal.c:5106
RUBY_EXTERN VALUE rb_cObject
Definition: ripper.y:1426
st_data_t st_index_t
Definition: ripper.y:63
#define ALLOC_N(type, n)
#define LONG2FIX(i)
VALUE rb_ary_includes(VALUE ary, VALUE item)
Definition: array.c:3654
#define RBASIC(obj)
#define ARY_INCREASE_PTR(ary, n)
Definition: array.c:104
static VALUE rb_ary_equal(VALUE ary1, VALUE ary2)
Definition: array.c:3561
VALUE rb_output_fs
Definition: ripper.y:488
static int push_value(st_data_t key, st_data_t val, st_data_t ary)
Definition: array.c:3907
klass
Definition: tcltklib.c:3503
#define ARY_INCREASE_LEN(ary, n)
Definition: array.c:109
static VALUE sym_random
Definition: array.c:4270
static VALUE sort_reentered(VALUE ary)
Definition: array.c:2210
int rb_respond_to(VALUE, ID)
Definition: vm_method.c:1591
static VALUE ary_make_hash_by(VALUE ary)
Definition: array.c:3770
VALUE rb_ary_sort_bang(VALUE ary)
Definition: array.c:2278
static long rotate_count(long cnt, long len)
Definition: array.c:2087
static void rb_ary_set_shared(VALUE ary, VALUE shared)
Definition: array.c:238
#define RARRAY_EMBED_FLAG
static VALUE rb_ary_length(VALUE ary)
Definition: array.c:1742
VALUE rb_ary_dup(VALUE ary)
Definition: array.c:1766
static VALUE rb_ary_repeated_combination(VALUE ary, VALUE num)
Definition: array.c:4926
int st_insert(st_table *, st_data_t, st_data_t)
VALUE rb_cArray
Definition: array.c:29
VALUE rb_ary_concat(VALUE x, VALUE y)
Definition: array.c:3370
VALUE rb_exec_recursive(VALUE(*)(VALUE, VALUE, int), VALUE, VALUE)
Definition: thread.c:4875
VALUE rb_ary_join(VALUE ary, VALUE sep)
Definition: array.c:1874
VALUE rb_ary_new2(long capa)
Definition: array.c:417
static VALUE rb_ary_repeated_permutation(VALUE ary, VALUE num)
Definition: array.c:4839
#define ARY_SET_SHARED_NUM(ary, value)
Definition: array.c:139
#define OBJ_UNTRUST(x)
#define ARY_SET_SHARED(ary, value)
Definition: array.c:129
static VALUE rb_ary_empty_p(VALUE ary)
Definition: array.c:1758
#define rb_safe_level()
Definition: tcltklib.c:94
static VALUE rb_ary_rotate_bang(int argc, VALUE *argv, VALUE ary)
Definition: array.c:2131
static void ary_recycle_hash(VALUE hash)
Definition: array.c:3777
static VALUE ary_make_shared(VALUE ary)
Definition: array.c:498
static VALUE recursive_eql(VALUE ary1, VALUE ary2, int recur)
Definition: array.c:3575
#define assert(condition)
Definition: ossl.h:45
VALUE rb_range_beg_len(VALUE, long *, long *, long, int)
Definition: range.c:990
static VALUE rb_ary_flatten(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4253
#define NUM2INT(x)
VALUE rb_hash_new(void)
Definition: hash.c:234
static VALUE ary_add_hash_by(VALUE hash, VALUE ary)
Definition: array.c:3756
VALUE rb_ary_reverse(VALUE ary)
Definition: array.c:2031
int cnt
Definition: tcltklib.c:6148
#define rb_check_arity(argc, min, max)
#define OBJ_UNTRUSTED(x)
#define tmpbuf(n, size)
Definition: array.c:4528
static VALUE ary_reject_bang(VALUE ary)
Definition: array.c:2929
RUBY_EXTERN VALUE rb_cRandom
Definition: ripper.y:1450
BDIGIT e
Definition: bigdecimal.c:5106
VALUE opts
Definition: tcltklib.c:6145
unsigned long VALUE
Definition: ripper.y:104
static VALUE rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
Definition: array.c:644
static VALUE rb_ary_cycle(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4504
static VALUE recursive_hash(VALUE ary, VALUE dummy, int recur)
Definition: array.c:3605
void rb_warning(const char *fmt,...)
Definition: error.c:234
static void rb_ary_decrement_share(VALUE shared)
Definition: array.c:197
VALUE rb_ary_cmp(VALUE ary1, VALUE ary2)
Definition: array.c:3712
void Init_Array(void)
Definition: array.c:5419
static VALUE rb_ary_eql(VALUE ary1, VALUE ary2)
Definition: array.c:3596
#define ARY_EMBED_PTR(a)
Definition: array.c:61
#define RHASH_EMPTY_P(h)
static VALUE rb_ary_uniq(VALUE ary)
Definition: array.c:3998
#define ARY_HEAP_LEN(a)
Definition: array.c:60
#define OBJ_TAINT(x)
VALUE rb_ary_resurrect(VALUE ary)
Definition: array.c:1775
#define rb_intern(str)
BDIGIT v
Definition: bigdecimal.c:5677
#define mod(x, y)
Definition: date_strftime.c:28
static VALUE ary_new(VALUE klass, long capa)
Definition: array.c:390
#define NULL
Definition: _sdbm.c:103
VALUE rb_check_string_type(VALUE)
Definition: string.c:1509
#define REALLOC_N(var, type, n)
static VALUE rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
Definition: array.c:901
#define ARY_CAPA(ary)
Definition: array.c:119
void rb_define_method(VALUE klass, const char *name, VALUE(*func)(ANYARGS), int argc)
Definition: class.c:1348
#define ALLOCV_N(type, v, n)
void rb_ary_delete_same(VALUE ary, VALUE item)
Definition: array.c:2778
void rb_warn(const char *fmt,...)
Definition: error.c:221
#define bp()
Definition: vm_debug.h:27
static VALUE rb_ary_and(VALUE ary1, VALUE ary2)
Definition: array.c:3840
VALUE rb_eArgError
Definition: error.c:517
RUBY_EXTERN VALUE rb_cNumeric
Definition: ripper.y:1448
VALUE rb_convert_type(VALUE, int, const char *, const char *)
Definition: object.c:2400
static VALUE rb_ary_shuffle(int argc, VALUE *argv, VALUE ary)
Definition: array.c:4329
VALUE rb_check_convert_type(VALUE, int, const char *, const char *)
Definition: object.c:2413
#define STRING_P(s)
Definition: array.c:2199
void st_free_table(st_table *)
Definition: st.c:334
VALUE rb_usascii_str_new_cstr(const char *)
static VALUE rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
Definition: array.c:860
int dummy
Definition: tcltklib.c:4482
VALUE rb_ary_aref(int argc, VALUE *argv, VALUE ary)
Definition: array.c:1150
#define FL_UNSET(x, f)
#define rb_hash_uint(h, i)
static void rb_ary_unshare_safe(VALUE ary)
Definition: array.c:220
VALUE rb_inspect(VALUE)
Definition: object.c:411
#define ALLOCV_END(v)
void rb_ary_set_len(VALUE ary, long len)
Definition: array.c:1478
static VALUE rb_ary_bsearch(VALUE ary)
Definition: array.c:2422
#define numberof(array)
Definition: array.c:27
size_t len
Definition: tcltklib.c:3567