Project

General

Profile

Feature #6515 ยป array.c

lellisga (Li Ellis Galardo), 05/30/2012 12:14 PM

 
1
/**********************************************************************
2

    
3
  array.c -
4

    
5
  $Author$
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

    
20
#ifndef ARRAY_DEBUG
21
# define NDEBUG
22
#endif
23
#include <assert.h>
24

    
25
#define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
26

    
27
VALUE rb_cArray;
28

    
29
static ID id_cmp;
30

    
31
#define ARY_DEFAULT_SIZE 16
32
#define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
33

    
34
void
35
rb_mem_clear(register VALUE *mem, register long size)
36
{
37
    while (size--) {
38
	*mem++ = Qnil;
39
    }
40
}
41

    
42
static inline void
43
memfill(register VALUE *mem, register long size, register VALUE val)
44
{
45
    while (size--) {
46
	*mem++ = val;
47
    }
48
}
49

    
50
# define ARY_SHARED_P(ary) \
51
    (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
52
     FL_TEST((ary),ELTS_SHARED)!=0)
53
# define ARY_EMBED_P(ary) \
54
    (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
55
     FL_TEST((ary), RARRAY_EMBED_FLAG)!=0)
56

    
57
#define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
58
#define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
59
#define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
60
#define ARY_EMBED_LEN(a) \
61
    (assert(ARY_EMBED_P(a)), \
62
     (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
63
	 (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
64

    
65
#define ARY_OWNS_HEAP_P(a) (!FL_TEST((a), ELTS_SHARED|RARRAY_EMBED_FLAG))
66
#define FL_SET_EMBED(a) do { \
67
    assert(!ARY_SHARED_P(a)); \
68
    assert(!OBJ_FROZEN(a)); \
69
    FL_SET((a), RARRAY_EMBED_FLAG); \
70
} while (0)
71
#define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
72
#define FL_SET_SHARED(ary) do { \
73
    assert(!ARY_EMBED_P(ary)); \
74
    FL_SET((ary), ELTS_SHARED); \
75
} while (0)
76
#define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)
77

    
78
#define ARY_SET_PTR(ary, p) do { \
79
    assert(!ARY_EMBED_P(ary)); \
80
    assert(!OBJ_FROZEN(ary)); \
81
    RARRAY(ary)->as.heap.ptr = (p); \
82
} while (0)
83
#define ARY_SET_EMBED_LEN(ary, n) do { \
84
    long tmp_n = (n); \
85
    assert(ARY_EMBED_P(ary)); \
86
    assert(!OBJ_FROZEN(ary)); \
87
    RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
88
    RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
89
} while (0)
90
#define ARY_SET_HEAP_LEN(ary, n) do { \
91
    assert(!ARY_EMBED_P(ary)); \
92
    RARRAY(ary)->as.heap.len = (n); \
93
} while (0)
94
#define ARY_SET_LEN(ary, n) do { \
95
    if (ARY_EMBED_P(ary)) { \
96
        ARY_SET_EMBED_LEN((ary), (n)); \
97
    } \
98
    else { \
99
        ARY_SET_HEAP_LEN((ary), (n)); \
100
    } \
101
    assert(RARRAY_LEN(ary) == (n)); \
102
} while (0)
103
#define ARY_INCREASE_PTR(ary, n) do  { \
104
    assert(!ARY_EMBED_P(ary)); \
105
    assert(!OBJ_FROZEN(ary)); \
106
    RARRAY(ary)->as.heap.ptr += (n); \
107
} while (0)
108
#define ARY_INCREASE_LEN(ary, n) do  { \
109
    assert(!OBJ_FROZEN(ary)); \
110
    if (ARY_EMBED_P(ary)) { \
111
        ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
112
    } \
113
    else { \
114
        RARRAY(ary)->as.heap.len += (n); \
115
    } \
116
} while (0)
117

    
118
#define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
119
		       ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : RARRAY(ary)->as.heap.aux.capa)
120
#define ARY_SET_CAPA(ary, n) do { \
121
    assert(!ARY_EMBED_P(ary)); \
122
    assert(!ARY_SHARED_P(ary)); \
123
    assert(!OBJ_FROZEN(ary)); \
124
    RARRAY(ary)->as.heap.aux.capa = (n); \
125
} while (0)
126

    
127
#define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
128
#define ARY_SET_SHARED(ary, value) do { \
129
    assert(!ARY_EMBED_P(ary)); \
130
    assert(ARY_SHARED_P(ary)); \
131
    assert(ARY_SHARED_ROOT_P(value)); \
132
    RARRAY(ary)->as.heap.aux.shared = (value); \
133
} while (0)
134
#define RARRAY_SHARED_ROOT_FLAG FL_USER5
135
#define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))
136
#define ARY_SHARED_NUM(ary) \
137
    (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
138
#define ARY_SET_SHARED_NUM(ary, value) do { \
139
    assert(ARY_SHARED_ROOT_P(ary)); \
140
    RARRAY(ary)->as.heap.aux.capa = (value); \
141
} while (0)
142
#define FL_SET_SHARED_ROOT(ary) do { \
143
    assert(!ARY_EMBED_P(ary)); \
144
    FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
145
} while (0)
146

    
147
static void
148
ary_resize_capa(VALUE ary, long capacity)
149
{
150
    assert(RARRAY_LEN(ary) <= capacity);
151
    assert(!OBJ_FROZEN(ary));
152
    assert(!ARY_SHARED_P(ary));
153
    if (capacity > RARRAY_EMBED_LEN_MAX) {
154
        if (ARY_EMBED_P(ary)) {
155
            long len = ARY_EMBED_LEN(ary);
156
            VALUE *ptr = ALLOC_N(VALUE, (capacity));
157
            MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
158
            FL_UNSET_EMBED(ary);
159
            ARY_SET_PTR(ary, ptr);
160
            ARY_SET_HEAP_LEN(ary, len);
161
        }
162
        else {
163
            REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));
164
        }
165
        ARY_SET_CAPA(ary, (capacity));
166
    }
167
    else {
168
        if (!ARY_EMBED_P(ary)) {
169
            long len = RARRAY_LEN(ary);
170
            VALUE *ptr = RARRAY_PTR(ary);
171
            if (len > capacity) len = capacity;
172
            MEMCPY(RARRAY(ary)->as.ary, ptr, VALUE, len);
173
            FL_SET_EMBED(ary);
174
            ARY_SET_LEN(ary, len);
175
            xfree(ptr);
176
        }
177
    }
178
}
179

    
180
static void
181
ary_double_capa(VALUE ary, long min)
182
{
183
    long new_capa = ARY_CAPA(ary) / 2;
184

    
185
    if (new_capa < ARY_DEFAULT_SIZE) {
186
	new_capa = ARY_DEFAULT_SIZE;
187
    }
188
    if (new_capa >= ARY_MAX_SIZE - min) {
189
	new_capa = (ARY_MAX_SIZE - min) / 2;
190
    }
191
    new_capa += min;
192
    ary_resize_capa(ary, new_capa);
193
}
194

    
195
static void
196
rb_ary_decrement_share(VALUE shared)
197
{
198
    if (shared) {
199
	long num = ARY_SHARED_NUM(shared) - 1;
200
	if (num == 0) {
201
	    rb_ary_free(shared);
202
	    rb_gc_force_recycle(shared);
203
	}
204
	else if (num > 0) {
205
	    ARY_SET_SHARED_NUM(shared, num);
206
	}
207
    }
208
}
209

    
210
static void
211
rb_ary_unshare(VALUE ary)
212
{
213
    VALUE shared = RARRAY(ary)->as.heap.aux.shared;
214
    rb_ary_decrement_share(shared);
215
    FL_UNSET_SHARED(ary);
216
}
217

    
218
static inline void
219
rb_ary_unshare_safe(VALUE ary)
220
{
221
    if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
222
	rb_ary_unshare(ary);
223
    }
224
}
225

    
226
static VALUE
227
rb_ary_increment_share(VALUE shared)
228
{
229
    long num = ARY_SHARED_NUM(shared);
230
    if (num >= 0) {
231
	ARY_SET_SHARED_NUM(shared, num + 1);
232
    }
233
    return shared;
234
}
235

    
236
static void
237
rb_ary_set_shared(VALUE ary, VALUE shared)
238
{
239
    rb_ary_increment_share(shared);
240
    FL_SET_SHARED(ary);
241
    ARY_SET_SHARED(ary, shared);
242
}
243

    
244
static inline void
245
rb_ary_modify_check(VALUE ary)
246
{
247
    rb_check_frozen(ary);
248
    if (!OBJ_UNTRUSTED(ary) && rb_safe_level() >= 4)
249
	rb_raise(rb_eSecurityError, "Insecure: can't modify array");
250
}
251

    
252
void
253
rb_ary_modify(VALUE ary)
254
{
255
    rb_ary_modify_check(ary);
256
    if (ARY_SHARED_P(ary)) {
257
        long len = RARRAY_LEN(ary);
258
        if (len <= RARRAY_EMBED_LEN_MAX) {
259
            VALUE *ptr = ARY_HEAP_PTR(ary);
260
            VALUE shared = ARY_SHARED(ary);
261
            FL_UNSET_SHARED(ary);
262
            FL_SET_EMBED(ary);
263
            MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
264
            rb_ary_decrement_share(shared);
265
            ARY_SET_EMBED_LEN(ary, len);
266
        }
267
        else {
268
            VALUE *ptr = ALLOC_N(VALUE, len);
269
            MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
270
            rb_ary_unshare(ary);
271
            ARY_SET_CAPA(ary, len);
272
            ARY_SET_PTR(ary, ptr);
273
        }
274
    }
275
}
276

    
277
VALUE
278
rb_ary_freeze(VALUE ary)
279
{
280
    return rb_obj_freeze(ary);
281
}
282

    
283
/*
284
 *  call-seq:
285
 *     ary.frozen?  -> true or false
286
 *
287
 *  Return <code>true</code> if this array is frozen (or temporarily frozen
288
 *  while being sorted).
289
 */
290

    
291
static VALUE
292
rb_ary_frozen_p(VALUE ary)
293
{
294
    if (OBJ_FROZEN(ary)) return Qtrue;
295
    return Qfalse;
296
}
297

    
298
static VALUE
299
ary_alloc(VALUE klass)
300
{
301
    NEWOBJ(ary, struct RArray);
302
    OBJSETUP(ary, klass, T_ARRAY);
303
    FL_SET_EMBED((VALUE)ary);
304
    ARY_SET_EMBED_LEN((VALUE)ary, 0);
305

    
306
    return (VALUE)ary;
307
}
308

    
309
static VALUE
310
ary_new(VALUE klass, long capa)
311
{
312
    VALUE ary;
313

    
314
    if (capa < 0) {
315
	rb_raise(rb_eArgError, "negative array size (or size too big)");
316
    }
317
    if (capa > ARY_MAX_SIZE) {
318
	rb_raise(rb_eArgError, "array size too big");
319
    }
320
    ary = ary_alloc(klass);
321
    if (capa > RARRAY_EMBED_LEN_MAX) {
322
        FL_UNSET_EMBED(ary);
323
        ARY_SET_PTR(ary, ALLOC_N(VALUE, capa));
324
        ARY_SET_CAPA(ary, capa);
325
        ARY_SET_HEAP_LEN(ary, 0);
326
    }
327

    
328
    return ary;
329
}
330

    
331
VALUE
332
rb_ary_new2(long capa)
333
{
334
    return ary_new(rb_cArray, capa);
335
}
336

    
337

    
338
VALUE
339
rb_ary_new(void)
340
{
341
    return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
342
}
343

    
344
#include <stdarg.h>
345

    
346
VALUE
347
rb_ary_new3(long n, ...)
348
{
349
    va_list ar;
350
    VALUE ary;
351
    long i;
352

    
353
    ary = rb_ary_new2(n);
354

    
355
    va_start(ar, n);
356
    for (i=0; i<n; i++) {
357
	RARRAY_PTR(ary)[i] = va_arg(ar, VALUE);
358
    }
359
    va_end(ar);
360

    
361
    ARY_SET_LEN(ary, n);
362
    return ary;
363
}
364

    
365
VALUE
366
rb_ary_new4(long n, const VALUE *elts)
367
{
368
    VALUE ary;
369

    
370
    ary = rb_ary_new2(n);
371
    if (n > 0 && elts) {
372
	MEMCPY(RARRAY_PTR(ary), elts, VALUE, n);
373
	ARY_SET_LEN(ary, n);
374
    }
375

    
376
    return ary;
377
}
378

    
379
VALUE
380
rb_ary_tmp_new(long capa)
381
{
382
    return ary_new(0, capa);
383
}
384

    
385
void
386
rb_ary_free(VALUE ary)
387
{
388
    if (ARY_OWNS_HEAP_P(ary)) {
389
	xfree(ARY_HEAP_PTR(ary));
390
    }
391
}
392

    
393
RUBY_FUNC_EXPORTED size_t
394
rb_ary_memsize(VALUE ary)
395
{
396
    if (ARY_OWNS_HEAP_P(ary)) {
397
	return RARRAY(ary)->as.heap.aux.capa * sizeof(VALUE);
398
    }
399
    else {
400
	return 0;
401
    }
402
}
403

    
404
static inline void
405
ary_discard(VALUE ary)
406
{
407
    rb_ary_free(ary);
408
    RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
409
    RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK;
410
}
411

    
412
static VALUE
413
ary_make_shared(VALUE ary)
414
{
415
    assert(!ARY_EMBED_P(ary));
416
    if (ARY_SHARED_P(ary)) {
417
	return ARY_SHARED(ary);
418
    }
419
    else if (ARY_SHARED_ROOT_P(ary)) {
420
	return ary;
421
    }
422
    else if (OBJ_FROZEN(ary)) {
423
	ary_resize_capa(ary, ARY_HEAP_LEN(ary));
424
	FL_SET_SHARED_ROOT(ary);
425
	ARY_SET_SHARED_NUM(ary, 1);
426
	return ary;
427
    }
428
    else {
429
	NEWOBJ(shared, struct RArray);
430
	OBJSETUP(shared, 0, T_ARRAY);
431
        FL_UNSET_EMBED(shared);
432

    
433
        ARY_SET_LEN((VALUE)shared, RARRAY_LEN(ary));
434
        ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
435
	FL_SET_SHARED_ROOT(shared);
436
	ARY_SET_SHARED_NUM((VALUE)shared, 1);
437
	FL_SET_SHARED(ary);
438
	ARY_SET_SHARED(ary, (VALUE)shared);
439
	OBJ_FREEZE(shared);
440
	return (VALUE)shared;
441
    }
442
}
443

    
444

    
445
static VALUE
446
ary_make_substitution(VALUE ary)
447
{
448
    if (RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX) {
449
        VALUE subst = rb_ary_new2(RARRAY_LEN(ary));
450
        MEMCPY(ARY_EMBED_PTR(subst), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
451
        ARY_SET_EMBED_LEN(subst, RARRAY_LEN(ary));
452
        return subst;
453
    }
454
    else {
455
        return rb_ary_increment_share(ary_make_shared(ary));
456
    }
457
}
458

    
459
VALUE
460
rb_assoc_new(VALUE car, VALUE cdr)
461
{
462
    return rb_ary_new3(2, car, cdr);
463
}
464

    
465
static VALUE
466
to_ary(VALUE ary)
467
{
468
    return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
469
}
470

    
471
VALUE
472
rb_check_array_type(VALUE ary)
473
{
474
    return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
475
}
476

    
477
/*
478
 *  call-seq:
479
 *     Array.try_convert(obj) -> array or nil
480
 *
481
 *  Tries to convert +obj+ into an array, using +to_ary+ method.  Returns the
482
 *  converted array or +nil+ if +obj+ cannot be converted for any reason.
483
 *  This method can be used to check if an argument is an array.
484
 *
485
 *     Array.try_convert([1])   #=> [1]
486
 *     Array.try_convert("1")   #=> nil
487
 *
488
 *     if tmp = Array.try_convert(arg)
489
 *       # the argument is an array
490
 *     elsif tmp = String.try_convert(arg)
491
 *       # the argument is a string
492
 *     end
493
 *
494
 */
495

    
496
static VALUE
497
rb_ary_s_try_convert(VALUE dummy, VALUE ary)
498
{
499
    return rb_check_array_type(ary);
500
}
501

    
502
/*
503
 *  call-seq:
504
 *     Array.new(size=0, obj=nil)
505
 *     Array.new(array)
506
 *     Array.new(size) {|index| block }
507
 *
508
 *  Returns a new array.
509
 *
510
 *  In the first form, if no arguments are sent, the new array will be empty.
511
 *  When a +size+ and an optional +obj+ are sent, an array is created with
512
 *  +size+ copies of +obj+.  Take notice that all elements will reference the
513
 *  same object +obj+.
514
 *
515
 *  The second form creates a copy of the array passed as a parameter (the
516
 *  array is generated by calling to_ary on the parameter).
517
 *
518
 *    first_array = ["Matz", "Guido"]
519
 *
520
 *    second_array = Array.new(first_array) #=> ["Matz", "Guido"]
521
 *
522
 *    first_array.equal? second_array       #=> false
523
 *
524
 *  In the last form, an array of the given size is created.  Each element in
525
 *  this array is created by passing the element's index to the given block
526
 *  and storing the return value.
527
 *
528
 *    Array.new(3){ |index| index ** 2 }
529
 *    # => [0, 1, 4]
530
 *
531
 *  == Common gotchas
532
 *
533
 *  When sending the second parameter, the same object will be used as the
534
 *  value for all the array elements:
535
 *
536
 *     a = Array.new(2, Hash.new)
537
 *     # => [{}, {}]
538
 *
539
 *     a[0]['cat'] = 'feline'
540
 *     a # => [{"cat"=>"feline"}, {"cat"=>"feline"}]
541
 *
542
 *     a[1]['cat'] = 'Felix'
543
 *     a # => [{"cat"=>"Felix"}, {"cat"=>"Felix"}]
544
 *
545
 *  Since all the Array elements store the same hash, changes to one of them
546
 *  will affect them all.
547
 *
548
 *  If multiple copies are what you want, you should use the block
549
 *  version which uses the result of that block each time an element
550
 *  of the array needs to be initialized:
551
 *
552
 *     a = Array.new(2) { Hash.new }
553
 *     a[0]['cat'] = 'feline'
554
 *     a # => [{"cat"=>"feline"}, {}]
555
 *
556
 */
557

    
558
static VALUE
559
rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
560
{
561
    long len;
562
    VALUE size, val;
563

    
564
    rb_ary_modify(ary);
565
    if (argc == 0) {
566
	if (ARY_OWNS_HEAP_P(ary) && RARRAY_PTR(ary)) {
567
	    xfree(RARRAY_PTR(ary));
568
	}
569
        rb_ary_unshare_safe(ary);
570
        FL_SET_EMBED(ary);
571
	ARY_SET_EMBED_LEN(ary, 0);
572
	if (rb_block_given_p()) {
573
	    rb_warning("given block not used");
574
	}
575
	return ary;
576
    }
577
    rb_scan_args(argc, argv, "02", &size, &val);
578
    if (argc == 1 && !FIXNUM_P(size)) {
579
	val = rb_check_array_type(size);
580
	if (!NIL_P(val)) {
581
	    rb_ary_replace(ary, val);
582
	    return ary;
583
	}
584
    }
585

    
586
    len = NUM2LONG(size);
587
    if (len < 0) {
588
	rb_raise(rb_eArgError, "negative array size");
589
    }
590
    if (len > ARY_MAX_SIZE) {
591
	rb_raise(rb_eArgError, "array size too big");
592
    }
593
    rb_ary_modify(ary);
594
    ary_resize_capa(ary, len);
595
    if (rb_block_given_p()) {
596
	long i;
597

    
598
	if (argc == 2) {
599
	    rb_warn("block supersedes default value argument");
600
	}
601
	for (i=0; i<len; i++) {
602
	    rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
603
	    ARY_SET_LEN(ary, i + 1);
604
	}
605
    }
606
    else {
607
	memfill(RARRAY_PTR(ary), len, val);
608
	ARY_SET_LEN(ary, len);
609
    }
610
    return ary;
611
}
612

    
613
/*
614
 * Returns a new array populated with the given objects.
615
 *
616
 *   Array.[]( 1, 'a', /^A/ ) # => [1, "a", /^A/]
617
 *   Array[ 1, 'a', /^A/ ]    # => [1, "a", /^A/]
618
 *   [ 1, 'a', /^A/ ]         # => [1, "a", /^A/]
619
 */
620

    
621
static VALUE
622
rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
623
{
624
    VALUE ary = ary_new(klass, argc);
625
    if (argc > 0 && argv) {
626
        MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
627
        ARY_SET_LEN(ary, argc);
628
    }
629

    
630
    return ary;
631
}
632

    
633
void
634
rb_ary_store(VALUE ary, long idx, VALUE val)
635
{
636
    if (idx < 0) {
637
	idx += RARRAY_LEN(ary);
638
	if (idx < 0) {
639
	    rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
640
		     idx - RARRAY_LEN(ary), -RARRAY_LEN(ary));
641
	}
642
    }
643
    else if (idx >= ARY_MAX_SIZE) {
644
	rb_raise(rb_eIndexError, "index %ld too big", idx);
645
    }
646

    
647
    rb_ary_modify(ary);
648
    if (idx >= ARY_CAPA(ary)) {
649
	ary_double_capa(ary, idx);
650
    }
651
    if (idx > RARRAY_LEN(ary)) {
652
	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary),
653
		     idx-RARRAY_LEN(ary) + 1);
