Feature #7393 ยป array_as_queue.patch
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 
* callseq: 
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 
* callseq: 
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 
* callseq: 
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 