At 4:44 PM +0200 9/27/02, Leopold Toetsch wrote:
>Tom Hughes wrote:
>
>>In message <[EMAIL PROTECTED]>
>> Leopold Toetsch <[EMAIL PROTECTED]> wrote:
>
>
>>I applied this to my checkout (with _intlist_new renamed to
>>allocate_chunk because names starting with _ are reserved).
>
>
>Ah, didn't know that - ok changed too.
>
>>Unfortunately it doesn't test clean afterwards:
>>
>>dunsmere [~/src/parrot] % perl t/harness t/pmc/intlist.t
>>t/pmc/intlist....NOK 3# Failed test (t/pmc/intlist.t at line 149)
>># got: ''
>
>
>Ah, dumps core, aha GC, ahaaha junk_list moved. I ran the tests with
>my Lea allocator in place, which doesn't suffer from this problem ;-)
>
>Anyway here is an update, tested with CVS GC.
>
>Additionally indexed access is simplified by a view lines.
>
>Thanks for testing and sorry,
>leo
>
>
>--- parrot/intlist.c Thu Sep 26 18:30:29 2002
>+++ parrot-leo/intlist.c Fri Sep 27 16:32:26 2002
>@@ -70,6 +70,24 @@
> * shift: read element, discard chunk and advance if necessary
> * unshift: unshift a chunk if necessary, write element
> *
>+ * Direct aka indexed access of intlist data:
>+ *
>+ * The classic method would be to walk the intlist->next pointers
>+ * (or optimized, the ->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_list ... holds pointers to individual chunks
>+ * collect_runs ... collect_runs counter, when chunk_list was
>+ * rebuilt last.
>+ * n_chunks ... used length in chunk_list
>+ *
>+ * 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.
>+ *
>+ *
> * History:
> * Notes:
> * References: */
>@@ -78,9 +96,29 @@
> #include "parrot/intlist.h"
>
> static size_t rebuild_chunk_list(Interp *interpreter, IntList *list);
>+static IntList* allocate_chunk(Interp *interpreter, int initial);
>+static size_t rebuild_chunk_list(Interp *interpreter, IntList *list);
>
> IntList*
>-intlist_new(Interp *interpreter, int initial)
>+intlist_new(Interp *interpreter) {
>+ return allocate_chunk(interpreter, 1);
>+}
>+
>+/* growth increment of chunk_list, must be a power of 2 */
>+#define CL_SIZE 16
>+
>+/* Buffers store the used len in bytes in buflen
>+ * so, the len in entries is: */
>+
>+#define chunk_list_size(list) \
>+ (list->chunk_list.buflen / sizeof(IntList_Chunk *))
>+
>+/* hide the ugly cast somehow: */
>+#define chunk_list_ptr(list, idx) \
>+ ((IntList_Chunk**)list->chunk_list.bufstart)[idx]
>+
>+static IntList*
>+allocate_chunk(Interp *interpreter, int initial)
> {
> IntList* list;
>
>@@ -96,11 +134,8 @@
> 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;
>+ /* we have a cleared list, so no need to zero chunk_list */
>+ rebuild_chunk_list(interpreter, list);
> }
> interpreter->DOD_block_level--;
> interpreter->GC_block_level--;
>@@ -115,10 +150,11 @@
> buffer_lives((Buffer *) chunk);
> chunk = chunk->next;
> } while (chunk != (IntList_Chunk*) list);
>-
>+ buffer_lives(&list->chunk_list);
> return last;
> }
>
>+#ifdef INTLIST_DEBUG
> void
> intlist_dump(FILE* fp, IntList* list, int verbose)
> {
>@@ -144,6 +180,7 @@
>
> fprintf(fp, "\n");
> }
>+#endif
>
> static size_t
> rebuild_chunk_list(Interp *interpreter, IntList *list)
>@@ -151,16 +188,25 @@
> IntList_Chunk* chunk = (IntList_Chunk*) list;
> IntList_Chunk* lastChunk = list->prev;
> size_t len = 0;
>+ /* allocate a new chunk_list buffer, old one my have moved
>+ * firsr, count chunks */
> 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;
>+ Parrot_allocate(interpreter, &list->chunk_list,
>+ (len+1) * sizeof(IntList_Chunk *));
>+ len = 0;
>+ chunk = list;
>+ /* then fill list */
>+ while (1) {
>+ chunk_list_ptr(list, len) = (IntList_Chunk*) chunk;
>+ len++;
>+ if (chunk == lastChunk) break;
>+ chunk = chunk->next;
>+ }
>+ list->collect_runs = interpreter->collect_runs;
> list->n_chunks = len;
> return len;
> }
>@@ -172,7 +218,7 @@
>
> if (chunk->next == list) {
> /* Need to add a new chunk */
>- IntList_Chunk* new_chunk = intlist_new(interpreter, 0);
>+ IntList_Chunk* new_chunk = allocate_chunk(interpreter, 0);
> new_chunk->next = list;
> new_chunk->prev = chunk;
> chunk->next = new_chunk;
>@@ -190,7 +236,17 @@
> add_chunk(interpreter, list);
> list->prev->start = 0;
> list->prev->end = 0;
>+ /* optimization, add new chunk directly, if still space
>+ * but only, if no collections was done in between
>+ */
>+ if (list->n_chunks >= chunk_list_size(list) ||
>+ list->collect_runs != interpreter->collect_runs)
> rebuild_chunk_list(interpreter, list);
>+ else {
>+ /* add the appended = last chunk = list->prev to chunk_list */
>+ chunk_list_ptr(list, list->n_chunks) = list->prev;
>+ list->n_chunks++;
>+ }
> }
>
> static void
>@@ -223,15 +279,15 @@
> 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;
>+ /* move chunk_list to new list head */
> (*list)->chunk_list = o->chunk_list;
>- (*list)->n_chunks = n;
>+ /* and rebuild it from scratch */
> rebuild_chunk_list(interpreter, *list);
> }
>
>@@ -247,7 +303,6 @@
> 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");
>@@ -262,8 +317,8 @@
> chunk->next->prev = chunk->prev;
> chunk->prev->next = chunk;
> *list = chunk->next;
>+ /* like above */
> (*list)->chunk_list = o->chunk_list;
>- (*list)->n_chunks = n;
> rebuild_chunk_list(interpreter, *list);
> }
>
>@@ -285,6 +340,7 @@
> chunk->next = list;
> list->prev = chunk->prev;
> chunk = chunk->prev;
>+ /* chunk_list hold one less valid entry now */
> list->n_chunks--;
> }
>
>@@ -306,23 +362,9 @@
> IntList_Chunk* chunk = list;
> UNUSED(interpreter);
>
>-#if 1
>- if (list->collect_runs != interpreter->dod_runs)
>+ if (list->collect_runs != interpreter->collect_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 */
>- while (idx >= chunk->end - chunk->start) {
>- idx -= chunk->end - chunk->start;
>- chunk = chunk->next;
>- }
>-
>- return chunk;
>-#endif
>+ return chunk_list_ptr(list, idx / INTLIST_CHUNK_SIZE);
> }
>
> INTVAL
>@@ -339,13 +381,13 @@
> }
>
> if (idx < 0) idx += length;
>+ idx += list->start;
>
> chunk = find_chunk(interpreter, list, idx);
>
>- if (idx >= list->end - list->start) idx -= list->end - list->start;
> idx = idx % INTLIST_CHUNK_SIZE;
>
>- return ((INTVAL*)chunk->buffer.bufstart)[idx + chunk->start];
>+ return ((INTVAL*)chunk->buffer.bufstart)[idx];
> }
>
> static void
>@@ -394,11 +436,11 @@
> intlist_extend(interpreter, list, idx + 1);
> }
>
>+ idx += list->start;
> chunk = find_chunk(interpreter, list, idx);
>
>- if (idx >= list->end - list->start) idx -= list->end - list->start;
> idx = idx % INTLIST_CHUNK_SIZE;
>- ((INTVAL*)chunk->buffer.bufstart)[idx + chunk->start] = val;
>+ ((INTVAL*)chunk->buffer.bufstart)[idx] = val;
> }
>
> /*
>--- parrot/include/parrot/intlist.h Thu Sep 26 18:30:30 2002
>+++ parrot-leo/include/parrot/intlist.h Fri Sep 27 12:10:47 2002
>@@ -24,10 +24,12 @@
>
> struct IntList_chunk_t {
> Buffer buffer; /* This struct is a Buffer header subclass! */
>- 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 length; /* number of items in list (1) */
>+ size_t collect_runs; /* counter, when chunklist was built (1) */
>+ Buffer chunk_list; /* holding list of chunks for fast
>access (1) */
>+ size_t n_chunks; /* number of used chunks in chunk_list (1) */
>+ /* all above items, marked (1) are only valid in the head junk
>+ * s. intlist.c for a detailled description */
> INTVAL start;
> INTVAL end;
> IntList_Chunk* next;
>@@ -38,7 +40,7 @@
>
> PMC* intlist_mark(Interp*, IntList*, PMC* last);
>
>-IntList *intlist_new(Interp*, int initial);
>+IntList *intlist_new(Interp*);
>
> static INTVAL intlist_length(Interp* interpreter, IntList* list)
> {
>--- parrot/classes/intlist.pmc Thu Sep 26 18:30:30 2002
>+++ parrot-leo/classes/intlist.pmc Fri Sep 27 11:55:15 2002
>@@ -30,7 +30,7 @@
> }
>
> void init () {
>- SELF->data = intlist_new(INTERP, 1);
>+ SELF->data = intlist_new(INTERP);
> SELF->cache.int_val = 0;
> SELF->flags |= PMC_custom_mark_FLAG;
> }
>--- parrot/t/src/intlist.t Thu Sep 26 18:30:36 2002
>+++ parrot-leo/t/src/intlist.t Fri Sep 27 15:42:25 2002
>@@ -15,7 +15,7 @@
> if (interpreter == NULL) return 1;
> Parrot_init(interpreter, (void*) &interpreter);
>
>- list = intlist_new(interpreter, 1);
>+ list = intlist_new(interpreter);
> 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, 1);
>+ list = intlist_new(interpreter);
> if (list == NULL) return "create list";
>
> /* Push 3, then pop 2. Repeat N times. */
>@@ -177,7 +177,7 @@
> if (interpreter == NULL) return 1;
> Parrot_init(interpreter, (void*) &interpreter);
>
>- list = intlist_new(interpreter, 1);
>+ list = intlist_new(interpreter);
> 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, 1);
>+ list = intlist_new(interpreter);
> if (list == NULL) return 1;
>
> for (i = 0; i < INTLIST_CHUNK_SIZE * 2.5; i++) {
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