654
    }
655

    
656
    if (idx >= RARRAY_LEN(ary)) {
657
	ARY_SET_LEN(ary, idx + 1);
658
    }
659
    RARRAY_PTR(ary)[idx] = val;
660
}
661

    
662
static VALUE
663
ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
664
{
665
    assert(offset >= 0);
666
    assert(len >= 0);
667
    assert(offset+len <= RARRAY_LEN(ary));
668

    
669
    if (len <= RARRAY_EMBED_LEN_MAX) {
670
        VALUE result = ary_alloc(klass);
671
        MEMCPY(ARY_EMBED_PTR(result), RARRAY_PTR(ary) + offset, VALUE, len);
672
        ARY_SET_EMBED_LEN(result, len);
673
        return result;
674
    }
675
    else {
676
        VALUE shared, result = ary_alloc(klass);
677
        FL_UNSET_EMBED(result);
678

    
679
        shared = ary_make_shared(ary);
680
        ARY_SET_PTR(result, RARRAY_PTR(ary));
681
        ARY_SET_LEN(result, RARRAY_LEN(ary));
682
        rb_ary_set_shared(result, shared);
683

    
684
        ARY_INCREASE_PTR(result, offset);
685
        ARY_SET_LEN(result, len);
686
        return result;
687
    }
688
}
689

    
690
static VALUE
691
ary_make_shared_copy(VALUE ary)
692
{
693
    return ary_make_partial(ary, rb_obj_class(ary), 0, RARRAY_LEN(ary));
694
}
695

    
696
enum ary_take_pos_flags
697
{
698
    ARY_TAKE_FIRST = 0,
699
    ARY_TAKE_LAST = 1
700
};
701

    
702
static VALUE
703
ary_take_first_or_last(int argc, VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
704
{
705
    VALUE nv;
706
    long n;
707
    long offset = 0;
708

    
709
    rb_scan_args(argc, argv, "1", &nv);
710
    n = NUM2LONG(nv);
711
    if (n > RARRAY_LEN(ary)) {
712
	n = RARRAY_LEN(ary);
713
    }
714
    else if (n < 0) {
715
	rb_raise(rb_eArgError, "negative array size");
716
    }
717
    if (last) {
718
	offset = RARRAY_LEN(ary) - n;
719
    }
720
    return ary_make_partial(ary, rb_cArray, offset, n);
721
}
722

    
723
static VALUE rb_ary_push_1(VALUE ary, VALUE item);
724

    
725
/*
726
 *  call-seq:
727
 *     ary << obj            -> ary
728
 *
729
 *  Append---Pushes the given object on to the end of this array. This
730
 *  expression returns the array itself, so several appends
731
 *  may be chained together.
732
 *
733
 *     [ 1, 2 ] << "c" << "d" << [ 3, 4 ]
734
 *             #=>  [ 1, 2, "c", "d", [ 3, 4 ] ]
735
 *
736
 */
737

    
738
VALUE
739
rb_ary_push(VALUE ary, VALUE item)
740
{
741
    rb_ary_modify(ary);
742
    return rb_ary_push_1(ary, item);
743
}
744

    
745
static VALUE
746
rb_ary_push_1(VALUE ary, VALUE item)
747
{
748
    long idx = RARRAY_LEN(ary);
749

    
750
    if (idx >= ARY_CAPA(ary)) {
751
	ary_double_capa(ary, idx);
752
    }
753
    RARRAY_PTR(ary)[idx] = item;
754
    ARY_SET_LEN(ary, idx + 1);
755
    return ary;
756
}
757

    
758
VALUE
759
rb_ary_cat(VALUE ary, const VALUE *ptr, long len)
760
{
761
    long oldlen;
762

    
763
    rb_ary_modify(ary);
764
    oldlen = RARRAY_LEN(ary);
765
    ary_resize_capa(ary, oldlen + len);
766
    MEMCPY(RARRAY_PTR(ary) + oldlen, ptr, VALUE, len);
767
    ARY_SET_LEN(ary, oldlen + len);
768
    return ary;
769
}
770

    
771
/*
772
 *  call-seq:
773
 *     ary.push(obj, ... )   -> ary
774
 *
775
 *  Append---Pushes the given object(s) on to the end of this array. This
776
 *  expression returns the array itself, so several appends
777
 *  may be chained together.
778
 *
779
 *     a = [ "a", "b", "c" ]
780
 *     a.push("d", "e", "f")
781
 *             #=> ["a", "b", "c", "d", "e", "f"]
782
 */
783

    
784
static VALUE
785
rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
786
{
787
    return rb_ary_cat(ary, argv, argc);
788
}
789

    
790
VALUE
791
rb_ary_pop(VALUE ary)
792
{
793
    long n;
794
    rb_ary_modify_check(ary);
795
    if (RARRAY_LEN(ary) == 0) return Qnil;
796
    if (ARY_OWNS_HEAP_P(ary) &&
797
	RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
798
	ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
799
    {
800
	ary_resize_capa(ary, RARRAY_LEN(ary) * 2);
801
    }
802
    n = RARRAY_LEN(ary)-1;
803
    ARY_SET_LEN(ary, n);
804
    return RARRAY_PTR(ary)[n];
805
}
806

    
807
/*
808
 *  call-seq:
809
 *     ary.pop    -> obj or nil
810
 *     ary.pop(n) -> new_ary
811
 *
812
 *  Removes the last element from +self+ and returns it, or
813
 *  <code>nil</code> if the array is empty.
814
 *
815
 *  If a number +n+ is given, returns an array of the last n elements
816
 *  (or less) just like <code>array.slice!(-n, n)</code> does.
817
 *
818
 *     a = [ "a", "b", "c", "d" ]
819
 *     a.pop     #=> "d"
820
 *     a.pop(2)  #=> ["b", "c"]
821
 *     a         #=> ["a"]
822
 */
823

    
824
static VALUE
825
rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
826
{
827
    VALUE result;
828

    
829
    if (argc == 0) {
830
	return rb_ary_pop(ary);
831
    }
832

    
833
    rb_ary_modify_check(ary);
834
    result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
835
    ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
836
    return result;
837
}
838

    
839
VALUE
840
rb_ary_shift(VALUE ary)
841
{
842
    VALUE top;
843

    
844
    rb_ary_modify_check(ary);
845
    if (RARRAY_LEN(ary) == 0) return Qnil;
846
    top = RARRAY_PTR(ary)[0];
847
    if (!ARY_SHARED_P(ary)) {
848
	if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
849
	    MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
850
            ARY_INCREASE_LEN(ary, -1);
851
	    return top;
852
	}
853
        assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */
854

    
855
	RARRAY_PTR(ary)[0] = Qnil;
856
	ary_make_shared(ary);
857
    }
858
    else if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
859
	RARRAY_PTR(ary)[0] = Qnil;
860
    }
861
    ARY_INCREASE_PTR(ary, 1);		/* shift ptr */
862
    ARY_INCREASE_LEN(ary, -1);
863

    
864
    return top;
865
}
866

    
867
/*
868
 *  call-seq:
869
 *     ary.shift    -> obj or nil
870
 *     ary.shift(n) -> new_ary
871
 *
872
 *  Returns the first element of +self+ and removes it (shifting all
873
 *  other elements down by one). Returns <code>nil</code> if the array
874
 *  is empty.
875
 *
876
 *  If a number +n+ is given, returns an array of the first n elements
877
 *  (or less) just like <code>array.slice!(0, n)</code> does.
878
 *
879
 *     args = [ "-m", "-q", "filename" ]
880
 *     args.shift     #=> "-m"
881
 *     args           #=> ["-q", "filename"]
882
 *
883
 *     args = [ "-m", "-q", "filename" ]
884
 *     args.shift(2)  #=> ["-m", "-q"]
885
 *     args           #=> ["filename"]
886
 */
887

    
888
static VALUE
889
rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
890
{
891
    VALUE result;
892
    long n;
893

    
894
    if (argc == 0) {
895
	return rb_ary_shift(ary);
896
    }
897

    
898
    rb_ary_modify_check(ary);
899
    result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
900
    n = RARRAY_LEN(result);
901
    if (ARY_SHARED_P(ary)) {
902
	if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
903
	    rb_mem_clear(RARRAY_PTR(ary), n);
904
	}
905
        ARY_INCREASE_PTR(ary, n);
906
    }
907
    else {
908
	MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
909
    }
910
    ARY_INCREASE_LEN(ary, -n);
911

    
912
    return result;
913
}
914

    
915
/*
916
 *  call-seq:
917
 *     ary.unshift(obj, ...)  -> ary
918
 *
919
 *  Prepends objects to the front of +self+,
920
 *  moving other elements upwards.
921
 *
922
 *     a = [ "b", "c", "d" ]
923
 *     a.unshift("a")   #=> ["a", "b", "c", "d"]
924
 *     a.unshift(1, 2)  #=> [ 1, 2, "a", "b", "c", "d"]
925
 */
926

    
927
static VALUE
928
rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
929
{
930
    long len;
931

    
932
    rb_ary_modify(ary);
933
    if (argc == 0) return ary;
934
    if (ARY_CAPA(ary) <= (len = RARRAY_LEN(ary)) + argc) {
935
	ary_double_capa(ary, len + argc);
936
    }
937

    
938
    /* sliding items */
939
    MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
940
    MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
941
    ARY_INCREASE_LEN(ary, argc);
942

    
943
    return ary;
944
}
945

    
946
VALUE
947
rb_ary_unshift(VALUE ary, VALUE item)
948
{
949
    return rb_ary_unshift_m(1,&item,ary);
950
}
951

    
952
/* faster version - use this if you don't need to treat negative offset */
953
static inline VALUE
954
rb_ary_elt(VALUE ary, long offset)
955
{
956
    if (RARRAY_LEN(ary) == 0) return Qnil;
957
    if (offset < 0 || RARRAY_LEN(ary) <= offset) {
958
	return Qnil;
959
    }
960
    return RARRAY_PTR(ary)[offset];
961
}
962

    
963
VALUE
964
rb_ary_entry(VALUE ary, long offset)
965
{
966
    if (offset < 0) {
967
	offset += RARRAY_LEN(ary);
968
    }
969
    return rb_ary_elt(ary, offset);
970
}
971

    
972
VALUE
973
rb_ary_subseq(VALUE ary, long beg, long len)
974
{
975
    VALUE klass;
976

    
977
    if (beg > RARRAY_LEN(ary)) return Qnil;
978
    if (beg < 0 || len < 0) return Qnil;
979

    
980
    if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
981
	len = RARRAY_LEN(ary) - beg;
982
    }
983
    klass = rb_obj_class(ary);
984
    if (len == 0) return ary_new(klass, 0);
985

    
986
    return ary_make_partial(ary, klass, beg, len);
987
}
988

    
989
/*
990
 *  call-seq:
991
 *     ary[index]                -> obj     or nil
992
 *     ary[start, length]        -> new_ary or nil
993
 *     ary[range]                -> new_ary or nil
994
 *     ary.slice(index)          -> obj     or nil
995
 *     ary.slice(start, length)  -> new_ary or nil
996
 *     ary.slice(range)          -> new_ary or nil
997
 *
998
 *  Element Reference---Returns the element at +index+,
999
 *  or returns a subarray starting at +start+ and
1000
 *  continuing for +length+ elements, or returns a subarray
1001
 *  specified by +range+.
1002
 *  Negative indices count backward from the end of the
1003
 *  array (-1 is the last element). Returns +nil+ if the index
1004
 *  (or starting index) are out of range.
1005
 *
1006
 *     a = [ "a", "b", "c", "d", "e" ]
1007
 *     a[2] +  a[0] + a[1]    #=> "cab"
1008
 *     a[6]                   #=> nil
1009
 *     a[1, 2]                #=> [ "b", "c" ]
1010
 *     a[1..3]                #=> [ "b", "c", "d" ]
1011
 *     a[4..7]                #=> [ "e" ]
1012
 *     a[6..10]               #=> nil
1013
 *     a[-3, 3]               #=> [ "c", "d", "e" ]
1014
 *     # special cases
1015
 *     a[5]                   #=> nil
1016
 *     a[5, 1]                #=> []
1017
 *     a[5..10]               #=> []
1018
 *
1019
 */
1020

    
1021
VALUE
1022
rb_ary_aref(int argc, VALUE *argv, VALUE ary)
1023
{
1024
    VALUE arg;
1025
    long beg, len;
1026

    
1027
    if (argc == 2) {
1028
	beg = NUM2LONG(argv[0]);
1029
	len = NUM2LONG(argv[1]);
1030
	if (beg < 0) {
1031
	    beg += RARRAY_LEN(ary);
1032
	}
1033
	return rb_ary_subseq(ary, beg, len);
1034
    }
1035
    if (argc != 1) {
1036
	rb_scan_args(argc, argv, "11", 0, 0);
1037
    }
1038
    arg = argv[0];
1039
    /* special case - speeding up */
1040
    if (FIXNUM_P(arg)) {
1041
	return rb_ary_entry(ary, FIX2LONG(arg));
1042
    }
1043
    /* check if idx is Range */
1044
    switch (rb_range_beg_len(arg, &beg, &len, RARRAY_LEN(ary), 0)) {
1045
      case Qfalse:
1046
	break;
1047
      case Qnil:
1048
	return Qnil;
1049
      default:
1050
	return rb_ary_subseq(ary, beg, len);
1051
    }
1052
    return rb_ary_entry(ary, NUM2LONG(arg));
1053
}
1054

    
1055
/*
1056
 *  call-seq:
1057
 *     ary.at(index)   ->   obj  or nil
1058
 *
1059
 *  Returns the element at +index+. A
1060
 *  negative index counts from the end of +self+.  Returns +nil+
1061
 *  if the index is out of range. See also <code>Array#[]</code>.
1062
 *
1063
 *     a = [ "a", "b", "c", "d", "e" ]
1064
 *     a.at(0)     #=> "a"
1065
 *     a.at(-1)    #=> "e"
1066
 */
1067

    
1068
static VALUE
1069
rb_ary_at(VALUE ary, VALUE pos)
1070
{
1071
    return rb_ary_entry(ary, NUM2LONG(pos));
1072
}
1073

    
1074
/*
1075
 *  call-seq:
1076
 *     ary.first     ->   obj or nil
1077
 *     ary.first(n)  ->   new_ary
1078
 *
1079
 *  Returns the first element, or the first +n+ elements, of the array.
1080
 *  If the array is empty, the first form returns <code>nil</code>, and the
1081
 *  second form returns an empty array.
1082
 *
1083
 *     a = [ "q", "r", "s", "t" ]
1084
 *     a.first     #=> "q"
1085
 *     a.first(2)  #=> ["q", "r"]
1086
 */
1087

    
1088
static VALUE
1089
rb_ary_first(int argc, VALUE *argv, VALUE ary)
1090
{
1091
    if (argc == 0) {
1092
	if (RARRAY_LEN(ary) == 0) return Qnil;
1093
	return RARRAY_PTR(ary)[0];
1094
    }
1095
    else {
1096
	return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
1097
    }
1098
}
1099

    
1100
/*
1101
 *  call-seq:
1102
 *     ary.last     ->  obj or nil
1103
 *     ary.last(n)  ->  new_ary
1104
 *
1105
 *  Returns the last element(s) of +self+. If the array is empty,
1106
 *  the first form returns <code>nil</code>.
1107
 *
1108
 *     a = [ "w", "x", "y", "z" ]
1109
 *     a.last     #=> "z"
1110
 *     a.last(2)  #=> ["y", "z"]
1111
 */
