| 1 |
// A doubly-linked list that can be embedded in a struct. |
| 2 |
// |
| 3 |
// Usage: |
| 4 |
// struct llist_node head = LLIST_INIT(head); |
| 5 |
// typedef struct { |
| 6 |
// ... |
| 7 |
// struct llist_node node; |
| 8 |
// ... |
| 9 |
// } MyObj; |
| 10 |
// |
| 11 |
// llist_insert_tail(&head, &obj->node); |
| 12 |
// llist_remove(&obj->node); |
| 13 |
// |
| 14 |
// struct llist_node *node; |
| 15 |
// llist_for_each(node, &head) { |
| 16 |
// MyObj *obj = llist_data(node, MyObj, node); |
| 17 |
// ... |
| 18 |
// } |
| 19 |
// |
| 20 |
|
| 21 |
#ifndef Py_INTERNAL_LLIST_H |
| 22 |
#define Py_INTERNAL_LLIST_H |
| 23 |
|
| 24 |
#include <stddef.h> |
| 25 |
|
| 26 |
#ifdef __cplusplus |
| 27 |
extern "C" { |
| 28 |
#endif |
| 29 |
|
| 30 |
#ifndef Py_BUILD_CORE |
| 31 |
# error "Py_BUILD_CORE must be defined to include this header" |
| 32 |
#endif |
| 33 |
|
| 34 |
struct llist_node { |
| 35 |
struct llist_node *next; |
| 36 |
struct llist_node *prev; |
| 37 |
}; |
| 38 |
|
| 39 |
// Get the struct containing a node. |
| 40 |
#define llist_data(node, type, member) (_Py_CONTAINER_OF(node, type, member)) |
| 41 |
|
| 42 |
// Iterate over a list. |
| 43 |
#define llist_for_each(node, head) \ |
| 44 |
for (node = (head)->next; node != (head); node = node->next) |
| 45 |
|
| 46 |
// Iterate over a list, but allow removal of the current node. |
| 47 |
#define llist_for_each_safe(node, head) \ |
| 48 |
for (struct llist_node *_next = (node = (head)->next, node->next); \ |
| 49 |
node != (head); node = _next, _next = node->next) |
| 50 |
|
| 51 |
#define LLIST_INIT(head) { &head, &head } |
| 52 |
|
| 53 |
static inline void |
| 54 |
llist_init(struct llist_node *head) |
| 55 |
{ |
| 56 |
head->next = head; |
| 57 |
head->prev = head; |
| 58 |
} |
| 59 |
|
| 60 |
// Returns 1 if the list is empty, 0 otherwise. |
| 61 |
static inline int |
| 62 |
llist_empty(struct llist_node *head) |
| 63 |
{ |
| 64 |
return head->next == head; |
| 65 |
} |
| 66 |
|
| 67 |
// Appends to the tail of the list. |
| 68 |
static inline void |
| 69 |
llist_insert_tail(struct llist_node *head, struct llist_node *node) |
| 70 |
{ |
| 71 |
node->prev = head->prev; |
| 72 |
node->next = head; |
| 73 |
head->prev->next = node; |
| 74 |
head->prev = node; |
| 75 |
} |
| 76 |
|
| 77 |
// Remove a node from the list. |
| 78 |
static inline void |
| 79 |
llist_remove(struct llist_node *node) |
| 80 |
{ |
| 81 |
struct llist_node *prev = node->prev; |
| 82 |
struct llist_node *next = node->next; |
| 83 |
prev->next = next; |
| 84 |
next->prev = prev; |
| 85 |
node->prev = NULL; |
| 86 |
node->next = NULL; |
| 87 |
} |
| 88 |
|
| 89 |
// Append all nodes from head2 onto head1. head2 is left empty. |
| 90 |
static inline void |
| 91 |
llist_concat(struct llist_node *head1, struct llist_node *head2) |
| 92 |
{ |
| 93 |
if (!llist_empty(head2)) { |
| 94 |
head1->prev->next = head2->next; |
| 95 |
head2->next->prev = head1->prev; |
| 96 |
|
| 97 |
head1->prev = head2->prev; |
| 98 |
head2->prev->next = head1; |
| 99 |
llist_init(head2); |
| 100 |
} |
| 101 |
} |
| 102 |
|
| 103 |
#ifdef __cplusplus |
| 104 |
} |
| 105 |
#endif |
| 106 |
#endif /* !Py_INTERNAL_LLIST_H */ |