Last active
January 19, 2020 05:35
-
-
Save attractivechaos/7b4b82bc19cf3a97008a7d8196032b0d to your computer and use it in GitHub Desktop.
Demonstration of a circular doubly linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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