1112

    
1113
VALUE
1114
rb_ary_last(int argc, VALUE *argv, VALUE ary)
1115
{
1116
    if (argc == 0) {
1117
	if (RARRAY_LEN(ary) == 0) return Qnil;
1118
	return RARRAY_PTR(ary)[RARRAY_LEN(ary)-1];
1119
    }
1120
    else {
1121
	return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
1122
    }
1123
}
1124

    
1125
/*
1126
 *  call-seq:
1127
 *     ary.fetch(index)                    -> obj
1128
 *     ary.fetch(index, default )          -> obj
1129
 *     ary.fetch(index) {|index| block }   -> obj
1130
 *
1131
 *  Tries to return the element at position +index+. If the index lies outside
1132
 *  the array, the first form throws an IndexError exception, the second form
1133
 *  returns +default+, and the third form returns the value of invoking the
1134
 *  block, passing in the index. Negative values of +index+ count from the end
1135
 *  of the array.
1136
 *
1137
 *  Tries to return the element at position +index+, but throws an IndexError
1138
 *  exception if the referenced index lies outside of the array bounds.  This
1139
 *  error can be prevented by supplying a second argument, which will act as a
1140
 *  +default+ value.  Alternatively, if the second argument is a block it will
1141
 *  only be executed when an invalid index is referenced.  Negative values of
1142
 *  +index+ count from the end of the array.
1143
 *
1144
 *     a = [ 11, 22, 33, 44 ]
1145
 *     a.fetch(1)               #=> 22
1146
 *     a.fetch(-1)              #=> 44
1147
 *     a.fetch(4, 'cat')        #=> "cat"
1148
 *     a.fetch(100) { |i| puts "#{i} is out of bounds" }
1149
 *                              #=> "100 is out of bounds"
1150
 */
1151

    
1152
static VALUE
1153
rb_ary_fetch(int argc, VALUE *argv, VALUE ary)
1154
{
1155
    VALUE pos, ifnone;
1156
    long block_given;
1157
    long idx;
1158

    
1159
    rb_scan_args(argc, argv, "11", &pos, &ifnone);
1160
    block_given = rb_block_given_p();
1161
    if (block_given && argc == 2) {
1162
	rb_warn("block supersedes default value argument");
1163
    }
1164
    idx = NUM2LONG(pos);
1165

    
1166
    if (idx < 0) {
1167
	idx +=  RARRAY_LEN(ary);
1168
    }
1169
    if (idx < 0 || RARRAY_LEN(ary) <= idx) {
1170
	if (block_given) return rb_yield(pos);
1171
	if (argc == 1) {
1172
	    rb_raise(rb_eIndexError, "index %ld outside of array bounds: %ld...%ld",
1173
			idx - (idx < 0 ? RARRAY_LEN(ary) : 0), -RARRAY_LEN(ary), RARRAY_LEN(ary));
1174
	}
1175
	return ifnone;
1176
    }
1177
    return RARRAY_PTR(ary)[idx];
1178
}
1179

    
1180
/*
1181
 *  call-seq:
1182
 *     ary.index(obj)           ->  int or nil
1183
 *     ary.index {|item| block} ->  int or nil
1184
 *     ary.index                ->  an_enumerator
1185
 *
1186
 *  Returns the index of the first object in +self+ such that the object is
1187
 *  <code>==</code> to +obj+. If a block is given instead of an
1188
 *  argument, returns index of first object for which <em>block</em> is true.
1189
 *  Returns <code>nil</code> if no match is found.
1190
 *  See also <code>Array#rindex</code>.
1191
 *
1192
 *  If neither block nor argument is given, an enumerator is returned instead.
1193
 *
1194
 *     a = [ "a", "b", "c" ]
1195
 *     a.index("b")        #=> 1
1196
 *     a.index("z")        #=> nil
1197
 *     a.index{|x|x=="b"}  #=> 1
1198
 *
1199
 *  This is an alias of <code>#find_index</code>.
1200
 */
1201

    
1202
static VALUE
1203
rb_ary_index(int argc, VALUE *argv, VALUE ary)
1204
{
1205
    VALUE val;
1206
    long i;
1207

    
1208
    if (argc == 0) {
1209
	RETURN_ENUMERATOR(ary, 0, 0);
1210
	for (i=0; i<RARRAY_LEN(ary); i++) {
1211
	    if (RTEST(rb_yield(RARRAY_PTR(ary)[i]))) {
1212
		return LONG2NUM(i);
1213
	    }
1214
	}
1215
	return Qnil;
1216
    }
1217
    rb_scan_args(argc, argv, "1", &val);
1218
    if (rb_block_given_p())
1219
	rb_warn("given block not used");
1220
    for (i=0; i<RARRAY_LEN(ary); i++) {
1221
	if (rb_equal(RARRAY_PTR(ary)[i], val))
1222
	    return LONG2NUM(i);
1223
    }
1224
    return Qnil;
1225
}
1226

    
1227
/*
1228
 *  call-seq:
1229
 *     ary.rindex(obj)           ->  int or nil
1230
 *     ary.rindex {|item| block} ->  int or nil
1231
 *     ary.rindex                ->  an_enumerator
1232
 *
1233
 *  Returns the index of the last object in +self+
1234
 *  <code>==</code> to +obj+. If a block is given instead of an
1235
 *  argument, returns index of first object for which <em>block</em> is
1236
 *  true, starting from the last object.
1237
 *  Returns <code>nil</code> if no match is found.
1238
 *  See also Array#index.
1239
 *
1240
 *  If neither block nor argument is given, an enumerator is returned instead.
1241
 *
1242
 *     a = [ "a", "b", "b", "b", "c" ]
1243
 *     a.rindex("b")             #=> 3
1244
 *     a.rindex("z")             #=> nil
1245
 *     a.rindex { |x| x == "b" } #=> 3
1246
 */
1247

    
1248
static VALUE
1249
rb_ary_rindex(int argc, VALUE *argv, VALUE ary)
1250
{
1251
    VALUE val;
1252
    long i = RARRAY_LEN(ary);
1253

    
1254
    if (argc == 0) {
1255
	RETURN_ENUMERATOR(ary, 0, 0);
1256
	while (i--) {
1257
	    if (RTEST(rb_yield(RARRAY_PTR(ary)[i])))
1258
		return LONG2NUM(i);
1259
	    if (i > RARRAY_LEN(ary)) {
1260
		i = RARRAY_LEN(ary);
1261
	    }
1262
	}
1263
	return Qnil;
1264
    }
1265
    rb_scan_args(argc, argv, "1", &val);
1266
    if (rb_block_given_p())
1267
	rb_warn("given block not used");
1268
    while (i--) {
1269
	if (rb_equal(RARRAY_PTR(ary)[i], val))
1270
	    return LONG2NUM(i);
1271
	if (i > RARRAY_LEN(ary)) {
1272
	    i = RARRAY_LEN(ary);
1273
	}
1274
    }
1275
    return Qnil;
1276
}
1277

    
1278
VALUE
1279
rb_ary_to_ary(VALUE obj)
1280
{
1281
    VALUE tmp = rb_check_array_type(obj);
1282

    
1283
    if (!NIL_P(tmp)) return tmp;
1284
    return rb_ary_new3(1, obj);
1285
}
1286

    
1287
static void
1288
rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
1289
{
1290
    long rlen;
1291

    
1292
    if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
1293
    if (beg < 0) {
1294
	beg += RARRAY_LEN(ary);
1295
	if (beg < 0) {
1296
	    rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
1297
		     beg - RARRAY_LEN(ary), -RARRAY_LEN(ary));
1298
	}
1299
    }
1300
    if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
1301
	len = RARRAY_LEN(ary) - beg;
1302
    }
1303

    
1304
    if (rpl == Qundef) {
1305
	rlen = 0;
1306
    }
1307
    else {
1308
	rpl = rb_ary_to_ary(rpl);
1309
	rlen = RARRAY_LEN(rpl);
1310
    }
1311
    rb_ary_modify(ary);
1312
    if (beg >= RARRAY_LEN(ary)) {
1313
	if (beg > ARY_MAX_SIZE - rlen) {
1314
	    rb_raise(rb_eIndexError, "index %ld too big", beg);
1315
	}
1316
	len = beg + rlen;
1317
	if (len >= ARY_CAPA(ary)) {
1318
	    ary_double_capa(ary, len);
1319
	}
1320
	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), beg - RARRAY_LEN(ary));
1321
	if (rlen > 0) {
1322
	    MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
1323
	}
1324
	ARY_SET_LEN(ary, len);
1325
    }
1326
    else {
1327
	long alen;
1328

    
1329
	alen = RARRAY_LEN(ary) + rlen - len;
1330
	if (alen >= ARY_CAPA(ary)) {
1331
	    ary_double_capa(ary, alen);
1332
	}
1333

    
1334
	if (len != rlen) {
1335
	    MEMMOVE(RARRAY_PTR(ary) + beg + rlen, RARRAY_PTR(ary) + beg + len,
1336
		    VALUE, RARRAY_LEN(ary) - (beg + len));
1337
	    ARY_SET_LEN(ary, alen);
1338
	}
1339
	if (rlen > 0) {
1340
	    MEMMOVE(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
1341
	}
1342
    }
1343
}
1344

    
1345
void
1346
rb_ary_set_len(VALUE ary, long len)
1347
{
1348
    long capa;
1349

    
1350
    rb_ary_modify_check(ary);
1351
    if (ARY_SHARED_P(ary)) {
1352
	rb_raise(rb_eRuntimeError, "can't set length of shared ");
1353
    }
1354
    if (len > (capa = (long)ARY_CAPA(ary))) {
1355
	rb_bug("probable buffer overflow: %ld for %ld", len, capa);
1356
    }
1357
    ARY_SET_LEN(ary, len);
1358
}
1359

    
1360
/*!
1361
 * expands or shrinks \a ary to \a len elements.
1362
 * expanded region will be filled with Qnil.
1363
 * \param ary  an array
1364
 * \param len  new size
1365
 * \return     \a ary
1366
 * \post       the size of \a ary is \a len.
1367
 */
1368
VALUE
1369
rb_ary_resize(VALUE ary, long len)
1370
{
1371
    long olen;
1372

    
1373
    rb_ary_modify(ary);
1374
    olen = RARRAY_LEN(ary);
1375
    if (len == olen) return ary;
1376
    if (len > ARY_MAX_SIZE) {
1377
	rb_raise(rb_eIndexError, "index %ld too big", len);
1378
    }
1379
    if (len > olen) {
1380
	if (len >= ARY_CAPA(ary)) {
1381
	    ary_double_capa(ary, len);
1382
	}
1383
	rb_mem_clear(RARRAY_PTR(ary) + olen, len - olen);
1384
        ARY_SET_LEN(ary, len);
1385
    }
1386
    else if (ARY_EMBED_P(ary)) {
1387
        ARY_SET_EMBED_LEN(ary, len);
1388
    }
1389
    else if (len <= RARRAY_EMBED_LEN_MAX) {
1390
	VALUE tmp[RARRAY_EMBED_LEN_MAX];
1391
	MEMCPY(tmp, ARY_HEAP_PTR(ary), VALUE, len);
1392
	ary_discard(ary);
1393
	MEMCPY(ARY_EMBED_PTR(ary), tmp, VALUE, len);
1394
        ARY_SET_EMBED_LEN(ary, len);
1395
    }
1396
    else {
1397
	if (olen > len + ARY_DEFAULT_SIZE) {
1398
	    REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, len);
1399
	    ARY_SET_CAPA(ary, len);
1400
	}
1401
	ARY_SET_HEAP_LEN(ary, len);
1402
    }
1403
    return ary;
1404
}
1405

    
1406
/*
1407
 *  call-seq:
1408
 *     ary[index]         = obj                      ->  obj
1409
 *     ary[start, length] = obj or other_ary or nil  ->  obj or other_ary or nil
1410
 *     ary[range]         = obj or other_ary or nil  ->  obj or other_ary or nil
1411
 *
1412
 *  Element Assignment---Sets the element at +index+,
1413
 *  or replaces a subarray starting at +start+ and
1414
 *  continuing for +length+ elements, or replaces a subarray
1415
 *  specified by +range+.  If indices are greater than
1416
 *  the current capacity of the array, the array grows
1417
 *  automatically. A negative indices will count backward
1418
 *  from the end of the array. Inserts elements if +length+ is
1419
 *  zero. An IndexError is raised if a negative index points
1420
 *  past the beginning of the array. See also
1421
 *  Array#push, and Array#unshift.
1422
 *
1423
 *     a = Array.new
1424
 *     a[4] = "4";                 #=> [nil, nil, nil, nil, "4"]
1425
 *     a[0, 3] = [ 'a', 'b', 'c' ] #=> ["a", "b", "c", nil, "4"]
1426
 *     a[1..2] = [ 1, 2 ]          #=> ["a", 1, 2, nil, "4"]
1427
 *     a[0, 2] = "?"               #=> ["?", 2, nil, "4"]
1428
 *     a[0..2] = "A"               #=> ["A", "4"]
1429
 *     a[-1]   = "Z"               #=> ["A", "Z"]
1430
 *     a[1..-1] = nil              #=> ["A", nil]
1431
 *     a[1..-1] = []               #=> ["A"]
1432
 */
1433

    
1434
static VALUE
1435
rb_ary_aset(int argc, VALUE *argv, VALUE ary)
1436
{
1437
    long offset, beg, len;
1438

    
1439
    if (argc == 3) {
1440
	rb_ary_modify_check(ary);
1441
	beg = NUM2LONG(argv[0]);
1442
	len = NUM2LONG(argv[1]);
1443
	rb_ary_splice(ary, beg, len, argv[2]);
1444
	return argv[2];
1445
    }
1446
    rb_check_arity(argc, 2, 2);
1447
    rb_ary_modify_check(ary);
1448
    if (FIXNUM_P(argv[0])) {
1449
	offset = FIX2LONG(argv[0]);
1450
	goto fixnum;
1451
    }
1452
    if (rb_range_beg_len(argv[0], &beg, &len, RARRAY_LEN(ary), 1)) {
1453
	/* check if idx is Range */
1454
	rb_ary_splice(ary, beg, len, argv[1]);
1455
	return argv[1];
1456
    }
1457

    
1458
    offset = NUM2LONG(argv[0]);
1459
fixnum:
1460
    rb_ary_store(ary, offset, argv[1]);
1461
    return argv[1];
1462
}
1463

    
1464
/*
1465
 *  call-seq:
1466
 *     ary.insert(index, obj...)  -> ary
1467
 *
1468
 *  Inserts the given values before the element with the given index
1469
 *  (which may be negative).
1470
 *
1471
 *     a = %w{ a b c d }
1472
 *     a.insert(2, 99)         #=> ["a", "b", 99, "c", "d"]
1473
 *     a.insert(-2, 1, 2, 3)   #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
1474
 */
1475

    
1476
static VALUE
1477
rb_ary_insert(int argc, VALUE *argv, VALUE ary)
1478
{
1479
    long pos;
1480

    
1481
    rb_check_arity(argc, 1, UNLIMITED_ARGUMENTS);
1482
    rb_ary_modify_check(ary);
1483
    if (argc == 1) return ary;
1484
    pos = NUM2LONG(argv[0]);
1485
    if (pos == -1) {
1486
	pos = RARRAY_LEN(ary);
1487
    }
1488
    if (pos < 0) {
1489
	pos++;
1490
    }
1491
    rb_ary_splice(ary, pos, 0, rb_ary_new4(argc - 1, argv + 1));
1492
    return ary;
1493
}
1494

    
1495
/*
1496
 *  call-seq:
1497
 *     ary.each {|item| block }   -> ary
1498
 *     ary.each                   -> an_enumerator
1499
 *
1500
 *  Calls +block+ once for each element in +self+, passing that
1501
 *  element as a parameter.
1502
 *
1503
 *  If no block is given, an enumerator is returned instead.
1504
 *
1505
 *     a = [ "a", "b", "c" ]
1506
 *     a.each {|x| print x, " -- " }
1507
 *
1508
 *  produces:
1509
 *
1510
 *     a -- b -- c --
1511
 */
1512

    
1513
VALUE
1514
rb_ary_each(VALUE array)
1515
{
1516
    long i;
1517
    volatile VALUE ary = array;
1518

    
1519
    RETURN_ENUMERATOR(ary, 0, 0);
1520
    for (i=0; i<RARRAY_LEN(ary); i++) {
1521
	rb_yield(RARRAY_PTR(ary)[i]);
1522
    }
1523
    return ary;
1524
}
1525

    
1526
/*
1527
 *  call-seq:
1528
 *     ary.each_index {|index| block }  -> ary
1529
 *     ary.each_index                   -> an_enumerator
1530
 *
1531
 *  Same as Array#each, but passes the index of the element instead of the
1532
 *  element itself.
1533
 *
1534
 *  If no block is given, an enumerator is returned instead.
1535
 *
1536
 *
1537
 *     a = [ "a", "b", "c" ]
1538
 *     a.each_index {|x| print x, " -- " }
1539
 *
1540
 *  produces:
1541
 *
1542
 *     0 -- 1 -- 2 --
1543
 */
1544

    
1545
static VALUE
1546
rb_ary_each_index(VALUE ary)
1547
{
1548
    long i;
1549
    RETURN_ENUMERATOR(ary, 0, 0);
1550

    
1551
    for (i=0; i<RARRAY_LEN(ary); i++) {
1552
	rb_yield(LONG2NUM(i));
1553
    }
1554
    return ary;
1555
}
1556

    
1557
/*
1558
 *  call-seq:
1559
 *     ary.reverse_each {|item| block }   -> ary
1560
 *     ary.reverse_each                   -> an_enumerator
1561
 *
1562
 *  Same as Array#each, but traverses +self+ in reverse order.
1563
 *
1564
 *     a = [ "a", "b", "c" ]
1565
 *     a.reverse_each {|x| print x, " " }
1566
 *
1567
 *  produces:
1568
 *
1569
 *     c b a
1570
 */
