1: /**********************************************************************
    2: 
    3:   array.c -
    4: 
    5:   $Author: akr $
    6:   $Date: 2007-12-24 17:19:28 +0900 (Mon, 24 Dec 2007) $
    7:   created at: Fri Aug  6 09:46:12 JST 1993
    8: 
    9:   Copyright (C) 1993-2007 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/ruby.h"
   16: #include "ruby/util.h"
   17: #include "ruby/st.h"
   18: 
   19: VALUE rb_cArray;
   20: 
   21: static ID id_cmp;
   22: 
   23: #define ARY_DEFAULT_SIZE 16
   24: 
   25: void
   26: rb_mem_clear(register VALUE *mem, register long size)
   27: {
   28:     while (size--) {
   29:         *mem++ = Qnil;
   30:     }
   31: }
   32: 
   33: static inline void
   34: memfill(register VALUE *mem, register long size, register VALUE val)
   35: {
   36:     while (size--) {
   37:         *mem++ = val;
   38:     }
   39: }
   40: 
   41: #define ARY_ITERLOCK FL_USER1
   42: static void
   43: ary_iter_check(VALUE ary)
   44: {
   45:     if (FL_TEST(ary, ARY_ITERLOCK)) {
   46:       rb_raise(rb_eRuntimeError, "can't modify array during iteration");
   47:     }
   48: }
   49: #define ARY_SORTLOCK FL_USER3
   50: #define ARY_SHARED_P(a) FL_TEST(a, ELTS_SHARED)
   51: 
   52: #define ARY_SET_LEN(ary, n) do { \
   53:     RARRAY(ary)->len = (n);\
   54: } while (0) 
   55: 
   56: #define ARY_CAPA(ary) RARRAY(ary)->aux.capa
   57: #define RESIZE_CAPA(ary,capacity) do {\
   58:     REALLOC_N(RARRAY(ary)->ptr, VALUE, (capacity));\
   59:     RARRAY(ary)->aux.capa = (capacity);\
   60: } while (0)
   61: 
   62: #define ITERATE(func, ary) do { \
   63:     FL_SET(ary, ARY_ITERLOCK); \
   64:     return rb_ensure(func, (ary), each_unlock, (ary));\
   65: } while (0)
   66: 
   67: static inline void
   68: rb_ary_modify_check(VALUE ary)
   69: {
   70:     if (OBJ_FROZEN(ary)) rb_error_frozen("array");
   71:     if (FL_TEST(ary, ARY_SORTLOCK))
   72:         rb_raise(rb_eRuntimeError, "can't modify array during sort");
   73:     if (!OBJ_TAINTED(ary) && rb_safe_level() >= 4)
   74:         rb_raise(rb_eSecurityError, "Insecure: can't modify array");
   75: }
   76: 
   77: static void
   78: rb_ary_modify(VALUE ary)
   79: {
   80:     VALUE *ptr;
   81: 
   82:     rb_ary_modify_check(ary);
   83:     if (ARY_SHARED_P(ary)) {
   84:         ptr = ALLOC_N(VALUE, RARRAY_LEN(ary));
   85:         FL_UNSET(ary, ELTS_SHARED);
   86:         RARRAY(ary)->aux.capa = RARRAY_LEN(ary);
   87:         MEMCPY(ptr, RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
   88:         RARRAY(ary)->ptr = ptr;
   89:     }
   90: }
   91: 
   92: VALUE
   93: rb_ary_freeze(VALUE ary)
   94: {
   95:     return rb_obj_freeze(ary);
   96: }
   97: 
   98: /*
   99:  *  call-seq:
  100:  *     array.frozen?  -> true or false
  101:  *
  102:  *  Return <code>true</code> if this array is frozen (or temporarily frozen
  103:  *  while being sorted).
  104:  */
  105: 
  106: static VALUE
  107: rb_ary_frozen_p(VALUE ary)
  108: {
  109:     if (OBJ_FROZEN(ary)) return Qtrue;
  110:     if (FL_TEST(ary, ARY_SORTLOCK)) return Qtrue;
  111:     return Qfalse;
  112: }
  113: 
  114: static VALUE
  115: ary_alloc(VALUE klass)
  116: {
  117:     NEWOBJ(ary, struct RArray);
  118:     OBJSETUP(ary, klass, T_ARRAY);
  119: 
  120:     ary->len = 0;
  121:     ary->ptr = 0;
  122:     ary->aux.capa = 0;
  123: 
  124:     return (VALUE)ary;
  125: }
  126: 
  127: static VALUE
  128: ary_new(VALUE klass, long len)
  129: {
  130:     VALUE ary;
  131: 
  132:     if (len < 0) {
  133:         rb_raise(rb_eArgError, "negative array size (or size too big)");
  134:     }
  135:     if (len > 0 && len * sizeof(VALUE) <= len) {
  136:         rb_raise(rb_eArgError, "array size too big");
  137:     }
  138:     ary = ary_alloc(klass);
  139:     if (len == 0) len++;
  140:     RARRAY(ary)->ptr = ALLOC_N(VALUE, len);
  141:     RARRAY(ary)->aux.capa = len;
  142: 
  143:     return ary;
  144: }
  145: 
  146: VALUE
  147: rb_ary_new2(long len)
  148: {
  149:     return ary_new(rb_cArray, len);
  150: }
  151: 
  152: 
  153: VALUE
  154: rb_ary_new(void)
  155: {
  156:     return rb_ary_new2(ARY_DEFAULT_SIZE);
  157: }
  158: 
  159: #include <stdarg.h>
  160: 
  161: VALUE
  162: rb_ary_new3(long n, ...)
  163: {
  164:     va_list ar;
  165:     VALUE ary;
  166:     long i;
  167: 
  168:     ary = rb_ary_new2(n);
  169: 
  170:     va_start(ar, n);
  171:     for (i=0; i<n; i++) {
  172:         RARRAY_PTR(ary)[i] = va_arg(ar, VALUE);
  173:     }
  174:     va_end(ar);
  175: 
  176:     RARRAY(ary)->len = n;
  177:     return ary;
  178: }
  179: 
  180: VALUE
  181: rb_ary_new4(long n, const VALUE *elts)
  182: {
  183:     VALUE ary;
  184: 
  185:     ary = rb_ary_new2(n);
  186:     if (n > 0 && elts) {
  187:         MEMCPY(RARRAY_PTR(ary), elts, VALUE, n);
  188:         RARRAY(ary)->len = n;
  189:     }
  190: 
  191:     return ary;
  192: }
  193: 
  194: void
  195: rb_ary_free(VALUE ary)
  196: {
  197:     if (!ARY_SHARED_P(ary)) {
  198:         xfree(RARRAY(ary)->ptr);
  199:     }
  200: }
  201: 
  202: static VALUE
  203: ary_make_shared(VALUE ary)
  204: {
  205:     if (ARY_SHARED_P(ary)) {
  206:         return RARRAY(ary)->aux.shared;
  207:     }
  208:     else {
  209:         NEWOBJ(shared, struct RArray);
  210:         OBJSETUP(shared, 0, T_ARRAY);
  211: 
  212:         shared->len = RARRAY(ary)->len;
  213:         shared->ptr = RARRAY(ary)->ptr;
  214:         shared->aux.capa = RARRAY(ary)->aux.capa;
  215:         RARRAY(ary)->aux.shared = (VALUE)shared;
  216:         FL_SET(ary, ELTS_SHARED);
  217:         OBJ_FREEZE(shared);
  218:         return (VALUE)shared;
  219:     }
  220: }
  221: 
  222: VALUE
  223: rb_assoc_new(VALUE car, VALUE cdr)
  224: {
  225:     return rb_ary_new3(2, car, cdr);
  226: }
  227: 
  228: static VALUE
  229: to_ary(VALUE ary)
  230: {
  231:     return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
  232: }
  233: 
  234: VALUE
  235: rb_check_array_type(VALUE ary)
  236: {
  237:     return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
  238: }
  239: 
  240: /*
  241:  *  call-seq:
  242:  *     Array.try_convert(obj) -> array or nil
  243:  *
  244:  *  Try to convert <i>obj</i> into an array, using to_ary method.
  245:  *  Returns converted array or nil if <i>obj</i> cannot be converted
  246:  *  for any reason.  This method is to check if an argument is an
  247:  *  array.  
  248:  *
  249:  *     Array.try_convert([1])   # => [1]
  250:  *     Array.try_convert("1")   # => nil
  251:  *     
  252:  *     if tmp = Array.try_convert(arg)
  253:  *       # the argument is an array
  254:  *     elsif tmp = String.try_convert(arg)
  255:  *       # the argument is a string
  256:  *     end
  257:  *
  258:  */
  259: 
  260: static VALUE
  261: rb_ary_s_try_convert(VALUE dummy, VALUE ary)
  262: {
  263:     return rb_check_array_type(ary);
  264: }
  265: 
  266: /*
  267:  *  call-seq:
  268:  *     Array.new(size=0, obj=nil)
  269:  *     Array.new(array)
  270:  *     Array.new(size) {|index| block }
  271:  *
  272:  *  Returns a new array. In the first form, the new array is
  273:  *  empty. In the second it is created with _size_ copies of _obj_
  274:  *  (that is, _size_ references to the same
  275:  *  _obj_). The third form creates a copy of the array
  276:  *  passed as a parameter (the array is generated by calling
  277:  *  to_ary  on the parameter). In the last form, an array
  278:  *  of the given size is created. Each element in this array is
  279:  *  calculated by passing the element's index to the given block and
  280:  *  storing the return value.
  281:  *
  282:  *     Array.new
  283:  *     Array.new(2)
  284:  *     Array.new(5, "A")
  285:  * 
  286:  *     # only one copy of the object is created
  287:  *     a = Array.new(2, Hash.new)
  288:  *     a[0]['cat'] = 'feline'
  289:  *     a
  290:  *     a[1]['cat'] = 'Felix'
  291:  *     a
  292:  * 
  293:  *     # here multiple copies are created
  294:  *     a = Array.new(2) { Hash.new }
  295:  *     a[0]['cat'] = 'feline'
  296:  *     a
  297:  * 
  298:  *     squares = Array.new(5) {|i| i*i}
  299:  *     squares
  300:  * 
  301:  *     copy = Array.new(squares)
  302:  */
  303: 
  304: static VALUE
  305: rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
  306: {
  307:     long len;
  308:     VALUE size, val;
  309: 
  310:     rb_ary_modify(ary);
  311:     ary_iter_check(ary);
  312:     if (rb_scan_args(argc, argv, "02", &size, &val) == 0) {
  313:         if (RARRAY_PTR(ary) && !ARY_SHARED_P(ary)) {
  314:             free(RARRAY(ary)->ptr);
  315:         }
  316:         RARRAY(ary)->len = 0;
  317:         if (rb_block_given_p()) {
  318:             rb_warning("given block not used");
  319:         }
  320:         return ary;
  321:     }
  322: 
  323:     if (argc == 1 && !FIXNUM_P(size)) {
  324:         val = rb_check_array_type(size);
  325:         if (!NIL_P(val)) {
  326:             rb_ary_replace(ary, val);
  327:             return ary;
  328:         }
  329:     }
  330: 
  331:     len = NUM2LONG(size);
  332:     if (len < 0) {
  333:         rb_raise(rb_eArgError, "negative array size");
  334:     }
  335:     if (len > 0 && len * (long)sizeof(VALUE) <= len) {
  336:         rb_raise(rb_eArgError, "array size too big");
  337:     }
  338:     rb_ary_modify(ary);
  339:         RESIZE_CAPA(ary, len);
  340:     if (rb_block_given_p()) {
  341:         long i;
  342: 
  343:         if (argc == 2) {
  344:             rb_warn("block supersedes default value argument");
  345:         }
  346:         for (i=0; i<len; i++) {
  347:             rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
  348:             RARRAY(ary)->len = i + 1;
  349:         }
  350:     }
  351:     else {
  352:         memfill(RARRAY_PTR(ary), len, val);
  353:         RARRAY(ary)->len = len;
  354:     }
  355:     return ary;
  356: }
  357: 
  358: 
  359: /* 
  360: * Returns a new array populated with the given objects. 
  361: *
  362: *   Array.[]( 1, 'a', /^A/ )
  363: *   Array[ 1, 'a', /^A/ ]
  364: *   [ 1, 'a', /^A/ ]
  365: */
  366: 
  367: static VALUE
  368: rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
  369: {
  370:     VALUE ary = ary_alloc(klass);
  371: 
  372:     if (argc < 0) {
  373:         rb_raise(rb_eArgError, "negative array size");
  374:     }
  375:     RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
  376:     RARRAY(ary)->aux.capa = argc;
  377:     MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
  378:     RARRAY(ary)->len = argc;
  379: 
  380:     return ary;
  381: }
  382: 
  383: void
  384: rb_ary_store(VALUE ary, long idx, VALUE val)
  385: {
  386:     if (idx < 0) {
  387:         idx += RARRAY_LEN(ary);
  388:         if (idx < 0) {
  389:             rb_raise(rb_eIndexError, "index %ld out of array",
  390:                     idx - RARRAY_LEN(ary));
  391:         }
  392:     }
  393: 
  394:     rb_ary_modify(ary);
  395:     if (idx >= ARY_CAPA(ary)) {
  396:         long new_capa = ARY_CAPA(ary) / 2;
  397: 
  398:         if (new_capa < ARY_DEFAULT_SIZE) {
  399:             new_capa = ARY_DEFAULT_SIZE;
  400:         }
  401:         if (new_capa + idx < new_capa) {
  402:             rb_raise(rb_eArgError, "index too big");
  403:         }
  404:         new_capa += idx;
  405:         if (new_capa * (long)sizeof(VALUE) <= new_capa) {
  406:             rb_raise(rb_eArgError, "index too big");
  407:         }
  408:         RESIZE_CAPA(ary, new_capa);
  409:     }
  410:     if (idx > RARRAY_LEN(ary)) {
  411:         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary),
  412:                      idx-RARRAY_LEN(ary) + 1);
  413:     }
  414: 
  415:     if (idx >= RARRAY_LEN(ary)) {
  416:         RARRAY(ary)->len = idx + 1;
  417:     }
  418:     RARRAY_PTR(ary)[idx] = val;
  419: }
  420: 
  421: static VALUE
  422: ary_shared_array(VALUE klass, VALUE ary)
  423: {
  424:     VALUE val = ary_alloc(klass);
  425: 
  426:     ary_make_shared(ary);
  427:     RARRAY(val)->ptr = RARRAY(ary)->ptr;
  428:     RARRAY(val)->len = RARRAY(ary)->len;
  429:     RARRAY(val)->aux.shared = RARRAY(ary)->aux.shared;
  430:     FL_SET(val, ELTS_SHARED);
  431:     return val;
  432: }
  433: 
  434: static VALUE
  435: ary_shared_first(int argc, VALUE *argv, VALUE ary, int last)
  436: {
  437:     VALUE nv, result;
  438:     long n;
  439:     long offset = 0;
  440: 
  441:     rb_scan_args(argc, argv, "1", &nv);
  442:     n = NUM2LONG(nv);
  443:     if (n > RARRAY_LEN(ary)) {
  444:         n = RARRAY_LEN(ary);
  445:     }
  446:     else if (n < 0) {
  447:         rb_raise(rb_eArgError, "negative array size");
  448:     }
  449:     if (last) {
  450:         offset = RARRAY_LEN(ary) - n;
  451:     }
  452:     result = ary_shared_array(rb_cArray, ary);
  453:     RARRAY(result)->ptr += offset;
  454:     RARRAY(result)->len = n;
  455: 
  456:     return result;
  457: }
  458: 
  459: /*
  460:  *  call-seq:
  461:  *     array << obj            -> array
  462:  *  
  463:  *  Append---Pushes the given object on to the end of this array. This
  464:  *  expression returns the array itself, so several appends
  465:  *  may be chained together.
  466:  *
  467:  *     [ 1, 2 ] << "c" << "d" << [ 3, 4 ]
  468:  *             #=>  [ 1, 2, "c", "d", [ 3, 4 ] ]
  469:  *
  470:  */
  471: 
  472: VALUE
  473: rb_ary_push(VALUE ary, VALUE item)
  474: {
  475:     rb_ary_store(ary, RARRAY_LEN(ary), item);
  476:     return ary;
  477: }
  478: 
  479: /* 
  480:  *  call-seq:
  481:  *     array.push(obj, ... )   -> array
  482:  *  
  483:  *  Append---Pushes the given object(s) on to the end of this array. This
  484:  *  expression returns the array itself, so several appends
  485:  *  may be chained together.
  486:  *
  487:  *     a = [ "a", "b", "c" ]
  488:  *     a.push("d", "e", "f")  
  489:  *             #=> ["a", "b", "c", "d", "e", "f"]
  490:  */
  491: 
  492: static VALUE
  493: rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
  494: {
  495:     while (argc--) {
  496:         rb_ary_push(ary, *argv++);
  497:     }
  498:     return ary;
  499: }
  500: 
  501: VALUE
  502: rb_ary_pop(VALUE ary)
  503: {
  504:     long n;
  505:     rb_ary_modify_check(ary);
  506:     if (RARRAY_LEN(ary) == 0) return Qnil;
  507:     if (!ARY_SHARED_P(ary) &&
  508:         RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
  509:         ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
  510:     {
  511:         RESIZE_CAPA(ary, RARRAY_LEN(ary) * 2);
  512:     }
  513:     n = RARRAY_LEN(ary)-1;
  514:     RARRAY(ary)->len = n;
  515:     return RARRAY_PTR(ary)[n];
  516: }
  517: 
  518: /*
  519:  *  call-seq:
  520:  *     array.pop  -> obj or nil
  521:  *  
  522:  *  Removes the last element from <i>self</i> and returns it, or
  523:  *  <code>nil</code> if the array is empty.
  524:  *     
  525:  *     a = [ "a", "b", "c", "d" ]
  526:  *     a.pop     #=> "d"
  527:  *     a.pop(2)  #=> ["b", "c"]
  528:  *     a         #=> ["a"]
  529:  */
  530: 
  531: static VALUE
  532: rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
  533: {
  534:     VALUE result;
  535: 
  536:     if (argc == 0) {
  537:         return rb_ary_pop(ary);
  538:     }
  539: 
  540:     rb_ary_modify_check(ary);
  541:     result = ary_shared_first(argc, argv, ary, Qtrue);
  542:     RARRAY(ary)->len -= RARRAY_LEN(result);
  543:     return result;
  544: }
  545: 
  546: VALUE
  547: rb_ary_shift(VALUE ary)
  548: {
  549:     VALUE top;
  550: 
  551:     rb_ary_modify_check(ary);
  552:     ary_iter_check(ary);
  553:     if (RARRAY_LEN(ary) == 0) return Qnil;
  554:     top = RARRAY_PTR(ary)[0];
  555:     if (!ARY_SHARED_P(ary)) {
  556:         if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
  557:             MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
  558:             RARRAY(ary)->len--;
  559:             return top;
  560:         }
  561:         RARRAY_PTR(ary)[0] = Qnil;
  562:         ary_make_shared(ary);
  563:     }
  564:     RARRAY(ary)->ptr++;         /* shift ptr */
  565:     RARRAY(ary)->len--;
  566: 
  567:     return top;
  568: }
  569: 
  570: /*
  571:  *  call-seq:
  572:  *     array.shift   ->   obj or nil
  573:  *  
  574:  *  Returns the first element of <i>self</i> and removes it (shifting all
  575:  *  other elements down by one). Returns <code>nil</code> if the array
  576:  *  is empty.
  577:  *     
  578:  *     args = [ "-m", "-q", "filename" ]
  579:  *     args.shift     #=> "-m"
  580:  *     args           #=> ["-q", "filename"]
  581:  *
  582:  *     args = [ "-m", "-q", "filename" ]
  583:  *     args.shift(2)  #=> ["-m", "-q"]
  584:  *     args           #=> ["filename"]
  585:  */
  586: 
  587: static VALUE
  588: rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
  589: {
  590:     VALUE result;
  591:     long n;
  592: 
  593:     if (argc == 0) {
  594:         return rb_ary_shift(ary);
  595:     }
  596: 
  597:     rb_ary_modify_check(ary);
  598:     ary_iter_check(ary);
  599:     result = ary_shared_first(argc, argv, ary, Qfalse);
  600:     n = RARRAY_LEN(result);
  601:     if (ARY_SHARED_P(ary)) {
  602:         RARRAY(ary)->ptr += n;
  603:         RARRAY(ary)->len -= n;
  604:         }
  605:     else {
  606:         MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
  607:         RARRAY(ary)->len -= n;
  608:     }
  609: 
  610:     return result;
  611: }
  612: 
  613: /*
  614:  *  call-seq:
  615:  *     array.unshift(obj, ...)  -> array
  616:  *  
  617:  *  Prepends objects to the front of <i>array</i>.
  618:  *  other elements up one.
  619:  *     
  620:  *     a = [ "b", "c", "d" ]
  621:  *     a.unshift("a")   #=> ["a", "b", "c", "d"]
  622:  *     a.unshift(1, 2)  #=> [ 1, 2, "a", "b", "c", "d"]
  623:  */
  624: 
  625: static VALUE
  626: rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
  627: {
  628:     long len = RARRAY(ary)->len;
  629: 
  630:     if (argc == 0) return ary;
  631:     rb_ary_modify(ary);
  632:     ary_iter_check(ary);
  633:     if (RARRAY(ary)->aux.capa <= RARRAY_LEN(ary)+argc) {
  634:         RESIZE_CAPA(ary, RARRAY(ary)->aux.capa + ARY_DEFAULT_SIZE);
  635:     }
  636: 
  637:     /* sliding items */
  638:     MEMMOVE(RARRAY(ary)->ptr + argc, RARRAY(ary)->ptr, VALUE, len);
  639:     MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
  640:     RARRAY(ary)->len += argc;
  641:     
  642:     return ary;
  643: }
  644: 
  645: