[gclist] Baker's treadmill without a doubly linked list.

[James McCartney]

At 8:44 PM -0800 1/29/97, Henry G. Baker wrote:
>> At 3:24 PM -0800 1/29/97, Henry G. Baker wrote:
>> >
>> >Isn't this essentially the _original_ (1976-78) RTGC algorithm for
>> >'displaced' (CL/Maclisp terminology) objects (i.e., objects with
>> >headers) ??
>>
>> I don't know. What's the reference? If it is then why was the linked
>> list introduced?
>
>Try ftp://ftp.netcom.com/pub/hb/hbaker/RealTimeGC.html (also .ps.Z).

OK I just looked at that paper. That is a copying GC. The method I posted
is a noncopying GC. No objects are moved. So it is not the same.

Here is a simplified version of the basic operations:

#define NUMSLOTS 32
#define NUMOBJECTS 10000

typedef struct obj {
    int gc_index;
    struct obj *slot[NUMSLOTS];
} MemObject;

MemObject* gc_root;
MemObject* gc_table[NUMOBJECTS];

int scan_index, white_index, allocate_index;

MemObject* allocate()
{
    return gc_table + allocate_index++;
}

/* get an object to scan */
MemObject* next_grey()
{
    return gc_table + scan_index++;
}

void write_barrier(MemObject* container, MemObject* containee, int slot_index)
{
    if (container->gc_index < scan_index /* is container black ? */
     && containee->gc_index >= white_index) /* is containee white ? */
    {
	white_to_grey(containee);
    }
    container->slot[slot_index] = containee;
}

/* make obj grey */
void white_to_grey(MemObject *obj)
{
    MemObject* temp_ptr;

    /* swap pointers in the table */
    temp_ptr = gc_table[white_index];
    gc_table[white_index] = gc_table[obj->gc_index];
    gc_table[obj->gc_index] = temp_ptr;

    /* fix indices */
    gc_table[white_index]->gc_index = white_index;
    gc_table[obj->gc_index]->gc_index = obj->gc_index;

    white_index++; /* the object is now in the grey region */
}

void gc_flip()
{
    allocate_index = white_index;
    white_index = 0;
    scan_index = 0;
    white_to_grey(gc_root);
}


   --- james mccartney     james@clyde.as.utexas.edu   james@lcsaudio.com
If you have a PowerMac check out SuperCollider, a real time synth program:
ftp://mirror.apple.com//mirrors/Info-Mac.Archive/gst/snd/super-collider-demo.hqx