array.c

00001 /*
00002 ** array.c - Array class
00003 **
00004 ** See Copyright Notice in mruby.h
00005 */
00006 
00007 #include "mruby.h"
00008 #include "mruby/array.h"
00009 #include "mruby/class.h"
00010 #include "mruby/string.h"
00011 #include "mruby/range.h"
00012 #include "value_array.h"
00013 
00014 #define ARY_DEFAULT_LEN   4
00015 #define ARY_SHRINK_RATIO  5 /* must be larger than 2 */
00016 #define ARY_C_MAX_SIZE (SIZE_MAX / sizeof(mrb_value))
00017 #define ARY_MAX_SIZE ((ARY_C_MAX_SIZE < (size_t)MRB_INT_MAX) ? (mrb_int)ARY_C_MAX_SIZE : MRB_INT_MAX-1)
00018 
00019 static inline mrb_value
00020 ary_elt(mrb_value ary, mrb_int offset)
00021 {
00022   if (RARRAY_LEN(ary) == 0) return mrb_nil_value();
00023   if (offset < 0 || RARRAY_LEN(ary) <= offset) {
00024     return mrb_nil_value();
00025   }
00026   return RARRAY_PTR(ary)[offset];
00027 }
00028 
00029 static struct RArray*
00030 ary_new_capa(mrb_state *mrb, mrb_int capa)
00031 {
00032   struct RArray *a;
00033   mrb_int blen;
00034 
00035   if (capa > ARY_MAX_SIZE) {
00036     mrb_raise(mrb, E_ARGUMENT_ERROR, "array size too big");
00037   }
00038   blen = capa * sizeof(mrb_value);
00039   if (blen < capa) {
00040     mrb_raise(mrb, E_ARGUMENT_ERROR, "array size too big");
00041   }
00042 
00043   a = (struct RArray*)mrb_obj_alloc(mrb, MRB_TT_ARRAY, mrb->array_class);
00044   a->ptr = (mrb_value *)mrb_malloc(mrb, blen);
00045   a->aux.capa = capa;
00046   a->len = 0;
00047 
00048   return a;
00049 }
00050 
00051 MRB_API mrb_value
00052 mrb_ary_new_capa(mrb_state *mrb, mrb_int capa)
00053 {
00054   struct RArray *a = ary_new_capa(mrb, capa);
00055   return mrb_obj_value(a);
00056 }
00057 
00058 MRB_API mrb_value
00059 mrb_ary_new(mrb_state *mrb)
00060 {
00061   return mrb_ary_new_capa(mrb, 0);
00062 }
00063 
00064 /*
00065  * to copy array, use this instead of memcpy because of portability
00066  * * gcc on ARM may fail optimization of memcpy
00067  *   http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka3934.html
00068  * * gcc on MIPS also fail
00069  *   http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39755
00070  * * memcpy doesn't exist on freestanding environment
00071  *
00072  * If you optimize for binary size, use memcpy instead of this at your own risk
00073  * of above portability issue.
00074  *
00075  * see also http://togetter.com/li/462898
00076  *
00077  */
00078 static inline void
00079 array_copy(mrb_value *dst, const mrb_value *src, mrb_int size)
00080 {
00081   mrb_int i;
00082 
00083   for (i = 0; i < size; i++) {
00084     dst[i] = src[i];
00085   }
00086 }
00087 
00088 MRB_API mrb_value
00089 mrb_ary_new_from_values(mrb_state *mrb, mrb_int size, const mrb_value *vals)
00090 {
00091   mrb_value ary;
00092   struct RArray *a;
00093 
00094   ary = mrb_ary_new_capa(mrb, size);
00095   a = mrb_ary_ptr(ary);
00096   array_copy(a->ptr, vals, size);
00097   a->len = size;
00098 
00099   return ary;
00100 }
00101 
00102 MRB_API mrb_value
00103 mrb_assoc_new(mrb_state *mrb, mrb_value car, mrb_value cdr)
00104 {
00105   struct RArray *a;
00106 
00107   a = ary_new_capa(mrb, 2);
00108   a->ptr[0] = car;
00109   a->ptr[1] = cdr;
00110   a->len = 2;
00111   return mrb_obj_value(a);
00112 }
00113 
00114 static void
00115 ary_fill_with_nil(mrb_value *ptr, mrb_int size)
00116 {
00117   mrb_value nil = mrb_nil_value();
00118 
00119   while (size--) {
00120     *ptr++ = nil;
00121   }
00122 }
00123 
00124 static void
00125 ary_modify(mrb_state *mrb, struct RArray *a)
00126 {
00127   if (ARY_SHARED_P(a)) {
00128     mrb_shared_array *shared = a->aux.shared;
00129 
00130     if (shared->refcnt == 1 && a->ptr == shared->ptr) {
00131       a->ptr = shared->ptr;
00132       a->aux.capa = a->len;
00133       mrb_free(mrb, shared);
00134     }
00135     else {
00136       mrb_value *ptr, *p;
00137       mrb_int len;
00138 
00139       p = a->ptr;
00140       len = a->len * sizeof(mrb_value);
00141       ptr = (mrb_value *)mrb_malloc(mrb, len);
00142       if (p) {
00143         array_copy(ptr, p, a->len);
00144       }
00145       a->ptr = ptr;
00146       a->aux.capa = a->len;
00147       mrb_ary_decref(mrb, shared);
00148     }
00149     ARY_UNSET_SHARED_FLAG(a);
00150   }
00151 }
00152 
00153 MRB_API void
00154 mrb_ary_modify(mrb_state *mrb, struct RArray* a)
00155 {
00156   mrb_write_barrier(mrb, (struct RBasic*)a);
00157   ary_modify(mrb, a);
00158 }
00159 
00160 static void
00161 ary_make_shared(mrb_state *mrb, struct RArray *a)
00162 {
00163   if (!ARY_SHARED_P(a)) {
00164     mrb_shared_array *shared = (mrb_shared_array *)mrb_malloc(mrb, sizeof(mrb_shared_array));
00165 
00166     shared->refcnt = 1;
00167     if (a->aux.capa > a->len) {
00168       a->ptr = shared->ptr = (mrb_value *)mrb_realloc(mrb, a->ptr, sizeof(mrb_value)*a->len+1);
00169     }
00170     else {
00171       shared->ptr = a->ptr;
00172     }
00173     shared->len = a->len;
00174     a->aux.shared = shared;
00175     ARY_SET_SHARED_FLAG(a);
00176   }
00177 }
00178 
00179 static void
00180 ary_expand_capa(mrb_state *mrb, struct RArray *a, mrb_int len)
00181 {
00182   mrb_int capa = a->aux.capa;
00183 
00184   if (len > ARY_MAX_SIZE) {
00185     mrb_raise(mrb, E_ARGUMENT_ERROR, "array size too big");
00186   }
00187 
00188   if (capa == 0) {
00189     capa = ARY_DEFAULT_LEN;
00190   }
00191   while (capa < len) {
00192     capa *= 2;
00193   }
00194 
00195   if (capa > ARY_MAX_SIZE) capa = ARY_MAX_SIZE; /* len <= capa <= ARY_MAX_SIZE */
00196 
00197   if (capa > a->aux.capa) {
00198     mrb_value *expanded_ptr = (mrb_value *)mrb_realloc(mrb, a->ptr, sizeof(mrb_value)*capa);
00199 
00200     a->aux.capa = capa;
00201     a->ptr = expanded_ptr;
00202   }
00203 }
00204 
00205 static void
00206 ary_shrink_capa(mrb_state *mrb, struct RArray *a)
00207 {
00208   mrb_int capa = a->aux.capa;
00209 
00210   if (capa < ARY_DEFAULT_LEN * 2) return;
00211   if (capa <= a->len * ARY_SHRINK_RATIO) return;
00212 
00213   do {
00214     capa /= 2;
00215     if (capa < ARY_DEFAULT_LEN) {
00216       capa = ARY_DEFAULT_LEN;
00217       break;
00218     }
00219   } while (capa > a->len * ARY_SHRINK_RATIO);
00220 
00221   if (capa > a->len && capa < a->aux.capa) {
00222     a->aux.capa = capa;
00223     a->ptr = (mrb_value *)mrb_realloc(mrb, a->ptr, sizeof(mrb_value)*capa);
00224   }
00225 }
00226 
00227 MRB_API mrb_value
00228 mrb_ary_resize(mrb_state *mrb, mrb_value ary, mrb_int new_len)
00229 {
00230   mrb_int old_len;
00231   struct RArray *a = mrb_ary_ptr(ary);
00232 
00233   ary_modify(mrb, a);
00234   old_len = RARRAY_LEN(ary);
00235   if (old_len != new_len) {
00236     a->len = new_len;
00237     if (new_len < old_len) {
00238       ary_shrink_capa(mrb, a);
00239     }
00240     else {
00241       ary_expand_capa(mrb, a, new_len);
00242       ary_fill_with_nil(a->ptr + old_len, new_len - old_len);
00243     }
00244   }
00245 
00246   return ary;
00247 }
00248 
00249 static mrb_value
00250 mrb_ary_s_create(mrb_state *mrb, mrb_value self)
00251 {
00252   mrb_value *vals;
00253   mrb_int len;
00254 
00255   mrb_get_args(mrb, "*", &vals, &len);
00256 
00257   return mrb_ary_new_from_values(mrb, len, vals);
00258 }
00259 
00260 static void
00261 ary_concat(mrb_state *mrb, struct RArray *a, mrb_value *ptr, mrb_int blen)
00262 {
00263   mrb_int len = a->len + blen;
00264 
00265   ary_modify(mrb, a);
00266   if (a->aux.capa < len) ary_expand_capa(mrb, a, len);
00267   array_copy(a->ptr+a->len, ptr, blen);
00268   mrb_write_barrier(mrb, (struct RBasic*)a);
00269   a->len = len;
00270 }
00271 
00272 MRB_API void
00273 mrb_ary_concat(mrb_state *mrb, mrb_value self, mrb_value other)
00274 {
00275   struct RArray *a2 = mrb_ary_ptr(other);
00276 
00277   ary_concat(mrb, mrb_ary_ptr(self), a2->ptr, a2->len);
00278 }
00279 
00280 static mrb_value
00281 mrb_ary_concat_m(mrb_state *mrb, mrb_value self)
00282 {
00283   mrb_value *ptr;
00284   mrb_int blen;
00285 
00286   mrb_get_args(mrb, "a", &ptr, &blen);
00287   ary_concat(mrb, mrb_ary_ptr(self), ptr, blen);
00288   return self;
00289 }
00290 
00291 static mrb_value
00292 mrb_ary_plus(mrb_state *mrb, mrb_value self)
00293 {
00294   struct RArray *a1 = mrb_ary_ptr(self);
00295   struct RArray *a2;
00296   mrb_value ary;
00297   mrb_value *ptr;
00298   mrb_int blen;
00299 
00300   mrb_get_args(mrb, "a", &ptr, &blen);
00301   ary = mrb_ary_new_capa(mrb, a1->len + blen);
00302   a2 = mrb_ary_ptr(ary);
00303   array_copy(a2->ptr, a1->ptr, a1->len);
00304   array_copy(a2->ptr + a1->len, ptr, blen);
00305   a2->len = a1->len + blen;
00306 
00307   return ary;
00308 }
00309 
00310 static void
00311 ary_replace(mrb_state *mrb, struct RArray *a, mrb_value *argv, mrb_int len)
00312 {
00313   ary_modify(mrb, a);
00314   if (a->aux.capa < len)
00315     ary_expand_capa(mrb, a, len);
00316   array_copy(a->ptr, argv, len);
00317   mrb_write_barrier(mrb, (struct RBasic*)a);
00318   a->len = len;
00319 }
00320 
00321 MRB_API void
00322 mrb_ary_replace(mrb_state *mrb, mrb_value self, mrb_value other)
00323 {
00324   struct RArray *a2 = mrb_ary_ptr(other);
00325 
00326   ary_replace(mrb, mrb_ary_ptr(self), a2->ptr, a2->len);
00327 }
00328 
00329 static mrb_value
00330 mrb_ary_replace_m(mrb_state *mrb, mrb_value self)
00331 {
00332   mrb_value other;
00333 
00334   mrb_get_args(mrb, "A", &other);
00335   mrb_ary_replace(mrb, self, other);
00336 
00337   return self;
00338 }
00339 
00340 static mrb_value
00341 mrb_ary_times(mrb_state *mrb, mrb_value self)
00342 {
00343   struct RArray *a1 = mrb_ary_ptr(self);
00344   struct RArray *a2;
00345   mrb_value ary;
00346   mrb_value *ptr;
00347   mrb_int times;
00348 
00349   mrb_get_args(mrb, "i", &times);
00350   if (times < 0) {
00351     mrb_raise(mrb, E_ARGUMENT_ERROR, "negative argument");
00352   }
00353   if (times == 0) return mrb_ary_new(mrb);
00354 
00355   ary = mrb_ary_new_capa(mrb, a1->len * times);
00356   a2 = mrb_ary_ptr(ary);
00357   ptr = a2->ptr;
00358   while (times--) {
00359     array_copy(ptr, a1->ptr, a1->len);
00360     ptr += a1->len;
00361     a2->len += a1->len;
00362   }
00363 
00364   return ary;
00365 }
00366 
00367 static mrb_value
00368 mrb_ary_reverse_bang(mrb_state *mrb, mrb_value self)
00369 {
00370   struct RArray *a = mrb_ary_ptr(self);
00371 
00372   if (a->len > 1) {
00373     mrb_value *p1, *p2;
00374 
00375     ary_modify(mrb, a);
00376     p1 = a->ptr;
00377     p2 = a->ptr + a->len - 1;
00378 
00379     while (p1 < p2) {
00380       mrb_value tmp = *p1;
00381       *p1++ = *p2;
00382       *p2-- = tmp;
00383     }
00384   }
00385   return self;
00386 }
00387 
00388 static mrb_value
00389 mrb_ary_reverse(mrb_state *mrb, mrb_value self)
00390 {
00391   struct RArray *a = mrb_ary_ptr(self), *b;
00392   mrb_value ary;
00393 
00394   ary = mrb_ary_new_capa(mrb, a->len);
00395   b = mrb_ary_ptr(ary);
00396   if (a->len > 0) {
00397     mrb_value *p1, *p2, *e;
00398 
00399     p1 = a->ptr;
00400     e  = p1 + a->len;
00401     p2 = b->ptr + a->len - 1;
00402     while (p1 < e) {
00403       *p2-- = *p1++;
00404     }
00405     b->len = a->len;
00406   }
00407   return ary;
00408 }
00409 
00410 MRB_API void
00411 mrb_ary_push(mrb_state *mrb, mrb_value ary, mrb_value elem)
00412 {
00413   struct RArray *a = mrb_ary_ptr(ary);
00414 
00415   ary_modify(mrb, a);
00416   if (a->len == a->aux.capa)
00417     ary_expand_capa(mrb, a, a->len + 1);
00418   a->ptr[a->len++] = elem;
00419   mrb_field_write_barrier_value(mrb, (struct RBasic*)a, elem);
00420 }
00421 
00422 static mrb_value
00423 mrb_ary_push_m(mrb_state *mrb, mrb_value self)
00424 {
00425   mrb_value *argv;
00426   mrb_int len;
00427 
00428   mrb_get_args(mrb, "*", &argv, &len);
00429   while (len--) {
00430     mrb_ary_push(mrb, self, *argv++);
00431   }
00432 
00433   return self;
00434 }
00435 
00436 MRB_API mrb_value
00437 mrb_ary_pop(mrb_state *mrb, mrb_value ary)
00438 {
00439   struct RArray *a = mrb_ary_ptr(ary);
00440 
00441   if (a->len == 0) return mrb_nil_value();
00442   return a->ptr[--a->len];
00443 }
00444 
00445 #define ARY_SHIFT_SHARED_MIN 10
00446 
00447 MRB_API mrb_value
00448 mrb_ary_shift(mrb_state *mrb, mrb_value self)
00449 {
00450   struct RArray *a = mrb_ary_ptr(self);
00451   mrb_value val;
00452 
00453   if (a->len == 0) return mrb_nil_value();
00454   if (ARY_SHARED_P(a)) {
00455   L_SHIFT:
00456     val = a->ptr[0];
00457     a->ptr++;
00458     a->len--;
00459     return val;
00460   }
00461   if (a->len > ARY_SHIFT_SHARED_MIN) {
00462     ary_make_shared(mrb, a);
00463     goto L_SHIFT;
00464   }
00465   else {
00466     mrb_value *ptr = a->ptr;
00467     mrb_int size = a->len;
00468 
00469     val = *ptr;
00470     while (--size) {
00471       *ptr = *(ptr+1);
00472       ++ptr;
00473     }
00474     --a->len;
00475   }
00476   return val;
00477 }
00478 
00479 /* self = [1,2,3]
00480    item = 0
00481    self.unshift item
00482    p self #=> [0, 1, 2, 3] */
00483 MRB_API mrb_value
00484 mrb_ary_unshift(mrb_state *mrb, mrb_value self, mrb_value item)
00485 {
00486   struct RArray *a = mrb_ary_ptr(self);
00487 
00488   if (ARY_SHARED_P(a)
00489       && a->aux.shared->refcnt == 1 /* shared only referenced from this array */
00490       && a->ptr - a->aux.shared->ptr >= 1) /* there's room for unshifted item */ {
00491     a->ptr--;
00492     a->ptr[0] = item;
00493   }
00494   else {
00495     ary_modify(mrb, a);
00496     if (a->aux.capa < a->len + 1)
00497       ary_expand_capa(mrb, a, a->len + 1);
00498     value_move(a->ptr + 1, a->ptr, a->len);
00499     a->ptr[0] = item;
00500   }
00501   a->len++;
00502   mrb_field_write_barrier_value(mrb, (struct RBasic*)a, item);
00503 
00504   return self;
00505 }
00506 
00507 static mrb_value
00508 mrb_ary_unshift_m(mrb_state *mrb, mrb_value self)
00509 {
00510   struct RArray *a = mrb_ary_ptr(self);
00511   mrb_value *vals;
00512   mrb_int len;
00513 
00514   mrb_get_args(mrb, "*", &vals, &len);
00515   if (ARY_SHARED_P(a)
00516       && a->aux.shared->refcnt == 1 /* shared only referenced from this array */
00517       && a->ptr - a->aux.shared->ptr >= len) /* there's room for unshifted item */ {
00518     a->ptr -= len;
00519   }
00520   else {
00521     ary_modify(mrb, a);
00522     if (len == 0) return self;
00523     if (a->aux.capa < a->len + len)
00524       ary_expand_capa(mrb, a, a->len + len);
00525     value_move(a->ptr + len, a->ptr, a->len);
00526   }
00527   array_copy(a->ptr, vals, len);
00528   a->len += len;
00529   while (len--) {
00530     mrb_field_write_barrier_value(mrb, (struct RBasic*)a, vals[len]);
00531   }
00532 
00533   return self;
00534 }
00535 
00536 MRB_API mrb_value
00537 mrb_ary_ref(mrb_state *mrb, mrb_value ary, mrb_int n)
00538 {
00539   struct RArray *a = mrb_ary_ptr(ary);
00540 
00541   /* range check */
00542   if (n < 0) n += a->len;
00543   if (n < 0 || a->len <= n) return mrb_nil_value();
00544 
00545   return a->ptr[n];
00546 }
00547 
00548 MRB_API void
00549 mrb_ary_set(mrb_state *mrb, mrb_value ary, mrb_int n, mrb_value val)
00550 {
00551   struct RArray *a = mrb_ary_ptr(ary);
00552 
00553   ary_modify(mrb, a);
00554   /* range check */
00555   if (n < 0) {
00556     n += a->len;
00557     if (n < 0) {
00558       mrb_raisef(mrb, E_INDEX_ERROR, "index %S out of array", mrb_fixnum_value(n - a->len));
00559     }
00560   }
00561   if (a->len <= n) {
00562     if (a->aux.capa <= n)
00563       ary_expand_capa(mrb, a, n + 1);
00564     ary_fill_with_nil(a->ptr + a->len, n + 1 - a->len);
00565     a->len = n + 1;
00566   }
00567 
00568   a->ptr[n] = val;
00569   mrb_field_write_barrier_value(mrb, (struct RBasic*)a, val);
00570 }
00571 
00572 MRB_API mrb_value
00573 mrb_ary_splice(mrb_state *mrb, mrb_value ary, mrb_int head, mrb_int len, mrb_value rpl)
00574 {
00575   struct RArray *a = mrb_ary_ptr(ary);
00576   mrb_int tail, size;
00577   const mrb_value *argv;
00578   mrb_int i, argc;
00579 
00580   ary_modify(mrb, a);
00581 
00582   /* len check */
00583   if (len < 0) mrb_raisef(mrb, E_INDEX_ERROR, "negative length (%S)", mrb_fixnum_value(len));
00584 
00585   /* range check */
00586   if (head < 0) {
00587     head += a->len;
00588     if (head < 0) {
00589       mrb_raise(mrb, E_INDEX_ERROR, "index is out of array");
00590     }
00591   }
00592   if (a->len < len || a->len < head + len) {
00593     len = a->len - head;
00594   }
00595   tail = head + len;
00596 
00597   /* size check */
00598   if (mrb_array_p(rpl)) {
00599     argc = RARRAY_LEN(rpl);
00600     argv = RARRAY_PTR(rpl);
00601   }
00602   else {
00603     argc = 1;
00604     argv = &rpl;
00605   }
00606   size = head + argc;
00607 
00608   if (tail < a->len) size += a->len - tail;
00609   if (size > a->aux.capa)
00610     ary_expand_capa(mrb, a, size);
00611 
00612   if (head > a->len) {
00613     ary_fill_with_nil(a->ptr + a->len, head - a->len);
00614   }
00615   else if (head < a->len) {
00616     value_move(a->ptr + head + argc, a->ptr + tail, a->len - tail);
00617   }
00618 
00619   for (i = 0; i < argc; i++) {
00620     *(a->ptr + head + i) = *(argv + i);
00621     mrb_field_write_barrier_value(mrb, (struct RBasic*)a, argv[i]);
00622   }
00623 
00624   a->len = size;
00625 
00626   return ary;
00627 }
00628 
00629 void
00630 mrb_ary_decref(mrb_state *mrb, mrb_shared_array *shared)
00631 {
00632   shared->refcnt--;
00633   if (shared->refcnt == 0) {
00634     mrb_free(mrb, shared->ptr);
00635     mrb_free(mrb, shared);
00636   }
00637 }
00638 
00639 static mrb_value
00640 ary_subseq(mrb_state *mrb, struct RArray *a, mrb_int beg, mrb_int len)
00641 {
00642   struct RArray *b;
00643 
00644   ary_make_shared(mrb, a);
00645   b  = (struct RArray*)mrb_obj_alloc(mrb, MRB_TT_ARRAY, mrb->array_class);
00646   b->ptr = a->ptr + beg;
00647   b->len = len;
00648   b->aux.shared = a->aux.shared;
00649   b->aux.shared->refcnt++;
00650   ARY_SET_SHARED_FLAG(b);
00651 
00652   return mrb_obj_value(b);
00653 }
00654 
00655 static mrb_int
00656 aget_index(mrb_state *mrb, mrb_value index)
00657 {
00658   if (mrb_fixnum_p(index)) {
00659     return mrb_fixnum(index);
00660   }
00661   else if (mrb_float_p(index)) {
00662     return (mrb_int)mrb_float(index);
00663   }
00664   else {
00665     mrb_int i, argc;
00666     mrb_value *argv;
00667 
00668     mrb_get_args(mrb, "i*", &i, &argv, &argc);
00669     return i;
00670   }
00671 }
00672 
00673 /*
00674  *  call-seq:
00675  *     ary[index]                -> obj     or nil
00676  *     ary[start, length]        -> new_ary or nil
00677  *     ary[range]                -> new_ary or nil
00678  *     ary.slice(index)          -> obj     or nil
00679  *     ary.slice(start, length)  -> new_ary or nil
00680  *     ary.slice(range)          -> new_ary or nil
00681  *
00682  *  Element Reference --- Returns the element at +index+, or returns a
00683  *  subarray starting at the +start+ index and continuing for +length+
00684  *  elements, or returns a subarray specified by +range+ of indices.
00685  *
00686  *  Negative indices count backward from the end of the array (-1 is the last
00687  *  element).  For +start+ and +range+ cases the starting index is just before
00688  *  an element.  Additionally, an empty array is returned when the starting
00689  *  index for an element range is at the end of the array.
00690  *
00691  *  Returns +nil+ if the index (or starting index) are out of range.
00692  *
00693  *  a = [ "a", "b", "c", "d", "e" ]
00694  *  a[1]     => "b"
00695  *  a[1,2]   => ["b", "c"]
00696  *  a[1..-2] => ["b", "c", "d"]
00697  *
00698  */
00699 
00700 static mrb_value
00701 mrb_ary_aget(mrb_state *mrb, mrb_value self)
00702 {
00703   struct RArray *a = mrb_ary_ptr(self);
00704   mrb_int i, len;
00705   mrb_value index;
00706 
00707   if (mrb_get_args(mrb, "o|i", &index, &len) == 1) {
00708     switch (mrb_type(index)) {
00709       /* a[n..m] */
00710     case MRB_TT_RANGE:
00711       if (mrb_range_beg_len(mrb, index, &i, &len, a->len)) {
00712         return ary_subseq(mrb, a, i, len);
00713       }
00714       else {
00715         return mrb_nil_value();
00716       }
00717     case MRB_TT_FIXNUM:
00718       return mrb_ary_ref(mrb, self, mrb_fixnum(index));
00719     default:
00720       return mrb_ary_ref(mrb, self, aget_index(mrb, index));
00721     }
00722   }
00723 
00724   i = aget_index(mrb, index);
00725   if (i < 0) i += a->len;
00726   if (i < 0 || a->len < i) return mrb_nil_value();
00727   if (len < 0) return mrb_nil_value();
00728   if (a->len == i) return mrb_ary_new(mrb);
00729   if (len > a->len - i) len = a->len - i;
00730 
00731   return ary_subseq(mrb, a, i, len);
00732 }
00733 
00734 /*
00735  *  call-seq:
00736  *     ary[index]         = obj                      ->  obj
00737  *     ary[start, length] = obj or other_ary or nil  ->  obj or other_ary or nil
00738  *     ary[range]         = obj or other_ary or nil  ->  obj or other_ary or nil
00739  *
00740  *  Element Assignment --- Sets the element at +index+, or replaces a subarray
00741  *  from the +start+ index for +length+ elements, or replaces a subarray
00742  *  specified by the +range+ of indices.
00743  *
00744  *  If indices are greater than the current capacity of the array, the array
00745  *  grows automatically.  Elements are inserted into the array at +start+ if
00746  *  +length+ is zero.
00747  *
00748  *  Negative indices will count backward from the end of the array.  For
00749  *  +start+ and +range+ cases the starting index is just before an element.
00750  *
00751  *  An IndexError is raised if a negative index points past the beginning of
00752  *  the array.
00753  *
00754  *  See also Array#push, and Array#unshift.
00755  *
00756  *     a = Array.new
00757  *     a[4] = "4";                 #=> [nil, nil, nil, nil, "4"]
00758  *     a[0, 3] = [ 'a', 'b', 'c' ] #=> ["a", "b", "c", nil, "4"]
00759  *     a[1..2] = [ 1, 2 ]          #=> ["a", 1, 2, nil, "4"]
00760  *     a[0, 2] = "?"               #=> ["?", 2, nil, "4"]
00761  *     a[0..2] = "A"               #=> ["A", "4"]
00762  *     a[-1]   = "Z"               #=> ["A", "Z"]
00763  *     a[1..-1] = nil              #=> ["A", nil]
00764  *     a[1..-1] = []               #=> ["A"]
00765  *     a[0, 0] = [ 1, 2 ]          #=> [1, 2, "A"]
00766  *     a[3, 0] = "B"               #=> [1, 2, "A", "B"]
00767  */
00768 
00769 static mrb_value
00770 mrb_ary_aset(mrb_state *mrb, mrb_value self)
00771 {
00772   mrb_value v1, v2, v3;
00773   mrb_int i, len;
00774 
00775   if (mrb_get_args(mrb, "oo|o", &v1, &v2, &v3) == 2) {
00776     switch (mrb_type(v1)) {
00777     /* a[n..m] = v */
00778     case MRB_TT_RANGE:
00779       if (mrb_range_beg_len(mrb, v1, &i, &len, RARRAY_LEN(self))) {
00780         mrb_ary_splice(mrb, self, i, len, v2);
00781       }
00782       break;
00783     /* a[n] = v */
00784     case MRB_TT_FIXNUM:
00785       mrb_ary_set(mrb, self, mrb_fixnum(v1), v2);
00786       break;
00787     default:
00788       mrb_ary_set(mrb, self, aget_index(mrb, v1), v2);
00789       break;
00790     }
00791     return v2;
00792   }
00793 
00794   /* a[n,m] = v */
00795   mrb_ary_splice(mrb, self, aget_index(mrb, v1), aget_index(mrb, v2), v3);
00796   return v3;
00797 }
00798 
00799 static mrb_value
00800 mrb_ary_delete_at(mrb_state *mrb, mrb_value self)
00801 {
00802   struct RArray *a = mrb_ary_ptr(self);
00803   mrb_int   index;
00804   mrb_value val;
00805   mrb_value *ptr;
00806   mrb_int len;
00807 
00808   mrb_get_args(mrb, "i", &index);
00809   if (index < 0) index += a->len;
00810   if (index < 0 || a->len <= index) return mrb_nil_value();
00811 
00812   ary_modify(mrb, a);
00813   val = a->ptr[index];
00814 
00815   ptr = a->ptr + index;
00816   len = a->len - index;
00817   while (--len) {
00818     *ptr = *(ptr+1);
00819     ++ptr;
00820   }
00821   --a->len;
00822 
00823   ary_shrink_capa(mrb, a);
00824 
00825   return val;
00826 }
00827 
00828 static mrb_value
00829 mrb_ary_first(mrb_state *mrb, mrb_value self)
00830 {
00831   struct RArray *a = mrb_ary_ptr(self);
00832   mrb_int size;
00833 
00834   if (mrb_get_args(mrb, "|i", &size) == 0) {
00835     return (a->len > 0)? a->ptr[0]: mrb_nil_value();
00836   }
00837   if (size < 0) {
00838     mrb_raise(mrb, E_ARGUMENT_ERROR, "negative array size");
00839   }
00840 
00841   if (size > a->len) size = a->len;
00842   if (ARY_SHARED_P(a)) {
00843     return ary_subseq(mrb, a, 0, size);
00844   }
00845   return mrb_ary_new_from_values(mrb, size, a->ptr);
00846 }
00847 
00848 static mrb_value
00849 mrb_ary_last(mrb_state *mrb, mrb_value self)
00850 {
00851   struct RArray *a = mrb_ary_ptr(self);
00852   mrb_int size;
00853 
00854   if (mrb_get_args(mrb, "|i", &size) == 0)
00855     return (a->len > 0)? a->ptr[a->len - 1]: mrb_nil_value();
00856 
00857   if (size < 0) {
00858     mrb_raise(mrb, E_ARGUMENT_ERROR, "negative array size");
00859   }
00860   if (size > a->len) size = a->len;
00861   if (ARY_SHARED_P(a) || size > ARY_DEFAULT_LEN) {
00862     return ary_subseq(mrb, a, a->len - size, size);
00863   }
00864   return mrb_ary_new_from_values(mrb, size, a->ptr + a->len - size);
00865 }
00866 
00867 static mrb_value
00868 mrb_ary_index_m(mrb_state *mrb, mrb_value self)
00869 {
00870   mrb_value obj;
00871   mrb_int i;
00872 
00873   mrb_get_args(mrb, "o", &obj);
00874   for (i = 0; i < RARRAY_LEN(self); i++) {
00875     if (mrb_equal(mrb, RARRAY_PTR(self)[i], obj)) {
00876       return mrb_fixnum_value(i);
00877     }
00878   }
00879   return mrb_nil_value();
00880 }
00881 
00882 static mrb_value
00883 mrb_ary_rindex_m(mrb_state *mrb, mrb_value self)
00884 {
00885   mrb_value obj;
00886   mrb_int i;
00887 
00888   mrb_get_args(mrb, "o", &obj);
00889   for (i = RARRAY_LEN(self) - 1; i >= 0; i--) {
00890     if (mrb_equal(mrb, RARRAY_PTR(self)[i], obj)) {
00891       return mrb_fixnum_value(i);
00892     }
00893   }
00894   return mrb_nil_value();
00895 }
00896 
00897 MRB_API mrb_value
00898 mrb_ary_splat(mrb_state *mrb, mrb_value v)
00899 {
00900   if (mrb_array_p(v)) {
00901     return v;
00902   }
00903   if (mrb_respond_to(mrb, v, mrb_intern_lit(mrb, "to_a"))) {
00904     return mrb_funcall(mrb, v, "to_a", 0);
00905   }
00906   else {
00907     return mrb_ary_new_from_values(mrb, 1, &v);
00908   }
00909 }
00910 
00911 static mrb_value
00912 mrb_ary_size(mrb_state *mrb, mrb_value self)
00913 {
00914   struct RArray *a = mrb_ary_ptr(self);
00915 
00916   return mrb_fixnum_value(a->len);
00917 }
00918 
00919 MRB_API mrb_value
00920 mrb_ary_clear(mrb_state *mrb, mrb_value self)
00921 {
00922   struct RArray *a = mrb_ary_ptr(self);
00923 
00924   if (ARY_SHARED_P(a)) {
00925     mrb_ary_decref(mrb, a->aux.shared);
00926     ARY_UNSET_SHARED_FLAG(a);
00927   }
00928   else {
00929     mrb_free(mrb, a->ptr);
00930   }
00931   a->len = 0;
00932   a->aux.capa = 0;
00933   a->ptr = 0;
00934 
00935   return self;
00936 }
00937 
00938 static mrb_value
00939 mrb_ary_empty_p(mrb_state *mrb, mrb_value self)
00940 {
00941   struct RArray *a = mrb_ary_ptr(self);
00942 
00943   return mrb_bool_value(a->len == 0);
00944 }
00945 
00946 MRB_API mrb_value
00947 mrb_check_array_type(mrb_state *mrb, mrb_value ary)
00948 {
00949   return mrb_check_convert_type(mrb, ary, MRB_TT_ARRAY, "Array", "to_ary");
00950 }
00951 
00952 MRB_API mrb_value
00953 mrb_ary_entry(mrb_value ary, mrb_int offset)
00954 {
00955   if (offset < 0) {
00956     offset += RARRAY_LEN(ary);
00957   }
00958   return ary_elt(ary, offset);
00959 }
00960 
00961 static mrb_value
00962 join_ary(mrb_state *mrb, mrb_value ary, mrb_value sep, mrb_value list)
00963 {
00964   mrb_int i;
00965   mrb_value result, val, tmp;
00966 
00967   /* check recursive */
00968   for (i=0; i<RARRAY_LEN(list); i++) {
00969     if (mrb_obj_equal(mrb, ary, RARRAY_PTR(list)[i])) {
00970       mrb_raise(mrb, E_ARGUMENT_ERROR, "recursive array join");
00971     }
00972   }
00973 
00974   mrb_ary_push(mrb, list, ary);
00975 
00976   result = mrb_str_buf_new(mrb, 64);
00977 
00978   for (i=0; i<RARRAY_LEN(ary); i++) {
00979     if (i > 0 && !mrb_nil_p(sep)) {
00980       mrb_str_cat_str(mrb, result, sep);
00981     }
00982 
00983     val = RARRAY_PTR(ary)[i];
00984     switch (mrb_type(val)) {
00985     case MRB_TT_ARRAY:
00986     ary_join:
00987       val = join_ary(mrb, val, sep, list);
00988       /* fall through */
00989 
00990     case MRB_TT_STRING:
00991     str_join:
00992       mrb_str_cat_str(mrb, result, val);
00993       break;
00994 
00995     default:
00996       tmp = mrb_check_string_type(mrb, val);
00997       if (!mrb_nil_p(tmp)) {
00998         val = tmp;
00999         goto str_join;
01000       }
01001       tmp = mrb_check_convert_type(mrb, val, MRB_TT_ARRAY, "Array", "to_ary");
01002       if (!mrb_nil_p(tmp)) {
01003         val = tmp;
01004         goto ary_join;
01005       }
01006       val = mrb_obj_as_string(mrb, val);
01007       goto str_join;
01008     }
01009   }
01010 
01011   mrb_ary_pop(mrb, list);
01012 
01013   return result;
01014 }
01015 
01016 MRB_API mrb_value
01017 mrb_ary_join(mrb_state *mrb, mrb_value ary, mrb_value sep)
01018 {
01019   sep = mrb_obj_as_string(mrb, sep);
01020   return join_ary(mrb, ary, sep, mrb_ary_new(mrb));
01021 }
01022 
01023 /*
01024  *  call-seq:
01025  *     ary.join(sep="")    -> str
01026  *
01027  *  Returns a string created by converting each element of the array to
01028  *  a string, separated by <i>sep</i>.
01029  *
01030  *     [ "a", "b", "c" ].join        #=> "abc"
01031  *     [ "a", "b", "c" ].join("-")   #=> "a-b-c"
01032  */
01033 
01034 static mrb_value
01035 mrb_ary_join_m(mrb_state *mrb, mrb_value ary)
01036 {
01037   mrb_value sep = mrb_nil_value();
01038 
01039   mrb_get_args(mrb, "|S", &sep);
01040   return mrb_ary_join(mrb, ary, sep);
01041 }
01042 
01043 static mrb_value
01044 mrb_ary_eq(mrb_state *mrb, mrb_value ary1)
01045 {
01046   mrb_value ary2;
01047 
01048   mrb_get_args(mrb, "o", &ary2);
01049   if (mrb_obj_equal(mrb, ary1, ary2)) return mrb_true_value();
01050   if (mrb_immediate_p(ary2)) return mrb_false_value();
01051   if (!mrb_array_p(ary2)) {
01052     return mrb_false_value();
01053   }
01054   if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return mrb_false_value();
01055 
01056   return ary2;
01057 }
01058 
01059 static mrb_value
01060 mrb_ary_cmp(mrb_state *mrb, mrb_value ary1)
01061 {
01062   mrb_value ary2;
01063 
01064   mrb_get_args(mrb, "o", &ary2);
01065   if (mrb_obj_equal(mrb, ary1, ary2)) return mrb_fixnum_value(0);
01066   if (mrb_immediate_p(ary2)) return mrb_nil_value();
01067   if (!mrb_array_p(ary2)) {
01068     return mrb_nil_value();
01069   }
01070 
01071   return ary2;
01072 }
01073 
01074 void
01075 mrb_init_array(mrb_state *mrb)
01076 {
01077   struct RClass *a;
01078 
01079   a = mrb->array_class = mrb_define_class(mrb, "Array", mrb->object_class);            /* 15.2.12 */
01080   MRB_SET_INSTANCE_TT(a, MRB_TT_ARRAY);
01081 
01082   mrb_define_class_method(mrb, a, "[]",        mrb_ary_s_create,     MRB_ARGS_ANY());  /* 15.2.12.4.1 */
01083 
01084   mrb_define_method(mrb, a, "+",               mrb_ary_plus,         MRB_ARGS_REQ(1)); /* 15.2.12.5.1  */
01085   mrb_define_method(mrb, a, "*",               mrb_ary_times,        MRB_ARGS_REQ(1)); /* 15.2.12.5.2  */
01086   mrb_define_method(mrb, a, "<<",              mrb_ary_push_m,       MRB_ARGS_REQ(1)); /* 15.2.12.5.3  */
01087   mrb_define_method(mrb, a, "[]",              mrb_ary_aget,         MRB_ARGS_ANY());  /* 15.2.12.5.4  */
01088   mrb_define_method(mrb, a, "[]=",             mrb_ary_aset,         MRB_ARGS_ANY());  /* 15.2.12.5.5  */
01089   mrb_define_method(mrb, a, "clear",           mrb_ary_clear,        MRB_ARGS_NONE()); /* 15.2.12.5.6  */
01090   mrb_define_method(mrb, a, "concat",          mrb_ary_concat_m,     MRB_ARGS_REQ(1)); /* 15.2.12.5.8  */
01091   mrb_define_method(mrb, a, "delete_at",       mrb_ary_delete_at,    MRB_ARGS_REQ(1)); /* 15.2.12.5.9  */
01092   mrb_define_method(mrb, a, "empty?",          mrb_ary_empty_p,      MRB_ARGS_NONE()); /* 15.2.12.5.12 */
01093   mrb_define_method(mrb, a, "first",           mrb_ary_first,        MRB_ARGS_OPT(1)); /* 15.2.12.5.13 */
01094   mrb_define_method(mrb, a, "index",           mrb_ary_index_m,      MRB_ARGS_REQ(1)); /* 15.2.12.5.14 */
01095   mrb_define_method(mrb, a, "initialize_copy", mrb_ary_replace_m,    MRB_ARGS_REQ(1)); /* 15.2.12.5.16 */
01096   mrb_define_method(mrb, a, "join",            mrb_ary_join_m,       MRB_ARGS_ANY());  /* 15.2.12.5.17 */
01097   mrb_define_method(mrb, a, "last",            mrb_ary_last,         MRB_ARGS_ANY());  /* 15.2.12.5.18 */
01098   mrb_define_method(mrb, a, "length",          mrb_ary_size,         MRB_ARGS_NONE()); /* 15.2.12.5.19 */
01099   mrb_define_method(mrb, a, "pop",             mrb_ary_pop,          MRB_ARGS_NONE()); /* 15.2.12.5.21 */
01100   mrb_define_method(mrb, a, "push",            mrb_ary_push_m,       MRB_ARGS_ANY());  /* 15.2.12.5.22 */
01101   mrb_define_method(mrb, a, "replace",         mrb_ary_replace_m,    MRB_ARGS_REQ(1)); /* 15.2.12.5.23 */
01102   mrb_define_method(mrb, a, "reverse",         mrb_ary_reverse,      MRB_ARGS_NONE()); /* 15.2.12.5.24 */
01103   mrb_define_method(mrb, a, "reverse!",        mrb_ary_reverse_bang, MRB_ARGS_NONE()); /* 15.2.12.5.25 */
01104   mrb_define_method(mrb, a, "rindex",          mrb_ary_rindex_m,     MRB_ARGS_REQ(1)); /* 15.2.12.5.26 */
01105   mrb_define_method(mrb, a, "shift",           mrb_ary_shift,        MRB_ARGS_NONE()); /* 15.2.12.5.27 */
01106   mrb_define_method(mrb, a, "size",            mrb_ary_size,         MRB_ARGS_NONE()); /* 15.2.12.5.28 */
01107   mrb_define_method(mrb, a, "slice",           mrb_ary_aget,         MRB_ARGS_ANY());  /* 15.2.12.5.29 */
01108   mrb_define_method(mrb, a, "unshift",         mrb_ary_unshift_m,    MRB_ARGS_ANY());  /* 15.2.12.5.30 */
01109 
01110   mrb_define_method(mrb, a, "__ary_eq",        mrb_ary_eq,           MRB_ARGS_REQ(1));
01111   mrb_define_method(mrb, a, "__ary_cmp",       mrb_ary_cmp,          MRB_ARGS_REQ(1));
01112 }
01113