1. rb_mem_clear
2. memfill
3. rb_ary_modify_check
4. rb_ary_modify
5. rb_ary_freeze
6. rb_ary_frozen_p
7. rb_ary_s_alloc
8. ary_new
9. rb_ary_new2
10. rb_ary_new
11. rb_ary_new3
12. rb_ary_new4
13. rb_assoc_new
14. to_ary
15. rb_ary_initialize
16. rb_ary_s_create
17. rb_ary_store
18. rb_ary_push
19. rb_ary_push_m
20. rb_ary_pop
21. ary_make_shared
22. rb_ary_shift
23. rb_ary_unshift
24. rb_ary_unshift_m
25. rb_ary_entry
26. rb_ary_subseq
27. rb_ary_aref
28. rb_ary_at
29. rb_ary_first
30. rb_ary_last
31. rb_ary_fetch
32. rb_ary_index
33. rb_ary_rindex
34. rb_ary_indexes
35. rb_ary_to_ary
36. rb_ary_update
37. rb_ary_aset
38. rb_ary_insert
39. rb_ary_each
40. rb_ary_each_index
41. rb_ary_reverse_each
42. rb_ary_length
43. rb_ary_empty_p
44. rb_ary_dup
45. inspect_join
46. rb_ary_join
47. rb_ary_join_m
48. rb_ary_to_s
49. inspect_call
50. inspect_ensure
51. rb_protect_inspect
52. rb_inspecting_p
53. inspect_ary
54. rb_ary_inspect
55. rb_ary_to_a
56. rb_ary_reverse
57. rb_ary_reverse_bang
58. rb_ary_reverse_m
59. rb_cmpint
60. sort_1
61. sort_2
62. sort_internal
63. sort_unlock
64. rb_ary_sort_bang
65. rb_ary_sort
66. rb_ary_collect
67. rb_ary_collect_bang
68. rb_ary_select
69. rb_ary_delete
70. rb_ary_delete_at
71. rb_ary_delete_at_m
72. rb_ary_slice_bang
73. rb_ary_reject_bang
74. rb_ary_reject
75. rb_ary_delete_if
76. rb_ary_replace
77. rb_ary_clear
78. rb_ary_fill
79. rb_ary_plus
80. rb_ary_concat
81. rb_ary_times
82. rb_ary_assoc
83. rb_ary_rassoc
84. rb_ary_equal
85. rb_ary_eql
86. rb_ary_hash
87. rb_ary_includes
88. rb_ary_cmp
89. rb_ary_diff
90. ary_make_hash
91. rb_ary_and
92. rb_ary_or
93. rb_ary_uniq_bang
94. rb_ary_uniq
95. rb_ary_compact_bang
96. rb_ary_compact
97. rb_ary_nitems
98. flatten
99. rb_ary_flatten_bang
100. rb_ary_flatten
101. Init_Array

   1  /**********************************************************************
   2  
   3    array.c -
   4  
   5    $Author: matz $
   6    $Date: 2002/09/03 05:20:06 $
   7    created at: Fri Aug  6 09:46:12 JST 1993
   8  
   9    Copyright (C) 1993-2002 Yukihiro Matsumoto
  10    Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  11    Copyright (C) 2000  Information-technology Promotion Agency, Japan
  12  
  13  **********************************************************************/
  14  
  15  #include "ruby.h"
  16  #include "util.h"
  17  #include "st.h"
  18  
  19  VALUE rb_cArray;
  20  static ID id_cmp;
  21  
  22  #define ARY_DEFAULT_SIZE 16
  23  
  24  void
rb_mem_clear(mem, size)
  26      register VALUE *mem;
  27      register long size;
  28  {
  29      while (size--) {
  30          *mem++ = Qnil;
  31      }
  32  }
  33  
  34  static void
memfill(mem, size, val)
  36      register VALUE *mem;
  37      register long size;
  38      register VALUE val;
  39  {
  40      while (size--) {
  41          *mem++ = val;
  42      }
  43  }
  44  
  45  #define ARY_TMPLOCK  FL_USER1
  46  
  47  static void
rb_ary_modify_check(ary)
  49      VALUE ary;
  50  {
  51      if (OBJ_FROZEN(ary)) rb_error_frozen("array");
  52      if (FL_TEST(ary, ARY_TMPLOCK))
rb_raise(rb_eTypeError, "can't modify array during sort");
  54      if (!OBJ_TAINTED(ary) && rb_safe_level() >= 4)
rb_raise(rb_eSecurityError, "Insecure: can't modify array");
  56  }
  57  
  58  static void
rb_ary_modify(ary)
  60      VALUE ary;
  61  {
  62      VALUE *ptr;
  63  
rb_ary_modify_check(ary);
  65      if (FL_TEST(ary, ELTS_SHARED)) {
  66          ptr = ALLOC_N(VALUE, RARRAY(ary)->len);
FL_UNSET(ary, ELTS_SHARED);
RARRAY(ary)->aux.capa = RARRAY(ary)->len;
MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
RARRAY(ary)->ptr = ptr;
  71      }
  72  }
  73  VALUE
  74  rb_ary_freeze(ary)
  75      VALUE ary;
  76  {
  77      return rb_obj_freeze(ary);
  78  }
  79  
  80  static VALUE
  81  rb_ary_frozen_p(ary)
  82      VALUE ary;
  83  {
  84      if (FL_TEST(ary, FL_FREEZE|ARY_TMPLOCK))
  85          return Qtrue;
  86      return Qfalse;
  87  }
  88  
  89  static VALUE
  90  rb_ary_s_alloc(klass)
  91      VALUE klass;
  92  {
NEWOBJ(ary, struct RArray);
OBJSETUP(ary, klass, T_ARRAY);
  95  
  96      ary->len = 0;
  97      ary->ptr = 0;
  98      ary->aux.capa = 0;
  99  
 100      return (VALUE)ary;
 101  }
 102  
 103  static VALUE
ary_new(klass, len)
 105      VALUE klass;
 106      long len;
 107  {
 108      VALUE ary = rb_obj_alloc(klass);
 109  
 110      if (len < 0) {
rb_raise(rb_eArgError, "negative array size (or size too big)");
 112      }
 113      if (len > 0 && len * sizeof(VALUE) <= len) {
rb_raise(rb_eArgError, "array size too big");
 115      }
 116      if (len == 0) len++;
RARRAY(ary)->ptr = ALLOC_N(VALUE, len);
RARRAY(ary)->aux.capa = len;
 119  
 120      return ary;
 121  }
 122  
 123  VALUE
rb_ary_new2(len)
 125      long len;
 126  {
 127      return ary_new(rb_cArray, len);
 128  }
 129  
 130  
 131  VALUE
rb_ary_new()
 133  {
 134      return rb_ary_new2(ARY_DEFAULT_SIZE);
 135  }
 136  
 137  #ifdef HAVE_STDARG_PROTOTYPES
 138  #include <stdarg.h>
 139  #define va_init_list(a,b) va_start(a,b)
 140  #else
 141  #include <varargs.h>
 142  #define va_init_list(a,b) va_start(a)
 143  #endif
 144  
 145  VALUE
 146  #ifdef HAVE_STDARG_PROTOTYPES
rb_ary_new3(long n, ...)
 148  #else
 149  rb_ary_new3(n, va_alist)
 150      long n;
 151      va_dcl
 152  #endif
 153  {
 154      va_list ar;
 155      VALUE ary;
 156      long i;
 157  
 158      ary = rb_ary_new2(n);
 159  
va_init_list(ar, n);
 161      for (i=0; i<n; i++) {
RARRAY(ary)->ptr[i] = va_arg(ar, VALUE);
 163      }
 164      va_end(ar);
 165  
RARRAY(ary)->len = n;
 167      return ary;
 168  }
 169  
 170  VALUE
rb_ary_new4(n, elts)
 172      long n;
 173      const VALUE *elts;
 174  {
 175      VALUE ary;
 176  
 177      ary = rb_ary_new2(n);
 178      if (n > 0 && elts) {
MEMCPY(RARRAY(ary)->ptr, elts, VALUE, n);
 180      }
RARRAY(ary)->len = n;
 182  
 183      return ary;
 184  }
 185  
 186  VALUE
rb_assoc_new(car, cdr)
 188      VALUE car, cdr;
 189  {
 190      VALUE ary;
 191  
 192      ary = rb_ary_new2(2);
RARRAY(ary)->ptr[0] = car;
RARRAY(ary)->ptr[1] = cdr;
RARRAY(ary)->len = 2;
 196  
 197      return ary;
 198  }
 199  
 200  static VALUE
to_ary(ary)
 202      VALUE ary;
 203  {
 204      return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
 205  }
 206  
 207  static VALUE rb_ary_replace _((VALUE, VALUE));
 208  
 209  static VALUE
 210  rb_ary_initialize(argc, argv, ary)
 211      int argc;
 212      VALUE *argv;
 213      VALUE ary;
 214  {
 215      long len;
 216      VALUE size, val;
 217  
rb_ary_modify(ary);
 219      if (rb_scan_args(argc, argv, "02", &size, &val) == 0) {
RARRAY(ary)->len = 0;
 221          if (rb_block_given_p()) {
rb_warning("given block not used");
 223          }
 224          return ary;
 225      }
 226  
 227      if (argc == 1 && !FIXNUM_P(size)) {
 228          val = rb_check_convert_type(size, T_ARRAY, "Array", "to_ary");
 229          if (!NIL_P(val)) {
rb_ary_replace(ary, val);
 231              return ary;
 232          }
 233      }
 234  
 235      len = NUM2LONG(size);
 236      if (len < 0) {
rb_raise(rb_eArgError, "negative array size");
 238      }
 239      if (len > 0 && len * (long)sizeof(VALUE) <= len) {
rb_raise(rb_eArgError, "array size too big");
 241      }
 242      if (len > RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, len);
RARRAY(ary)->aux.capa = len;
 245      }
 246      if (rb_block_given_p()) {
 247          long i;
 248  
 249          if (argc > 1) {
rb_raise(rb_eArgError, "wrong number of arguments");
 251          }
 252          for (i=0; i<len; i++) {
RARRAY(ary)->ptr[i] = rb_yield(LONG2NUM(i));
RARRAY(ary)->len = i + 1;
 255          }
 256      }
 257      else {
memfill(RARRAY(ary)->ptr, len, val);
RARRAY(ary)->len = len;
 260      }
 261  
 262      return ary;
 263  }
 264  
 265  static VALUE
 266  rb_ary_s_create(argc, argv, klass)
 267      int argc;
 268      VALUE *argv;
 269      VALUE klass;
 270  {
 271      VALUE ary = rb_obj_alloc(klass);
 272  
 273      if (argc < 0) {
rb_raise(rb_eArgError, "negative number of arguments");
 275      }
 276      if (argc > 0) {
RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
 279      }
RARRAY(ary)->len = RARRAY(ary)->aux.capa = argc;
 281  
 282      return ary;
 283  }
 284  
 285  void
rb_ary_store(ary, idx, val)
 287      VALUE ary;
 288      long idx;
 289      VALUE val;
 290  {
rb_ary_modify(ary);
 292      if (idx < 0) {
 293          idx += RARRAY(ary)->len;
 294          if (idx < 0) {
rb_raise(rb_eIndexError, "index %ld out of array",
 296                      idx - RARRAY(ary)->len);
 297          }
 298      }
 299  
 300      if (idx >= RARRAY(ary)->aux.capa) {
 301          long new_capa = RARRAY(ary)->aux.capa / 2;
 302  
 303          if (new_capa < ARY_DEFAULT_SIZE) {
 304              new_capa = ARY_DEFAULT_SIZE;
 305          }
 306          new_capa += idx;
 307          if (new_capa * (long)sizeof(VALUE) <= new_capa) {
rb_raise(rb_eArgError, "index too big");
 309          }
REALLOC_N(RARRAY(ary)->ptr, VALUE, new_capa);
RARRAY(ary)->aux.capa = new_capa;
 312      }
 313      if (idx > RARRAY(ary)->len) {
rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len,
 315                       idx-RARRAY(ary)->len + 1);
 316      }
 317  
 318      if (idx >= RARRAY(ary)->len) {
RARRAY(ary)->len = idx + 1;
 320      }
RARRAY(ary)->ptr[idx] = val;
 322  }
 323  
 324  VALUE
rb_ary_push(ary, item)
 326      VALUE ary;
 327      VALUE item;
 328  {
rb_ary_store(ary, RARRAY(ary)->len, item);
 330      return ary;
 331  }
 332  
 333  static VALUE
 334  rb_ary_push_m(argc, argv, ary)
 335      int argc;
 336      VALUE *argv;
 337      VALUE ary;
 338  {
 339      if (argc <= 0) {
rb_raise(rb_eArgError, "wrong number arguments (at least 1)");
 341      }
 342      while (argc--) {
rb_ary_push(ary, *argv++);
 344      }
 345      return ary;
 346  }
 347  
 348  VALUE
rb_ary_pop(ary)
 350      VALUE ary;
 351  {
rb_ary_modify_check(ary);
 353      if (RARRAY(ary)->len == 0) return Qnil;
 354      if (!FL_TEST(ary, ELTS_SHARED) &&
RARRAY(ary)->len * 2 < RARRAY(ary)->aux.capa &&
RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
RARRAY(ary)->aux.capa = RARRAY(ary)->len * 2;
REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa);
 359      }
 360      return RARRAY(ary)->ptr[--RARRAY(ary)->len];
 361  }
 362  
 363  static void
ary_make_shared(ary)
 365      VALUE ary;
 366  {
 367      if (!FL_TEST(ary, ELTS_SHARED)) {
NEWOBJ(shared, struct RArray);
OBJSETUP(shared, rb_cArray, T_ARRAY);
 370  
 371          shared->len = RARRAY(ary)->len;
 372          shared->ptr = RARRAY(ary)->ptr;
 373          shared->aux.capa = RARRAY(ary)->aux.capa;
RARRAY(ary)->aux.shared = (VALUE)shared;
FL_SET(ary, ELTS_SHARED);
 376      }
 377  }
 378  
 379  VALUE
rb_ary_shift(ary)
 381      VALUE ary;
 382  {
 383      VALUE top;
 384  
rb_ary_modify_check(ary);
 386      if (RARRAY(ary)->len == 0) return Qnil;
 387      top = RARRAY(ary)->ptr[0];
ary_make_shared(ary);
RARRAY(ary)->ptr++;         /* shift ptr */
RARRAY(ary)->len--;
 391  
 392      return top;
 393  }
 394  
 395  VALUE
rb_ary_unshift(ary, item)
 397      VALUE ary, item;
 398  {
rb_ary_modify(ary);
 400      if (RARRAY(ary)->len == RARRAY(ary)->aux.capa) {
 401          long capa_inc = RARRAY(ary)->aux.capa / 2;
 402          if (capa_inc < ARY_DEFAULT_SIZE) {
 403              capa_inc = ARY_DEFAULT_SIZE;
 404          }
RARRAY(ary)->aux.capa += capa_inc;
REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa);
 407      }
 408  
 409      /* sliding items */
MEMMOVE(RARRAY(ary)->ptr + 1, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
 411  
RARRAY(ary)->len++;
RARRAY(ary)->ptr[0] = item;
 414  
 415      return ary;
 416  }
 417  
 418  static VALUE
 419  rb_ary_unshift_m(argc, argv, ary)
 420      int argc;
 421      VALUE *argv;
 422      VALUE ary;
 423  {
 424      long len = RARRAY(ary)->len;
 425      
 426      if (argc <= 0) {
rb_raise(rb_eArgError, "wrong number of arguments (at least 1)");
 428      }
 429  
 430      /* make rooms by setting the last item */
rb_ary_store(ary, len + argc - 1, Qnil);
 432  
 433      /* sliding items */
MEMMOVE(RARRAY(ary)->ptr + argc, RARRAY(ary)->ptr, VALUE, len);
MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
 436      
 437      return ary;
 438  }
 439  
 440  VALUE
rb_ary_entry(ary, offset)
 442      VALUE ary;
 443      long offset;
 444  {
 445      if (RARRAY(ary)->len == 0) return Qnil;
 446  
 447      if (offset < 0) {
 448          offset += RARRAY(ary)->len;
 449      }
 450      if (offset < 0 || RARRAY(ary)->len <= offset) {
 451          return Qnil;
 452      }
 453  
 454      return RARRAY(ary)->ptr[offset];
 455  }
 456  
 457  static VALUE