1571

    
1572
static VALUE
1573
rb_ary_reverse_each(VALUE ary)
1574
{
1575
    long len;
1576

    
1577
    RETURN_ENUMERATOR(ary, 0, 0);
1578
    len = RARRAY_LEN(ary);
1579
    while (len--) {
1580
	rb_yield(RARRAY_PTR(ary)[len]);
1581
	if (RARRAY_LEN(ary) < len) {
1582
	    len = RARRAY_LEN(ary);
1583
	}
1584
    }
1585
    return ary;
1586
}
1587

    
1588
/*
1589
 *  call-seq:
1590
 *     ary.length -> int
1591
 *
1592
 *  Returns the number of elements in +self+. May be zero.
1593
 *
1594
 *     [ 1, 2, 3, 4, 5 ].length   #=> 5
1595
 */
1596

    
1597
static VALUE
1598
rb_ary_length(VALUE ary)
1599
{
1600
    long len = RARRAY_LEN(ary);
1601
    return LONG2NUM(len);
1602
}
1603

    
1604
/*
1605
 *  call-seq:
1606
 *     ary.empty?   -> true or false
1607
 *
1608
 *  Returns <code>true</code> if +self+ contains no elements.
1609
 *
1610
 *     [].empty?   #=> true
1611
 */
1612

    
1613
static VALUE
1614
rb_ary_empty_p(VALUE ary)
1615
{
1616
    if (RARRAY_LEN(ary) == 0)
1617
	return Qtrue;
1618
    return Qfalse;
1619
}
1620

    
1621
VALUE
1622
rb_ary_dup(VALUE ary)
1623
{
1624
    VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
1625
    MEMCPY(RARRAY_PTR(dup), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
1626
    ARY_SET_LEN(dup, RARRAY_LEN(ary));
1627
    return dup;
1628
}
1629

    
1630
VALUE
1631
rb_ary_resurrect(VALUE ary)
1632
{
1633
    return rb_ary_new4(RARRAY_LEN(ary), RARRAY_PTR(ary));
1634
}
1635

    
1636
extern VALUE rb_output_fs;
1637

    
1638
static void ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first);
1639

    
1640
static VALUE
1641
recursive_join(VALUE obj, VALUE argp, int recur)
1642
{
1643
    VALUE *arg = (VALUE *)argp;
1644
    VALUE ary = arg[0];
1645
    VALUE sep = arg[1];
1646
    VALUE result = arg[2];
1647
    int *first = (int *)arg[3];
1648

    
1649
    if (recur) {
1650
	rb_raise(rb_eArgError, "recursive array join");
1651
    }
1652
    else {
1653
	ary_join_1(obj, ary, sep, 0, result, first);
1654
    }
1655
    return Qnil;
1656
}
1657

    
1658
static void
1659
ary_join_0(VALUE ary, VALUE sep, long max, VALUE result)
1660
{
1661
    long i;
1662
    VALUE val;
1663

    
1664
    if (max > 0) rb_enc_copy(result, RARRAY_PTR(ary)[0]);
1665
    for (i=0; i<max; i++) {
1666
	val = RARRAY_PTR(ary)[i];
1667
	if (i > 0 && !NIL_P(sep))
1668
	    rb_str_buf_append(result, sep);
1669
	rb_str_buf_append(result, val);
1670
	if (OBJ_TAINTED(val)) OBJ_TAINT(result);
1671
	if (OBJ_UNTRUSTED(val)) OBJ_TAINT(result);
1672
    }
1673
}
1674

    
1675
static void
1676
ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first)
1677
{
1678
    VALUE val, tmp;
1679

    
1680
    for (; i<RARRAY_LEN(ary); i++) {
1681
	if (i > 0 && !NIL_P(sep))
1682
	    rb_str_buf_append(result, sep);
1683

    
1684
	val = RARRAY_PTR(ary)[i];
1685
	switch (TYPE(val)) {
1686
	  case T_STRING:
1687
	  str_join:
1688
	    rb_str_buf_append(result, val);
1689
	    *first = FALSE;
1690
	    break;
1691
	  case T_ARRAY:
1692
	    obj = val;
1693
	  ary_join:
1694
	    if (val == ary) {
1695
		rb_raise(rb_eArgError, "recursive array join");
1696
	    }
1697
	    else {
1698
		VALUE args[4];
1699

    
1700
		args[0] = val;
1701
		args[1] = sep;
1702
		args[2] = result;
1703
		args[3] = (VALUE)first;
1704
		rb_exec_recursive(recursive_join, obj, (VALUE)args);
1705
	    }
1706
	    break;
1707
	  default:
1708
	    tmp = rb_check_string_type(val);
1709
	    if (!NIL_P(tmp)) {
1710
		val = tmp;
1711
		goto str_join;
1712
	    }
1713
	    tmp = rb_check_convert_type(val, T_ARRAY, "Array", "to_ary");
1714
	    if (!NIL_P(tmp)) {
1715
		obj = val;
1716
		val = tmp;
1717
		goto ary_join;
1718
	    }
1719
	    val = rb_obj_as_string(val);
1720
	    if (*first) {
1721
		rb_enc_copy(result, val);
1722
		*first = FALSE;
1723
	    }
1724
	    goto str_join;
1725
	}
1726
    }
1727
}
1728

    
1729
VALUE
1730
rb_ary_join(VALUE ary, VALUE sep)
1731
{
1732
    long len = 1, i;
1733
    int taint = FALSE;
1734
    int untrust = FALSE;
1735
    VALUE val, tmp, result;
1736

    
1737
    if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new(0, 0);
1738
    if (OBJ_TAINTED(ary) || OBJ_TAINTED(sep)) taint = TRUE;
1739
    if (OBJ_UNTRUSTED(ary) || OBJ_UNTRUSTED(sep)) untrust = TRUE;
1740

    
1741
    if (!NIL_P(sep)) {
1742
	StringValue(sep);
1743
	len += RSTRING_LEN(sep) * (RARRAY_LEN(ary) - 1);
1744
    }
1745
    for (i=0; i<RARRAY_LEN(ary); i++) {
1746
	val = RARRAY_PTR(ary)[i];
1747
	tmp = rb_check_string_type(val);
1748

    
1749
	if (NIL_P(tmp) || tmp != val) {
1750
	    int first;
1751
	    result = rb_str_buf_new(len + (RARRAY_LEN(ary)-i)*10);
1752
	    rb_enc_associate(result, rb_usascii_encoding());
1753
	    if (taint) OBJ_TAINT(result);
1754
	    if (untrust) OBJ_UNTRUST(result);
1755
	    ary_join_0(ary, sep, i, result);
1756
	    first = i == 0;
1757
	    ary_join_1(ary, ary, sep, i, result, &first);
1758
	    return result;
1759
	}
1760

    
1761
	len += RSTRING_LEN(tmp);
1762
    }
1763

    
1764
    result = rb_str_buf_new(len);
1765
    if (taint) OBJ_TAINT(result);
1766
    if (untrust) OBJ_UNTRUST(result);
1767
    ary_join_0(ary, sep, RARRAY_LEN(ary), result);
1768

    
1769
    return result;
1770
}
1771

    
1772
/*
1773
 *  call-seq:
1774
 *     ary.join(sep=$,)    -> str
1775
 *
1776
 *  Returns a string created by converting each element of the array to
1777
 *  a string, separated by +sep+.
1778
 *
1779
 *     [ "a", "b", "c" ].join        #=> "abc"
1780
 *     [ "a", "b", "c" ].join("-")   #=> "a-b-c"
1781
 */
1782

    
1783
static VALUE
1784
rb_ary_join_m(int argc, VALUE *argv, VALUE ary)
1785
{
1786
    VALUE sep;
1787

    
1788
    rb_scan_args(argc, argv, "01", &sep);
1789
    if (NIL_P(sep)) sep = rb_output_fs;
1790

    
1791
    return rb_ary_join(ary, sep);
1792
}
1793

    
1794
static VALUE
1795
inspect_ary(VALUE ary, VALUE dummy, int recur)
1796
{
1797
    int tainted = OBJ_TAINTED(ary);
1798
    int untrust = OBJ_UNTRUSTED(ary);
1799
    long i;
1800
    VALUE s, str;
1801

    
1802
    if (recur) return rb_usascii_str_new_cstr("[...]");
1803
    str = rb_str_buf_new2("[");
1804
    for (i=0; i<RARRAY_LEN(ary); i++) {
1805
	s = rb_inspect(RARRAY_PTR(ary)[i]);
1806
	if (OBJ_TAINTED(s)) tainted = TRUE;
1807
	if (OBJ_UNTRUSTED(s)) untrust = TRUE;
1808
	if (i > 0) rb_str_buf_cat2(str, ", ");
1809
	else rb_enc_copy(str, s);
1810
	rb_str_buf_append(str, s);
1811
    }
1812
    rb_str_buf_cat2(str, "]");
1813
    if (tainted) OBJ_TAINT(str);
1814
    if (untrust) OBJ_UNTRUST(str);
1815
    return str;
1816
}
1817

    
1818
/*
1819
 *  call-seq:
1820
 *     ary.to_s -> string
1821
 *     ary.inspect  -> string
1822
 *
1823
 *  Creates a string representation of +self+.
1824
 */
1825

    
1826
static VALUE
1827
rb_ary_inspect(VALUE ary)
1828
{
1829
    if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new2("[]");
1830
    return rb_exec_recursive(inspect_ary, ary, 0);
1831
}
1832

    
1833
VALUE
1834
rb_ary_to_s(VALUE ary)
1835
{
1836
    return rb_ary_inspect(ary);
1837
}
1838

    
1839
/*
1840
 *  call-seq:
1841
 *     ary.to_a     -> ary
1842
 *
1843
 *  Returns +self+. If called on a subclass of Array, converts
1844
 *  the receiver to an Array object.
1845
 */
1846

    
1847
static VALUE
1848
rb_ary_to_a(VALUE ary)
1849
{
1850
    if (rb_obj_class(ary) != rb_cArray) {
1851
	VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
1852
	rb_ary_replace(dup, ary);
1853
	return dup;
1854
    }
1855
    return ary;
1856
}
1857

    
1858
/*
1859
 *  call-seq:
1860
 *     ary.to_ary -> ary
1861
 *
1862
 *  Returns +self+.
1863
 */
1864

    
1865
static VALUE
1866
rb_ary_to_ary_m(VALUE ary)
1867
{
1868
    return ary;
1869
}
1870

    
1871
static void
1872
ary_reverse(p1, p2)
1873
    VALUE *p1, *p2;
1874
{
1875
    while (p1 < p2) {
1876
	VALUE tmp = *p1;
1877
	*p1++ = *p2;
1878
	*p2-- = tmp;
1879
    }
1880
}
1881

    
1882
VALUE
1883
rb_ary_reverse(VALUE ary)
1884
{
1885
    VALUE *p1, *p2;
1886

    
1887
    rb_ary_modify(ary);
1888
    if (RARRAY_LEN(ary) > 1) {
1889
	p1 = RARRAY_PTR(ary);
1890
	p2 = p1 + RARRAY_LEN(ary) - 1;	/* points last item */
1891
	ary_reverse(p1, p2);
1892
    }
1893
    return ary;
1894
}
1895

    
1896
/*
1897
 *  call-seq:
1898
 *     ary.reverse!   -> ary
1899
 *
1900
 *  Reverses +self+ in place.
1901
 *
1902
 *     a = [ "a", "b", "c" ]
1903
 *     a.reverse!       #=> ["c", "b", "a"]
1904
 *     a                #=> ["c", "b", "a"]
1905
 */
1906

    
1907
static VALUE
1908
rb_ary_reverse_bang(VALUE ary)
1909
{
1910
    return rb_ary_reverse(ary);
1911
}
1912

    
1913
/*
1914
 *  call-seq:
1915
 *     ary.reverse -> new_ary
1916
 *
1917
 *  Returns a new array containing +self+'s elements in reverse order.
1918
 *
1919
 *     [ "a", "b", "c" ].reverse   #=> ["c", "b", "a"]
1920
 *     [ 1 ].reverse               #=> [1]
1921
 */
1922

    
1923
static VALUE
1924
rb_ary_reverse_m(VALUE ary)
1925
{
1926
    long len = RARRAY_LEN(ary);
1927
    VALUE dup = rb_ary_new2(len);
1928

    
1929
    if (len > 0) {
1930
	VALUE *p1 = RARRAY_PTR(ary);
1931
	VALUE *p2 = RARRAY_PTR(dup) + len - 1;
1932
	do *p2-- = *p1++; while (--len > 0);
1933
    }
1934
    ARY_SET_LEN(dup, RARRAY_LEN(ary));
1935
    return dup;
1936
}
1937

    
1938
static inline long
1939
rotate_count(long cnt, long len)
1940
{
1941
    return (cnt < 0) ? (len - (~cnt % len) - 1) : (cnt % len);
1942
}
1943

    
1944
VALUE
1945
rb_ary_rotate(VALUE ary, long cnt)
1946
{
1947
    rb_ary_modify(ary);
1948

    
1949
    if (cnt != 0) {
1950
	VALUE *ptr = RARRAY_PTR(ary);
1951
	long len = RARRAY_LEN(ary);
1952

    
1953
	if (len > 0 && (cnt = rotate_count(cnt, len)) > 0) {
1954
	    --len;
1955
	    if (cnt < len) ary_reverse(ptr + cnt, ptr + len);
1956
	    if (--cnt > 0) ary_reverse(ptr, ptr + cnt);
1957
	    if (len > 0) ary_reverse(ptr, ptr + len);
1958
	    return ary;
1959
	}
1960
    }
1961

    
1962
    return Qnil;
1963
}
1964

    
1965
/*
1966
 *  call-seq:
1967
 *     ary.rotate!(cnt=1) -> ary
1968
 *
1969
 *  Rotates +self+ in place so that the element at +cnt+ comes first,
1970
 *  and returns +self+.  If +cnt+ is negative then it rotates in
1971
 *  the opposite direction.
1972
 *
1973
 *     a = [ "a", "b", "c", "d" ]
1974
 *     a.rotate!        #=> ["b", "c", "d", "a"]
1975
 *     a                #=> ["b", "c", "d", "a"]
1976
 *     a.rotate!(2)     #=> ["d", "a", "b", "c"]
1977
 *     a.rotate!(-3)    #=> ["a", "b", "c", "d"]
1978
 */
1979

    
1980
static VALUE
1981
rb_ary_rotate_bang(int argc, VALUE *argv, VALUE ary)
1982
{
1983
    long n = 1;
1984

    
1985
    switch (argc) {
1986
      case 1: n = NUM2LONG(argv[0]);
1987
      case 0: break;
1988
      default: rb_scan_args(argc, argv, "01", NULL);
1989
    }
1990
    rb_ary_rotate(ary, n);
1991
    return ary;
1992
}
1993

    
1994
/*
1995
 *  call-seq:
1996
 *     ary.rotate(cnt=1) -> new_ary
1997
 *
1998
 *  Returns new array by rotating +self+ so that the element at
1999
 *  +cnt+ in +self+ is the first element of the new array. If +cnt+
2000
 *  is negative then it rotates in the opposite direction.
2001
 *
2002
 *     a = [ "a", "b", "c", "d" ]
2003
 *     a.rotate         #=> ["b", "c", "d", "a"]
2004
 *     a                #=> ["a", "b", "c", "d"]
2005
 *     a.rotate(2)      #=> ["c", "d", "a", "b"]
2006
 *     a.rotate(-3)     #=> ["b", "c", "d", "a"]
2007
 */
2008

    
2009
static VALUE
2010
rb_ary_rotate_m(int argc, VALUE *argv, VALUE ary)
2011
{
2012
    VALUE rotated, *ptr, *ptr2;
2013
    long len, cnt = 1;
2014

    
2015
    switch (argc) {
2016
      case 1: cnt = NUM2LONG(argv[0]);
2017
      case 0: break;
2018
      default: rb_scan_args(argc, argv, "01", NULL);
2019
    }
2020

    
2021
    len = RARRAY_LEN(ary);
2022
    rotated = rb_ary_new2(len);
2023
    if (len > 0) {
2024
	cnt = rotate_count(cnt, len);
2025
	ptr = RARRAY_PTR(ary);
2026
	ptr2 = RARRAY_PTR(rotated);
2027
	len -= cnt;
2028
	MEMCPY(ptr2, ptr + cnt, VALUE, len);
2029
	MEMCPY(ptr2 + len, ptr, VALUE, cnt);
2030
    }
2031
    ARY_SET_LEN(rotated, RARRAY_LEN(ary));
2032
    return rotated;
2033
}
2034

    
2035
struct ary_sort_data {
2036
    VALUE ary;
2037
    int opt_methods;
2038
    int opt_inited;
2039
};
2040

    
2041
enum {
2042
    sort_opt_Fixnum,
2043
    sort_opt_String,
2044
    sort_optimizable_count
2045
};
2046

    
2047
#define STRING_P(s) (RB_TYPE_P((s), T_STRING) && CLASS_OF(s) == rb_cString)
2048

    
2049
#define SORT_OPTIMIZABLE_BIT(type) (1U << TOKEN_PASTE(sort_opt_,type))
2050
#define SORT_OPTIMIZABLE(data, type) \
2051
    (((data)->opt_inited & SORT_OPTIMIZABLE_BIT(type)) ? \
2052
     ((data)->opt_methods & SORT_OPTIMIZABLE_BIT(type)) : \
2053
     (((data)->opt_inited |= SORT_OPTIMIZABLE_BIT(type)), \
2054
      rb_method_basic_definition_p(TOKEN_PASTE(rb_c,type), id_cmp) && \
2055
      ((data)->opt_methods |= SORT_OPTIMIZABLE_BIT(type))))
