Project

General

Profile

Feature #7393 ยป array_as_queue.patch

zzak (Zachary Scott), 11/19/2012 12:18 PM

View differences:

array.c
255 255
    rb_ary_modify_check(ary);
256 256
    if (ARY_SHARED_P(ary)) {
257 257
        long len = RARRAY_LEN(ary);
258
	VALUE shared = ARY_SHARED(ary);
258 259
        if (len <= RARRAY_EMBED_LEN_MAX) {
259 260
            VALUE *ptr = ARY_HEAP_PTR(ary);
260
            VALUE shared = ARY_SHARED(ary);
261 261
            FL_UNSET_SHARED(ary);
262 262
            FL_SET_EMBED(ary);
263 263
            MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
264 264
            rb_ary_decrement_share(shared);
265 265
            ARY_SET_EMBED_LEN(ary, len);
266 266
        }
267
	else if (ARY_SHARED_NUM(shared) == 1 && len > RARRAY_LEN(shared)>>1) {
268
	    long shift = RARRAY_PTR(ary) - RARRAY_PTR(shared);
269
	    ARY_SET_PTR(ary, RARRAY_PTR(shared));
270
	    ARY_SET_CAPA(ary, RARRAY_LEN(shared));
271
	    MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+shift, VALUE, len);
272
	    FL_UNSET_SHARED(ary);
273
            FL_SET_EMBED(shared);
274
	    rb_ary_decrement_share(shared);
275
	}