rb_ary_subseq(ary, beg, len)
 459      VALUE ary;
 460      long beg, len;
 461  {
 462      VALUE klass, ary2;
 463  
 464      if (beg > RARRAY(ary)->len) return Qnil;
 465      if (beg < 0 || len < 0) return Qnil;
 466  
 467      if (beg + len > RARRAY(ary)->len) {
 468          len = RARRAY(ary)->len - beg;
 469          if (len < 0)
 470              len = 0;
 471      }
 472      klass = rb_obj_class(ary);
 473      if (len == 0) return ary_new(klass, 0);
 474  
ary_make_shared(ary);
 476      ary2 = rb_obj_alloc(klass);
RARRAY(ary2)->ptr = RARRAY(ary)->ptr + beg;
RARRAY(ary2)->len = len;
RARRAY(ary2)->aux.shared = RARRAY(ary)->aux.shared;
FL_SET(ary2, ELTS_SHARED);
 481  
 482      return ary2;
 483  }
 484  
 485  VALUE
rb_ary_aref(argc, argv, ary)
 487      int argc;
 488      VALUE *argv;
 489      VALUE ary;
 490  {
 491      VALUE arg;
 492      long beg, len;
 493  
 494      if (argc == 2) {
 495          beg = NUM2LONG(argv[0]);
 496          len = NUM2LONG(argv[1]);
 497          if (beg < 0) {
 498              beg += RARRAY(ary)->len;
 499          }
 500          return rb_ary_subseq(ary, beg, len);
 501      }
 502      if (argc != 1) {
rb_scan_args(argc, argv, "11", 0, 0);
 504      }
 505      arg = argv[0];
 506      /* special case - speeding up */
 507      if (FIXNUM_P(arg)) {
 508          return rb_ary_entry(ary, FIX2LONG(arg));
 509      }
 510      /* check if idx is Range */
 511      switch (rb_range_beg_len(arg, &beg, &len, RARRAY(ary)->len, 0)) {
 512        case Qfalse:
 513          break;
 514        case Qnil:
 515          return Qnil;
 516        default:
 517          return rb_ary_subseq(ary, beg, len);
 518      }
 519      return rb_ary_entry(ary, NUM2LONG(arg));
 520  }
 521  
 522  static VALUE
 523  rb_ary_at(ary, pos)
 524      VALUE ary, pos;
 525  {
 526      return rb_ary_entry(ary, NUM2LONG(pos));
 527  }
 528  
 529  static VALUE
 530  rb_ary_first(ary)
 531      VALUE ary;
 532  {
 533      if (RARRAY(ary)->len == 0) return Qnil;
 534      return RARRAY(ary)->ptr[0];
 535  }
 536  
 537  static VALUE
 538  rb_ary_last(ary)
 539      VALUE ary;
 540  {
 541      if (RARRAY(ary)->len == 0) return Qnil;
 542      return RARRAY(ary)->ptr[RARRAY(ary)->len-1];
 543  }
 544  
 545  static VALUE
 546  rb_ary_fetch(argc, argv, ary)
 547      int argc;
 548      VALUE *argv;
 549      VALUE ary;
 550  {
 551      VALUE pos, ifnone;
 552      long idx;
 553  
rb_scan_args(argc, argv, "11", &pos, &ifnone);
 555      idx = NUM2LONG(pos);
 556  
 557      if (idx < 0) {
 558          idx +=  RARRAY(ary)->len;
 559      }
 560      if (idx < 0 || RARRAY(ary)->len <= idx) {
 561          if (rb_block_given_p()) {
 562              if (argc > 1) {
rb_raise(rb_eArgError, "wrong number of arguments");
 564              }
 565              return rb_yield(pos);
 566          }
 567          if (argc == 1) {
rb_raise(rb_eIndexError, "index %ld out of array", idx);
 569          }
 570          return ifnone;
 571      }
 572      return RARRAY(ary)->ptr[idx];
 573  }
 574  
 575  static VALUE
 576  rb_ary_index(ary, val)
 577      VALUE ary;
 578      VALUE val;
 579  {
 580      long i;
 581  
 582      for (i=0; i<RARRAY(ary)->len; i++) {
 583          if (rb_equal(RARRAY(ary)->ptr[i], val))
 584              return LONG2NUM(i);
 585      }
 586      return Qnil;
 587  }
 588  
 589  static VALUE
 590  rb_ary_rindex(ary, val)
 591      VALUE ary;
 592      VALUE val;
 593  {
 594      long i = RARRAY(ary)->len;
 595  
 596      while (i--) {
 597          if (rb_equal(RARRAY(ary)->ptr[i], val))
 598              return LONG2NUM(i);
 599      }
 600      return Qnil;
 601  }
 602  
 603  static VALUE
 604  rb_ary_indexes(argc, argv, ary)
 605      int argc;
 606      VALUE *argv;
 607      VALUE ary;
 608  {
 609      VALUE new_ary;
 610      long i;
 611  
rb_warn("Array#%s is deprecated; use Array#select",
rb_id2name(rb_frame_last_func()));
 614      new_ary = rb_ary_new2(argc);
 615      for (i=0; i<argc; i++) {
rb_ary_push(new_ary, rb_ary_aref(1, argv+i, ary));
 617      }
 618  
 619      return new_ary;
 620  }
 621  
 622  VALUE
rb_ary_to_ary(obj)
 624      VALUE obj;
 625  {
 626      if (NIL_P(obj)) return rb_ary_new2(0);
 627      if (TYPE(obj) == T_ARRAY) {
 628          return obj;
 629      }
 630      if (rb_respond_to(obj, rb_intern("to_ary"))) {
 631          return rb_convert_type(obj, T_ARRAY, "Array", "to_ary");
 632      }
 633      return rb_ary_new3(1, obj);
 634  }
 635  
 636  static void
rb_ary_update(ary, beg, len, rpl)
 638      VALUE ary;
 639      long beg, len;
 640      VALUE rpl;
 641  {
 642      long rlen;
 643  
 644      rpl = rb_ary_to_ary(rpl);
 645      rlen = RARRAY(rpl)->len;
 646  
 647      if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
 648      if (beg < 0) {
 649          beg += RARRAY(ary)->len;
 650          if (beg < 0) {
 651              beg -= RARRAY(ary)->len;
rb_raise(rb_eIndexError, "index %ld out of array", beg);
 653          }
 654      }
 655      if (beg + len > RARRAY(ary)->len) {
 656          len = RARRAY(ary)->len - beg;
 657      }
 658  
rb_ary_modify(ary);
 660      if (beg >= RARRAY(ary)->len) {
 661          len = beg + rlen;
 662          if (len >= RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, len);
RARRAY(ary)->aux.capa = len;
 665          }
rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, beg - RARRAY(ary)->len);
MEMCPY(RARRAY(ary)->ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen);
RARRAY(ary)->len = len;
 669      }
 670      else {
 671          long alen;
 672  
 673          if (beg + len > RARRAY(ary)->len) {
 674              len = RARRAY(ary)->len - beg;
 675          }
 676  
 677          alen = RARRAY(ary)->len + rlen - len;
 678          if (alen >= RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, alen);
RARRAY(ary)->aux.capa = alen;
 681          }
 682  
 683          if (len != rlen) {
MEMMOVE(RARRAY(ary)->ptr + beg + rlen, RARRAY(ary)->ptr + beg + len,
 685                      VALUE, RARRAY(ary)->len - (beg + len));
RARRAY(ary)->len = alen;
 687          }