2056

    
2057
static VALUE
2058
sort_reentered(VALUE ary)
2059
{
2060
    if (RBASIC(ary)->klass) {
2061
	rb_raise(rb_eRuntimeError, "sort reentered");
2062
    }
2063
    return Qnil;
2064
}
2065

    
2066
static int
2067
sort_1(const void *ap, const void *bp, void *dummy)
2068
{
2069
    struct ary_sort_data *data = dummy;
2070
    VALUE retval = sort_reentered(data->ary);
2071
    VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2072
    int n;
2073

    
2074
    retval = rb_yield_values(2, a, b);
2075
    n = rb_cmpint(retval, a, b);
2076
    sort_reentered(data->ary);
2077
    return n;
2078
}
2079

    
2080
static int
2081
sort_2(const void *ap, const void *bp, void *dummy)
2082
{
2083
    struct ary_sort_data *data = dummy;
2084
    VALUE retval = sort_reentered(data->ary);
2085
    VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2086
    int n;
2087

    
2088
    if (FIXNUM_P(a) && FIXNUM_P(b) && SORT_OPTIMIZABLE(data, Fixnum)) {
2089
	if ((long)a > (long)b) return 1;
2090
	if ((long)a < (long)b) return -1;
2091
	return 0;
2092
    }
2093
    if (STRING_P(a) && STRING_P(b) && SORT_OPTIMIZABLE(data, String)) {
2094
	return rb_str_cmp(a, b);
2095
    }
2096

    
2097
    retval = rb_funcall(a, id_cmp, 1, b);
2098
    n = rb_cmpint(retval, a, b);
2099
    sort_reentered(data->ary);
2100

    
2101
    return n;
2102
}
2103

    
2104
/*
2105
 *  call-seq:
2106
 *     ary.sort!                   -> ary
2107
 *     ary.sort! {| a,b | block }  -> ary
2108
 *
2109
 *  Sorts +self+. Comparisons for
2110
 *  the sort will be done using the <code><=></code> operator or using
2111
 *  an optional code block. The block implements a comparison between
2112
 *  +a+ and +b+, returning -1, 0, or +1. See also
2113
 *  Enumerable#sort_by.
2114
 *
2115
 *     a = [ "d", "a", "e", "c", "b" ]
2116
 *     a.sort!                    #=> ["a", "b", "c", "d", "e"]
2117
 *     a.sort! {|x,y| y <=> x }   #=> ["e", "d", "c", "b", "a"]
2118
 */
2119

    
2120
VALUE
2121
rb_ary_sort_bang(VALUE ary)
2122
{
2123
    rb_ary_modify(ary);
2124
    assert(!ARY_SHARED_P(ary));
2125
    if (RARRAY_LEN(ary) > 1) {
2126
	VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
2127
	struct ary_sort_data data;
2128

    
2129
	RBASIC(tmp)->klass = 0;
2130
	data.ary = tmp;
2131
	data.opt_methods = 0;
2132
	data.opt_inited = 0;
2133
	ruby_qsort(RARRAY_PTR(tmp), RARRAY_LEN(tmp), sizeof(VALUE),
2134
		   rb_block_given_p()?sort_1:sort_2, &data);
2135

    
2136
        if (ARY_EMBED_P(tmp)) {
2137
            assert(ARY_EMBED_P(tmp));
2138
            if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */
2139
                rb_ary_unshare(ary);
2140
            }
2141
            FL_SET_EMBED(ary);
2142
            MEMCPY(RARRAY_PTR(ary), ARY_EMBED_PTR(tmp), VALUE, ARY_EMBED_LEN(tmp));
2143
            ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
2144
        }
2145
        else {
2146
            assert(!ARY_EMBED_P(tmp));
2147
            if (ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
2148
                assert(!ARY_EMBED_P(ary));
2149
                FL_UNSET_SHARED(ary);
2150
                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
2151
            }
2152
            else {
2153
                assert(!ARY_SHARED_P(tmp));
2154
                if (ARY_EMBED_P(ary)) {
2155
                    FL_UNSET_EMBED(ary);
2156
                }
2157
                else if (ARY_SHARED_P(ary)) {
2158
                    /* ary might be destructively operated in the given block */
2159
                    rb_ary_unshare(ary);
2160
                }
2161
                else {
2162
                    xfree(ARY_HEAP_PTR(ary));
2163
                }
2164
                ARY_SET_PTR(ary, RARRAY_PTR(tmp));
2165
                ARY_SET_HEAP_LEN(ary, RARRAY_LEN(tmp));
2166
                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
2167
            }
2168
            /* tmp was lost ownership for the ptr */
2169
            FL_UNSET(tmp, FL_FREEZE);
2170
            FL_SET_EMBED(tmp);
2171
            ARY_SET_EMBED_LEN(tmp, 0);
2172
            FL_SET(tmp, FL_FREEZE);
2173
	}
2174
        /* tmp will be GC'ed. */
2175
        RBASIC(tmp)->klass = rb_cArray;
2176
    }
2177
    return ary;
2178
}
2179

    
2180
/*
2181
 *  call-seq:
2182
 *     ary.sort                   -> new_ary
2183
 *     ary.sort {| a,b | block }  -> new_ary
2184
 *
2185
 *  Returns a new array created by sorting +self+. Comparisons for
2186
 *  the sort will be done using the <code><=></code> operator or using
2187
 *  an optional code block. The block implements a comparison between
2188
 *  +a+ and +b+, returning -1, 0, or +1. See also
2189
 *  Enumerable#sort_by.
2190
 *
2191
 *     a = [ "d", "a", "e", "c", "b" ]
2192
 *     a.sort                    #=> ["a", "b", "c", "d", "e"]
2193
 *     a.sort {|x,y| y <=> x }   #=> ["e", "d", "c", "b", "a"]
2194
 */
2195

    
2196
VALUE
2197
rb_ary_sort(VALUE ary)
2198
{
2199
    ary = rb_ary_dup(ary);
2200
    rb_ary_sort_bang(ary);
2201
    return ary;
2202
}
2203

    
2204

    
2205
static VALUE
2206
sort_by_i(VALUE i)
2207
{
2208
    return rb_yield(i);
2209
}
2210

    
2211
/*
2212
 *  call-seq:
2213
 *     ary.sort_by! {| obj | block }    -> ary
2214
 *     ary.sort_by!                     -> an_enumerator
2215
 *
2216
 *  Sorts +self+ in place using a set of keys generated by mapping the
2217
 *  values in +self+ through the given block.
2218
 *
2219
 *  If no block is given, an enumerator is returned instead.
2220
 *
2221
 */
2222

    
2223
static VALUE
2224
rb_ary_sort_by_bang(VALUE ary)
2225
{
2226
    VALUE sorted;
2227

    
2228
    RETURN_ENUMERATOR(ary, 0, 0);
2229
    rb_ary_modify(ary);
2230
    sorted = rb_block_call(ary, rb_intern("sort_by"), 0, 0, sort_by_i, 0);
2231
    rb_ary_replace(ary, sorted);
2232
    return ary;
2233
}
2234

    
2235

    
2236
/*
2237
 *  call-seq:
2238
 *     ary.collect {|item| block }  -> new_ary
2239
 *     ary.map     {|item| block }  -> new_ary
2240
 *     ary.collect                  -> an_enumerator
2241
 *     ary.map                      -> an_enumerator
2242
 *
2243
 *  Invokes +block+ once for each element of +self+. Creates a
2244
 *  new array containing the values returned by the block.
2245
 *  See also Enumerable#collect.
2246
 *
2247
 *  If no block is given, an enumerator is returned instead.
2248
 *
2249
 *     a = [ "a", "b", "c", "d" ]
2250
 *     a.map {|x| x + "!" }   #=> ["a!", "b!", "c!", "d!"]
2251
 *     a                      #=> ["a", "b", "c", "d"]
2252
 */
2253

    
2254
static VALUE
2255
rb_ary_collect(VALUE ary)
2256
{
2257
    long i;
2258
    VALUE collect;
2259

    
2260
    RETURN_ENUMERATOR(ary, 0, 0);
2261
    collect = rb_ary_new2(RARRAY_LEN(ary));
2262
    for (i = 0; i < RARRAY_LEN(ary); i++) {
2263
	rb_ary_push(collect, rb_yield(RARRAY_PTR(ary)[i]));
2264
    }
2265
    return collect;
2266
}
2267

    
2268

    
2269
/*
2270
 *  call-seq:
2271
 *     ary.collect! {|item| block }   -> ary
2272
 *     ary.map!     {|item| block }   -> ary
2273
 *     ary.collect                    -> an_enumerator
2274
 *     ary.map                        -> an_enumerator
2275
 *
2276
 *  Invokes the block once for each element of +self+, replacing the
2277
 *  element with the value returned by +block+.
2278
 *  See also Enumerable#collect.
2279
 *
2280
 *  If no block is given, an enumerator is returned instead.
2281
 *
2282
 *     a = [ "a", "b", "c", "d" ]
2283
 *     a.map! {|x| x + "!" }
2284
 *     a #=>  [ "a!", "b!", "c!", "d!" ]
2285
 */
2286

    
2287
static VALUE
2288
rb_ary_collect_bang(VALUE ary)
2289
{
2290
    long i;
2291

    
2292
    RETURN_ENUMERATOR(ary, 0, 0);
2293
    rb_ary_modify(ary);
2294
    for (i = 0; i < RARRAY_LEN(ary); i++) {
2295
	rb_ary_store(ary, i, rb_yield(RARRAY_PTR(ary)[i]));
2296
    }
2297
    return ary;
2298
}
2299

    
2300
VALUE
2301
rb_get_values_at(VALUE obj, long olen, int argc, VALUE *argv, VALUE (*func) (VALUE, long))
2302
{
2303
    VALUE result = rb_ary_new2(argc);
2304
    long beg, len, i, j;
2305

    
2306
    for (i=0; i<argc; i++) {
2307
	if (FIXNUM_P(argv[i])) {
2308
	    rb_ary_push(result, (*func)(obj, FIX2LONG(argv[i])));
2309
	    continue;
2310
	}
2311
	/* check if idx is Range */
2312
	switch (rb_range_beg_len(argv[i], &beg, &len, olen, 0)) {
2313
	  case Qfalse:
2314
	    break;
2315
	  case Qnil:
2316
	    continue;
2317
	  default:
2318
	    for (j=0; j<len; j++) {
2319
		rb_ary_push(result, (*func)(obj, j+beg));
2320
	    }
2321
	    continue;
2322
	}
2323
	rb_ary_push(result, (*func)(obj, NUM2LONG(argv[i])));
2324
    }
2325
    return result;
2326
}
2327

    
2328
/*
2329
 *  call-seq:
2330
 *     ary.values_at(selector,... )  -> new_ary
2331
 *
2332
 *  Returns an array containing the elements in
2333
 *  +self+ corresponding to the given selector(s). The selectors
2334
 *  may be either integer indices or ranges.
2335
 *  See also Array#select.
2336
 *
2337
 *     a = %w{ a b c d e f }
2338
 *     a.values_at(1, 3, 5)
2339
 *     a.values_at(1, 3, 5, 7)
2340
 *     a.values_at(-1, -3, -5, -7)
2341
 *     a.values_at(1..3, 2...5)
2342
 */
2343

    
2344
static VALUE
2345
rb_ary_values_at(int argc, VALUE *argv, VALUE ary)
2346
{
2347
    return rb_get_values_at(ary, RARRAY_LEN(ary), argc, argv, rb_ary_entry);
2348
}
2349

    
2350

    
2351
/*
2352
 *  call-seq:
2353
 *     ary.select {|item| block } -> new_ary
2354
 *     ary.select                 -> an_enumerator
2355
 *
2356
 *  Invokes the block passing in successive elements from +self+,
2357
 *  returning an array containing those elements for which the block
2358
 *  returns a true value (equivalent to Enumerable#select).
2359
 *
2360
 *  If no block is given, an enumerator is returned instead.
2361
 *
2362
 *     a = %w{ a b c d e f }
2363
 *     a.select {|v| v =~ /[aeiou]/}   #=> ["a", "e"]
2364
 */
2365

    
2366
static VALUE
2367
rb_ary_select(VALUE ary)
2368
{
2369
    VALUE result;
2370
    long i;
2371

    
2372
    RETURN_ENUMERATOR(ary, 0, 0);
2373
    result = rb_ary_new2(RARRAY_LEN(ary));
2374
    for (i = 0; i < RARRAY_LEN(ary); i++) {
2375
	if (RTEST(rb_yield(RARRAY_PTR(ary)[i]))) {
2376
	    rb_ary_push(result, rb_ary_elt(ary, i));
2377
	}
2378
    }
2379
    return result;
2380
}
2381

    
2382
/*
2383
 *  call-seq:
2384
 *     ary.select! {|item| block } -> ary or nil
2385
 *     ary.select!                 -> an_enumerator
2386
 *
2387
 *  Invokes the block passing in successive elements from
2388
 *  +self+, deleting elements for which the block returns a
2389
 *  false value. It returns +self+ if changes were made,
2390
 *  otherwise it returns <code>nil</code>.
2391
 *  See also Array#keep_if
2392
 *
2393
 *  If no block is given, an enumerator is returned instead.
2394
 *
2395
 */
2396

    
2397
static VALUE
2398
rb_ary_select_bang(VALUE ary)
2399
{
2400
    long i1, i2;
2401

    
2402
    RETURN_ENUMERATOR(ary, 0, 0);
2403
    rb_ary_modify(ary);
2404
    for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2405
	VALUE v = RARRAY_PTR(ary)[i1];
2406
	if (!RTEST(rb_yield(v))) continue;
2407
	if (i1 != i2) {
2408
	    rb_ary_store(ary, i2, v);
2409
	}
2410
	i2++;
2411
    }
2412

    
2413
    if (RARRAY_LEN(ary) == i2) return Qnil;
2414
    if (i2 < RARRAY_LEN(ary))
2415
	ARY_SET_LEN(ary, i2);
2416
    return ary;
2417
}
2418

    
2419
/*
2420
 *  call-seq:
2421
 *     ary.keep_if {|item| block } -> ary
2422
 *     ary.keep_if                 -> an_enumerator
2423
 *
2424
 *  Deletes every element of +self+ for which +block+ evaluates
2425
 *  to false.
2426
 *  See also Array#select!
2427
 *
2428
 *  If no block is given, an enumerator is returned instead.
2429
 *
2430
 *     a = %w{ a b c d e f }
2431
 *     a.keep_if {|v| v =~ /[aeiou]/}   #=> ["a", "e"]
2432
 */
2433

    
2434
static VALUE
2435
rb_ary_keep_if(VALUE ary)
2436
{
2437
    RETURN_ENUMERATOR(ary, 0, 0);
2438
    rb_ary_select_bang(ary);
2439
    return ary;
2440
}
2441

    
2442
/*
2443
 *  call-seq:
2444
 *     ary.delete(obj)            -> obj or nil
2445
 *     ary.delete(obj) { block }  -> obj or nil
2446
 *
2447
 *  Deletes items from +self+ that are equal to +obj+.
2448
 *  If any items are found, returns +obj+.   If
2449
 *  the item is not found, returns <code>nil</code>. If the optional
2450
 *  code block is given, returns the result of +block+ if the item
2451
 *  is not found.  (To remove <code>nil</code> elements and
2452
 *  get an informative return value, use #compact!)
2453
 *
2454
 *     a = [ "a", "b", "b", "b", "c" ]
2455
 *     a.delete("b")                   #=> "b"
2456
 *     a                               #=> ["a", "c"]
2457
 *     a.delete("z")                   #=> nil
2458
 *     a.delete("z") { "not found" }   #=> "not found"
2459
 */
2460

    
2461
VALUE
2462
rb_ary_delete(VALUE ary, VALUE item)
2463
{
2464
    VALUE v = item;
2465
    long i1, i2;
2466

    
2467
    for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2468
	VALUE e = RARRAY_PTR(ary)[i1];
2469

    
2470
	if (rb_equal(e, item)) {
2471
	    v = e;
2472
	    continue;
2473
	}
2474
	if (i1 != i2) {
2475
	    rb_ary_store(ary, i2, e);
2476
	}
2477
	i2++;
2478
    }
2479
    if (RARRAY_LEN(ary) == i2) {
2480
	if (rb_block_given_p()) {
2481
	    return rb_yield(item);
2482
	}
2483
	return Qnil;
2484
    }
2485

    
2486
    rb_ary_modify(ary);
2487
    if (RARRAY_LEN(ary) > i2) {
2488
	ARY_SET_LEN(ary, i2);
2489
	if (i2 * 2 < ARY_CAPA(ary) &&
2490
	    ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
2491
	    ary_resize_capa(ary, i2*2);
2492
	}
2493
    }
2494

    
2495
    return v;
2496
}
2497

    
2498
VALUE
2499
rb_ary_delete_at(VALUE ary, long pos)
2500
{
2501
    long len = RARRAY_LEN(ary);
2502
    VALUE del;
2503

    
2504
    if (pos >= len) return Qnil;
2505
    if (pos < 0) {
2506
	pos += len;
2507
	if (pos < 0) return Qnil;
2508
    }
2509

    
2510
    rb_ary_modify(ary);
2511
    del = RARRAY_PTR(ary)[pos];
2512
    MEMMOVE(RARRAY_PTR(ary)+pos, RARRAY_PTR(ary)+pos+1, VALUE,
2513
	    RARRAY_LEN(ary)-pos-1);
2514
    ARY_INCREASE_LEN(ary, -1);
2515

    
2516
    return del;
2517
}
2518

    
2519
/*
2520
 *  call-seq:
2521
 *     ary.delete_at(index)  -> obj or nil
2522
 *
2523
 *  Deletes the element at the specified index, returning that element,
2524
 *  or <code>nil</code> if the index is out of range. See also
2525
 *  Array#slice!.
2526
 *
2527
 *     a = ["ant", "bat", "cat", "dog"]
2528
 *     a.delete_at(2)    #=> "cat"
2529
 *     a                 #=> ["ant", "bat", "dog"]
2530
 *     a.delete_at(99)   #=> nil
2531
 */
2532

    
2533
static VALUE
2534
rb_ary_delete_at_m(VALUE ary, VALUE pos)
2535
{
2536
    return rb_ary_delete_at(ary, NUM2LONG(pos));
2537
}
2538

    
2539
/*
2540
 *  call-seq:
2541
 *     ary.slice!(index)         -> obj or nil
2542
 *     ary.slice!(start, length) -> new_ary or nil
2543
 *     ary.slice!(range)         -> new_ary or nil
2544
 *
2545
 *  Deletes the element(s) given by an index (optionally with a length)
2546
 *  or by a range. Returns the deleted object (or objects), or
2547
 *  <code>nil</code> if the index is out of range.
2548
 *
2549
 *     a = [ "a", "b", "c" ]
2550
 *     a.slice!(1)     #=> "b"
2551
 *     a               #=> ["a", "c"]
2552
 *     a.slice!(-1)    #=> "c"
2553
 *     a               #=> ["a"]
2554
 *     a.slice!(100)   #=> nil
2555
 *     a               #=> ["a"]
2556
 */
