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