MEMMOVE(RARRAY(ary)->ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen);
 689      }
 690  }
 691  
 692  static VALUE
 693  rb_ary_aset(argc, argv, ary)
 694      int argc;
 695      VALUE *argv;
 696      VALUE ary;
 697  {
 698      long offset, beg, len;
 699  
 700      if (argc == 3) {
rb_ary_update(ary, NUM2LONG(argv[0]), NUM2LONG(argv[1]), argv[2]);
 702          return argv[2];
 703      }
 704      if (argc != 2) {
rb_raise(rb_eArgError, "wrong number of arguments (%d for 2)", argc);
 706      }
 707      if (FIXNUM_P(argv[0])) {
 708          offset = FIX2LONG(argv[0]);
 709          goto fixnum;
 710      }
 711      if (rb_range_beg_len(argv[0], &beg, &len, RARRAY(ary)->len, 1)) {
 712          /* check if idx is Range */
rb_ary_update(ary, beg, len, argv[1]);
 714          return argv[1];
 715      }
 716  
 717      offset = NUM2LONG(argv[0]);
 718  fixnum:
rb_ary_store(ary, offset, argv[1]);
 720      return argv[1];
 721  }
 722  
 723  static VALUE
 724  rb_ary_insert(argc, argv, ary)
 725      int argc;
 726      VALUE *argv;
 727      VALUE ary;
 728  {
 729      long pos;
 730  
 731      if (argc < 2) {
rb_raise(rb_eArgError, "wrong number of arguments (at least 2)");
 733      }
 734      pos = NUM2LONG(argv[0]);
 735      if (pos == -1) {
 736          pos = RARRAY(ary)->len;
 737      }
 738      else if (pos < 0) {
 739          pos++;
 740      }
 741  
rb_ary_update(ary, pos, 0, rb_ary_new4(argc - 1, argv + 1));
 743      return ary;
 744  }
 745  
 746  VALUE
 747  rb_ary_each(ary)
 748      VALUE ary;
 749  {
 750      long i;
 751  
 752      for (i=0; i<RARRAY(ary)->len; i++) {
rb_yield(RARRAY(ary)->ptr[i]);
 754      }
 755      return ary;
 756  }
 757  
 758  static VALUE
 759  rb_ary_each_index(ary)
 760      VALUE ary;
 761  {
 762      long i;
 763  
 764      for (i=0; i<RARRAY(ary)->len; i++) {
rb_yield(LONG2NUM(i));
 766      }
 767      return ary;
 768  }
 769  
 770  static VALUE
 771  rb_ary_reverse_each(ary)
 772      VALUE ary;
 773  {
 774      long len = RARRAY(ary)->len;
 775  
 776      while (len--) {
rb_yield(RARRAY(ary)->ptr[len]);
 778      }
 779      return ary;
 780  }
 781  
 782  static VALUE
 783  rb_ary_length(ary)
 784      VALUE ary;
 785  {
 786      return LONG2NUM(RARRAY(ary)->len);
 787  }
 788  
 789  static VALUE
 790  rb_ary_empty_p(ary)
 791      VALUE ary;
 792  {
 793      if (RARRAY(ary)->len == 0)
 794          return Qtrue;
 795      return Qfalse;
 796  }
 797  
 798  VALUE