2557

    
2558
static VALUE
2559
rb_ary_slice_bang(int argc, VALUE *argv, VALUE ary)
2560
{
2561
    VALUE arg1, arg2;
2562
    long pos, len, orig_len;
2563

    
2564
    rb_ary_modify_check(ary);
2565
    if (argc == 2) {
2566
	pos = NUM2LONG(argv[0]);
2567
	len = NUM2LONG(argv[1]);
2568
      delete_pos_len:
2569
	if (len < 0) return Qnil;
2570
	orig_len = RARRAY_LEN(ary);
2571
	if (pos < 0) {
2572
	    pos += orig_len;
2573
	    if (pos < 0) return Qnil;
2574
	}
2575
	else if (orig_len < pos) return Qnil;
2576
	if (orig_len < pos + len) {
2577
	    len = orig_len - pos;
2578
	}
2579
	if (len == 0) return rb_ary_new2(0);
2580
	arg2 = rb_ary_new4(len, RARRAY_PTR(ary)+pos);
2581
	RBASIC(arg2)->klass = rb_obj_class(ary);
2582
	rb_ary_splice(ary, pos, len, Qundef);
2583
	return arg2;
2584
    }
2585

    
2586
    if (argc != 1) {
2587
	/* error report */
2588
	rb_scan_args(argc, argv, "11", NULL, NULL);
2589
    }
2590
    arg1 = argv[0];
2591

    
2592
    if (!FIXNUM_P(arg1)) {
2593
	switch (rb_range_beg_len(arg1, &pos, &len, RARRAY_LEN(ary), 0)) {
2594
	  case Qtrue:
2595
	    /* valid range */
2596
	    goto delete_pos_len;
2597
	  case Qnil:
2598
	    /* invalid range */
2599
	    return Qnil;
2600
	  default:
2601
	    /* not a range */
2602
	    break;
2603
	}
2604
    }
2605

    
2606
    return rb_ary_delete_at(ary, NUM2LONG(arg1));
2607
}
2608

    
2609
static VALUE
2610
ary_reject(VALUE orig, VALUE result)
2611
{
2612
    long i;
2613

    
2614
    for (i = 0; i < RARRAY_LEN(orig); i++) {
2615
	VALUE v = RARRAY_PTR(orig)[i];
2616
	if (!RTEST(rb_yield(v))) {
2617
	    rb_ary_push_1(result, v);
2618
	}
2619
    }
2620
    return result;
2621
}
2622

    
2623
static VALUE
2624
ary_reject_bang(VALUE ary)
2625
{
2626
    long i;
2627
    VALUE result = Qnil;
2628

    
2629
    rb_ary_modify_check(ary);
2630
    for (i = 0; i < RARRAY_LEN(ary); ) {
2631
	VALUE v = RARRAY_PTR(ary)[i];
2632
	if (RTEST(rb_yield(v))) {
2633
	    rb_ary_delete_at(ary, i);
2634
	    result = ary;
2635
	}
2636
	else {
2637
	    i++;
2638
	}
2639
    }
2640
    return result;
2641
}
2642

    
2643
/*
2644
 *  call-seq:
2645
 *     ary.reject! {|item| block }  -> ary or nil
2646
 *     ary.reject!                  -> an_enumerator
2647
 *
2648
 *  Equivalent to Array#delete_if, deleting elements from
2649
 *  +self+ for which the block evaluates to true, but returns
2650
 *  <code>nil</code> if no changes were made.
2651
 *  The array is changed instantly every time the block is called and
2652
 *  not after the iteration is over.
2653
 *  See also Enumerable#reject and Array#delete_if.
2654
 *
2655
 *  If no block is given, an enumerator is returned instead.
2656
 *
2657
 */
2658

    
2659
static VALUE
2660
rb_ary_reject_bang(VALUE ary)
2661
{
2662
    RETURN_ENUMERATOR(ary, 0, 0);
2663
    return ary_reject_bang(ary);
2664
}
2665

    
2666
/*
2667
 *  call-seq:
2668
 *     ary.reject {|item| block }  -> new_ary
2669
 *     ary.reject                  -> an_enumerator
2670
 *
2671
 *  Returns a new array containing the items in +self+
2672
 *  for which the block is not true.
2673
 *  See also Array#delete_if
2674
 *
2675
 *  If no block is given, an enumerator is returned instead.
2676
 *
2677
 */
2678

    
2679
static VALUE
2680
rb_ary_reject(VALUE ary)
2681
{
2682
    VALUE rejected_ary;
2683

    
2684
    RETURN_ENUMERATOR(ary, 0, 0);
2685
    rejected_ary = rb_ary_new();
2686
    ary_reject(ary, rejected_ary);
2687
    return rejected_ary;
2688
}
2689

    
2690
/*
2691
 *  call-seq:
2692
 *     ary.delete_if {|item| block }  -> ary
2693
 *     ary.delete_if                  -> an_enumerator
2694
 *
2695
 *  Deletes every element of +self+ for which +block+ evaluates
2696
 *  to true.
2697
 *  The array is changed instantly every time the block is called and
2698
 *  not after the iteration is over.
2699
 *  See also Array#reject!
2700
 *
2701
 *  If no block is given, an enumerator is returned instead.
2702
 *
2703
 *     a = [ "a", "b", "c" ]
2704
 *     a.delete_if {|x| x >= "b" }   #=> ["a"]
2705
 */
2706

    
2707
static VALUE
2708
rb_ary_delete_if(VALUE ary)
2709
{
2710
    RETURN_ENUMERATOR(ary, 0, 0);
2711
    ary_reject_bang(ary);
2712
    return ary;
2713
}
2714

    
2715
static VALUE
2716
take_i(VALUE val, VALUE *args, int argc, VALUE *argv)
2717
{
2718
    if (args[1]-- == 0) rb_iter_break();
2719
    if (argc > 1) val = rb_ary_new4(argc, argv);
2720
    rb_ary_push(args[0], val);
2721
    return Qnil;
2722
}
2723

    
2724
static VALUE
2725
take_items(VALUE obj, long n)
2726
{
2727
    VALUE result = rb_check_array_type(obj);
2728
    VALUE args[2];
2729

    
2730
    if (!NIL_P(result)) return rb_ary_subseq(result, 0, n);
2731
    result = rb_ary_new2(n);
2732
    args[0] = result; args[1] = (VALUE)n;
2733
    rb_block_call(obj, rb_intern("each"), 0, 0, take_i, (VALUE)args);
2734
    return result;
2735
}
2736

    
2737

    
2738
/*
2739
 *  call-seq:
2740
 *     ary.zip(arg, ...)                   -> new_ary
2741
 *     ary.zip(arg, ...) {| arr | block }  -> nil
2742
 *
2743
 *  Converts any arguments to arrays, then merges elements of
2744
 *  +self+ with corresponding elements from each argument. This
2745
 *  generates a sequence of <code>self.size</code> <em>n</em>-element
2746
 *  arrays, where <em>n</em> is one more that the count of arguments. If
2747
 *  the size of any argument is less than <code>enumObj.size</code>,
2748
 *  <code>nil</code> values are supplied. If a block is given, it is
2749
 *  invoked for each output array, otherwise an array of arrays is
2750
 *  returned.
2751
 *
2752
 *     a = [ 4, 5, 6 ]
2753
 *     b = [ 7, 8, 9 ]
2754
 *     [1,2,3].zip(a, b)      #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
2755
 *     [1,2].zip(a,b)         #=> [[1, 4, 7], [2, 5, 8]]
2756
 *     a.zip([1,2],[8])       #=> [[4,1,8], [5,2,nil], [6,nil,nil]]
2757
 */
2758

    
2759
static VALUE
2760
rb_ary_zip(int argc, VALUE *argv, VALUE ary)
2761
{
2762
    int i, j;
2763
    long len;
2764
    VALUE result = Qnil;
2765

    
2766
    len = RARRAY_LEN(ary);
2767
    for (i=0; i<argc; i++) {
2768
	argv[i] = take_items(argv[i], len);
2769
    }
2770
    if (!rb_block_given_p()) {
2771
	result = rb_ary_new2(len);
2772
    }
2773

    
2774
    for (i=0; i<RARRAY_LEN(ary); i++) {
2775
	VALUE tmp = rb_ary_new2(argc+1);
2776

    
2777
	rb_ary_push(tmp, rb_ary_elt(ary, i));
2778
	for (j=0; j<argc; j++) {
2779
	    rb_ary_push(tmp, rb_ary_elt(argv[j], i));
2780
	}
2781
	if (NIL_P(result)) {
2782
	    rb_yield(tmp);
2783
	}
2784
	else {
2785
	    rb_ary_push(result, tmp);
2786
	}
2787
    }
2788
    return result;
2789
}
2790

    
2791
/*
2792
 *  call-seq:
2793
 *     ary.transpose -> new_ary
2794
 *
2795
 *  Assumes that +self+ is an array of arrays and transposes the
2796
 *  rows and columns.
2797
 *
2798
 *     a = [[1,2], [3,4], [5,6]]
2799
 *     a.transpose   #=> [[1, 3, 5], [2, 4, 6]]
2800
 */
2801

    
2802
static VALUE
2803
rb_ary_transpose(VALUE ary)
2804
{
2805
    long elen = -1, alen, i, j;
2806
    VALUE tmp, result = 0;
2807

    
2808
    alen = RARRAY_LEN(ary);
2809
    if (alen == 0) return rb_ary_dup(ary);
2810
    for (i=0; i<alen; i++) {
2811
	tmp = to_ary(rb_ary_elt(ary, i));
2812
	if (elen < 0) {		/* first element */
2813
	    elen = RARRAY_LEN(tmp);
2814
	    result = rb_ary_new2(elen);
2815
	    for (j=0; j<elen; j++) {
2816
		rb_ary_store(result, j, rb_ary_new2(alen));
2817
	    }
2818
	}
2819
	else if (elen != RARRAY_LEN(tmp)) {
2820
	    rb_raise(rb_eIndexError, "element size differs (%ld should be %ld)",
2821
		     RARRAY_LEN(tmp), elen);
2822
	}
2823
	for (j=0; j<elen; j++) {
2824
	    rb_ary_store(rb_ary_elt(result, j), i, rb_ary_elt(tmp, j));
2825
	}
2826
    }
2827
    return result;
2828
}
2829

    
2830
/*
2831
 *  call-seq:
2832
 *     ary.replace(other_ary)  -> ary
2833
 *
2834
 *  Replaces the contents of +self+ with the contents of
2835
 *  +other_ary+, truncating or expanding if necessary.
2836
 *
2837
 *     a = [ "a", "b", "c", "d", "e" ]
2838
 *     a.replace([ "x", "y", "z" ])   #=> ["x", "y", "z"]
2839
 *     a                              #=> ["x", "y", "z"]
2840
 */
2841

    
2842
VALUE
2843
rb_ary_replace(VALUE copy, VALUE orig)
2844
{
2845
    rb_ary_modify_check(copy);
2846
    orig = to_ary(orig);
2847
    if (copy == orig) return copy;
2848

    
2849
    if (RARRAY_LEN(orig) <= RARRAY_EMBED_LEN_MAX) {
2850
        VALUE *ptr;
2851
        VALUE shared = 0;
2852

    
2853
        if (ARY_OWNS_HEAP_P(copy)) {
2854
            xfree(RARRAY_PTR(copy));
2855
        }
2856
        else if (ARY_SHARED_P(copy)) {
2857
            shared = ARY_SHARED(copy);
2858
            FL_UNSET_SHARED(copy);
2859
        }
2860
        FL_SET_EMBED(copy);
2861
        ptr = RARRAY_PTR(orig);
2862
        MEMCPY(RARRAY_PTR(copy), ptr, VALUE, RARRAY_LEN(orig));
2863
        if (shared) {
2864
            rb_ary_decrement_share(shared);
2865
        }
2866
        ARY_SET_LEN(copy, RARRAY_LEN(orig));
2867
    }
2868
    else {
2869
        VALUE shared = ary_make_shared(orig);
2870
        if (ARY_OWNS_HEAP_P(copy)) {
2871
            xfree(RARRAY_PTR(copy));
2872
        }
2873
        else {
2874
            rb_ary_unshare_safe(copy);
2875
        }
2876
        FL_UNSET_EMBED(copy);
2877
        ARY_SET_PTR(copy, RARRAY_PTR(orig));
2878
        ARY_SET_LEN(copy, RARRAY_LEN(orig));
2879
        rb_ary_set_shared(copy, shared);
2880
    }
2881
    return copy;
2882
}
2883

    
2884
/*
2885
 *  call-seq:
2886
 *     ary.clear    -> ary
2887
 *
2888
 *  Removes all elements from +self+.
2889
 *
2890
 *     a = [ "a", "b", "c", "d", "e" ]
2891
 *     a.clear    #=> [ ]
2892
 */
2893

    
2894
VALUE
2895
rb_ary_clear(VALUE ary)
2896
{
2897
    rb_ary_modify_check(ary);
2898
    ARY_SET_LEN(ary, 0);
2899
    if (ARY_SHARED_P(ary)) {
2900
	if (!ARY_EMBED_P(ary)) {
2901
	    rb_ary_unshare(ary);
2902
	    FL_SET_EMBED(ary);
2903
	}
2904
    }
2905
    else if (ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
2906
	ary_resize_capa(ary, ARY_DEFAULT_SIZE * 2);
2907
    }
2908
    return ary;
2909
}
2910

    
2911
/*
2912
 *  call-seq:
2913
 *     ary.fill(obj)                                -> ary
2914
 *     ary.fill(obj, start [, length])              -> ary
2915
 *     ary.fill(obj, range )                        -> ary
2916
 *     ary.fill {|index| block }                    -> ary
2917
 *     ary.fill(start [, length] ) {|index| block } -> ary
2918
 *     ary.fill(range) {|index| block }             -> ary
2919
 *
2920
 *  The first three forms set the selected elements of +self+ (which
2921
 *  may be the entire array) to +obj+. A +start+ of
2922
 *  <code>nil</code> is equivalent to zero. A +length+ of
2923
 *  <code>nil</code> is equivalent to <code>self.length</code>. The last three
2924
 *  forms fill the array with the value of the block. The block is
2925
 *  passed the absolute index of each element to be filled.
2926
 *  Negative values of +start+ count from the end of the array.
2927
 *
2928
 *     a = [ "a", "b", "c", "d" ]
2929
 *     a.fill("x")              #=> ["x", "x", "x", "x"]
2930
 *     a.fill("z", 2, 2)        #=> ["x", "x", "z", "z"]
2931
 *     a.fill("y", 0..1)        #=> ["y", "y", "z", "z"]
2932
 *     a.fill {|i| i*i}         #=> [0, 1, 4, 9]
2933
 *     a.fill(-2) {|i| i*i*i}   #=> [0, 1, 8, 27]
2934
 */
2935

    
2936
static VALUE
2937
rb_ary_fill(int argc, VALUE *argv, VALUE ary)
2938
{
2939
    VALUE item, arg1, arg2;
2940
    long beg = 0, end = 0, len = 0;
2941
    VALUE *p, *pend;
2942
    int block_p = FALSE;
2943

    
2944
    if (rb_block_given_p()) {
2945
	block_p = TRUE;
2946
	rb_scan_args(argc, argv, "02", &arg1, &arg2);
2947
	argc += 1;		/* hackish */
2948
    }
2949
    else {
2950
	rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
2951
    }
2952
    switch (argc) {
2953
      case 1:
2954
	beg = 0;
2955
	len = RARRAY_LEN(ary);
2956
	break;
2957
      case 2:
2958
	if (rb_range_beg_len(arg1, &beg, &len, RARRAY_LEN(ary), 1)) {
2959
	    break;
2960
	}
2961
	/* fall through */
2962
      case 3:
2963
	beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
2964
	if (beg < 0) {
2965
	    beg = RARRAY_LEN(ary) + beg;
2966
	    if (beg < 0) beg = 0;
2967
	}
2968
	len = NIL_P(arg2) ? RARRAY_LEN(ary) - beg : NUM2LONG(arg2);
2969
	break;
2970
    }
2971
    rb_ary_modify(ary);
2972
    if (len < 0) {
2973
        return ary;
2974
    }
2975
    if (beg >= ARY_MAX_SIZE || len > ARY_MAX_SIZE - beg) {
2976
	rb_raise(rb_eArgError, "argument too big");
2977
    }
2978
    end = beg + len;
2979
    if (RARRAY_LEN(ary) < end) {
2980
	if (end >= ARY_CAPA(ary)) {
2981
	    ary_resize_capa(ary, end);
2982
	}
2983
	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), end - RARRAY_LEN(ary));
2984
	ARY_SET_LEN(ary, end);
2985
    }
2986

    
2987
    if (block_p) {
2988
	VALUE v;
2989
	long i;
2990

    
2991
	for (i=beg; i<end; i++) {
2992
	    v = rb_yield(LONG2NUM(i));
2993
	    if (i>=RARRAY_LEN(ary)) break;
2994
	    RARRAY_PTR(ary)[i] = v;
2995
	}
2996
    }
2997
    else {
2998
	p = RARRAY_PTR(ary) + beg;
2999
	pend = p + len;
3000
	while (p < pend) {
3001
	    *p++ = item;
3002
	}
3003
    }
3004
    return ary;
3005
}
3006

    
3007
/*
3008
 *  call-seq:
3009
 *     ary + other_ary   -> new_ary
3010
 *
3011
 *  Concatenation---Returns a new array built by concatenating the
3012
 *  two arrays together to produce a third array.
3013
 *
3014
 *     [ 1, 2, 3 ] + [ 4, 5 ]    #=> [ 1, 2, 3, 4, 5 ]
3015
 */
3016

    
3017
VALUE
3018
rb_ary_plus(VALUE x, VALUE y)
3019
{
3020
    VALUE z;
3021
    long len;
3022

    
3023
    y = to_ary(y);
3024
    len = RARRAY_LEN(x) + RARRAY_LEN(y);
3025
    z = rb_ary_new2(len);
3026
    MEMCPY(RARRAY_PTR(z), RARRAY_PTR(x), VALUE, RARRAY_LEN(x));
3027
    MEMCPY(RARRAY_PTR(z) + RARRAY_LEN(x), RARRAY_PTR(y), VALUE, RARRAY_LEN(y));
3028
    ARY_SET_LEN(z, len);
3029
    return z;
3030
}
3031

    
3032
/*
3033
 *  call-seq:
3034
 *     ary.concat(other_ary)   -> ary
3035
 *
3036
 *  Appends the elements of +other_ary+ to +self+.
3037
 *
3038
 *     [ "a", "b" ].concat( ["c", "d"] ) #=> [ "a", "b", "c", "d" ]
3039
 */
