2 Copyright (C) 2002-2009, Parrot Foundation.
3 License: Artistic 2.0, see README and LICENSE for details
8 src/list.c - List aka array routines
12 List is roughly based on concepts of IntList (thanks to Steve),
13 so I don't repeat them here.
15 Especially the same invariants hold, except an empty list is really
16 empty, meaning, push does first check for space.
18 The main differences are:
20 - List can hold items of different size, it's suitable for ints and PMCs
21 ..., calculations are still done in terms of items. The item_size is
22 specified at list creation time with the "type" argument.
24 If you later store different item types in the list, as stated
25 initially, you'll get probably not what you want - so don't do this.
27 - List does auto grow. The caller may implement a different behaviour if
30 - Error checking for out of bounds access is minimal, caller knows
31 better, what should be done.
33 - List structure itself is different from List_chunk, implying:
37 =item * end of list is not C<< list->prev >> but C<< list->end >>
39 =item * start of list is list->first
41 =item * the list of chunks is not closed, detecting the end is more simple
43 =item * no spare is keeped, didn't improve due to size constraints
45 =item * the List object itself doesn't move around for shift/unshift
49 - list chunks don't have C<< ->start >> and C<< ->end >>
50 fields. Instead the list has C<< ->start >>, which is start of first
51 chunk, and C<< ->cap >>, the total usable capacity in the list.
53 - number of items in chunks are not fixed, but there is a mode
54 using same sized chunks
60 =item C<enum_grow_fixed>
62 All chunks are of C<MAX_ITEMS> size, chosen, when the first access to
63 the array is indexed and beyond C<MIN_ITEMS> and below 10 *
66 If the first access is beyond 10 * C<MAX_ITEMS> a sparse chunk will
69 To avoid this - and the performance penalty - set the array size
70 before setting elements.
73 set P0, 100000 # sets fixed sized, no sparse
75 This is only meaningful, if a lot of the entries are used too.
77 =item C<enum_grow_growing>
79 Chunk sizes grow from C<MIN_ITEMS> to C<MAX_ITEMS>, this will be selected
80 for pushing data on an empty array.
82 =item C<enum_grow_mixed>
84 Mixture of above chunk types and when sparse chunks are present, or
85 after insert and delete.
87 The chunks hold the information, how many chunks are of the same type,
88 beginning from the current, and how many items are included in this
89 range. See C<get_chunk> below for details.
96 To save memory, List can handle sparse arrays. This code snippet:
101 generates 3 List_chunks, one at the beginning of the array, a
102 big sparse chunk and a chunk for the actual data.
104 Setting values inside sparse chunks changes them to real chunks.
105 For poping/shifting inside sparse chunks, s. return value below.
113 Have allocated space, size is a power of 2, consecutive chunks are same sized.
117 Same, but consecutive chunks are growing.
121 Have allocated space but any size.
125 Only dummy allocation, C<< chunk->items >> holds the items of this sparse
132 A List can hold various datatypes. See F<src/datatypes.h> for the
133 enumeration of types.
135 Not all are yet implemented in C<list_set>/C<list_item>, see the
138 Arbitrary length data:
140 Construct initializer with:
144 =item C<enum_type_sized>
146 =item C<item_size> (in bytes)
148 =item C<items_per_chunk> (rounded up to power of 2, default C<MAX_ITEMS>)
152 In C<list_assign> the values are copied into the array, C<list_get>
153 returns a pointer as for all other data types.
155 See F<src/list_2.t> and C<list_new_init()>.
159 List get functions return a C<(void*)> pointer to the location of the
160 stored data. The caller has to extract the value from this pointer.
162 For non existent data beyond the dimensions of the array a C<NULL>
165 For non existing data inside sparse holes, a pointer C<(void*)-1> is
168 The caller can decide to assume these data as undef or 0 or whatever is
173 See F<t/src/{int, }list.c> and F<t/pmc/{int, }list.t>.
175 Also all array usage depends on list.
185 #include "parrot/parrot.h"
187 /* HEADERIZER HFILE: include/parrot/list.h */
189 /* HEADERIZER BEGIN: static */
190 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
192 PARROT_IGNORABLE_RESULT
193 PARROT_CANNOT_RETURN_NULL
194 static List_chunk
* add_chunk_at_end(PARROT_INTERP
,
197 __attribute__nonnull__(1)
198 __attribute__nonnull__(2)
199 FUNC_MODIFIES(*list
);
201 PARROT_IGNORABLE_RESULT
202 PARROT_CANNOT_RETURN_NULL
203 static List_chunk
* add_chunk_at_start(PARROT_INTERP
,
206 __attribute__nonnull__(1)
207 __attribute__nonnull__(2)
208 FUNC_MODIFIES(*list
);
210 PARROT_WARN_UNUSED_RESULT
211 PARROT_CANNOT_RETURN_NULL
212 static List_chunk
* alloc_next_size(PARROT_INTERP
,
216 __attribute__nonnull__(1)
217 __attribute__nonnull__(2)
218 FUNC_MODIFIES(*list
);
220 PARROT_CANNOT_RETURN_NULL
221 PARROT_WARN_UNUSED_RESULT
222 static List_chunk
* allocate_chunk(PARROT_INTERP
,
226 __attribute__nonnull__(1)
227 __attribute__nonnull__(2);
229 PARROT_WARN_UNUSED_RESULT
230 PARROT_CANNOT_RETURN_NULL
231 static List_chunk
* get_chunk(PARROT_INTERP
,
233 ARGMOD(UINTVAL
*idx
))
234 __attribute__nonnull__(1)
235 __attribute__nonnull__(2)
236 __attribute__nonnull__(3)
240 static void list_append(PARROT_INTERP
,
242 ARGIN_NULLOK(void *item
),
245 __attribute__nonnull__(1)
246 __attribute__nonnull__(2)
247 FUNC_MODIFIES(*list
);
249 PARROT_WARN_UNUSED_RESULT
250 PARROT_CANNOT_RETURN_NULL
251 static void * list_item(PARROT_INTERP
,
255 __attribute__nonnull__(1)
256 __attribute__nonnull__(2)
257 FUNC_MODIFIES(*list
);
259 static void list_set(PARROT_INTERP
,
261 ARGIN_NULLOK(void *item
),
264 __attribute__nonnull__(1)
265 __attribute__nonnull__(2)
266 FUNC_MODIFIES(*list
);
268 static void rebuild_chunk_list(PARROT_INTERP
, ARGMOD(List
*list
))
269 __attribute__nonnull__(1)
270 __attribute__nonnull__(2)
271 FUNC_MODIFIES(*list
);
273 static void rebuild_chunk_ptrs(ARGMOD(List
*list
), int cut
)
274 __attribute__nonnull__(1)
275 FUNC_MODIFIES(*list
);
277 static void rebuild_fix_ends(ARGMOD(List
*list
))
278 __attribute__nonnull__(1)
279 FUNC_MODIFIES(*list
);
281 static void rebuild_other(PARROT_INTERP
, ARGMOD(List
*list
))
282 __attribute__nonnull__(1)
283 __attribute__nonnull__(2)
284 FUNC_MODIFIES(*list
);
286 static void rebuild_sparse(ARGMOD(List
*list
))
287 __attribute__nonnull__(1)
288 FUNC_MODIFIES(*list
);
290 static void split_chunk(PARROT_INTERP
,
292 ARGMOD(List_chunk
*chunk
),
294 __attribute__nonnull__(1)
295 __attribute__nonnull__(2)
296 __attribute__nonnull__(3)
298 FUNC_MODIFIES(*chunk
);
300 #define ASSERT_ARGS_add_chunk_at_end __attribute__unused__ int _ASSERT_ARGS_CHECK = \
301 PARROT_ASSERT_ARG(interp) \
302 || PARROT_ASSERT_ARG(list)
303 #define ASSERT_ARGS_add_chunk_at_start __attribute__unused__ int _ASSERT_ARGS_CHECK = \
304 PARROT_ASSERT_ARG(interp) \
305 || PARROT_ASSERT_ARG(list)
306 #define ASSERT_ARGS_alloc_next_size __attribute__unused__ int _ASSERT_ARGS_CHECK = \
307 PARROT_ASSERT_ARG(interp) \
308 || PARROT_ASSERT_ARG(list)
309 #define ASSERT_ARGS_allocate_chunk __attribute__unused__ int _ASSERT_ARGS_CHECK = \
310 PARROT_ASSERT_ARG(interp) \
311 || PARROT_ASSERT_ARG(list)
312 #define ASSERT_ARGS_get_chunk __attribute__unused__ int _ASSERT_ARGS_CHECK = \
313 PARROT_ASSERT_ARG(interp) \
314 || PARROT_ASSERT_ARG(list) \
315 || PARROT_ASSERT_ARG(idx)
316 #define ASSERT_ARGS_list_append __attribute__unused__ int _ASSERT_ARGS_CHECK = \
317 PARROT_ASSERT_ARG(interp) \
318 || PARROT_ASSERT_ARG(list)
319 #define ASSERT_ARGS_list_item __attribute__unused__ int _ASSERT_ARGS_CHECK = \
320 PARROT_ASSERT_ARG(interp) \
321 || PARROT_ASSERT_ARG(list)
322 #define ASSERT_ARGS_list_set __attribute__unused__ int _ASSERT_ARGS_CHECK = \
323 PARROT_ASSERT_ARG(interp) \
324 || PARROT_ASSERT_ARG(list)
325 #define ASSERT_ARGS_rebuild_chunk_list __attribute__unused__ int _ASSERT_ARGS_CHECK = \
326 PARROT_ASSERT_ARG(interp) \
327 || PARROT_ASSERT_ARG(list)
328 #define ASSERT_ARGS_rebuild_chunk_ptrs __attribute__unused__ int _ASSERT_ARGS_CHECK = \
329 PARROT_ASSERT_ARG(list)
330 #define ASSERT_ARGS_rebuild_fix_ends __attribute__unused__ int _ASSERT_ARGS_CHECK = \
331 PARROT_ASSERT_ARG(list)
332 #define ASSERT_ARGS_rebuild_other __attribute__unused__ int _ASSERT_ARGS_CHECK = \
333 PARROT_ASSERT_ARG(interp) \
334 || PARROT_ASSERT_ARG(list)
335 #define ASSERT_ARGS_rebuild_sparse __attribute__unused__ int _ASSERT_ARGS_CHECK = \
336 PARROT_ASSERT_ARG(list)
337 #define ASSERT_ARGS_split_chunk __attribute__unused__ int _ASSERT_ARGS_CHECK = \
338 PARROT_ASSERT_ARG(interp) \
339 || PARROT_ASSERT_ARG(list) \
340 || PARROT_ASSERT_ARG(chunk)
341 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
342 /* HEADERIZER END: static */
344 #define chunk_list_size(list) \
345 (PObj_buflen(&(list)->chunk_list) / sizeof (List_chunk *))
347 /* hide the ugly cast somehow: */
348 #define chunk_list_ptr(list, idx) \
349 ((List_chunk**) PObj_bufstart(&(list)->chunk_list))[(idx)]
353 =item C<static List_chunk * allocate_chunk(PARROT_INTERP, List *list, UINTVAL
354 items, UINTVAL size)>
356 Makes a new chunk, and allocates C<size> bytes for buffer storage from the
357 generic memory pool. The chunk holds C<items> items. Marks the chunk as
358 being part of C<< list->container >>, if it exists, for the purposes of GC. Does
359 not install the chunk into C<< list->container >> yet.
365 PARROT_CANNOT_RETURN_NULL
366 PARROT_WARN_UNUSED_RESULT
368 allocate_chunk(PARROT_INTERP
, ARGIN(List
*list
), UINTVAL items
, UINTVAL size
)
370 ASSERT_ARGS(allocate_chunk
)
373 Parrot_block_GC_mark(interp
);
374 /* Parrot_block_GC_sweep(interp); - why */
376 chunk
= (List_chunk
*)Parrot_gc_new_bufferlike_header(interp
, sizeof (*chunk
));
378 chunk
->items
= items
;
383 Parrot_gc_allocate_buffer_storage_aligned(interp
, (Buffer
*)chunk
, size
);
384 memset(PObj_bufstart((Buffer
*)chunk
), 0, size
);
386 /* see also src/hash.c */
388 GC_WRITE_BARRIER(interp
, list
->container
, 0, chunk
);
390 Parrot_unblock_GC_mark(interp
);
392 /* Parrot_unblock_GC_sweep(interp); */
399 =item C<static void rebuild_chunk_ptrs(List *list, int cut)>
401 Rebuilds C<list> and updates/optimizes chunk usage. Deletes empty chunks,
402 counts chunks, and fixes C<prev> pointers.
409 rebuild_chunk_ptrs(ARGMOD(List
*list
), int cut
)
411 ASSERT_ARGS(rebuild_chunk_ptrs
)
412 List_chunk
*chunk
, *prev
;
413 UINTVAL start
= list
->start
;
417 for (prev
= NULL
, chunk
= list
->first
; chunk
; chunk
= chunk
->next
) {
418 /* skip empty chunks, first is empty, when all items get skipped due
420 if (chunk
->items
== start
) {
422 prev
->next
= chunk
->next
;
424 list
->first
= chunk
->next
;
436 if (cut
&& cap
> list
->start
+ list
->length
&& chunk
!= list
->first
) {
437 list
->last
= chunk
->prev
? chunk
->prev
: list
->first
;
445 list
->last
->next
= NULL
;
450 list
->first
->prev
= NULL
;
452 list
->n_chunks
= len
;
458 =item C<static void rebuild_sparse(List *list)>
460 Combines adjacent sparse chunks in C<list>.
467 rebuild_sparse(ARGMOD(List
*list
))
469 ASSERT_ARGS(rebuild_sparse
)
471 List_chunk
*chunk
= list
->first
;
472 List_chunk
*prev
= NULL
;
475 for (; chunk
; chunk
= chunk
->next
) {
476 if (prev
&& (prev
->flags
& sparse
) && (chunk
->flags
& sparse
)) {
477 prev
->items
+= chunk
->items
;
486 rebuild_chunk_ptrs(list
, 0);
492 =item C<static void rebuild_other(PARROT_INTERP, List *list)>
494 Combines adjacent irregular chunks in C<list>.
501 rebuild_other(PARROT_INTERP
, ARGMOD(List
*list
))
503 ASSERT_ARGS(rebuild_other
)
504 List_chunk
*chunk
= list
->first
;
505 List_chunk
*prev
= NULL
;
508 for (; chunk
; chunk
= chunk
->next
) {
509 /* two adjacent irregular chunks */
510 if (prev
&& (prev
->flags
& no_power_2
) && (chunk
->flags
& no_power_2
)) {
511 /* DONE don't make chunks bigger then MAX_ITEMS, no - make then
512 * but: if bigger, split them in a next pass
513 * TODO test the logic that solves the above problem */
514 if (prev
->items
+ chunk
->items
> MAX_ITEMS
) {
515 Parrot_gc_reallocate_buffer_storage(interp
, (Buffer
*)prev
,
516 MAX_ITEMS
* list
->item_size
);
518 if (list
->container
) {
519 GC_WRITE_BARRIER(interp
, list
->container
, 0, prev
);
523 (char *) PObj_bufstart(&prev
->data
) +
524 prev
->items
* list
->item_size
,
525 (const char *) PObj_bufstart(&chunk
->data
),
526 (MAX_ITEMS
- prev
->items
) * list
->item_size
);
528 (char *) PObj_bufstart(&chunk
->data
),
529 (const char *) PObj_bufstart(&chunk
->data
) +
530 (MAX_ITEMS
- prev
->items
) * list
->item_size
,
531 (chunk
->items
- (MAX_ITEMS
- prev
->items
))
533 chunk
->items
= chunk
->items
- (MAX_ITEMS
- prev
->items
);
534 prev
->items
= MAX_ITEMS
;
537 Parrot_gc_reallocate_buffer_storage(interp
, (Buffer
*)prev
,
538 (prev
->items
+ chunk
->items
) * list
->item_size
);
539 if (list
->container
) {
540 GC_WRITE_BARRIER(interp
, list
->container
, 0, prev
);
543 (char *) PObj_bufstart(&prev
->data
) +
544 prev
->items
* list
->item_size
,
545 (const char *) PObj_bufstart(&chunk
->data
),
546 chunk
->items
* list
->item_size
);
547 prev
->items
+= chunk
->items
;
557 rebuild_chunk_ptrs(list
, 0);
563 =item C<static void rebuild_fix_ends(List *list)>
565 Resets some values in C<list> and the lists's first chunk. Called by
566 C<rebuild_chunk_list()>.
573 rebuild_fix_ends(ARGMOD(List
*list
))
575 ASSERT_ARGS(rebuild_fix_ends
)
576 List_chunk
* const chunk
= list
->first
;
578 /* first is irregular, next is empty */
579 if (list
->n_chunks
<= 2 && (chunk
->flags
& no_power_2
)
581 || chunk
->next
->items
== 0
582 || list
->start
+ list
->length
<= chunk
->items
)) {
585 list
->grow_policy
= enum_grow_unknown
;
586 list
->cap
+= PObj_buflen(&chunk
->data
) / list
->item_size
- chunk
->items
;
587 chunk
->items
= PObj_buflen(&chunk
->data
) / list
->item_size
;
590 /* XXX - still needed? - if last is empty and last->prev not full then
591 * delete last - combine small chunks if list is big */
597 =item C<static void rebuild_chunk_list(PARROT_INTERP, List *list)>
599 Optimizes a modified C<list>: combines adjacent chunks if they are both sparse
600 or irregular and updates the grow policies and computes list statistics.
607 rebuild_chunk_list(PARROT_INTERP
, ARGMOD(List
*list
))
609 ASSERT_ARGS(rebuild_chunk_list
)
610 List_chunk
*chunk
, *prev
, *first
;
613 Parrot_block_GC_mark(interp
);
614 Parrot_block_GC_sweep(interp
);
616 /* count chunks and fix prev pointers */
617 rebuild_chunk_ptrs(list
, 0);
619 /* if not regular, check & optimize */
620 if (list
->grow_policy
== enum_grow_mixed
) {
621 rebuild_sparse(list
);
622 rebuild_other(interp
, list
);
623 rebuild_fix_ends(list
);
626 /* allocate a new chunk_list buffer, if old one has moved or is too small */
627 len
= list
->n_chunks
;
628 if (list
->collect_runs
!= Parrot_gc_count_collect_runs(interp
)
629 || len
> chunk_list_size(list
)) {
630 /* round up to reasonable size */
631 len
= 1 << (ld(len
) + 1);
636 Parrot_gc_reallocate_buffer_storage(interp
, (Buffer
*)list
,
637 len
* sizeof (List_chunk
*));
639 if (list
->container
) {
640 GC_WRITE_BARRIER(interp
, list
->container
, 0, list
);
643 list
->collect_runs
= Parrot_gc_count_collect_runs(interp
);
646 /* reset type, actual state of chunks will show, what we really have */
647 list
->grow_policy
= enum_grow_unknown
;
649 /* fill chunk_list and update statistics */
650 first
= chunk
= list
->first
;
651 for (prev
= NULL
, len
= 0; chunk
; chunk
= chunk
->next
) {
652 chunk_list_ptr(list
, len
) = chunk
;
655 /* look what type of chunks we have this is always correct: */
657 chunk
->n_items
= chunk
->items
;
659 /* sparse hole or irregular chunk */
660 if (chunk
->flags
& (sparse
| no_power_2
)) {
663 /* add next sparse or no_power_2 chunks up so that get_chunk will
664 * skip this range of chunks, when the idx is beyond this block. */
665 for (next
= chunk
->next
; next
; next
= next
->next
)
666 if (next
->flags
& (sparse
| no_power_2
)) {
668 chunk
->n_items
+= next
->items
;
673 list
->grow_policy
= enum_grow_mixed
;
677 /* clear flag, next chunks will tell what comes */
678 chunk
->flags
= enum_grow_unknown
;
680 if (first
&& first
!= chunk
) {
681 /* constant chunk block */
682 if (first
->items
== chunk
->items
) {
684 first
->n_items
+= chunk
->items
;
685 first
->flags
= fixed_items
;
687 /* TODO optimize for fixed but non MAX_ITEMS lists */
688 if (first
->items
== MAX_ITEMS
)
689 list
->grow_policy
|= enum_grow_fixed
;
691 list
->grow_policy
|= enum_grow_mixed
;
694 /* growing chunk block could optimize small growing blocks, they
695 * are probably not worth the effort. */
696 else if (prev
&& (prev
->items
== chunk
->items
>> 1)) {
698 first
->n_items
+= chunk
->items
;
699 first
->flags
= grow_items
;
700 list
->grow_policy
|= enum_grow_growing
;
702 /* different growing scheme starts here */
710 /* if we have some mixture of grow_policies, then set it to _mixed */
711 if (list
->grow_policy
&& list
->grow_policy
!= enum_grow_growing
712 && list
->grow_policy
!= enum_grow_fixed
)
713 list
->grow_policy
= enum_grow_mixed
;
715 Parrot_unblock_GC_mark(interp
);
716 Parrot_unblock_GC_sweep(interp
);
722 =item C<static List_chunk * alloc_next_size(PARROT_INTERP, List *list, int
725 Calculates the size and number of items for the next chunk and allocates it.
726 Adds the number of allocated items to the list's total, but does not
727 directly add the chunk to the C<list>.
733 PARROT_WARN_UNUSED_RESULT
734 PARROT_CANNOT_RETURN_NULL
736 alloc_next_size(PARROT_INTERP
, ARGMOD(List
*list
), int where
, UINTVAL idx
)
738 ASSERT_ARGS(alloc_next_size
)
739 List_chunk
*new_chunk
;
741 const int much
= idx
- list
->cap
>= MIN_ITEMS
;
742 int do_sparse
= (INTVAL
)idx
- (INTVAL
)list
->cap
>= 10 * MAX_ITEMS
;
744 if (list
->item_type
== enum_type_sized
) {
746 items
= list
->items_per_chunk
;
747 size
= items
* list
->item_size
;
749 list
->grow_policy
= items
== MAX_ITEMS
?
750 enum_grow_fixed
: enum_grow_mixed
;
752 else if (do_sparse
) {
753 PARROT_ASSERT(where
);
754 /* don't add sparse chunk at start of list */
755 if (!list
->n_chunks
) {
759 /* if we need more, the next allocation will allocate the rest */
760 size
= items
* list
->item_size
;
761 list
->grow_policy
= enum_grow_fixed
;
764 /* allocate a dummy chunk holding many items virtually */
765 size
= list
->item_size
;
766 items
= idx
- list
->cap
- 1;
768 /* round down this function will then be called again, to add the
769 * final real chunk, with the rest of the needed size */
770 items
&= ~(MAX_ITEMS
- 1);
771 list
->grow_policy
= enum_grow_mixed
;
774 /* initial size for empty lists grow_policy is not yet known or was
776 else if (!list
->cap
) {
777 #ifdef ONLY_FIXED_ALLOCATIONS
778 list
->grow_policy
= enum_grow_fixed
;
780 list
->grow_policy
= enum_grow_unknown
;
782 /* more then MIN_ITEMS, i.e. indexed access beyond length */
784 list
->grow_policy
= enum_grow_fixed
;
788 /* TODO make bigger for small items like char */
791 size
= items
* list
->item_size
;
794 if (list
->grow_policy
& (enum_grow_fixed
| enum_grow_mixed
))
797 items
= where
? list
->last
->items
: list
->first
->items
;
798 /* push: allocate at end, more if possbile */
800 if (items
< MAX_ITEMS
) {
802 list
->grow_policy
= enum_grow_growing
;
805 /* unshift: if possible, make less items */
807 list
->grow_policy
= enum_grow_growing
;
808 if (items
> MIN_ITEMS
)
809 items
>>= 1; /* allocate less */
810 /* if not: second allocation from unshift */
812 list
->grow_policy
= enum_grow_mixed
;
817 size
= items
* list
->item_size
;
820 new_chunk
= allocate_chunk(interp
, list
, items
, size
);
824 new_chunk
->flags
|= sparse
;
832 =item C<static List_chunk * add_chunk_at_start(PARROT_INTERP, List *list,
835 Adds a new chunk to the start of C<list>.
841 PARROT_IGNORABLE_RESULT
842 PARROT_CANNOT_RETURN_NULL
844 add_chunk_at_start(PARROT_INTERP
, ARGMOD(List
*list
), UINTVAL idx
)
846 ASSERT_ARGS(add_chunk_at_start
)
847 List_chunk
* const chunk
= list
->first
;
848 List_chunk
* const new_chunk
= alloc_next_size(interp
, list
, enum_add_at_start
, idx
);
850 new_chunk
->next
= chunk
;
851 list
->first
= new_chunk
;
854 list
->last
= new_chunk
;
856 rebuild_chunk_list(interp
, list
);
864 =item C<static List_chunk * add_chunk_at_end(PARROT_INTERP, List *list, UINTVAL
867 Adds a new chunk to the end of C<list>.
873 PARROT_IGNORABLE_RESULT
874 PARROT_CANNOT_RETURN_NULL
876 add_chunk_at_end(PARROT_INTERP
, ARGMOD(List
*list
), UINTVAL idx
)
878 ASSERT_ARGS(add_chunk_at_end
)
879 List_chunk
* const chunk
= list
->last
;
880 List_chunk
* const new_chunk
= alloc_next_size(interp
, list
, enum_add_at_end
, idx
);
883 chunk
->next
= new_chunk
;
886 list
->first
= new_chunk
;
888 list
->last
= new_chunk
;
890 rebuild_chunk_list(interp
, list
);
898 =item C<UINTVAL ld(UINTVAL x)>
900 Calculates log2(x), or a useful approximation thereof. Stolen from
908 PARROT_CONST_FUNCTION
909 PARROT_WARN_UNUSED_RESULT
914 UINTVAL m
; /* bit position of highest set bit of m */
916 /* On intel, use BSRL instruction to find highest bit */
917 #if defined(__GNUC__) && defined(i386)
919 __asm__("bsrl %1,%0\n\t":"=r"(m
)
925 * Based on branch-free nlz algorithm in chapter 5 of Henry S. Warren
926 * Jr's book "Hacker's Delight". */
928 unsigned int n
= ((x
- 0x100) >> 16) & 8;
931 m
= ((x
- 0x1000) >> 16) & 4;
934 m
= ((x
- 0x4000) >> 16) & 2;
937 m
= 13 - n
+ (x
& ~(x
>> 1));
946 =item C<static List_chunk * get_chunk(PARROT_INTERP, List *list, UINTVAL *idx)>
948 Get the chunk for C<idx>, also update the C<idx> to point into the chunk.
950 This routine will be called for every operation on list, so it's
951 optimized to be fast and needs an up-to-date chunk statistic.
952 C<rebuild_chunk_list> provides the necessary chunk statistics.
954 The scheme of operations is:
956 if all_chunks_are_MAX_ITEMS
957 chunk = chunk_list[ idx / MAX_ITEMS ]
958 idx = idx % MAX_ITEMS
963 if (index < chunk->items)
966 if (index >= items_in_chunk_block)
967 index -= items_in_chunk_block
968 chunk += chunks_in_chunk_block
971 calc chunk and index in this block
974 One chunk_block consists of chunks of the same type: fixed, growing or
975 other. So the time to look up a chunk doesn't depend on the array
976 length, but on the complexity of the array. C<rebuild_chunk_list> tries
977 to reduce the complexity, but may fail, if you e.g. do a prime sieve by
978 actually C<list_delet>ing the none prime numbers.
980 The complexity of the array is how many different C<chunk_blocks> are
981 there. They come from:
985 - initially growing: 2
987 - first unshift: 1 except for initially fixed arrays
993 - sparse hole: 3 (could be 2, code assumes access at either end now)
995 There could be some optimizer that, after detecting almost only indexed access
996 after some time, reorganizes the array to be all C<MAX_ITEMS> sized when this
997 would improve performance.
1003 PARROT_WARN_UNUSED_RESULT
1004 PARROT_CANNOT_RETURN_NULL
1006 get_chunk(PARROT_INTERP
, ARGMOD(List
*list
), ARGMOD(UINTVAL
*idx
))
1008 ASSERT_ARGS(get_chunk
)
1012 #ifndef GC_IS_MALLOC
1013 if (list
->collect_runs
!= Parrot_gc_count_collect_runs(interp
))
1014 rebuild_chunk_list(interp
, list
);
1016 #ifdef SLOW_AND_BORING
1017 /* in SLOW_AND_BORING mode, we loop through each chunk, and determine if
1018 idx is in the chunk using basic bounds checking. If the loop completes
1019 without finding idx we panic. "Panic" is probably not the best
1020 reaction, however. */
1022 for (chunk
= list
->first
; chunk
; chunk
= chunk
->next
) {
1023 if (*idx
< chunk
->items
)
1025 *idx
-= chunk
->items
;
1028 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_INTERNAL_PANIC
,
1029 "Reached end of list %p without finding item index %d\n",
1033 /* fixed sized chunks - easy: all MAX_ITEMS sized */
1034 if (list
->grow_policy
== enum_grow_fixed
) {
1035 chunk
= chunk_list_ptr(list
, *idx
>> LD_MAX
);
1040 /* else look at chunks flags, what grow type follows and adjust chunks and
1042 for (i
= 0, chunk
= list
->first
; chunk
;) {
1043 /* if we have no more items, we have found the chunk */
1044 if (*idx
< chunk
->items
)
1047 /* now look, if we can use the range of items in chunk_block: if idx
1048 * is beyond n_items, skip n_chunks */
1049 if (*idx
>= chunk
->n_items
) {
1050 i
+= chunk
->n_chunks
;
1051 *idx
-= chunk
->n_items
;
1052 chunk
= chunk_list_ptr(list
, i
);
1056 /* we are inside this range of items */
1057 if (chunk
->flags
& fixed_items
) {
1058 /* all chunks are chunk->items big, a power of 2 */
1059 chunk
= chunk_list_ptr(list
, i
+ (*idx
>> ld(chunk
->items
)));
1060 *idx
&= chunk
->items
- 1;
1065 * Here is a small table, providing the basics of growing sized
1066 * addressing, for people like me, whose math lessons are +30 years
1068 * assuming MIN_ITEMS=4
1070 * ch# size idx +4 bit ld2(idx) -ld2(4)
1072 * 0 4 0..3 4..7 0000 01xx 2 0
1073 * 1 8 4..11 8..15 0000 1xxx 3 1
1074 * 2 16 12..27 16..31 0001 xxxx 4 2
1076 * 8 1024 1020.. ...2047 10 8
1079 if (chunk
->flags
& grow_items
) {
1080 /* the next chunks are growing from chunk->items ... last->items */
1081 const UINTVAL ld_first
= ld(chunk
->items
);
1082 const UINTVAL slot
= ld(*idx
+ chunk
->items
) - ld_first
;
1084 /* we are in this growing area, so we are done */
1085 PARROT_ASSERT(slot
< chunk
->n_chunks
);
1086 *idx
-= (1 << (ld_first
+ slot
)) - chunk
->items
;
1087 return chunk_list_ptr(list
, i
+ slot
);
1090 if (chunk
->flags
& (sparse
| no_power_2
)) {
1091 /* these chunks hold exactly chunk->items */
1092 *idx
-= chunk
->items
;
1093 chunk
= chunk
->next
;
1098 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_INTERNAL_PANIC
,
1099 "Cannot determine how to find location %d in list %p of %d items\n",
1100 *idx
, list
, list
->cap
);
1103 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_INTERNAL_PANIC
,
1104 "Cannot find index %d in list %p of %d items using any method\n",
1105 *idx
, list
, list
->cap
);
1111 =item C<static void split_chunk(PARROT_INTERP, List *list, List_chunk *chunk,
1114 Splits a sparse chunk, so that we have
1116 - allocated space at C<idx>
1120 - C<MAX_ITEMS> near C<idx> and if there is still sparse space after the
1121 real chunk, this also C<n*MAX_ITEMS> sized, so that consecutive writing
1122 would make C<MAX_ITEMS> sized real chunks.
1129 split_chunk(PARROT_INTERP
, ARGMOD(List
*list
), ARGMOD(List_chunk
*chunk
), UINTVAL ix
)
1131 ASSERT_ARGS(split_chunk
)
1132 /* allocate space at idx */
1133 if (chunk
->items
<= MAX_ITEMS
) {
1134 /* it fits, just allocate */
1135 Parrot_gc_reallocate_buffer_storage(interp
, (Buffer
*)chunk
,
1136 chunk
->items
* list
->item_size
);
1138 if (list
->container
) {
1139 GC_WRITE_BARRIER(interp
, list
->container
, 0, chunk
);
1142 chunk
->flags
|= no_power_2
;
1143 chunk
->flags
&= ~sparse
;
1146 /* split chunk->items: n3 = n*MAX_ITEMS after chunk n2 = MAX_ITEMS
1147 * chunk n1 = rest before */
1148 const INTVAL idx
= ix
;
1149 const INTVAL n2
= MAX_ITEMS
;
1150 const INTVAL n3
= ((chunk
->items
- idx
) / MAX_ITEMS
) * MAX_ITEMS
;
1151 const INTVAL n1
= chunk
->items
- n2
- n3
;
1155 Parrot_gc_reallocate_buffer_storage(interp
, (Buffer
*)chunk
,
1156 chunk
->items
* list
->item_size
);
1158 if (list
->container
) {
1159 GC_WRITE_BARRIER(interp
, list
->container
, 0, chunk
);
1162 chunk
->flags
&= ~sparse
;
1165 List_chunk
* const new_chunk
= allocate_chunk(interp
, list
, n3
, list
->item_size
);
1167 new_chunk
->flags
|= sparse
;
1168 new_chunk
->next
= chunk
->next
;
1171 chunk
->next
= new_chunk
;
1173 list
->last
= new_chunk
;
1176 /* size before idx */
1178 /* insert a new sparse chunk before this one */
1179 List_chunk
* const new_chunk
= allocate_chunk(interp
, list
, n1
, list
->item_size
);
1181 new_chunk
->flags
|= sparse
;
1182 new_chunk
->next
= chunk
;
1185 chunk
->prev
->next
= new_chunk
;
1187 list
->first
= new_chunk
;
1191 rebuild_chunk_list(interp
, list
);
1197 =item C<static void list_set(PARROT_INTERP, List *list, void *item, INTVAL type,
1200 Sets C<item> of type C<type> in chunk at C<idx>.
1207 list_set(PARROT_INTERP
, ARGMOD(List
*list
), ARGIN_NULLOK(void *item
),
1208 INTVAL type
, INTVAL idx
)
1210 ASSERT_ARGS(list_set
)
1211 List_chunk
*chunk
= get_chunk(interp
, list
, (UINTVAL
*)&idx
);
1212 const INTVAL oidx
= idx
;
1214 PARROT_ASSERT(chunk
);
1216 /* if this is a sparse chunk: split in possibly 2 sparse parts before and
1217 * after then make a real chunk, rebuild chunk list and set item */
1218 if (chunk
->flags
& sparse
) {
1219 split_chunk(interp
, list
, chunk
, idx
);
1220 /* reget chunk and idx */
1222 chunk
= get_chunk(interp
, list
, (UINTVAL
*)&idx
);
1223 PARROT_ASSERT(chunk
);
1224 PARROT_ASSERT(!(chunk
->flags
& sparse
));
1228 case enum_type_sized
:
1229 /* copy data into list */
1230 memcpy(&((char *) PObj_bufstart(&chunk
->data
))[idx
* list
->item_size
],
1231 item
, list
->item_size
);
1233 case enum_type_char
:
1234 ((char *) PObj_bufstart(&chunk
->data
))[idx
] = (char)PTR2INTVAL(item
);
1236 case enum_type_short
:
1237 ((short *) PObj_bufstart(&chunk
->data
))[idx
] = (short)PTR2INTVAL(item
);
1240 ((int *) PObj_bufstart(&chunk
->data
))[idx
] = (int)PTR2INTVAL(item
);
1242 case enum_type_INTVAL
:
1243 ((INTVAL
*) PObj_bufstart(&chunk
->data
))[idx
] = PTR2INTVAL(item
);
1245 case enum_type_FLOATVAL
:
1246 ((FLOATVAL
*) PObj_bufstart(&chunk
->data
))[idx
] = *(FLOATVAL
*)item
;
1249 if (list
->container
) {
1250 GC_WRITE_BARRIER(interp
, list
->container
,
1251 ((PMC
**) PObj_bufstart(&chunk
->data
))[idx
],
1254 ((PMC
**) PObj_bufstart(&chunk
->data
))[idx
] = (PMC
*)item
;
1256 case enum_type_STRING
:
1257 ((STRING
**) PObj_bufstart(&chunk
->data
))[idx
] = (STRING
*)item
;
1260 Parrot_ex_throw_from_c_args(interp
, NULL
, 1, "Unknown list entry type\n");
1268 =item C<static void * list_item(PARROT_INTERP, List *list, int type, INTVAL
1271 Get the pointer to the item of type C<type> in the chunk at C<idx>.
1277 PARROT_WARN_UNUSED_RESULT
1278 PARROT_CANNOT_RETURN_NULL
1280 list_item(PARROT_INTERP
, ARGMOD(List
*list
), int type
, INTVAL idx
)
1282 ASSERT_ARGS(list_item
)
1283 List_chunk
* const chunk
= get_chunk(interp
, list
, (UINTVAL
*)&idx
);
1284 /* if this is a sparse chunk return -1, the caller may decide to return 0
1285 * or undef or whatever */
1286 if (chunk
->flags
& sparse
) {
1288 static int null
= 0;
1290 return (void *)&null
;
1297 case enum_type_sized
:
1298 return (void *)&((char *)
1299 PObj_bufstart(&chunk
->data
))[idx
* list
->item_size
];
1300 case enum_type_char
:
1301 return (void *)&((char *) PObj_bufstart(&chunk
->data
))[idx
];
1302 case enum_type_short
:
1303 return (void *)&((short *) PObj_bufstart(&chunk
->data
))[idx
];
1305 return (void *)&((int *) PObj_bufstart(&chunk
->data
))[idx
];
1306 case enum_type_INTVAL
:
1307 return (void *)&((INTVAL
*) PObj_bufstart(&chunk
->data
))[idx
];
1308 case enum_type_FLOATVAL
:
1309 return (void *)&((FLOATVAL
*) PObj_bufstart(&chunk
->data
))[idx
];
1311 return (void *)&((PMC
**) PObj_bufstart(&chunk
->data
))[idx
];
1312 case enum_type_STRING
:
1313 return (void *)&((STRING
**) PObj_bufstart(&chunk
->data
))[idx
];
1315 Parrot_ex_throw_from_c_args(interp
, NULL
, 1, "Unknown list entry type\n");
1322 =item C<static void list_append(PARROT_INTERP, List *list, void *item, int type,
1325 Adds one or more chunks to end of list.
1332 list_append(PARROT_INTERP
, ARGMOD(List
*list
), ARGIN_NULLOK(void *item
), int type
, UINTVAL idx
)
1334 ASSERT_ARGS(list_append
)
1335 /* initially, list may be empty, also used by assign */
1336 while (idx
>= list
->cap
)
1337 add_chunk_at_end(interp
, list
, idx
);
1339 list_set(interp
, list
, item
, type
, idx
);
1341 /* invariant: prepare for next push */
1342 if (idx
>= list
->cap
- 1)
1343 add_chunk_at_end(interp
, list
, 0);
1351 =head2 Public Interface Functions
1355 =item C<List * list_new(PARROT_INTERP, PARROT_DATA_TYPE type)>
1357 Returns a new list of type C<type>.
1364 PARROT_WARN_UNUSED_RESULT
1365 PARROT_CANNOT_RETURN_NULL
1367 list_new(PARROT_INTERP
, PARROT_DATA_TYPE type
)
1369 ASSERT_ARGS(list_new
)
1370 List
* const list
= (List
*)Parrot_gc_new_bufferlike_header(interp
,
1373 list
->item_type
= type
;
1375 case enum_type_sized
: /* gets overridden below */
1376 case enum_type_char
:
1377 list
->item_size
= sizeof (char);
1379 case enum_type_short
:
1380 list
->item_size
= sizeof (short);
1383 list
->item_size
= sizeof (int);
1385 case enum_type_INTVAL
:
1386 list
->item_size
= sizeof (INTVAL
);
1388 case enum_type_FLOATVAL
:
1389 list
->item_size
= sizeof (FLOATVAL
);
1392 list
->item_size
= sizeof (PMC
*);
1394 case enum_type_STRING
:
1395 list
->item_size
= sizeof (STRING
*);
1398 Parrot_ex_throw_from_c_args(interp
, NULL
, 1, "Unknown list type\n");
1408 =item C<void list_pmc_new(PARROT_INTERP, PMC *container)>
1410 Creates a new list containing PMC* values in C<PMC_data(container)>.
1418 list_pmc_new(PARROT_INTERP
, ARGMOD(PMC
*container
))
1420 ASSERT_ARGS(list_pmc_new
)
1422 List
* const l
= list_new(interp
, enum_type_PMC
);
1423 l
->container
= container
;
1424 PMC_data(container
) = l
;
1430 =item C<List * list_new_init(PARROT_INTERP, PARROT_DATA_TYPE type, PMC *init)>
1432 C<list_new_init()> uses these initializers:
1434 0 ... size (set initial size of list)
1435 1 ... array dimensions (multiarray)
1436 2 ... type (overriding type parameter)
1437 3 ... item_size for enum_type_sized
1438 4 ... items_per_chunk
1445 PARROT_WARN_UNUSED_RESULT
1446 PARROT_CANNOT_RETURN_NULL
1448 list_new_init(PARROT_INTERP
, PARROT_DATA_TYPE type
, ARGIN(PMC
*init
))
1450 ASSERT_ARGS(list_new_init
)
1452 PMC
*multi_key
= NULL
;
1454 INTVAL item_size
= 0;
1455 INTVAL items_per_chunk
= 0;
1460 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
1461 "Illegal initializer for init\n");
1463 len
= VTABLE_elements(interp
, init
);
1466 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
1467 "Illegal initializer for init: odd elements\n");
1469 for (i
= 0; i
< len
; i
+= 2) {
1470 const INTVAL key
= VTABLE_get_integer_keyed_int(interp
, init
, i
);
1471 const INTVAL val
= i
+ 1;
1474 size
= VTABLE_get_integer_keyed_int(interp
, init
, val
);
1477 multi_key
= VTABLE_get_pmc_keyed_int(interp
, init
, val
);
1481 const INTVAL result
=
1482 VTABLE_get_integer_keyed_int(interp
, init
, val
);
1483 type
= (PARROT_DATA_TYPE
)result
;
1487 item_size
= VTABLE_get_integer_keyed_int(interp
, init
, val
);
1490 items_per_chunk
= VTABLE_get_integer_keyed_int(
1494 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
1495 "Invalid initializer for list\n");
1499 list
= list_new(interp
, type
);
1501 if (list
->item_type
== enum_type_sized
) { /* override item_size */
1504 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
1505 "No item_size for type_sized list\n");
1507 list
->item_size
= item_size
;
1508 list
->items_per_chunk
=
1510 ? (1 << (ld(items_per_chunk
) + 1)) /* make power of 2 */
1515 list_set_length(interp
, list
, size
);
1523 =item C<void list_pmc_new_init(PARROT_INTERP, PMC *container, PMC *init)>
1525 Creates a new list of PMC* values in C<PMC_data(container)>.
1533 list_pmc_new_init(PARROT_INTERP
, ARGMOD(PMC
*container
), ARGIN(PMC
*init
))
1535 ASSERT_ARGS(list_pmc_new_init
)
1537 List
* const l
= list_new_init(interp
, enum_type_PMC
, init
);
1538 l
->container
= container
;
1539 PMC_data(container
) = l
;
1545 =item C<List * list_clone(PARROT_INTERP, const List *other)>
1547 Returns a clone of the C<other> list.
1549 TODO - Barely tested. Optimize new array structure, fixed if big.
1556 PARROT_WARN_UNUSED_RESULT
1557 PARROT_CANNOT_RETURN_NULL
1559 list_clone(PARROT_INTERP
, ARGIN(const List
*other
))
1561 ASSERT_ARGS(list_clone
)
1563 List_chunk
*chunk
, *prev
;
1566 Parrot_block_GC_mark(interp
);
1567 Parrot_block_GC_sweep(interp
);
1569 l
= list_new(interp
, other
->item_type
);
1571 STRUCT_COPY(l
, other
);
1572 PObj_buflen(&l
->chunk_list
) = 0;
1573 PObj_bufstart(&l
->chunk_list
) = NULL
;
1575 for (chunk
= other
->first
, prev
= NULL
; chunk
; chunk
= chunk
->next
) {
1576 List_chunk
* const new_chunk
= allocate_chunk(interp
, l
,
1577 chunk
->items
, PObj_buflen(&chunk
->data
));
1579 new_chunk
->flags
= chunk
->flags
;
1582 l
->first
= new_chunk
;
1584 prev
->next
= new_chunk
;
1588 if (!(new_chunk
->flags
& sparse
)) {
1589 switch (l
->item_type
) {
1591 for (i
= 0; i
< chunk
->items
; i
++) {
1592 PMC
* const op
= ((PMC
**) PObj_bufstart(&chunk
->data
))[i
];
1595 ((PMC
**) PObj_bufstart(&new_chunk
->data
))[i
] =
1596 VTABLE_clone(interp
, op
);
1599 case enum_type_STRING
:
1600 for (i
= 0; i
< chunk
->items
; i
++) {
1601 STRING
*s
= ((STRING
**) PObj_bufstart(&chunk
->data
))[i
];
1603 ((STRING
**) PObj_bufstart(&new_chunk
->data
))[i
] =
1604 Parrot_str_copy(interp
, s
);
1608 mem_sys_memcopy(PObj_bufstart(&new_chunk
->data
),
1609 PObj_bufstart(&chunk
->data
), PObj_buflen(&chunk
->data
));
1615 rebuild_chunk_list(interp
, l
);
1616 Parrot_unblock_GC_mark(interp
);
1617 Parrot_unblock_GC_sweep(interp
);
1625 =item C<void list_mark(PARROT_INTERP, List *list)>
1627 Marks the list and its contents as live for the memory management system.
1635 list_mark(PARROT_INTERP
, ARGMOD(List
*list
))
1637 ASSERT_ARGS(list_mark
)
1640 for (chunk
= list
->first
; chunk
; chunk
= chunk
->next
) {
1641 Parrot_gc_mark_PObj_alive(interp
, (PObj
*)chunk
);
1643 if (list
->item_type
== enum_type_PMC
1644 || list
->item_type
== enum_type_STRING
) {
1645 if (!(chunk
->flags
& sparse
)) {
1646 PObj
**p
= ((PObj
**) PObj_bufstart(&chunk
->data
));
1649 for (i
= 0; i
< chunk
->items
; i
++, ++p
) {
1651 Parrot_gc_mark_PObj_alive(interp
, *p
);
1658 Parrot_gc_mark_PObj_alive(interp
, (PObj
*)list
);
1664 =item C<void list_visit(PARROT_INTERP, List *list, void *pinfo)>
1666 This is used by freeze/thaw to visit the contents of the list.
1668 C<pinfo> is the visit info, (see include/parrot/pmc_freeze.h>).
1676 list_visit(PARROT_INTERP
, ARGIN(List
*list
), ARGMOD(void *pinfo
))
1678 ASSERT_ARGS(list_visit
)
1680 visit_info
* const info
= (visit_info
*) pinfo
;
1683 const UINTVAL n
= list_length(interp
, list
);
1684 PARROT_ASSERT(list
->item_type
== enum_type_PMC
);
1686 for (idx
= 0, chunk
= list
->first
; chunk
; chunk
= chunk
->next
) {
1687 /* TODO deleted elements */
1688 if (!(chunk
->flags
& sparse
)) {
1690 for (i
= 0; i
< chunk
->items
&& idx
< n
; i
++, idx
++) {
1691 PMC
** const pos
= ((PMC
**) PObj_bufstart(&chunk
->data
)) + i
;
1692 info
->thaw_ptr
= pos
;
1693 (info
->visit_pmc_now
)(interp
, *pos
, info
);
1697 * TODO handle sparse
1705 =item C<INTVAL list_length(PARROT_INTERP, const List *list)>
1707 Returns the length of the list.
1713 PARROT_WARN_UNUSED_RESULT
1714 PARROT_PURE_FUNCTION
1716 list_length(SHIM_INTERP
, ARGIN(const List
*list
))
1718 ASSERT_ARGS(list_length
)
1719 return list
->length
;
1725 =item C<void list_set_length(PARROT_INTERP, List *list, INTVAL len)>
1727 Sets the length of the list to C<len>.
1735 list_set_length(PARROT_INTERP
, ARGMOD(List
*list
), INTVAL len
)
1737 ASSERT_ARGS(list_set_length
)
1740 len
+= list
->length
;
1743 const UINTVAL idx
= list
->start
+ (UINTVAL
)len
;
1746 if (idx
>= list
->cap
) {
1747 /* assume user will fill it, so don't generate sparse chunks */
1748 if (!list
->cap
&& idx
> MAX_ITEMS
) {
1749 while (idx
- MAX_ITEMS
>= list
->cap
) {
1750 add_chunk_at_end(interp
, list
, list
->cap
+ MAX_ITEMS
);
1754 list_append(interp
, list
, NULL
, list
->item_type
, idx
);
1757 rebuild_chunk_ptrs(list
, 1);
1759 rebuild_chunk_list(interp
, list
);
1766 =item C<void list_insert(PARROT_INTERP, List *list, INTVAL idx, INTVAL n_items)>
1768 Makes room for C<n_items> at C<idx>.
1776 list_insert(PARROT_INTERP
, ARGMOD(List
*list
), INTVAL idx
, INTVAL n_items
)
1778 ASSERT_ARGS(list_insert
)
1781 PARROT_ASSERT(idx
>= 0);
1784 PARROT_ASSERT(n_items
>= 0);
1789 if (idx
>= (INTVAL
)list
->cap
) {
1793 while (idx
>= (INTVAL
)list
->cap
)
1794 add_chunk_at_end(interp
, list
, idx
);
1799 list
->length
+= n_items
;
1800 list
->cap
+= n_items
;
1801 chunk
= get_chunk(interp
, list
, (UINTVAL
*)&idx
);
1803 /* the easy case: */
1804 if (chunk
->flags
& sparse
)
1805 chunk
->items
+= n_items
;
1807 List_chunk
*new_chunk
;
1810 /* 1. cut this chunk at idx */
1811 list
->grow_policy
= enum_grow_mixed
;
1813 /* allocate a sparse chunk, n_items big */
1814 new_chunk
= allocate_chunk(interp
, list
, n_items
, list
->item_size
);
1815 new_chunk
->flags
|= sparse
;
1816 items
= chunk
->items
- idx
;
1819 /* allocate a small chunk, holding the rest of chunk beyond idx */
1820 List_chunk
*rest
= allocate_chunk(interp
, list
, items
,
1821 items
* list
->item_size
);
1823 chunk
->flags
= no_power_2
;
1824 rest
->flags
|= no_power_2
;
1826 /* hang them together */
1827 rest
->next
= chunk
->next
;
1828 chunk
->next
= new_chunk
;
1829 new_chunk
->next
= rest
;
1831 /* copy data over */
1833 (char *)PObj_bufstart(&rest
->data
),
1834 (char *)PObj_bufstart(&chunk
->data
) + idx
* list
->item_size
,
1835 items
* list
->item_size
);
1838 new_chunk
->next
= chunk
->next
;
1839 chunk
->next
= new_chunk
;
1845 rebuild_chunk_list(interp
, list
);
1851 =item C<void list_delete(PARROT_INTERP, List *list, INTVAL idx, INTVAL n_items)>
1853 Deletes C<n_items> at C<idx>.
1861 list_delete(PARROT_INTERP
, ARGMOD(List
*list
), INTVAL idx
, INTVAL n_items
)
1863 ASSERT_ARGS(list_delete
)
1866 PARROT_ASSERT(idx
>= 0);
1867 PARROT_ASSERT(n_items
>= 0);
1873 chunk
= get_chunk(interp
, list
, (UINTVAL
*)&idx
);
1875 /* deleting beyond end? */
1876 if (idx
+ n_items
> (INTVAL
)list
->length
)
1877 n_items
= list
->length
- idx
;
1879 list
->length
-= n_items
;
1880 list
->cap
-= n_items
;
1881 list
->grow_policy
= enum_grow_mixed
;
1883 while (n_items
> 0) {
1884 if (idx
+ n_items
<= (INTVAL
)chunk
->items
) {
1885 /* chunk is bigger then we want to delete */
1886 if (!(chunk
->flags
& sparse
)) {
1887 chunk
->flags
= no_power_2
;
1888 if (idx
+ n_items
<= (INTVAL
)chunk
->items
) {
1890 /* LCC has a bug where it can't handle all the temporary
1891 * variables created in this one line. adding an explicit
1892 * one fixes things. No need to force this workaround on
1893 * less brain-damaged compilers though */
1894 size_t tmp_size
= (chunk
->items
- idx
- n_items
) *
1898 (char *) PObj_bufstart(&chunk
->data
) +
1899 idx
* list
->item_size
,
1900 (char *) PObj_bufstart(&chunk
->data
) +
1901 (idx
+ n_items
) * list
->item_size
, tmp_size
);
1904 (char *) PObj_bufstart(&chunk
->data
) +
1905 idx
* list
->item_size
,
1906 (char *) PObj_bufstart(&chunk
->data
) +
1907 (idx
+ n_items
) * list
->item_size
,
1908 (chunk
->items
- idx
- n_items
) * list
->item_size
);
1912 chunk
->items
-= n_items
;
1916 if (idx
== 0 && n_items
>= (INTVAL
)chunk
->items
) {
1917 /* delete this chunk */
1918 n_items
-= chunk
->items
;
1920 /* rebuild_chunk_list will kill it because: */
1924 list
->first
= chunk
->next
;
1927 /* else shrink chunk, it starts at idx then */
1928 if (!(chunk
->flags
& sparse
))
1929 chunk
->flags
= no_power_2
;
1931 n_items
-= chunk
->items
- idx
;
1936 chunk
= chunk
->next
;
1939 rebuild_chunk_ptrs(list
, 1);
1940 rebuild_chunk_list(interp
, list
);
1946 =item C<void list_push(PARROT_INTERP, List *list, void *item, int type)>
1948 Pushes C<item> of type C<type> on to the end of the list.
1956 list_push(PARROT_INTERP
, ARGMOD(List
*list
), ARGIN_NULLOK(void *item
), int type
)
1958 ASSERT_ARGS(list_push
)
1959 const INTVAL idx
= list
->start
+ list
->length
++;
1961 list_append(interp
, list
, item
, type
, idx
);
1967 =item C<void list_unshift(PARROT_INTERP, List *list, void *item, int type)>
1969 Pushes C<item> of type C<type> on to the start of the list.
1977 list_unshift(PARROT_INTERP
, ARGMOD(List
*list
), ARGIN(void *item
), int type
)
1979 ASSERT_ARGS(list_unshift
)
1982 if (list
->start
== 0) {
1983 chunk
= add_chunk_at_start(interp
, list
, 0);
1984 list
->start
= chunk
->items
;
1987 /* XXX This chunk is unused. Why are we getting it? */
1989 chunk
= list
->first
;
1991 list_set(interp
, list
, item
, type
, --list
->start
);
1998 =item C<void * list_pop(PARROT_INTERP, List *list, int type)>
2000 Removes and returns the last item of type C<type> from the end of the list.
2007 PARROT_CAN_RETURN_NULL
2009 list_pop(PARROT_INTERP
, ARGMOD(List
*list
), int type
)
2011 ASSERT_ARGS(list_pop
)
2012 List_chunk
*chunk
= list
->last
;
2015 if (list
->length
== 0)
2018 idx
= list
->start
+ --list
->length
;
2020 if (list
->length
== 0)
2023 /* shrink array if necessary */
2024 if (idx
< list
->cap
- chunk
->items
) {
2025 list
->cap
-= chunk
->items
;
2026 chunk
= list
->last
= chunk
->prev
;
2029 if (list
->n_chunks
<= 2)
2030 list
->first
= list
->last
;
2032 rebuild_chunk_list(interp
, list
);
2035 return list_item(interp
, list
, type
, idx
);
2041 =item C<void * list_shift(PARROT_INTERP, List *list, int type)>
2043 Removes and returns the first item of type C<type> from the start of the list.
2050 PARROT_CAN_RETURN_NULL
2052 list_shift(PARROT_INTERP
, ARGMOD(List
*list
), int type
)
2054 ASSERT_ARGS(list_shift
)
2056 List_chunk
*chunk
= list
->first
;
2059 if (list
->length
== 0)
2064 /* optimize push + shift on empty lists */
2065 if (--list
->length
== 0)
2070 ret
= list_item(interp
, list
, type
, idx
);
2072 if (list
->start
>= chunk
->items
) {
2073 list
->cap
-= chunk
->items
;
2074 chunk
= list
->first
= chunk
->next
? chunk
->next
: list
->last
;
2077 rebuild_chunk_list(interp
, list
);
2079 if (list
->n_chunks
== 1)
2080 list
->last
= list
->first
;
2089 =item C<void list_assign(PARROT_INTERP, List *list, INTVAL idx, void *item, int
2092 Assigns C<item> of type C<type> to index C<idx>.
2100 list_assign(PARROT_INTERP
, ARGMOD(List
*list
), INTVAL idx
, ARGIN_NULLOK(void *item
), int type
)
2102 ASSERT_ARGS(list_assign
)
2103 const INTVAL length
= list
->length
;
2106 idx
= -idx
- length
- 1;
2109 if (idx
>= length
) {
2110 list_append(interp
, list
, item
, type
, list
->start
+ idx
);
2111 list
->length
= idx
+ 1;
2114 list_set(interp
, list
, item
, type
, list
->start
+ idx
);
2120 =item C<void * list_get(PARROT_INTERP, List *list, INTVAL idx, int type)>
2122 Returns the item of type C<type> at index C<idx>.
2129 PARROT_CAN_RETURN_NULL
2130 PARROT_WARN_UNUSED_RESULT
2132 list_get(PARROT_INTERP
, ARGMOD(List
*list
), INTVAL idx
, int type
)
2134 ASSERT_ARGS(list_get
)
2135 const INTVAL length
= list
->length
;
2137 if (idx
>= length
|| -idx
> length
)
2145 return list_item(interp
, list
, type
, idx
);
2151 =item C<void list_splice(PARROT_INTERP, List *list, List *value_list, INTVAL
2152 offset, INTVAL count)>
2154 Replaces C<count> items starting at C<offset> with the items in C<value>.
2156 If C<count> is 0 then the items in C<value> will be inserted after C<offset>.
2164 list_splice(PARROT_INTERP
, ARGMOD(List
*list
), ARGMOD_NULLOK(List
*value_list
),
2165 INTVAL offset
, INTVAL count
)
2167 ASSERT_ARGS(list_splice
)
2168 const INTVAL value_length
= value_list
? value_list
->length
: 0;
2169 const INTVAL length
= list
->length
;
2170 const int type
= list
->item_type
;
2173 if (value_list
&& type
!= value_list
->item_type
)
2174 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
2175 "Item type mismatch in splice\n");
2177 /* start from end */
2181 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_OUT_OF_BOUNDS
,
2182 "illegal splice offset\n");
2185 /* "leave that many elements off the end of the array" */
2187 count
+= length
- offset
+ 1;
2192 /* replace count items at offset with values */
2193 for (i
= j
= 0; i
< count
&& j
< value_length
; i
++, j
++) {
2194 void *val
= list_get(interp
, value_list
, j
, type
);
2196 /* no clone here, if the HL wants to reuse the values, the HL has to */
2197 /* clone the values */
2199 /* XXX We don't know that val is non-NULL coming back from list_get. */
2200 /* We need to check that we're not dereferencing NULL. */
2201 if (type
== enum_type_PMC
)
2203 else if (type
== enum_type_STRING
)
2204 val
= *(STRING
**)val
;
2206 list_assign(interp
, list
, offset
+ i
, val
, type
);
2209 /* if we still have values in value_list, insert them */
2210 if (j
< value_length
) {
2211 /* make room for the remaining values */
2212 list_insert(interp
, list
, offset
+ i
, value_length
- j
);
2214 for (; j
< value_length
; i
++, j
++) {
2215 void *val
= list_get(interp
, value_list
, j
, type
);
2217 /* XXX We don't know that val is non-NULL coming back from
2218 * list_get; check that we're not dereferencing NULL. */
2219 if (type
== enum_type_PMC
)
2221 else if (type
== enum_type_STRING
)
2222 val
= *(STRING
**)val
;
2224 list_assign(interp
, list
, offset
+ i
, val
, type
);
2227 /* else delete the rest */
2229 list_delete(interp
, list
, offset
+ i
, count
- i
);
2243 * c-file-style: "parrot"
2245 * vim: expandtab shiftwidth=4: