Intrusive Linked List Node Offset

Challenge

The Linux kernel uses intrusive doubly-linked lists (struct list_head) embedded directly inside domain structures. The offsetof / container_of idiom recovers the parent container pointer from an embedded node pointer without separate memory allocations.

Your Task

Given the intrusive node:

typedef struct ListNode {
    struct ListNode *next;
    struct ListNode *prev;
} ListNode;

typedef struct {
    int id;
    char name[32];
    ListNode node; // embedded intrusive node
} UserRecord;

Implement list operations and container recovery:

void list_init(ListNode *head);
void list_push_tail(ListNode *head, ListNode *new_node);
UserRecord *user_from_node(ListNode *n);

Rules

1. In list_init:
   • Set head->next = head and head->prev = head (circular empty list).
2. In list_push_tail:
   • Insert new_node right before head (i.e. at the tail): new_node->next = head; new_node->prev = head->prev; head->prev->next = new_node; head->prev = new_node;
3. In user_from_node:
   • If n == NULL, return NULL.
   • Compute offset of node member inside UserRecord using offsetof(UserRecord, node).
   • Subtract that byte offset from (char *)n and cast to UserRecord *.
   • Return the recovered UserRecord *.

Example

ListNode head;
list_init(&head);
UserRecord u = { .id = 42, .name = "Alice" };
list_push_tail(&head, &u.node);
UserRecord *found = user_from_node(head.next); // found->id == 42

Input format

head, new_node, n: ListNode pointers.

Output format

Returns pointer to enclosing UserRecord struct.

Constraints

Must use offsetof from stddef.h to compute container offset.

Starter code

#include <stddef.h>

typedef struct ListNode {
    struct ListNode *next;
    struct ListNode *prev;
} ListNode;

typedef struct {
    int id;
    char name[32];
    ListNode node;
} UserRecord;

void list_init(ListNode *head) {
    (void)head;
}
void list_push_tail(ListNode *head, ListNode *new_node) {
    (void)head; (void)new_node;
}
UserRecord *user_from_node(ListNode *n) {
    (void)n;
    return NULL;
}

Common mistakes

Hardcoding member offsets instead of using offsetof; pointer arithmetic without char* cast.

Edge cases to handle

Empty list has head->next == head; NULL node returns NULL.

Background lessons

• Linked lists
• Structs