3040

    
3041

    
3042
VALUE
3043
rb_ary_concat(VALUE x, VALUE y)
3044
{
3045
    rb_ary_modify_check(x);
3046
    y = to_ary(y);
3047
    if (RARRAY_LEN(y) > 0) {
3048
	rb_ary_splice(x, RARRAY_LEN(x), 0, y);
3049
    }
3050
    return x;
3051
}
3052

    
3053

    
3054
/*
3055
 *  call-seq:
3056
 *     ary * int     -> new_ary
3057
 *     ary * str     -> new_string
3058
 *
3059
 *  Repetition---With a String argument, equivalent to
3060
 *  self.join(str). Otherwise, returns a new array
3061
 *  built by concatenating the +int+ copies of +self+.
3062
 *
3063
 *
3064
 *     [ 1, 2, 3 ] * 3    #=> [ 1, 2, 3, 1, 2, 3, 1, 2, 3 ]
3065
 *     [ 1, 2, 3 ] * ","  #=> "1,2,3"
3066
 *
3067
 */
3068

    
3069
static VALUE
3070
rb_ary_times(VALUE ary, VALUE times)
3071
{
3072
    VALUE ary2, tmp, *ptr, *ptr2;
3073
    long t, len;
3074

    
3075
    tmp = rb_check_string_type(times);
3076
    if (!NIL_P(tmp)) {
3077
	return rb_ary_join(ary, tmp);
3078
    }
3079

    
3080
    len = NUM2LONG(times);
3081
    if (len == 0) {
3082
	ary2 = ary_new(rb_obj_class(ary), 0);
3083
	goto out;
3084
    }
3085
    if (len < 0) {
3086
	rb_raise(rb_eArgError, "negative argument");
3087
    }
3088
    if (ARY_MAX_SIZE/len < RARRAY_LEN(ary)) {
3089
	rb_raise(rb_eArgError, "argument too big");
3090
    }
3091
    len *= RARRAY_LEN(ary);
3092

    
3093
    ary2 = ary_new(rb_obj_class(ary), len);
3094
    ARY_SET_LEN(ary2, len);
3095

    
3096
    ptr = RARRAY_PTR(ary);
3097
    ptr2 = RARRAY_PTR(ary2);
3098
    t = RARRAY_LEN(ary);
3099
    if (0 < t) {
3100
        MEMCPY(ptr2, ptr, VALUE, t);
3101
        while (t <= len/2) {
3102
            MEMCPY(ptr2+t, ptr2, VALUE, t);
3103
            t *= 2;
3104
        }
3105
        if (t < len) {
3106
            MEMCPY(ptr2+t, ptr2, VALUE, len-t);
3107
        }
3108
    }
3109
  out:
3110
    OBJ_INFECT(ary2, ary);
3111

    
3112
    return ary2;
3113
}
3114

    
3115
/*
3116
 *  call-seq:
3117
 *     ary.assoc(obj)   -> new_ary  or  nil
3118
 *
3119
 *  Searches through an array whose elements are also arrays
3120
 *  comparing +obj+ with the first element of each contained array
3121
 *  using obj.==.
3122
 *  Returns the first contained array that matches (that
3123
 *  is, the first associated array),
3124
 *  or +nil+ if no match is found.
3125
 *  See also Array#rassoc.
3126
 *
3127
 *     s1 = [ "colors", "red", "blue", "green" ]
3128
 *     s2 = [ "letters", "a", "b", "c" ]
3129
 *     s3 = "foo"
3130
 *     a  = [ s1, s2, s3 ]
3131
 *     a.assoc("letters")  #=> [ "letters", "a", "b", "c" ]
3132
 *     a.assoc("foo")      #=> nil
3133
 */
3134

    
3135
VALUE
3136
rb_ary_assoc(VALUE ary, VALUE key)
3137
{
3138
    long i;
3139
    VALUE v;
3140

    
3141
    for (i = 0; i < RARRAY_LEN(ary); ++i) {
3142
	v = rb_check_array_type(RARRAY_PTR(ary)[i]);
3143
	if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
3144
	    rb_equal(RARRAY_PTR(v)[0], key))
3145
	    return v;
3146
    }
3147
    return Qnil;
3148
}
3149

    
3150
/*
3151
 *  call-seq:
3152
 *     ary.rassoc(obj) -> new_ary or nil
3153
 *
3154
 *  Searches through the array whose elements are also arrays. Compares
3155
 *  +obj+ with the second element of each contained array using
3156
 *  <code>==</code>. Returns the first contained array that matches. See
3157
 *  also Array#assoc.
3158
 *
3159
 *     a = [ [ 1, "one"], [2, "two"], [3, "three"], ["ii", "two"] ]
3160
 *     a.rassoc("two")    #=> [2, "two"]
3161
 *     a.rassoc("four")   #=> nil
3162
 */
3163

    
3164
VALUE
3165
rb_ary_rassoc(VALUE ary, VALUE value)
3166
{
3167
    long i;
3168
    VALUE v;
3169

    
3170
    for (i = 0; i < RARRAY_LEN(ary); ++i) {
3171
	v = RARRAY_PTR(ary)[i];
3172
	if (RB_TYPE_P(v, T_ARRAY) &&
3173
	    RARRAY_LEN(v) > 1 &&
3174
	    rb_equal(RARRAY_PTR(v)[1], value))
3175
	    return v;
3176
    }
3177
    return Qnil;
3178
}
3179

    
3180
static VALUE
3181
recursive_equal(VALUE ary1, VALUE ary2, int recur)
3182
{
3183
    long i;
3184

    
3185
    if (recur) return Qtrue; /* Subtle! */
3186
    for (i=0; i<RARRAY_LEN(ary1); i++) {
3187
	if (!rb_equal(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
3188
	    return Qfalse;
3189
    }
3190
    return Qtrue;
3191
}
3192

    
3193
/*
3194
 *  call-seq:
3195
 *     ary == other_ary   ->   bool
3196
 *
3197
 *  Equality---Two arrays are equal if they contain the same number
3198
 *  of elements and if each element is equal to (according to
3199
 *  Object.==) the corresponding element in the other array.
3200
 *
3201
 *     [ "a", "c" ]    == [ "a", "c", 7 ]     #=> false
3202
 *     [ "a", "c", 7 ] == [ "a", "c", 7 ]     #=> true
3203
 *     [ "a", "c", 7 ] == [ "a", "d", "f" ]   #=> false
3204
 *
3205
 */
3206

    
3207
static VALUE
3208
rb_ary_equal(VALUE ary1, VALUE ary2)
3209
{
3210
    if (ary1 == ary2) return Qtrue;
3211
    if (!RB_TYPE_P(ary2, T_ARRAY)) {
3212
	if (!rb_respond_to(ary2, rb_intern("to_ary"))) {
3213
	    return Qfalse;
3214
	}
3215
	return rb_equal(ary2, ary1);
3216
    }
3217
    if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
3218
    return rb_exec_recursive_paired(recursive_equal, ary1, ary2, ary2);
3219
}
3220

    
3221
static VALUE
3222
recursive_eql(VALUE ary1, VALUE ary2, int recur)
3223
{
3224
    long i;
3225

    
3226
    if (recur) return Qtrue; /* Subtle! */
3227
    for (i=0; i<RARRAY_LEN(ary1); i++) {
3228
	if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
3229
	    return Qfalse;
3230
    }
3231
    return Qtrue;
3232
}
3233

    
3234
/*
3235
 *  call-seq:
3236
 *     ary.eql?(other)  -> true or false
3237
 *
3238
 *  Returns <code>true</code> if +self+ and +other+ are the same object,
3239
 *  or are both arrays with the same content.
3240
 */
3241

    
3242
static VALUE
3243
rb_ary_eql(VALUE ary1, VALUE ary2)
3244
{
3245
    if (ary1 == ary2) return Qtrue;
3246
    if (!RB_TYPE_P(ary2, T_ARRAY)) return Qfalse;
3247
    if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
3248
    return rb_exec_recursive_paired(recursive_eql, ary1, ary2, ary2);
3249
}
3250

    
3251
static VALUE
3252
recursive_hash(VALUE ary, VALUE dummy, int recur)
3253
{
3254
    long i;
3255
    st_index_t h;
3256
    VALUE n;
3257

    
3258
    h = rb_hash_start(RARRAY_LEN(ary));
3259
    if (recur) {
3260
	h = rb_hash_uint(h, NUM2LONG(rb_hash(rb_cArray)));
3261
    }
3262
    else {
3263
	for (i=0; i<RARRAY_LEN(ary); i++) {
3264
	    n = rb_hash(RARRAY_PTR(ary)[i]);
3265
	    h = rb_hash_uint(h, NUM2LONG(n));
3266
	}
3267
    }
3268
    h = rb_hash_end(h);
3269
    return LONG2FIX(h);
3270
}
3271

    
3272
/*
3273
 *  call-seq:
3274
 *     ary.hash   -> fixnum
3275
 *
3276
 *  Compute a hash-code for this array. Two arrays with the same content
3277
 *  will have the same hash code (and will compare using <code>eql?</code>).
3278
 */
3279

    
3280
static VALUE
3281
rb_ary_hash(VALUE ary)
3282
{
3283
    return rb_exec_recursive_outer(recursive_hash, ary, 0);
3284
}
3285

    
3286
/*
3287
 *  call-seq:
3288
 *     ary.include?(object)   -> true or false
3289
 *
3290
 *  Returns <code>true</code> if the given +object+ is present in
3291
 *  +self+ (that is, if any object <code>==</code> +object+),
3292
 *  <code>false</code> otherwise.
3293
 *
3294
 *     a = [ "a", "b", "c" ]
3295
 *     a.include?("b")   #=> true
3296
 *     a.include?("z")   #=> false
3297
 */
3298

    
3299
VALUE
3300
rb_ary_includes(VALUE ary, VALUE item)
3301
{
3302
    long i;
3303

    
3304
    for (i=0; i<RARRAY_LEN(ary); i++) {
3305
	if (rb_equal(RARRAY_PTR(ary)[i], item)) {
3306
	    return Qtrue;
3307
	}
3308
    }
3309
    return Qfalse;
3310
}
3311

    
3312

    
3313
static VALUE
3314
recursive_cmp(VALUE ary1, VALUE ary2, int recur)
3315
{
3316
    long i, len;
3317

    
3318
    if (recur) return Qundef;	/* Subtle! */
3319
    len = RARRAY_LEN(ary1);
3320
    if (len > RARRAY_LEN(ary2)) {
3321
	len = RARRAY_LEN(ary2);
3322
    }
3323
    for (i=0; i<len; i++) {
3324
	VALUE v = rb_funcall(rb_ary_elt(ary1, i), id_cmp, 1, rb_ary_elt(ary2, i));
3325
	if (v != INT2FIX(0)) {
3326
	    return v;
3327
	}
3328
    }
3329
    return Qundef;
3330
}
3331

    
3332
/*
3333
 *  call-seq:
3334
 *     ary <=> other_ary   ->  -1, 0, +1 or nil
3335
 *
3336
 *  Comparison---Returns an integer (-1, 0,
3337
 *  or +1) if this array is less than, equal to, or greater than
3338
 *  +other_ary+.
3339
 *
3340
 *  Each object in each array is compared (using <=>). Arrays are compared in
3341
 *  an "element-wise" manner; the first two elements that are not equal will
3342
 *  determine the return value for the whole comparison.  If all the values
3343
 *  are equal, then the return is based on a comparison of the array lengths.
3344
 *  Thus, two arrays are "equal" according to Array#<=> if and only if they
3345
 *  have the same length and the value of each element is equal to the
3346
 *  value of the corresponding element in the other array.
3347
 *
3348
 *     [ "a", "a", "c" ]    <=> [ "a", "b", "c" ]   #=> -1
3349
 *     [ 1, 2, 3, 4, 5, 6 ] <=> [ 1, 2 ]            #=> +1
3350
 *
3351
 */
3352

    
3353
VALUE
3354
rb_ary_cmp(VALUE ary1, VALUE ary2)
3355
{
3356
    long len;
3357
    VALUE v;
3358

    
3359
    ary2 = rb_check_array_type(ary2);
3360
    if (NIL_P(ary2)) return Qnil;
3361
    if (ary1 == ary2) return INT2FIX(0);
3362
    v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
3363
    if (v != Qundef) return v;
3364
    len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
3365
    if (len == 0) return INT2FIX(0);
3366
    if (len > 0) return INT2FIX(1);
3367
    return INT2FIX(-1);
3368
}
3369

    
3370
static VALUE
3371
ary_add_hash(VALUE hash, VALUE ary)
3372
{
3373
    long i;
3374

    
3375
    for (i=0; i<RARRAY_LEN(ary); i++) {
3376
	rb_hash_aset(hash, RARRAY_PTR(ary)[i], Qtrue);
3377
    }
3378
    return hash;
3379
}
3380

    
3381
static inline VALUE
3382
ary_tmp_hash_new(void)
3383
{
3384
    VALUE hash = rb_hash_new();
3385

    
3386
    RBASIC(hash)->klass = 0;
3387
    return hash;
3388
}
3389

    
3390
static VALUE
3391
ary_make_hash(VALUE ary)
3392
{
3393
    VALUE hash = ary_tmp_hash_new();
3394
    return ary_add_hash(hash, ary);
3395
}
3396

    
3397
static VALUE
3398
ary_add_hash_by(VALUE hash, VALUE ary)
3399
{
3400
    long i;
3401

    
3402
    for (i = 0; i < RARRAY_LEN(ary); ++i) {
3403
	VALUE v = rb_ary_elt(ary, i), k = rb_yield(v);
3404
	if (rb_hash_lookup2(hash, k, Qundef) == Qundef) {
3405
	    rb_hash_aset(hash, k, v);
3406
	}
3407
    }
3408
    return hash;
3409
}
3410

    
3411
static VALUE
3412
ary_make_hash_by(VALUE ary)
3413
{
3414
    VALUE hash = ary_tmp_hash_new();
3415
    return ary_add_hash_by(hash, ary);
3416
}
3417

    
3418
static inline void
3419
ary_recycle_hash(VALUE hash)
3420
{
3421
    if (RHASH(hash)->ntbl) {
3422
	st_table *tbl = RHASH(hash)->ntbl;
3423
	RHASH(hash)->ntbl = 0;
3424
	st_free_table(tbl);
3425
    }
3426
}
3427

    
3428
/*
3429
 *  call-seq:
3430
 *     ary - other_ary    -> new_ary
3431
 *
3432
 *  Array Difference---Returns a new array that is a copy of
3433
 *  the original array, removing any items that also appear in
3434
 *  +other_ary+. (If you need set-like behavior, see the
3435
 *  library class Set.)
3436
 *
3437
 *     [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ]  #=>  [ 3, 3, 5 ]
3438
 */
3439

    
3440
static VALUE
3441
rb_ary_diff(VALUE ary1, VALUE ary2)
3442
{
3443
    VALUE ary3;
3444
    volatile VALUE hash;
3445
    long i;
3446

    
3447
    hash = ary_make_hash(to_ary(ary2));
3448
    ary3 = rb_ary_new();
3449

    
3450
    for (i=0; i<RARRAY_LEN(ary1); i++) {
3451
	if (st_lookup(RHASH_TBL(hash), RARRAY_PTR(ary1)[i], 0)) continue;
3452
	rb_ary_push(ary3, rb_ary_elt(ary1, i));
3453
    }
3454
    ary_recycle_hash(hash);
3455
    return ary3;
3456
}
3457

    
3458
/*
3459
 *  call-seq:
3460
 *     ary & other_ary      -> new_ary
3461
 *
3462
 *  Set Intersection---Returns a new array
3463
 *  containing elements common to the two arrays, with no duplicates.
3464
 *
3465
 *     [ 1, 1, 3, 5 ] & [ 1, 2, 3 ]   #=> [ 1, 3 ]
3466
 */
3467

    
3468

    
3469
static VALUE
3470
rb_ary_and(VALUE ary1, VALUE ary2)
3471
{
3472
    VALUE hash, ary3, v;
3473
    st_data_t vv;
3474
    long i;
3475

    
3476
    ary2 = to_ary(ary2);
3477
    ary3 = rb_ary_new2(RARRAY_LEN(ary1) < RARRAY_LEN(ary2) ?
3478
	    RARRAY_LEN(ary1) : RARRAY_LEN(ary2));
3479
    hash = ary_make_hash(ary2);
3480

    
3481
    if (RHASH_EMPTY_P(hash))
3482
        return ary3;
3483

    
3484
    for (i=0; i<RARRAY_LEN(ary1); i++) {
3485
	vv = (st_data_t)(v = rb_ary_elt(ary1, i));
3486
	if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3487
	    rb_ary_push(ary3, v);
3488
	}
3489
    }
3490
    ary_recycle_hash(hash);
3491

    
3492
    return ary3;
3493
}
3494

    
3495
/*
3496
 *  call-seq:
3497
 *     ary | other_ary     -> new_ary
3498
 *
3499
 *  Set Union---Returns a new array by joining this array with
3500
 *  +other_ary+, removing duplicates.
3501
 *
3502
 *     [ "a", "b", "c" ] | [ "c", "d", "a" ]
3503
 *            #=> [ "a", "b", "c", "d" ]
3504
 */
3505

    
3506
static VALUE
3507
rb_ary_or(VALUE ary1, VALUE ary2)
3508
{
3509
    VALUE hash, ary3, v;
3510
    st_data_t vv;
3511
    long i;
3512

    
3513
    ary2 = to_ary(ary2);
3514
    ary3 = rb_ary_new2(RARRAY_LEN(ary1)+RARRAY_LEN(ary2));
3515
    hash = ary_add_hash(ary_make_hash(ary1), ary2);
3516

    
3517
    for (i=0; i<RARRAY_LEN(ary1); i++) {
3518
	vv = (st_data_t)(v = rb_ary_elt(ary1, i));
3519
	if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3520
	    rb_ary_push(ary3, v);
3521
	}
3522
    }
3523
    for (i=0; i<RARRAY_LEN(ary2); i++) {
3524
	vv = (st_data_t)(v = rb_ary_elt(ary2, i));
3525
	if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3526
	    rb_ary_push(ary3, v);
3527
	}
3528
    }
