Created
January 19, 2020 02:50
-
-
Save attractivechaos/1036f9ec253b831d146530009256329b to your computer and use it in GitHub Desktop.
Demonstrating an intrusive 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 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; | |
} |
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 "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