Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Demonstrating an intrusive doubly linked list
#pragma once // or use the #ifndef guard
#include <stddef.h> // for offsetof()
typedef struct dl_head_s { // this struct can't be hidden
struct dl_head_s *p[2]; // p[0] points the previous record; p[1] points to the next
} dl_head_t;
// Given a pointer to a struct member, get the pointer to the struct
#define dl_container_of(ptr, type, member) ((type*)((char*)(ptr) - offsetof(type, member)))
static inline void dl_push(dl_head_t *head[2], dl_head_t *p, int dir)
{
dir = !!dir; // make sure dir is either 0 or 1
p->p[0] = p->p[1] = 0;
if (head[0] == 0 && head[1] == 0) head[0] = head[1] = p; // an empty list; then just add
else head[dir]->p[dir] = p, p->p[!dir] = head[dir], head[dir] = p; // push
}
static inline dl_head_t *dl_pop(dl_head_t *head[2], int dir)
{
dl_head_t *p;
dir = !!dir;
if (head[0] == 0 && head[1] == 0) return 0; // an empty list; return a NULL pointer
else if (head[0] == head[1]) p = head[0], head[0] = head[1] = 0; // only one element
else p = head[dir], head[dir] = p->p[!dir], head[dir]->p[dir] = 0; // >1 elements
return p;
}
#include <stdlib.h> // for malloc()
#include <stdio.h> // for printf()
#include "dlist.h"
typedef struct {
int x;
dl_head_t head; // this field forms a double-linked list
} my_elem_t;
int main(void)
{
int i, N = 5;
dl_head_t *head[2] = {0, 0};
for (i = 0; i < N; ++i) {
my_elem_t *p = (my_elem_t*)malloc(sizeof(*p)); // caller controls memory
p->x = i;
dl_push(head, &p->head, 1); // STL's push_back()
}
while (head[0]) {
dl_head_t *p = dl_pop(head, 0); // STL's pop_front()
my_elem_t *q = dl_container_of(p, my_elem_t, head); // pointer to the parent
printf("out: %d\n", q->x);
free(q); // again, caller controls memory
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.