Skip to content

Instantly share code, notes, and snippets.

@attractivechaos attractivechaos/clist.h
Last active Jan 19, 2020

Embed
What would you like to do?
Demonstration of a circular doubly linked list
#pragma once // or use the #ifndef guard
#include <stddef.h> // for offsetof()
typedef struct cl_head_s {
struct cl_head_s *prev, *next;
} cl_head_t;
static inline void cl_insert_after(cl_head_t *q, cl_head_t *p)
{ // insert _p_ after _q_; _q_ is in the list
p->prev = q, p->next = q->next, q->next = p, p->next->prev = p;
}
static inline void cl_push(cl_head_t **head, cl_head_t *p, int push_back)
{
if (*head) cl_insert_after(*head, p);
else *head = p, p->prev = p->next = p;
if (push_back) *head = p;
}
static inline cl_head_t *cl_erase(cl_head_t *p)
{ // erase _p_ in the list; return p->prev, or 0 if p is the only one
cl_head_t *q = p->prev;
if (p == q) return 0; // _p_ is the only one in the list
q->next = p->next, q->next->prev = q;
return q;
}
static inline cl_head_t *cl_pop(cl_head_t **head, int pop_back)
{
cl_head_t *p;
if (*head == 0) return 0;
p = pop_back? *head : (*head)->next;
*head = cl_erase(p);
return p;
}
// Given a pointer to a struct member, get the pointer to the struct
#define cl_container_of(ptr, type, member) ((type*)((char*)(ptr) - offsetof(type, member)))
#include <stdlib.h> // for malloc()
#include <stdio.h> // for printf()
#include "clist.h"
typedef struct {
int x;
cl_head_t head; // this field forms a double-linked list
} my_elem_t;
static inline my_elem_t *my_elem_create(int x)
{
my_elem_t *p = (my_elem_t*)malloc(sizeof(*p));
p->x = x;
return p;
}
int main(void)
{
cl_head_t *head = 0;
cl_push(&head, &my_elem_create(3)->head, 1);
cl_push(&head, &my_elem_create(4)->head, 1);
cl_push(&head, &my_elem_create(2)->head, 0);
cl_push(&head, &my_elem_create(5)->head, 1);
cl_push(&head, &my_elem_create(1)->head, 0);
while (head) {
cl_head_t *p = cl_pop(&head, 1);
my_elem_t *q = cl_container_of(p, my_elem_t, head);
printf("out: %d\n", q->x); // in the order of 5, 4, 3, 2, 1
free(q);
}
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.