lunaix-os/includes/lunaix/ds/llist.h

   1 /**
   2  * @file llist.h
   3  * @author Lunaixsky
   4  * @brief This doubly linked cyclic list is adopted from Linux kernel
   5  * <linux/list.h>
   6  * @version 0.1
   7  * @date 2022-03-12
   8  *
   9  * @copyright Copyright (c) 2022
  10  *
  11  */
  12 #ifndef __LUNAIX_LLIST_H
  13 #define __LUNAIX_LLIST_H
  14
  15 #include <lunaix/types.h>
  16
  17 struct llist_header
  18 {
  19     struct llist_header* prev;
  20     struct llist_header* next;
  21 };
  22
  23 static inline void
  24 __llist_add(struct llist_header* elem,
  25             struct llist_header* prev,
  26             struct llist_header* next)
  27 {
  28     next->prev = elem;
  29     elem->next = next;
  30     elem->prev = prev;
  31     prev->next = elem;
  32 }
  33
  34 static inline void
  35 llist_init_head(struct llist_header* head)
  36 {
  37     head->next = head;
  38     head->prev = head;
  39 }
  40
  41 static inline void
  42 llist_append(struct llist_header* head, struct llist_header* elem)
  43 {
  44     __llist_add(elem, head->prev, head);
  45 }
  46
  47 static inline void
  48 llist_prepend(struct llist_header* head, struct llist_header* elem)
  49 {
  50     __llist_add(elem, head, head->next);
  51 }
  52
  53 static inline void
  54 llist_insert_after(struct llist_header* head, struct llist_header* elem)
  55 {
  56     __llist_add(elem, head, head->next);
  57 }
  58
  59 static inline void
  60 llist_delete(struct llist_header* elem)
  61 {
  62     elem->prev->next = elem->next;
  63     elem->next->prev = elem->prev;
  64
  65     // make elem orphaned
  66     elem->prev = elem;
  67     elem->next = elem;
  68 }
  69
  70 static inline int
  71 llist_empty(struct llist_header* elem)
  72 {
  73     return elem->next == elem && elem->prev == elem;
  74 }
  75
  76 #define DEFINE_LLIST(name)                                                     \
  77     struct llist_header name = (struct llist_header)                           \
  78     {                                                                          \
  79         .prev = &name, .next = &name                                           \
  80     }
  81
  82 /**
  83  * list_entry - get the struct for this entry
  84  * @ptr:        the &struct list_head pointer.
  85  * @type:       the type of the struct this is embedded in.
  86  * @member:     the name of the list_struct within the struct.
  87  */
  88 #define list_entry(ptr, type, member) container_of(ptr, type, member)
  89
  90 /**
  91  * list_next - get the struct for next entry
  92  * @ptr:        the &struct list_head pointer.
  93  * @type:       the type of the struct this is embedded in.
  94  * @member:     the name of the list_struct within the struct.
  95  */
  96 #define list_next(current, type, member) container_of(current->member.next, type, member)
  97
  98 /**
  99  * list_prev - get the struct for prev entry
 100  * @ptr:        the &struct list_head pointer.
 101  * @type:       the type of the struct this is embedded in.
 102  * @member:     the name of the list_struct within the struct.
 103  */
 104 #define list_prev(current, type, member) container_of(current->member.prev, type, member)
 105
 106 /**
 107  * list_for_each_entry  -       iterate over list of given type
 108  * @pos:        the type * to use as a loop counter.
 109  * @head:       the head for your list.
 110  * @member:     the name of the list_struct within the struct.
 111  */
 112 #define llist_for_each(pos, n, head, member)                                   \
 113     for (pos = list_entry((head)->next, typeof(*pos), member),                 \
 114         n = list_entry(pos->member.next, typeof(*pos), member);                \
 115          &pos->member != (head);                                               \
 116          pos = n, n = list_entry(n->member.next, typeof(*n), member))
 117
 118 struct hlist_node
 119 {
 120     struct hlist_node *next, **pprev;
 121 };
 122
 123 static inline void
 124 hlist_delete(struct hlist_node* node)
 125 {
 126     if (!node->pprev)
 127         return;
 128     *node->pprev = node->next;
 129     node->next = 0;
 130     node->pprev = 0;
 131 }
 132
 133 static inline void
 134 hlist_add(struct hlist_node** head, struct hlist_node* node)
 135 {
 136     node->next = *head;
 137     if (*head) {
 138         (*head)->pprev = &node->next;
 139     }
 140     node->pprev = head;
 141     *head = node;
 142 }
 143 #endif /* __LUNAIX_LLIST_H */