Need help deconstructing RosettaStone Huffman Code

Question

I'm taking a class in C with a couple of friends. We're doing a project on Huffman Encoding and I am trying to understand the Rosetta stone version of the code. I think I've figured most of it out, but I don't understand a couple of variables.

typedef struct node_t {
    struct node_t *left, *right;
    int freq;
    char c;
} *node;

struct node_t pool[256] = { { 0 } };
node qqq[255], *q = qqq - 1;

Can someone please explain to me what *node means, and what node qqq[255] is, and what *q = qqq-1 means.

The only reason I ask is I think I am making an error somewhere in my understanding because I don't really get the relationships between these pointer nodes.

Answer 1

The declaration:

typedef struct node_t { ... } *node;

defines the node type as pointer to node_t structures (which appear to be typical binary search nodes). So while pool[] is an array of node_t structures, qqq[] is an array of pointers (to said structures). Now think of qqq as a pointer to the start of some (stack reserved) bytes to hold a bunch of pointers (255*sizeof(node) or 255*sizeof(struct node_t*) bytes).

Then

node ..., *q = ...

is similar in that it defines q as a pointer to nodes, but without reserving any bytes. Instead, q is initialized to point to qqq-1 which is probably intended to mean "point to sizeof(node) before qqq".

(While this last piece of pointer arithmetic probably works, pointing outside of qqq is not a good idea because adding an subtracting pointers is only defined behaviour when resulting address is within defined range.)

Supposedly, what follows is a loop where q is a pre-incremented iterator traversing qqqs data.