1

/**********************************************************************

2


3

array.c 

4


5

$Author$

6

created at: Fri Aug 6 09:46:12 JST 1993

7


8

Copyright (C) 19932007 Yukihiro Matsumoto

9

Copyright (C) 2000 Network Applied Communication Laboratory, Inc.

10

Copyright (C) 2000 Informationtechnology 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_SHAREDRARRAY_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_FLAGRARRAY_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

* callseq:

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

* callseq:

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

* callseq:

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

idxRARRAY_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

* callseq:

727

* ary << obj > ary

728

*

729

* AppendPushes 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

* callseq:

773

* ary.push(obj, ... ) > ary

774

*

775

* AppendPushes 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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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 ReferenceReturns 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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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{xx=="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

* callseq:

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

* callseq:

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 AssignmentSets 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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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("") #=> "abc"

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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)pos1);

2514

ARY_INCREASE_LEN(ary, 1);

2515


2516

return del;

2517

}

2518


2519

/*

2520

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

3009

* ary + other_ary > new_ary

3010

*

3011

* ConcatenationReturns 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

* callseq:

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

* callseq:

3056

* ary * int > new_ary

3057

* ary * str > new_string

3058

*

3059

* RepetitionWith 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, lent);

3107

}

3108

}

3109

out:

3110

OBJ_INFECT(ary2, ary);

3111


3112

return ary2;

3113

}

3114


3115

/*

3116

* callseq:

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

* callseq:

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

* callseq:

3195

* ary == other_ary > bool

3196

*

3197

* EqualityTwo 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

* callseq:

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

* callseq:

3274

* ary.hash > fixnum

3275

*

3276

* Compute a hashcode 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

* callseq:

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

* callseq:

3334

* ary <=> other_ary > 1, 0, +1 or nil

3335

*

3336

* ComparisonReturns 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 "elementwise" 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

* callseq:

3430

* ary  other_ary > new_ary

3431

*

3432

* Array DifferenceReturns 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 setlike 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

* callseq:

3460

* ary & other_ary > new_ary

3461

*

3462

* Set IntersectionReturns 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

* callseq:

3497

* ary  other_ary > new_ary

3498

*

3499

* Set UnionReturns 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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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

* callseq:

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{xx%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

* callseq:

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

* callseq:

3845

* ary.flatten > new_ary

3846

* ary.flatten(level) > new_ary

3847

*

3848

* Returns a new array that is a onedimensional 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[argc1])) && (argc, 1))

3879

static VALUE sym_random;

3880


3881

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

3882


3883

/*

3884

* callseq:

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

* callseq:

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

* callseq:

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] * (len1));

4012

if (j >= i) j++;

4013

return rb_ary_new3(2, ptr[i], ptr[j]);

4014

case 3:

