if struct and its contained structs are not made of primivitive types, the how size get evaluated. How to use it correct way

Question

If I have a struct like

struct list_head {
    struct list_head *next, *prev;
};

so I like to know what is the point of this struct?

what next and priv can contain. since its a pointer. I really don't know its size

if I have simple code like below

struct list_head 
{
    struct list_head *next, *prev;
} *p,v;
printf("%lu %lu %lu ...",sizeof(p),sizeof(*p),sizeof(v));

the output shows

8 16 16 .

but the thing I am confused with is how I can use the struct. What I will assigned to it

Up until now I was under the impression that we do and must need primitive types to define a type. For example this makes sense

struct a{
    int *x;
    char b[100];
 };
 struct b{
    struct a *p;
   }

so in above struct the child contains primitive types. In what way I get the output of my first program 8 16 16 ... how my struct got even evaluated. is there anything I am missing? p is pointer but how 8 is printed? who defined the size of struct a to be 8 Obviously I didn't.

Also how to use my first example struct

this one

struct list_head {
    struct list_head *next, *prev;
};

 

Answer 1

This doesn't hold any data by itself. It's used as a substructure in other structures, e.g.

struct offset {
    struct list_head list;
    unsigned offset;
};

This makes offset a doubly-linked list.

They could have done it by including a generic data pointer in the list_head structure:

struct list_head {
    struct list_head *next, *prev;
    void *data;
};

But this would waste memory with an extra pointer, and it's also less efficient because there will be frequent cache misses when you have to follow the pointer. Putting the links directly in the structure avoids these problems.

Answer 2

This is a Linux kernel list.

It is dedicated to be placed inside a struct as a member.

Typically there is one object that "owns" the head of list and the children objects that owns list node:

struct parent {
  int a;
  struct list_head head;
};

struct child {
  int a;
  struct list_head node;
  int b;
};

New elements are added using list_add function:

struct parent p;
INIT_LIST_HEAD(&p.head);
struct child c1, c2;
list_add(&c1.node, &p.head);
list_add(&c2.node, &p.head);

Elements can remove themself from the list with list_del. For example c2 could remove itself from the list with:

list_del(&c2.node);

The typical iteration over list would be:

struct parent *p = ...;
for (struct list_head *n = p->head.next; p != &p->head; p = p->next) {
   struct child *c = list_entry(p, struct child, node);
   ... do stuff with c ...
}

Note that list_entry is used to convert a pointer to struct member to the pointer to parenting struct. It is a wrapper around container_of macro which is not strictly conforming. So it should be used with care.

---

EDIT

The Linux implementation of lists is quite complex. Below one can find a simpler implementation:

#pragma once

#include <stddef.h>

struct list {
    struct list *next, *prev;
};

static inline void list_add(struct list *node, struct list *head)
{
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

static inline void list_del(struct list *node)
{
    node->next->prev = node->prev;
    node->prev->next = node->next;
}

#define list_entry(ptr,type,member) \
    ((type*)(((char*)ptr) - offsetof(type,member)))

static inline void list_init(struct list *node)
{
    node->next = node;
    node->prev = node;
}

#define DEFINE_LIST(name) struct list name = { .next = &name, .prev = &name }

#define LIST_FOREACH(it,head) \
    for (struct list *it = (head)->next; it != (head); it = it->next)