# New Ticket Created by Leopold Toetsch # Please include the string: [perl #17569] # in the subject line of all future correspondence about this issue. # <URL: http://rt.perl.org/rt2/Ticket/Display.html?id=17569 >
This is an update/bugfix - t/src/intlist.t was missing - find_chunk was partly wrong for shift/unshift - new shift/unshift integer in pmc Please apply, leo -- attachment 1 ------------------------------------------------------ url: http://rt.perl.org/rt2/attach/38541/31336/445379/intlist-2.patch
--- parrot/intlist.c Mon Sep 9 07:47:48 2002 +++ parrot-leo/intlist.c Tue Sep 24 22:24:50 2002 @@ -77,8 +77,10 @@ #include "parrot/parrot.h" #include "parrot/intlist.h" +static size_t rebuild_chunk_list(Interp *interpreter, IntList *list); + IntList* -intlist_new(Interp *interpreter) +intlist_new(Interp *interpreter, int initial) { IntList* list; @@ -93,6 +95,13 @@ interpreter->GC_block_level++; Parrot_allocate(interpreter, (Buffer*) list, INTLIST_CHUNK_SIZE * sizeof(INTVAL)); + if (initial) { + /* XXX managed memory or custom destroy? */ + list->chunk_list = mem_sys_allocate(sizeof(IntList_Chunk *)); + list->n_chunks = 1; + list->collect_runs = interpreter->dod_runs; + list->chunk_list[0] = (IntList_Chunk*) list; + } interpreter->DOD_block_level--; interpreter->GC_block_level--; return list; @@ -136,6 +145,26 @@ fprintf(fp, "\n"); } +static size_t +rebuild_chunk_list(Interp *interpreter, IntList *list) +{ + IntList_Chunk* chunk = (IntList_Chunk*) list; + IntList_Chunk* lastChunk = list->prev; + size_t len = 0; + while (1) { + if (len >= list->n_chunks) + list->chunk_list = mem_sys_realloc(list->chunk_list, + (len + 1)* sizeof(IntList_Chunk *)); + list->chunk_list[len] = chunk; + len++; + if (chunk == lastChunk) break; + chunk = chunk->next; + } + list->collect_runs = interpreter->dod_runs; + list->n_chunks = len; + return len; +} + static void add_chunk(Interp* interpreter, IntList* list) { @@ -143,7 +172,7 @@ if (chunk->next == list) { /* Need to add a new chunk */ - IntList_Chunk* new_chunk = intlist_new(interpreter); + IntList_Chunk* new_chunk = intlist_new(interpreter, 0); new_chunk->next = list; new_chunk->prev = chunk; chunk->next = new_chunk; @@ -161,6 +190,7 @@ add_chunk(interpreter, list); list->prev->start = 0; list->prev->end = 0; + rebuild_chunk_list(interpreter, list); } static void @@ -192,12 +222,17 @@ IntList_Chunk* chunk = (IntList_Chunk *) *list; INTVAL length = chunk->length + 1; INTVAL offset; + IntList_Chunk * o = chunk; + size_t n = chunk->n_chunks; /* Add on a new chunk if necessary */ if (chunk->start == 0) { unshift_chunk(interpreter, *list); chunk = chunk->prev; *list = chunk; + (*list)->chunk_list = o->chunk_list; + (*list)->n_chunks = n; + rebuild_chunk_list(interpreter, *list); } ((INTVAL*)chunk->buffer.bufstart)[--chunk->start] = data; @@ -211,6 +246,8 @@ IntList_Chunk* chunk = (IntList_Chunk *) *list; INTVAL length = chunk->length - 1; INTVAL value; + IntList_Chunk * o = chunk; + size_t n = chunk->n_chunks; if (chunk->start >= chunk->end) { internal_exception(OUT_OF_BOUNDS, "No entries on list!\n"); @@ -225,6 +262,9 @@ chunk->next->prev = chunk->prev; chunk->prev->next = chunk; *list = chunk->next; + (*list)->chunk_list = o->chunk_list; + (*list)->n_chunks = n; + rebuild_chunk_list(interpreter, *list); } (*list)->length = length; @@ -245,6 +285,7 @@ chunk->next = list; list->prev = chunk->prev; chunk = chunk->prev; + list->n_chunks--; } /* Quick sanity check */ @@ -265,6 +306,13 @@ IntList_Chunk* chunk = list; UNUSED(interpreter); +#if 1 + if (list->collect_runs != interpreter->dod_runs) + rebuild_chunk_list(interpreter, list); + idx += chunk->start; + + return list->chunk_list[idx / INTLIST_CHUNK_SIZE]; +#else /* Possible optimization: start from the closer end of the chunk list */ /* Find the chunk containing the requested element */ @@ -274,6 +322,7 @@ } return chunk; +#endif } INTVAL @@ -347,7 +396,9 @@ chunk = find_chunk(interpreter, list, idx); - ((INTVAL*)chunk->buffer.bufstart)[idx] = val; + if (idx >= list->end - list->start) idx -= list->end - list->start; + idx = idx % INTLIST_CHUNK_SIZE; + ((INTVAL*)chunk->buffer.bufstart)[idx + chunk->start] = val; } /* --- parrot/include/parrot/intlist.h Mon Sep 9 07:49:08 2002 +++ parrot-leo/include/parrot/intlist.h Tue Sep 24 06:32:06 2002 @@ -24,7 +24,10 @@ struct IntList_chunk_t { Buffer buffer; /* This struct is a Buffer header subclass! */ - INTVAL length; /* Only valid for the "head" chunk */ + INTVAL length; /* Only valid for the "head" chunk (1) */ + size_t collect_runs; /* when chunklist was built (1) */ + IntList_Chunk ** chunk_list; /* list of chunks for fast access (1) */ + size_t n_chunks; /* number of chunks in chunk_list */ INTVAL start; INTVAL end; IntList_Chunk* next; @@ -35,7 +38,7 @@ PMC* intlist_mark(Interp*, IntList*, PMC* last); -IntList *intlist_new(Interp*); +IntList *intlist_new(Interp*, int initial); static INTVAL intlist_length(Interp* interpreter, IntList* list) { --- parrot/classes/intlist.pmc Mon Sep 9 07:48:15 2002 +++ parrot-leo/classes/intlist.pmc Tue Sep 24 07:44:27 2002 @@ -30,7 +30,7 @@ } void init () { - SELF->data = intlist_new(INTERP); + SELF->data = intlist_new(INTERP, 1); SELF->cache.int_val = 0; SELF->flags |= PMC_custom_mark_FLAG; } @@ -170,4 +170,13 @@ THROW_UNSUPPORTED; return 0; } + + void unshift_integer (INTVAL value) { + intlist_unshift(INTERP, (IntList**) &SELF->data, value); + } + + INTVAL shift_integer() { + return intlist_shift(INTERP, (IntList**) &SELF->data); + } + } --- parrot/t/pmc/intlist.t Mon Sep 9 07:49:35 2002 +++ parrot-leo/t/pmc/intlist.t Tue Sep 24 08:20:49 2002 @@ -1,6 +1,6 @@ #! perl -w -use Parrot::Test tests => 2; +use Parrot::Test tests => 4; use Test::More; output_is(<<'CODE', <<'OUTPUT', "creation"); @@ -145,3 +145,87 @@ CODE I need a shower. OUTPUT + +output_is(<<'CODE', <<'OUTPUT', "direct access"); + new P0, .IntList + set S0, "" + set S1, "abcdefghijklmnopqrst" + set I10, 100000 + set I0, 0 +lp: + set P0[I0], I0 + inc I0 + mod I9, I0, 100 + ne I9, 0, lp1 + # force GC => 142 DOD + 142 collects / 10^5 accesses + new P1, .PerlArray + set P1[I0], I0 + concat S0, S1, S1 + set S2, S0 + set S0, S1 + set S2, "" +lp1: + le I0, I10, lp + + set I0, 0 +lp2: + set I1, P0[I0] + ne I0, I1, err + inc I0 + le I0, I10, lp2 + print "ok\n" + end +err: + print "err: wanted " + print I0 + print " got " + print I1 + print "\n" + end +CODE +ok +OUTPUT + +output_is(<<'CODE', <<'OUTPUT', "shift/unshift"); + new P0, .IntList + set I10, 100000 + set S0, "" + set S1, "abcdefghijklmnopqrst" + set I0, 0 +lp: + unshift P0, I0 + inc I0 + mod I9, I0, 100 + ne I9, 0, lp1 + # force GC => 124 DOD + 124 collects / 10^5 accesses + new P1, .PerlArray + set P1[I0], I0 + concat S0, S1, S1 + set S2, S0 + set S0, S1 + set S2, "" +lp1: + ne I0, I10, lp +lp2: + dec I0 + shift I1, P0 + ne I0, I1, err + ne I0, 0, lp2 + print "ok 1\n" + set I1, P0 + set I0, 0 + ne I0, 0, err + print "ok 2\n" + end +err: + print "err: wanted " + print I0 + print " got " + print I1 + print "\n" + end +CODE +ok 1 +ok 2 +OUTPUT + --- parrot/t/src/intlist.t Tue Sep 10 12:17:00 2002 +++ parrot-leo/t/src/intlist.t Tue Sep 24 21:26:48 2002 @@ -15,7 +15,7 @@ if (interpreter == NULL) return 1; Parrot_init(interpreter, (void*) &interpreter); - list = intlist_new(interpreter); + list = intlist_new(interpreter, 1); if (list == NULL) return 1; intlist_push(interpreter, list, 42); @@ -44,7 +44,7 @@ if (interpreter == NULL) return "create interpreter"; Parrot_init(interpreter, (void*) &interpreter); - list = intlist_new(interpreter); + list = intlist_new(interpreter, 1); if (list == NULL) return "create list"; /* Push 3, then pop 2. Repeat N times. */ @@ -134,7 +134,7 @@ for (i = 0; i < N; i++) { if (intlist_get(interpreter, list, i+ground) != i * 3) { sprintf(msg, "get from left: wanted %d, got %d", - i * 3, intlist_get(interpreter, list, i)); + i * 3, intlist_get(interpreter, list, i+ground)); return msg; } } @@ -177,7 +177,7 @@ if (interpreter == NULL) return 1; Parrot_init(interpreter, (void*) &interpreter); - list = intlist_new(interpreter); + list = intlist_new(interpreter, 1); if (list == NULL) return 1; printf("Step 1: 0\n"); @@ -282,7 +282,7 @@ if (interpreter == NULL) return 1; Parrot_init(interpreter, (void*) &interpreter); - list = intlist_new(interpreter); + list = intlist_new(interpreter, 1); if (list == NULL) return 1; for (i = 0; i < INTLIST_CHUNK_SIZE * 2.5; i++) {