Site hosted by Angelfire.com: Build your free website today!
Using Linked Lists in ROM

ROM uses singly linked lists for just about everything. So in this document I'll be looking into how to create them, how to use them, and how to prevent crashes from trying to use NULL pointers.

Linked List Basics

A linked list takes the form of a structure containing a next pointer to another structure of the same type: 

struct whatever
{
    /* Point to the next element in the list */
    struct whatever *next;
};

Now you have the head of the list: 

struct whatever *head_of_list;

Whenever you need to search through the list, you can just use a simple for loop: 

struct whatever *blah;



for( blah = head_of_list; blah; blah = blah->next )
{
    ...
}

IMPORTANT NOTE - If we intended to free blah anywhere inside the for loop the above code would not work as intended. This is because when the loop comes to access blah->next, blah will be a NULL pointer (giving unpredictable results). Instead we must do the following: 

struct whatever *blah, *blah_next;



for( blah = head_of_list; blah; blah = blah_next )
{
    blah_next = blah->next;
    ...
}

IMPORTANT NOTE - The above code should definitely NOT be used in all cases, just those requiring it. If we free the structure pointed to by blah->next anywhere in the for loop, then blah_next will be a NULL pointer. It may not be obvious where a structure is freed, you have to think of possible situations - a final measure is to work through all the functions inside the for loop and see what can possibly be freed.

Memory Management in ROM

All the structures in ROM are allocated by functions in the recycle.c file, a quick look through that should be enough for most programmers to work out how structures are allocated.

Basically, ROM allocates memory for structures on a permanent basis. When a structure can be freed, ROM adds it to a free list. Whenever a new structure needs to be allocated, ROM first checks to see if there's an appropriate block of memory available on that structure type's free list. If there is then ROM just points the new structure at the head of the free list (for that type), and points the head of the free list to the next free memory block.

Here's a simple example from my MobProg variables code. The code is pretty much the same for any structure: 

/* The free list */
MPROG_VAR *mpvar_free;



MPROG_VAR *new_var( void )
{
    /* Used to empty recycled structures */
    static MPROG_VAR mp_zero;
    /* Our list pointer */
    MPROG_VAR *mp;



/* Check for previously freed structures */
    if (mpvar_free == NULL)
        mp = alloc_perm(sizeof(*mp));
    else
    {
        /* Got one so point to it */
        mp = mpvar_free;
        /* Move the free list on one */
        mpvar_free=mpvar_free->next;
    }



/* Empty recycled structures */
    *mp = mp_zero;
    /* Zero value - not really necessary but better to be safe */
    mp->value = 0;
    /* Return new structure */
    return mp;
}



void free_var(MPROG_VAR *mp)
{
    /* Free internal dynamically allocated data */
    free_string( mp->name );
    /* Set next pointer to current head of free list */
    mp->next = mpvar_free;
    /* Point head of free list to mp */
    mpvar_free = mp;
}

Definitions in Merc.h

In merc.h you'll find several lines like this: 

typedef struct  mprog_var       MPROG_VAR;

This just tells the compiler that we will be referring to struct mprog_var as simply MPROG_VAR. It is mostly for convenience - imagine having to type struct mprog_var every time.

That's about all you need to know about linked lists in ROM. Doubly linked lists are not used (or really needed) anywhere in the code, and I doubt you'd find a use for one anyway.

Mail me at dasran@claramail.com

"MERC/Derivative Programmers" webring [Next] [Index] [Prev] [Joining]