Create a d-dimensional pointer

Question

We use to indicate a pointer with the symbol *. Iterating the procedure, we obtain a "double" pointer **, a "triple" pointer *** and, more generally, a "d-dimensional" pointer (for each d positive natural number).

Problem: given such a d as an input, define S to be a d-dimensional pointer.

Because I started studying dynamic structures only some days ago, I am unfortunately a bit in trouble with this problem. Does anyone have a suggestion/hint?

Thank you in advance, and my apologies for my probably too basic question.

Ps: I used the word "pointer" without specify its type only for sake of brevity.

Answer 1

This problem has a solution in C as long as two conditions are met:

• The value of d is known at compile time, and
• d has a pre-defined limit, e.g. 10

You can solve this problem by defining a series of macros and "pasting" the value of d as a token:

#define D_PTR(d,T) D_PTR##d(T)
#define D_PTR0(T) T
#define D_PTR1(T) T*
#define D_PTR2(T) T**
#define D_PTR3(T) T***
...
#define D_PTR10(T) T**********

Now you can declare d-dimension pointers like this:

D_PTR(5,int) ptr5 = NULL;

Demo.

Answer 2

There are three distinct ways to solve this:

1. Your d is a compile-time constant. For this case, dasblinkenlight has already given the solution.

2. The hacky-C solution: Just use a cast to get back to the pointer type:

   double* dereferenceDLevels(double* pointer, int d) {
       for(; d--; ) pointer = *(double**)pointer;
       return pointer;
   }
   

   I do not recommend this approach, though. It's just too dirty.

3. You implement your d-level pointers as user defined types:

   typedef struct nLevelPointer {
       int n;
       union {
           nLevelPointer* pointer;
           double value;
       };
   } nLevelPointer;
   
   double nLevelPointer_dereference(nLevelPointer* me) {
       for(int i = me->n; i--; ) me = me->pointer;
       return me->value;
   }
   

   I consider this approach the cleanest and most flexible one. However, it has the trade-off of requiring a significant amount of boilerplate code to make it fly.

Answer 3

Basically the number of * represents the number of indirections to reach the variable. So you have to create d indirections. I assume this has no practical application - that's an answer to a recreative problem.

An indirection in C is an address, a pointer. Creating d indirections means the creation of d addresses to reach a variable data (the space allocated to the variable of type T).

p(d) -> p(d-1) -> ... -> p(1) -> variable

To create dynamically such a structure, you could do it via malloc (replace T with any known type), and - since you may not specify the number of * dynamically to a pointer - requires some C hacking.

So, again, this is not something recommended and is a particularly bad design, especially for inexperienced C developers. Purpose is to show it could be done dynamically, whatever the value of d.

Say T is a double

int d = ...; // from input (d >= 1)
double variable;

double **S = malloc(sizeof(double *) * d); // array of pointers to pointer

S[d-1] = &variable; // last address points to target
int i;
for(i=d-2 ; i>=0 ; i--) S[i] = (double *)&S[i+1]; // previous address
                                                  // points to next location

There is no way to represent an arbitrary number of indirections in C, so S is only a ** to satisfy the compiler requirements, and is cast when necessary.

Let's try with d set to 4 and applying the algorithm above (say T is a double), having

double variable is at address 0100 (decimal), value 3.14
S address given by malloc at  1000
a pointer size being             4
a double  size being             8

variable
v
[8 bytes double value 3.14]
^
0100

S
v
[1004][1008][1012][0100]
^                 ^
1000              1012

Now the structure is in place, how to use/test it? You could create a function that returns the type T (double here), take the S value and d, operate the d indirections and return the variable

double getvariable(double **S, int d) {
    while (--d > 0) S = (double **)*S; // d-1 iterations
    return *(double *)*S;
}

trying it

printf("%lf\n", getvariable(S, d)); // 3.14

to test the above structure without a function, for d == 4, you could create

double ****p = (double ****)*S;
printf("%lf\n", ****p);             // 3.14

Answer 4

Problem: given such a d as an input, define S to be a d-dimensional pointer.

