# 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++) {
