Re: Question concerning linked lists

From: Daniel A. Koepke (
Date: 12/14/99

On Tue, 14 Dec 1999, Jason Beeland wrote:

> The goal of this code is to make a linked list of only special doors
> to be checked every tick. This way i don't have to process every exit
> on the mud every tick to decrement counters and remove flags from door
> affecting spells.  Also this way i can put the timer interger and
> owner variable only on the special doors, to further conserve memory.
> Unfortunately I'm not that terribly familiar with how to create and
> modify linked lists (i know what i have learned from the example on
> the mud itself) and i seem to have some bugs to work out.  The code
> for the spell CREATE()'s a spec_door variable and theninserts the
> propper data into the fields.  Then it links it to the spec_door_list
> list.

Just to go over some linked list theory, first.  As your list only has one
link, it's called a singly linked list.  There are also doubly linked
list, which hold more relational data (specifically, a "prev" pointer to
keep track of what comes before it).  Doubly linked lists add 4 bytes (or
more -- I assume everyone is using a 32 bit architecture, here) to each
node (i.e., member) of the list, but are less computationally intensive
for many sorts of storing (push) and removal (pop) operations.  Singly
linked lists require 4 fewer bytes per node (because they only keep one
pointer, "next" in our case) but require more CPU for certain
operations.  CircleMUD uses singly linked lists because memory is more of
a concern for muds than is CPU and most linked list operations in
CircleMUD are fairly simple (i.e., no sorted pushes, etc.).

> struct spec_door {
>     struct room_direction_data *door;
>     int timer;
>     char *owner;

Is that a 'struct char_data *owner'?  Not that it matters, but I'm just
curious what you're storing there.

>         for(k = spec_door_list; k ; k = k->next) {
>           if( k->door == EXITN(ch->in_room, door)) break;
>         }
>         REMOVE_FROM_LIST(k, spec_door_list, next);

If you're under Linux or a UNIX operating system and have the 'gdb'
debugger, enter gdb with: "gdb bin/circle lib/core" and type 'bt 5' to get
the first 5 stack frames.  Looking for some variable that is NULL
(0x0) when it shouldn't be is a good idea.  You can use "print" followed
by the name of some variable within the current frame to print its memory
address and/or contents.  For instance, if frame #0 has a 'ch' variable in
it, "print ch," would print the pointers address and, "print *ch," would
print the contents of that memory address.  You can switch frames with the
"frame" command.  The default frame is 0.

Also, if the entry is not found in the list, k will be NULL (0x0) and will
probably cause a crash.

Next, this is rather inefficient code.  We're looping through the list
once to find the special door (k), and then if that door is not the head
of the list (k = spec_door_list), we end up going through the list again
in REMOVE_FROM_LIST.  This is unnecessary, and can be compacted to:

    struct spec_door *kPrev;

    for (kPrev = NULL, k = spec_door_list; k; kPrev = k, k = k->next)
        if (k->door == EXITN(ch->in_room, door))

    if (k) {
        if (kPrev) {
            /* I.e., we're not the head of the list. */
            kPrev->next = k->next;
        } else {
            /* I.e., we are the head of the list. */
            spec_door_list = spec_door_list->next;

Finally, note that unless you have a special EX_ flag to indicate when an
exit should be checked, you'll still be passing potentially every exit in
the game to this code, depending upon when it's called.

> when removing a item from this linked list, i assume i should free it.

As a general rule, anything you CREATE [malloc()/calloc()/realloc()] that
you no longer need should be free()'d.  Failing to do so is a memory leak.
The same goes for things that return CREATE'd memory.  Such as strdup()
and str_dup(), fopen(), and others.

> I have written a free_spec_door() function, but could someone more
> knowledgeable about this give me what is -correct- for a
> free_spec_door function, givin the above structure for spec_door? I
> really appreaciate all the help, and the CM mailing list is already in
> the credits on my login page.  :-) thanks all


You don't want to free toFree->door, unless you really want to remove some
room's exit; and, if toFree->owner is not memory that you CREATE
specifically for spec_door_list, I assume you don't want to free it,
either.  Making this is a separate function is kind of pointless, since
it's one whole statement.

So, basically, in the above removal code you'd add "free(k);" just before
the closing brace for the "if (k) {" clause...


     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     |  |

This archive was generated by hypermail 2b30 : 12/15/00 PST