Re: Linked Lists and Arrays

From: Daniel A. Koepke (
Date: 05/01/00

On Mon, 1 May 2000, Patrick Dughi wrote:

>   Now, if you - for some reason - want to allocate memory dynamically
> for a multidimensional array, it gets complicated because dynamic
> allocation of an n-dimensional array actually requires dynamic
> allocation of n 1-dimensional arrays. To allocate a 2-dimensional
> array one must first allocate memory sufficient to hold all the
> elements of the array, then allocate memory for pointers to each row
> of the array.  A for loop will do this pretty well.

You can treat an arbitrary dimensioned array as a single pointer of
size x1 * x2 * ... * xN * sizeof(T).  The only thing you need is a means
to convert from any set of coordinates to a unique linear address.  This
is easy with two dimensions -- anyone who did graphics programming in the
olden days should recognize this:

    #define COORD(m, x, y)   (((m)->sizeX * (y)) + (x))

will return a unique value between zero and m->sizeX*m->sizeY for any
coordinate X between zero and m->sizeX-1, and Y between zero and

Applying this to three dimensions takes a bit more work.  We'll use an
example to lead us into the theory.  In our example, we'll be dealing with
a 320x200x5 three dimensional object.  We know that, were we to treat each
layer (0-4) as a two dimensional rectangle, the area of said rectangle
would be 320x200 (or 64000).  So, to have it all be linear, we need to

        0 - 63999     for layer 1's (x, y) coordinate space
    64000 - 127999    for layer 2's (x, y) coordinate space
   128000 - 255999    for layer 3's (x, y) coordinate space

and so on up until we get to layer 5's coordinate space.  So let's say we
have the coordinate pair (2, 3) in our above mentioned three dimensional

    COORD(cube, 2, 3) = ((320 * 3) + 2) = 962

That's the coordinate's linear address within a two dimensional space.
But when dealing with three dimensions, we're not going to think of that
as its absolute location, but as an _offset_ from the appropriate layer's
address space.  That is, for any given layer, Z, the room (2, 3) on that
layer is the 962nd from the first.  So, really, we're adding the point
address (as returned by our old COORD) to the layer's starting
address.  And if you haven't already figured it out, an easy way to get
a layer's starting address is:

    (m->sizeX * m->sizeY) * z

You can verify this works: for the first layer (0), it returns 0.  For the
second layer (1), it returns 64000.  For the third (2), it returns
128000.  So we can now change our COORD macro to respect this third

    #define RLAS(m, z)         ((m)->sizeX * (m)->sizeY * (z))
    #define COORD(m, x, y, z)  (RLAS(m, z) + (((m)->sizeX * (y)) + (x)))

The RLAS (Reserved Linear Address Space) macro is used as a convenience,
in case we ever want to use it separate of COORD (mainly for debugging
purposes).  To finish it off, we're going to create a MAP macro and
demonstrate the creation and destruction of the map linear memory space:

    #define MAP(m, x, y, z)    ((m)[COORD(m, x, y, z)])

    struct map_data
        int sizeX;
        int sizeY;
        int layers;
        struct room_data *rooms;

    struct room_data
        char *name;
        char *description;
        struct exit_data *exits[NUM_OF_DIRS];
        struct character_data *people;
        struct obj_data *contents;

    struct map_data *create_map(int x, int y, int z)
        struct map_data *retMap;
        CREATE(retMap, struct map_data, 1);

        retMap->sizeX = x;
        retMap->sizeY = y;
        retMap->layers = z;
        CREATE(retMap->rooms, struct room_data, x*y*z);


    void destroy_map(struct map_data *m)
        if (m->rooms) {
            for (x = 0; x < RLAS(m, m->sizeZ); x++)


This is MailerCode.  The author (Daniel A. Koepke) is not liable for its
failure to work under any cause, including acts of God(s), such as
lightning, typhoon, hurricane, or plague of locusts; war; or government,
such as the complete removal of fair use for the consumer, which is where
the US is heading anyway...

-dak : Remember, young Skywalker, always count from zero up.

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

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