3529
    ary_recycle_hash(hash);
3530
    return ary3;
3531
}
3532

    
3533
static int
3534
push_value(st_data_t key, st_data_t val, st_data_t ary)
3535
{
3536
    rb_ary_push((VALUE)ary, (VALUE)val);
3537
    return ST_CONTINUE;
3538
}
3539

    
3540
/*
3541
 *  call-seq:
3542
 *     ary.uniq!                -> ary or nil
3543
 *     ary.uniq! { |item| ... } -> ary or nil
3544
 *
3545
 *  Removes duplicate elements from +self+. If a block is given,
3546
 *  it will use the return value of the block for comparison.
3547
 *  Returns <code>nil</code> if no changes are made (that is, no
3548
 *  duplicates are found).
3549
 *
3550
 *     a = [ "a", "a", "b", "b", "c" ]
3551
 *     a.uniq!   # => ["a", "b", "c"]
3552
 *
3553
 *     b = [ "a", "b", "c" ]
3554
 *     b.uniq!   # => nil
3555
 *
3556
 *     c = [["student","sam"], ["student","george"], ["teacher","matz"]]
3557
 *     c.uniq! { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
3558
 *
3559
 */
3560

    
3561
static VALUE
3562
rb_ary_uniq_bang(VALUE ary)
3563
{
3564
    VALUE hash, v;
3565
    long i, j;
3566

    
3567
    rb_ary_modify_check(ary);
3568
    if (RARRAY_LEN(ary) <= 1)
3569
        return Qnil;
3570
    if (rb_block_given_p()) {
3571
	hash = ary_make_hash_by(ary);
3572
	if (RARRAY_LEN(ary) == (i = RHASH_SIZE(hash))) {
3573
	    return Qnil;
3574
	}
3575
	ARY_SET_LEN(ary, 0);
3576
	if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
3577
	    rb_ary_unshare(ary);
3578
	    FL_SET_EMBED(ary);
3579
	}
3580
	ary_resize_capa(ary, i);
3581
	st_foreach(RHASH_TBL(hash), push_value, ary);
3582
    }
3583
    else {
3584
	hash = ary_make_hash(ary);
3585
	if (RARRAY_LEN(ary) == (long)RHASH_SIZE(hash)) {
3586
	    return Qnil;
3587
	}
3588
	for (i=j=0; i<RARRAY_LEN(ary); i++) {
3589
	    st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
3590
	    if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3591
		rb_ary_store(ary, j++, v);
3592
	    }
3593
	}
3594
	ARY_SET_LEN(ary, j);
3595
    }
3596
    ary_recycle_hash(hash);
3597

    
3598
    return ary;
3599
}
3600

    
3601
/*
3602
 *  call-seq:
3603
 *     ary.uniq                -> ary or nil
3604
 *     ary.uniq { |item| ... } -> ary or nil
3605
 *
3606
 *  Returns a new array by removing duplicate values in +self+. If a block
3607
 *  is given, it will use the return value of the block for comparison.
3608
 *
3609
 *     a = [ "a", "a", "b", "b", "c" ]
3610
 *     a.uniq   # => ["a", "b", "c"]
3611
 *
3612
 *     b = [["student","sam"], ["student","george"], ["teacher","matz"]]
3613
 *     b.uniq { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
3614
 *
3615
 */
3616

    
3617
static VALUE
3618
rb_ary_uniq(VALUE ary)
3619
{
3620
    VALUE hash, uniq, v;
3621
    long i;
3622

    
3623
    if (RARRAY_LEN(ary) <= 1)
3624
        return rb_ary_dup(ary);
3625
    if (rb_block_given_p()) {
3626
	hash = ary_make_hash_by(ary);
3627
	uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
3628
	st_foreach(RHASH_TBL(hash), push_value, uniq);
3629
    }
3630
    else {
3631
	hash = ary_make_hash(ary);
3632
	uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
3633
	for (i=0; i<RARRAY_LEN(ary); i++) {
3634
	    st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
3635
	    if (st_delete(RHASH_TBL(hash), &vv, 0)) {
3636
		rb_ary_push(uniq, v);
3637
	    }
3638
	}
3639
    }
3640
    ary_recycle_hash(hash);
3641

    
3642
    return uniq;
3643
}
3644

    
3645
/*
3646
 *  call-seq:
3647
 *     ary.compact!    -> ary  or  nil
3648
 *
3649
 *  Removes +nil+ elements from the array.
3650
 *  Returns +nil+ if no changes were made, otherwise returns the array.
3651
 *
3652
 *     [ "a", nil, "b", nil, "c" ].compact! #=> [ "a", "b", "c" ]
3653
 *     [ "a", "b", "c" ].compact!           #=> nil
3654
 */
3655

    
3656
static VALUE
3657
rb_ary_compact_bang(VALUE ary)
3658
{
3659
    VALUE *p, *t, *end;
3660
    long n;
3661

    
3662
    rb_ary_modify(ary);
3663
    p = t = RARRAY_PTR(ary);
3664
    end = p + RARRAY_LEN(ary);
3665

    
3666
    while (t < end) {
3667
	if (NIL_P(*t)) t++;
3668
	else *p++ = *t++;
3669
    }
3670
    n = p - RARRAY_PTR(ary);
3671
    if (RARRAY_LEN(ary) == n) {
3672
	return Qnil;
3673
    }
3674
    ARY_SET_LEN(ary, n);
3675
    if (n * 2 < ARY_CAPA(ary) && ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
3676
	ary_resize_capa(ary, n * 2);
3677
    }
3678

    
3679
    return ary;
3680
}
3681

    
3682
/*
3683
 *  call-seq:
3684
 *     ary.compact     -> new_ary
3685
 *
3686
 *  Returns a copy of +self+ with all +nil+ elements removed.
3687
 *
3688
 *     [ "a", nil, "b", nil, "c", nil ].compact
3689
 *                       #=> [ "a", "b", "c" ]
3690
 */
3691

    
3692
static VALUE
3693
rb_ary_compact(VALUE ary)
3694
{
3695
    ary = rb_ary_dup(ary);
3696
    rb_ary_compact_bang(ary);
3697
    return ary;
3698
}
3699

    
3700
/*
3701
 *  call-seq:
3702
 *     ary.count      -> int
3703
 *     ary.count(obj) -> int
3704
 *     ary.count { |item| block }  -> int
3705
 *
3706
 *  Returns the number of elements.  If an argument is given, counts
3707
 *  the number of elements which equals to +obj+.  If a block is
3708
 *  given, counts the number of elements for which the block returns a true
3709
 *  value.
3710
 *
3711
 *     ary = [1, 2, 4, 2]
3712
 *     ary.count             #=> 4
3713
 *     ary.count(2)          #=> 2
3714
 *     ary.count{|x|x%2==0}  #=> 3
3715
 *
3716
 */
3717

    
3718
static VALUE
3719
rb_ary_count(int argc, VALUE *argv, VALUE ary)
3720
{
3721
    long n = 0;
3722

    
3723
    if (argc == 0) {
3724
	VALUE *p, *pend;
3725

    
3726
	if (!rb_block_given_p())
3727
	    return LONG2NUM(RARRAY_LEN(ary));
3728

    
3729
	for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
3730
	    if (RTEST(rb_yield(*p))) n++;
3731
	}
3732
    }
3733
    else {
3734
	VALUE obj, *p, *pend;
3735

    
3736
	rb_scan_args(argc, argv, "1", &obj);
3737
	if (rb_block_given_p()) {
3738
	    rb_warn("given block not used");
3739
	}
3740
	for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
3741
	    if (rb_equal(*p, obj)) n++;
3742
	}
3743
    }
3744

    
3745
    return LONG2NUM(n);
3746
}
3747

    
3748
static VALUE
3749
flatten(VALUE ary, int level, int *modified)
3750
{
3751
    long i = 0;
3752
    VALUE stack, result, tmp, elt;
3753
    st_table *memo;
3754
    st_data_t id;
3755

    
3756
    stack = ary_new(0, ARY_DEFAULT_SIZE);
3757
    result = ary_new(0, RARRAY_LEN(ary));
3758
    memo = st_init_numtable();
3759
    st_insert(memo, (st_data_t)ary, (st_data_t)Qtrue);
3760
    *modified = 0;
3761

    
3762
    while (1) {
3763
	while (i < RARRAY_LEN(ary)) {
3764
	    elt = RARRAY_PTR(ary)[i++];
3765
	    tmp = rb_check_array_type(elt);
3766
	    if (RBASIC(result)->klass) {
3767
		rb_raise(rb_eRuntimeError, "flatten reentered");
3768
	    }
3769
	    if (NIL_P(tmp) || (level >= 0 && RARRAY_LEN(stack) / 2 >= level)) {
3770
		rb_ary_push(result, elt);
3771
	    }
3772
	    else {
3773
		*modified = 1;
3774
		id = (st_data_t)tmp;
3775
		if (st_lookup(memo, id, 0)) {
3776
		    st_free_table(memo);
3777
		    rb_raise(rb_eArgError, "tried to flatten recursive array");
3778
		}
3779
		st_insert(memo, id, (st_data_t)Qtrue);
3780
		rb_ary_push(stack, ary);
3781
		rb_ary_push(stack, LONG2NUM(i));
3782
		ary = tmp;
3783
		i = 0;
3784
	    }
3785
	}
3786
	if (RARRAY_LEN(stack) == 0) {
3787
	    break;
3788
	}
3789
	id = (st_data_t)ary;
3790
	st_delete(memo, &id, 0);
3791
	tmp = rb_ary_pop(stack);
3792
	i = NUM2LONG(tmp);
3793
	ary = rb_ary_pop(stack);
3794
    }
3795

    
3796
    st_free_table(memo);
3797

    
3798
    RBASIC(result)->klass = rb_class_of(ary);
3799
    return result;
3800
}
3801

    
3802
/*
3803
 *  call-seq:
3804
 *     ary.flatten!        -> ary or nil
3805
 *     ary.flatten!(level) -> array or nil
3806
 *
3807
 *  Flattens +self+ in place.
3808
 *  Returns <code>nil</code> if no modifications were made (i.e.,
3809
 *  the array contains no subarrays.)  If the optional +level+
3810
 *  argument determines the level of recursion to flatten.
3811
 *
3812
 *     a = [ 1, 2, [3, [4, 5] ] ]
3813
 *     a.flatten!   #=> [1, 2, 3, 4, 5]
3814
 *     a.flatten!   #=> nil
3815
 *     a            #=> [1, 2, 3, 4, 5]
3816
 *     a = [ 1, 2, [3, [4, 5] ] ]
3817
 *     a.flatten!(1) #=> [1, 2, 3, [4, 5]]
3818
 */
3819

    
3820
static VALUE
3821
rb_ary_flatten_bang(int argc, VALUE *argv, VALUE ary)
3822
{
3823
    int mod = 0, level = -1;
3824
    VALUE result, lv;
3825

    
3826
    rb_scan_args(argc, argv, "01", &lv);
3827
    rb_ary_modify_check(ary);
3828
    if (!NIL_P(lv)) level = NUM2INT(lv);
3829
    if (level == 0) return Qnil;
3830

    
3831
    result = flatten(ary, level, &mod);
3832
    if (mod == 0) {
3833
	ary_discard(result);
3834
	return Qnil;
3835
    }
3836
    if (!(mod = ARY_EMBED_P(result))) rb_obj_freeze(result);
3837
    rb_ary_replace(ary, result);
3838
    if (mod) ARY_SET_EMBED_LEN(result, 0);
3839

    
3840
    return ary;
3841
}
3842

    
3843
/*
3844
 *  call-seq:
3845
 *     ary.flatten -> new_ary
3846
 *     ary.flatten(level) -> new_ary
3847
 *
3848
 *  Returns a new array that is a one-dimensional flattening of this
3849
 *  array (recursively). That is, for every element that is an array,
3850
 *  extract its elements into the new array.  If the optional
3851
 *  +level+ argument determines the level of recursion to flatten.
3852
 *
3853
 *     s = [ 1, 2, 3 ]           #=> [1, 2, 3]
3854
 *     t = [ 4, 5, 6, [7, 8] ]   #=> [4, 5, 6, [7, 8]]
3855
 *     a = [ s, t, 9, 10 ]       #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
3856
 *     a.flatten                 #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
3857
 *     a = [ 1, 2, [3, [4, 5] ] ]
3858
 *     a.flatten(1)              #=> [1, 2, 3, [4, 5]]
3859
 */
3860

    
3861
static VALUE
3862
rb_ary_flatten(int argc, VALUE *argv, VALUE ary)
3863
{
3864
    int mod = 0, level = -1;
3865
    VALUE result, lv;
3866

    
3867
    rb_scan_args(argc, argv, "01", &lv);
3868
    if (!NIL_P(lv)) level = NUM2INT(lv);
3869
    if (level == 0) return ary_make_shared_copy(ary);
3870

    
3871
    result = flatten(ary, level, &mod);
3872
    OBJ_INFECT(result, ary);
3873

    
3874
    return result;
3875
}
3876

    
3877
#define OPTHASH_GIVEN_P(opts) \
3878
    (argc > 0 && !NIL_P((opts) = rb_check_hash_type(argv[argc-1])) && (--argc, 1))
3879
static VALUE sym_random;
3880

    
3881
#define RAND_UPTO(max) (long)(rb_random_real(randgen)*(max))
3882

    
3883
/*
3884
 *  call-seq:
3885
 *     ary.shuffle!              -> ary
3886
 *     ary.shuffle!(random: rng) -> ary
3887
 *
3888
 *  Shuffles elements in +self+ in place.
3889
 *  If +rng+ is given, it will be used as the random number generator.
3890
 */
3891

    
3892
static VALUE
3893
rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
3894
{
3895
    VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
3896
    long i, snap_len;
3897

    
3898
    if (OPTHASH_GIVEN_P(opts)) {
3899
	randgen = rb_hash_lookup2(opts, sym_random, randgen);
3900
    }
3901
    rb_check_arity(argc, 0, 0);
3902
    rb_ary_modify(ary);
3903
    i = RARRAY_LEN(ary);
3904
    ptr = RARRAY_PTR(ary);
3905
    snap_len = i;
3906
    snap_ptr = ptr;
3907
    while (i) {
3908
	long j = RAND_UPTO(i);
3909
	VALUE tmp;
3910
	if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
3911
	    rb_raise(rb_eRuntimeError, "modified during shuffle");
3912
	}
3913
	tmp = ptr[--i];
3914
	ptr[i] = ptr[j];
3915
	ptr[j] = tmp;
3916
    }
3917
    return ary;
3918
}
3919

    
3920

    
3921
/*
3922
 *  call-seq:
3923
 *     ary.shuffle              -> new_ary
3924
 *     ary.shuffle(random: rng) -> new_ary
3925
 *
3926
 *  Returns a new array with elements of this array shuffled.
3927
 *
3928
 *     a = [ 1, 2, 3 ]           #=> [1, 2, 3]
3929
 *     a.shuffle                 #=> [2, 3, 1]
3930
 *
3931
 *  If +rng+ is given, it will be used as the random number generator.
3932
 *
3933
 *     a.shuffle(random: Random.new(1))  #=> [1, 3, 2]
3934
 */
3935

    
3936
static VALUE
3937
rb_ary_shuffle(int argc, VALUE *argv, VALUE ary)
3938
{
3939
    ary = rb_ary_dup(ary);
3940
    rb_ary_shuffle_bang(argc, argv, ary);
3941
    return ary;
3942
}
3943

    
3944

    
3945
/*
3946
 *  call-seq:
3947
 *     ary.sample                  -> obj
3948
 *     ary.sample(random: rng)     -> obj
3949
 *     ary.sample(n)               -> new_ary
3950
 *     ary.sample(n, random: rng)  -> new_ary
3951
 *
3952
 *  Choose a random element or +n+ random elements from the array. The elements
3953
 *  are chosen by using random and unique indices into the array in order to
3954
 *  ensure that an element doesn't repeat itself unless the array already
3955
 *  contained duplicate elements. If the array is empty the first form returns
3956
 *  <code>nil</code> and the second form returns an empty array.
3957
 *
3958
 *  If +rng+ is given, it will be used as the random number generator.
3959
 *
3960
 *     a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
3961
 *     a.sample         #=> 7
3962
 *     a.sample(4)      #=> [6, 4, 2, 5]
3963
 */
3964

    
3965

    
3966
static VALUE
3967
rb_ary_sample(int argc, VALUE *argv, VALUE ary)
3968
{
3969
    VALUE nv, result, *ptr;
3970
    VALUE opts, randgen = rb_cRandom;
3971
    long n, len, i, j, k, idx[10];
3972
    double rnds[numberof(idx)];
3973

    
3974
    if (OPTHASH_GIVEN_P(opts)) {
3975
	randgen = rb_hash_lookup2(opts, sym_random, randgen);
3976
    }
3977
    ptr = RARRAY_PTR(ary);
3978
    len = RARRAY_LEN(ary);
3979
    if (argc == 0) {
3980
	if (len == 0) return Qnil;
3981
	if (len == 1) {
3982
	    i = 0;
3983
	}
3984
	else {
3985
	    double x = rb_random_real(randgen);
3986
	    if ((len = RARRAY_LEN(ary)) == 0) return Qnil;
3987
	    i = (long)(x * len);
3988
	}
3989
	return RARRAY_PTR(ary)[i];
3990
    }
3991
    rb_scan_args(argc, argv, "1", &nv);
3992
    n = NUM2LONG(nv);
3993
    if (n < 0) rb_raise(rb_eArgError, "negative sample number");
3994
    if (n > len) n = len;
3995
    if (n <= numberof(idx)) {
3996
	for (i = 0; i < n; ++i) {
3997
	    rnds[i] = rb_random_real(randgen);
3998
	}
3999
    }
4000
    len = RARRAY_LEN(ary);
4001
    ptr = RARRAY_PTR(ary);
4002
    if (n > len) n = len;
4003
    switch (n) {
4004
      case 0:
4005
	return rb_ary_new2(0);
4006
      case 1:
4007
	i = (long)(rnds[0] * len);
4008
	return rb_ary_new4(1, &ptr[i]);
4009
      case 2:
4010
	i = (long)(rnds[0] * len);
4011
	j = (long)(rnds[1] * (len-1));
4012
	if (j >= i) j++;
4013
	return rb_ary_new3(2, ptr[i], ptr[j]);
4014
      case 3: