|parrotcode: Regex stack handling routines|
|Contents | C|
src/intlists.c - Regex stack handling routines
intlist emulation code, calls routines in src/list.c.
Here is the original documentation for intlist:
The basic data structure is a variant of a doubly-linked list of 'chunks',
where a chunk is a
Buffer header subclass containing the link pointers and other metadata for the chunk.
As expected from it being a
PObj_bufstart field points to the actual array of
The handle used by external code for one of these IntLists is just a pointer to a chunk,
always called 'list' in this code.
For now, all of the chunks are fixed-length in size. (That could easily be changed, at the cost of another integer in each header.)
Notice that I said 'variant' of a doubly-linked list.
That is because if you start at 'list' and follow prev pointers,
you will loop through all the used nodes of the list,
But if you follow next pointers instead,
you might find a spare node hanging off the last node in the list (the last node is always
so if there is a spare node,
it will be at
If no spare exists,
The first node in the list may be partly full; the intermediate nodes are always completely full; and the last node may be partly full.
Each node has a
giving the offset of the first valid element (always zero except for possibly the first node),
giving one past the offset of the last valid element (always equal to
INTLIST_CHUNK_SIZE except for possibly the last node).
To make it concrete,
let's walk through some sample operations.
To push onto the end of the list,
first find the last chunk:
chunk->end < INTLIST_CHUNK_SIZE,
there is space to fit another element and so just stick it in.
we must add a chunk to the end of the list.
If there is a spare,
just link it fully into the list (forming a conventional doubly-linked list).
create a new chunk and link it fully into the list.
To pop something off the end,
first go to the end chunk (
Pop off an element and decrement
.end if the chunk is nonempty.
If it is empty,
make that last chunk into the spare (discarding the previous spare).
Then go to the previous chunk,
which is guaranteed to have
.end set to
The length of the list is always cached in the overall header chunk. If an operation changes which chunk is the header (i.e., shift or unshift), then the length is copied to the new header.
There is always space in
list->prev to insert an element.
The 'list' chunk is never empty unless the entire list is empty.
In combination, the above invariants imply that the various operations are implemented as:
Direct aka indexed access of intlist data:
The classic method would be to walk the
intlist->next pointers (or optimized,
->prev pointers if an index near the end is requested) and locate the chunk,
that holds the wanted list item.
To speed things up, especially for bigger lists, there are additional fields in the 'list' (the head chunk):
chunk_listwas rebuilt last.
If on any indexed access interpreter's collect_runs is different, the chunks might have been moved, so the chunk_list has to be rebuilt.
Getting data outside the array dimensions will return the value
the intlist did an explicit exception,
so there is not much difference.
a check for valid pointers could be added here.
void intlist_mark(Interp *i, IntList *l)
IntList *intlist_clone(Interp *i, IntList *list)
IntList *intlist_new(Interp *i)
INTVAL intlist_length(Interp *interpreter, IntList *list)
void intlist_assign(Interp *i, IntList *l, INTVAL idx, INTVAL val)
void intlist_push(Interp *i, IntList *l, INTVAL val)
valon the end of the list.
void intlist_unshift(Interp *i, IntList **l, INTVAL val)
valon the front of the list.
INTVAL intlist_pop(Interp *i, IntList *l)
INTVAL intlist_shift(Interp *i, IntList **l)
INTVAL intlist_get(Interp *i, IntList *l, INTVAL idx)
void intlist_dump(FILE *fp, IntList *list, int verbose)
include/parrot/intlist.h, src/list.c and include/parrot/list.h.