Re: Arrays and Linked Lists

From: Patrick Dughi (dughi@imaxx.net)
Date: 04/27/00


> I searched the archives for previous posts regarding storing the world
> within an array and found some references, but no real practical advice on
> how to create one.

        In general, arrays are created with a simple instruction:

int x_array[20];
        or
int x_array[] = {
        .
        .
        .
};
        However, most of the arrays you're talking about are generated
dynamically - they often need to be resized not only during the
initalization stage, but also during actual game-in-progress stage.  These
are generally performed via the RECREATE macro, which uses realloc(3) -
more on this below.  Generally speaking though, you just create a pointer
to that sort of data type (ie int *x_array;), and then realloc your size
realloc(x_array, sizeof(int) * 20).  Then you treat it like an array.

> However, it appears that an array will make things infinitely simpler
> for my mud.  So, my question is this: What's a practical manner in which
> I can discover the required limits for an array with minimal time and
> memory?  Actual code isn't required, rather just an explanation of the
> mechanics.

        Now, if you're just trying to find the size of any given array,
just do sizeof(array) / sizeof( type of array member).  In general,
sizeof(variable) will give you the size, though this will give you the
uh..byte count, so you'll want to always divide by the return of
sizeof(int/char/struct x/etc), to get the actual number used.

>  The reason a linked list was used was because linked lists have no
> boundaries or limits, while one must define the limits, creating waste
> or too many rooms.

        Waste or too many rooms? Hm.

        Actually, if I were to hazzard a guess, I'd say linked lists were
not used because of the variable access time.  See, if I were performing a
'tell', first i'd have to lookup the room my first character was in; i'd
iterate down the entire list of rooms till I found the one my character
was in; I'd then check for the silent flag.  Then, I'd iterate down the
list again to find the room that my second character (the one being told)
was in.  Now, consider that there are hundreds of function calls which
occur in the space between player input cycles; each of these, when
referencing a room would have to iterate through the entire list.  Now, if
I have an array, it's a single lookup:

Room Number             Iterations with linked lists    Iterations w/array
    1                                 1                          1
    10                               10                          1
  3,002,002,122                 3,002,002,122                    1

        You get the idea.

        The problems inherent with using arrays though are twofold; first,
you do have a predefined upper limit(though you do define it).  If you
want to add or remove a member permanantly, it's a rough task.  Depending
on the job, you would probably use realloc() to redefine your array size,
and then run through the array and 'bump' everything up or down as
necessary.  Then, you'd want to validate all rnum/etc references in the
rest of active memory space (character 'in_room' if you're altering the
'world' struct, for example). That is, all references to rnum 445 will
have to be changed to rnum 456, etc.  Matter of fact, if you have alot of
builders, you may even see issues where if someone redits a new room,
while someone above them (in vnums) is rediting, certain information
regarding that upper room may alter/write out incorrectly.  Because this
information is usually fixed without anyones knowledge after the next edit
of that zone it's usually not a problem - but if you crash, you chance
mangled (and unloadable) zones.

        The second thing is that (as you can see above) it is much more
difficult to keep your array references valid (or at least correct).  Any
alterations in the data means running through all references to the array
that fall in the area above the insertion/deletion to 'fix' them.

        This is also why there isn't any room/zone/etc removal code.  It's
a pain in the butt to find the point of insertion and increment up -
realloc doesn't change contents within the minimum of the old and new
sizes.  It's even more of a pain in the butt to locate the point of
deletion, save the state of everything above it, and push it back into the
array after it's been resized in the correct position.

        Hm. Well, I guess you could always use memcpy.  Either way you're
going to be thrashing memory usage for a short amount of time.

        In general, arrays are lots harder to maintain than linked list
addition/removal.  Of course, the payback is lookup time of 1, when you
know what you're looking for.  If you have the ability, arrays are usually
worth your time for frequently accessed lists.


                                                PjD


     +------------------------------------------------------------+
     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     |  http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html  |
     +------------------------------------------------------------+



This archive was generated by hypermail 2b30 : 04/10/01 PDT