C++ Structure within itself?

Question

I've been trying to port this code to python, but there is something I do not quite understand in C++ (I do know a bit of C++ but this is beyond me):

typedef struct huffnode_s
{
    struct huffnode_s *zero;
    struct huffnode_s *one;
    unsigned char val;
    float freq;
} huffnode_t;

What I don't get is how huffnode_s can be within itself, I've never seen this before and don't quite understand it. What does this mean, and if someone can, what would be the python equivalent?

Answer 1

it does not have a structure in itself. it has a pointer to that structure.

in memory struct huffnode_s would look like (32 bit machine):

---

|------------------ huffnode_s* zero - 4 bytes --------------|

|------------------ huffnode_s* one - 4 bytes----------------|

|unsigned char val - 1 byte + 3 bytes padding=======|

|------------------- float freq - 4 bytes -------------------------|

---

these sizes would vary machine to machine, and how it looks in memory is decided by compiler .

Answer 2

huffnode_s isn't within itself, only pointers to huffnode_s are in there. Since a pointer is of known size, it's no problem.

Answer 3

As others have noted, the references to itself are simply pointers to other instances of that structure.

The pointers within the structure would allow one to connect instances together as a linked list.

Answer 4

This.

class Huffnode(object):
    def __init__(self, zero, one, val, freq):
        """zero and one are Huffnode's, val is a 'char' and freq is a float."""
        self.zero = zero
        self.one = one
        self.val = val
        self.freq = freq

You can then refactor your various C functions to be methods of this class.

Or maybe this.

from collections import namedtuple
Huffnode = namedtuple( 'Huffnode', [ 'zero', 'one', 'val', 'freq' ] )

If you want your C functions to remain functions.

That's it.

h0 = Huffnode(None, None, 'x', 0.0)
h1 = Huffnode(None, None, 'y', 1.0)
h2 = Huffnode(h0, h1, 'z', 2.0)

That's all that's required.

Answer 5

(struct huffnode_s *) declares a pointer to another structure that includes same variables as the structure that it's declared in. See this question.

Answer 6

This is a pointer to a huffnode inside of a huffnode. What this means is that you can say:

huffnode_t *node = ...;
huffnode_t *greatgreatgreatgrandchild = node->zero->zero->zero->zero->zero;

This will compile, and it will work as long as all those huffnode descendents are actually allocated and pointed to correctly.

Pointers are much like object references in JavaScript. They don't actually contain data, they just refer to it. Rest assured that you are not looking at an infinite type.

Answer 7

To add to Carl's answer, the same thing in C++ is also possible:

class Foo {
public:
    Foo() {}

    Foo *anotherFoo;
};   

(Note the above class is silly, but the point is you can have a pointer inside a class that is of the class type)

Answer 8

This is known as a self referential structure and it is exactly what it sounds like: a structure which contains a reference to itself. A common occurrence of this is in a structure which describes a node for a linked list. Each node needs a reference to the next node in the chain.

struct linked_list_node { 
    int data; 
    struct linked_list_node *next; // <- self reference 
};