Multiple levels of indirection 
Author Message
 Multiple levels of indirection

I shall use conspicuous terminology to be ANSI specific!

When one allows ones imagination to freestyle savor the c language one
rather intriging notion to me, are the possibilities for pointers to
pointers... to pointers, etc. In my reading I occasionally see 2 levels of
indirection. I wonder if there are valid cases in ANSI C for more than 2
levels of indirection. What {*filter*} data-structures might there be that
utilize a great many levels of indirection?
It's late and I'm jiving on to bed. All replies appreciated.
Henry Williams



Sun, 15 Apr 2001 03:00:00 GMT  
 Multiple levels of indirection

Quote:

> I shall use conspicuous terminology to be ANSI specific!

This is *very nice* of you and highly apreciated ;-)

Quote:
> When one allows ones imagination to freestyle savor the c language

Ok, now you've got me wondering how one savors the C language in
freestyle :-)
I do savor C in freestanding sitting down.

Quote:
> one
> rather intriging notion to me, are the possibilities for pointers to
> pointers... to pointers, etc.

Don't get carried away. Stop while you stiil can.

Quote:
> In my reading I occasionally see 2 levels of
> indirection. I wonder if there are valid cases in ANSI C for more than 2
> levels of indirection. What {*filter*} data-structures might there be that
> utilize a great many levels of indirection?

Ok, jokes aside, there are indeed rare but serious resons for
using tripple pointers. For instance consider a function for
dynamically allocating a 2D array. What you typically do is
allocate an array of pointers and allocate one block of memory
for each pointer (as explained in the FAQ). The 2D array is
in this case represented by a pointer pointer ("**").  If you
want to write a create function where the array is returned
via a function parameter, you must have a pointer to the object
being allocated, ie. a tripple pointer ("***").

This gets excessivly wierd when you try to apply the same logic
to a 3D array :-) The array itself is stored in a tripple pointer
(ie. an array of pointers to pointers) and writing as a paramter
to a create function you would need a quadruple pointer. Entering
the world of dynamically allocated multi dimensional array will
almost certainly end up in heavy pointer (ab)use.

Stephan
(initiator of the campaign against grumpiness in c.l.c)



Mon, 16 Apr 2001 03:00:00 GMT  
 Multiple levels of indirection

Quote:
>Ok, jokes aside, there are indeed rare but serious resons for
>using tripple pointers. For instance consider a function for
>dynamically allocating a 2D array. ...

Here is another example.  Suppose you have a linked list data
structure of "name=value" pairs, i.e,

        struct nvlist {
                struct nvlist *nv_next;
                char    *nv_name;
                char    *nv_value;
        };

Now, suppose that a list of this type is to be built dynamically,
with new entries appended to the end of the list.  The slow way
to append to a list, given a "head" pointer, is:

        struct nvlist *mkoptions = NULL;

        /* Add a filled-in option to the list.  opt->nv_next must be NULL. */
        void append(struct nvlist *opt) {
                struct nvlist *p;

                if (mkoptions == NULL)
                        mkoptions = opt;
                else {
                        for (p = mkoptions; p->nv_next != NULL; p = p->nv_next)
                                continue;
                        p->nv_next = opt;
                }
        }

This function has O(N^2) behavior.

A much faster way is to keep a pointer to the pointer that currently
is NULL and thus marks the end of the list:

        struct nvlist *mkoptions = NULL;
        struct nvlist **nextmkopt = &mkoptions;

        void append(struct nvlist *opt) {
                *nextmkopt = opt;
                nextmkopt = &opt->nv_next;
        }

But now the "append" operation is small enough (two lines of code)
to just insert in-line in the code that creates an option.  If this
code is to work on more than one list, it will need a pointer to the
"nextmkopt" pointer:

        void append(struct nvlist ***p, const char *name, const char *value) {
                struct nvlist *nv;

                if ((nv = malloc(sizeof *nv)) == NULL)
                        panic("out of memory");
                nv->nv_name = name;
                nv->nv_value = value;
                nv->nv_next = NULL;
                **p = nv;
                *p = &nv->nv_next;
        }

and now you have a triple-indirect.
--
In-Real-Life: Chris Torek, Berkeley Software Design Inc

