malloc for struct with pointer (revisited)

Question

Apologies if this seems like a duplicate question but I'd like some clarification on a previous question I found here regarding allocating heap memory using malloc for a struct containing a pointer. I have found various other questions regarding malloc and structs, but for some reason they all seem to involve people using typedef when defining the struct, I don't know if this changes the context of the question so I want to avoid confusion by asking a new question.

So the answers to this question seems to imply that with a struct such as:

struct Vector {
    double *data;
    size_t size;
};

When creating an instance we should allocate memory space for the struct itself:

struct Vector *retVal = malloc (sizeof (struct Vector));

AND the pointer to data inside the struct:

retVal->data = malloc (sz * sizeof (double));

Problem is I've been reading 'The ANSI C Programming Language' (second edition) by Brian Kernighan and Dannis Ritchie, it's quite an old book but I assumed it was good stuff. Unfortunately it doesn't go into malloc in much detail. I then came across the following code on page 119 which is illustrating an example of how symbol table management (e.g. for the preprocessor) might work. It defines a struct (nlist) for a symbol and the text to replace the symbol with. nlists are stored in a static array (hashtab), using a simple hash function then a modulo array size of the hash to calculate the array index, so there is a pointer to the next nlist if there is a collision:

struct nlist { /* table entry: */
     struct nlist *next; /* next entry in chain */
     char *name; /* defined name */
     char *defn; /* replacement text */
 };

There is then an install function which is used to add a new nlist to hashtab:

struct nlist *lookup(char *);
char *strdup(char *);

/* install: put (name, defn) in hashtab */
 struct nlist *install(char *name, char *defn)
 {
     struct nlist *np;
     unsigned hashval;
     if ((np = lookup(name)) == NULL) { /* not found */
            np = (struct nlist *) malloc(sizeof(*np));
         if (np == NULL || (np->name = strdup(name)) == NULL)
            return NULL;
         hashval = hash(name);
         np->next = hashtab[hashval];
         hashtab[hashval] = np;
     } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;
     return np;
 }

This is the point at which I started to weep and rock backwards and forwards, drooling as my brain melted out of my ears. There doesn't appear to be any malloc action going on for the pointers to next, name or defn in the nlist struct. Is this right or wrong?

Thanks.

PS the lookup function is:

/* lookup: look for s in hashtab */
 struct nlist *lookup(char *s)
 {
     struct nlist *np;
     for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np; /* found */
     return NULL; /* not found */
 }

Answer 1

There are several parts to your question:

There doesn't appear to be any malloc action going on for the pointers to next, name or defn in the nlist struct. Is this right or wrong?

You have seen from the comments that both name and defn have space allocated to hold the associated string by virtue of strdup allocating for you. (you are therefore on the hook to free both name and defn when they are no longer needed.)

The crux of the question, and what seems to be the source of your confusion, is the next pointer for the linked-list. As Ahmad correctly points out, a pointer is a data type, just the same as an int or char. (the storage size differs depending on the operating system, but generally you will find 4-byte pointers on x86 and 8-byte pointers on x86_64. there are corner-cases with embedded systems, etc.)

Just as an int can hold an integer and a char can hold a character without further allocation, a pointer can hold a memory address without further allocation. If you look at your linked list, specifically, how the next pointer is used, and what the next pointer holds, you will see that next is used to hold nothing but the address of the node that follows:

    +----+      +----+      +----+
    |1st |      |2nd |      |3rd |
    |node|  +-->|node|  +-->|node|
    |    |  |   |    |  |   |    |
    |next|--+   |next|--+   |next|-->...
    +----+      +----+      +----+

The nodes themselves are allocated:

np = (struct nlist *) malloc(sizeof(*np));    [see: footnote 1]

When each node is allocated, space for the next pointer is also allocated. There is no need to further allocate next. It can happily hold the address of the next node all by itself. You only need allocate a block of memory for what is pointed to by the pointer, not the pointer itself.

What you are allocating for may be pointers in many cases, for example:

#define NUMPTRS 10

char **list;
list = malloc (NUMPTRS * sizeof *list);

but if you look closely, it follows the rule. You are not allocating space to hold the address of list, you are allocating 10 pointers to hold the address of something else.

Hopefully that adds to what Ahmad sought to explain and makes it a little clearer in your mind. Let me know if you have any questions.

footnotes:

1. There is no need to cast the return of malloc.

    np = malloc (sizeof *np);

is fine by itself. see Do I cast the result of malloc?

Answer 2

If I have understood your question, here is the answer. (by the way K&R is the best) A pointer holds a memory address, okay? when you allocate a, say, int *, or char *, they all allocate the same space in memory to reference respectively an int and a char. How? In a 32bit system if you take sizeof from both int * and char * you'll find out they have already allocated 4bytes of memory. why? because they must be big enough to hold the largest address of Ram in a 32bit computer. So if they have already taken a space why would we need to use malloc? that's because for a string of size 5 you'll need 6 bytes of memory ( 5 + '\0' ). you allocate that memory using malloc then you write down the address of the first byte inside your char *. We won't write it directly inside the char * because those 4bytes are meant to store the address of a string. right? but let's say you want to just reference another struct in the system(not creating one) then you just put the address of the first byte of the allocated struct inside you struct pointer. Hopefully I've understood your question, otherwise, feel free to comment.