python3.13/internal/pycore_llist.h

0001 // A doubly-linked list that can be embedded in a struct.
0002 //
0003 // Usage:
0004 //  struct llist_node head = LLIST_INIT(head);
0005 //  typedef struct {
0006 //      ...
0007 //      struct llist_node node;
0008 //      ...
0009 //  } MyObj;
0010 //
0011 //  llist_insert_tail(&head, &obj->node);
0012 //  llist_remove(&obj->node);
0013 //
0014 //  struct llist_node *node;
0015 //  llist_for_each(node, &head) {
0016 //      MyObj *obj = llist_data(node, MyObj, node);
0017 //      ...
0018 //  }
0019 //
0020
0021 #ifndef Py_INTERNAL_LLIST_H
0022 #define Py_INTERNAL_LLIST_H
0023
0024 #include <stddef.h>
0025
0026 #ifdef __cplusplus
0027 extern "C" {
0028 #endif
0029
0030 #ifndef Py_BUILD_CORE
0031 #  error "Py_BUILD_CORE must be defined to include this header"
0032 #endif
0033
0034 struct llist_node {
0035     struct llist_node *next;
0036     struct llist_node *prev;
0037 };
0038
0039 // Get the struct containing a node.
0040 #define llist_data(node, type, member) (_Py_CONTAINER_OF(node, type, member))
0041
0042 // Iterate over a list.
0043 #define llist_for_each(node, head) \
0044     for (node = (head)->next; node != (head); node = node->next)
0045
0046 // Iterate over a list, but allow removal of the current node.
0047 #define llist_for_each_safe(node, head) \
0048     for (struct llist_node *_next = (node = (head)->next, node->next); \
0049          node != (head); node = _next, _next = node->next)
0050
0051 #define LLIST_INIT(head) { &head, &head }
0052
0053 static inline void
0054 llist_init(struct llist_node *head)
0055 {
0056     head->next = head;
0057     head->prev = head;
0058 }
0059
0060 // Returns 1 if the list is empty, 0 otherwise.
0061 static inline int
0062 llist_empty(struct llist_node *head)
0063 {
0064     return head->next == head;
0065 }
0066
0067 // Appends to the tail of the list.
0068 static inline void
0069 llist_insert_tail(struct llist_node *head, struct llist_node *node)
0070 {
0071     node->prev = head->prev;
0072     node->next = head;
0073     head->prev->next = node;
0074     head->prev = node;
0075 }
0076
0077 // Remove a node from the list.
0078 static inline void
0079 llist_remove(struct llist_node *node)
0080 {
0081     struct llist_node *prev = node->prev;
0082     struct llist_node *next = node->next;
0083     prev->next = next;
0084     next->prev = prev;
0085     node->prev = NULL;
0086     node->next = NULL;
0087 }
0088
0089 // Append all nodes from head2 onto head1. head2 is left empty.
0090 static inline void
0091 llist_concat(struct llist_node *head1, struct llist_node *head2)
0092 {
0093     if (!llist_empty(head2)) {
0094         head1->prev->next = head2->next;
0095         head2->next->prev = head1->prev;
0096
0097         head1->prev = head2->prev;
0098         head2->prev->next = head1;
0099         llist_init(head2);
0100     }
0101 }
0102
0103 #ifdef __cplusplus
0104 }
0105 #endif
0106 #endif /* !Py_INTERNAL_LLIST_H */