Antispam notice: unsolicited commercial email will be handled at my
consulting rate; pyramid-scheme mail will be forwarded to the FTC.



Mon, 16 Apr 2001 03:00:00 GMT  
 Multiple levels of indirection

Quote:

> When one allows ones imagination to freestyle savor the c language one
> rather intriging notion to me, are the possibilities for pointers to
> pointers... to pointers, etc. In my reading I occasionally see 2 levels of
> indirection. I wonder if there are valid cases in ANSI C for more than 2
> levels of indirection.

More than two: sure, though they're pretty rare.
More than three: getting pretty dubious.

In theory, of course, one might have occasion to use arbitrarily
many levels of indirection.  I'm reminded of Steven Pinker's
discussion on the topic of "the longest sentence":

        By the same logic that shows that there are an infinite
        number of integers -- if you ever think you have the
        largest integer, just add 1 to it and you will have
        another -- there must be an infinite number of
        sentences.  The Guinness Book of World Records once
        claimed to recognize the longest English sentence:
        a 1,300-word stretch in William Faulkner's novel
        Absalom, Absalom! that begins:

                They both bore it as though in deliberate
                flagellant exaltation...

        I am tempted to achieve immortality by submitting the
        following record-breaker:

                Faulkner wrote, "They both bore it as though
                in deliberate flagellant exaltation..."

        But it would only be the proverbial fif{*filter*} minutes of
        fame, for soon I could be bested by:

                Pinker wrote that Faulkner wrote, "They both bore
                it as though in deliberate flagellant exaltation..."

        And that record, too, would fall when someone submitted:

                Who cares that Pinker wrote that Faulkner wrote,
                "They both bore it as though in deliberate
                flagellant exaltation..."?

        [The Language Instinct, 1994, ch. 4]

In C, whenever we wish to pass a value to a function by reference
(perhaps so that the function can "return" a new value via the
reference parameter), we use pointers.  To pass an integer to a
function by reference, we use type pointer-to-int.  But sometimes
we might have occasion to pass a pointer by reference, in which
case the parameter could have type pointer-to-pointer-to-int.
And if we ever had to pass a pointer to a pointer by reference...

I think I've used triple pointers perhaps three or four times
(ever), usually for this reason.

Rumor has it that there's a 7-level pointer somewhere in the
Linux kernel, but I don't believe it.

                                        Steve Summit



Tue, 17 Apr 2001 03:00:00 GMT  
 Multiple levels of indirection
Stephan Wilms wrote in a message to Henry Williams:

 SW> This gets excessivly wierd when you try to apply the same logic to
 SW> a 3D array :-) The array itself is stored in a tripple pointer (ie.
 SW>
 SW> an array of pointers to pointers) and writing as a paramter to a
 SW> create function you would need a quadruple pointer.

How about introducing a new operator in C9X, comparable to the variable
length arrays, the variable indirection level pointer:



*/

Where 20 can be replaced by any constant or variable expression of type
size_t, e.g.:

#include <stdlib.h>
#include <assert.h>

void foo(size_t bar)
{

   /* etc. */

Quote:
}

This would allow for an easy method to dynamically allocate arrays with
a variable number of dimensions.

It would also get us around this limitation:

       5.2.4.1  Translation limits

<snip>

          - 12 pointer, array, and  function  declarators  (in  any
            combinations)   modifying   an  arithmetic,  structure,
            union, or incomplete type in a declaration

And immediately allow upto SIZE_MAX levels of indirection... oh joy :-)

greetings,
Tom



Tue, 17 Apr 2001 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. indirection levels warning

2. error: different levels of indirection

3. Multiple Indirection (Pointer Arithmatic)

4. Newbie Question: Multiple indirection

5. multiple indirection + arrays

6. Maloc and multiple indirection

7. Looking for info on multiple indirection/GC in C.

8. Multiple Indirection (Pointer Arithmatic)

9. Multiple levels of implementation and implementation inheritance

10. problems with multiple levels of virtual base classes

11. Multiple Level Dialog with Back, Next buttons

12. CRichCtrl with multiple levels of Undo

 

 
Powered by phpBB® Forum Software