Re: Linked Lists and Arrays

From: Daniel A. Koepke (dkoepke@california.com)
Date: 05/02/00


On Tue, 2 May 2000, Patrick Dughi wrote:

>         Yep - the biggest problem though is that you can't access and
> throw it around like you can an array.

Technically, you can: it _is_ an array as far as C is concerned.  I don't
see anything, then, you can do with a statically sized array you can't do
here.  Nor anything you can do with a statically sized multi-dimensional
array that you can't do here with as much ease.  The macro use is a bit
heavy and might not be the most superb idea, but it's not difficult to
understand or follow for newbies (AFAICT).

> I always think it's better though to put off that huge amount of work
> with multiple macros which to use eventually requires a decent amount
> of understanding about how the system is setup.

Huge amount of work?  The additional work amounts to:

    /* Changed to use m->rooms, so we can have variable-sized layers. */
    CREATE(m, struct map_data, Z);
    CREATE(m->rooms, struct room_data, X*Y);

    #define COORD(m, x, y)    (((m)->sizeX * (y)) + (x))
    #define MAP(m, x, y, z)   ((m)[z].rooms[COORD(m, x, y)])

Beyond that, I think it masks use of the map space quite well.  Code I
write that does:

    int laddr, z, max = (m->sizeX * m->sizeY);

    for (z = 0; z < m->sizeZ; z++)
        for (laddr = 0; laddr < max; laddr++)
            /* access m[z].rooms[laddr] */

which takes for granted the linear allocation of the memory can just as
easily be written as,

    int x, y, z;

    for (x = 0; x < m->sizeX; x++)
        for (y = 0; y < m->sizeY; y++)
            for (z = 0; z < m->sizeZ; z++)
                /* do something to MAP(m, x, y, z) */

which might be what a newbie is inclined to do.  Of course, this last is
slower than the similar construct with an actual multi-dimensional array
because you don't have to fudge x, y, z to get the unique linear
address.  That's probably not a big deal unless you're doing it a _lot_,
and if you are, then the linear address method will probably be faster
than both, anyway.

I don't see any other cases where you'll have to exploit or understand the
actual nature of m->rooms.  The only thing you need to know is precisely
what you would need to know with an actual multi-dimensional array: the
access MAP(m, x, y, z) returns a single point on the map ("room").  This
is not unlike understanding that world[X] returns a single room in the
world, or array[x][y][z] returns a single point on the map.  But it is
ultimately more flexible, and, I believe, not subject to any significant
increase in code complexity or effort.

Correct me if I'm out of my head, of course.

-dak


     +------------------------------------------------------------+
     | 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