rb_ary_dup(ary)
 800      VALUE ary;
 801  {
 802      VALUE dup = rb_ary_new2(RARRAY(ary)->len);
 803  
DUPSETUP(dup, ary);
MEMCPY(RARRAY(dup)->ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
RARRAY(dup)->len = RARRAY(ary)->len;
 807      return dup;
 808  }
 809  
 810  extern VALUE rb_output_fs;
 811  
 812  static VALUE
 813  inspect_join(ary, arg)
 814      VALUE ary;
 815      VALUE *arg;
 816  {
 817      return rb_ary_join(arg[0], arg[1]);
 818  }
 819  
 820  VALUE
rb_ary_join(ary, sep)
 822      VALUE ary, sep;
 823  {
 824      long len = 1, i;
 825      int taint = Qfalse;
 826      VALUE result, tmp;
 827  
 828      if (RARRAY(ary)->len == 0) return rb_str_new(0, 0);
 829      if (OBJ_TAINTED(ary) || OBJ_TAINTED(sep)) taint = Qtrue;
 830  
 831      for (i=0; i<RARRAY(ary)->len; i++) {
 832          if (TYPE(RARRAY(ary)->ptr[i]) == T_STRING) {
 833              len += RSTRING(RARRAY(ary)->ptr[i])->len;
 834          }
 835          else {
 836              len += 10;
 837          }
 838      }
 839      if (!NIL_P(sep)) {
StringValue(sep);
 841          len += RSTRING(sep)->len * (RARRAY(ary)->len - 1);
 842      }
 843      result = rb_str_buf_new(len);
 844      for (i=0; i<RARRAY(ary)->len; i++) {
 845          tmp = RARRAY(ary)->ptr[i];
 846          switch (TYPE(tmp)) {
 847            case T_STRING:
 848              break;
 849            case T_ARRAY:
 850              if (rb_inspecting_p(tmp)) {
 851                  tmp = rb_str_new2("[...]");
 852              }
 853              else {
 854                  VALUE args[2];
 855  
 856                  args[0] = tmp;
 857                  args[1] = sep;
 858                  tmp = rb_protect_inspect(inspect_join, ary, (VALUE)args);
 859              }
 860              break;
 861            default:
 862              tmp = rb_obj_as_string(tmp);
 863          }
 864          if (i > 0 && !NIL_P(sep))
rb_str_buf_append(result, sep);
rb_str_buf_append(result, tmp);
 867          if (OBJ_TAINTED(tmp)) taint = Qtrue;
 868      }
 869  
 870      if (taint) OBJ_TAINT(result);
 871      return result;
 872  }
 873  
 874  static VALUE
 875  rb_ary_join_m(argc, argv, ary)
 876      int argc;
 877      VALUE *argv;
 878      VALUE ary;
 879  {
 880      VALUE sep;
 881  
rb_scan_args(argc, argv, "01", &sep);
 883      if (NIL_P(sep)) sep = rb_output_fs;
 884      
 885      return rb_ary_join(ary, sep);
 886  }
 887  
 888  VALUE
rb_ary_to_s(ary)
 890      VALUE ary;
 891  {
 892      if (RARRAY(ary)->len == 0) return rb_str_new(0, 0);
 893      
 894      return rb_ary_join(ary, rb_output_fs);
 895  }
 896  
 897  static ID inspect_key;
 898  
 899  struct inspect_arg {
 900      VALUE (*func)();
 901      VALUE arg1, arg2;
 902  };
 903  
 904  static VALUE
 905  inspect_call(arg)
 906      struct inspect_arg *arg;
 907  {
 908      return (*arg->func)(arg->arg1, arg->arg2);
 909  }
 910  
 911  static VALUE
 912  inspect_ensure(obj)
 913      VALUE obj;
 914  {
 915      VALUE inspect_tbl;
 916  
 917      inspect_tbl = rb_thread_local_aref(rb_thread_current(), inspect_key);
rb_ary_pop(inspect_tbl);
 919      return 0;
 920  }
 921  
 922  VALUE
rb_protect_inspect(func, obj, arg)
 924      VALUE (*func)(ANYARGS);
 925      VALUE obj, arg;
 926  {
 927      struct inspect_arg iarg;
 928      VALUE inspect_tbl;
 929      VALUE id;
 930  
 931      inspect_tbl = rb_thread_local_aref(rb_thread_current(), inspect_key);
 932      if (NIL_P(inspect_tbl)) {
 933          inspect_tbl = rb_ary_new();
rb_thread_local_aset(rb_thread_current(), inspect_key, inspect_tbl);
 935      }
 936      id = rb_obj_id(obj);
 937      if (rb_ary_includes(inspect_tbl, id)) {
 938          return (*func)(obj, arg);
 939      }
rb_ary_push(inspect_tbl, id);
 941      iarg.func = func;
 942      iarg.arg1 = obj;
 943      iarg.arg2 = arg;
 944  
 945      return rb_ensure(inspect_call, (VALUE)&iarg, inspect_ensure, obj);
 946  }
 947  
 948  VALUE
rb_inspecting_p(obj)
 950      VALUE obj;
 951  {
 952      VALUE inspect_tbl;
 953  
 954      inspect_tbl = rb_thread_local_aref(rb_thread_current(), inspect_key);
 955      if (NIL_P(inspect_tbl)) return Qfalse;
 956      return rb_ary_includes(inspect_tbl, rb_obj_id(obj));
 957  }
 958  
 959  static VALUE
 960  inspect_ary(ary)
 961      VALUE ary;
 962  {
 963      int tainted = OBJ_TAINTED(ary);
 964      long i;
 965      VALUE s, str;
 966  
 967      str = rb_str_buf_new2("[");
 968      for (i=0; i<RARRAY(ary)->len; i++) {
 969          s = rb_inspect(RARRAY(ary)->ptr[i]);
 970          if (OBJ_TAINTED(s)) tainted = Qtrue;
 971          if (i > 0) rb_str_buf_cat2(str, ", ");
rb_str_buf_append(str, s);
 973      }
rb_str_buf_cat2(str, "]");
 975      if (tainted) OBJ_TAINT(str);
 976      return str;
 977  }
 978  
 979  static VALUE
 980  rb_ary_inspect(ary)
 981      VALUE ary;
 982  {
 983      if (RARRAY(ary)->len == 0) return rb_str_new2("[]");
 984      if (rb_inspecting_p(ary)) return rb_str_new2("[...]");
 985      return rb_protect_inspect(inspect_ary, ary, 0);
 986  }
 987  
 988  static VALUE
 989  rb_ary_to_a(ary)
 990      VALUE ary;
 991  {
 992      return ary;
 993  }
 994  
 995  VALUE
rb_ary_reverse(ary)
 997      VALUE ary;
 998  {
 999      VALUE *p1, *p2;
1000      VALUE tmp;
1001  
rb_ary_modify(ary);
1003      if (RARRAY(ary)->len <= 1) return ary;
1004  
1005      p1 = RARRAY(ary)->ptr;
1006      p2 = p1 + RARRAY(ary)->len - 1;     /* points last item */
1007  
1008      while (p1 < p2) {
1009          tmp = *p1;
1010          *p1++ = *p2;
1011          *p2-- = tmp;
1012      }
1013  
1014      return ary;
1015  }
1016  
1017  static VALUE
1018  rb_ary_reverse_bang(ary)
1019      VALUE ary;
1020  {
1021      if (RARRAY(ary)->len <= 1) return Qnil;
1022      return rb_ary_reverse(ary);
1023  }
1024  
1025  static VALUE
1026  rb_ary_reverse_m(ary)
1027      VALUE ary;
1028  {
1029      return rb_ary_reverse(rb_ary_dup(ary));
1030  }
1031  
1032  int
rb_cmpint(cmp)
1034      VALUE cmp;
1035  {
1036      if (FIXNUM_P(cmp)) return FIX2INT(cmp);
1037      if (TYPE(cmp) == T_BIGNUM) {
1038          if (RBIGNUM(cmp)->sign) return 1;
1039          return -1;
1040      }
1041      if (RTEST(rb_funcall(cmp, '>', 1, INT2FIX(0)))) return 1;
1042      if (RTEST(rb_funcall(cmp, '<', 1, INT2FIX(0)))) return -1;
1043      return 0;
1044  }
1045  
1046  static int
1047  sort_1(a, b)
1048      VALUE *a, *b;
1049  {
1050      VALUE retval = rb_yield(rb_assoc_new(*a, *b));
1051      return rb_cmpint(retval);
1052  }
1053  
1054  static int
1055  sort_2(ap, bp)
1056      VALUE *ap, *bp;
1057  {
1058      VALUE retval;
1059      long a = (long)*ap, b = (long)*bp;
1060  
1061      if (FIXNUM_P(a) && FIXNUM_P(b)) {
1062          if (a > b) return 1;
1063          if (a < b) return -1;
1064          return 0;
1065      }
1066      if (TYPE(a) == T_STRING && TYPE(b) == T_STRING) {
1067          return rb_str_cmp(a, b);
1068      }
1069  
1070      retval = rb_funcall(a, id_cmp, 1, b);
1071      return rb_cmpint(retval);
1072  }
1073  
1074  static VALUE
1075  sort_internal(ary)
1076      VALUE ary;
1077  {
qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE),
rb_block_given_p()?sort_1:sort_2);
1080      return ary;
1081  }
1082  
1083  static VALUE
1084  sort_unlock(ary)
1085      VALUE ary;
1086  {
FL_UNSET(ary, ARY_TMPLOCK);
1088      return ary;
1089  }
1090  
1091  VALUE
rb_ary_sort_bang(ary)
1093      VALUE ary;
1094  {
rb_ary_modify(ary);
1096      if (RARRAY(ary)->len <= 1) return ary;
1097  
FL_SET(ary, ARY_TMPLOCK);   /* prohibit modification during sort */
rb_ensure(sort_internal, ary, sort_unlock, ary);
1100      return ary;
1101  }
1102  
1103  VALUE
rb_ary_sort(ary)
1105      VALUE ary;
1106  {
1107      ary = rb_ary_dup(ary);
rb_ary_sort_bang(ary);
1109      return ary;
1110  }
1111  
1112  static VALUE
1113  rb_ary_collect(ary)
1114      VALUE ary;
1115  {
1116      long len, i;
1117      VALUE collect;
1118  
1119      if (!rb_block_given_p()) {
1120          return rb_ary_new4(RARRAY(ary)->len, RARRAY(ary)->ptr);
1121      }
1122  
1123      len = RARRAY(ary)->len;
1124      collect = rb_ary_new2(len);
1125      for (i=0; i<len; i++) {
rb_ary_push(collect, rb_yield(RARRAY(ary)->ptr[i]));
1127      }
1128      return collect;
1129  }
1130  
1131  static VALUE
1132  rb_ary_collect_bang(ary)
1133      VALUE ary;
1134  {
1135      long i;
1136  
rb_ary_modify(ary);
1138      for (i = 0; i < RARRAY(ary)->len; i++) {
RARRAY(ary)->ptr[i] = rb_yield(RARRAY(ary)->ptr[i]);
1140      }
1141      return ary;
1142  }
1143  
1144  static VALUE
1145  rb_ary_select(argc, argv, ary)
1146      int argc;
1147      VALUE *argv;
1148      VALUE ary;
1149  {
1150      VALUE result;
1151      long i;
1152  
1153      if (rb_block_given_p()) {
1154          if (argc > 0) {
rb_raise(rb_eArgError, "wrong number arguments (%d for 0)", argc);
1156          }
1157          result = rb_ary_new2(RARRAY(ary)->len);
1158          for (i = 0; i < RARRAY(ary)->len; i++) {
1159              if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
rb_ary_push(result, RARRAY(ary)->ptr[i]);
1161              }
1162          }
1163      }
1164      else {
1165          result = rb_ary_new2(argc);
1166          for (i=0; i<argc; i++) {
rb_ary_push(result, rb_ary_entry(ary, NUM2LONG(argv[i])));
1168          }
1169      }
1170      return result;
1171  }
1172  
1173  VALUE
rb_ary_delete(ary, item)
1175      VALUE ary;
1176      VALUE item;
1177  {
1178      long i1, i2;
1179  
rb_ary_modify(ary);
1181      for (i1 = i2 = 0; i1 < RARRAY(ary)->len; i1++) {
1182          if (rb_equal(RARRAY(ary)->ptr[i1], item)) continue;
1183          if (i1 != i2) {
RARRAY(ary)->ptr[i2] = RARRAY(ary)->ptr[i1];
1185          }
1186          i2++;
1187      }
1188      if (RARRAY(ary)->len == i2) {
1189          if (rb_block_given_p()) {
1190              return rb_yield(item);
1191          }
1192          return Qnil;
1193      }
1194  
RARRAY(ary)->len = i2;
1196      if (i2 * 2 < RARRAY(ary)->aux.capa &&
RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, i2 * 2);
RARRAY(ary)->aux.capa = i2 * 2;
1200      }
1201  
1202      return item;
1203  }
1204  
1205  VALUE
rb_ary_delete_at(ary, pos)
1207      VALUE ary;
1208      long pos;
1209  {
1210      long i, len = RARRAY(ary)->len;
1211      VALUE del;
1212  
rb_ary_modify(ary);
1214      if (pos >= len) return Qnil;
1215      if (pos < 0) {
1216          pos += len;
1217          if (pos < 0) return Qnil;
1218      }
1219  
1220      del = RARRAY(ary)->ptr[pos];
1221      for (i = pos + 1; i < len; i++, pos++) {
RARRAY(ary)->ptr[pos] = RARRAY(ary)->ptr[i];
1223      }
RARRAY(ary)->len = pos;
1225  
1226      return del;
1227  }
1228  
1229  static VALUE
1230  rb_ary_delete_at_m(ary, pos)
1231      VALUE ary, pos;
1232  {
1233      return rb_ary_delete_at(ary, NUM2LONG(pos));
1234  }
1235  
1236  static VALUE
1237  rb_ary_slice_bang(argc, argv, ary)
1238      int argc;
1239      VALUE *argv;
1240      VALUE ary;
1241  {
1242      VALUE arg1, arg2;
1243      long pos, len;
1244  
rb_ary_modify(ary);
1246      if (rb_scan_args(argc, argv, "11", &arg1, &arg2) == 2) {
1247          pos = NUM2LONG(arg1);
1248          len = NUM2LONG(arg2);
1249        delete_pos_len:
1250          if (pos < 0) {
1251              pos = RARRAY(ary)->len + pos;
1252          }
1253          arg2 = rb_ary_subseq(ary, pos, len);
rb_ary_update(ary, pos, len, Qnil);     /* Qnil/rb_ary_new2(0) */
1255          return arg2;
1256      }
1257  
1258      if (!FIXNUM_P(arg1) && rb_range_beg_len(arg1, &pos, &len, RARRAY(ary)->len, 1)) {
1259          goto delete_pos_len;
1260      }
1261  
1262      return rb_ary_delete_at(ary, NUM2LONG(arg1));
1263  }
1264  
1265  static VALUE
rb_ary_reject_bang(ary)
1267      VALUE ary;
1268  {
1269      long i1, i2;
1270  
rb_ary_modify(ary);
1272      for (i1 = i2 = 0; i1 < RARRAY(ary)->len; i1++) {
1273          if (RTEST(rb_yield(RARRAY(ary)->ptr[i1]))) continue;
1274          if (i1 != i2) {
RARRAY(ary)->ptr[i2] = RARRAY(ary)->ptr[i1];
1276          }
1277          i2++;
1278      }
1279      if (RARRAY(ary)->len == i2) return Qnil;
RARRAY(ary)->len = i2;
1281  
1282      return ary;
1283  }
1284  
1285  static VALUE
1286  rb_ary_reject(ary)
1287      VALUE ary;
1288  {
1289      ary = rb_ary_dup(ary);
rb_ary_reject_bang(ary);
1291      return ary;
1292  }
1293  
1294  static VALUE
1295  rb_ary_delete_if(ary)
1296      VALUE ary;
1297  {
rb_ary_reject_bang(ary);
1299      return ary;
1300  }
1301  
1302  static VALUE
rb_ary_replace(copy, orig)
1304      VALUE copy, orig;
1305  {
rb_ary_modify(copy);
1307      orig = to_ary(orig);
1308      if (copy == orig) return copy;
ary_make_shared(orig);
1310      if (RARRAY(copy)->ptr && !FL_TEST(copy, ELTS_SHARED))
1311          free(RARRAY(copy)->ptr);
RARRAY(copy)->ptr = RARRAY(orig)->ptr;
RARRAY(copy)->len = RARRAY(orig)->len;
RARRAY(copy)->aux.shared = RARRAY(orig)->aux.shared;
FL_SET(copy, ELTS_SHARED);
1316  
1317      return copy;
1318  }
1319  
1320  VALUE
rb_ary_clear(ary)
1322      VALUE ary;
1323  {
rb_ary_modify(ary);
RARRAY(ary)->len = 0;
1326      if (ARY_DEFAULT_SIZE * 2 < RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, ARY_DEFAULT_SIZE * 2);
RARRAY(ary)->aux.capa = ARY_DEFAULT_SIZE * 2;
1329      }
1330      return ary;
1331  }
1332  
1333  static VALUE
1334  rb_ary_fill(argc, argv, ary)
1335      int argc;
1336      VALUE *argv;
1337      VALUE ary;
1338  {
1339      VALUE item, arg1, arg2;
1340      long beg, end, len;
1341      VALUE *p, *pend;
1342      int block_p = Qfalse;
1343  
1344      if (rb_block_given_p()) {
1345          block_p = Qtrue;
rb_scan_args(argc, argv, "02", &arg1, &arg2);
1347          argc += 1;              /* hackish */
1348      }
1349      else {
rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
1351      }
1352      switch (argc) {
1353        case 1:
1354          beg = 0;
1355          len = RARRAY(ary)->len;
1356          break;
1357        case 2:
1358          if (rb_range_beg_len(arg1, &beg, &len, RARRAY(ary)->len, 1)) {
1359              break;
1360          }
1361          /* fall through */
1362        case 3:
1363          beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
1364          if (beg < 0) {
1365              beg = RARRAY(ary)->len + beg;
1366              if (beg < 0) beg = 0;
1367          }
1368          len = NIL_P(arg2) ? RARRAY(ary)->len - beg : NUM2LONG(arg2);
1369          break;
1370      }
rb_ary_modify(ary);
1372      end = beg + len;
1373      if (end > RARRAY(ary)->len) {
1374          if (end >= RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, end);
RARRAY(ary)->aux.capa = end;
1377          }
1378          if (beg > RARRAY(ary)->len) {
rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, end - RARRAY(ary)->len);
1380          }
RARRAY(ary)->len = end;
1382      }
1383      p = RARRAY(ary)->ptr + beg;
1384      pend = p + len;
1385  
1386      if (block_p) {
1387          while (p < pend) {
1388              *p++ = rb_yield(LONG2NUM(beg++));
1389          }
1390      }
1391      else {
1392          while (p < pend) {
1393              *p++ = item;
1394          }
1395      }
1396      return ary;
1397  }
1398  
1399  VALUE
1400  rb_ary_plus(x, y)
1401      VALUE x, y;
1402  {
1403      VALUE z;
1404      long len;
1405  
1406      y = to_ary(y);
1407      len = RARRAY(x)->len + RARRAY(y)->len;
1408      z = rb_ary_new2(len);
MEMCPY(RARRAY(z)->ptr, RARRAY(x)->ptr, VALUE, RARRAY(x)->len);
MEMCPY(RARRAY(z)->ptr + RARRAY(x)->len, RARRAY(y)->ptr, VALUE, RARRAY(y)->len);
RARRAY(z)->len = len;
1412      return z;
1413  }
1414  
1415  VALUE
rb_ary_concat(x, y)
1417      VALUE x, y;
1418  {
1419      y = to_ary(y);
1420      if (RARRAY(y)->len > 0) {
rb_ary_update(x, RARRAY(x)->len, 0, y);
1422      }
1423      return x;
1424  }
1425  
1426  static VALUE
1427  rb_ary_times(ary, times)
1428      VALUE ary, times;
1429  {
1430      VALUE ary2;
1431      long i, len;
1432  
1433      if (TYPE(times) == T_STRING) {
1434          return rb_ary_join(ary, times);
1435      }
1436  
1437      len = NUM2LONG(times);
1438      if (len < 0) {
rb_raise(rb_eArgError, "negative argument");
1440      }
1441      len *= RARRAY(ary)->len;
1442  
1443      ary2 = ary_new(rb_obj_class(ary), len);
RARRAY(ary2)->len = len;
1445  
1446      for (i=0; i<len; i+=RARRAY(ary)->len) {
MEMCPY(RARRAY(ary2)->ptr+i, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
1448      }
OBJ_INFECT(ary2, ary);
1450  
1451      return ary2;
1452  }
1453  
1454  VALUE
1455  rb_ary_assoc(ary, key)
1456      VALUE ary, key;
1457  {
1458      VALUE *p, *pend;
1459  
1460      p = RARRAY(ary)->ptr;
1461      pend = p + RARRAY(ary)->len;
1462      
1463      while (p < pend) {
1464          if (TYPE(*p) == T_ARRAY &&
RARRAY(*p)->len > 0 &&
rb_equal(RARRAY(*p)->ptr[0], key))
1467              return *p;
1468          p++;
1469      }
1470      return Qnil;
1471  }
1472  
1473  VALUE
1474  rb_ary_rassoc(ary, value)
1475      VALUE ary, value;
1476  {
1477      VALUE *p, *pend;
1478  
1479      p = RARRAY(ary)->ptr;
1480      pend = p + RARRAY(ary)->len;
1481  
1482      while (p < pend) {
1483          if (TYPE(*p) == T_ARRAY
1484              && RARRAY(*p)->len > 1
1485              && rb_equal(RARRAY(*p)->ptr[1], value))
1486              return *p;
1487          p++;
1488      }
1489      return Qnil;
1490  }
1491  
1492  static VALUE
1493  rb_ary_equal(ary1, ary2)
1494      VALUE ary1, ary2;
1495  {
1496      long i;
1497  
1498      if (ary1 == ary2) return Qtrue;
1499      if (TYPE(ary2) != T_ARRAY) return Qfalse;
1500      if (RARRAY(ary1)->len != RARRAY(ary2)->len) return Qfalse;
1501      for (i=0; i<RARRAY(ary1)->len; i++) {
1502          if (!rb_equal(RARRAY(ary1)->ptr[i], RARRAY(ary2)->ptr[i]))
1503              return Qfalse;
1504      }
1505      return Qtrue;
1506  }
1507  
1508  static VALUE
1509  rb_ary_eql(ary1, ary2)
1510      VALUE ary1, ary2;
1511  {
1512      long i;
1513  
1514      if (TYPE(ary2) != T_ARRAY) return Qfalse;
1515      if (RARRAY(ary1)->len != RARRAY(ary2)->len) return Qfalse;
1516      for (i=0; i<RARRAY(ary1)->len; i++) {
1517          if (!rb_eql(RARRAY(ary1)->ptr[i], RARRAY(ary2)->ptr[i]))
1518              return Qfalse;
1519      }
1520      return Qtrue;
1521  }
1522  
1523  static VALUE
1524  rb_ary_hash(ary)
1525      VALUE ary;
1526  {
1527      long i, h;
1528      VALUE n;
1529  
1530      h = RARRAY(ary)->len;
1531      for (i=0; i<RARRAY(ary)->len; i++) {
1532          h = (h << 1) | (h<0 ? 1 : 0);
1533          n = rb_hash(RARRAY(ary)->ptr[i]);
1534          h ^= NUM2LONG(n);
1535      }
1536      return LONG2FIX(h);
1537  }
1538  
1539  VALUE
rb_ary_includes(ary, item)
1541      VALUE ary;
1542      VALUE item;
1543  {
1544      long i;
1545      
1546      for (i=0; i<RARRAY(ary)->len; i++) {
1547          if (rb_equal(RARRAY(ary)->ptr[i], item)) {
1548              return Qtrue;
1549          }
1550      }
1551      return Qfalse;
1552  }
1553  
1554  VALUE
1555  rb_ary_cmp(ary1, ary2)
1556      VALUE ary1, ary2;
1557  {
1558      long i, len;
1559  
1560      ary2 = to_ary(ary2);
1561      len = RARRAY(ary1)->len;
1562      if (len > RARRAY(ary2)->len) {
1563          len = RARRAY(ary2)->len;
1564      }
1565      for (i=0; i<len; i++) {
1566          VALUE v = rb_funcall(RARRAY(ary1)->ptr[i], id_cmp, 1, RARRAY(ary2)->ptr[i]);
1567          if (v != INT2FIX(0)) {
1568              return v;
1569          }
1570      }
1571      len = RARRAY(ary1)->len - RARRAY(ary2)->len;
1572      if (len == 0) return INT2FIX(0);
1573      if (len > 0) return INT2FIX(1);
1574      return INT2FIX(-1);
1575  }
1576  
1577  static VALUE
1578  rb_ary_diff(ary1, ary2)
1579      VALUE ary1, ary2;
1580  {
1581      VALUE ary3;
1582      long i;
1583  
1584      ary2 = to_ary(ary2);
1585      ary3 = rb_ary_new();
1586      for (i=0; i<RARRAY(ary1)->len; i++) {
1587          if (rb_ary_includes(ary2, RARRAY(ary1)->ptr[i])) continue;
1588          if (rb_ary_includes(ary3, RARRAY(ary1)->ptr[i])) continue;
rb_ary_push(ary3, RARRAY(ary1)->ptr[i]);
1590      }
1591      return ary3;
1592  }
1593  
1594  static VALUE
ary_make_hash(ary1, ary2)
1596      VALUE ary1, ary2;
1597  {
1598      VALUE hash = rb_hash_new();
1599      long i;
1600  
1601      for (i=0; i<RARRAY(ary1)->len; i++) {
rb_hash_aset(hash, RARRAY(ary1)->ptr[i], Qtrue);
1603      }
1604      if (ary2) {
1605          for (i=0; i<RARRAY(ary2)->len; i++) {
rb_hash_aset(hash, RARRAY(ary2)->ptr[i], Qtrue);
1607          }
1608      }
1609      return hash;
1610  }
1611  
1612  static VALUE
1613  rb_ary_and(ary1, ary2)
1614      VALUE ary1, ary2;
1615  {
1616      VALUE hash, ary3;
1617      long i;
1618  
1619      ary2 = to_ary(ary2);
1620      ary3 = rb_ary_new2(RARRAY(ary1)->len < RARRAY(ary2)->len ?
RARRAY(ary1)->len : RARRAY(ary2)->len);
1622      hash = ary_make_hash(ary2, 0);
1623  
1624      for (i=0; i<RARRAY(ary1)->len; i++) {
1625          VALUE v = RARRAY(ary1)->ptr[i];
1626          if (st_delete(RHASH(hash)->tbl, &v, 0)) {
rb_ary_push(ary3, RARRAY(ary1)->ptr[i]);
1628          }
1629      }
1630  
1631      return ary3;
1632  }
1633  
1634  static VALUE
1635  rb_ary_or(ary1, ary2)
1636      VALUE ary1, ary2;
1637  {
1638      VALUE hash, ary3;
1639      VALUE v;
1640      long i;
1641  
1642      ary2 = to_ary(ary2);
1643      ary3 = rb_ary_new2(RARRAY(ary1)->len+RARRAY(ary2)->len);
1644      hash = ary_make_hash(ary1, ary2);
1645  
1646      for (i=0; i<RARRAY(ary1)->len; i++) {
1647          v = RARRAY(ary1)->ptr[i];
1648          if (st_delete(RHASH(hash)->tbl, &v, 0)) {
rb_ary_push(ary3, RARRAY(ary1)->ptr[i]);
1650          }
1651      }
1652      for (i=0; i<RARRAY(ary2)->len; i++) {
1653          v = RARRAY(ary2)->ptr[i];
1654          if (st_delete(RHASH(hash)->tbl, &v, 0)) {
rb_ary_push(ary3, RARRAY(ary2)->ptr[i]);
1656          }
1657      }
1658      return ary3;
1659  }
1660  
1661  static VALUE
rb_ary_uniq_bang(ary)
1663      VALUE ary;
1664  {
1665      VALUE hash;
1666      VALUE *p, *q, *end;
1667  
rb_ary_modify(ary); 
1669  
1670      hash = ary_make_hash(ary, 0);
1671  
1672      if (RARRAY(ary)->len == RHASH(hash)->tbl->num_entries) {
1673          return Qnil;
1674      }
1675      p = q = RARRAY(ary)->ptr;
1676      end = p + RARRAY(ary)->len;
1677      while (p < end) {
1678          VALUE v = *p;
1679          if (st_delete(RHASH(hash)->tbl, &v, 0)) {
1680              *q++ = *p;
1681          }
1682          p++;
1683      }
RARRAY(ary)->len = (q - RARRAY(ary)->ptr);
1685  
1686      return ary;
1687  }
1688  
1689  static VALUE
1690  rb_ary_uniq(ary)
1691      VALUE ary;
1692  {
1693      ary = rb_ary_dup(ary);
rb_ary_uniq_bang(ary);
1695      return ary;
1696  }
1697  
1698  static VALUE
rb_ary_compact_bang(ary)
1700      VALUE ary;
1701  {
1702      VALUE *p, *t, *end;
1703  
rb_ary_modify(ary);
1705      p = t = RARRAY(ary)->ptr;
1706      end = p + RARRAY(ary)->len;
1707      
1708      while (t < end) {
1709          if (NIL_P(*t)) t++;
1710          else *p++ = *t++;
1711      }
1712      if (RARRAY(ary)->len == (p - RARRAY(ary)->ptr)) {
1713          return Qnil;
1714      }
RARRAY(ary)->len = RARRAY(ary)->aux.capa = (p - RARRAY(ary)->ptr);
REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
1717  
1718      return ary;
1719  }
1720  
1721  static VALUE
1722  rb_ary_compact(ary)
1723      VALUE ary;
1724  {
1725      ary = rb_ary_dup(ary);
rb_ary_compact_bang(ary);
1727      return ary;
1728  }
1729  
1730  static VALUE
1731  rb_ary_nitems(ary)
1732      VALUE ary;
1733  {
1734      long n = 0;
1735      VALUE *p, *pend;
1736  
1737      p = RARRAY(ary)->ptr;
1738      pend = p + RARRAY(ary)->len;
1739  
1740      while (p < pend) {
1741          if (!NIL_P(*p)) n++;
1742          p++;
1743      }
1744      return LONG2NUM(n);
1745  }
1746  
1747  static long
flatten(ary, idx, ary2, memo)
1749      VALUE ary;
1750      long idx;
1751      VALUE ary2, memo;
1752  {
1753      VALUE id;
1754      long i = idx;
1755      long n, lim = idx + RARRAY(ary2)->len;
1756  
1757      id = rb_obj_id(ary2);
1758      if (rb_ary_includes(memo, id)) {
rb_raise(rb_eArgError, "tried to flatten recursive array");
1760      }
rb_ary_push(memo, id);
rb_ary_update(ary, idx, 1, ary2);
1763      while (i < lim) {
1764          if (TYPE(RARRAY(ary)->ptr[i]) == T_ARRAY) {
1765              n = flatten(ary, i, RARRAY(ary)->ptr[i], memo);
1766              i += n; lim += n;
1767          }
1768          i++;
1769      }
rb_ary_pop(memo);
1771  
1772      return lim - idx - 1;       /* returns number of increased items */
1773  }
1774  
1775  static VALUE
rb_ary_flatten_bang(ary)
1777      VALUE ary;
1778  {
1779      long i = 0;
1780      int mod = 0;
1781      VALUE memo = Qnil;
1782  
rb_ary_modify(ary);
1784      while (i<RARRAY(ary)->len) {
1785          VALUE ary2 = RARRAY(ary)->ptr[i];
1786  
1787          if (TYPE(ary2) == T_ARRAY) {
1788              if (NIL_P(memo)) {
1789                  memo = rb_ary_new();
1790              }
1791              i += flatten(ary, i, ary2, memo);
1792              mod = 1;
1793          }
1794          i++;
1795      }
1796      if (mod == 0) return Qnil;
1797      return ary;
1798  }
1799  
1800  static VALUE
1801  rb_ary_flatten(ary)
1802      VALUE ary;
1803  {
1804      ary = rb_ary_dup(ary);
rb_ary_flatten_bang(ary);
1806      return ary;
1807  }
1808  
1809  void
Init_Array()
1811  {
1812      rb_cArray  = rb_define_class("Array", rb_cObject);
rb_include_module(rb_cArray, rb_mEnumerable);
1814  
rb_define_singleton_method(rb_cArray, "allocate", rb_ary_s_alloc, 0);
rb_define_singleton_method(rb_cArray, "[]", rb_ary_s_create, -1);
rb_define_method(rb_cArray, "initialize", rb_ary_initialize, -1);
rb_define_method(rb_cArray, "to_s", rb_ary_to_s, 0);
rb_define_method(rb_cArray, "inspect", rb_ary_inspect, 0);
rb_define_method(rb_cArray, "to_a", rb_ary_to_a, 0);
rb_define_method(rb_cArray, "to_ary", rb_ary_to_a, 0);
rb_define_method(rb_cArray, "frozen?",  rb_ary_frozen_p, 0);
1823  
rb_define_method(rb_cArray, "==", rb_ary_equal, 1);
rb_define_method(rb_cArray, "eql?", rb_ary_eql, 1);
rb_define_method(rb_cArray, "hash", rb_ary_hash, 0);
rb_define_method(rb_cArray, "===", rb_ary_equal, 1);
1828  
rb_define_method(rb_cArray, "[]", rb_ary_aref, -1);
rb_define_method(rb_cArray, "[]=", rb_ary_aset, -1);
rb_define_method(rb_cArray, "at", rb_ary_at, 1);
rb_define_method(rb_cArray, "fetch", rb_ary_fetch, -1);
rb_define_method(rb_cArray, "first", rb_ary_first, 0);
rb_define_method(rb_cArray, "last", rb_ary_last, 0);
rb_define_method(rb_cArray, "concat", rb_ary_concat, 1);
rb_define_method(rb_cArray, "<<", rb_ary_push, 1);
rb_define_method(rb_cArray, "push", rb_ary_push_m, -1);
rb_define_method(rb_cArray, "pop", rb_ary_pop, 0);
rb_define_method(rb_cArray, "shift", rb_ary_shift, 0);
rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
rb_define_method(rb_cArray, "insert", rb_ary_insert, -1);
rb_define_method(rb_cArray, "each", rb_ary_each, 0);
rb_define_method(rb_cArray, "each_index", rb_ary_each_index, 0);
rb_define_method(rb_cArray, "reverse_each", rb_ary_reverse_each, 0);
rb_define_method(rb_cArray, "length", rb_ary_length, 0);
rb_define_alias(rb_cArray,  "size", "length");
rb_define_method(rb_cArray, "empty?", rb_ary_empty_p, 0);
rb_define_method(rb_cArray, "index", rb_ary_index, 1);
rb_define_method(rb_cArray, "rindex", rb_ary_rindex, 1);
rb_define_method(rb_cArray, "indexes", rb_ary_indexes, -1);
rb_define_method(rb_cArray, "indices", rb_ary_indexes, -1);
rb_define_method(rb_cArray, "become", rb_ary_replace, 1);
rb_define_method(rb_cArray, "join", rb_ary_join_m, -1);
rb_define_method(rb_cArray, "reverse", rb_ary_reverse_m, 0);
rb_define_method(rb_cArray, "reverse!", rb_ary_reverse_bang, 0);
rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);
rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
rb_define_method(rb_cArray, "collect!", rb_ary_collect_bang, 0);
rb_define_method(rb_cArray, "select", rb_ary_select, -1);
rb_define_method(rb_cArray, "map", rb_ary_collect, 0);
rb_define_method(rb_cArray, "map!", rb_ary_collect_bang, 0);
rb_define_method(rb_cArray, "delete", rb_ary_delete, 1);
rb_define_method(rb_cArray, "delete_at", rb_ary_delete_at_m, 1);
rb_define_method(rb_cArray, "delete_if", rb_ary_delete_if, 0);
rb_define_method(rb_cArray, "reject", rb_ary_reject, 0);
rb_define_method(rb_cArray, "reject!", rb_ary_reject_bang, 0);
rb_define_method(rb_cArray, "replace", rb_ary_replace, 1);
rb_define_method(rb_cArray, "clear", rb_ary_clear, 0);
rb_define_method(rb_cArray, "fill", rb_ary_fill, -1);
rb_define_method(rb_cArray, "include?", rb_ary_includes, 1);
rb_define_method(rb_cArray, "<=>", rb_ary_cmp, 1);
1873  
rb_define_method(rb_cArray, "slice", rb_ary_aref, -1);
rb_define_method(rb_cArray, "slice!", rb_ary_slice_bang, -1);
1876  
rb_define_method(rb_cArray, "assoc", rb_ary_assoc, 1);
rb_define_method(rb_cArray, "rassoc", rb_ary_rassoc, 1);
1879  
rb_define_method(rb_cArray, "+", rb_ary_plus, 1);
rb_define_method(rb_cArray, "*", rb_ary_times, 1);
1882  
rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
rb_define_method(rb_cArray, "&", rb_ary_and, 1);
rb_define_method(rb_cArray, "|", rb_ary_or, 1);
1886  
rb_define_method(rb_cArray, "uniq", rb_ary_uniq, 0);
rb_define_method(rb_cArray, "uniq!", rb_ary_uniq_bang, 0);
rb_define_method(rb_cArray, "compact", rb_ary_compact, 0);
rb_define_method(rb_cArray, "compact!", rb_ary_compact_bang, 0);
rb_define_method(rb_cArray, "flatten", rb_ary_flatten, 0);
rb_define_method(rb_cArray, "flatten!", rb_ary_flatten_bang, 0);
rb_define_method(rb_cArray, "nitems", rb_ary_nitems, 0);
1894  
1895      id_cmp = rb_intern("<=>");
1896      inspect_key = rb_intern("__inspect_key__");
1897  }