267 276
        else {
268 277
            VALUE *ptr = ALLOC_N(VALUE, len);
269 278
            MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
......
440 449
	OBJSETUP(shared, 0, T_ARRAY);
441 450
        FL_UNSET_EMBED(shared);
442 451

  
443
        ARY_SET_LEN((VALUE)shared, RARRAY_LEN(ary));
452
        ARY_SET_LEN((VALUE)shared, ARY_CAPA(ary));
444 453
        ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
454
	rb_mem_clear(RARRAY_PTR(shared) + RARRAY_LEN(ary), ARY_CAPA(ary) - RARRAY_LEN(ary));
445 455
	FL_SET_SHARED_ROOT(shared);
446 456
	ARY_SET_SHARED_NUM((VALUE)shared, 1);
447 457
	FL_SET_SHARED(ary);
......
2171 2181
    if (RARRAY_LEN(ary) > 1) {
2172 2182
	VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
2173 2183
	struct ary_sort_data data;
2184
	long len = RARRAY_LEN(ary);
2174 2185

  
2175 2186
	RBASIC(tmp)->klass = 0;
2176 2187
	data.ary = tmp;
2177 2188
	data.opt_methods = 0;
2178 2189
	data.opt_inited = 0;
2179
	ruby_qsort(RARRAY_PTR(tmp), RARRAY_LEN(tmp), sizeof(VALUE),
2190
	ruby_qsort(RARRAY_PTR(tmp), len, sizeof(VALUE),
2180 2191
		   rb_block_given_p()?sort_1:sort_2, &data);
2181 2192

  
2182 2193
        if (ARY_EMBED_P(tmp)) {
......
2193 2204
            if (ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
2194 2205
                assert(!ARY_EMBED_P(ary));
2195 2206
                FL_UNSET_SHARED(ary);
2196
                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
2207
                ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2197 2208
            }
2198 2209
            else {
2199 2210
                assert(!ARY_SHARED_P(tmp));
......
2208 2219
                    xfree(ARY_HEAP_PTR(ary));
2209 2220
                }
2210 2221
                ARY_SET_PTR(ary, RARRAY_PTR(tmp));
2211
                ARY_SET_HEAP_LEN(ary, RARRAY_LEN(tmp));
2212
                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
2222
                ARY_SET_HEAP_LEN(ary, len);
2223
                ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2213 2224
            }
2214 2225
            /* tmp was lost ownership for the ptr */
2215 2226
            FL_UNSET(tmp, FL_FREEZE);
2216
- 
array.c
283 283
    }
284 284
}
285 285

  
286
static void
287
ary_ensure_room_for_push(VALUE ary, long add_len)
288
{
289
    long new_len = RARRAY_LEN(ary) + add_len;
290
    long capa;
291

  
292
    if (ARY_SHARED_P(ary)) {
293
        if (new_len > RARRAY_EMBED_LEN_MAX) {
294
            VALUE shared = ARY_SHARED(ary);
295
            if (ARY_SHARED_NUM(shared) == 1) {
296
		if (RARRAY_PTR(ary) - RARRAY_PTR(shared) + new_len <= RARRAY_LEN(shared)) {
297
		    rb_ary_modify_check(ary);
298
		}
299
		else {
300
		    /* if array is shared, than it is likely it participate in push/shift pattern */
301
		    rb_ary_modify(ary);
302
		    capa = ARY_CAPA(ary);
303
		    if (new_len > capa - (capa >> 6)) {
304
			ary_double_capa(ary, new_len);
305
		    }
306
		}
307
		return;
308
            }
309
        }
310
    }
311
    rb_ary_modify(ary);
312
    capa = ARY_CAPA(ary);
313
    if (new_len > capa) {
314
	ary_double_capa(ary, new_len);
315
    }
316
}
317

  
286 318
/*
287 319
 *  call-seq:
288 320
 *      ary.freeze -> ary
......
740 772
    return ary_make_partial(ary, rb_cArray, offset, n);
741 773
}
742 774

  
743
static VALUE rb_ary_push_1(VALUE ary, VALUE item);
744

  
745 775
/*
746 776
 *  call-seq:
747 777
 *     ary << obj            -> ary
......
758 788
VALUE
759 789
rb_ary_push(VALUE ary, VALUE item)
760 790
{
761
    rb_ary_modify(ary);
762
    return rb_ary_push_1(ary, item);
791
    long idx = RARRAY_LEN(ary);
792

  
793
    ary_ensure_room_for_push(ary, 1);
794
    RARRAY_PTR(ary)[idx] = item;
795
    ARY_SET_LEN(ary, idx + 1);
796
    return ary;
763 797
}
764 798

  
765 799
static VALUE
......
778 812
VALUE
779 813
rb_ary_cat(VALUE ary, const VALUE *ptr, long len)
780 814
{
781
    long oldlen;
815
    long oldlen = RARRAY_LEN(ary);
782 816

  
783
    rb_ary_modify(ary);
784
    oldlen = RARRAY_LEN(ary);
785
    ary_resize_capa(ary, oldlen + len);
817
    ary_ensure_room_for_push(ary, len);
786 818
    MEMCPY(RARRAY_PTR(ary) + oldlen, ptr, VALUE, len);
787 819
    ARY_SET_LEN(ary, oldlen + len);
788 820
    return ary;
789
- 
array.c
1374 1374
	rpl = rb_ary_to_ary(rpl);
1375 1375
	rlen = RARRAY_LEN(rpl);
1376 1376
    }
1377
    rb_ary_modify(ary);
1378 1377
    if (beg >= RARRAY_LEN(ary)) {
1379 1378
	if (beg > ARY_MAX_SIZE - rlen) {
1380 1379
	    rb_raise(rb_eIndexError, "index %ld too big", beg);
1381 1380
	}
1381
	ary_ensure_room_for_push(ary, rlen);
1382 1382
	len = beg + rlen;
1383
	if (len >= ARY_CAPA(ary)) {
1384
	    ary_double_capa(ary, len);
1385
	}
1386 1383
	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), beg - RARRAY_LEN(ary));
1387 1384
	if (rlen > 0) {
1388 1385
	    MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
......
1392 1389
    else {
1393 1390
	long alen;
1394 1391

  
1392
	rb_ary_modify(ary);
1395 1393
	alen = RARRAY_LEN(ary) + rlen - len;
1396 1394
	if (alen >= ARY_CAPA(ary)) {
1397 1395
	    ary_double_capa(ary, alen);
1398
- 
array.c
970 970
    return result;
971 971
}
972 972

  
973
static void
974
ary_ensure_room_for_unshift(VALUE ary, int argc)
975
{
976
    long len = RARRAY_LEN(ary);
977
    long new_len = len + argc;
978
    long capa;
979
    VALUE *head, *sharedp;
980

  
981
    if (ARY_SHARED_P(ary)) {
982
	VALUE shared = ARY_SHARED(ary);
983
	capa = RARRAY_LEN(shared);
984
	if (ARY_SHARED_NUM(shared) == 1 && capa > new_len) {
985
	    head = RARRAY_PTR(ary);
986
	    sharedp = RARRAY_PTR(shared);
987
	    goto makeroom_if_need;
988
	}
989
    }
990

  
991
    rb_ary_modify(ary);
992
    capa = ARY_CAPA(ary);
993
    if (capa - (capa >> 6) <= new_len) {
994
	ary_double_capa(ary, new_len);
995
    }
996

  
997
    /* use shared array for big "queues" */
998
    if (new_len > ARY_DEFAULT_SIZE * 4) {
999
	/* make a room for unshifted items */
1000
	capa = ARY_CAPA(ary);
1001
	ary_make_shared(ary);
1002

  
1003
	head = sharedp = RARRAY_PTR(ary);
1004
	goto makeroom;
1005
makeroom_if_need:
1006
	if (head - sharedp < argc) {
1007
	    long room;
1008
makeroom:
1009
	    room = capa - new_len;
1010
	    room -= room >> 4;
1011
	    MEMMOVE(sharedp + argc + room, head, VALUE, len);
1012
	    head = sharedp + argc + room;
1013
	}
1014
	ARY_SET_PTR(ary, head - argc);
1015
    }
1016
    else {
1017
	/* sliding items */
1018
	MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
1019
    }
1020
}
1021

  
973 1022
/*
974 1023
 *  call-seq:
975 1024
 *     ary.unshift(obj, ...)  -> ary
......
985 1034
static VALUE
986 1035
rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
987 1036
{
988
    long len;
1037
    long len = RARRAY_LEN(ary);
989 1038

  
990
    rb_ary_modify(ary);
991
    if (argc == 0) return ary;
992
    if (ARY_CAPA(ary) <= (len = RARRAY_LEN(ary)) + argc) {
993
	ary_double_capa(ary, len + argc);
1039
    if (argc == 0) {
1040
	rb_ary_modify_check(ary);
1041
	return ary;
994 1042
    }
995 1043

  
996
    /* sliding items */
997
    MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
1044
    ary_ensure_room_for_unshift(ary, argc);
998 1045
    MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
999
    ARY_INCREASE_LEN(ary, argc);
1000

  
1046
    ARY_SET_LEN(ary, len + argc);
1001 1047
    return ary;
1002 1048
}
1003 1049

  
1004
-