Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)

[Nick Sabalausky]

On Thu, 8 Nov 2012 21:15:17 +0000 (UTC)
Manfred Nowak <svv1999 at hotmail.com> wrote:

> Rob T wrote:
> 
> > In fact, I can define the structure just fine provided that I do
> > not use a template.
> 
> .. and if one uses a template one can get an infinite recursion, 
> because templates include recursion. This is the case in your code.
> 

It is *not* the case in his code. He has three actual instantiated
structs:

R
------------------
1. int value (4 bytes)
2. d_list!R Rlist (size: TBD)

d_list!R
------------------
// **JUST POINTERS**
1. (d_list!R).node* head (4 bytes, assuming -m32)
2. (d_list!R).node* tail (4 bytes, assuming -m32)

(d_list!R).node
------------------
1. (d_list!R)* outer (4 bytes, assuming -m32)
2. R payload (size: TBD)
3. (d_list!R).node* (4 bytes, assuming -m32)
4. (d_list!R).node* (4 bytes, assuming -m32)

What other concrete types are there? *None*. Just those three.

Now, let's expand *all* of the aggregate value types:

R
------------------
1. int value (4 bytes)
2. d_list!R Rlist (size: 8 bytes)
    2.1. (d_list!R).node* head (4 bytes, assuming -m32)
    2.2. (d_list!R).node* tail (4 bytes, assuming -m32)
Total: 4+8 == 12 bytes

d_list!R
------------------
// *JUST POINTERS*
1. (d_list!R).node* head (4 bytes, assuming -m32)
2. (d_list!R).node* tail (4 bytes, assuming -m32)
Total: 4+4 == 8 bytes

(d_list!R).node
------------------
1. (d_list!R)* outer (4 bytes, assuming -m32)
2. R payload (size: 12 bytes)
    2.1. int value (4 bytes)
    2.2. d_list!R Rlist (size: 8 bytes)
        2.2.1. (d_list!R).node* head (4 bytes, assuming -m32)
        2.2.2. (d_list!R).node* tail (4 bytes, assuming -m32)
3. (d_list!R).node* (4 bytes, assuming -m32)
4. (d_list!R).node* (4 bytes, assuming -m32)
Total: 4+12+4+4 == 24 bytes

Now there are NO MORE aggregate types left to be expanded, and ALL 3
types have an exact, FINITE size.

There *IS NO RECURSION* here.