It's possible in C to functionally represent an N dimensional array at run time, if not a pointer with an arbitrary number of levels of indirection. This could be a start (uncompiled, and this utterly ignores any possible alignment issues):

void *allocateArray( unsigned int N, size_t elemSize, unsigned int *dimensions )
{
    if ( N == 1U )
    {
        return( malloc( elemSize * dimensions[ 0 ] ) )
    }

    void *array = malloc( sizeof( void * ) * dimensions[ 0 ] );
    for ( unsigned ii = 0; ii < dimensions[ 0 ]; ii++ )
    {
        array[ ii ] = allocateArray( N - 1, elemSize, &( dimensions[ 1 ] ) );
    }

    return( array );
}

Note, that is not a very efficient way of allocating an N-dimensional array.

You could call it like this:

unsigned dims[] = { 5,7,8,9 };
unsigned d = sizeof( dims ) / sizeof( dims[ 0 ] );
size_t elemSize = sizeof( double );

void *array = allocateArray( d, elemSize, dims );

A varargs solution is probably possible, too.

Dereferencing the array would require something similar. This returns the address of the element dereferenced:

void *dereferenceArray( void *array, unsigned int N,
    size_t elemSize, unsigned int *element )
{
    if ( N == 1U )
    {
        char *tmp = array;
        return( tmp + ( elemSize * element[ 0 ] ) );
    }
    else
    {
        void **tmp = array;
        return( dereferenceArray( tmp[ element[ 0 ] ],
            N - 1, elemSize, &( element[ 1 ] ) ) );
    }
}

It'd be much easier in C++ as you could provide a [] operator to your array object and nest them to build N-dimensional arrays.

Answer 5

You could create the runtime equivalent of a d-indirection pointer by chaining as many void ** pointers as you need. A sparse array could then be built this way:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int main(int argc, char *argv[])
{
    if (argc < 4)
    {
        printf("Call this passing d (dimensions), n (elements for each dim), u (used elements) as parameters\n");
        return 0;
    }
    int d = atoi(argv[1]);
    assert(d > 0);
    int n = atoi(argv[2]);
    assert(n > 0);
    int u = atoi(argv[3]);
    assert(u < n * d);

    // Creating
    void *root = malloc(sizeof(void *) * n);
    memset(root, 0, sizeof(void *) * n);
    srand(time(NULL));
    int i, p, c;
    void **cursor;
    for (int c = 0; c < u; ++c)
    {
        cursor = root;
        for (i = 0; i < d; ++i)
        {
            p = rand() % n; 
            if (cursor[p] == NULL)
            {
                cursor[p] = malloc(sizeof(void *) * n);
                memset(cursor[p], 0, sizeof(void *) * n);
            }
            cursor = cursor[p];
        }
        p = rand() % n;
        if (cursor[p] == NULL)
            cursor[p] = "Hello";
        else
          --c;
    }
    // Traversing
    struct SE
    {
        void * *s;
        int p;
    };
    struct SE *stack = malloc(sizeof(struct SE) * (d + 1));
    for (cursor = root, p = 0, i = 0; ; ++p)
    {
        if (p == n)
        {
            if (i == 0)
                break;
            cursor = stack[--i].s;
            p = stack[i].p;
        }
        else if (cursor[p] != NULL)
        {
            if (i < d)
            {
                stack[i].s = cursor;
                stack[i++].p = p;
                cursor = cursor[p];
                p = -1;
            }
            else
            {
                printf("root");
                for (c = 0; c < i; ++c)
                    printf("[%d]->", stack[c].p);
                printf("[%d]=\"%s\"\n", p, cursor[p]);
            }
        }
    }

    // Tearing down
    for (cursor = root, p = 0, i = 0; ; ++p)
    {
        if (p == n)
        {
            if (i == 0)
                break;
            cursor = stack[--i].s;
            p = stack[i].p;
            free(cursor[p]);
        }
        else if (cursor[p] != NULL && i < d)
        {
            stack[i].s = cursor;
            stack[i++].p = p;
            cursor = cursor[p];
            p = -1;
        }
    }
    free(root);
    free(stack);
    return 0;
}