0

I'm studying some C code just for understanding and I found a pointer with an index between [] like it was an array (as " pointer[i] "); I don't understand what does it mean or how does it work

this is a piece of the code where i found it:

struct turing_machine_t{
    struct linked_list_t*** transitions;
    bool* acceptors;
    unsigned int max_steps;
    unsigned int num_states;
};

void delete_turing_machine(struct turing_machine_t* tm){ 
    int i,j;
    for(i = 0; i < tm->num_states; i++){
        if(tm->transitions[i] != NULL){
            for(j = 0; j < ALPHABET_SIZE; j++){
                struct linked_list_t* tl = tm->transitions[i][j];

                //after here there are just some free

It is from a turing machine simulator but that doesn't matter really; If I'm correct, transition is a triple pointer, but what does it mean transition[i] and transition[i][j]? If it isn't an array what is the meaning of those indexes?

wattbatt
  • 447
  • 2
  • 13
  • 1
    Search for "pointer arithmetic" in the internet – andreee Aug 01 '19 at 20:32
  • See also [With arrays why is it the case that `a[5] == 5[a]`?](https://stackoverflow.com/questions/381542/with-arrays-why-is-it-the-case-that-a5-5a) – Charles Duffy Aug 01 '19 at 20:50
  • 1
    The following are all equivalent: `a[b]`, `b[a]`, `*(a+b)`. One of `a` or `b` should have a pointer or array type, and the other should have an integer type. In practice, when `a[b]` is used, `a` normally has a pointer or array type and `b` an integer type, but you can reverse them if you want to confuse people. – Tom Karzes Aug 01 '19 at 20:50
  • You might like the [comp.lang.c faq](http://c-faq.com/) especially section 6. – pmg Aug 01 '19 at 21:05
  • See also https://stackoverflow.com/questions/43542407/whats-the-difference-among-array-array-and-array0-in-c-language/43542554 – davmac Aug 03 '19 at 02:28

2 Answers2

1

If a pointer ptr points to a contiguous group of objects then ptr[i] would refer to the i+1th element of that group just as it would if ptr were an array. That's probably the case with tm->transitions and tm->transitions[i].

Awais Chishti
  • 395
  • 2
  • 19
0

tl;dr arrays behave similarly to pointers, and you can use array notation on pointers.

transition is a triple pointer. That means it's

a pointer to
a pointer to
a pointer to
a `struct linked_list_t`

It can also be interpreted as a 3D array, because that's actually how arrays work behind the scenes. The following two syntaxes are functionally identical:

int a = array[index];
int a = *(array + index);

Arrays are slightly different because if they were created in-scope then whatever IDE or static analysis tool you're using will generally keep track of their range, but the compiler treats them the same way. This works because, when you do arithmetic on a pointer like this, the compiler basically multiplies index by sizeof(*array) (which is the same as sizeof(array[0]).

That is, array + 1 is a pointer to the memory address immediately after whatever is allocated for array. array + 2 is a pointer to the memory address after that, assuming it's the same size as array. array + 3 is the memory address after that, and so on ad infinitum.

So, the bracket operation is basically syntactic sugar for pointer arithmetic. The expression transitions[i][j] can be considered like:

  1. transitions is an array with pointer-sized elements
  2. Get the value of the ith pointer-sized element from transitions (that is, *(transitions + i))
  3. The value we just got (let's call it pointer_val) is itself a pointer to an array of pointer-sized elements.
  4. Get the value of the jth pointer-sized element from pointer_val (that is, *(pointer_val + j), or, longhand, *(*(transitions + i) + j))
  5. The value we just got is a pointer to a linked_list_t, which we assign to a variable tl.

Notice that there are three asterisks in the definition of transitions. We're accounting for all of them here - the first two are in the array indexing, and the third is in the linked_list_t* that we're assigning.

Green Cloak Guy
  • 23,793
  • 4
  • 33
  • 53
  • 6
    *Arrays are just pointers in disguise* is a **dangerous** half-truth at best, if not a flat-out lie. As an aside, indexing is a pointer-operation, not an array one. – Deduplicator Aug 01 '19 at 20:55
  • The indexing operator is *exactly* syntactic sugar for pointer arithmetic combined with dereferencing the result. That's how it is **defined**. When one operand happens to designate an array, the normal automatic conversion to a pointer applies. – John Bollinger Aug 01 '19 at 20:59
  • so, writing `struct linked_list_t transitions[num_states][ALPHABET SIZE][something];` would make the code work the same way? – wattbatt Aug 01 '19 at 21:19
  • 1
    @wattbatt Not really, because that's a *definition* rather than an *access*. Rather than saying "this is a pointer to a pointer to a pointer", here you're defining all the sizes of everything in advance. This mostly affects when and how memory is allocated (because now `transitions` is an array of blocks of memory exactly as big as `ALPHABET_SIZE * something * sizeof(struct linked_list_t)`. Pointer arithmetic accounts for this, so the end usage ends up being the same. But the memory allocation is completely different, which would affect other parts of the code. – Green Cloak Guy Aug 01 '19 at 21:42
  • @Deduplicator I more-or-less know the architecture of C, but I haven't done much practical programming on it, so if you could expand on that assertion (and edit the answer to improve it for anyone who looks at it in the future) it would be useful. Thanks for your input! – Green Cloak Guy Aug 01 '19 at 21:45
  • 1
    @GreenCloakGuy: Arrays are not pointers in disguise - array *expressions* get converted ("decay") to pointer expressions as necessary. The subscript operator `a[i]` is defined in terms of pointer operations - `*(a + i)`, it's just that if `a` is an expression of array type, it's converted to a pointer type (and the value is the address of the first element) before the larger expression is evaluated. – John Bode Aug 01 '19 at 23:31
  • 1
    @GreenCloakGuy an array is an object comprising a series of elements, whereas a pointer is just a single value referring to the location of another single value. Of course a pointer can point to an element within an array, but it's certainly not the case that an array and pointer are almost the same thing or that, as you put it, "arrays are just pointers in disguise". Confusion often arises because when you refer to an array by name, there is in most (but not all) contexts an implicit conversion to a pointer (pointing to the first element). This does not mean arrays _are_ pointers! – davmac Aug 02 '19 at 07:49